蔡春梅

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

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

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

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

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

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

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

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

三、總結(jié)

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

參考文獻(xiàn)

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

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

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

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

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