香農(nóng)編碼的優(yōu)化算法與哈夫曼編碼探究

孔元君+宋玉

摘 要：香農(nóng)編碼作為一種十分重要的變長(zhǎng)信源編碼的編碼方案，具有重要的指導(dǎo)意義.但其在實(shí)際應(yīng)用中也存在著效率低的不足.本文針對(duì)這一缺點(diǎn)，通過(guò)判斷相鄰碼字之間是否互為前綴對(duì)香農(nóng)編碼進(jìn)行了優(yōu)化，并進(jìn)行了仿真對(duì)比分析。最后，通過(guò)引入有‘最佳編碼之稱的哈夫曼編碼，與香農(nóng)編碼及其優(yōu)化算法進(jìn)行對(duì)比，說(shuō)明哈夫曼編碼策略的確是一種更加高效、更為可行的編碼方法。

關(guān)鍵詞：香農(nóng)編碼；信源編碼；哈夫曼編碼；最佳編碼

1 香農(nóng)編碼

1.1 香農(nóng)編碼原理

美國(guó)的工程師香農(nóng)于1948年在美國(guó)貝爾實(shí)驗(yàn)室期刊上刊登發(fā)表了一篇長(zhǎng)文《通訊的數(shù)學(xué)原理》[1] 。香農(nóng)編碼是一種不定長(zhǎng)編碼方式，通常將頻繁出現(xiàn)的消息信號(hào)編成短碼，不經(jīng)常出現(xiàn)的消息信號(hào)編成長(zhǎng)碼，從而有效地提高通信效率。香農(nóng)第一定理指出了

平均碼長(zhǎng)與信源字符之間的對(duì)應(yīng)關(guān)系，同時(shí)也指出：可以通過(guò)信源編碼方式使平均碼長(zhǎng)達(dá)到極限。

香農(nóng)第一定理指出，每個(gè)碼字的長(zhǎng)度Ki應(yīng)該滿足下式：

-log2 p（xi）≤ Ki <1-log2 p（xi） （1）

就能得到這種碼字。這種編碼方法就稱作香農(nóng)編碼 。

1.2 編碼步驟

二進(jìn)制香農(nóng)編碼的步驟如下：

（1）將信源符號(hào)按概率從大到小的順序排列

（2）對(duì)第j個(gè)前的概率進(jìn)行累加得到pa（aj）

（3）由-logp（ai） ki<1-logp（ai）求得碼字長(zhǎng)度ki

（4）用二進(jìn)制方式表示pa（aj），并取小數(shù)點(diǎn)后的ki位當(dāng)作符號(hào)ai的編碼碼字。

1.3 仿真實(shí)驗(yàn)

假設(shè)有7個(gè)信源符號(hào)，其概率分布為 {0.20，0.19，0.18，0.17，0.15，0.10，0.01}，在Visual Studio 2012上運(yùn)行，其編碼后的碼字和編碼效率如圖2所示。

2 哈夫曼編碼

2.1 哈夫曼編碼原理

哈夫曼編碼算法是滿足前綴條件下，所得到的平均二進(jìn)制碼長(zhǎng)最短的一種編-源表示，它將較短的碼字分配給大概率的信源符號(hào)。算法是：在信源符號(hào)集合中，首先將兩個(gè)最小概率的信源輸出合并為新的輸出，其概率是兩個(gè)相應(yīng)輸出符號(hào)的概率的和值。重復(fù)該過(guò)程，直到僅僅剩下一個(gè)合并輸出為止，這個(gè)最后的輸出符號(hào)概率為1。

例如，對(duì)信源符號(hào)概率0.4，0.2，0.2，0.1，0.1的編碼過(guò)程如表2所示

通過(guò)上表的對(duì)信源縮減合并過(guò)程，從而完成了對(duì)信源的霍夫曼編碼。

2.2 編碼步驟

編碼步驟主要分為兩步，首先是碼樹(shù)形成：對(duì)信源概率合并，形成編碼碼樹(shù)。第二是碼樹(shù)回溯：在碼樹(shù)上調(diào)配編碼碼字，最終得到哈夫曼碼。

1、碼樹(shù)構(gòu)造流程：將信源概率依據(jù)從小到大的順序排序，同時(shí)建立到相應(yīng)位置的索引。然后依照上述規(guī)則進(jìn)行信源合并，再對(duì)信源依次排序，并建立新的位置索引，直至結(jié)束合并。在該過(guò)程中每一次都把經(jīng)過(guò)排序的信源概率存放入矩陣G中，位置索引放入矩陣Index中。

表2 哈夫曼編碼過(guò)程

2、碼樹(shù)回溯流程：在碼樹(shù)上調(diào)配碼字，并最終得到Huffman編碼。從索引矩陣M的尾行向前回溯。

2.3 仿真實(shí)驗(yàn)

假設(shè)有7個(gè)信源符號(hào)，其概率分布為 {0.20，0.19，0.18，0.17，0.15，0.10，0.01}，在MATLAB 2014a平臺(tái)上仿真實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果如圖3所示。

3 結(jié)論

從上述實(shí)驗(yàn)可以看出，對(duì)同一信源概率矩陣，傳統(tǒng)香農(nóng)編碼的效率為0.830，經(jīng)過(guò)文獻(xiàn)法改進(jìn)，剔除了先限定每個(gè)碼字的碼長(zhǎng)這一過(guò)程，通過(guò)判斷碼字之間是否互為前綴來(lái)確定碼字，去除了大量冗余，編碼算法的效率達(dá)到了0.891，提高了6%。最后，哈夫曼編碼作為最佳編碼的代表，其編碼效率可以達(dá)到0.960，可見(jiàn)的確是一種更為高效可行的編碼方式。

參考文獻(xiàn)

[1] Shannon C E.A Mathematical Theory of Communication[J].The Bell System Technical Journal，1948，27：379—423

[2] 邵軍花， 劉玉紅， 邸敬，等. 香農(nóng)編碼的優(yōu)化算法研究[J]. 蘭州交通大學(xué)學(xué)報(bào)， 2010， 29（6）：110-113.

[3] Robert J，M The theory of information and coding [M].北京：電子工業(yè)出版社，2003：84—91

[4] Travis G.Shannon coding[J] Information Processing Letters，2007，102（2）：15—20.

[5] Yang Yan，Qian Tao.Co—dimension—P Shannon sampling theorems[J].Complex variables and elliptic equations。2007，52（1）：46—55.endprint