信息論課件chap以第一定理為指導無失真信源壓縮的

上次課q 及相關(guān)概 qKraft不等

r i 碼

H(S)1LNH(Slog log log (i1, ,q p(s

Pi pk碼 碼的編碼步驟1）將個信源符號按概率遞減的方式進行排列p1p2 第一定理計算出每個信源符號的碼長 iPi k1將累加概率Pi用二進制數(shù)表示取Pi對應二進制數(shù)的小數(shù)點后符號的二進制碼

位構(gòu)成該3碼的編碼步驟如下信源符號以概率遞減的次序排列起來將排列好的信源符號按概率值劃分成兩大，使每組的概率之和接近于相等，并對每予一個二元碼符號“0”和5信源符號所對應的碼字即 碼4 1952年，（Huffman）提出了一種符號的編碼方法，一般稱作碼。設(shè)編碼對象為離散S{s1,s2,...,其對應的概率分p(si){p1,p2,...,pq}則對二 碼而言，其編碼步驟如下5編碼步驟（對二元系統(tǒng)將q個信源符號按概率遞減的方式排列起來用“0”,1”得到只包含1；S0，“縮減信源；0，“1”;從最后一級縮減信源開始，向前返回，得出各信源所對應的碼符號序列，即得出對應的碼字 例:對離散 信

s2s3s4s50s2s3s4s50. 0. 0. 0. 0.1 進 編碼為下面的信源符號為“1”上面的信源符號為“0”。從概率等于“1.0”端沿合并路線逆行至對應消息編碼78信源的熵為：H(S2.12(比特／符號從li123,45

p(ai)li

2.編碼效率為： H(S) 0.96L9[例]將下列消息按二 方法編

a7p(a

01

0.61

a5a2

a5 l1a2 l11a6 1 0

a6

llla30.100 0.011

a3→0110la7→0111l：

a7p(a 7可求出信源的熵7H(Sp(ailogp(ai2.61(比特/符號i

a5 l從：l=(2,2,3,3,3,4,4)可求得平均碼長為a2

l7Lp(ai)li2.72(二元碼符號/信源符號7i編碼效率H(S)

a6

lll

a3→0110la7→0111l1 碼的編碼方法，可知這種碼有如下特征①它是一種分組碼：各個信源符號都被映射成一組固定次序的碼符號；②它是一種即時碼：一串碼符號中的每個碼字都可不考其后的符號解③它是一種惟一可譯碼：任何碼符號串只能以碼

式 la2 la6 碼串可通過從左到右檢查各個

ll符號進行譯碼。本例中000110110101011可譯

l

a3→0110la7→0111l碼是一種即時碼，可用碼樹形式來表示“1”碼是可以任意的，所以可得到不同的碼，碼長li對給定信源，編碼方法得到的碼并非但平均碼長不[例]離散 信

s5p(s

信 編

概

縮減信源 0.4

00.4

0.20.1 10.1

1按概率分布的大小遞減次

將概率最小的兩個信源符號分別用“個符

從最后一級縮 s5p(s)

4所 碼的平均碼長為5Lp(si)li0.410.220.230.140.152.2（二元符號信源符號編碼效率

H(S)L對應的碼樹

信源

曼編碼所得的碼一定時碼0

第二 碼信 編 概 0

縮減信源

0.6

0.4

0.4

0.2

源開始向前返回縮減信源中合并的概率排列在這時各碼字長度分別為2，2，2，3，35

得出各信源符號應的碼平均碼長為：Lp(si)li0.40.20.2)20.10.12.2（二元信源符號上述編上述編碼的碼樹如圖

同樣可得

信 編 概

兩種編碼方法比較 樹結(jié)構(gòu)如右圖所示 ；平均碼長相同→編碼效率相；每個信源符號的碼長卻不編碼選擇依據(jù)：碼長li偏離平均長度L的方差q2E[(lL)2]p(s)(lL 2本例中，第一種編碼2＝1.366，第二種編碼2＝0.16，后 編碼過程中，當縮減信源的概率分布重新排列時，使合并得來的概率和盡量處于最高的位置，這樣可使合元素重復編碼次數(shù)減少，使短碼得到充分利用 碼的 碼，概率小的符號對應于長碼，即pj＞pk→ljlk同，前面各位碼元相同(二元編碼情況)。每次縮減信源的最長兩個碼字有相r 不同的只是每次把r個符號(概率最小的)合并成一個新的信源符號，并分別用0，1，…，(r-1)等碼元表示。r因此對于r元編碼，信源S的符號個數(shù)q必須滿足q＝n(r-1)+n表示縮減的次數(shù)，(r-1)為每次縮減所減少的信源符數(shù)對于二元碼(r＝2)，信源符號個數(shù)q必須滿足q＝n+因此q可等于任意整正數(shù) 而對于r元碼（r2）時，不一定能找到一個nq＝n(r-1)r成立。q不滿足上式時，可設(shè)一sq1,sq2,...,sqtpq1

...pqt

虛擬的信qt＝n(r-1r能成立這樣得到的r 碼一定 碼

方法及其對應的碼字 q＝n(r-1)+表中s9s10假設(shè)的信源符號，這樣q+t=10，能找到n=2。該四 碼的碼樹，如圖所示q＝n(r-1)+r時，所得從圖可知，當信源符號個數(shù)qq＝n(r-1r，則得到r元碼樹一定是整樹。所以，二元碼樹一定節(jié)點，。至此討論的三種編碼方法中 編碼方法所求得的二進制碼組集合是唯一的，即有信源符號