信息論-變長(zhǎng)碼的編碼方法

1、5.4變長(zhǎng)碼的編碼方法宿菲coding 費(fèi)諾編碼Fano 霍夫曼編碼Huffman 香農(nóng)編碼Shannon香農(nóng)編碼（Shannon coding）1.信源的q個(gè)消息概率從大到小排序2.計(jì)算各個(gè)信源符號(hào)的累加概率3.計(jì)算第i個(gè)消息的碼長(zhǎng)4.將累加概率 變換成二進(jìn)制小數(shù)。根據(jù)碼長(zhǎng) 取小數(shù)點(diǎn)后 個(gè)二進(jìn)制符號(hào)作為第i個(gè)消息的碼字信源符號(hào)si概率平p（si）累加概率F（si）碼長(zhǎng)li二元碼S1S2S3S4S5S6S70.200.190.180.170.150.100.0100.20.390.570.740.890.992.342.412.482.562.743.346.66333334700000101

2、110010111101111110信源符號(hào)si及概率s1 s2 s3 s4 s5 s6 s70.21 0.19 0.17 0.16 0.15 0.10 0.02Huffman于1952年提出了這種方法，開(kāi)始主要用于電報(bào)報(bào)文的編碼，常用的英文字母E，T應(yīng)該如何編碼，不常用的應(yīng)該如何編碼，這樣編下來(lái)使報(bào)文最短。 它的基本原理是頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長(zhǎng)的代碼代替，每個(gè)數(shù)據(jù)的代碼各不相同。 Company Logo霍夫曼編碼（Huffman coding）信源的q個(gè)消息概率從大到小排序。0，1碼分別代表概率最小的兩個(gè)信源符號(hào)，并將這兩個(gè)概率最小的信源符號(hào)合并成一個(gè)，從而得

3、到只包括q-1個(gè)符號(hào)的新信源。將新信源仍按概率從大到小排序，再將最后兩個(gè)概率最小的信源符號(hào)分別用0和1碼符號(hào)表示，合并成一個(gè)新符號(hào)，這樣形成了q-2個(gè)符號(hào)的新信源。依次繼續(xù)下去，直至信源最后只剩下兩個(gè)信源符號(hào)為止。將這最后兩個(gè)信源符號(hào)用0和1表示。從最后一級(jí)縮減信源開(kāi)始，進(jìn)行回溯。Company Logo信源符號(hào)si及概率s1 s2 s3 s4 s5 s6 s70.21 0.19 0.17 0.16 0.15 0.10 0.02霍夫曼碼是即時(shí)碼？樹(shù)圖費(fèi)諾編碼（Fano coding）1.信源的q個(gè)消息概率從大到小排序。信源符號(hào)si概率平p（si）第一次分組第二次分組第三次分組第四次分組S1S2

4、S3S4S5S6S70.200.190.180.170.150.100.010101010101012.將依次排列的信源符號(hào)以概率分為兩組，使兩組的概率和基本相等。并賦予符號(hào)0和13.再分組，使劃分后的兩組的概率和基本相等，并賦予符號(hào)0和1。4.重復(fù)，直至每組只剩下一個(gè)信源符號(hào)為止。信源符號(hào)si及概率s1 s2 s3 s4 s5 s6 s70.21 0.19 0.17 0.16 0.15 0.10 0.02霍夫曼編碼（Huffman coding）霍夫曼碼是即時(shí)碼兩個(gè)特點(diǎn)：（1）保證了概率大的信源符號(hào)對(duì)應(yīng)的碼長(zhǎng)小，概率小的信源符號(hào)對(duì)應(yīng)的碼長(zhǎng)大，充分利用了短碼；（2）每次縮減信源的最長(zhǎng)兩個(gè)碼字有相同的碼長(zhǎng)，最后一位碼符號(hào)不同。（碼長(zhǎng)相差的?。┚幋a最短，傳輸效率最高實(shí)用的無(wú)失真編碼方法1.游程編碼（REL,REC） 應(yīng)用于：BMP TIF AVI