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

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

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