1、信息論基礎(chǔ),李剛 北京科技大學(xué)信息工程學(xué)院 ,信息論基礎(chǔ)教程,李亦農(nóng) 李梅 編著 北京郵電大學(xué)出版社,目錄,第一章 緒論 第二章 信息的度量 第三章 信源及信息熵 第四章 信道及信道容量 第五章 無失真信源編碼 第六章 有噪信道編碼 第七章 限失真信源編碼,1.1 信息的概念 1.2 信息論研究對象、目的和內(nèi)容,第一章 緒論,1.1 信息的概念,信息論是通信的數(shù)學(xué)基礎(chǔ)，它是隨著通信技術(shù)的發(fā)展而形成和發(fā)展起來的一門新興橫斷學(xué)科。信息論創(chuàng)立標(biāo)志是1948年Claude Shannon(香農(nóng))發(fā)表論文“A Mathematical Theory of Communication”。在這篇文章中香農(nóng)創(chuàng)

2、造性的采用概率論的方法來研究通信中的問題，并且對信息給予了科學(xué)的定量描述，第一次提出了信息熵的概念。 1928年，哈特萊(Hartley)首先提出了用對數(shù)度量信息的概念。一個消息所含有的信息量用它的可能值的個數(shù)的對數(shù)來表示。,香農(nóng),(香農(nóng))信息： 信息是事物運(yùn)動狀態(tài)或存在方式的不確定性的描述。 可運(yùn)用研究隨機(jī)事件的數(shù)學(xué)工具概率來測度不確定性大小。 在信息論中，我們把消息用隨機(jī)事件表示，而發(fā)出這些消息的信 源則用隨機(jī)變量來表示。,我們把某個消息 出現(xiàn)的不確定性的大小，定義為自信息，用這 個消息出現(xiàn)的概率的對數(shù)的負(fù)值來表示： 自信息同時表示這個消息所包含的信息量，也就是最大能夠給予 收信者的信息量

3、。如果消息能夠正確傳送，收信者就能夠獲得這 么大小的信息量。,信源所含有的信息量定義為信源發(fā)出的所有可能消息的平均不確定性，香農(nóng)把信源所含有的信息量稱為信息熵。自信息的統(tǒng)計平均定義為信源熵，即： 這里的q表示信源消息的個數(shù)。信息熵表示信源的平均不確定性的大小，同時表示信源輸出的消息所含的平均信息量。因此，雖然信源產(chǎn)生的消息可能會含有不同的信息量。 在收信端，信源的不確定性得到部分或全部消除，收信者就得到信息。信息在數(shù)量上等于通信前后“不確定性”的消除量(減少量),1.2 信息論研究對象、目的和內(nèi)容,信息論研究對象 廣義的通信系統(tǒng)，它把所有的信息流通系統(tǒng)都抽象成如下模型：,圖1.1 通信系統(tǒng)模型

4、,這個通信系統(tǒng)主要分成五個部分： (1). 信源 顧名思義，信源是產(chǎn)生消息和消息序列的源。 (2). 編碼器 編碼就是把消息變成適合在信道傳輸?shù)奈锢砹啃盘枴?編碼器可分為信源編碼器和信道編碼器。信源編碼目的是提高通信系統(tǒng)有效性 和提高信息傳輸?shù)目煽啃浴?shí)際通信系統(tǒng)中，可靠性和有效性常常相互矛盾 。 (3). 信道 信道是指通信系統(tǒng)把載荷消息的信號從發(fā)送端送到接收端的媒介或通道， 是包括收發(fā)設(shè)備在內(nèi)的物理設(shè)施。 (4). 譯碼器 譯碼就是把信道輸出的已迭加了干擾的編碼信號進(jìn)行反變換，變成信宿 能夠接受的消息。譯碼器也可分成信源譯碼器和信道譯碼器。 (5). 信宿 信宿是消息傳送的對象，即接受消息

5、的人或機(jī)器。,信息論研究的是關(guān)于這個通信系統(tǒng)的最根本、最本質(zhì)的問題。例如： . 什么是信息？如何度量信息？ . 怎樣確定信源中含有多少信息量？ . 對于一個信道，它傳輸信息量的最高極限(信道容量)是多少？ . 為了能夠無失真的傳輸信源信息，對信源編碼時所需的最少的碼 符號數(shù)是多少？(無失真信源編碼即香農(nóng)第一定理) . 在有噪信道中有沒有可能以接近信道容量的信息傳輸率傳輸信息 而錯誤概率幾乎為零？(有噪信道編碼即香農(nóng)第二定理) . 如果對信源編碼時允許一定量的失真，所需的最少的碼符號數(shù)又 是多少？(限失真信源編碼即香農(nóng)第三定理),目前，對信息論的研究內(nèi)容一般有三種理解： (1)狹義信息論： 又稱

6、香農(nóng)信息論。主要通過數(shù)學(xué)描述與定量分析，研究通信系統(tǒng)從信源到信宿 的全過程，包括信息的測度、信道容量以及信源和信道編碼理論等問題，強(qiáng)調(diào) 通過編碼和譯碼使收、發(fā)兩端聯(lián)合最優(yōu)化，并且以定理的形式證明極限的存在 這部分內(nèi)容是信息論的基礎(chǔ)理論。 (2)一般信息論：也稱工程信息論。 主要也是研究信息傳輸和處理問題，除香農(nóng)信息論的內(nèi)容外，還包括噪聲理論 信號濾波和預(yù)測、統(tǒng)計檢測和估計、調(diào)制理論、信息處理理論以及保密理論等 (3)廣義信息論： 不僅包括上述兩方面內(nèi)容，而且包括所有與信息有關(guān)的自然和社會領(lǐng)域，如模 式識別、計算機(jī)翻譯、心理學(xué)、遺傳學(xué)、神經(jīng)生理學(xué)、語言學(xué)、語義學(xué)甚至包 括社會學(xué)中有關(guān)信息的問題。

7、,2.1 自信息和互信息 2.2 平均自信息 2.3 平均互信息,第二章 信息的度量,關(guān)于信息的度量有幾個重要的概念： （1）自信息：一個事件(消息)本身所包含的信息量，它是由事件的不確 定性決定的。比如拋擲一枚硬幣的結(jié)果是正面這個消息所包含的信息量 （2）互信息：一個事件所給出關(guān)于另一個事件的信息量，比如今天下 雨所給出關(guān)于明天下雨的信息量。 （3）平均自信息（信息熵）：事件集（用隨機(jī)變量表示）所包含的平 均信息量，它表示信源的平均不確定性。比如拋擲一枚硬幣的試驗(yàn)所包 含的信息量。 （4）平均互信息：一個事件集所給出關(guān)于另一個事件集的平均信息量 比如今天的天氣所給出關(guān)于明天的天氣的信息量。,

8、2.1 自信息和互信息,2.1.1 自信息 隨機(jī)事件的自信息量 是該事件發(fā)生概率 的函數(shù)，并且應(yīng)該滿 足以下公理化條件： 1. 是 的嚴(yán)格遞減函數(shù)。當(dāng) 時， ，概率 越小，事件發(fā)生的不確定性越大，事件發(fā)生后所包含的自信息量越大 2極限情況下當(dāng) =0時， ；當(dāng) =1時， =0。 3另外，從直觀概念上講，由兩個相對獨(dú)立的不同的消息所提供的 信息量應(yīng)等于它們分別提供的信息量之和。 可以證明，滿足以上公理化條件的函數(shù)形式是對數(shù)形式。,定義2.1 隨機(jī)事件的自信息量定義為該事件發(fā)生概率的對數(shù)的負(fù)值。 事件 的概率為 ，則它的自信息定義為： 從圖2.1種可以看到上述信息量的定義正 是滿足上述公理性條件的函

9、數(shù)形式。 代表兩種含義：當(dāng)事件發(fā)生以前，等于 事件發(fā)生的不確定性的大??；當(dāng)事件發(fā) 生以后，表示事件所含有或所能提供的 信息量。,圖2.1 自信息量,自信息量的單位與所用對數(shù)的底有關(guān)。 （1）常取對數(shù)的底為2，信息量的單位為比特(bit，binary unit)。當(dāng) =1/2時， =1比特，即概率等于1/2的事件具有1比特的自信 息量。 （2）若取自然對數(shù)（對數(shù)以e為底），自信息量的單位為奈特（nat， natural unit）。 1奈特= 比特=1.443比特 （3）工程上用以10為底較方便。若以10為對數(shù)底，則自信息量的單位 為哈特萊（Hartley）。1哈特萊= 比特=3.322比特 （

10、4）如果取以r為底的對數(shù)（r1），則 = 進(jìn)制單位 1r進(jìn)制單位= 比特,2.1.2 互信息,定義2.2 一個事件 所給出關(guān)于另一個事件 的信息定義為互信息，用 表示。 互信息 是已知事件 后所消除的關(guān)于事件 的不確定性，它等 于事件 本身的不確定性 減去已知事件 后對 仍然存在的不確 定性 。 互信息的引出，使信息得到了定量的表示，是信息論發(fā)展的一個重要的 里程碑。,2.2 平均自信息,2.2.1 平均自信息(信息熵)的概念 自信息量是信源發(fā)出某一具體消息所含有的信息量，發(fā)出的消息不同所 含有的信息量不同。因此自信息量不能用來表征整個信源的不確定度。 我們定義平均自信息量來表征整個信源的不確

11、定度。平均自信息量又稱 為信息熵、信源熵，簡稱熵。 因?yàn)樾旁淳哂胁淮_定性，所以我們把信源用隨機(jī)變量來表示，用隨機(jī)變 量的概率分布來描述信源的不確定性。通常把一個隨機(jī)變量的所有可能 的取值和這些取值對應(yīng)的概率 稱為它的概率空間。,定義2.3 隨機(jī)變量X的每一個可能取值的自信息 的統(tǒng)計平均值定 義為隨機(jī)變量X的平均自信息量: 這里q為的所有X可能取值的個數(shù)。 熵的單位也是與所取的對數(shù)底有關(guān)，根據(jù)所取的對數(shù)底不同，可以是比 特/符號、奈特/符號、哈特萊/符號或者是r進(jìn)制單位/符號。通常用比 特/符號為單位。 一般情況下，信息熵并不等于收信者平均獲得的信息量，收信者不能全 部消除信源的平均不確定性，獲

12、得的信息量將小于信息熵。,2.2.2 熵函數(shù)的性質(zhì),信息熵 是隨機(jī)變量X的概率分布的函數(shù)，所以又稱為熵函數(shù)。如果 把概率分布 ，記為 ，則熵函數(shù)又可以 寫成概率矢量 的函數(shù)的形式，記為 。 熵函數(shù) 具有以下性質(zhì)： 1.對稱性： 對稱性說明熵函數(shù)僅與信源的總體統(tǒng)計特性有關(guān)。,2. 確定性： 在概率矢量中，只要有一個分量為1，其它分量必為0，它們對熵的 貢獻(xiàn)均為0，因此熵等于0。也就是說確定信源的不確定度為0。 3. 非負(fù)性： 對確定信源，等號成立。信源熵是自信息的數(shù)學(xué)期望，自信息是非 負(fù)值，所以信源熵必定是非負(fù)的。 4. 擴(kuò)展性： 這個性質(zhì)的含義是增加一個基本不會出現(xiàn)的小概率事件，信源的熵 保持

13、不變。 5. 連續(xù)性： 即信源概率空間中概率分量的微小波動，不會引起熵的變化。,6. 遞增性 這性質(zhì)表明，假如有一信源的n個元素的概率分布為 ，其中某個元素 又被劃分成m個元素，這m個元素的概率之和等于元素 的概率，這樣得到的新信源的熵增加，熵增加了一項(xiàng)是由于劃分產(chǎn)生的不確定性。 7. 極值性： 式中n是隨機(jī)變量X的可能取值的個數(shù)。 極值性表明離散信源中各消息等概率出現(xiàn)時熵最大，這就是最大離散熵定理。連續(xù)信源的最大熵則與約束條件有關(guān)。,8. 上凸性: 是嚴(yán)格的上凸函數(shù)，設(shè) 則對于任意小于1的正數(shù) 有以下不等式成立： 凸函數(shù)在定義域內(nèi)的極值必為極大值，可以利用熵函數(shù)的這個性質(zhì) 可以證明熵函數(shù)的極

14、值性。,直觀來看，隨機(jī)變量的不確定程度并不都是一樣的。香農(nóng)指出，存在這樣的不 確定性度量，它是隨機(jī)變量的概率分布的函數(shù)，而且必須滿足三個公理性條件 1. 連續(xù)性條件： 應(yīng)是 的連續(xù)函數(shù)； 2. 等概時為單調(diào)函數(shù)： 應(yīng)是 的增函數(shù)； 3. 遞增性條件：當(dāng)隨機(jī)變量的取值不是通過一次試驗(yàn)而是若干次試驗(yàn)才最 后得到時，隨機(jī)變量在各次試驗(yàn)中的不確定性應(yīng)該可加，且其和始終與 通過一次試驗(yàn)取得的不確定程度相同，即： 其中,2.2.3 聯(lián)合熵與條件熵,一個隨機(jī)變量的不確定性可以用熵來表示，這一概念可以方便地推廣到 多個隨機(jī)變量。 定義2.4 二維隨機(jī)變量 的概率空間表示為 其中： 滿足概率空間的非負(fù)性和完備性

15、：,二維隨機(jī)變量 的聯(lián)合熵定義為聯(lián)合自信息的數(shù)學(xué)期望，它是二維隨 機(jī)變量 的不確定性的度量。 定義2.5 給定 時， 的條件熵： 其中， 表示已知 時， 的平均不確定性。,各類熵之間關(guān)系：,1聯(lián)合熵與信息熵、條件熵的關(guān)系： 這個關(guān)系可以方便地推廣到N個隨機(jī)變量的情況： 稱為熵函數(shù)的鏈規(guī)則。 推論：當(dāng)二維隨機(jī)變量X,Y相互獨(dú)立時，聯(lián)合熵等于X,Y各自熵之和： 2條件熵與信息熵的關(guān)系： 3聯(lián)合熵和信息熵的關(guān)系： 當(dāng)X、Y相互獨(dú)立時等號成立。,2.3 平均互信息,2.3.1 平均互信息的概念 為了從整體上表示從一個隨機(jī)變量Y所給出關(guān)于另一個隨機(jī)變量 的信 息量，我們定義互信息 在的 聯(lián)合概率空間中的

16、統(tǒng)計平均值為 隨機(jī)變量X和Y間的平均互信息： 定義2.6,2.3.2 平均互信息的性質(zhì),1.非負(fù)性: 平均互信息是非負(fù)的，說明給定隨機(jī)變量Y后，一般來說總能消除一 部分關(guān)于X的不確定性。 2.互易性(對稱性)： 對稱性表示從Y中獲得的關(guān)于X信息量等于從X中獲得的關(guān)于Y信息量 3.平均互信息和各類熵的關(guān)系: 當(dāng) 統(tǒng)計獨(dú)立時，,4. 極值性： 極值性說明從一個事件提取關(guān)于另一個事件的信息量，至多只能是另一個 事件的平均自信息量，不會超過另一事件本身所含的信息量。 5. 凸函數(shù)性： 定理2.1 當(dāng)條件概率分布 給定時，平均互信息 是輸入分 布 的上凸函數(shù)。 定理2.2 對于固定的輸入分布 ，平均互信

17、息量 是條件概率 分布 的下凸函數(shù)。,2.3.3 數(shù)據(jù)處理定理,為了表述數(shù)據(jù)處理定理，需要引入三元隨機(jī)變量 的平均條件互信息 和平均聯(lián)合互信息的概念。 定義2.7 平均條件互信息 它表示隨機(jī)變量 給定后，從隨機(jī)變量 所得到的關(guān)于隨機(jī)變量 的信息量 定義2.8 平均聯(lián)合互信息 它表示從二維隨機(jī)變量 所得到得關(guān)于隨機(jī)變量 的信息量。,定理2.3 (數(shù)據(jù)處理定理) 如果隨機(jī)變量 構(gòu)成一個馬爾可夫鏈，則有以下關(guān)系成立： 等號成立的條件是對于任意的 ，有： 數(shù)據(jù)處理定理再一次說明，在任何信息傳輸系統(tǒng)中，最后獲得的信息至 多是信源所提供的信息，如果一旦在某一過程中丟失一些信息，以后的 系統(tǒng)不管如何處理，如

18、不觸及丟失信息的輸入端，就不能再恢復(fù)已丟失 的信息，這就是信息不增性原理，它與熱熵不減原理正好對應(yīng)，反映了 信息的物理意義。,3.1 信源的分類及其數(shù)學(xué)模型 3.2 離散單符號信源 3.3 離散多符號信源 *3.4 連續(xù)信源,第三章 信源及信息熵,信源(Information Source)是信息的來源，是產(chǎn)生消息(符號)、時間離散的消息序列(符號序列)以及時間連續(xù)的消息的來源。 信源輸出的消息都是隨機(jī)的，因此可用概率來描述其統(tǒng)計特性。 在信息論中，用隨機(jī)變量X、隨機(jī)矢量X、隨機(jī)過程 分別表示 產(chǎn)生消息、消息序列以及時間連續(xù)消息的信源。 信源的主要問題： 1如何描述信源（信源的數(shù)學(xué)建模問題）

19、2怎樣計算信源所含的信息量 3怎樣有效的表示信源輸出的消息，也就是信源編碼問題,3.1 信源的分類及其數(shù)學(xué)模型,信源分類有多種方法，根據(jù)信源輸出的消息在時間和取值上是離散或連續(xù)進(jìn)行分類：,表3.1 信源的分類,我們還可以根據(jù)各維隨機(jī)變量的概率分布是否隨時間變化將信源分為 平穩(wěn)信源和非平穩(wěn)信源，根據(jù)隨機(jī)變量間是否統(tǒng)計獨(dú)立將信源分為有 記憶信源和無記憶信源。 一個實(shí)際信源的統(tǒng)計特性往往是相當(dāng)復(fù)雜的，要想找到精確的數(shù)學(xué)模 型很困難。實(shí)際應(yīng)用時常常用一些可以處理的數(shù)學(xué)模型來近似。隨機(jī) 序列，特別是離散平穩(wěn)隨機(jī)序列是我們研究的主要內(nèi)容。,隨機(jī)序列,3.2 離散單符號信源,輸出單個離散取值的符號的信源稱為

20、離散單符號信源。它是最簡單、 最基本的信源，是組成實(shí)際信源的基本單元。用離散隨機(jī)變量表示。 信源所有可能輸出的消息及其對應(yīng)的概率組成的二元序?qū)?稱為信源的概率空間： 信源輸出的所有消息自信息的統(tǒng)計平均值定義為信源的平均自信息量 (信息熵)，它表示離散單符號信源的平均不確定性：,3.3 離散多符號信源,定義3.1：對于隨機(jī)變量序列 ，在任意兩個不同時刻 和 ( 和 為大于1的任意整數(shù))信源發(fā)出消息的概率分布完全相同 即對于任意的 ， 和 具有相同的概率分布。也就是 即各維聯(lián)合概率分布均與時間起點(diǎn)無關(guān)的信源稱為離散平穩(wěn)信源。,對于離散多符號信源, 我們引入熵率的概念，它表示信源輸出的符號 序列中，

21、平均每個符號所攜帶的信息量。 定義3.2 隨機(jī)變量序列中，對前N個隨機(jī)變量的聯(lián)合熵求平均： 稱為平均符號熵。如果當(dāng) 時上式極限存在，則 稱為 熵率，或稱為極限熵，記為：,3.3.1 離散平穩(wěn)無記憶信源,離散平穩(wěn)無記憶信源輸出的符號序列是平穩(wěn)隨機(jī)序列，并且符號之間 是無關(guān)的，即是統(tǒng)計獨(dú)立的。假定信源每次輸出的是N長符號序列，則 它的數(shù)學(xué)模型是N維離散隨機(jī)變量序列： ， 并且每個隨機(jī)變量之間統(tǒng)計獨(dú)立。同時，由于是平穩(wěn)信源，每個隨機(jī) 變量的統(tǒng)計特性都相同，還可把一個輸出N長符號序列的信源記為： 根據(jù)統(tǒng)計獨(dú)立的多維隨機(jī)變量聯(lián)合熵與信息熵之間的關(guān)系，可推出： 離散平穩(wěn)無記憶信源的熵率：,3.3.2 離散

22、平穩(wěn)有記憶信源,實(shí)際信源往往是有記憶信源。 對于相互間有依賴關(guān)系的N維隨機(jī)變量 的聯(lián)合熵存在以下關(guān)系（熵函數(shù)的鏈規(guī)則） ： 定理3.1 對于離散平穩(wěn)信源，有以下幾個結(jié)論： （1）條件熵 隨N的增加是遞減的； （2）N給定時平均符號熵大于等于條件熵，即 （3）平均符號熵 隨N的增加是遞減的； （4）如果 ，則 存在，并且,有一類信源，信源在某時刻發(fā)出的符號僅與在此之前發(fā)出的有限個符 號有關(guān)，而與更早些時候發(fā)出的符號無關(guān)，這稱為馬爾可夫性，這類 信源稱為馬爾可夫信源。馬爾可夫信源可以在N不很大時得到 。如 果信源在某時刻發(fā)出的符號僅與在此之前發(fā)出的m個符號有關(guān)，則稱為 m階馬爾可夫信源，它的熵率：

23、,（馬爾可夫性）,（平穩(wěn)性）,通常記作,3.3.3 馬爾可夫信源,馬爾可夫信源是一類相對簡單的有記憶信 源，信源在某一時刻發(fā)出某一符號的概率 除與該符號有關(guān)外，只與此前發(fā)出的有限 個符號有關(guān)。因此我們把前面若干個符號 看作一個狀態(tài)，可以認(rèn)為信源在某一時刻 發(fā)出某一符號的概率除了與該符號有關(guān)外 只與該時刻信源所處的狀態(tài)有關(guān)，而與過 去的狀態(tài)無關(guān)。信源發(fā)出一個符號后，信 源所處的狀態(tài)即發(fā)生改變，這些狀態(tài)的變 化組成了馬氏鏈。,圖3.1 馬爾可夫信源,對于一般的 階馬爾可夫信源，它的概率空間可以表示成： 令 ，從而得到馬爾可夫信 源的狀態(tài)空間： 狀態(tài)空間由所有狀態(tài)及狀態(tài)間的狀態(tài)轉(zhuǎn)移概率組成。通過引入

24、狀態(tài)轉(zhuǎn) 移概率，可以將對馬爾可夫信源的研究轉(zhuǎn)化為對馬爾可夫鏈的研究。,下面計算遍歷的m階馬爾可夫信源的熵率。 當(dāng)時間足夠長后，遍歷的馬爾可夫信源可以視作平穩(wěn)信源來處理，又 因?yàn)閙階馬爾可夫信源發(fā)出的符號只與最近的m個符號有關(guān)，所以極限 熵 等于條件熵 。 對于齊次遍歷的馬爾可夫鏈，其狀態(tài) 由 唯一確定，因此有 所以,3.3.4 信源的相關(guān)性和剩余度,根據(jù)定理3.1可得 由此看出，由于信源輸出符號間的依賴關(guān)系也就是信源的相關(guān)性使信 源的實(shí)際熵減小。信源輸出符號間統(tǒng)計約束關(guān)系越長，信源的實(shí)際熵 越小。當(dāng)信源輸出符號間彼此不存在依賴關(guān)系且為等概率分布時，信 源的實(shí)際熵等于最大熵 。 定義3.3 一個

25、信源的熵率(極限熵)與具有相同符號集的最大熵的比 值稱為熵的相對率： 信源剩余度為：,信源的剩余度來自兩個方面，一是信源符號間的相關(guān)性，相關(guān)程度越大 符號間的依賴關(guān)系越長，信源的實(shí)際熵越小，另一方面是信源符號分布 的不均勻性使信源的實(shí)際熵越小。 為更經(jīng)濟(jì)有效地傳送信息，需要盡量壓縮信源的剩余度，壓縮剩余度的 方法就是盡量減小符號間相關(guān)性，且盡可能的使信源符號等概率分布。 從提高信息傳輸效率的觀點(diǎn)出發(fā)，人們總是希望盡量去掉剩余度。但從 提高抗干擾能力角度來看，卻希望增加或保留信源的剩余度，因?yàn)槭Ｓ?度大的消息抗干擾能力強(qiáng)。 信源編碼是減少或消除信源的剩余度以提高信息的傳輸效率，而信道編 碼則通過

26、增加冗余度來提高信息傳輸?shù)目垢蓴_能力。,*3.4 連續(xù)信源,3.4.1 連續(xù)信源的微分熵 連續(xù)隨機(jī)變量的取值是連續(xù)的，一般用概率密度函數(shù)描述其統(tǒng)計特征 單變量連續(xù)信源的數(shù)學(xué)模型為 ，并滿足 ， 是實(shí)數(shù)域，表示 的取值范圍。 對于取值范圍有限的連續(xù)信源還可以表示成： ，并滿足 ，（a,b）是 的取值范圍。 通過對連續(xù)變量的取值進(jìn)行量化分層，可以將連續(xù)隨機(jī)變量用離散隨 機(jī)變量來逼近。量化間隔越小，離散隨機(jī)變量與連續(xù)隨機(jī)變量越接近 當(dāng)量化間隔趨于0時，離散隨機(jī)變量就變成了連續(xù)隨機(jī)變量。通過這種 方式，我們來推導(dǎo)連續(xù)隨機(jī)變量的熵。,定義連續(xù)信源的微分熵為： 微分熵又稱為差熵。雖然已不能代表連續(xù)信源的平

27、均不確定性，也不 能代表連續(xù)信源輸出的信息量，但是它具有和離散熵相同的形式，也 滿足離散熵的主要特性，比如可加性，但是不具有非負(fù)性。 同樣，我們可以定義兩個連續(xù)隨機(jī)變量的聯(lián)合熵： 以及條件熵,3.4.2 連續(xù)信源的最大熵,離散信源當(dāng)信源符號為等概分布時有最大熵。連續(xù)信源微分熵也有極 大值，但是與約束條件有關(guān)，當(dāng)約束條件不同時，信源的最大熵不同 我們一般關(guān)心的是下面兩種約束下的最大熵。 定理3.1 在輸出幅度受限時，服從均勻分布的隨機(jī)變量X具有最大輸出熵。 定理3.2 對于平均功率受限的連續(xù)隨機(jī)變量，當(dāng)服從高斯分布時具有最大熵。 （對于均值為m ，方差為 的連續(xù)隨機(jī)變量，平均功率 p=直流功率+

28、交流功率= ）,3.4.3 連續(xù)信源的熵功率,均值為零，平均功率限定為p的連續(xù)信源當(dāng)服從高斯分布時達(dá)到最大熵 也就是說，高斯信源的熵值與p有確定的對應(yīng)關(guān)系： 現(xiàn)在假定限定的平均功率為p，某連續(xù)信源的熵為h(X)，則與它具有相 同熵的高斯信源的平均功率 定義為熵功率即 所以， ，當(dāng)該連續(xù)信源為高斯信源時等號成立。 的大小可表示連續(xù)信源剩余的大小。如果熵功率等于信源平均功率 表示信源沒有剩余；熵功率和信源平均功率相差越大，說明信源的剩 余越大。信源平均功率和熵功率之差 稱為連續(xù)信源的剩余度。,4.1 信道的分類 4.2 離散單符號信道及其信道容量 4.3 離散多符號信道及其信道容量 4.4 組合信

29、道及其信道容量 *4.5 連續(xù)信道及其信道容量 *4.6 波形信道及其信道容量,第四章 信道及其信道容量,信道是指信息傳輸?shù)耐ǖ?，包括空間傳輸和時間傳輸。我們在實(shí)際通 信中所利用的各種物理通道是空間傳輸信道的最典型的例子，時間傳 輸是指將信息保存，在以后讀取，如磁帶、光盤等在時間上將信息進(jìn) 行傳輸?shù)男诺?。有時我們把為了某種目的而使信息不得不經(jīng)過的通道 也看作信道，這里最關(guān)鍵的是信道有一個輸入以及一個與輸入有關(guān)的 輸出。至于信道本身的物理結(jié)構(gòu)可能是千差萬別的，信息論研究的信 道其輸入點(diǎn)和輸出點(diǎn)在一個實(shí)際物理通道中所處位置的選擇完全取決 于研究的目的。關(guān)于信道的主要問題有： 1.信道的建模（信道的

30、統(tǒng)計特性的描述） 2.信道容量的計算 3.在有噪信道中能不能實(shí)現(xiàn)可靠傳輸？怎樣實(shí)現(xiàn)可靠傳輸？,4.1 信道的分類,信息論不研究信號在信道中傳輸?shù)奈锢磉^程，假定信道的傳輸特性已 知，這樣信道就可以用圖4.1所示的抽象的數(shù)學(xué)模型來描述。在信息論 中，信道通常表示成： ，即信道輸入隨機(jī)變量X、輸出隨 機(jī)變量Y以及在輸入已知的情況下，輸出的條件概率分布 。 根據(jù)實(shí)際應(yīng)用的需要，信道有幾種分類方法： (1)按其輸入/輸出信號在幅度和時間 上的取值是離散或連續(xù)來劃分 如表4.1所示：,圖4.1 信道模型,表4.1 按其輸入/輸出信號在幅度和時間上的取值是離散或連續(xù)來劃分 （2）按其輸入/輸出信號之間關(guān)系的

31、記憶特性分為有記憶信道和 無記憶信道。 （3）按輸入/輸出信號之間的關(guān)系是否確定關(guān)系分為有噪聲信道 和無噪聲信道。,（4）另外，根據(jù)信道輸入和輸出的個數(shù)可分為 兩端信道（單用戶信道）：只有一個輸入端和一個輸出端的單 向通信的信道。 多端信道（多用戶信道）：雙向通信或三個或更多個用戶之間 相互通信的情況。 本課程主要研究兩端信道的情況。 （5）根據(jù)信道的統(tǒng)計特性是否隨時間變化分為： 恒參信道（平穩(wěn)信道）：信道的統(tǒng)計特性不隨時間變化。 衛(wèi)星通信信道在某種意義下可以近似為恒參信道。 隨參信道（非平穩(wěn)信道）：信道的統(tǒng)計特性隨時間變化。 如短波通信中，其信道可看成隨參信道。 本課程主要研究恒參信道的情況

32、。,4.2 離散單符號信道及其信道容量,4.2.1 離散單符號信道的數(shù)學(xué)模型 信道的輸入、輸出都取值于離散符號集，且都用一個隨機(jī)變量來表示 的信道就是離散單符號信道。 設(shè)離散單符號信道的輸入隨機(jī)變量為 ，輸出隨機(jī)變 量為 ，由于信道中存在干擾，因此輸入符號在傳輸中 將產(chǎn)生錯誤，這種信道干擾對傳輸?shù)挠绊懣捎脗鬟f概率 描述： 信道傳遞概率實(shí)際上是一個傳遞概率矩陣，稱為信道矩陣，記為：,為了表述簡便，常常寫成,下面推導(dǎo)一般離散單符號信道的一些概率關(guān)系： （1）輸入輸出隨機(jī)變量的聯(lián)合概率分布為 則有 其中， 是信道傳遞概率，即輸入為 ，通過信道傳輸輸出 的概率，通常稱為前向概率。它是由于信道噪聲引起的

33、，所 以通常用它描述信道噪聲的特性。而 是已知信道輸出符號 ，輸入符號為 的概率，稱為后向概率。有時把 稱為輸入 符號的先驗(yàn)概率。而對應(yīng)的把 稱為輸入符號的后驗(yàn)概率。,（2）由全概率公式，可從先驗(yàn)概率和信道傳遞概率求輸出符號概率： 寫成向量的形式： 或記成 （3）根據(jù)貝葉斯公式，可由先驗(yàn)概率和信道的傳遞概率求后向概率：,4.2.2 信道容量的概念,平均互信息 是接收到輸出符號集 后所獲得的關(guān)于輸入符號集 的信息量。信源的不確定性為 ，由于干擾的存在，接收端收到 后對信源仍然存在的不確定性為 ，又稱為信道疑義度。信宿所消除的關(guān)于信源的不確定性，也就是獲得的關(guān)于信源的信息為 ，它是平均意義上每傳送

34、一個符號流經(jīng)信道的信息量，從這個意義上來說，平均互信息又稱為信道的信息傳輸率，通常用 表示。即 有時我們所關(guān)心的是信道在單位時間內(nèi)平均傳輸?shù)男畔⒘?。如果平均傳輸一個符號為t秒，則信道平均每秒鐘傳輸?shù)男畔⒘繛?一般稱為信息傳輸速率。,比特/符號,比特/秒,對于固定的信道，總存在一種信源（某種輸入概率分布），使信道平均傳輸一個符號接收端獲得的信息量最大，也就是說對于每個固定信道都有一個最大的信息傳輸率，這個最大的信息傳輸率即為信道容量，而相應(yīng)的輸入概率分布稱為最佳輸入分布。 定義4.1 信道容量為平均互信息對于輸入概率分布的最大值： 單位依所用的對數(shù)底不同可以是比特/符號、奈特/符號等。 若平均傳

35、輸一個符號需要t秒鐘，則信道在單位時間內(nèi)平均傳輸?shù)淖畲笮畔⒘?信道容量是信道傳送信息的最大能力的度量，信道實(shí)際傳送的信息量必然不大于信道容量。,圖4.3 表示不同的二元對稱信道，其 傳遞概率p不同，信道容量也不同。 當(dāng)p=1/2時，是一種最壞的信道，這 時C=0，即該信道不能傳遞任何信 息，信息全部損失在信道中了。而當(dāng) p=0 或p=1時，C=1，這是最好的情 況，信道能夠無失真?zhèn)魉托旁葱畔ⅰ?圖4.3 BSC的信道容量,4.2.3 幾種特殊信道的信道容量,1.具有擴(kuò)展性能的無損信道 無損信道是一個輸入對應(yīng)多個輸出。 如圖4.4所示，信道矩陣為 無損信道信道矩陣中每一列只有一個非 零元素，接收

36、到信道輸出符號后對輸入 符號將不存在不確定性。,圖4.4 無損信道,2.具有歸并性能的無噪信道 無噪信道是一個輸出對應(yīng)多個輸入。 如圖4.5所示，信道矩陣為 無噪信道每一行只有一個非零元素1， 信道矩陣元素非零即1。已知信道輸 入符號，必能確定輸出符號。,圖4.5 無噪信道,3.具有一一對應(yīng)關(guān)系的無噪無損信道 無噪無損信道輸入、輸出之間有確定的一 一對應(yīng)關(guān)系，即 。 信道傳遞概率為： 如圖4.6所示，信道矩陣為： 無噪無損信道每一行、每一列只有一個“1” 已知 X后對Y不存在不確定性，收到 Y后對 X也不存在不確定性。,圖4.6 無噪無損信道,4.2.4 離散對稱信道的信道容量,離散信道中有一

37、類特殊的信道，其特點(diǎn)是信道矩陣具有行對稱性，利 用這個對稱性我們可以簡化信道容量的計算。 定義4.2 若信道矩陣中，每行都是第一行元素的不同排列，則稱此 類信道為行對稱信道。 定義4.3 若信道矩陣中，不僅每行都是第一行元素的不同排列，而 且每列都是第一列元素的不同排列，這類信道稱為對稱信道。 定義4.4 若信道矩陣中，每行都是第一行元素的不同排列，每列并不 都是第一列元素的不同排列，但是可以按照信道矩陣的列將信道矩陣 劃分成若干對稱的子矩陣，則稱這類信道為準(zhǔn)對稱信道。,定義4.5 若對稱信道中輸入符號和輸出符號個數(shù)相同，且信道中總 的錯誤概率為p，對稱地平均分配給r-1個輸出符號，r為輸入輸

38、出符號 的個數(shù)，即信道矩陣為 則稱此信道為強(qiáng)對稱信道或均勻信道。,二元對稱信道就是r=2的均勻信道。一般信道的信道矩陣中各行之和為1 但各列之和不一定等于1，而均勻信道中各列之和亦等于1。 定理4.1 對于對稱信道，當(dāng)輸入分布為等概分布時，輸出分布必能達(dá) 到等概分布。 定理4.2 若一個離散對稱信道具有r個輸入符號，s個輸出符號，則當(dāng) 輸入為等概分布時達(dá)到信道容量，且 其中 為信道矩陣中的任一行。 推論：均勻信道的信道容量為,當(dāng)輸入為等概分布時，輸出為等概分布，信道達(dá)到信道容量。當(dāng)r=2 時的均勻信道常稱為二元對稱信道，這時C = 1H(p)。 對于一般的離散行對稱信道，信道容量C仍然可以寫成

39、： 但不一定存在一種輸入分布能使輸出達(dá)到等概分布，此時信道容量 而離散對稱信道的信道矩陣中每一列都是由同一組元素的不同排列組成 所以保證了當(dāng)輸入符號X為等概分布時，輸出符號Y一定也是等概分布 輸出隨機(jī)變量熵可以達(dá)到 。 對于離散準(zhǔn)對稱信道， 但是可以證明當(dāng)輸入為等概分布時，可以達(dá)到信道容量,4.2.5 一般離散信道的信道容量,平均互信息 是輸入概率分布p(x)的上凸函數(shù)，因此必存在極大值 在信道固定的條件下，平均互信息是r個變量 的多元函 數(shù)，且滿足約束條件 ，故可用拉格朗日乘子法來求這個條件 極值。即在 設(shè)輔助函數(shù)： ，當(dāng) 時求得的 的值即為信道容量。 通過計算可得平均互信息的極大值 ，即,

40、的條件下求 的極值。,這樣得到的信道容量有一個參數(shù) 。在某些情況下可以消去 得到信 道容量值。 1當(dāng)輸入概率分布只有一個變量時，例如r=2，可以設(shè)輸入概率分布 為 和 ，因此輸入概率分布只有一個變量，這時我們可以直接對 求導(dǎo)求出，從而得出 的極大值C。 2對于信道矩陣為可逆矩陣的信道，我們可以采用解方程組的方法。 在一般信道的信道容量的推導(dǎo)中我們推出了下式：,移項(xiàng)得 當(dāng)r=s，且信道矩陣是可逆矩陣時，該方程組有唯一解。這時就可以求 出 ，然后根據(jù) 求出信道容量：,令,則,所以,由 和C就可以求得輸出概率分布： （1）由 列方程組求出 ； （2）由 求出C； （3）由 求出 ； （4）由 列方程

41、組求 。,再根據(jù),列方程組求,將計算步驟總結(jié)如下：,4.2.6 信道容量定理,從以上的討論可知，求信道容量的問題實(shí)際上是在約束條件下求多元 函數(shù)極值問題，在通常情況下，計算量是非常大的。 下面我們介紹一般離散信道的平均互信息 達(dá)到信道容量的充要 條件，在某些情況下它可以幫助我們較快地找到極值點(diǎn)。 定理4.3 設(shè)有一般離散信道，它有r個輸入信號，s個輸出信號。當(dāng)且 僅當(dāng)存在常數(shù)C使輸入分布 滿足： (1) 當(dāng) (2) 當(dāng) 其中， 它表示信道輸入 時，所給出關(guān)于輸出Y的信息量。常數(shù)C即為所求的 信道容量。,時， 達(dá)到最大值。,信道容量定理告訴我們，平均互信息 取到極大值也就是信道容 量時，對于任意

42、 ，只要它出現(xiàn)的概率大于0， 都相等。 信道容量定理只給出了達(dá)到信道容量時，最佳輸入概率分布應(yīng)滿足的 條件，并沒有給出最佳輸入概率分布值，也沒有給出信道容量的數(shù)值 另外，定理本身也隱含著達(dá)到信道容量的最佳分布不一定是唯一的， 只要輸入概率分布滿足充要條件式，就是信道的最佳輸入分布。在一 些特殊情況下，我們常常利用這一定理尋求輸入分布和信道容量值。,4.3 離散多符號信道及其信道容量,實(shí)際離散信道的輸入和輸出常常是隨機(jī)變量序列，用隨機(jī)矢量來表示 稱為離散多符號信道，如圖4.8所示。實(shí)際離散信道往往是有記憶信道 為了簡化起見，我們主要研究離散無記憶信道。 定義4.6 若在任意時刻信道的輸出只與此時

43、刻信道的輸入有關(guān)，而 與其他時刻的輸入和輸出無關(guān)，則稱之為離散無記憶信道，簡稱為 DMC(discrete memoryless channel)。 輸入、輸出隨機(jī)序列的長度為N的離散 無記憶平穩(wěn)信道通常稱為離散無記憶 信道的N次擴(kuò)展信道。 N次擴(kuò)展信道的信道矩陣是一個 的矩陣。,圖4.8 離散多符號信道,離散無記憶信道的數(shù)學(xué)模型仍然表示為： ，注意： 這時輸入、輸出均為隨機(jī)矢量。 根據(jù)信道無記憶的特性，其轉(zhuǎn)移概率 定理4.4 若信道的輸入和輸出分別是N長序列X和Y，且信道是無記 憶的，則存在 這里Xk、Yk分別是序列X和Y中第k位隨機(jī)變量。,對于離散無記憶N次擴(kuò)展信道，當(dāng)信源是平穩(wěn)無記憶信源

44、時，其平均互 信息 等于單符號信道的平均互信息的N倍。 離散無記憶信道的N次擴(kuò)展信道的信道容量為 因?yàn)楝F(xiàn)在輸入隨機(jī)序列在同一信道中傳輸，所以任何時刻通過離散無 記憶信道傳輸?shù)淖畲笮畔⒘慷枷嗤?，?所以 當(dāng)信源也是無記憶信源并且每一時刻的輸入分布各自達(dá)到最佳輸入分 布時，才能達(dá)到這個信道容量NC。 一般情況下，消息序列在離散無記憶N次擴(kuò)展信道中傳輸時，其平均互 信息量,4. 4 組合信道及其信道容量,前面我們分析了離散單符號信道和離散無記憶信道的擴(kuò)展信道。實(shí)際應(yīng)用中常常會遇到兩個或更多個信道組合在一起使用的情況。例如，待發(fā)送的消息比較多時，可能要用兩個或更多個信道并行發(fā)送，這種組合信道稱為并聯(lián)信

45、道；有時消息會依次地通過幾個信道串聯(lián)發(fā)送，例如無線電中繼信道，數(shù)據(jù)處理系統(tǒng)，這種組合信道稱為級聯(lián)信道。在研究較復(fù)雜信道時，為使問題簡化，往往可以將它們分解成幾個簡單的信道的組合。這一節(jié)我們將討論這兩種組合信道的信道容量與其組成信道的信道容量間關(guān)系。,4.4.1 獨(dú)立并聯(lián)信道,一般獨(dú)立并聯(lián)信道如圖4.10所示。 可以把定理4.2的結(jié)論推廣到N個獨(dú)立并聯(lián) 信道中來： 只有當(dāng)每個輸入隨機(jī)變量的概率分布均達(dá) 到各自信道的最佳輸入分布時，獨(dú)立并聯(lián) 信道的信道容量才等于各信道容量之和： 當(dāng)N個獨(dú)立并聯(lián)信道信道容量都相同時，,圖4.10 獨(dú)立并聯(lián)信道,4.4.2 級聯(lián)信道,級聯(lián)信道是信道最基本的組合形式，許

46、多實(shí)際信道都可以看成是其組 成信道的級聯(lián)。圖4.11是由兩個單符號信道組成的最簡單的級聯(lián)信道 XYZ 組成一個馬爾可夫鏈。根據(jù)馬爾可夫鏈的性質(zhì)，級聯(lián)信道的 總的信道矩陣等于這兩個串接信道的信道矩陣的乘積。求得級聯(lián)信道 的總的信道矩陣后，級聯(lián)信道的信道容量就可以用求離散單符號信道 的信道容量的方法計算。,圖4.11 級聯(lián)信道,*4. 5 連續(xù)信道及其信道容量,4.5.1 連續(xù)隨機(jī)變量的互信息 連續(xù)隨機(jī)變量和之間的平均互信息定義為 連續(xù)隨機(jī)變量的平均互信息具有和離散隨機(jī)變量的平均互信息一樣的性質(zhì)： 1對稱性： 2非負(fù)性： 當(dāng)且僅當(dāng)隨機(jī)變量和統(tǒng)計獨(dú)立時等號成立,4.5.2 高斯加性信道的信道容量,高

47、斯信道是最差的信道，實(shí)際應(yīng)用中往往把噪聲視為高斯噪聲。 噪聲源為高斯白噪聲的加性信道。其信道容量 如果噪聲N是均值為0、方差為 的高斯隨機(jī)變量，即 表示噪聲N的平均功率。這種信道稱為高斯加性連續(xù)信道。,當(dāng)輸入隨機(jī)變量X的概率密度是均值為0、方差為 的高斯隨機(jī)變量， 加性信道的噪聲N是均值為0、方差為 的高斯隨機(jī)變量時，輸出隨機(jī) 變量Y也是一個高斯隨機(jī)變量，其均值為0、方差為 此時輸出隨機(jī)變量的熵 達(dá)到最大，而信道達(dá)到信道容量： 其中, 稱為信道的信噪比。,4.5.3 多維高斯加性信道的信道容量,當(dāng)信道為多維高斯加性信道時，由于加性噪聲信道必然是一個無記憶 信道，所以 當(dāng)且僅當(dāng)輸入隨機(jī)矢量X中各

48、分量統(tǒng)計獨(dú)立，并且均為高斯變量時達(dá)到 信道容量。 如果在每個抽樣時刻信源和噪聲是均值為0、方差分別為 和 的高斯隨機(jī)變量，,因此,則,比特/n個樣值,*4.6 波形信道及其信道容量,波形信道通常根據(jù)抽樣定理轉(zhuǎn)化成多維連續(xù)信道進(jìn)行處理。 一般來說，信道的帶寬總是有限的。假設(shè)某信道的頻帶限于（0，B） 則其輸入、輸出信號和噪聲都是限頻的隨機(jī)過程，頻帶限于（0，B） 根據(jù)抽樣定理，可把一個時間連續(xù)的信道變換成時間離散的隨機(jī)序列 信道來處理，即用每隔 秒時間的采樣值來表示輸入、輸出信號和噪 聲。我們把一次采樣看成信道的一次傳輸， 由于每秒傳送2B個樣值，所以單位時間的信道容量為 當(dāng)噪聲是雙邊功率譜密度

49、為 的高斯白噪聲時，,比特/秒,這就是著名的香農(nóng)公式，它適用于加性高斯白噪聲信道。從前面的討 論可知，只有當(dāng)輸入信號為功率受限的高斯白噪聲信號時，才能達(dá)到 該信道容量。 香農(nóng)公式說明，當(dāng)信道容量一定時，增大信道的帶寬，可以降低對信 噪功率比的要求；反之，當(dāng)信道頻帶較窄時，可以通過提高信噪功率 比來補(bǔ)償。 上式表明當(dāng)頻帶很寬時，信道容量正比于信號功率與噪聲譜密度之比 上式是加性高斯噪聲信道信息傳輸率的極限值。,當(dāng) 時，則,5.1 信源編碼的相關(guān)概念 5.2 定長碼及定長編碼定理 5.3 變長碼及變長編碼定理 5.4 變長碼的編碼方法 5.5 實(shí)用的無失真信源碼方法,第五章 無失真信源編碼,5.1

50、 信源編碼的相關(guān)概念,5.1.1 編碼器 信源輸出的符號序列，需要變換成適合信道傳輸?shù)姆栃蛄校话惴Q為碼序列，對信源輸出的原始符號按照一定的數(shù)學(xué)規(guī)則進(jìn)行的這種變換稱為編碼，完成編碼功能的器件，稱為編碼器。接收端有一個譯碼器完成相反的功能。 信源編碼器的輸入是信源符號集 ，共有q個信源符號。同時存在另一個符號集 ，稱為碼符號集，共有r個碼符號，碼符號集中的元素稱為碼元或碼符號，編碼器的作用就是將信源符號集 中的符號 變換成由 個碼符號組成的一一對應(yīng)的碼符號序列。編碼器輸出的碼符號序列稱為碼字，并用 來表示，它與信源符號 之間是一一對應(yīng)的關(guān)系，如圖5.1所示。,碼字的集合C稱為碼，即 。信源符號

51、 對應(yīng)的碼字 包含 個碼符號， 稱為碼字長度，簡稱碼長。 所以，信源編碼就是把信源符號序列變換到碼符號序列的一種映射。 若要實(shí)現(xiàn)無失真編碼，那么這種映射必須是一一對應(yīng)的、可逆的。 一般來說，人們總是希望把信源所有的信息毫無保留地傳遞到接收端，即實(shí)現(xiàn)無失真?zhèn)鬟f，所以首先要對信源實(shí)現(xiàn)無失真編碼。,圖5.1 信源編碼器,信源編碼有以下3種主要方法： (1) 匹配編碼根據(jù)信源符號的概率不同，編碼的碼長不同：概率大的信源符號，所編的代碼短；概率小的信源符號所編的代碼長，這樣使平均碼長最短。將要講述的香農(nóng)編碼、哈夫曼編碼、費(fèi)諾碼都是概率匹配編碼，都是無失真信源編碼。 (2) 變換編碼 先對信號進(jìn)行變換，從

52、一種信號空間變換為另一種信號空間，然后針對變換后的信號進(jìn)行編碼。 (3) 識別編碼識別編碼主要用于印刷或打字機(jī)等有標(biāo)準(zhǔn)形狀的文字符號和數(shù)據(jù)的編碼，比如中文文字和語音的識別。 后兩種信源編碼均為有失真的信源編碼。 無失真信源編碼主要針對離散信源，連續(xù)信源在量化編碼的過程中必然會有量化失真，所以對連續(xù)信源只能近似地再現(xiàn)信源的消息。,5.1.2 碼的分類,1. 分組碼和非分組碼 定義5.1 將信源符號集中的每個信源符號 固定地映射成一個碼字 ，這樣的碼稱為分組碼。 用分組碼對信源符號進(jìn)行編碼時，為了使接收端能夠迅速準(zhǔn)確地將碼譯出，分組碼必須具有一些直觀屬性。與分組碼對應(yīng)的是非分組碼，又稱為樹碼、樹碼

53、編碼器輸出的碼符號通常與編碼器的所有信源符號都有關(guān)。 2. 奇異碼與非奇異碼 定義5.2 若一種分組碼中的所有碼字都不相同，則稱此分組碼為非奇異碼，否則稱為奇異碼。,3. 唯一可譯碼與非唯一可譯碼 定義5.3 任意有限長的碼元序列，如果只能唯一地分割成一個個碼字，便稱為唯一可譯碼。 唯一可譯碼的物理含義是指不僅要求不同的碼字表示不同的信源符號，而且還要求對由信源符號構(gòu)成的符號序列進(jìn)行編碼時，在接收端仍能正確譯碼而不發(fā)生混淆。唯一可譯碼首先是非奇異碼，且任意有限長的碼字序列不會雷同。 4. 即時碼與非即時碼 定義5.4 無需考慮后續(xù)的碼符號就可以從碼符號序列中譯出碼字，這樣的唯一可譯碼稱為即時碼

54、。,下面討論唯一可譯碼成為即時碼的條件。 定義5.5 設(shè) 為一碼字，對于任意的 ，稱碼符號序列的前j個元素 為碼字的前綴。 按照上述的前綴的定義，有下述結(jié)論： 定理5.1 一個唯一可譯碼成為即時碼 的充要條件是其中任何一個碼字都不是 其他碼字的前綴。 即時碼可以用樹圖來構(gòu)造圖5.2是一個 二元即時碼的樹圖,圖5.2 二元即時碼的樹圖,樹是沒有回路的圖，所以它也是由節(jié)點(diǎn)和弧構(gòu)成的樹中最頂部的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)。 所有根節(jié)點(diǎn)的子節(jié)點(diǎn)稱為一階節(jié)點(diǎn)，所有一階節(jié)點(diǎn)的子節(jié)點(diǎn)稱為二階節(jié)點(diǎn)，依此類推。 階節(jié)點(diǎn)最多有 個。節(jié)點(diǎn)的階次又稱為節(jié)點(diǎn)的深度。 綜上所述，可將信源編碼作如下分類：

55、,5.2 定長碼及定長編碼定理,若對一個有q個信源符號的信源S進(jìn)行定長編碼，那么信源S存在唯一可譯定長碼的條件是： (5.1) 其中，r是碼符號集中的碼元數(shù)，l是定長碼的碼長。 如果對信源S的N次擴(kuò)展信源 進(jìn)行定長編碼，若要編得的定長碼是唯一可譯碼，則必須滿足 (5.2) 其中，q是信源S的符號個數(shù)， 是信源S的N次擴(kuò)展信源 的符號個數(shù)，r是碼符號集X的碼符號數(shù)。,定長編碼的信息傳輸效率是很低的。提高信息傳輸效率的方法有： 方法1：考慮符號之間的依賴關(guān)系，對信源S的擴(kuò)展信源進(jìn)行編碼。 方法2：對于概率等于0或非常小的符號序列不予編碼。 定理5.2 離散無記憶信源的熵為H(S)，若對信源長為N的

56、序列進(jìn)行定長編碼，碼 符號集X中有r個碼符號，碼長為l，則對于任意 ，只要滿足： 則當(dāng)N足夠大時，可實(shí)現(xiàn)幾乎無失真編碼，即譯碼錯誤概率任??； 反之，如果 則不可能實(shí)現(xiàn)幾乎無失真編碼，即當(dāng)N足夠大時，譯碼錯誤概率為1。,定理5.2是在離散平穩(wěn)無記憶信源的條件下證明的，但它同樣適合于平 穩(wěn)有記憶信源，只要將式中H(S)改為極限熵 即可，條件是有記憶 信源的極限熵 和極限方差 存在。 定長信源編碼定理給出了定長編碼時每個信源符號最少所需的碼符號的 理論極限，該極限值由H(S)決定。 定義5.6 設(shè)熵為H(S)的離散無記憶信源，若對信源的長為N的符號序 列進(jìn)行定長編碼，碼符號集中碼符號個數(shù)為r，設(shè)碼字

57、長為l，定義： 比特/信源符號為編碼速率，它表示平均每個信源符號 編碼后能載荷的最大信息量。 這時，定理5.2的條件可表述為RH(S)+，即編碼速率大于信源的 熵才能實(shí)現(xiàn)幾乎無失真編碼。為了衡量編碼效果，引進(jìn)編碼效率。,定義5.7 定義 為編碼效率。 由定理5.2可得最佳編碼效率為 ，所以 在已知方差和信源熵的條件下，信源符號序列長度N與最佳編碼效率 和允許錯誤概率 的關(guān)系為： 當(dāng)允許錯誤概率越小，編碼效率又要高，那么信源符號序列長度N必須 越長在實(shí)際情況下，要實(shí)現(xiàn)幾乎無失真的定長編碼，N需要的長度將 會大到難以實(shí)現(xiàn)。,5.3 變長碼及變長編碼定理,5.3.1 Kraft不等式和McMillan不等式 定理5.3 設(shè)信源符號集為 ，碼符號集為 對信源進(jìn)行編碼，得到的碼為 ，碼長分別為 。 即時碼存在的充要條件是： 這稱為Kraft不等式。 由Kraft不等式可知，給定r和q，只要允許碼字長度可以足夠長，則碼長 總可以滿足Kraft不等式而得到即時碼，Kraft不等式指出了即時碼的碼長 必