香農編碼的優化算法與哈夫曼編碼探究

孔元君+宋玉

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

關鍵詞：香農編碼；信源編碼；哈夫曼編碼；最佳編碼

1 香農編碼

1.1 香農編碼原理

美國的工程師香農于1948年在美國貝爾實驗室期刊上刊登發表了一篇長文《通訊的數學原理》[1] 。香農編碼是一種不定長編碼方式，通常將頻繁出現的消息信號編成短碼，不經常出現的消息信號編成長碼，從而有效地提高通信效率。香農第一定理指出了

平均碼長與信源字符之間的對應關系，同時也指出：可以通過信源編碼方式使平均碼長達到極限。

香農第一定理指出，每個碼字的長度Ki應該滿足下式：

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

就能得到這種碼字。這種編碼方法就稱作香農編碼 。

1.2 編碼步驟

二進制香農編碼的步驟如下：

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

（2）對第j個前的概率進行累加得到pa（aj）

（3）由-logp（ai） ki<1-logp（ai）求得碼字長度ki

（4）用二進制方式表示pa（aj），并取小數點后的ki位當作符號ai的編碼碼字。

1.3 仿真實驗

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

2 哈夫曼編碼

2.1 哈夫曼編碼原理

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

例如，對信源符號概率0.4，0.2，0.2，0.1，0.1的編碼過程如表2所示

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

2.2 編碼步驟

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

1、碼樹構造流程：將信源概率依據從小到大的順序排序，同時建立到相應位置的索引。然后依照上述規則進行信源合并，再對信源依次排序，并建立新的位置索引，直至結束合并。在該過程中每一次都把經過排序的信源概率存放入矩陣G中，位置索引放入矩陣Index中。

表2 哈夫曼編碼過程

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

2.3 仿真實驗

假設有7個信源符號，其概率分布為 {0.20，0.19，0.18，0.17，0.15，0.10，0.01}，在MATLAB 2014a平臺上仿真實現，實驗結果如圖3所示。

3 結論

從上述實驗可以看出，對同一信源概率矩陣，傳統香農編碼的效率為0.830，經過文獻法改進，剔除了先限定每個碼字的碼長這一過程，通過判斷碼字之間是否互為前綴來確定碼字，去除了大量冗余，編碼算法的效率達到了0.891，提高了6%。最后，哈夫曼編碼作為最佳編碼的代表，其編碼效率可以達到0.960，可見的確是一種更為高效可行的編碼方式。

參考文獻

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

[2] 邵軍花， 劉玉紅， 邸敬，等. 香農編碼的優化算法研究[J]. 蘭州交通大學學報， 2010， 29（6）：110-113.

[3] Robert J，M The theory of information and coding [M].北京：電子工業出版社，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