第4章-離散信源編碼理論

第1頁(yè)2023/2/1第四章

──────────────

離散信源編碼理論4.1信源編碼的基本概念4.3信源無(wú)失真編碼4.4信息率失真函數(shù)及性質(zhì)4.5信息率失真函數(shù)與信道容量4.7香農(nóng)第三定理第2頁(yè)2023/2/14.1信源編碼的基本概念4.1信源編碼的基本概念1.為什么要進(jìn)行信源編碼信源的兩個(gè)重要問(wèn)題信源輸出的信息量計(jì)算問(wèn)題；如何更有效地表示信源輸出的問(wèn)題。

信源編碼就是為了提高通信效率，對(duì)信源所發(fā)送的消息進(jìn)行變換的方法之一。為什么要進(jìn)行信源編碼人們都希望無(wú)失真?zhèn)魉停紫纫獙?duì)信源無(wú)差錯(cuò)編碼；數(shù)字技術(shù)應(yīng)用越來(lái)越多，模擬信源通過(guò)數(shù)字化變成數(shù)字信號(hào)傳送。第3頁(yè)2023/2/14.1信源編碼的基本概念2.信源編碼的概念信源編碼定義：指定能夠滿足信道特性（適合于信道傳輸）的符號(hào)序列—碼序列，來(lái)代表信源輸出的消息。編碼器：完成編碼功能的器件。離散信源輸出的碼序列

離散信源輸出的消息是由一個(gè)個(gè)離散符號(hào)組成的隨機(jī)序列信源編碼就是把信源輸出的隨機(jī)符號(hào)序列變成碼序列第4頁(yè)2023/2/14.1信源編碼的基本概念2.信源編碼的概念研究信源編碼時(shí)，將信道編碼和譯碼看成是信道的一部分，而突出信源編碼；研究信道編碼時(shí)，將信源編碼和譯碼看成是信源和信宿的一部分，而突出信道編碼。第5頁(yè)2023/2/14.1信源編碼的基本概念2.信源編碼的概念討論無(wú)失真信源編碼先不考慮抗干擾問(wèn)題，它的數(shù)學(xué)模型比較簡(jiǎn)單，如下圖。信源符號(hào)：編碼器的輸入是信源符號(hào)X={x1,x2,…,xi,…xn}。信源符號(hào)序列：碼符號(hào)/碼元：元素yj是適合信道傳輸?shù)姆?hào)，Y={y1,y2,…,yj,…ym}稱(chēng)為碼符號(hào)/碼元。第6頁(yè)2023/2/14.1信源編碼的基本概念碼字（碼符號(hào)序列）：碼長(zhǎng)（碼字長(zhǎng)度）：ki稱(chēng)為碼字長(zhǎng)度或簡(jiǎn)稱(chēng)碼長(zhǎng)。編碼：從信源符號(hào)到碼符號(hào)的一種映射。若要實(shí)現(xiàn)無(wú)失真編碼，這種映射必須是一一對(duì)應(yīng)的，可逆的。2.信源編碼的概念編碼器功能：將信源符號(hào)集當(dāng)中的符號(hào)xi（或者長(zhǎng)為L(zhǎng)的信源符號(hào)序列）變換成由yj(j=1,2,…,m)組成的長(zhǎng)度為ki

的序列。第7頁(yè)2023/2/14.1信源編碼的基本概念二元碼：碼符號(hào)集為X={0,1}，所得碼字都是一些二元序列。定長(zhǎng)碼（等長(zhǎng)碼）：一組碼中所有碼字的碼長(zhǎng)都相同，即：ki=K(i=1,2,…,n)。變長(zhǎng)碼：一組碼字中所有碼字的碼長(zhǎng)各不相同，即任意碼字由不同長(zhǎng)度的碼符號(hào)序列組成。非奇異碼：一組碼字中所有碼字都不相同，即所有信源符號(hào)影射到不同的碼符號(hào)序列。奇異碼：一組碼中有相同的碼字。惟一可譯碼：碼的任意一串有限長(zhǎng)的碼符號(hào)序列只能被惟一地譯成所對(duì)應(yīng)的信源符號(hào)。即時(shí)碼：不需要考慮后續(xù)的碼符號(hào)，可以根據(jù)當(dāng)前的碼符號(hào)序列正確譯出相應(yīng)的碼字。第8頁(yè)2023/2/14.1信源編碼的基本概念碼樹(shù)圖m元（m進(jìn)制）碼樹(shù)圖樹(shù)根：最頂部畫(huà)一個(gè)起始點(diǎn)。樹(shù)枝：從根部引出m條線段，每條線段都稱(chēng)為樹(shù)枝。一級(jí)節(jié)點(diǎn)：自根部起,通過(guò)一條樹(shù)枝到達(dá)的節(jié)點(diǎn)。一級(jí)節(jié)點(diǎn)最多有m個(gè).n級(jí)節(jié)點(diǎn)：通過(guò)

n條樹(shù)枝達(dá)到的節(jié)點(diǎn)。最多有mn。終節(jié)點(diǎn)/終端節(jié)點(diǎn)：下面不再有樹(shù)枝的節(jié)點(diǎn)。中間節(jié)點(diǎn)：除了樹(shù)根和終節(jié)點(diǎn)以外的節(jié)點(diǎn)。聯(lián)枝：串聯(lián)的樹(shù)枝。滿樹(shù)：在碼樹(shù)圖中，當(dāng)每一個(gè)碼字的串聯(lián)枝數(shù)都相同時(shí)，就是定長(zhǎng)碼。此時(shí)的碼樹(shù)稱(chēng)為滿樹(shù)。第9頁(yè)2023/2/14.1信源編碼的基本概念[例]：碼1：顯然不是惟一可譯碼。x2和x4對(duì)應(yīng)于同一碼字“11”，碼1是一個(gè)奇異碼。碼2：是非奇異碼，不是惟一可譯碼。當(dāng)收到一串碼符號(hào)“01000”時(shí)，可將它譯成“x4x3x1”，也可譯為“x4x1x3”，“x1x2x3”或“x1x2x1x1”等，這種碼從單個(gè)碼字來(lái)看雖然不是奇異的，但從有限長(zhǎng)的碼序列來(lái)看，它仍然是一個(gè)奇異碼。碼3：雖然是惟一可譯碼，但它要等到下一個(gè)“1”收到后才能確定碼字的結(jié)束，譯碼有延時(shí)。碼4：既是惟一可譯碼，又沒(méi)有譯碼延時(shí)。碼字中的符號(hào)“1”起了逗點(diǎn)的作用，故稱(chēng)為逗點(diǎn)碼。即時(shí)碼/前綴條件碼/異前置碼/異字頭碼/逗點(diǎn)碼/非延長(zhǎng)碼：如果一個(gè)碼的任何一個(gè)碼字都不是其它碼字的前綴。第10頁(yè)2023/2/13.克拉夫特不等式

克拉夫特不等式：m元長(zhǎng)度為ki，i=1,2,…,n的即時(shí)碼存在的充要條件是證明：必要條件：設(shè)即時(shí)碼第i個(gè)碼字的長(zhǎng)度為ki，i=1,2,…,n，造一個(gè)碼樹(shù)圖，在第ki級(jí)總共有個(gè)節(jié)點(diǎn)。第i個(gè)碼字占據(jù)了第ki級(jí)的，根據(jù)即時(shí)碼的定義，其后的樹(shù)枝不能再用。對(duì)于N級(jí)滿樹(shù)，其后不能用的枝數(shù)為，那么總共不用的枝數(shù)為。N級(jí)滿樹(shù)第N級(jí)上的總枝數(shù)已知為mN，所以必有兩邊除以mN，就得：。4.1信源編碼的基本概念第11頁(yè)2023/2/13.克拉夫特不等式

克拉夫特不等式：m元長(zhǎng)度為ki，i=1,2,…,n的即時(shí)碼存在的充要條件是證明：充分條件：如果式成立，則必成立，總可以把第N級(jí)上的樹(shù)枝分成n組；各組中從第N級(jí)開(kāi)始刪除

(i=1,2,…n)個(gè)枝；相對(duì)于N級(jí)滿樹(shù)，等于刪除了所有可能的ki級(jí)節(jié)點(diǎn)的在該組中以第ki級(jí)節(jié)點(diǎn)作為終節(jié)點(diǎn)，就構(gòu)造好了第i

個(gè)碼字。對(duì)所有碼字如法炮制，則總共刪除了所有mN個(gè)節(jié)點(diǎn)中的。由于，于是構(gòu)造了一個(gè)即時(shí)碼。4.1信源編碼的基本概念第12頁(yè)2023/2/14.3信源無(wú)失真編碼碼字與信息率的關(guān)系有時(shí)消息太多，不可能或者沒(méi)必要給每個(gè)消息分配一個(gè)碼字；給多少消息分配碼字可以做到幾乎無(wú)失真譯碼？傳送碼字需要一定的信息率，碼字越多，所需的信息率越大。編多少碼字的問(wèn)題可以轉(zhuǎn)化為對(duì)信息率大小的問(wèn)題；信息率越小越好，最小能小到多少才能做到無(wú)失真譯碼呢？

這些問(wèn)題就是信源編碼定理要研究的問(wèn)題。第13頁(yè)2023/2/14.3信源無(wú)失真編碼信源編碼有定長(zhǎng)和變長(zhǎng)兩種方法。定長(zhǎng)編碼：碼字長(zhǎng)度K是固定的，相應(yīng)的編碼定理稱(chēng)為定長(zhǎng)信源編碼定理，是尋求最小K值的編碼方法。變長(zhǎng)編碼：K是變值，相應(yīng)的編碼定理稱(chēng)為變長(zhǎng)編碼定理。這里的K值最小意味著數(shù)學(xué)期望最小。無(wú)失真信源編碼就是要求信源符號(hào)與碼字之間形成一一映射的關(guān)系，并且要求編碼輸出的碼字序列對(duì)應(yīng)的反變換是惟一的，即是惟一可譯碼的，否則會(huì)造成譯碼錯(cuò)誤或者失真。第14頁(yè)2023/2/11.定長(zhǎng)編碼定理(1)定長(zhǎng)編碼定理定長(zhǎng)編碼定理：一個(gè)熵為H(X)的離散無(wú)記憶信源X1X2…Xl…XL，若對(duì)信源長(zhǎng)為L(zhǎng)的符號(hào)序列進(jìn)行定長(zhǎng)編碼，設(shè)碼字是從m個(gè)字母的碼符號(hào)集中，選取K個(gè)碼元組成Y1Y2…Yk…YK。對(duì)于任意ε>0，δ>0，只要滿足當(dāng)L足夠大時(shí)，必可使譯碼差錯(cuò)小于δ，即譯碼錯(cuò)誤概率能為任意小；反之，若：

則不可能實(shí)現(xiàn)無(wú)失真編碼，而當(dāng)L足夠大時(shí)，譯碼錯(cuò)誤概率近似等于1。4.3信源無(wú)失真編碼第15頁(yè)2023/2/1(1)定長(zhǎng)編碼定理

4.3信源無(wú)失真編碼定理中的公式改寫(xiě)成：Klog2m>LH(X)

Klog2m：表示長(zhǎng)為K的碼符號(hào)序列能載荷的最大信息量LH(X)：代表長(zhǎng)為L(zhǎng)的信源序列平均攜帶的信息量平均符號(hào)熵。定長(zhǎng)編碼定理說(shuō)明：只要碼字傳輸?shù)男畔⒘看笥谛旁磾y帶的信息量，總可實(shí)現(xiàn)幾乎無(wú)失真編碼。第16頁(yè)2023/2/1(1)定長(zhǎng)編碼定理信源熵H(X)就是一個(gè)界限（臨界值）。當(dāng)編碼器輸出的信息率超過(guò)這個(gè)臨界值時(shí)，就能無(wú)失真譯碼，否則就不行。信源編碼定理從理論上說(shuō)明了編碼效率接近于1，即：

的理想編碼器的存在性，代價(jià)是在實(shí)際編碼時(shí)取無(wú)限長(zhǎng)的信源符號(hào)(L→∞)進(jìn)行統(tǒng)一編碼。說(shuō)明：定長(zhǎng)編碼定理是在平穩(wěn)無(wú)記憶離散信源的條件下論證的，但它同樣適用于平穩(wěn)有記憶信源，只是要求有記憶信源的極限熵和極限方差存在即可。對(duì)于平穩(wěn)有記憶信源，定理中的熵應(yīng)改為極限熵。4.3信源無(wú)失真編碼第17頁(yè)2023/2/1定長(zhǎng)編碼定理的意義

(1)對(duì)于給定的離散無(wú)記憶信源X和碼元數(shù)m，如果對(duì)X的N次擴(kuò)展信源進(jìn)行無(wú)失真等長(zhǎng)編碼，那么當(dāng)碼長(zhǎng)K滿足條件時(shí)，一定存在一種編碼方案，能夠?qū)崿F(xiàn)無(wú)失真編碼；反之，不可能進(jìn)行無(wú)失真編碼。4.3信源無(wú)失真編碼

(2)對(duì)于給定的信源離散無(wú)記憶X，信源的熵H(X)是一定的，當(dāng)碼符號(hào)數(shù)量m選定時(shí)，可以增加信源序列的長(zhǎng)度L，使得無(wú)失真編碼產(chǎn)生的每個(gè)符號(hào)平均長(zhǎng)度盡可能小，但是無(wú)論怎樣增加序列長(zhǎng)度L，信源每個(gè)符號(hào)的平均碼長(zhǎng)不可能小于，即碼長(zhǎng)的極限為。第18頁(yè)2023/2/1定長(zhǎng)編碼定理的意義4.3信源無(wú)失真編碼(3)當(dāng)序列長(zhǎng)度L一定，譯碼錯(cuò)誤概率PE為其中，D［I(ai)］為自信息量方差，定義為當(dāng)信源給定時(shí)，自信息方差是一定的，序列長(zhǎng)度L越大，錯(cuò)誤概率越小，要實(shí)現(xiàn)無(wú)失真編碼，序列長(zhǎng)度就應(yīng)當(dāng)足夠長(zhǎng)，使PE能夠滿足一定要求。第19頁(yè)2023/2/1(2)舉例[例4.1]：設(shè)單符號(hào)信源模型為：其信息熵為：H(X)=2.55（比特／符號(hào)）

若編碼效率為η

=90%，取L=1，則?。?/p>

ε=0.28，若譯碼差錯(cuò)率為δ=10－6,在差錯(cuò)率和效率要求都不苛刻的情況下，就必須有1600多萬(wàn)個(gè)信源符號(hào)一起編碼，技術(shù)實(shí)現(xiàn)非常困難。4.3信源無(wú)失真編碼1.定長(zhǎng)編碼定理第20頁(yè)2023/2/1(2)舉例[例]：離散無(wú)記憶信源：其信息熵為：自信息的方差為：4.3信源無(wú)失真編碼若對(duì)信源X采取等長(zhǎng)二元編碼時(shí)，要求η=0.96，δ=10－5信源序列長(zhǎng)度需長(zhǎng)達(dá)4130萬(wàn)以上，才能實(shí)現(xiàn)給定的要求，這在實(shí)際中很難實(shí)現(xiàn)。一般來(lái)說(shuō)，當(dāng)L

有限時(shí)，高傳輸效率的等長(zhǎng)碼往往要引入一定的失真和錯(cuò)誤，它不能像變長(zhǎng)碼那樣可以實(shí)現(xiàn)無(wú)失真編碼。第21頁(yè)2023/2/1

編碼信息率：設(shè)離散無(wú)記憶信源X的熵為H(X)，對(duì)X擴(kuò)展信源的符號(hào)序列XL進(jìn)行等長(zhǎng)無(wú)失真編碼，碼長(zhǎng)為K，編碼信息率為如果編碼信息率R′小于信源熵H(X)，存在一種編碼器能夠?qū)崿F(xiàn)無(wú)失真編碼；反之，如果編碼信息率大于信源熵H(X)，則不能實(shí)現(xiàn)無(wú)失真編碼。

編碼效率η：

4.3信源無(wú)失真編碼1.定長(zhǎng)編碼定理第22頁(yè)2023/2/1(1)基本概念變長(zhǎng)編碼（不等長(zhǎng)編碼）：不等長(zhǎng)編碼允許把等長(zhǎng)的消息變換成不等長(zhǎng)的碼序列。通常把經(jīng)常出現(xiàn)的消息編成短碼，不常出現(xiàn)的消息編成長(zhǎng)碼。這樣可使平均碼長(zhǎng)最短，從而提高通信效率，代價(jià)是增加了編譯碼設(shè)備的復(fù)雜度。

例如：在不等長(zhǎng)碼字組成的序列中要正確識(shí)別每個(gè)長(zhǎng)度不同的碼字的起點(diǎn)就比等長(zhǎng)碼復(fù)雜得多。譯碼延時(shí)／譯碼同步：接收到一個(gè)不等長(zhǎng)碼序列后，有時(shí)不能馬上斷定碼字是否真正結(jié)束，因而不能立即譯出該碼，要等到后面的符號(hào)收到后才能正確譯出。2.變長(zhǎng)編碼定理4.3信源無(wú)失真編碼第23頁(yè)2023/2/1(2)變長(zhǎng)編碼定理（香農(nóng)第一定理）平均碼長(zhǎng)：變長(zhǎng)編碼定理：若一離散無(wú)記憶信源的平均符號(hào)熵為H(X)，對(duì)信源符號(hào)進(jìn)行m元變長(zhǎng)編碼，一定存在一種無(wú)失真編碼方法，其碼字平均長(zhǎng)度滿足下列不等式：化莫其平均信息率滿足不等式H(X)+ε>R≥H(X)，式中ε為任意正數(shù)。4.3信源無(wú)失真編碼對(duì)信源進(jìn)行變長(zhǎng)編碼一般所要求的信源符號(hào)長(zhǎng)度L比定長(zhǎng)編碼小的多。第24頁(yè)2023/2/1(2)變長(zhǎng)編碼定理（香農(nóng)第一定理）信道的信息傳輸率為（從信道的角度看）：編碼效率定義為：二元無(wú)損無(wú)噪信道中m=2，所以Hm(X)=H(X)4.3信源無(wú)失真編碼第25頁(yè)2023/2/1(2)變長(zhǎng)編碼定理舉例[例]：設(shè)單符號(hào)信源模型為：其信息熵為：H(X)=2.55（比特/符號(hào)）這里m=2，log2m=1要求η>90%，則：4.3信源無(wú)失真編碼與定長(zhǎng)編碼相比，對(duì)同一信源，要求編碼效率都達(dá)到90%時(shí)，變長(zhǎng)編碼只需L=4進(jìn)行編碼，而等長(zhǎng)碼則要求L大于1.6875×107。用變長(zhǎng)編碼時(shí),L不需要很大就可以達(dá)到相當(dāng)高的編碼效率而且可實(shí)現(xiàn)無(wú)失真編碼。第26頁(yè)2023/2/1(2)變長(zhǎng)編碼定理舉例[例]：離散無(wú)記憶信源：其信息熵為：用二元碼符號(hào)(0,1)來(lái)構(gòu)造一個(gè)即時(shí)碼：x1→0，x2→1這時(shí)平均碼長(zhǎng)：編碼效率為：信道信息傳輸率為：R=0.811比特/二元碼符號(hào)4.3信源無(wú)失真編碼為了提高傳輸效率，對(duì)無(wú)記憶信源X

的二次擴(kuò)展信源X2進(jìn)行編碼，下面給出擴(kuò)展信源X2

及其某一個(gè)即時(shí)碼：第27頁(yè)2023/2/1

這個(gè)碼的平均長(zhǎng)度為：

信源符號(hào)X中每一單個(gè)符號(hào)的平均碼長(zhǎng)為：4.3信源無(wú)失真編碼其編碼效率為：信息傳輸速率為：編碼復(fù)雜了一些，但信息傳輸率有了提高。對(duì)信源X的三次和四次擴(kuò)展信源進(jìn)行編碼，編碼效率為：信息傳輸率為：第28頁(yè)2023/2/1(2)變長(zhǎng)編碼定理與定長(zhǎng)碼比較：對(duì)于同一信源，要求編碼效率都達(dá)到96%時(shí)，變長(zhǎng)碼只需對(duì)二次擴(kuò)展信源（N=2）進(jìn)行編碼，而等長(zhǎng)碼則要求L>4.13×107。

結(jié)論用變長(zhǎng)碼編碼時(shí)，L不需要很大就可以達(dá)到相當(dāng)高的編碼效率，而且可以實(shí)現(xiàn)無(wú)失真編碼。隨著擴(kuò)展信源次數(shù)的增加，編碼的效率越來(lái)越接近于1比特/二元碼符號(hào)，達(dá)到信源與信道匹配，使信道得到充分利用。4.3信源無(wú)失真編碼第29頁(yè)2023/2/1信道編碼定理：無(wú)論何種信道，只要信息率R小于信道容量C，總能找到一種編碼，使在信道上能以任意小的錯(cuò)誤概率和任意接近于C的傳輸率來(lái)傳送信息。反之，若R>C，則傳輸總要失真。完全無(wú)失真?zhèn)魉筒豢蓪?shí)現(xiàn)

實(shí)際的信源常常是連續(xù)的，信息率無(wú)限大，要無(wú)失真?zhèn)魉鸵笮畔⒙蔙為無(wú)窮大；實(shí)際信道帶寬是有限的，所以信道容量受限制。要想無(wú)失真?zhèn)鬏敚璧男畔⒙蚀蟠蟪^(guò)信道容量R>>C?；靖拍?.4信息率失真函數(shù)及性質(zhì)第30頁(yè)2023/2/1技術(shù)發(fā)展的需要隨著科技的發(fā)展，數(shù)字系統(tǒng)應(yīng)用得越來(lái)越廣泛，需要傳送、存儲(chǔ)和處理大量的數(shù)據(jù)。為了提高傳輸和處理效率，需要對(duì)數(shù)據(jù)壓縮，這樣會(huì)帶來(lái)一定的信息損失。信息時(shí)代，信息爆炸，要求解決對(duì)海量數(shù)據(jù)有效的壓縮，減少數(shù)據(jù)的存儲(chǔ)容量(如各種數(shù)據(jù)庫(kù)、電子出版物、多媒體娛樂(lè))、傳輸時(shí)間(如數(shù)據(jù)通信和遙測(cè))、或占有帶寬(如多媒體通信、數(shù)字音頻廣播、高清晰度電視)，想方設(shè)法壓縮給定消息集合占用的空間域、時(shí)間域和頻率域資源.

如海洋地球物理勘探遙測(cè)數(shù)據(jù)，用60路傳感器，每路信號(hào)1kHz，16位A/D量化，每航測(cè)1km就需記錄1盤(pán)0.5英寸的磁帶，一條測(cè)量船每年就可勘測(cè)15000km。基本概念4.4信息率失真函數(shù)及性質(zhì)第31頁(yè)2023/2/1實(shí)際生活中的需要

實(shí)際生活中，人們一般并不要求獲得完全無(wú)失真的消息，通常只要求近似地再現(xiàn)原始消息，即允許一定的失真存在。打電話：即使語(yǔ)音信號(hào)有一些失真，接電話的人也能聽(tīng)懂。人耳接收信號(hào)的帶寬和分辨率是有限的。放電影：理論上需要無(wú)窮多幅靜態(tài)畫(huà)面，由于人眼的“視覺(jué)暫留性”，實(shí)際上只要每秒放映24幅靜態(tài)畫(huà)面。有些失真沒(méi)有必要完全消除。既然允許一定的失真存在，對(duì)信息率的要求便可降低。基本概念4.4信息率失真函數(shù)及性質(zhì)第32頁(yè)2023/2/1信息率失真理論研究的內(nèi)容:

信息率與允許失真之間的關(guān)系。

信息率失真函數(shù)

香農(nóng)定義了信息率失真函數(shù)R(D)?！氨Ｕ娑葴?zhǔn)則下的信源編碼定理”指出：在允許一定失真度D的情況下，信源輸出的信息率可壓縮到R(D)。信息率失真理論是量化（模數(shù)轉(zhuǎn)換）、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮的理論基礎(chǔ)?；靖拍?.4信息率失真函數(shù)及性質(zhì)第33頁(yè)2023/2/1信息率失真函數(shù)極小值問(wèn)題

I(X;Y)是P(X)和P(X/Y)的二元函數(shù)；在討論信道容量時(shí)：規(guī)定了P(X/Y)，I(X;Y)變成了P(X)的函數(shù)。在離散情況下，因?yàn)镮(X;Y)對(duì)p(xi)是上凸函數(shù)，所以變更p(xi)所求極值一定是I(X;Y)的極大值；在連續(xù)情況下，變更信源P(X)求出的也是極大值，但求極值時(shí)還要一些其它的限制條件。在討論信息率時(shí)：規(guī)定p(xi)，變更p(yj/xi)來(lái)求平均互信息的極值，稱(chēng)為信道容量對(duì)偶問(wèn)題。由于I(X;Y)是p(yj/xi)的下凸函數(shù)，所求的極值一定是極小值。但若X和Y相互統(tǒng)計(jì)獨(dú)立（p(yj/xi)=p(yj)），這個(gè)極小值就是0，因?yàn)镮(X;Y)是非負(fù)的，0必為極小值，這樣求極小值就沒(méi)意義了。引入一個(gè)失真函數(shù)，計(jì)算在失真度一定的情況下信息率的極小值就變的有意義了。4.4信息率失真函數(shù)及性質(zhì)第34頁(yè)2023/2/1(1)信息率與失真的關(guān)系信道中固有的噪聲和不可避免的干擾，使信源的消息通過(guò)信道傳輸后造成誤差和失真。誤差或失真越大，接收者收到消息后對(duì)信源存在的不確定性就越大，獲得的信息量就越小，信道傳輸消息的信息率也越小。4.4.1失真測(cè)度4.4信息率失真函數(shù)及性質(zhì)第35頁(yè)2023/2/1(2)失真度失真度

設(shè)離散無(wú)記憶信源為：信源符號(hào)通過(guò)信道傳送到接收端Y：信道的傳遞概率矩陣：對(duì)每一對(duì)(xi,yj)，指定一個(gè)非負(fù)函數(shù)d(xi,yj)≥0i=1,2,…,n

j=1,2,…,m稱(chēng)d(xi,yj)為單個(gè)符號(hào)的失真度（失真函數(shù)）。表示信源發(fā)出一個(gè)符號(hào)xi，在接收端再現(xiàn)yj所引起的誤差或失真。4.4.1失真測(cè)度4.4信息率失真函數(shù)及性質(zhì)第36頁(yè)2023/2/1(2)失真度失真矩陣

失真度還可表示成矩陣的形式稱(chēng)[D]為失真矩陣。它是n×m階矩陣。連續(xù)信源和連續(xù)信道的失真函數(shù)在連續(xù)信源和連續(xù)信道情況下，失真度定義為：d(x,y)≥0。4.4信息率失真函數(shù)及性質(zhì)第37頁(yè)2023/2/1(3)常用的失真函數(shù)第一種：

當(dāng)i=j時(shí)，X與Y的取值一樣，用Y來(lái)代表X就沒(méi)有誤差，所以定義失真度為0；當(dāng)i≠j時(shí)，用Y代表X就有誤差。這種定義認(rèn)為對(duì)所有不同的i和j引起的誤差都一樣，所以定義失真度常數(shù)a。特點(diǎn)：對(duì)角線上的元素均為0，對(duì)角線以外的其它元素都為常數(shù)a。漢明失真函數(shù)：a=1。4.4.1失真測(cè)度4.4信息率失真函數(shù)及性質(zhì)第38頁(yè)2023/2/1(3)常用的失真函數(shù)

第二種（平方誤差失真函數(shù)）：d(xi,yj)=(yj－xi)2

失真矩陣：平方誤差失真矩陣。若信源符號(hào)代表輸出信號(hào)的幅度值，則較大的幅度失真比較小的幅度失真引起的錯(cuò)誤更為嚴(yán)重,嚴(yán)重程度用平方表示。

第三種（絕對(duì)失真函數(shù)）：d(xi,yj)=|yj－xi|4.4信息率失真函數(shù)及性質(zhì)失真矩陣：絕對(duì)誤差失真矩陣。失真函數(shù)是根據(jù)人們的實(shí)際需要和失真引起的損失、風(fēng)險(xiǎn)、主觀感覺(jué)上的差別大小等因素人為規(guī)定的。第39頁(yè)2023/2/1(4)平均失真度平均失真度

d(xi,yj)只能表示兩個(gè)特定的具體符號(hào)xi和yj之間的失真。平均失真度：失真度的數(shù)學(xué)期望，即：4.4.1失真測(cè)度4.4信息率失真函數(shù)及性質(zhì)第40頁(yè)2023/2/1(4)平均失真度平均失真度的意義

是在平均意義上，從總體上對(duì)整個(gè)系統(tǒng)失真情況的描述。它是信源統(tǒng)計(jì)特性p(xi)、信道統(tǒng)計(jì)特性p(yj/xi

)和失真度d(xi,yj)的函數(shù)。當(dāng)p(xi)，p(yj/xi

)和d(xi,yj)給定后，平均失真度就不是一個(gè)隨機(jī)變量了，而是一個(gè)確定的量。如果信源和失真度一定，就只是信道統(tǒng)計(jì)特性的函數(shù)。信道傳遞概率不同，平均失真度隨之改變。保真度準(zhǔn)則

人們所允許的失真指的都是平均意義上的失真。保真度準(zhǔn)則：規(guī)定平均失真度不能超過(guò)某一限定的值D，即，則D

就是允許失真的上界。該式稱(chēng)為保真度準(zhǔn)則。4.4信息率失真函數(shù)及性質(zhì)第41頁(yè)2023/2/1(5)N次擴(kuò)展信道的平均失真度

N次擴(kuò)展

單符號(hào)離散無(wú)記憶信源X{x1,x2,…,xn}的N次擴(kuò)展信源XN

=X1X2…XN

，在信道中的傳遞作用相當(dāng)于單符號(hào)離散無(wú)記憶信道的N次擴(kuò)展信道，輸出也是一個(gè)隨機(jī)變量序列YN=Y1Y2…YN

。此時(shí)輸入共有nN個(gè)不同的符號(hào)：信道的輸出共有mN個(gè)不同的符號(hào)：4.4.1失真測(cè)度4.4信息率失真函數(shù)及性質(zhì)第42頁(yè)2023/2/1(5)N次擴(kuò)展信道的平均失真度

N次擴(kuò)展

定義離散無(wú)記憶信道{X

P(Y/X)Y}的N次擴(kuò)展信道的輸入序列X和輸出序列Y

之間的失真函數(shù)：定義的說(shuō)明：離散無(wú)記憶信道的N次擴(kuò)展信道輸入輸出之間的失真，等于輸入序列X中N個(gè)信源符號(hào)xi1,xi2,…,xiN各自通過(guò)信道{X

P(Y/X)Y}，分別輸出對(duì)應(yīng)的N個(gè)信宿符號(hào)yj1,yj2,…,yjN后所引起的N個(gè)單符號(hào)失真d(xik,yjk)(k=1,2,…,N)之和。

N次離散無(wú)記憶擴(kuò)展信源和信道的平均失真度為，則：4.4信息率失真函數(shù)及性質(zhì)第43頁(yè)2023/2/1(5)N次擴(kuò)展信道的平均失真度“N次擴(kuò)展”與“單符號(hào)”平均失真度的關(guān)系

由擴(kuò)展信源和擴(kuò)展信道的無(wú)記憶性有：（k=1,2,…,N）是同一信源X在N個(gè)不同時(shí)刻通過(guò)同一信道{X

P(Y/X)Y}所造成的平均失真度，因此都等于單符號(hào)信源X通過(guò)信道{X

P(Y/X)Y}所造成的平均失真度，即：結(jié)論說(shuō)明：離散無(wú)記憶N次擴(kuò)展信源通過(guò)離散無(wú)記憶N次擴(kuò)展信道的平均失真度是單符號(hào)信源通過(guò)單符號(hào)信道的平均失真度的N倍。N次擴(kuò)展的保真度準(zhǔn)則：離散無(wú)記憶N次擴(kuò)展信源通過(guò)離散無(wú)記憶N次擴(kuò)展信道的保真度準(zhǔn)則為：4.4信息率失真函數(shù)及性質(zhì)第44頁(yè)2023/2/1(1)試驗(yàn)信道單符號(hào)信源和單符號(hào)信道的試驗(yàn)信道當(dāng)固定信源（P(X)已知），單個(gè)符號(hào)失真度也給定時(shí)，選擇信道使。凡滿足要求的信道稱(chēng)為D失真許可的試驗(yàn)信道，簡(jiǎn)稱(chēng)試驗(yàn)信道。所有試驗(yàn)信道構(gòu)成的集合用PD來(lái)表示，即：4.4.2信息率失真函數(shù)的定義

N次擴(kuò)展的試驗(yàn)信道：

對(duì)于離散無(wú)記憶信源的N次擴(kuò)展信源和離散無(wú)記憶信道的N次擴(kuò)展信道，其試驗(yàn)信道集合PD(N)為：4.4信息率失真函數(shù)及性質(zhì)第45頁(yè)2023/2/14.4.2信息率失真函數(shù)的定義(2)信息率失真函數(shù)單符號(hào)信源和單符號(hào)信道的信息率失真函數(shù)

信息率失真函數(shù)（率失真函數(shù)）R(D)：在信源和失真度給定以后，PD是滿足保真度準(zhǔn)則的試驗(yàn)信道集合，平均互信息I(X;Y)是信道傳遞概率p(yj/xi)的下凸函數(shù)，所以在PD中一定可以找到某個(gè)試驗(yàn)信道，使I(X;Y)達(dá)到最小，即：在信源給定以后，總希望在允許一定失真的情況下，傳送信源所必須的信息率越小越好。從接收端來(lái)看，就是在滿足保真度準(zhǔn)則的條件下，尋找再現(xiàn)信源消息必須的最低平均信息量，即平均互信息的最小值。4.4信息率失真函數(shù)及性質(zhì)第46頁(yè)2023/2/14.4.2信息率失真函數(shù)的定義(2)信息率失真函數(shù)“N次擴(kuò)展”的信息率失真函數(shù)“N次擴(kuò)展”的信息率失真函數(shù)RN(D)：對(duì)于離散無(wú)記憶信源的N次擴(kuò)展信源和離散無(wú)記憶信道的N次擴(kuò)展信道，在所有滿足保真度準(zhǔn)則的N維試驗(yàn)信道集合中，一定可以尋找到某個(gè)信道使平均互信息取最小值：由信源和信道的無(wú)記憶性，可以證明：RN(D)=NR(D)4.4信息率失真函數(shù)及性質(zhì)第47頁(yè)2023/2/14.4.2信息率失真函數(shù)的定義(3)求信息率失真函數(shù)的方法對(duì)偶問(wèn)題：

平均互信息I(X;Y)既是信源概率分布p(xi)的上凸函數(shù)，又是信道傳遞概率p(yj/xi)的下凸函數(shù)。率失真函數(shù)R(D)是在允許平均失真度D和信源概率分布p(xi)已給的條件下，求平均互信息的極小值（最?。﹩?wèn)題。而信道容量C是在信道特性p(yj/xi)已知的條件下求平均互信息的極大值（最大）問(wèn)題。這兩個(gè)問(wèn)題是對(duì)偶問(wèn)題。求信道容量的方法：信道容量是假定信道固定的前提下，選擇一種試驗(yàn)信源，使信息率最大。一旦找到了這個(gè)信道容量，它就與信源不再有關(guān)，而是信道特性的參量，隨信道特性的變化而變化。4.4信息率失真函數(shù)及性質(zhì)第48頁(yè)2023/2/14.4.2信息率失真函數(shù)的定義(3)求信息率失真函數(shù)的方法求信息率失真函數(shù)的方法：

信息率失真函數(shù)R(D)是假定信源給定的情況下，在用戶(hù)可以容忍的失真度內(nèi)再現(xiàn)信源消息所必須獲得的最小平均信息量。它反映的是信源可壓縮程度。率失真函數(shù)一旦找到，就與求極值過(guò)程中選擇的試驗(yàn)信道不再有關(guān)，而只是信源特性的參量。不同的信源，其R(D)是不同的。4.4信息率失真函數(shù)及性質(zhì)第49頁(yè)2023/2/14.4.2信息率失真函數(shù)的定義(4)研究信道編碼和率失真函數(shù)的意義研究信道容量的意義：在實(shí)際應(yīng)用中，研究信道容量是為了解決在已知信道中傳送最大信息率問(wèn)題。目的是充分利用已給信道，使傳輸?shù)男畔⒘孔畲蠖l(fā)生錯(cuò)誤的概率任意小，以提高通信的可靠性。這就是信道編碼問(wèn)題。

研究信息率失真函數(shù)的意義：研究信息率失真函數(shù)是為了解決在已知信源和允許失真度D的條件下，使信源必須傳送給信宿的信息率最小。即用盡可能少的碼符號(hào)盡快地傳送盡可能多的信源消息，以提高通信的有效性。這是信源編碼問(wèn)題。4.4信息率失真函數(shù)及性質(zhì)第50頁(yè)2023/2/14.4.3信息率失真函數(shù)的性質(zhì)(1)率失真函數(shù)的定義域什么是率失真函數(shù)的定義域允許平均失真度：率失真函數(shù)中的自變量D，也就是人們規(guī)定的平均失真度的上限值。率失真函數(shù)的定義域問(wèn)題就是在信源和失真函數(shù)已知的情況下，討論允許平均失真度D的最小和最大值問(wèn)題。

D的選取必須根據(jù)固定信源X的統(tǒng)計(jì)特性p(x)和選定的失真函數(shù)d(xi,yj)，在平均失真度的可能取值范圍內(nèi)。4.4信息率失真函數(shù)及性質(zhì)第51頁(yè)2023/2/1(1)率失真函數(shù)的定義域信源最小平均失真度Dmin

是非負(fù)函數(shù)d(xi,yj)的數(shù)學(xué)期望，也是一個(gè)非負(fù)函數(shù)，顯然其下限為0。因此允許平均失真度D的下限也必然是0，這就是不允許有任何失真的情況。允許平均失真度D能否達(dá)到其下限值0，與單個(gè)符號(hào)的失真函數(shù)有關(guān)。

信源最小平均失真度Dmin

：對(duì)于每一個(gè)xi，找出一個(gè)yj與之對(duì)應(yīng)，使d(xi,yj)最小，不同的xi對(duì)應(yīng)的最小d(xi,yj)也不同。這相當(dāng)于在失真矩陣的每一行找出一個(gè)最小的d(xi,yj)，各行的最小d(xi,yj)值都不同。對(duì)所有這些不同的最小值求數(shù)學(xué)期望，就是信源的最小平均失真度。4.4信息率失真函數(shù)及性質(zhì)第52頁(yè)2023/2/1(1)率失真函數(shù)的定義域信源最小平均失真度Dmin

只有當(dāng)失真矩陣的每一行至少有一個(gè)0元素時(shí)，信源的平均失真度才能達(dá)到下限值0。

當(dāng)Dmin=0時(shí)（信源不允許任何失真存在），信息率至少應(yīng)等于信源輸出的平均信息量（信源熵），即R(0)=H(X)。連續(xù)信源有。這時(shí)雖然信源熵是有限的，但信息量是無(wú)窮大。實(shí)際信道容量總是有限的，無(wú)失真?zhèn)魉瓦@種連續(xù)信息是不可能的。只有當(dāng)允許失真（R(D)為有限值），傳送才是可能的。4.4.3信息率失真函數(shù)的性質(zhì)4.4信息率失真函數(shù)及性質(zhì)第53頁(yè)2023/2/1(1)率失真函數(shù)的定義域信源最小平均失真度Dmin

[舉例]：除刪信源X取值于{0,1}，Y取值于

{0,1,2}，失真矩陣為：滿足最小允許失真度的試驗(yàn)信道是一個(gè)無(wú)噪無(wú)損的試驗(yàn)信道：4.4信息率失真函數(shù)及性質(zhì)第54頁(yè)2023/2/1(1)率失真函數(shù)的定義域信源最大平均失真度Dmax

信源最大平均失真度Dmax：必須的信息率越小，容忍的失真就越大。當(dāng)R(D)等于0時(shí)，對(duì)應(yīng)的平均失真最大，也就是函數(shù)R(D)定義域的上界值Dmax

。信息率失真函數(shù)是平均互信息的極小值：當(dāng)R(D)=0時(shí)，平均互信息的極小值等于0；當(dāng)D>Dmax時(shí)，從數(shù)學(xué)意義上講，因?yàn)镽(D)是非負(fù)函數(shù)，所以它仍只能等于0。這相當(dāng)于輸入X和輸出Y統(tǒng)計(jì)獨(dú)立。意味著在接收端收不到信源發(fā)送的任何信息，與信源不發(fā)送任何信息等效?；蛘哒f(shuō)傳送信源符號(hào)的信息率可以壓縮至0。4.4信息率失真函數(shù)及性質(zhì)第55頁(yè)2023/2/1(1)率失真函數(shù)的定義域信源最大平均失真度Dmax

計(jì)算Dmax的值令試驗(yàn)信道特性p(yj/xi)=p(yj)(i=1,2,…,n)這時(shí)X和Y相互獨(dú)立，等效于通信中斷，因此I(X;Y)=0，即R(D)=0。滿足上式的試驗(yàn)信道有許多，相應(yīng)地可求出許多平均失真度值，從中選取最小的一個(gè)，就是這類(lèi)平均失真值的下界Dmax。4.4信息率失真函數(shù)及性質(zhì)第56頁(yè)2023/2/1(1)率失真函數(shù)的定義域信源最大平均失真度Dmax

計(jì)算Dmax的值上式是用不同的概率分布{p(yj)}對(duì)Dj求數(shù)學(xué)期望，取數(shù)學(xué)期望當(dāng)中最小的一個(gè)作為Dmax。實(shí)際是用p(yj)對(duì)Dj進(jìn)行線性分配，使線性分配的結(jié)果最小。當(dāng)p(xi)和d(xi,yj)給定時(shí)，必可計(jì)算出Dj

，Dj隨j的變化而變化，p(yj)是任選的，只需滿足非負(fù)性和歸一性。若Ds是所有Dj當(dāng)中最小的一個(gè)，可取p(ys)=1，其它p(yj)為0，這時(shí)Dj的線性分配（數(shù)學(xué)期望）必然最小，即：4.4信息率失真函數(shù)及性質(zhì)第57頁(yè)2023/2/1(1)率失真函數(shù)的定義域[例4.1.1]二元信源，相應(yīng)的失真矩陣，計(jì)算Dmax

。先計(jì)算Dj

：

根據(jù)概率的完備性：p(y1)+p(y2)=1當(dāng)p(y1)=0，p(y2)=1時(shí)，得到最小值：4.4信息率失真函數(shù)及性質(zhì)第58頁(yè)2023/2/1(1)率失真函數(shù)的定義域結(jié)論

R(D)的定義域?yàn)椋?Dmin,Dmax)

一般情況下：Dmin=0，R(Dmin)=H(X)

當(dāng)D≥Dmax時(shí)：R(D)=0

當(dāng)Dmin<D<Dmax時(shí)：0<R(D)<H(X)4.4.3信息率失真函數(shù)的性質(zhì)4.4信息率失真函數(shù)及性質(zhì)第59頁(yè)2023/2/14.4.3信息率失真函數(shù)的性質(zhì)(2)率失真函數(shù)對(duì)允許平均失真度的下凸性對(duì)任一0≤θ≤1和任意平均失真度D，D’’≤Dmax，

R[θD’+(1－θ)D’’]≤θR(D’)+(1－θ)R(D’’)。4.4信息率失真函數(shù)及性質(zhì)第60頁(yè)2023/2/14.4.3信息率失真函數(shù)的性質(zhì)(3)率失真函數(shù)的單調(diào)遞減和連續(xù)性R(D)的連續(xù)性：可由平均互信息I(X;Y)是信道傳遞概率p(yj/xi)的連續(xù)性來(lái)證明。R(D)單調(diào)遞減性：可以證明，在Dmin<D<Dmax范圍內(nèi)R(D)單調(diào)遞減。率失真函數(shù)曲線圖說(shuō)明

R(0)=H(X)，R(Dmax)=0，決定了曲線邊緣上的兩個(gè)點(diǎn)；在0和Dmax之間，R(D)是單調(diào)遞減的下凸函數(shù)；在連續(xù)信源時(shí)，當(dāng)D→0時(shí)，

R(D)→∞，曲線將不與R(D)

軸相交。4.4信息率失真函數(shù)及性質(zhì)第61頁(yè)2023/2/14.5信息率失真函數(shù)與信道容量對(duì)離散信源，求R(D)與求C類(lèi)似，是一個(gè)在有約束條件下求平均互信息極值問(wèn)題，只是約束條件不同；C是求平均互信息的條件極大值，R(D)是求平均互信息的條件極小值。第62頁(yè)2023/2/14.5.1信息率失真函數(shù)與信息價(jià)值信息價(jià)值比信息量更難定義，它與信息的接收者有關(guān)。同樣的信息對(duì)不同的使用者，信息量相同但價(jià)值卻不一樣。香農(nóng)信息論研究的是客觀信息量，一般不涉及接收者的情況。從信息率失真理論出發(fā)，如果把平均失真理解成平均損失，則損失的大小就與接收者的情況有關(guān)了，在此基礎(chǔ)上可定義信息價(jià)值，從而用信息論解決實(shí)際問(wèn)題。4.5信息率失真函數(shù)與信道容量第63頁(yè)2023/2/14.5.1信息率失真函數(shù)與信息價(jià)值說(shuō)明：

信息價(jià)值隨著信息率的增加而增加；獲取信息要付出代價(jià)，得到信息會(huì)獲得利益。一般來(lái)說(shuō)，獲得的信息越多，付出的代價(jià)也越大；信息價(jià)值的概念從理論上定量地證明了信息是財(cái)富的假說(shuō)；進(jìn)一步的研究證明：信息還可以代替人力、物質(zhì)、能源和資本，從而得到更多的經(jīng)濟(jì)利益。這些問(wèn)題的深入討論涉及到信息經(jīng)濟(jì)學(xué)理論，屬于廣義信息論范疇。4.5信息率失真函數(shù)與信道容量第64頁(yè)2023/2/14.5.2信道容量與信息率失真函數(shù)的比較

從數(shù)學(xué)上說(shuō)，信道容量和信息率失真函數(shù)的問(wèn)題，都是求平均互信息極值問(wèn)題，有相仿之處，故常稱(chēng)為對(duì)偶問(wèn)題。(1)

求極值問(wèn)題(2)

特性(3)

解決的問(wèn)題4.5信息率失真函數(shù)與信道容量第65頁(yè)2023/2/14.5.2信道容量與信息率失真函數(shù)的比較(1)求極值問(wèn)題平均互信息I(X;Y)是信源概率分布p(xi)(i=1,2,…,n)或概率密度函數(shù)p(x)的上凸函數(shù)。根據(jù)上凸函數(shù)定義，如果I(X;Y)在定義域內(nèi)對(duì)p(xi)或p(x)的極值存在，則該極值一定是極大值。信道容量就是在固定信道情況下，求平均互信息極大值的問(wèn)題，即：4.5信息率失真函數(shù)與信道容量第66頁(yè)2023/2/14.5.2信道容量與信息率失真函數(shù)的比較(1)求極值問(wèn)題I(X;Y)又是信道轉(zhuǎn)移概率分布p(yj/xi)(i=1,2,…,n；j=1,2,…,m)或條件概率密度函數(shù)p(y/x)的下凸函數(shù)，因此在滿足保真度準(zhǔn)則條件下，I(X;Y)對(duì)p(yj/xi)或p(y/x)的條件極值若存在，則一定是極小值。信息率失真函數(shù)就是在試驗(yàn)信道（滿足保真度準(zhǔn)則的信道）中尋找平均互信息極小值的問(wèn)題，即：4.5信息率失真函數(shù)與信道容