信息論編碼教材

信源編碼

第5章25.1

編碼的定義5.2

無失真信源編碼5.3限失真信源編碼5.4常用信源編碼方法簡(jiǎn)介內(nèi)容35.2無失真信源編碼45.2.3最佳變長(zhǎng)編碼最佳碼(緊致碼)：對(duì)于某一信源和某一碼符號(hào)集來說,若有一唯一可譯碼,其平均碼長(zhǎng)小于所有其他唯一可譯碼的平均長(zhǎng)度。緊致碼香農(nóng)（Shannon）費(fèi)諾（Fano）哈夫曼（Huffman）

——均為匹配編碼（統(tǒng)計(jì)編碼），都是通過使用較短的碼字來給出現(xiàn)概率較高的信源符號(hào)編碼，而出現(xiàn)概率較小的信源符號(hào)用較長(zhǎng)的碼字來編碼，從而使得平均碼長(zhǎng)最短，達(dá)到最佳編碼的目的。5香農(nóng)編碼無失真信源編碼定理(香農(nóng)第一定理)給出了平均碼長(zhǎng)和信源之間的關(guān)系，并指出可通過編碼使平均碼長(zhǎng)達(dá)到極限值。根據(jù)定理，先決定碼長(zhǎng)，再用合適的方法構(gòu)造碼字，這就是香農(nóng)編碼。香農(nóng)碼選擇每個(gè)碼字的長(zhǎng)度Ki滿足下式：－log2

p(xi)≤Ki

<1－log2

p(xi)取整或:

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

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

－log2

p(ai)≤Ki

<1－log2

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

(0.7)10=(0.10110…)21011110011101信源符號(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.351110100018香農(nóng)碼的平均碼長(zhǎng)熵編碼效率

為提高編碼效率,把x4,x5換成前面的節(jié)點(diǎn),可減小平均碼長(zhǎng)。不應(yīng)先規(guī)定碼長(zhǎng),而是由碼樹來規(guī)定碼字,可得更好的結(jié)果。x1x2x5x3x49費(fèi)諾編碼費(fèi)諾編碼屬于概率匹配編碼

。編碼步驟如下：將概率按從大到小的順序排列,令p(x1)≥p(x2)≥…≥p(xn)按編碼進(jìn)制數(shù)將依次排列的概率分組,使每組概率和盡可能接近或相等。如編二進(jìn)制碼就分成兩組,編m進(jìn)制碼就分成m組。給每一組分配一位碼元。將每一分組再按同樣原則劃分,重復(fù)步驟2和3,直至概率不再可分為止。信源符號(hào)所對(duì)應(yīng)的碼字就是費(fèi)諾碼。10例設(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.0編碼效率:η=97.5%11平均碼長(zhǎng)編碼效率費(fèi)諾碼比較適合于每次分組概率都很接近的信源特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí),可達(dá)到理想的編碼效率。12例有一單符號(hào)離散無記憶信源對(duì)該信源編二進(jìn)制費(fèi)諾碼,編碼過程如表:13信源熵為H(X)=2.75平均碼長(zhǎng)為編碼效率為

η=1之所以如此,因?yàn)槊看嗡謨山M的概率恰好相等。費(fèi)諾碼是從樹根開始,把各節(jié)點(diǎn)分給某子集,若子集已是單點(diǎn)集,它就被賦予一片樹葉而作為碼字。14哈夫曼編碼哈夫曼編碼也是用碼樹來分配各符號(hào)的碼字。哈夫曼編碼是先給每一符號(hào)一片樹葉,逐步合并成節(jié)點(diǎn)直到樹根。哈夫曼(Huffman)編碼是一種效率比較高的變長(zhǎng)無失真信源編碼方法。15哈夫曼編碼的步驟如下：⑴將信源消息符號(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ù)步驟⑵的過程。⑷不斷繼續(xù)上述過程,直到最后兩個(gè)符號(hào)配以0和1為止。⑸從最后一級(jí)開始,向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列,即相應(yīng)的碼字。16例5-7

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

符號(hào)概率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在圖中讀取碼字的時(shí)候,要從后向前讀。17熵平均碼長(zhǎng)為編碼效率18哈夫曼的編法并不惟一。每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的,所以可得到不同的碼字。不同的碼元分配,得到的具體碼字不同,但碼長(zhǎng)Ki不變,平均碼長(zhǎng)也不變,所以沒有本質(zhì)區(qū)別；縮減信源時(shí),若合并后的新符號(hào)概率與其他符號(hào)概率相等,從編碼方法上來說,這幾個(gè)符號(hào)的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。此時(shí)，不同的編法得到的碼字長(zhǎng)度Ki也不盡相同。哈夫曼編碼19例5-8

單符號(hào)離散無記憶信源信源符號(hào)xi

符號(hào)概率p(xi)編碼過程x10.4x20.2x30.2x40.1x50.1010.40.20.20.2010.40.40.2010.60.401碼110100000100011碼200101101001120單符號(hào)信源編二進(jìn)制哈夫曼碼,編碼效率主要決定于信源熵和平均碼長(zhǎng)之比。對(duì)相同的信源編碼,其熵是一樣的,采用不同的編法,得到的平均碼長(zhǎng)可能不同。平均碼長(zhǎng)越短,編碼效率就越高。編法一的平均碼長(zhǎng)為編法二的平均碼長(zhǎng)為兩種編法的平均碼長(zhǎng)相同,所以編碼效率相同。21討論：哪種方法更好？定義碼字長(zhǎng)度的方差σ2：第二種編碼方法的碼長(zhǎng)方差要小許多。第二種編碼方法的碼長(zhǎng)變化較小,比較接近于平均碼長(zhǎng)。哈夫曼編碼22哈夫曼編碼第一種方法編出的5個(gè)碼字有4種不同的碼長(zhǎng)；第二種方法編出的碼長(zhǎng)只有兩種不同的碼長(zhǎng)；第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn),所以更好。結(jié)論：在哈夫曼編碼過程中,對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí),應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置,這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少,使短碼得到充分利用。23哈夫曼編碼的特點(diǎn)哈夫曼碼是用概率匹配方法進(jìn)行信源編碼。哈夫曼碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，充分利用了短碼；縮減信源的最后二個(gè)碼字總是最后一位不同，從而保證了哈夫曼碼是即時(shí)碼24比較香農(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)的、惟一的編碼方法,但在很多情況下編碼效率不是很高；費(fèi)諾碼和哈夫曼碼的編碼方法都不惟一