哈夫曼編碼方法的方案選擇研究

蔡春梅

【摘要】本文首先分析了哈夫曼編碼的理論根據(jù)，介紹了哈夫曼編碼的編碼過程，通過舉例詳細(xì)分析了不同編碼方案的編碼結(jié)果，最后對(duì)不同方案的編碼方法進(jìn)行了總結(jié)。

【關(guān)鍵詞】哈夫曼編碼無失真編碼編碼方案

香農(nóng)編碼理論指出存在一種無失真的編碼方法，使得編碼平均碼長逼近熵值這個(gè)下限，并指出了理想編碼器的存在。但在香農(nóng)理論中并未給出使用碼的結(jié)構(gòu)及構(gòu)造方法，即沒有給出具體的編碼方法，編碼理論為解決此問題而發(fā)展起來，如香農(nóng)編碼法、費(fèi)諾編碼法和哈夫曼編碼法，其中尤其以哈夫曼編碼法為最佳。哈夫曼編碼方法于1952年問世，至今仍廣泛應(yīng)用于各種數(shù)據(jù)壓縮技術(shù)中，在多媒體編碼系統(tǒng)中常用這種方法作熵保持編碼。

一、哈夫曼編碼方法簡(jiǎn)介

最佳編碼定理指出：在編碼過程中，對(duì)于信源符號(hào)，如果出現(xiàn)概率大的符號(hào)分配短字長的碼字，出現(xiàn)概率小的符號(hào)分配長碼字，編碼編碼結(jié)束后，得到的碼字長度嚴(yán)格按照符號(hào)概率的大小的相反順序，那么這種編碼方式得到的平均碼字長度一定小于任何其他排列方式得到的碼字長度。哈夫曼編碼法就是利用了這個(gè)原理，是一種典型的無失真的編碼方法，且是熵編碼中的最佳編碼方法。

哈夫曼編碼法的過程：首先將信源按概率遞減排列，然后將最小兩個(gè)概率相加，得到的新概率再放入原概率序列中重新排列，如此反復(fù)，不斷的縮減信源，直至信源個(gè)數(shù)只剩一個(gè)為止。最后從最后一級(jí)縮減信源開始，依編碼路徑向前返回，并分配碼字，得到哈夫曼碼。

二、哈夫曼編碼方案分析與選擇

根據(jù)哈夫曼編碼的方法可得：哈夫曼編碼法編碼結(jié)果一定不唯一。首先，縮減信源結(jié)束后，對(duì)最小概率分配“0”和“1”是任意的；其次，當(dāng)將概率序列中的兩個(gè)最小概率相加時(shí)，得到的概率和可能與原序列中的概率相等，此時(shí)，概率相等的幾個(gè)符號(hào)及可以任意排列，也將導(dǎo)致最終的編碼不唯一。那編碼中究竟哪種方案更好呢？用以下這由此可見，編碼二的方差較小，說明其碼字的變化較小，此方案較好。

三、總結(jié)

哈夫曼編碼方法主要是依據(jù)最佳編碼定理，通過以上例子的分析，我們得出結(jié)論：在編碼的過程中，對(duì)縮減信源符號(hào)按概率由大到小得順序重新排列時(shí)，應(yīng)將相加后的新概率盡可能的排在其他相同概率之前，這樣就可以使相加后的新符號(hào)概率重復(fù)編碼的次數(shù)減少，使得短碼得到充分利用。

參考文獻(xiàn)

[1]陳運(yùn).信息論與編碼.北京：電子工業(yè)出版社. 2009

[2]姜丹.信息論與編碼.合肥：中國科技技術(shù)大學(xué)出版社. 2001

[3]傅祖蕓.信息論與基礎(chǔ).北京：電子工業(yè)出版社. 2006

[4]鐘家愷.通信原理教程.北京：科學(xué)出版社. 2003

[5]鐘玉琢.多媒體技術(shù)基礎(chǔ)與應(yīng)用.北京：清華大學(xué)出版社，2008