信息論與編碼-第7講-信源及其信息量6-無失真信源編碼定理

第1頁2024/4/14第二章信源及其信息量本章重點：信源的統(tǒng)計特性和數(shù)學(xué)模型、各類信源的信息測度—熵及其性質(zhì)。2.1單符號離散信源2.2多符號離散平穩(wěn)信源2.3連續(xù)信源2.4離散無失真信源編碼定理2.5小結(jié)ElectronicsEngineeringDepartment,XXXXXxxXxxx第2頁2024/4/142.4離散無失真信源編碼定理2.4.1問題的提出2.4.2等長／定長編碼定理2.4.3不等長編碼定理2.4離散無失真信源編碼定理第3頁2024/4/142.4.1問題的提出(1)為什么要進(jìn)行信源編碼(2)信源編碼的概念(3)一些碼的定義(4)信源編碼的方法2.4離散無失真信源編碼定理第4頁2024/4/142.4.1問題的提出(1)為什么要進(jìn)行信源編碼信源的兩個重要問題信源輸出的信息量計算問題；如何更有效地表示信源輸出的問題。信源編碼就是為了提高通信效率，對信源所發(fā)送的消息進(jìn)行變換的方法之一。為什么要進(jìn)行信源編碼人們都希望無失真?zhèn)魉?，首先要對信源無差錯編碼；數(shù)字技術(shù)應(yīng)用越來越多，模擬信源通過數(shù)字化變成數(shù)字信號傳送。2.4離散無失真信源編碼定理第5頁2024/4/142.4.1問題的提出(2)信源編碼的概念信源編碼定義：指定能夠滿足信道特性（適合于信道傳輸）的符號序列—碼序列，來代表信源輸出的消息。

編碼器：完成編碼功能的器件。離散信源輸出的碼序列離散信源輸出的消息是由一個個離散符號組成的隨機序列信源編碼就是把信源輸出的隨機符號序列變成碼序列2.4離散無失真信源編碼定理第6頁2024/4/142.4.1問題的提出(2)信源編碼的概念研究信源編碼時，將信道編碼和譯碼看成是信道的一部分，而突出信源編碼；研究信道編碼時，將信源編碼和譯碼看成是信源和信宿的一部分，而突出信道編碼。2.4離散無失真信源編碼定理第7頁2024/4/142.4.1問題的提出(2)信源編碼的概念討論無失真信源編碼可以先不考慮抗干擾問題，所以它的數(shù)學(xué)模型比較簡單，如圖2.4.0。2.4離散無失真信源編碼定理第8頁2024/4/142.4.1問題的提出(2)信源編碼的概念信源符號：編碼器的輸入是信源符號X={x1,x2,…,xi,…,xn}信源符號序列：碼符號/碼元：元素

cj是適合信道傳輸?shù)姆枺?/p>

C={c1,c2,…,cj,…,cr}稱為碼符號/碼元。碼字（碼符號序列）：碼長（碼字長度）：

li稱為碼字Wi

的碼長。編碼：從信源符號到碼符號的一種映射。若要實現(xiàn)無失真編碼，這種映射必須是一一對應(yīng)的，可逆的。2.4離散無失真信源編碼定理第9頁2024/4/142.4.1問題的提出(2)信源編碼的概念編碼器功能：將信源符號集中的符號xi（或者長為N

的信源符號序列）變換成由cj(j=1,2,

…,r)

組成的長度為li的序列。2.4離散無失真信源編碼定理第10頁2024/4/142.4.1問題的提出(3)一些碼的定義二元碼：碼符號集為X={0,1}，所得碼字都是一些二元序列。等長碼（定長碼）：一組碼中所有碼字的碼長都相同，即：li=L(i=1,2,…,n)。不等長碼（變長碼）：一組碼字中所有碼字的碼長各不相同，即任意碼字由不同長度的碼符號序列組成。2.4離散無失真信源編碼定理第11頁2024/4/142.4.1問題的提出(3)一些碼的定義非奇異碼：一組碼字中所有碼字都不相同，即所有信源符號影射到不同的碼符號序列。奇異碼：一組碼中有相同的碼字。唯一可譯碼：碼的任意一串有限長的碼符號序列只能被唯一地譯成所對應(yīng)的信源符號。2.4離散無失真信源編碼定理第12頁2024/4/142.4.1問題的提出(3)一些碼的定義舉例：設(shè)信源X

的概率空間為：把它通過一個二元信道傳輸；為使信源適合信道傳輸，必須把信源符號變換成0、1符號組成的碼符號序列（二元序列）；可采用不同的二元序列使其與信源符號一一對應(yīng)，得到不同的二元碼。2.4離散無失真信源編碼定理第13頁2024/4/142.4.1問題的提出(3)一些碼的定義舉例：碼1是等長非奇異碼，碼2是不等長非奇異碼。2.4離散無失真信源編碼定理第14頁2024/4/142.4.1問題的提出(3)一些碼的定義碼的N

次擴展：以碼2的二次擴展為例X2=[α1=x1x1,α2=x1x2,α3=x1x3,…,α16=x4x4]

所以碼的二次擴展為：2.4離散無失真信源編碼定理第15頁2024/4/142.4.1問題的提出(3)一些碼的定義碼字與信息率的關(guān)系有時消息太多，不可能或者沒必要給每個消息都分配一個碼字；給多少消息分配碼字可以做到幾乎無失真譯碼？傳送碼字需要一定的信息率，碼字越多，所需的信息率越大。編多少碼字的問題可以轉(zhuǎn)化為對信息率大小的問題；信息率越小越好，最小能小到多少才能做到無失真譯碼呢？這些問題就是信源編碼定理要研究的問題。2.4離散無失真信源編碼定理第16頁2024/4/142.4.1問題的提出(4)信源編碼的方法信源編碼有等長和不等長兩種方法。等長編碼：碼字長度L

是固定的，相應(yīng)的編碼定理稱為等長信源編碼定理，是尋求最小L值的編碼方法。不等長編碼：L是變值，相應(yīng)的編碼定理稱為不等長編碼定理。這里的L值最小意味著數(shù)學(xué)期望最小。2.4離散無失真信源編碼定理第17頁2024/4/142.4.2等長編碼定理(1)等長編碼定理等長編碼定理：一個熵為H(X)的離散無記憶信源X1X2…Xl…XN，若對信源長為N的符號序列進(jìn)行等長編碼，設(shè)碼字是從r個字母的碼符號集中，選取L個碼元組成c1c2…cl…cL。對于任意ε>0，δ>0，只要滿足：則當(dāng)N足夠大時，必可使譯碼差錯小于δ，即譯碼錯誤概率能為任意小。反之，若：

則不可能實現(xiàn)無失真編碼，而當(dāng)N足夠大時，譯碼錯誤概率近似等于1。2.4離散無失真信源編碼定理第18頁2024/4/142.4.2等長編碼定理(1)等長編碼定理定理中的公式改寫成：Llog2r>NH(X)

Llog2r：表示長為L的碼符號序列能載荷的最大信息量

NH(X)

：代表長為

N的信源序列平均攜帶的信息量平均符號熵。

等長編碼定理告訴我們：只要碼字傳輸?shù)男畔⒘看笥谛旁磾y帶的信息量，總可實現(xiàn)幾乎無失真編碼。2.4離散無失真信源編碼定理編碼效率譯碼差錯率δ第19頁2024/4/142.4.2等長編碼定理(1)等長編碼定理可以證明：信息熵H(X)就是一個界限（臨界值）。當(dāng)編碼器輸出的信息率超過這個臨界值時，就能無失真譯碼，否則就不行。2.4離散無失真信源編碼定理譯碼差錯率小于任意正整數(shù)δ。第20頁2024/4/142.4.2等長編碼定理(1)等長編碼定理

信源編碼定理從理論上說明了編碼效率接近于1，即：的理想編碼器的存在性，代價是在實際編碼時取無限長的信源符號(N→∞)進(jìn)行統(tǒng)一編碼。說明：等長編碼定理是在平穩(wěn)無記憶離散信源的條件下論證的，但它同樣適用于平穩(wěn)有記憶信源，只是要求有記憶信源的極限熵和極限方差存在即可。對于平穩(wěn)有記憶信源，定理中的熵應(yīng)改為極限熵。2.4離散無失真信源編碼定理第21頁2024/4/142.4.2等長編碼定理(2)舉例[例2.4.1]：設(shè)單符號信源模型為：其信息熵為：H(X)=2.55（比特／符號）

σ2(x)=1.323若要求編碼效率為η=

90%，即：譯碼差錯率為δ=10－6，則ε=0.28，在差錯率和效率要求都不苛刻的情況下，就必須有1600多萬個信源符號一起編碼，技術(shù)實現(xiàn)非常困難。2.4離散無失真信源編碼定理第22頁2024/4/142.4.2等長編碼定理(2)舉例[例]：離散無記憶信源：其信息熵為：自信息的方差為：2.4離散無失真信源編碼定理第23頁2024/4/142.4.2等長編碼定理(2)舉例[例]：若對信源X采取等長二元編碼時，要求η=0.96，δ=10－5信源序列長度需長達(dá)4130萬以上，才能實現(xiàn)給定的要求，這在實際中很難實現(xiàn)。一般來說，當(dāng)N

有限時，高傳輸效率的等長碼往往要引入一定的失真和錯誤，它不能像變長碼那樣可以實現(xiàn)無失真編碼。2.4離散無失真信源編碼定理第24頁2024/4/14DepartmentofElectronicsandInformation,NCUTSongPeng2.4.3不等長編碼定理(1)基本概念(2)碼樹圖(3)克拉夫特不等式(4)變長編碼定理2.4離散無失真信源編碼定理第25頁2024/4/142.4.3不等長編碼定理(1)基本概念不等長編碼（變長編碼）：不等長編碼允許把等長的消息變換成不等長的碼序列。通常把經(jīng)常出現(xiàn)的消息編成短碼，不常出現(xiàn)的消息編成長碼。這樣可使平均碼長最短，從而提高通信效率，代價是增加了編譯碼設(shè)備的復(fù)雜度。例如：在不等長碼字組成的序列中要正確識別每個長度不同的碼字的起點就比等長碼復(fù)雜得多。譯碼延時／譯碼同步：接收到一個不等長碼序列后，有時不能馬上斷定碼字是否真正結(jié)束，因而不能立即譯出該碼，要等到后面的符號收到后才能正確譯出。2.4離散無失真信源編碼定理第26頁2024/4/142.4.3不等長編碼定理(1)基本概念[例2.4.2]：碼1：顯然不是唯一可譯碼。x2

和x4

對應(yīng)于同一碼字“11”，碼1

是一個奇異碼。碼2：是非奇異碼，不是唯一可譯碼。當(dāng)收到一串碼符號“01000”時，可將它譯成“x4x3x1”，也可譯為“x4x1x3”，“x1x2x3”或“x1x2x1x1”等，這種碼從單個碼字來看雖然不是奇異的，但從有限長的碼序列來看，它仍然是一個奇異碼。2.4離散無失真信源編碼定理第27頁2024/4/142.4.3不等長編碼定理(1)基本概念[例2.4.2]：碼3：雖然是唯一可譯碼，但它要等到下一個“1”收到后才能確定碼字的結(jié)束，譯碼有延時。碼4：既是唯一可譯碼，又沒有譯碼延時。碼字中的符號“1”起了逗點的作用，故稱為逗點碼。即時碼/前綴條件碼/異前置碼/異字頭碼/逗點碼/非延長碼：如果一個碼的任何一個碼字都不是其它碼字的前綴。碼4是即時碼2.4離散無失真信源編碼定理

(2)碼樹圖

r

元（r

進(jìn)制）碼樹圖樹根：最頂部畫一個起始點。樹枝：從根部引出

r

條線段，每條線段都稱為樹枝。一級節(jié)點：自根部起，通過一條樹枝到達(dá)的節(jié)點。一級節(jié)點最多有r

個。n級節(jié)點：通過

n

條樹枝達(dá)到的節(jié)點。最多有rn。第28頁2024/4/142.4.3不等長編碼定理2.4離散無失真信源編碼定理第29頁2024/4/14

(2)碼樹圖終節(jié)點/終端節(jié)點：下面不再有樹枝的節(jié)點。中間節(jié)點：除了樹根和終節(jié)點以外的節(jié)點。聯(lián)枝：串聯(lián)的樹枝。滿樹：在碼樹圖中，當(dāng)每一個碼字的串聯(lián)枝數(shù)都相同時，就是等長碼。此時的碼樹稱為滿樹。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第30頁2024/4/14

(2)碼樹圖例如：碼長為N的滿樹的終節(jié)點個數(shù)為rN，即可表示rN個碼字。非滿樹：有些樹枝未用時的碼樹。

非滿樹構(gòu)造的就是變長碼。

如果每一個碼字都被安排在終節(jié)點上，這種碼就是即時碼。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第31頁2024/4/14(3)克拉夫特不等式克拉夫特不等式：r

元長度為li，i=1,2,…,n的即時碼存在的充要條件是：證明：必要條件：設(shè)即時碼第

i個碼字的長度為li，i=1,2,…,n造一個碼樹圖，在第

li級總共有個節(jié)點。第

i個碼字占據(jù)了第

li級的，根據(jù)即時碼的定義，其后的樹枝不能再用。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第32頁2024/4/14(3)克拉夫特不等式

克拉夫特不等式：r

元長度為li，i=1,2,…,n的即時碼存在的充要條件是：證明：必要條件：對于

N級滿樹，其后不能用的枝數(shù)為，那么總共不用的枝數(shù)為。

N

級滿樹第

N級上的總枝數(shù)已知為rN，所以必有兩邊除以rN，就得：。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第33頁2024/4/14(3)克拉夫特不等式

克拉夫特不等式：r

元長度為li，i=1,2,…,n的即時碼存在的充要條件是：證明：充分條件：如果式

成立，則必成立，總可以把第N

級上的樹枝分成n

組；各組中從第N

級開始刪除

(i=1,2,…,n)個枝；相對于N

級滿樹，等于刪除了所有可能的

li級節(jié)點的2.4.3不等長編碼定理2.4離散無失真信源編碼定理第34頁2024/4/14(3)克拉夫特不等式

克拉夫特不等式：r

元長度為li，i=1,2,…,n的即時碼存在的充要條件是：證明：充分條件：在該組中以第li

級節(jié)點作為終節(jié)點，就構(gòu)造好了第

i

個碼字。對所有碼字如法炮制，則總共刪除了所有

rN個節(jié)點中的。由，構(gòu)造了一個即時碼。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第35頁2024/4/14(4)不等長編碼定理①不等長編碼定理（香農(nóng)第一定理）平均碼長：不等長編碼定理：若一離散無記憶信源的平均符號熵為H(X)，對信源符號進(jìn)行

r元變長編碼，一定存在一種無失真編碼方法，其碼字平均長度滿足下列不等式：其平均信息率滿足不等式

H(X)+ε>R≥H(X)，式中ε為任意正數(shù)。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第36頁2024/4/14(4)不等長編碼定理①不等長編碼定理（香農(nóng)第一定理）證明：設(shè)信源符號X∈{x1,x2,…,xi,…,xn}，概率p(xi)(i=1,2,…,n)

對

xi用一個長度為

li的碼字，使：規(guī)定為正整數(shù)時，上式取等號，非整數(shù)時，li

取比它大一些的最接近的整數(shù)，則滿足上式的整數(shù)必存在。將上式分別乘以p(xi)

再對

i求和，得：2.4.3不等長編碼定理2.4離散無失真信源編碼定理第37頁2024/4/14(4)不等長編碼定理①不等長編碼定理（香農(nóng)第一定理）證明：對

li取數(shù)學(xué)期望就是平均值，故：由上面式子可得

lilog2r≥－log2p(xi)，或，對兩邊求和得：碼字長度滿足克拉夫特不等式，因而是即時碼。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第38頁2024/4/14(4)不等長編碼定理①不等長編碼定理（香農(nóng)第一定理）證明：多符號情況對于平穩(wěn)無記憶信源來說，當(dāng)信源輸出的是長度為N的消息序列時，容易證明定理中式子可改進(jìn)為：這時的代表平均碼序列長度。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第39頁2024/4/14(4)不等長編碼定理①不等長編碼定理（香農(nóng)第一定理）證明：多符號情況已知編碼后平均每個信源符號能載荷的最大信息量為（不等長信源編碼信源平均輸出信息率）：2.4.3不等長編碼定理2.4離散無失真信源編碼定理第40頁2024/4/14(4)不等長編碼定理①不等長編碼定理（香農(nóng)第一定理）對信源進(jìn)行不等長編碼一般所要求的信源符號長度N

比定長編碼小的多。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第41頁2024/4/14(4)不等長編碼定理①不等長編碼定理（香農(nóng)第一定理）信道的信息傳輸率為（從信道的角度看）：編碼效率定義為：二元無損無噪信道中r=2，所以Hr(X)=H(X)2.4.3不等長編碼定理2.4離散無失真信源編碼定理第42頁2024/4/14(4)不等長編碼定理②舉例[例2.4.1]：設(shè)單符號信源模型為：其信息熵為：H(X)=2.55（比特/符號）這里r=2，log2r=1要求η>90%，則：2.4.3不等長編碼定理2.4離散無失真信源編碼定理第43頁2024/4/14(4)不等長編碼定理②舉例[例2.4.1]：與等長編碼相比，對同一信源，要求編碼效率都達(dá)到90%

時，變長編碼只需N=4

進(jìn)行編碼，而等長碼則要求N

大于1.6875×107。用變長編碼時,N不需要很大就可以達(dá)到相當(dāng)高的編碼效率而且可實現(xiàn)無失真編碼。2.4.3不等長編碼定理2.4離散無失真信源編碼定理第44頁2024/4/142.4.3不等長編碼定理(4)不等長編碼定理②舉例[例]：離散無記憶信源：其信息熵為：用二元碼符號(0,1)來構(gòu)造一個即時碼：x1→0，x2→1這時平均碼長：編碼效率為：信道信息傳輸率為：R=0.811比特/二元碼符號2.4離散無失真信源編碼定理第45頁2024/4/142.4.3不等長編碼定理(4)不等長編碼定理②舉例[例]：為了提高傳輸效率，對無記憶信源X

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

及其某一個即時碼：

這個碼的平均長度為：

信源符號X中每一單個符號的平均碼長為：2.4離散無失真信源編碼定理第46頁2024/4/142.4.3不等長編碼定理(4)不等長編碼定理②舉例[例]：其編碼效率為：編碼復(fù)雜了一些，但信息傳輸率有了提高。對信源X的三次和四次擴展信源進(jìn)行編碼，編碼效率為：2.4離散無失真信源編碼定理第47頁2024/4/142.4.3不等長編碼定理(4)不等長編碼定理②舉例[例]：與等長碼比較：對于同一信源，要求編碼效率都達(dá)到96%時，變長碼只需對二次擴展信源（N=2）進(jìn)行編碼，而等長碼則要求N>4.13×107。結(jié)論用變長碼編碼時，N不需要很大就可以達(dá)到相當(dāng)高的編碼效率，而且可以實現(xiàn)無失真編碼。隨著擴展信源次數(shù)的增加，編碼的效率越來越接近于1比特/二元碼符號，達(dá)到信源與信道匹配，使信道得到充分利用。2.4離散無失真信源編碼定理第48頁2024/4/14(1)單符號離散信源①信息量自信息、條件自信息概念、性質(zhì)、計算2.5小結(jié)第49頁2024/4/14(1)單符號離散信源②信息熵信息熵的概念、性質(zhì)、計算無條件熵、條件熵（信道疑義度、噪聲熵）2.5小結(jié)第50頁2024/4/14(1)單符號離散信源②信息熵信息熵的性質(zhì)：若離散隨機變量X的概率分布為，則H(P)具有以下性質(zhì)：2.5小結(jié)第51頁2024/4/14(1)單符號離散信源②信息熵信息熵的性質(zhì)：若離散隨機變量X的概率分布為，則H(P)具有以下性質(zhì)：2.5小結(jié)第52頁2024/4/14(1)單符號離散信源②信息熵信息熵的性質(zhì)：若離散隨機變量X的概率分布為，則H(P)具有以下性質(zhì)：2.5小結(jié)第53頁2024/4/14(1)單符號離散信源②信息熵互信息概念、性質(zhì)、計算平均互信息概念、性質(zhì)、計算2.5小結(jié)第54頁2024/4/14(1)單符號離散信源②信息熵平均條件互信息：三個離散隨機變量X，Y和Z之間的平均條件互信息平均互信息：三個離散隨機變量X，Y和Z之間的平均互信息2.5小結(jié)第55頁2024/4/14(1)單符號離散信源②信息熵平均互信息的性質(zhì)2.5小結(jié)第56頁2024/4/14(2)多符號離散信源①離散平穩(wěn)無記憶信源概念、計算離散無記憶信源的N次擴展信源的熵：H(X)=H(XN)=NH(X)2.5小結(jié)第57頁2024/4/14(2)多符號離散信源②離散平穩(wěn)有記憶信源概念、簡單計算條件熵、極限熵概念、簡單計算離散平穩(wěn)信源的平均符號熵：離散平穩(wěn)信源的條件熵：H(XN/X1X2…XN－1)離散平穩(wěn)信源的極限熵：2.5