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

信源編碼

第5章15.1

編碼的定義5.2

無失真信源編碼5.3限失真信源編碼5.4常用信源編碼方法簡介內容2編碼的目的香農編碼定理雖然指出了理想編碼器的存在性,但是并沒有給出實用碼的結構及構造方法；編碼理論正是為了解決這一問題而發(fā)展起來的科學理論；編碼的目的是為了優(yōu)化通信系統(tǒng),就是使這些指標達到最佳；通信系統(tǒng)的性能指標主要是有效性、可靠性、安全性和經(jīng)濟性,除了經(jīng)濟性外,這些指標正是信息論研究的對象。按不同的編碼目的,編碼分為三類：信源編碼信道編碼安全編碼/密碼。3信源編碼：以提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實現(xiàn)。采用的一般方法是壓縮每個信源符號的平均比特數(shù)或信源的碼率。即同樣多的信息用較少的碼率傳送,使單位時間內傳送的平均信息量增加,從而提高通信的有效性。信道編碼：是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通常通過增加信源的冗余度來實現(xiàn)。采用的一般方法是增大碼率/帶寬。與信源編碼正好相反。密碼：是以提高通信系統(tǒng)的安全性為目的的編碼。通常通過加密和解密來實現(xiàn)。從信息論的觀點出發(fā)“加密”可視為增熵的過程,“解密”可視為減熵的過程。4信源編碼理論是信息論的一個重要分支,其理論基礎是信源編碼的兩個定理。無失真信源編碼定理：是離散信源/數(shù)字信號編碼的基礎；限失真信源編碼定理：是連續(xù)信源/模擬信號編碼的基礎。信源編碼的分類：離散信源編碼：獨立信源編碼,可做到無失真編碼；連續(xù)信源編碼：獨立信源編碼,只能做到限失真信源編碼；相關信源編碼：非獨立信源編碼。55.2無失真信源編碼6信源符號信源符號出現(xiàn)概率C1C2A0.600

0B0.2501

10C0.110

110D0.0511

1110信源{A,B,C,D}信源編碼器信道Error:10-4解碼信宿無失真信源編碼7C2

的效率比C1高碼字平均長度C1

和C2平均長度C2的區(qū)分

：0

表示碼字的結束011100110100…ADACBA…碼字平均長度8編碼效率信息率與編碼效率信息率95.2.3最佳變長編碼最佳碼：對于某一信源和某一碼符號集來說,若有一唯一可譯碼,其平均碼長小于所有其他唯一可譯碼的平均長度。緊致碼香農（Shannon）費諾（Fano）哈夫曼（Huffma）10香農編碼香農第一定理指出了平均碼長與信源之間的關系,同時也指出了可以通過編碼使平均碼長達到極限值,這是一個很重要的極限定理。香農第一定理指出,選擇每個碼字的長度Ki滿足下式：或:－log2

p(xi)≤Ki

<1－log2

p(xi)就可以得到這種碼。這種編碼方法稱為香農編碼

取整11二進制香農碼的編碼步驟如下：⑴將信源符號按概率從大到小的順序排列,

p(a1)≥p(a2)≥…≥p(an)⑵確定滿足下列不等式的整數(shù)Ki

,－log2

p(ai)≤Ki

<1－log2

p(ai)⑶令p(a1)=0,用Pi表示第i個碼字的累加概率，香農編碼⑷將Pi用二進制表示,并取小數(shù)點后Ki位作為符號ai的編碼。12例有一單符號離散無記憶信源對該信源編二進制香農碼。其編碼過程如表所示以i=3為例:碼字長度：K4=[－log0.2]=3累加概率

Pi=0.70→0.10110…00011011110011101這些碼字沒有占滿所有樹葉,所以是非最佳碼信源符號xi

符號概率p(xi)累加概率Pi-logp(xi)碼長碼字x10.401.32200x20.30.41.73201x30.20.72.323101x40.050.94.3

511100x50.050.954.351110113香農碼的平均碼長熵編碼效率為提高編碼效率,首先應達到滿樹;如把x4x5換成前面的節(jié)點,可減小平均碼長。不應先規(guī)定碼長,而是由碼樹來規(guī)定碼字,可得更好的結果。x1x2x5x3x414費諾編碼費諾編碼屬于概率匹配編碼

。編碼步驟如下：將概率按從大到小的順序排列,令p(x1)≥p(x2)≥…≥p(xn)按編碼進制數(shù)將概率分組,使每組概率盡可能接近或相等。如編二進制碼就分成兩組,編m進制碼就分成m組。給每一組分配一位碼元。將每一分組再按同樣原則劃分,重復步驟2和3,直至概率不再可分為止。15信源符號xi

符號概率p(xi)第1次分組第2次分組第3次分組碼字碼長x10.400002x40.05100103x50.0510113x20.310102x30.21112例設有一單符號離散信源對該信源編二進制費諾碼。信源符號xi

符號概率p(xi)第1分組第2分組第3分組第4分組碼字碼長x10.4001x20.310102x30.2101103x40.051011104x50.05111114平均碼長：K=2.1編碼效率:η=93%平均碼長：K=2.0編碼效率:η=97.5%16平均碼長編碼效率費諾碼比較適合于每次分組概率都很接近的信源特別是對每次分組概率都相等的信源進行編碼時,可達到理想的編碼效率。17例有一單符號離散無記憶信源對該信源編二進制費諾碼,編碼過程如表:18信源熵為H(X)=2.75(比特/符號)平均碼長為編碼效率為

η=1之所以如此,因為每次所分兩組的概率恰好相等。19哈夫曼編碼哈夫曼編碼也是用碼樹來分配各符號的碼字。費諾碼是從樹根開始,把各節(jié)點分給某子集,若子集已是單點集,它就是一片樹葉而作為碼字。哈夫曼編碼是先給每一符號一片樹葉,逐步合并成節(jié)點直到樹根。哈夫曼(Huffman)編碼是一種效率比較高的變長無失真信源編碼方法。20哈夫曼編碼的步驟如下：⑴將信源消息符號按其出現(xiàn)的概率大小依次排列

p(x1)≥p(x2)≥…≥p(xn)⑵取兩個概率最小的字母分別配以0和1兩碼元,并將這兩個概率相加作為一個新字母的概率,與未分配的二進符號的字母重新排隊。⑶對重排后的兩個概率最小符號重復步驟⑵的過程。⑷不斷繼續(xù)上述過程,直到最后兩個符號配以0和1為止。⑸從最后一級開始,向前返回得到各個信源符號所對應的碼元序列,即相應的碼字。21例5-7

設單符號離散無記憶信源如下,要求對信源編二進制哈夫曼碼。編碼過程如下表信源符號xi

符號概率p(xi)編碼過程x10.20x20.19x30.18x40.17x50.15x60.10x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901碼字101100000101001100111在圖中讀取碼字的時候,要從后向前讀,此時編出來的碼字是可分離的異前置碼。22熵平均碼長為編碼效率23哈夫曼的編法并不惟一。每次對縮減信源兩個概率最小的符號分配“0”和“1”碼元是任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。不同的碼元分配,得到的具體碼字不同,但碼長Ki不變,平均碼長也不變,所以沒有本質區(qū)別；縮減信源時,若合并后的新符號概率與其他符號概率相等,從編碼方法上來說,這幾個符號的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。不同的編法得到的碼字長度Ki也不盡相同。哈夫曼編碼24例5-8

單符號離散無記憶信源信源符號xi

符號概率p(xi)編碼過程x10.4x20.2x30.2x40.1x50.1010.40.20.20.2010.40.40.2010.60.401碼字10100000100011碼字00101101001125

26單符號信源編二進制哈夫曼碼,編碼效率主要決定于信源熵和平均碼長之比。對相同的信源編碼,其熵是一樣的,采用不同的編法,得到的平均碼長可能不同。平均碼長越短,編碼效率就越高。編法一的平均碼長為編法二的平均碼長為兩種編法的平均碼長相同,所以編碼效率相同。27討論：哪種方法更好？定義碼字長度的方差σ2：第二種編碼方法的碼長方差要小許多。第二種編碼方法的碼長變化較小,比較接近于平均碼長。哈夫曼編碼28哈夫曼編碼第一種方法編出的5個碼字有4種不同的碼長；第二種方法編出的碼長只有兩種不同的碼長；第二種編碼方法更簡單、更容易實現(xiàn),所以更好。結論：在哈夫曼編碼過程中,對縮減信源符號按概率由大到小的順序重新排列時,應使合并后的新符號盡可能排在靠前的位置,這樣可使合并后的新符號重復編碼次數(shù)減少,使短碼得到充分利用。29m進制哈夫曼編碼在編m進制哈夫曼碼時為了使平均碼長最短,必須使最后一步縮減信源有m個信源符號。對于m進制編碼,若所有碼字構成全樹,可分離的碼字數(shù)必為:

m＋k(m－l)非全樹時,有s個碼字不用：第一次對最小概率符號分配碼元時只取(m－s)個,分別配以0,1,…,m-s-1,把這些符號的概率相加作為一個新符號的概率,與其它符號一起重新排列以后每次取m個符號,分別配以0,1,…,m-1；如此下去,直至所有概率相加得1為止,即得到各符號的m進制碼字。30例:對如下單符號離散無記憶信源編三進制哈夫曼碼這里：m=3，n=8令k=3，m+k(m－1)=9，則s=9－n=9－8=1所以第一次取m－s=2個符號進行編碼。313進制哈夫曼編碼信源符號xi

符號概率p(xi)編碼過程x10.40x20.18x30.10x40.10x50.07x60.06x70.05x80.04010120.400.180.100.100.090.070.060.400.220.180.100.100120.400.380.22012碼字010111221222002013233平均碼長為信息率為編碼效率為哈夫曼的編碼效率相當高,對編碼器的要求也簡單得多。34

結論香農碼、費諾碼、哈夫曼碼都考慮了信源的統(tǒng)計特性,使經(jīng)常出現(xiàn)的信源符號對應較短的碼字,使信源的平均碼長縮短,從而實現(xiàn)了對信源的壓縮；香農碼有系統(tǒng)的、惟一的編碼方法,但在很多情況下編碼效率不是很高；費諾碼和哈夫曼碼的編碼方法都不惟一；費諾碼比較適合于對分組概率相等或接近的信源編碼,費諾碼也可以編m進制碼,但m越大,信源的符號數(shù)越多,可能的編碼方案就越多,編碼過程就越復雜,有時短碼未必能得到充分利