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

信源編碼

第5章15.2無(wú)失真信源編碼25.2.3最佳變長(zhǎng)編碼1、最佳碼定義：對(duì)于某一信源和某一碼符號(hào)集來(lái)說(shuō),若有可分離的變長(zhǎng)碼，且其平均碼長(zhǎng)最短。2、最佳碼分類(lèi)香農(nóng)（Shannon）費(fèi)諾（Fano）哈夫曼（Huffma）3

香農(nóng)編碼香農(nóng)第一定理指出,選擇每個(gè)碼字的長(zhǎng)度Ki滿(mǎn)足下式：或:－log2

p(xi)≤Ki

<1－log2

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

取整4二進(jìn)制香農(nóng)碼的編碼步驟如下：⑴將信源符號(hào)按概率從大到小的順序排列,

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

p(ai)≤Ki

<1－log2

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

Pi=0.70→0.10110…00011011110011101信源符號(hào)xi

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

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

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

符號(hào)概率p(xi)第1次分組第2次分組第3次分組碼字碼長(zhǎng)x10.400002x40.05100103x50.0510113x20.310102x30.21112例設(shè)有一單符號(hào)離散信源對(duì)該信源編二進(jìn)制費(fèi)諾碼。信源符號(hào)xi

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

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

設(shè)單符號(hào)離散無(wú)記憶信源如下,要求對(duì)信源編二進(jìn)制哈夫曼碼。編碼過(guò)程如下表信源符號(hào)xi

符號(hào)概率p(xi)編碼過(guò)程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在圖中讀取碼字的時(shí)候,要從后向前讀,此時(shí)編出來(lái)的碼字是可分離的異前置碼。15熵平均碼長(zhǎng)為編碼效率16哈夫曼的編法并不惟一。每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。不同的碼元分配,得到的具體碼字不同,但碼長(zhǎng)Ki不變,平均碼長(zhǎng)也不變,所以沒(méi)有本質(zhì)區(qū)別；縮減信源時(shí),若合并后的新符號(hào)概率與其他符號(hào)概率相等,從編碼方法上來(lái)說(shuō),這幾個(gè)符號(hào)的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度Ki也不盡相同。哈夫曼編碼17例5-8單符號(hào)離散無(wú)記憶信源信源符號(hào)xi

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

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

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

符號(hào)概率p(xi)編碼過(guò)程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平均碼長(zhǎng)為信息率為編碼效率為哈夫曼的編碼效率相當(dāng)高,對(duì)編碼器的要求也簡(jiǎn)單得多。27

結(jié)論香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源的統(tǒng)計(jì)特性,使經(jīng)常出現(xiàn)的信源符號(hào)對(duì)應(yīng)較短的碼字,使信源的平均碼長(zhǎng)縮短,從而實(shí)現(xiàn)了對(duì)信源的壓縮；香農(nóng)碼有系統(tǒng)的、