第3章 離散信源無失真編碼

2012年3月31日星期六信息論導(dǎo)論通信與信息工程學(xué)院楊海芬第3章離散信源無失真編碼理解無失真信源編碼定理；了解異前置碼的特點、樹圖表示和克拉夫特不等式，掌握二進(jìn)制香農(nóng)碼、費諾碼的編碼步驟，編碼效率計算；掌握二進(jìn)制霍夫曼碼的編碼步驟，編碼效率計算。從數(shù)學(xué)意義上，信源編碼就是信源符號序列到碼序列(數(shù)字序列)之間的映射。在應(yīng)用中，如果只關(guān)心信道的輸入而不追究其初始消息和編碼過程，可以將信源與信源編碼合在一起稱為等效信源。衡量編碼方法優(yōu)劣的主要指標(biāo)中，碼長和易實現(xiàn)性最受重視。

通信的實質(zhì)是傳輸信息，要求傳輸?shù)挠行院秃涂煽啃浴Ｓ行浴诓皇д婊蛟试S失真的條件下，用盡可能少的符號傳送信源信息。信源編碼分為無失真和限失真。（1）無失真編碼，又名冗余度壓縮編碼：僅對信源的冗余度進(jìn)行壓縮，不改變信源的熵；（2）限失真編碼，又名熵壓縮編碼：在失真受限的情況下進(jìn)行限失真編碼。信源編碼的分類信源編碼的基礎(chǔ)是信息論中的兩個編碼定理：無失真編碼定理限失真編碼定理

無失真編碼是可逆的，即當(dāng)信源符號變換成代碼以后，可以從代碼無失真地恢復(fù)出原信源符號。只適用于離散；在連續(xù)信源的情況下，由于信源的信息量趨于無限，顯然不能用離散符號序列Y來完成無失真編碼，而只能進(jìn)行限失真編碼。一般稱無失真信源編碼定理為第一極限定理；信道編碼定理（離散和連續(xù)信道）稱為第二極限定理；限失真信源編碼定理稱為第三極限定理。信源編碼的基本途徑有兩個：使序列中的各個符號盡可能地互相獨立，即解除相關(guān)性，去冗余；使編碼中各個符號出現(xiàn)的概率盡可能地相等，即概率均勻化。本章討論離散信源編碼，首先從無失真編碼定理出發(fā)，重點討論以香農(nóng)碼、費諾碼和哈夫曼碼為代表的最佳無失真碼。一、無失真信源編碼定理對于N維平穩(wěn)無記憶信源，熵率為H(X)，如果對信源進(jìn)行二元編碼，設(shè)K為碼長，對任意給定的ε>0，只要碼率則當(dāng)N足夠大時，該編碼為無失真編碼；如果碼率則無論N多大，該編碼也一定出錯。無失真信源編碼定理也叫香農(nóng)第一定理，該定理表明了無失真編碼的存在性，并明確了熵率H(X)是無失真編碼碼率的下界，通常將其稱為香農(nóng)界。根據(jù)香農(nóng)第一定理，無失真編碼的碼長定義無失真編碼的編碼效率從提高傳輸效率的角度出發(fā)，希望碼長越接近聯(lián)合熵越好。二、異前置碼與最優(yōu)碼碼長的界一個單符號離散信源無失真編碼的例子：信源的熵一種無失真等長編碼是對信源符號進(jìn)行4-2進(jìn)制變換該編碼的碼長K=2(bit/symbol)，其編碼效率為提高編碼效率，考慮將整數(shù)比特的碼長壓縮為小數(shù)比特的平均碼長，對信源符號進(jìn)行不等長編碼。一種無失真不等長編碼該編碼的平均碼長其編碼效率該信源的二次擴展信源的一種無失真不等長編碼該編碼的平均碼長其編碼效率不等長編碼的結(jié)論與問題：不等長編碼的基本原則是大概率符號序列編為短碼，小概率符號序列編為長碼不等長編碼可將整數(shù)比特碼長壓縮為小數(shù)比特平均碼長以接近聯(lián)合熵，在無失真前提下提高編碼效率。由于碼長不等，如何保證接收端從碼串中唯一地分割出對應(yīng)與每一個符號序列的碼字，實現(xiàn)無失真譯碼？1、異前置碼如果所采用的不等長編碼使接收端能從碼串中唯一地分割出對應(yīng)與每一個符號序列的碼字，則稱該不等長編碼為單義可譯碼。單義可譯碼中，如果能在對應(yīng)與每一個符號序列的碼字結(jié)束時立即譯出的稱為即時碼，如果要等到對應(yīng)與下一個符號序列的碼字出現(xiàn)時才能譯出的稱為延時碼。碼A不是單義可譯碼，它有二義性；碼B和碼C是單義可譯碼；碼B是延時碼，它需等到對應(yīng)與下一個符號的碼字開頭0才能確定本碼字的結(jié)束，存在譯碼延時；碼C是即時碼。碼C的特點——任何一個碼字都不是其它碼字的前綴，因此將該碼稱為異前置碼。異前置碼可以用樹圖來構(gòu)造。一個三元碼樹圖從樹根開始到每一個終節(jié)點的聯(lián)枝代表一個碼字，相應(yīng)的異前置碼012012012012碼C所對應(yīng)的二元碼樹圖010101即時碼是一種實時的唯一可譯碼，這類碼無需另加同步信息，就能在接收端被分離出來。在信源編碼和數(shù)據(jù)壓縮中，這類編碼無論在理論還是在實際中都有很大意義，對較簡單的信源，可以很方便地用碼樹法直接且直觀地構(gòu)造出可以分離碼（異前置碼）。但是當(dāng)信源較復(fù)雜，直接畫碼樹就比較復(fù)雜。則如何判定異前置碼？長度為ki

i=1,2,…,n的二元異前置碼存在的充分必要條件該充要條件稱為克拉夫特(Kraft)不等式2、Kraft不等式設(shè)二元異前置碼第i個碼字的長度為ki

i=1,2,…,n考慮一個N級滿樹，在第N級共有2N個節(jié)點，在第ki(<N)級共有2ki個節(jié)點。根據(jù)異前置碼的定義，第i個碼字后的節(jié)點不能再用，故不能用的第N級節(jié)點數(shù)為2N-ki。構(gòu)造異前置碼的碼樹圖上總共不用的第N級節(jié)點總數(shù)香農(nóng)碼直接基于最優(yōu)碼碼長的界，是一種采用異前置碼實現(xiàn)的無失真不等長編碼。三、無失真信源編碼香農(nóng)碼的編碼步驟：①將符號序列按概率降序排列②確定第i個碼字的碼長ki1、香農(nóng)碼③令P(a0)=0，計算第i-1個符號序列的累加概率④將Pa(ai)用二進(jìn)制表示，取小數(shù)點后ki位作為符號序列ai的碼字ci編香農(nóng)碼，并計算編碼效率。①將符號xi按概率降序排列例1②確定第i個碼字的碼長kixiP(xi)kiPa(xi)cix10.51x20.32x30.153x40.055③令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.95xiP(xi)kiPa(xi)cix10.510x20.320.5x30.1530.8x40.0550.95④將Pa(xi)用二進(jìn)制表示，取小數(shù)點后ki位作為xi的碼字ciPa(x1)=0.0=(0.0)2→c1=0Pa(x2)=0.5=(0.10)2→c2=10Pa(x3)=0.8=(0.110…)2→c3=110Pa(x4)=0.95=(0.11110…)2→c4=11110xiP(xi)kiPa(xi)cix10.5100x20.320.510x30.1530.8110x40.0550.9511110分別對該信源和其二次擴展信源編香農(nóng)碼，并計算編碼效率。(1)對信源編碼例2Pa(x1)=0.0=(0.0)2→c1=0Pa(x2)=0.5=(0.10)2→c2=10Pa(x3)=0.8=(0.110…)2→c3=110Pa(x1)=0Pa(x2)=0+0.5=0.5Pa(x3)=0.5+0.3=0.8xiP(xi)kiPa(xi)cix10.5100x20.320.510x30.230.8110(2)對二次擴展信源編碼將符號序列ai按概率降序排列Pa(a1)=0Pa(a2)=0+0.25=0.25Pa(a3)=0.25+0.15=0.4Pa(a4)=0.4+0.15=0.55Pa(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.96Pa(a1)=0.0=(0.00)2→c1=00Pa(a2)=0.25=(0.010)2→c2=010Pa(a3)=0.4=(0.011…)2→c3=011Pa(a4)=0.55=(0.1000…)2→c4=1000Pa(a5)=0.65=(0.1010…)2→c5=1010Pa(a6)=0.75=(0.1100)2→c6=1100Pa(a7)=0.84=(0.11010…)2→c7=11010Pa(a8)=0.9=(0.11100…)2→c8=11100Pa(a9)=0.96=(0.11101…)2→c9=11101aiP(ai)kiPa(ai)cia10.252000a20.1530.25010a30.1530.4011a40.140.551000a50.140.651010a60.0940.751100a70.0650.8411010a80.0650.911100a90.0450.9611101香農(nóng)碼的特點編碼過程中先確定碼長，后確定碼字，保證大概率符號序列編為短碼，小概率符號序列編為長碼第一個符號序列的累加概率為0，其對應(yīng)的碼字總是0、00、…形式具有唯一性平均碼長不超過聯(lián)合熵一個比特，N越大平均碼長越接近聯(lián)合熵費諾碼基于概率匹配的思想，也是采用異前置碼實現(xiàn)的無失真不等長編碼。①將符號序列ai按概率降序排列②進(jìn)行分組，使每組概率盡可能相等③給每個分組分配一個二進(jìn)制碼元0和1對每個分組重復(fù)②③步驟，直到不可分為止費諾碼的編碼步驟：2、費諾碼編費諾碼，并計算編碼效率。xiP(xi)分組1分組2分組3cix10.5x20.3x30.15x40.05例1xiP(xi)分組1分組2分組3cix10.50x20.31x30.15x40.05第一次分組：第二次分組：xiP(xi)分組1分組2分組3cix10.50x20.310x30.151x40.05第三次分組：xiP(xi)分組1分組2分組3cix10.500x20.31010x30.1510110x40.051111例2分別對信源和其二次擴展信源編費諾碼，并計算編碼效率。(1)對單符號離散信源編碼第一次分組：第二次分組：xiP(xi)分組1分組2cix10.500x20.41010x30.1111(2)對二次擴展信源編碼將符號序列ai按概率降序排列第二次分組：第一次分組：第三次分組：第四次分組：第五次分組：第六次分組：aiP(ai)分組1分組2分組3分組4分組5分組6cia10.250000a20.2101a30.21010a40.1610110a50.0510011100a60.05111101a70.041011110a80.0410111110a90.011111111費諾碼的特點編碼過程中先確定碼字，后確定碼長大概率符號序列分解次數(shù)少，編為短碼，小概率符號序列分解次數(shù)多，編為長碼具有唯一性平均碼長不超過聯(lián)合熵一個比特，N越大平均碼長越接近聯(lián)合熵3、赫夫曼碼赫夫曼碼也是采用異前置碼實現(xiàn)的無失真不等長編碼，通常赫夫曼碼的編碼效率高于香農(nóng)碼。赫夫曼碼的編碼步驟：①將符號序列ai按概率降序排列②為概率最小的符號序列分配一個二進(jìn)制碼元1(或0)，概率次小的符號序列分配一個二進(jìn)制碼元0(或1)③將概率最小的兩個符號序列合并成一個新的符號序列，用兩者概率之和作為新符號序列的概率重復(fù)①②③步驟，直到合并出一個以1為概率的新符號序列，結(jié)束編碼編赫夫曼碼，并計算編碼效率。①將符號xi按概率降序排列例110②為概率最小的符號分配一個二進(jìn)制碼元1，概率次小的符號分配一個二進(jìn)制碼元0③將概率最小的兩個符號合并成一個新的符號，用兩者概率之和作為新符號的概率0.2x3，xiP(xi)x10.5x2x3x40.30.150.05重復(fù)①②③步驟，直到合并出一個以1為概率的新符號，結(jié)束編碼xiP(xi)x10.5x2x3，0.30.2100.5x2，xiP(xi)x10.5x2，0.5101x1，cikixiP(xi)x10.5x2x3x40.30.150.050.20.511110000101101111233整個編碼過程集中在一起例2分別對信源和其二次擴展信源編赫夫曼碼，并計算編碼效率。(1)對信源編碼xiP(xi)x10.5x2x30.40.10.510110ciki01011122(2)對二次擴展信源編碼將符號序列ai按概率降序排列aiP(ai)a10.25a2a3a40.20.20.16a50.05a6a70.050.04a80.04a90.010.050.091000110.1100.190.410010.35100.6101223625556011000100010