【正文】 依編碼路徑向前返回，就得到各信源符號所對應的碼字。 第七節(jié) 霍夫曼編碼 —— 二進制哈夫曼編碼 例 設單符號離散無記憶信源如下，要求對信源編二進制 霍夫曼碼。編碼過程如下圖（后頁）。 1 2 3 4 5 6 7 8, , , , ,( ) 0 . 4 0 . 1 8 0 . 1 0 . 1 0 . 0 7 0 . 0 6 0 . 0 5 0 . 0 4X x x x x x x x xPX? ? ? ?? ????? ? ? ?? 在圖中讀取碼字的時候，一定要從后向前讀，此時編出來的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。 第七節(jié) 霍夫曼編碼 —— 二進制哈夫曼編碼 第七節(jié) 霍夫曼編碼 —— 二進制哈夫曼編碼 ? 將上圖左右顛倒過來重畫一下，即可得到二進制哈夫曼碼的碼樹。 ? 信源熵為： ? 平均碼長為 ? 編碼效率為 ? 若采用定長編碼，碼長 K=3，則編碼效率 ? 可見哈夫曼的編碼效率提高了 %。 第七節(jié) 霍夫曼編碼 —— 二進制哈夫曼編碼 821( ) ( ) l o g ( ) 2 . 5 5 ( / )iiiH X p x p x?? ? ?? 比特 符號81( ) 0 . 4 1 ( 0 . 1 8 0 . 1 ) 3 ( 0 . 1 0 0 . 0 7 0 . 0 6 ) 4 ( 0 . 0 5 0 . 0 4 ) 5 2 . 6 1 ( / )iiiK p x k?? ? ? ? ? ? ? ? ? ? ? ? ? ?? 比特 符號( ) ( ) 2 .5 52 .6 1 %H X H XR K? ? ? ? ?2 .5 53 85%? ??第七節(jié) 霍夫曼編碼 —— 二進制哈夫曼編碼 注意 ： 哈夫曼的編法并不惟一 。 ? 每次對縮減信源兩個概率最小的符號分配“ 0”和“ 1”碼元是任意的，所以可得到不同的碼字。只要 在各次縮減信源中保持碼元分配的一致性 ， 即能得到可分離碼字。 ? 不同的碼元分配，得到的具體碼字不同，但碼長 ki不變，平均碼長 也不變，所以沒有本質區(qū)別； ? 縮減信源時，若合并后的新符號概率與其他符號概率相等，從編碼方法上來說， 這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的 碼字不相同 。 不同的編法得到的 碼字長度 ki也不盡相同 。 K例： 單符號離散無記憶信源 ，用 兩種不同的方法對其編二進制哈夫曼碼。 si li Wi 概率 s1 s2 s3 s4 s5 1 2 3 4 4 1 01 000 0010 0011 0 1 0 1 0 1 方法一： 合并后的新符號排在其它相同概率符號的后面。 1 2 3 4 5, , , , ,( ) 0 . 4 0 . 2 0 . 2 0 . 1 0 . 1X x x x x xPX? ? ? ?? ????? ? ? ?第七節(jié) 霍夫曼編碼 —— 二進制哈夫曼編碼 si li Wi 概率 s1 s2 s3 s4 s5 1 2 3 4 4 1 01 000 0010 0011 0 1 0 1 0 1 這兩種編碼哪一種更好呢，我們來計算一下二者的碼長。 方法二： 合并后的新符號排在其它相同概率符號的前面。 第七節(jié) 霍夫曼編碼 —— 二進制哈夫曼編碼 兩種編碼的平均碼長是一樣的，都是 ，那一種更好呢，我們可以計算一下平均碼長的方差。 511( ) 0 . 4 1 0 . 2 2 0 . 2 3 0 . 1 4 0 . 1 4 2 . 2iiiL P s l?? ? ? ? ? ? ? ? ? ? ? ??521( ) 0 . 4 2 0 . 2 2 0 . 2 2 0 . 1 3 0 . 1 3 2 . 2iiiL P s l?? ? ? ? ? ? ? ? ? ? ? ??2 2 21[ ( ) ] ( ) ( )qi i iiE l L P s l L??? ? ? ??522111( ) ( ) 1 . 3 6iiiP s l L??? ? ??5221( ) ( ) 0 .1 6iiiP s l L??? ? ??定義碼字長度的方差 σ2： 第七節(jié) 霍夫曼編碼 —— 二進制哈夫曼編碼 第七節(jié) 霍夫曼編碼 —— 二進制哈夫曼編碼 ? 可見：第二種編碼方法的碼長方差要小許多。意味著第二種編碼方法的碼長變化較小，比較接近于平均碼長。 ? 第一種方法編出的 5個碼字有 4種不同的碼長； ? 第二種方法編出的碼長只有兩種不同的碼長； ? 顯然， 第二種編碼方法更簡單、更容易實現(xiàn)，所以更好 。 結論 ： 在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應 使合并后的新符號盡可能排在靠前的位置 ，這樣可使合并后的新符號重復編碼次數(shù)減少，使短碼得到充分利用。 第七節(jié) 霍夫曼編碼 —— m進制哈夫曼編碼 “全樹”概念 ? 定義：碼樹圖中每個中間節(jié)點后續(xù)的枝數(shù)為 m時稱為 全樹 ；若有些節(jié)點的后續(xù)枝數(shù)不足 m，就稱為 非全樹 。 ? 二進制碼不存在非全樹的情況，因為后續(xù)枝數(shù)是一時，這個枝就可以去掉使碼字長度縮短。 ? 對 m進制編碼：若所有碼字構成全樹，可分離的碼字數(shù)（信源個數(shù)）必為 m+k(m－ 1)。 k為信源縮減次數(shù)。 ? 若信源所含的符號數(shù) n不能構成 m進制全樹，必須增加 s個不用的碼字形成全樹。顯然 sm－ 1，若 s=m－ 1，意味著某個中間節(jié)點之后只有一個分枝，為了節(jié)約碼長，這一分枝可以省略。 第七節(jié) 霍夫曼編碼 —— m進制哈夫曼編碼 ? 在編 m進制哈夫曼碼時為了使平均碼長最短，必須使最后一步縮減信源有 m個信源符號。