[工學(xué)]第8章無失真的信源編碼-展示頁
2025-01-28 12:05本頁面
【正文】 霍夫曼編碼 —— 二進(jìn)制哈夫曼編碼 第七節(jié) 霍夫曼編碼 —— 二進(jìn)制哈夫曼編碼 ? 將上圖左右顛倒過來重畫一下，即可得到二進(jìn)制哈夫曼碼的碼樹。 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? ? ? ?? ????? ? ? ?? 在圖中讀取碼字的時(shí)候，一定要從后向前讀，此時(shí)編出來的碼字才是可分離的異前置碼。 第七節(jié) 霍夫曼編碼 —— 二進(jìn)制哈夫曼編碼 例 設(shè)單符號離散無記憶信源如下，要求對信源編二進(jìn)制 霍夫曼碼。 ? 重復(fù)上述步驟，直至縮減信源只剩兩個(gè)符號為止，此時(shí)所剩兩個(gè)符號的概率之和必為 1。稱為 信源的第一次縮減信源 ，用 S1表示。 第七節(jié) 霍夫曼編碼 霍夫曼 (Huffman)編碼是一種效率比較高的變長 無失真信源編碼方法。特別是對每次 分組概率都相等 的信源進(jìn)行編碼時(shí)，可達(dá)到理想的編碼效率。 二進(jìn)制費(fèi)諾編碼 信源符號 概率 編碼 碼字 碼長 x 1 0 . 3 2 0 00 2 x 2 0 . 2 2 0 1 01 2 x 3 0 . 1 8 0 10 2 x 4 0 . 1 6 0 1 1 0 3 x 5 0 . 0 8 0 1 1 1 0 4 x 6 0 . 0 4 1 1 1 1 1111 4 1 2 3 4 5 6, , , , ,( ) 0 . 3 2 0 . 2 2 0 . 1 8 0 . 1 6 0 . 0 8 0 . 0 4X x x x x x xPX? ? ? ?? ????? ? ? ?第六節(jié) 費(fèi)諾編碼 ? 該信源的熵為 ? 平均碼長為 ? 編碼效率為 ? 本例中費(fèi)諾編碼有較高的編碼效率。 第六節(jié) 費(fèi)諾編碼 例 設(shè)有一單符號離散信源 ? 對該信源編二進(jìn)制費(fèi)諾碼。 ? 給每一組分配一位碼元。 編碼步驟如下： ? 將概率按從大到小的順序排列，令 p(x1)≥ p(x2)≥…≥ p(xn) ? 按編碼進(jìn)制數(shù)將概率分組，使每組概率盡可能接近或相等。則 ? 可以看出，編碼效率并不是很高。相比較，香農(nóng)編碼對信源進(jìn)行了壓縮。其編碼過程如下表所示。第八章 無失真的信源編碼 霍夫曼（ Huffman）碼 費(fèi)諾 (Fano)碼 香農(nóng) 費(fèi)諾 埃得斯碼 游程編碼和 MH編碼 字典碼 算術(shù)編碼 霍夫曼（ Huffman）碼 ? 設(shè)離散無記憶信源 ? 二進(jìn)制香農(nóng)碼的編碼步驟如下： ? 將信源符號按概率從大到小的順序排列，為方便起見，令 p(x1)≥ p(x2)≥…≥ p(xn) ? 令 p(x0)=0，用 pa(xj)， j=i+1表示第 i個(gè)碼字的累加概率，則： ? 確定滿足下列不等式的整數(shù) ki ，并令 ki為第 i個(gè)碼字的長度 ? － log2 p(xn)≤ki－ log2 p(xn)+1 ? 將 pa(xj) 用二進(jìn)制表示，并取小數(shù)點(diǎn)后 ki 位作為符號 xi的編碼。 10( ) ( ) , 1 , 2 , ,ja j iip x p x j n?????12112, , , , , , ( ) 1( ) , ( ) , , ( ) , , ( )()niniiinx x x xX pxp x p x p x p xPX ????? ???????? ?? ?例 有一單符號離散無記憶信源 對該信源編二進(jìn)制香農(nóng)碼。 二 進(jìn)制香農(nóng)編碼 x i p ( x i ) p a ( x j ) k i 碼字 x 1 0 . 2 5 0 . 0 0 0 2 0 0 (0 . 0 0 0 ) 2 x 2 0 . 2 5 0 . 2 5 0 2 0 1 (0 . 0 1 0 ) 2 x 3 0 . 2 0 0 . 5 0 0 3 1 0 0 (0 . 1 0 0 ) 2 x 4 0 . 1 5 0 . 7 0 0 3 1 0 1 (0 . 1 0 1 ) 2 x 5 0 . 1 0 0 . 8 5 0 4 1 1 0 1 (0 . 1 1 0 1 ) 2 x 6 0 . 0 5 0 . 9 5 0 5 1 1 1 1 1 0 (0 . 1 1 1 1 0 ) 2 1 2 3 4 5 6, , , , ,( ) 0 . 2 5 0 . 2 5 0 . 2 0 0 . 1 5 0 . 1 0 0 . 0 5X x x x x x xPX? ? ? ?? ????? ? ? ? 霍夫曼（ Huffman）碼 ? 計(jì)算出給定信源香農(nóng)碼的平均碼長 ? 若對上述信源采用等長編碼，要做到無失真譯碼，每個(gè)符號至少要用 3個(gè)比特表示。 ? 由離散無記憶信源熵定義，可計(jì)算出： ? 對上述信源采用香農(nóng)編碼的信息率為 ? 編碼效率為信源熵和信息率之比。 0 .2 5 2 2 ( 0 .2 0 .1 5 ) 3 0 .1 0 4 0 .0 5 5 2 .7 ( / )K ? ? ? ? ? ? ? ? ? ? ? 比特 符號222 . 7l o g l o g 2 2 . 7 1 , 21KR m L mL? ? ? ? ?這里( ) 2 .4 2 8 9 .6 3 %2 .7HXR? ? ? ?621( ) ( ) l o g ( ) 2 . 4 2 ( / )iiiH X p x p x?? ? ?? 比特 符號 霍夫曼（ Huffman）碼 第六節(jié) 費(fèi)諾編碼 費(fèi)諾編碼也是一種常見的信源編碼方法。如編二進(jìn)制碼就分成兩組，編 m進(jìn)制碼就分成 m組。 ? 將每一分組再按同樣原則劃分，重復(fù)步驟 2和 3，直至概率不再可分為止。編碼過程如下表。費(fèi)諾碼比較適合于每次分組概率都很接近 的信源。 621( ) ( ) l o g ( ) 2 . 3 5 ( / )iiiH X p x p x?? ? ?? 比特 符號61( ) 2 . 4 ( / )iiiK p x k???? 比特 符號 1( ) 2 . 3 5 2 . 3 5 9 7 . 9 2 % 1 , 2l o g l o g 2 2 . 4KLHX Lmm? ? ? ? ? ? ?這里第六節(jié)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1