信息論導(dǎo)論-第3章-2013

第3章離散信源無失真編碼趙宏志2013年3月《信息論導(dǎo)論》2復(fù)習(xí)

信息熵的含義離散平穩(wěn)無記憶信源馬爾可夫信源3信源發(fā)出的消息需要傳輸或存儲才能發(fā)揮作用，而對于傳輸或存儲來說，現(xiàn)在二進(jìn)制信號最具優(yōu)勢。信息傳輸?shù)?個(gè)關(guān)鍵要求：效率、可靠、安全第3章離散信源無失真編碼為了滿足信道特性，往往需要將n元的信源符號序列變換為m元(現(xiàn)在一般為二元)的信源碼序列，這一過程就是信源編碼。4②怎樣有效地利用碼字的每一個(gè)比特去攜帶信息，即在編碼過程中怎樣用最少的比特?cái)?shù)去表示信源的信息熵？①怎樣保證編碼和譯碼過程不丟失信息，即怎樣實(shí)現(xiàn)無失真編碼？③無失真編碼的具體方法？第3章離散信源無失真編碼信源編碼的3個(gè)問題是：5第3章的主要內(nèi)容與課時(shí)一、無失真編碼的基本思路二、無失真編碼定理三、香農(nóng)編碼四、霍夫曼編碼6一、無失真編碼的基本思路先看一個(gè)單符號離散信源無失真編碼的例子：其信息熵7無失真編碼的含義：保證符號元與碼字一一對應(yīng)，此時(shí)用碼序列表示的信源信息熵保持不變。最簡單的無失真編碼：4-2進(jìn)制變換，即該編碼的碼長K=2，碼字的每一個(gè)比特?cái)y帶信息的效率即編碼效率一、無失真編碼的基本思路思考：效率可以再提高嗎？8為了壓縮比特?cái)?shù)，可以考慮對信源符號進(jìn)行不等長編碼，如碼字的比特?cái)?shù)中約有17.6%未攜帶信息，屬于冗余比特，傳輸效率不高。但該編碼不能實(shí)現(xiàn)無失真譯碼，即不能保證符號元與碼字的一一對應(yīng)。一、無失真編碼的基本思路可以無失真譯碼嗎？9其平均碼長一種能保證符號元與碼字一一對應(yīng)的不等長編碼為編碼效率與第一種編碼相比，碼字壓縮了0.3個(gè)比特，編碼效率提高了14.5%。一、無失真編碼的基本思路10進(jìn)一步，如果對該信源的二次擴(kuò)展信源進(jìn)行無失真編碼，一種能保證符號序列元與碼字一一對應(yīng)的不等長編碼為一、無失真編碼的基本思路11其平均碼長編碼效率一、無失真編碼的基本思路12與第二種編碼相比，碼字又壓縮了約0.04個(gè)比特，編碼效率提高了2.1%。總結(jié)該例子，有以下幾點(diǎn)結(jié)論與問題：①一般采用不等長編碼，使平均碼長接近信息熵，從而在無失真前提下提高編碼效率；編碼的基本原則是大概率符號元編成短碼，小概率符號元編成長碼。一、無失真編碼的基本思路13②由于碼長不等，如何保證接收端從碼序列中唯一地分割出對應(yīng)與每一個(gè)符號元的碼字，以實(shí)現(xiàn)無失真譯碼？③對符號序列進(jìn)行組(block)編碼有助于使平均碼長接近信息熵，但平均碼長能否無限接近信息熵，從而使編碼效率趨近1？如果能，對序列長度有什么要求？一、無失真編碼的基本思路引發(fā)的問題14第3章的主要內(nèi)容與課時(shí)一、無失真編碼的基本思路二、無失真編碼定理三、香農(nóng)編碼四、霍夫曼編碼15二、無失真編碼定理1、異前置碼如果所采用的不等長編碼使接收端能從碼序列中唯一地分割出對應(yīng)與每一個(gè)符號元的碼字，則稱該不等長編碼為單義可譯碼。單義可譯碼中，如果能在對應(yīng)于每一個(gè)符號元的碼字結(jié)束時(shí)立即譯出的稱為即時(shí)碼，如果要等到對應(yīng)與下一個(gè)符號元的碼字才能譯出的稱為延時(shí)碼。16碼A--不是單義可譯碼，它有二義性碼B和碼C才是單義可譯碼；碼B是延時(shí)碼，它需等到對應(yīng)與下一個(gè)符號元的碼字開頭0才能確定本碼字的結(jié)束，存在譯碼延時(shí)，只有碼C才是即時(shí)碼。二、無失真編碼定理17從樹根開始到每一個(gè)終節(jié)點(diǎn)的聯(lián)枝代表一個(gè)碼字，故相應(yīng)的異前置碼碼C的特點(diǎn)是：任何一個(gè)碼字都不是其他碼字的前綴，因此將該碼稱為異前置碼。異前置碼可以用樹圖來構(gòu)造：一個(gè)三元碼樹圖二、無失真編碼定理18碼C所對應(yīng)的二元碼樹圖m元長度為ki,i=1,2,…,n的異前置碼存在的充分必要條件是：該充要條件稱為克拉夫特(Kraft)不等式。二、無失真編碼定理19設(shè)m元異前置碼第i個(gè)碼字的長度為ki,i=1,2,…,n考慮一個(gè)N級滿樹，在第N級共有mN個(gè)節(jié)點(diǎn)，在第ki級共有mki個(gè)節(jié)點(diǎn)。根據(jù)異前置碼的定義，第i個(gè)碼字后的節(jié)點(diǎn)不能再用，故第N級不能用的節(jié)點(diǎn)數(shù)為mN-ki構(gòu)造異前置碼的碼樹圖第N級上總共不能用的節(jié)點(diǎn)總數(shù)二、無失真編碼定理20【無失真編碼定理】如果N維離散平穩(wěn)信源的平均符號熵為HN(X1X2…XN)，對信源符號序列進(jìn)行m元不等長組編碼，一定存在一種無失真編碼方法，當(dāng)N足夠大時(shí)，使得每個(gè)信源符號所對應(yīng)碼字的平均比特?cái)?shù)式中，ε為任意給定的小正數(shù)。二、無失真編碼定理21Kraft不等式設(shè)不等長組編碼對應(yīng)于符號元ai=xi1xi2…xiN的碼字長度為ki說明該編碼是異前置碼【無失真編碼定理】的證明22其平均碼長【無失真編碼定理】的證明23無失真編碼定理又叫香農(nóng)第一定理，該定理從理論上闡明了編碼效率的理想無失真編碼的存在性.【無失真編碼定理】的證明24無失真編碼的代價(jià)是取無限長的符號序列進(jìn)行組編碼，即只有N→∞時(shí)可見，極限熵H∞是一個(gè)界限，通常也稱為(信源編碼的)香農(nóng)界。二、無失真編碼定理25剛才討論了一般的離散平穩(wěn)信源，對其他已學(xué)過的離散信源，根據(jù)無失真編碼定理可得出什么結(jié)論呢？N維離散平穩(wěn)無記憶信源m階馬爾科夫信源二、無失真編碼定理26N維離散平穩(wěn)無記憶信源由于其平均符號熵HN(X1X2…XN)=H(X)式中，ε為任意給定的小正數(shù)。此時(shí)香農(nóng)界為H(X)。二、無失真編碼定理故對信源符號序列進(jìn)行m元不等長組編碼，一定存在一種無失真編碼方法，當(dāng)N足夠大時(shí)，使得每個(gè)信源符號所對應(yīng)碼字的平均比特?cái)?shù)27m階馬爾科夫信源(m<N),N足夠大時(shí)，平均符號熵HN(X1X2…XN)=Hm+1式中，ε為任意給定的小正數(shù)。此時(shí)香農(nóng)界為Hm+1。二、無失真編碼定理對信源符號序列進(jìn)行m元不等長組編碼，一定存在一種無失真編碼方法，使得每個(gè)信源符號對應(yīng)碼字的平均比特?cái)?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)信源進(jìn)行無失真編碼，每個(gè)信源符號所對應(yīng)碼字的平均比特?cái)?shù)平穩(wěn)無記憶信源最多，m階馬爾科夫信源次之，一般平穩(wěn)信源最少。二、無失真編碼定理29一、無失真編碼的基本思路二、無失真編碼定理三、香農(nóng)編碼四、霍夫曼編碼第3章的主要內(nèi)容與課時(shí)30三、香農(nóng)編碼設(shè)離散信源香農(nóng)編碼是一種采用異前置碼的m進(jìn)制編碼方法。不失一般性，設(shè)p(x1)>p(x2)>…>p(xn)，且31①將符號元xi按概率進(jìn)行降序排列；②令p(x0)=0，計(jì)算第i個(gè)碼字的累加概率③確定第i個(gè)碼字的碼長ki，ki為滿足下列不等式的最小整數(shù)：④將pa(xi)用二進(jìn)制表示，取小數(shù)點(diǎn)后ki位作為符號元xi的碼字。三、香農(nóng)編碼—編碼步驟32例1，對單符號離散信源編二進(jìn)制香農(nóng)碼，并計(jì)算其編碼效率。解：①將xi按概率進(jìn)行降序排列xip(xi)pa(xi)ki碼字x10.5x20.3x30.15x40.05三、香農(nóng)編碼—舉例33②令p(x0)=0，計(jì)算第i個(gè)碼字的累加概率pa(x1)=0pa(x2)=0+0.5=0.5pa(x3)=0.5+0.3=0.8pa(x4)=0.8+0.15=0.95③確定第i個(gè)碼字的碼長ki：三、香農(nóng)編碼34④將pa(xi)用二進(jìn)制表示，取小數(shù)點(diǎn)后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，分別對下列單符號離散信源和該信源的二次擴(kuò)展信源編二進(jìn)制香農(nóng)碼，并計(jì)算其編碼效率。解：⑴對單符號離散信源編碼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⑵對二次擴(kuò)展信源編碼將符號元ai按概率進(jìn)行降序排列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è)于俄亥俄州立大學(xué)電子工程系，畢業(yè)后服役于美國海軍，大黃蜂號航母，兵種：廚師。1949年獲得俄亥俄州立大學(xué)電子工程系碩士學(xué)位；1953年獲MIT電子工程系博士學(xué)位。1953年博士畢業(yè)后留校任教；1967年起任教于加州大學(xué)圣克魯茲分校，直至1994年退休?；舴蚵簧浜芏?，主要貢獻(xiàn)有信息論、編碼、雷達(dá)信號設(shè)計(jì)、邏輯電路設(shè)計(jì)。他最著名的霍夫曼編碼來自于碩士期間的某門課程的期末考試報(bào)告?；舴蚵鼜奈礊樗某删蜕暾垖＠?，座右銘“Myproductsaremystudents”48四、霍夫曼(Huffman)編碼設(shè)離散信源霍夫曼編碼也是一種采用異前置碼的m進(jìn)制編碼方法。不失一般性，設(shè)p(x1)>p(x2)>…>p(xn)，且霍夫曼編碼的編碼效率高于香農(nóng)編碼。49①將符號元按概率進(jìn)行降序排列；②為概率最小的符號元分配一個(gè)碼元1，概率次小的符號元分配一個(gè)碼元0；③將概率最小的兩個(gè)符號元合并成一個(gè)新的符號元，用兩者概率之和作為該新符號元的概率；重復(fù)以上三個(gè)步驟，直到最后合并出一個(gè)以1為概率的符號元，結(jié)束編碼。四、霍夫曼(Huffman)編碼--編碼步驟50例1，對單符號離散信源編二進(jìn)制霍夫曼碼，并計(jì)算其編碼效率。解：①將符號元按概率進(jìn)行降序排列符號元概率x10.5x2x3x40.30.150.05四、霍夫曼(Huffman)編碼5110②為概率最小的符號元分配一個(gè)碼元1，概率次小的符號元分配一個(gè)碼元0；符號元概率x10.5x2x3x40.30.150.05③將概率最小的兩個(gè)符號元合并成一個(gè)新的符號元，用兩者概率之和作為該新符號元的概率；0.2x′3四、霍夫曼(Huffman)編碼52重復(fù)以上三個(gè)步驟，直到最后合并出一個(gè)以1為概率的符號元，結(jié)束編碼。符號元概率x10.5x2x′30.30.2100.5x′2符號元概率x10.5x′20.5101x′1四、霍夫曼(Huffman)編碼53碼字碼長符號元概率x10.5x2x3x40.30.150.050.20.511110000101101111233顯然，所編霍夫曼碼構(gòu)成二元碼樹，為異前置碼。四、霍夫曼(Huffman)編碼—整個(gè)過程54四、霍夫曼(Huffman)編碼55例2，分別對下列單符號離散信源和該信源的二次擴(kuò)展信源編二進(jìn)制霍夫曼碼，并計(jì)算其編碼效率。解：⑴對單符號離散信源編碼符號元概率x10.6x2x30.30.10.410110碼字碼長01011122四、霍夫曼(Huffman)編碼56四、霍夫曼(Huffman)編碼57⑵對二次擴(kuò)展信源編碼將符號元ai按概率進(jìn)行降序排列霍夫曼編碼過程為四、霍夫曼(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四