信息論與編碼課件第5章-2

信源編碼

第5章15.2無失真信源編碼25.2.3最佳變長編碼1、最佳碼定義：對于某一信源和某一碼符號集來說,若有可分離的變長碼，且其平均碼長最短。2、最佳碼分類香農（Shannon）費諾（Fano）哈夫曼（Huffma）3

香農編碼香農第一定理指出,選擇每個碼字的長度Ki滿足下式：或:－log2

p(xi)≤Ki

<1－log2

p(xi)就可以得到最佳碼。這種編碼方法稱為香農編碼

取整4二進制香農碼的編碼步驟如下：⑴將信源符號按概率從大到小的順序排列,

p(a1)≥p(a2)≥…≥p(an)⑵確定滿足下列不等式的整數(shù)Ki,－log2

p(ai)≤Ki

<1－log2

p(ai)⑶令P1=0,用Pi表示第i個碼字的累加概率，⑷將Pi用二進制表示,并取小數(shù)點后Ki位作為符號ai的編碼。香農編碼5例1有一單符號離散無記憶信源對該信源編二進制香農碼。其編碼過程如表所示以i=3為例:碼字長度：K4=[－log0.2]=3累加概率

Pi=0.70→0.10110…00011011110011101信源符號xi

符號概率p(xi)累加概率Pi-logp(xi)碼長碼字x10.401.32200x20.30.41.73201x30.20.72.323101x40.050.94.3

511100x50.050.954.35111016香農碼的平均碼長熵編碼效率為提高編碼效率,首先應達到滿樹;如把x4x5換成前面的節(jié)點,可減小平均碼長。不應先規(guī)定碼長,而是由碼樹來規(guī)定碼字,可得更好的結果。x1x2x5x3x47費諾編碼費諾編碼屬于概率匹配編碼

。編碼步驟如下：（1）將概率按從大到小的順序排列,令p(x1)≥p(x2)≥…≥p(xn)（2）按編碼進制數(shù)將概率分組,使每組概率盡可能接近或相等。如編二進制碼就分成兩組,編m進制碼就分成m組。（3）給每一組分配一位碼元。（4）將每一分組再按同樣原則劃分,重復步驟2和3,直至概率不再可分為止。8信源符號xi

符號概率p(xi)第1次分組第2次分組第3次分組碼字碼長x10.400002x40.05100103x50.0510113x20.310102x30.21112例設有一單符號離散信源對該信源編二進制費諾碼。信源符號xi

符號概率p(xi)第1分組第2分組第3分組第4分組碼字碼長x10.4001x20.310102x30.2101103x40.051011104x50.05111114平均碼長：K=2.1編碼效率:η=93%平均碼長：K=2.0編碼效率:η=97.5%9平均碼長編碼效率費諾碼比較適合于每次分組概率都很接近的信源特別是對每次分組概率都相等的信源進行編碼時,可達到理想的編碼效率。10例有一單符號離散無記憶信源對該信源編二進制費諾碼,編碼過程如表:11信源熵為H(X)=2.75(比特/符號)平均碼長為編碼效率為η=1之所以如此,因為每次所分兩組的概率恰好相等。12哈夫曼編碼哈夫曼編碼也是用碼樹來分配各符號的碼字。費諾碼是從樹根開始,把各節(jié)點分給某子集,若子集已是單點集,它就是一片樹葉而作為碼字。哈夫曼編碼是先給每一符號一片樹葉,逐步合并成節(jié)點直到樹根。哈夫曼(Huffman)編碼是一種效率比較高的變長無失真信源編碼方法。13哈夫曼編碼的步驟如下：⑴將信源消息符號按其出現(xiàn)的概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)⑵取兩個概率最小的字母分別配以0和1兩碼元,并將這兩個概率相加作為一個新字母的概率,與未分配的二進符號的字母重新排隊。⑶對重排后的兩個概率最小符號重復步驟⑵的過程。⑷不斷繼續(xù)上述過程,直到最后兩個符號配以0和1為止。⑸從最后一級開始,向前返回得到各個信源符號所對應的碼元序列,即相應的碼字。14例5-7

設單符號離散無記憶信源如下,要求對信源編二進制哈夫曼碼。編碼過程如下表信源符號xi

符號概率p(xi)編碼過程x10.20x20.19x30.18x40.17x50.15x60.10x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901碼字101100000101001100111在圖中讀取碼字的時候,要從后向前讀,此時編出來的碼字是可分離的異前置碼。15熵平均碼長為編碼效率16哈夫曼的編法并不惟一。每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。不同的碼元分配,得到的具體碼字不同,但碼長Ki不變,平均碼長也不變,所以沒有本質區(qū)別；縮減信源時,若合并后的新符號概率與其他符號概率相等,從編碼方法上來說,這幾個符號的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。不同的編法得到的碼字長度Ki也不盡相同。哈夫曼編碼17例5-8單符號離散無記憶信源信源符號xi

符號概率p(xi)編碼過程x10.4x20.2x30.2x40.1x50.1010.40.20.20.2010.40.40.2010.60.401碼字10100000100011碼字00101101001118

19單符號信源編二進制哈夫曼碼,編碼效率主要決定于信源熵和平均碼長之比。對相同的信源編碼,其熵是一樣的,采用不同的編法,得到的平均碼長可能不同。平均碼長越短,編碼效率就越高。編法一的平均碼長為編法二的平均碼長為兩種編法的平均碼長相同,所以編碼效率相同。20討論：哪種方法更好？定義碼字長度的方差σ2：第二種編碼方法的碼長方差要小許多。第二種編碼方法的碼長變化較小,比較接近于平均碼長。哈夫曼編碼21哈夫曼編碼第一種方法編出的5個碼字有4種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長；第二種編碼方法更簡單、更容易實現(xiàn),所以更好。結論：在哈夫曼編碼過程中,對縮減信源符號按概率由大到小的順序重新排列時,應使合并后的新符號盡可能排在靠前的位置,這樣可使合并后的新符號重復編碼次數(shù)減少,使短碼得到充分利用。22m進制哈夫曼編碼在編m進制哈夫曼碼時為了使平均碼長最短,必須使最后一步縮減信源有m個信源符號。對于m進制編碼,若所有碼字構成全樹,可分離的碼字數(shù)必為:

m＋k(m－l)非全樹時,有s個碼字不用：第一次對最小概率符號分配碼元時只取(m－s)個,分別配以0,1,…,m-s-1,把這些符號的概率相加作為一個新符號的概率,與其它符號一起重新排列以后每次取m個符號,分別配以0,1,…,m-1；如此下去,直至所有概率相加得1為止,即得到各符號的m進制碼字。23例:對如下單符號離散無記憶信源編三進制哈夫曼碼這里：m=3，n=8令k=3，m+k(m－1)=9，則s=9－n=9－8=1所以第一次取m－s=2個符號進行編碼。243進制哈夫曼編碼信源符號xi

符號概率p(xi)編碼過程x10.40x20.18x30.10x40.10x50.07x60.06x70.05x80.04010120.400.180.100.100.090.070.060.400.220.180.100.100120.400.380.22012碼字010111221222002012526平均碼長為信息率為編碼效率為哈夫曼的編碼效率相當高,對編碼器的要求也簡單得多。27

結論香農碼、費諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特性,使經常出現(xiàn)的信源符號對應較短的碼字,使信源的平均碼長縮短,從而實現(xiàn)了對信源的壓縮；香農碼有系統(tǒng)的、