【正文】 編碼 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 游程編碼 ④ 二元獨(dú)立序列的熵 ? “ 0”游程序列的熵與“ 1”游程長度的熵之和除以它們的平均游程長度之和，即為對應(yīng)原二元序列的熵 H(X) ? 游程變換后符號熵沒有變。 ? 令“ 0”和“ 1”的概率分別為 p0和 p1，則“ 0”游程長度 L(0)的概率為 p[L(0)]=p0L(0)－ 1p1 式中 L(0)=1,2,…, ? 在計(jì)算 p[L(0)]時(shí)必然已有“ 0”出現(xiàn)，否則就不是“ 0”游程，若下一個(gè)符號是“ 1”，則游程長度為 1，其概率是 p1 =1－ p0；若下一個(gè)符號為“ 0”、再下一個(gè)符號為“ 1”，則游程長度為 2，其概率將為 p0p1 ；依此類推。 ? 編碼方法： ? 首先測定“ 0”游程長度和“ 1”游程長度的概率分布，即以游程長度為元素，構(gòu)造一個(gè)新的信源 ； ? 對新的信源（游程序列）進(jìn)行哈夫曼編碼。 例如：二元序列： 000101110010001… ，可變換成如下游程序列： 31132131 第八節(jié) 游程編碼、算術(shù)編碼、冗余編碼 ? 游程變換減弱了原序列符號間的相關(guān)性。 ? 游程長度序列 /游程序列：用交替出現(xiàn)的“ 0”游程和“ 1”游程長度表示任意二元序列。 游程編碼 ① 二元獨(dú)立序列游程長度概率 ? 若規(guī)定二元序列總是從“ 0”開始。 ? 二元序列的游程：只有“ 0”和“ 1”兩種符號。當(dāng)信源有記憶時(shí)上述編碼效率不高； ? 游程編碼對 相關(guān)信源 編碼更有效； ? 香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼屬于 無失真信源編碼 ； ? 游程編碼屬于 限失真信源編碼 。 511( ) 0 . 4 1 ( 0 . 1 8 0 . 1 0 . 0 7 0 . 0 6 ) 2 ( 0 . 0 5 0 . 0 4 ) 3 1 . 6 9 ( /)iiiK p x k?? ? ? ? ? ? ? ? ? ? ? ?? 比特 符號221 . 6 9l o g 3 l o g 3 2 . 6 8 ( / )1KRL? ? ? 比特 符號( ) 2 .5 5 9 5 .2 %2 .6 8HXR? ? ? ?一些結(jié)論 ? 香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源的統(tǒng)計(jì)特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實(shí)現(xiàn)了對信源的壓縮； ? 香農(nóng)碼有系統(tǒng)的、惟一的編碼方法，但在很多情況下編碼效率不是很高； ? 費(fèi)諾碼和哈夫曼碼的編碼方法都不惟一； ? 費(fèi)諾碼比較適合于對分組概率相等或接近的信源編碼； ? 哈夫曼碼對信源的統(tǒng)計(jì)特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼 。 這里： m=3， n=8 ? 令 k=3， m+k(m－ 1)=9，則 s=9－ n=9－ 8=1 ? 所以第一次取 m－ s=2個(gè)符號進(jìn)行編碼。 ? 以后每次就可以取 m個(gè)符號，分別配以 0,1,…, m－1； … ；如此下去，直至所有概率相加得 1為止，即得到各符號的 m進(jìn)制碼字。 第七節(jié) 霍夫曼編碼 —— m進(jìn)制哈夫曼編碼 ? 在編 m進(jìn)制哈夫曼碼時(shí)為了使平均碼長最短，必須使最后一步縮減信源有 m個(gè)信源符號。 ? 若信源所含的符號數(shù) n不能構(gòu)成 m進(jìn)制全樹，必須增加 s個(gè)不用的碼字形成全樹。 ? 對 m進(jìn)制編碼：若所有碼字構(gòu)成全樹，可分離的碼字?jǐn)?shù)（信源個(gè)數(shù)）必為 m+k(m－ 1)。 第七節(jié) 霍夫曼編碼 —— m進(jìn)制哈夫曼編碼 “全樹”概念 ? 定義：碼樹圖中每個(gè)中間節(jié)點(diǎn)后續(xù)的枝數(shù)為 m時(shí)稱為 全樹 ；若有些節(jié)點(diǎn)的后續(xù)枝數(shù)不足 m，就稱為 非全樹 。 ? 第一種方法編出的 5個(gè)碼字有 4種不同的碼長； ? 第二種方法編出的碼長只有兩種不同的碼長； ? 顯然， 第二種編碼方法更簡單、更容易實(shí)現(xiàn)，所以更好 。 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é) 霍夫曼編碼 —— 二進(jìn)制哈夫曼編碼 第七節(jié) 霍夫曼編碼 —— 二進(jìn)制哈夫曼編碼 ? 可見：第二種編碼方法的碼長方差要小許多。 方法二： 合并后的新符號排在其它相同概率符號的前面。 si li Wi 概率 s1 s2 s3 s4 s5 1 2 3 4 4 1 01 000 0010 0011 0 1 0 1 0 1 方法一： 合并后的新符號排在其它相同概率符號的后面。 不同的編法得到的 碼字長度 ki也不盡相同 。只要 在各次縮減信源中保持碼元分配的一致性 ， 即能得到可分離碼字。 第七節(jié) 霍夫曼編碼 —— 二進(jìn)制哈夫曼編碼 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é) 霍夫曼編碼 —— 二進(jìn)制哈夫曼編碼 注意 ： 哈夫曼的編法并不惟一 。 第七節(jié)