信息論導論-第3章-2013

第3章離散信源無失真編碼趙宏志2013年3月《信息論導論》2復習

信息熵的含義離散平穩(wěn)無記憶信源馬爾可夫信源3信源發(fā)出的消息需要傳輸或存儲才能發(fā)揮作用，而對于傳輸或存儲來說，現(xiàn)在二進制信號最具優(yōu)勢。信息傳輸?shù)?個關鍵要求：效率、可靠、安全第3章離散信源無失真編碼為了滿足信道特性，往往需要將n元的信源符號序列變換為m元(現(xiàn)在一般為二元)的信源碼序列，這一過程就是信源編碼。4②怎樣有效地利用碼字的每一個比特去攜帶信息，即在編碼過程中怎樣用最少的比特數(shù)去表示信源的信息熵？①怎樣保證編碼和譯碼過程不丟失信息，即怎樣實現(xiàn)無失真編碼？③無失真編碼的具體方法？第3章離散信源無失真編碼信源編碼的3個問題是：5第3章的主要內(nèi)容與課時一、無失真編碼的基本思路二、無失真編碼定理三、香農(nóng)編碼四、霍夫曼編碼6一、無失真編碼的基本思路先看一個單符號離散信源無失真編碼的例子：其信息熵7無失真編碼的含義：保證符號元與碼字一一對應，此時用碼序列表示的信源信息熵保持不變。最簡單的無失真編碼：4-2進制變換，即該編碼的碼長K=2，碼字的每一個比特攜帶信息的效率即編碼效率一、無失真編碼的基本思路思考：效率可以再提高嗎？8為了壓縮比特數(shù)，可以考慮對信源符號進行不等長編碼，如碼字的比特數(shù)中約有17.6%未攜帶信息，屬于冗余比特，傳輸效率不高。但該編碼不能實現(xiàn)無失真譯碼，即不能保證符號元與碼字的一一對應。一、無失真編碼的基本思路可以無失真譯碼嗎？9其平均碼長一種能保證符號元與碼字一一對應的不等長編碼為編碼效率與第一種編碼相比，碼字壓縮了0.3個比特，編碼效率提高了14.5%。一、無失真編碼的基本思路10進一步，如果對該信源的二次擴展信源進行無失真編碼，一種能保證符號序列元與碼字一一對應的不等長編碼為一、無失真編碼的基本思路11其平均碼長編碼效率一、無失真編碼的基本思路12與第二種編碼相比，碼字又壓縮了約0.04個比特，編碼效率提高了2.1%。總結該例子，有以下幾點結論與問題：①一般采用不等長編碼，使平均碼長接近信息熵，從而在無失真前提下提高編碼效率；編碼的基本原則是大概率符號元編成短碼，小概率符號元編成長碼。一、無失真編碼的基本思路13②由于碼長不等，如何保證接收端從碼序列中唯一地分割出對應與每一個符號元的碼字，以實現(xiàn)無失真譯碼？③對符號序列進行組(block)編碼有助于使平均碼長接近信息熵，但平均碼長能否無限接近信息熵，從而使編碼效率趨近1？如果能，對序列長度有什么要求？一、無失真編碼的基本思路引發(fā)的問題14第3章的主要內(nèi)容與課時一、無失真編碼的基本思路二、無失真編碼定理三、香農(nóng)編碼四、霍夫曼編碼15二、無失真編碼定理1、異前置碼如果所采用的不等長編碼使接收端能從碼序列中唯一地分割出對應與每一個符號元的碼字，則稱該不等長編碼為單義可譯碼。單義可譯碼中，如果能在對應于每一個符號元的碼字結束時立即譯出的稱為即時碼，如果要等到對應與下一個符號元的碼字才能譯出的稱為延時碼。16碼A--不是單義可譯碼，它有二義性碼B和碼C才是單義可譯碼；碼B是延時碼，它需等到對應與下一個符號元的碼字開頭0才能確定本碼字的結束，存在譯碼延時，只有碼C才是即時碼。二、無失真編碼定理17從樹根開始到每一個終節(jié)點的聯(lián)枝代表一個碼字，故相應的異前置碼碼C的特點是：任何一個碼字都不是其他碼字的前綴，因此將該碼稱為異前置碼。異前置碼可以用樹圖來構造：一個三元碼樹圖二、無失真編碼定理18碼C所對應的二元碼樹圖m元長度為ki,i=1,2,…,n的異前置碼存在的充分必要條件是：該充要條件稱為克拉夫特(Kraft)不等式。二、無失真編碼定理19設m元異前置碼第i個碼字的長度為ki,i=1,2,…,n考慮一個N級滿樹，在第N級共有mN個節(jié)點，在第ki級共有mki個節(jié)點。根據(jù)異前置碼的定義，第i個碼字后的節(jié)點不能再用，故第N級不能用的節(jié)點數(shù)為mN-ki構造異前置碼的碼樹圖第N級上總共不能用的節(jié)點總數(shù)二、無失真編碼定理20【無失真編碼定理】如果N維離散平穩(wěn)信源的平均符號熵為HN(X1X2…XN)，對信源符號序列進行m元不等長組編碼，一定存在一種無失真編碼方法，當N足夠大時，使得每個信源符號所對應碼字的平均比特數(shù)式中，ε為任意給定的小正數(shù)。二、無失真編碼定理21Kraft不等式設不等長組編碼對應于符號元ai=xi1xi2…xiN的碼字長度為ki說明該編碼是異前置碼【無失真編碼定理】的證明22其平均碼長【無失真編碼定理】的證明23無失真編碼定理又叫香農(nóng)第一定理，該定理從理論上闡明了編碼效率的理想無失真編碼的存在性.【無失真編碼定理】的證明24無失真編碼的代價是取無限長的符號序列進行組編碼，即只有N→∞時可見，極限熵H∞是一個界限，通常也稱為(信源編碼的)香農(nóng)界。二、無失真編碼定理25剛才討論了一般的離散平穩(wěn)信源，對其他已學過的離散信源，根據(jù)無失真編碼定理可得出什么結論呢？N維離散平穩(wěn)無記憶信源m階馬爾科夫信源二、無失真編碼定理26N維離散平穩(wěn)無記憶信源由于其平均符號熵HN(X1X2…XN)=H(X)式中，ε為任意給定的小正數(shù)。此時香農(nóng)界為H(X)。二、無失真編碼定理故對信源符號序列進行m元不等長組編碼，一定存在一種無失真編碼方法，當N足夠大時，使得每個信源符號所對應碼字的平均比特數(shù)27m階馬爾科夫信源(m<N),N足夠大時，平均符號熵HN(X1X2…XN)=Hm+1式中，ε為任意給定的小正數(shù)。此時香農(nóng)界為Hm+1。二、無失真編碼定理對信源符號序列進行m元不等長組編碼，一定存在一種無失真編碼方法，使得每個信源符號對應碼字的平均比特數(shù)28平穩(wěn)無記憶信源的香農(nóng)界H(X)大于m階馬爾科夫信源的香農(nóng)界Hm+1，而m階馬爾科夫信源的香農(nóng)界Hm+1又大于一般平穩(wěn)信源的香農(nóng)界H∞。因此，對離散平穩(wěn)信源進行無失真編碼，每個信源符號所對應碼字的平均比特數(shù)平穩(wěn)無記憶信源最多，m階馬爾科夫信源次之，一般平穩(wěn)信源最少。二、無失真編碼定理29一、無失真編碼的基本思路二、無失真編碼定理三、香農(nóng)編碼四、霍夫曼編碼第3章的主要內(nèi)容與課時30三、香農(nóng)編碼設離散信源香農(nóng)編碼是一種采用異前置碼的m進制編碼方法。不失一般性，設p(x1)>p(x2)>…>p(xn)，且31①將符號元xi按概率進行降序排列；②令p(x0)=0，計算第i個碼字的累加概率③確定第i個碼字的碼長ki，ki為滿足下列不等式的最小整數(shù)：④將pa(xi)用二進制表示，取小數(shù)點后ki位作為符號元xi的碼字。三、香農(nóng)編碼—編碼步驟32例1，對單符號離散信源編二進制香農(nóng)碼，并計算其編碼效率。解：①將xi按概率進行降序排列xip(xi)pa(xi)ki碼字x10.5x20.3x30.15x40.05三、香農(nóng)編碼—舉例33②令p(x0)=0，計算第i個碼字的累加概率pa(x1)=0pa(x2)=0+0.5=0.5pa(x3)=0.5+0.3=0.8pa(x4)=0.8+0.15=0.95③確定第i個碼字的碼長ki：三、香農(nóng)編碼34④將pa(xi)用二進制表示，取小數(shù)點后ki位作為xi的碼字pa(x1)=0.0=(0.0)2→0pa(x2)=0.5=(0.10)2→10pa(x3)=0.8=(0.110…)2→110pa(x4)=0.95=(0.11110…)2→11110三、香農(nóng)編碼35xip(xi)pa(xi)ki碼字x10.5010x20.30.5210x30.150.83110x40.050.95511110三、香農(nóng)編碼36三、香農(nóng)編碼37例2，分別對下列單符號離散信源和該信源的二次擴展信源編二進制香農(nóng)碼，并計算其編碼效率。解：⑴對單符號離散信源編碼pa(x1)=0pa(x2)=0+0.5=0.5pa(x3)=0.5+0.3=0.8三、香農(nóng)編碼38pa(x1)=0.0=(0.0)2→0pa(x2)=0.5=(0.10)2→10pa(x3)=0.8=(0.110…)2→110三、香農(nóng)編碼39xip(xi)pa(xi)ki碼字x10.5010x20.30.5210x30.20.83110三、香農(nóng)編碼40⑵對二次擴展信源編碼將符號元ai按概率進行降序排列pa(a1)=0pa(a2)=0+0.25=0.25pa(a3)=0.25+0.15=0.4pa(a4)=0.4+0.15=0.55三、香農(nóng)編碼41pa(a5)=0.55+0.1=0.65pa(a6)=0.65+0.1=0.75pa(a7)=0.75+0.09=0.84pa(a8)=0.84+0.06=0.9pa(a9)=0.9+0.06=0.96三、香農(nóng)編碼42三、香農(nóng)編碼43pa(a1)=0.0=(0.00)2→00pa(a2)=0.25=(0.010)2→010pa(a3)=0.4=(0.011…)2→011三、香農(nóng)編碼44pa(a4)=0.55=(0.1000…)2→1000pa(a5)=0.65=(0.1010…)2→1010pa(a6)=0.75=(0.1100)2→1100pa(a7)=0.84=(0.11010…)2→11010pa(a8)=0.9=(0.11100…)2→11100pa(a9)=0.96=(0.11101…)2→11101aip(ai)pa(ai)ki碼字a10.250200a20.150.253010a30.150.43011三、香農(nóng)編碼45a40.10.5541000a50.10.6541010a60.090.7541100a70.060.84511010a80.060.9511100a90.040.96511101三、香農(nóng)編碼46三、香農(nóng)編碼47DavidAlbertHuffman(August9,1925–October7,1999)四、霍夫曼編碼1944年畢業(yè)于俄亥俄州立大學電子工程系，畢業(yè)后服役于美國海軍，大黃蜂號航母，兵種：廚師。1949年獲得俄亥俄州立大學電子工程系碩士學位；1953年獲MIT電子工程系博士學位。1953年博士畢業(yè)后留校任教；1967年起任教于加州大學圣克魯茲分校，直至1994年退休。霍夫曼一生建樹很多，主要貢獻有信息論、編碼、雷達信號設計、邏輯電路設計。他最著名的霍夫曼編碼來自于碩士期間的某門課程的期末考試報告?；舴蚵鼜奈礊樗某删蜕暾垖＠毅憽癕yproductsaremystudents”48四、霍夫曼(Huffman)編碼設離散信源霍夫曼編碼也是一種采用異前置碼的m進制編碼方法。不失一般性，設p(x1)>p(x2)>…>p(xn)，且霍夫曼編碼的編碼效率高于香農(nóng)編碼。49①將符號元按概率進行降序排列；②為概率最小的符號元分配一個碼元1，概率次小的符號元分配一個碼元0；③將概率最小的兩個符號元合并成一個新的符號元，用兩者概率之和作為該新符號元的概率；重復以上三個步驟，直到最后合并出一個以1為概率的符號元，結束編碼。四、霍夫曼(Huffman)編碼--編碼步驟50例1，對單符號離散信源編二進制霍夫曼碼，并計算其編碼效率。解：①將符號元按概率進行降序排列符號元概率x10.5x2x3x40.30.150.05四、霍夫曼(Huffman)編碼5110②為概率最小的符號元分配一個碼元1，概率次小的符號元分配一個碼元0；符號元概率x10.5x2x3x40.30.150.05③將概率最小的兩個符號元合并成一個新的符號元，用兩者概率之和作為該新符號元的概率；0.2x′3四、霍夫曼(Huffman)編碼52重復以上三個步驟，直到最后合并出一個以1為概率的符號元，結束編碼。符號元概率x10.5x2x′30.30.2100.5x′2符號元概率x10.5x′20.5101x′1四、霍夫曼(Huffman)編碼53碼字碼長符號元概率x10.5x2x3x40.30.150.050.20.511110000101101111233顯然，所編霍夫曼碼構成二元碼樹，為異前置碼。四、霍夫曼(Huffman)編碼—整個過程54四、霍夫曼(Huffman)編碼55例2，分別對下列單符號離散信源和該信源的二次擴展信源編二進制霍夫曼碼，并計算其編碼效率。解：⑴對單符號離散信源編碼符號元概率x10.6x2x30.30.10.410110碼字碼長01011122四、霍夫曼(Huffman)編碼56四、霍夫曼(Huffman)編碼57⑵對二次擴展信源編碼將符號元ai按概率進行降序排列霍夫曼編碼過程為四、霍夫曼(Huffman)編碼580.040.071111000符號元概率a10.36a2a3a40.180.180.09a50.06a6a70.060.03a80.03a90.010.12010.160.3610100.28100.6410四、霍夫曼(Huffman)編碼590.040.071111000符號元概率a10.36a2a3a40.180.180.09a50.06a6a70.060.03a80.03a90.010.12010.160.3610100.28100.6410碼字碼長100001000101010010111010110110134634546010100四、霍夫曼(Huffman)編碼60四