《信息論與編碼(第二版)》第5章-2

1、25.1 編碼的定義5.2 無失真信源編碼5.3 限失真信源編碼5.4 常用信源編碼方法簡介3 香農(nóng)編碼定理雖然指出了理想編碼器的存在性,但是并沒有給出實用碼的結(jié)構(gòu)及構(gòu)造方法； 編碼理論正是為了解決這一問題而發(fā)展起來的科學(xué)理論； 編碼的目的是為了優(yōu)化通信系統(tǒng),就是使這些指標(biāo)達(dá)到最佳； 通信系統(tǒng)的性能指標(biāo)主要是有效性、可靠性、安全性和經(jīng)濟(jì)性,除了經(jīng)濟(jì)性外,這些指標(biāo)正是信息論研究的對象。 按不同的編碼目的,編碼分為三類： 信源編碼 信道編碼 安全編碼/密碼。4 信源編碼： 以提高通信為目的的編碼。 通常通過壓縮信源的冗余度來實現(xiàn)。采用的一般方法是壓縮每個信源符號的平均比特數(shù)或信源的碼率。即同樣多的

2、信息用較少的碼率傳送,使單位時間內(nèi)傳送的平均信息量增加,從而提高通信的有效性。 信道編碼： 是以提高信息傳輸?shù)臑槟康牡木幋a。 通常通過增加信源的冗余度來實現(xiàn)。采用的一般方法是增大碼率/帶寬。與信源編碼正好相反。 密碼： 是以提高通信系統(tǒng)的為目的的編碼。 通常通過加密和解密來實現(xiàn)。從信息論的觀點(diǎn)出發(fā) “加密”可視為增熵的過程,“解密”可視為減熵的過程。5 信源編碼理論是信息論的一個重要分支,其理論基礎(chǔ)是信源編碼的兩個定理。無失真信源編碼定理：是離散信源/數(shù)字信號編碼的基礎(chǔ)；限失真信源編碼定理：是連續(xù)信源/模擬信號編碼的基礎(chǔ)。 信源編碼的分類：離散信源編碼：獨(dú)立信源編碼,可做到無失真編碼；連續(xù)信源

3、編碼：獨(dú)立信源編碼,只能做到限失真信源編碼；相關(guān)信源編碼：非獨(dú)立信源編碼。67信源符號信源符號出現(xiàn)概率C1C2A0.60 0 0B0.250 1 1 0C0.11 0 1 1 0D0.051 1 1 1 1 0信源A, B, C, D信源編碼器信道Error: 10-4解碼信宿8C2 的效率比 C1高 C1 和C2平均長度 C2的區(qū)分 ：0 表示碼字的結(jié)束011100110100ADACBA205.021.0225.026.021K6 . 105. 041 . 0325. 026 . 012KniiiKapK1)( 碼字平均長度9 編碼效率RXH)( 信息率mLKRLlog10 最佳碼： 對于

4、某一信源和某一碼符號集來說,若有一唯一可譯碼,其平均碼長小于所有其他唯一可譯碼的平均長度。 緊致碼 香農(nóng)（Shannon） 費(fèi)諾（Fano） 哈夫曼（Huffma ）11 香農(nóng)第一定理指出了平均碼長與信源之間的關(guān)系,同時也指出了可以通過編碼使平均碼長達(dá)到極限值,這是一個很重要的極限定理。 香農(nóng)第一定理指出,選擇每個碼字的長度Ki滿足下式： )(1logiixpK或: log2 p(xi) Ki 1log2 p(xi) 就可以得到這種碼。 這種編碼方法稱為 取整12 二進(jìn)制香農(nóng)碼的編碼步驟如下：將信源符號按概率從大到小的順序排列, p(a1) p(a2) p(an)確定滿足下列不等式的整數(shù)Ki

5、, log2 p(ai) Ki 1log2 p(ai)令p(a1)=0,用Pi表示第i個碼字的累加概率，11)(ikkiapP將Pi用二進(jìn)制表示,并取小數(shù)點(diǎn)后Ki位作為符號ai的編碼。例有一單符號離散無記憶信源 對該信源編二進(jìn)制香農(nóng)碼。其編碼過程如表所示以i = 3為例:碼字長度：K4 = log0.2 = 3累加概率 Pi=0.70 0.10110 00011011110011101這些碼字沒有占滿所有樹葉,所以是非最佳碼 信源符號xi 符號概率p(xi)累加概率Pi-log p(xi) 碼長碼字 x10.4 01.32 200 x20.30.41.73 201x30.20.72.32 31

6、01x40.050.94.3 511100 x50.050.954.351110105. 005. 02 . 03 . 04 . 0)(54321xxxxxxpX 香農(nóng)碼的平均碼長5 . 22505. 032 . 023 . 024 . 0)(51iiiKxpK 熵95. 105. 0log05. 022 . 0log2 . 03 . 0log3 . 04 . 0log4 . 0)(XH 編碼效率%785 . 295. 1)(KXH 為提高編碼效率,首先應(yīng)達(dá)到滿樹;如把x4x5換成前面的節(jié)點(diǎn),可減小平均碼長。 不應(yīng)先規(guī)定碼長,而是由碼樹來規(guī)定碼字,可得更好的結(jié)果。 x1x2x5x3x415 費(fèi)

7、諾編碼屬于概率匹配編碼 。 編碼步驟如下： 將概率按從大到小的順序排列,令p(x1) p(x2) p(xn) 按編碼進(jìn)制數(shù)將概率分組,使每組概率盡可能接近或相等。如編二進(jìn)制碼就分成兩組,編m進(jìn)制碼就分成m組。 給每一組分配一位碼元。 將每一分組再按同樣原則劃分,重復(fù)步驟2和3,直至概率不再可分為止。16信源符號xi 符號概率p(xi)第1次分組 第2次分組第3次分組碼字 碼長x10.4 00002x40.05100103x50.0510113x20.310102x30.21112 例設(shè)有一單符號離散信源 對該信源編二進(jìn)制費(fèi)諾碼。05. 005. 02 . 03 . 04 . 0)(54321x

8、xxxxxpX信源符號xi 符號概率p(xi)第1分組 第2分組第3分組第4分組碼字 碼長x10.4 001x20.310102x30.2101103x40.0510 1110 4x50.051 1111 4平均碼長：K= 2.1編碼效率: =93% 平均碼長：K= 2.0編碼效率: =97.5% 17%931 . 295. 1)(11KXH 平均碼長 編碼效率 費(fèi)諾碼比較適合于每次分組概率都很接近的信源 特別是對每次分組概率都相等的信源進(jìn)行編碼時,可達(dá)到理想的編碼效率。1 . 2) 305. 0 (222 . 023 . 024 . 0)(511iiiKxpK0 . 2) 405. 0 (2

9、32 . 023 . 014 . 0)(512iiiKxpK%5 .970 . 295. 1)(22KXH18例有一單符號離散無記憶信源 對該信源編二進(jìn)制費(fèi)諾碼,編碼過程如表:16/116/116/116/18/18/14/14/1,)(87654321xxxxxxxxXPX19 信源熵為 H(X)=2.75(比特/符號) 平均碼長為)/(75. 2440625. 03212. 02)25. 025. 0(符號比特K 編碼效率為 =1 之所以如此,因為每次所分兩組的概率恰好相等。20 哈夫曼編碼也是用碼樹來分配各符號的碼字。 費(fèi)諾碼是從樹根開始,把各節(jié)點(diǎn)分給某子集,若子集已是單點(diǎn)集,它就是一片

10、樹葉而作為碼字。 哈夫曼編碼是先給每一符號一片樹葉,逐步合并成節(jié)點(diǎn)直到樹根。 哈夫曼(Huffman)編碼是一種效率比較高的變長無失真信源編碼方法。21 哈夫曼編碼的步驟如下： 將信源消息符號按其出現(xiàn)的概率大小依次排列 p(x1)p(x2) p(xn)取兩個概率最小的字母分別配以0和1兩碼元,并將這兩個概率相加作為一個新字母的概率,與未分配的二進(jìn)符號的字母重新排隊。 對重排后的兩個概率最小符號重復(fù)步驟的過程。不斷繼續(xù)上述過程,直到最后兩個符號配以0和1為止。 從最后一級開始,向前返回得到各個信源符號所對應(yīng)的碼元序列,即相應(yīng)的碼字。22例5-7 設(shè)單符號離散無記憶信源如下,要求對信源編二進(jìn)制哈夫

11、曼碼。編碼過程如下表01. 010. 015. 017. 018. 019. 020. 0)(7654321xxxxxxxxpX信源符號xi 符號概率p(xi)編碼過程x10.20 x20.19x30.18x40.17x50.15x60.10 x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901碼字101100000101001100111在圖中讀取碼字的時候,要從后向前讀,此時編出來的碼字是可分離的異前置碼。23 熵61. 201. 0log01.

12、010. 0log10. 015. 0log15. 017. 0log17. 018. 0log18. 019. 0log19. 02 . 0log2 . 0)(XH 平均碼長為72. 2401. 0410. 0315. 0317. 0318. 0219. 022 . 0)(71iiiKxpK 編碼效率()()2.6196%2.72H XH XRK24 哈夫曼的編法并不惟一。 每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。 不同的碼元分配,得到的具體碼字不同,但碼長Ki不變,平均碼長也不變,所

13、以沒有本質(zhì)區(qū)別； 縮減信源時,若合并后的新符號概率與其他符號概率相等,從編碼方法上來說,這幾個符號的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。 不同的編法得到的碼字長度Ki也不盡相同。25 例5-8 單符號離散無記憶信源1 . 01 . 02 . 02 . 04 . 0,)(54321xxxxxXPX信源符號xi 符號概率p(xi)編碼過程x10.4 x20.2x30.2x40.1x50.1010.40.20.20.2010.40.40.2010.60.401碼字10100000100011碼字00101101001126 27 單符號信源編二進(jìn)制哈夫曼碼,編碼效率主要決定于信源

14、熵和平均碼長之比。 對相同的信源編碼,其熵是一樣的,采用不同的編法,得到的平均碼長可能不同。 平均碼長越短,編碼效率就越高。 編法一的平均碼長為2 . 2231 . 0222 . 024 . 0)(512iiiKxpK2 . 2241 . 032 . 022 . 014 . 0)(511iiiKxpK 編法二的平均碼長為 兩種編法的平均碼長相同,所以編碼效率相同。28 討論：哪種方法更好？ 定義碼字長度的方差2：51222)()(iiiiKKxpKKE36. 12) 2 . 24 ( 1 . 0) 2 . 23 ( 2 . 0) 2 . 22 ( 2 . 0) 2 . 21 ( 4 . 022

15、222116. 02) 2 . 23 ( 1 . 02) 2 . 22 ( 2 . 0) 2 . 22 ( 4 . 022222 第二種編碼方法的碼長方差要小許多。 第二種編碼方法的碼長變化較小,比較接近于平均碼長。29 第一種方法編出的5個碼字有4種不同的碼長； 第二種方法編出的碼長只有兩種不同的碼長； 第二種編碼方法更簡單、更容易實現(xiàn),所以更好。 在哈夫曼編碼過程中,對縮減信源符號按概率由大到小的順序重新排列時,應(yīng)使合并后的新符號盡可能排在靠前的位置,這樣可使合并后的新符號重復(fù)編碼次數(shù)減少,使短碼得到充分利用。30 在編m進(jìn)制哈夫曼碼時為了使平均碼長最短,必須使最后一步縮減信源有m個信源符

16、號。 對于m進(jìn)制編碼,若所有碼字構(gòu)成全樹,可分離的碼字?jǐn)?shù)必為: mk(ml) 非全樹時,有s個碼字不用： 第一次對最小概率符號分配碼元時只取(ms)個,分別配以0,1, ,m-s-1,把這些符號的概率相加作為一個新符號的概率,與其它符號一起重新排列 以后每次取m個符號,分別配以0,1,m-1；如此下去,直至所有概率相加得1為止,即得到各符號的m進(jìn)制碼字。31 例:對如下單符號離散無記憶信源編三進(jìn)制哈夫曼碼04. 005. 006. 007. 01 . 01 . 018. 04 . 0,)(87654321xxxxxxxxXPX這里：m =3，n =8 令k=3，m+k(m1)=9，則 s =

17、9n = 98 =1 所以第一次取ms=2個符號進(jìn)行編碼。32信源符號xi 符號概率p(xi)編碼過程x10.40 x20.18x30.10 x40.10 x50.07x60.06x70.05x80.04010120.400.180.100.100.090.070.060.400.220.180.100.100120.400.380.22012碼字010111221222002013334 平均碼長為)/(69. 13)04. 005. 0(2)06. 007. 01 . 018. 0(14 . 0)(51符號比特iiiKxpK)/(68. 23log169. 13log22符號比特LKR%2

18、 .9568. 255. 2)(RXH 信息率為 編碼效率為 哈夫曼的編碼效率相當(dāng)高,對編碼器的要求也簡單得多。35 香農(nóng)碼、費(fèi)諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特性,使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字,使信源的平均碼長縮短,從而實現(xiàn)了對信源的壓縮； 香農(nóng)碼有系統(tǒng)的、惟一的編碼方法,但在很多情況下編碼效率不是很高； 費(fèi)諾碼和哈夫曼碼的編碼方法都不惟一； 費(fèi)諾碼比較適合于對分組概率相等或接近的信源編碼,費(fèi)諾碼也可以編m進(jìn)制碼,但m越大,信源的符號數(shù)越多,可能的編碼方案就越多,編碼過程就越復(fù)雜,有時短碼未必能得到充分利用；對信源的統(tǒng)計特性沒有特殊要求,編碼效率比較高,對編碼設(shè)備的要求也比較簡單,因此綜合性能優(yōu)于香農(nóng)碼和費(fèi)諾碼。36 5-1137 香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼主要是針對無記憶信源。 當(dāng)信源有記憶時上述編碼效率不高； 游程編碼對編碼更有效； 香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼屬于無失真信源編碼； 游程編碼屬于限失真信源編碼。38： 數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。 二元序