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

信息論導(dǎo)論-第3章_2013第一頁，共66頁。復(fù)習(xí)

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