哈夫曼編碼的方法

1．哈夫曼編碼的方法編碼過(guò)程如下:

(1)將信源符號(hào)按概率遞減順序排列;

(2)把兩個(gè)最小的概率加起來(lái),作為新符號(hào)的概率;

(3)重復(fù)步驟(1)、(2),直到概率和達(dá)到1為止;

(4)在每次合并消息時(shí)，將被合并的消息賦以1和0或0和1；

(5)尋找從每個(gè)信源符號(hào)到概率為1處的路徑，記錄下路徑上的1和0；

(6)對(duì)每個(gè)符號(hào)寫(xiě)出"1"、"0"序列（從碼數(shù)的根到終節(jié)點(diǎn)）。2．哈夫曼編碼的特點(diǎn)①哈夫曼方法構(gòu)造出來(lái)的碼不是唯一的。原因

·在給兩個(gè)分支賦值時(shí),可以是左支(或上支)為0,也可以是右支(或下支)為0,造成編碼的不唯一。

·當(dāng)兩個(gè)消息的概率相等時(shí),誰(shuí)前誰(shuí)后也是隨機(jī)的,構(gòu)造出來(lái)的碼字就不是唯一的。②哈夫曼編碼碼字字長(zhǎng)參差不齊,因此硬件實(shí)現(xiàn)起來(lái)不大方便。

③哈夫曼編碼對(duì)不同的信源的編碼效率是不同的?！ぎ?dāng)信源概率是2的負(fù)冪時(shí),哈夫曼碼的編碼效率達(dá)到100%;

·當(dāng)信源概率相等時(shí),其編碼效率最低。

·只有在概率分布很不均勻時(shí),哈夫曼編碼才會(huì)收到顯著的效果,而在信源分布均勻的情況下,一般不使用哈夫曼編碼。

④對(duì)信源進(jìn)行哈夫曼編碼后,形成了一個(gè)哈夫曼編碼表。解碼時(shí),必須參照這一哈夫編碼表才能正確譯碼?！ぴ谛旁吹拇鎯?chǔ)與傳輸過(guò)程中必須首先存儲(chǔ)或傳輸這一哈夫曼編碼表在實(shí)際計(jì)算壓縮效果時(shí),必須考慮哈夫曼編碼表占有的比特?cái)?shù)。在某些應(yīng)用場(chǎng)合,信源概率服從于某一分布或存在一定規(guī)律(這主要由大量的統(tǒng)計(jì)得到),這樣就可以在發(fā)送端和接收端固定哈夫曼編碼表,在傳輸數(shù)據(jù)時(shí)就省去了傳輸哈夫曼編碼表,這種方法稱(chēng)為哈夫曼編碼表缺省使用。

使用缺省的哈夫曼編碼表有兩點(diǎn)好處:

·降低了編碼的時(shí)間,改變了編碼和解碼的時(shí)間不對(duì)稱(chēng)性;

·便于用硬件實(shí)現(xiàn),編碼和解碼電路相對(duì)簡(jiǎn)單。這種方法適用于實(shí)時(shí)性要求較強(qiáng)的場(chǎng)合。雖然這種方法對(duì)某一個(gè)特定應(yīng)用來(lái)說(shuō)不一定最好,但從總體上說(shuō),只要哈夫曼編表基于大量概率統(tǒng)計(jì),其編碼效果是足夠好的。3．哈夫曼編碼舉例現(xiàn)在有8個(gè)待編碼的符號(hào)M0，….，M0它們的概率如下表所示，使用霍夫曼編碼算法求出8個(gè)符號(hào)所分配的代碼。（寫(xiě)出編碼