信息論：第8章 無失真的信源編碼

1、 第第8章章 無失真的信源編碼無失真的信源編碼趙趙 越越2012.112l香農(nóng)編碼定理雖然指出了理想編碼器的存在性香農(nóng)編碼定理雖然指出了理想編碼器的存在性,但是但是并沒有給出實(shí)用碼的結(jié)構(gòu)及構(gòu)造方法；并沒有給出實(shí)用碼的結(jié)構(gòu)及構(gòu)造方法；l編碼理論正是為了解決這一問題而發(fā)展起來的科學(xué)編碼理論正是為了解決這一問題而發(fā)展起來的科學(xué)理論；編碼的目的是為了優(yōu)化通信系統(tǒng)，就是使這些理論；編碼的目的是為了優(yōu)化通信系統(tǒng)，就是使這些指標(biāo)達(dá)到最佳；指標(biāo)達(dá)到最佳；l通信系統(tǒng)的性能指標(biāo)主要是通信系統(tǒng)的性能指標(biāo)主要是有效性有效性、可靠性可靠性、安全安全性性和和經(jīng)濟(jì)性經(jīng)濟(jì)性，除了經(jīng)濟(jì)性外，這些指標(biāo)正是信息論研，除了經(jīng)濟(jì)性外，

2、這些指標(biāo)正是信息論研究的對象。究的對象。l按不同的編碼目的，編碼分為三類：按不同的編碼目的，編碼分為三類：信源編碼信源編碼、信信道編碼道編碼和和安全編碼安全編碼/密碼密碼。3信源編碼信源編碼：以提高通信有效性為目的的編碼。通常通：以提高通信有效性為目的的編碼。通常通過壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮過壓縮信源的冗余度來實(shí)現(xiàn)。采用的一般方法是壓縮每個信源符號的平比特?cái)?shù)或信源的碼率。即同樣多的每個信源符號的平比特?cái)?shù)或信源的碼率。即同樣多的信息用較少的碼率傳送，使單位時間內(nèi)傳送的平均信信息用較少的碼率傳送，使單位時間內(nèi)傳送的平均信息量增加，從而提高通信的有效性。息量增加，從而提高通信的有

3、效性。信道編碼信道編碼：是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。：是以提高信息傳輸?shù)目煽啃詾槟康牡木幋a。通過增加信源的冗余度來實(shí)現(xiàn)。采用的一般方法是增通過增加信源的冗余度來實(shí)現(xiàn)。采用的一般方法是增大碼率大碼率/帶寬。與信源編碼正好相反。帶寬。與信源編碼正好相反。4密碼密碼：是以提高通信系統(tǒng)的安全性為目的的編碼。通：是以提高通信系統(tǒng)的安全性為目的的編碼。通常通過加密和解密來實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，常通過加密和解密來實(shí)現(xiàn)。從信息論的觀點(diǎn)出發(fā)，“加密加密”可視為增熵的過程，可視為增熵的過程，“解密解密”可視為減熵的可視為減熵的過程。過程。 信源編碼理論是信息論的一個重要分支，其理論基信源編碼理論是信

4、息論的一個重要分支，其理論基礎(chǔ)是信源編碼的兩個定理。礎(chǔ)是信源編碼的兩個定理。無失真信源編碼定理無失真信源編碼定理：是離散信源：是離散信源/數(shù)字信號編碼的基礎(chǔ)；數(shù)字信號編碼的基礎(chǔ)；限失真信源編碼定理限失真信源編碼定理：是連續(xù)信源：是連續(xù)信源/模擬信號編碼的基礎(chǔ)。模擬信號編碼的基礎(chǔ)。5信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相信源編碼的分類：離散信源編碼、連續(xù)信源編碼和相關(guān)信源編碼三類。關(guān)信源編碼三類。離散信源編碼離散信源編碼：獨(dú)立信源編碼，可做到無失真編碼；：獨(dú)立信源編碼，可做到無失真編碼；連續(xù)信源編碼連續(xù)信源編碼：獨(dú)立信源編碼，只能做到限失真信源：獨(dú)立信源編碼，只能做到限失真信源 編碼；編

5、碼；相關(guān)信源編碼相關(guān)信源編碼：非獨(dú)立信源編碼。：非獨(dú)立信源編碼。6 有些編碼原理和技術(shù)在通信原理和信號處理等相關(guān)課有些編碼原理和技術(shù)在通信原理和信號處理等相關(guān)課程中介紹。例如：程中介紹。例如：u連續(xù)信源編碼：脈沖編碼調(diào)制連續(xù)信源編碼：脈沖編碼調(diào)制(PCM)、矢量量化技術(shù)；、矢量量化技術(shù)；u相關(guān)信源編碼：相關(guān)信源編碼：預(yù)測編碼：增量編碼、差分脈沖調(diào)制預(yù)測編碼：增量編碼、差分脈沖調(diào)制(DPCM)、自適應(yīng)、自適應(yīng)差分脈沖調(diào)制差分脈沖調(diào)制(ADPCM)、線性預(yù)測聲碼器；、線性預(yù)測聲碼器；變換編碼：變換編碼：K-L變換、離散變換、子帶編碼、變換、離散變換、子帶編碼、 小波變換。小波變換。7無失真信源編碼

6、無失真信源編碼和和限失真信源編碼限失真信源編碼的應(yīng)用的應(yīng)用l 前者主要用于離散信源或數(shù)字信號，如文本、表格前者主要用于離散信源或數(shù)字信號，如文本、表格及工程圖紙等信源，要求進(jìn)行無失真的數(shù)據(jù)壓縮，及工程圖紙等信源，要求進(jìn)行無失真的數(shù)據(jù)壓縮，要求能夠無失真地可逆恢復(fù)要求能夠無失真地可逆恢復(fù);l 后者主要用于波形信源或波形信號，如語音、電視后者主要用于波形信源或波形信號，如語音、電視圖像、彩色靜止圖像等信號，它們不要求完全可逆圖像、彩色靜止圖像等信號，它們不要求完全可逆地恢復(fù)，而是允許在一定限度可以有失真的壓縮。地恢復(fù)，而是允許在一定限度可以有失真的壓縮。l 兩者目的都是為了用較少的碼率來傳送同樣多

7、的信兩者目的都是為了用較少的碼率來傳送同樣多的信息，提高系統(tǒng)有效性。息，提高系統(tǒng)有效性。8 香農(nóng)第一定理給出了香農(nóng)第一定理給出了信源熵信源熵與編碼后的與編碼后的平均碼長平均碼長之間的關(guān)系，同時也指出可已通過編碼使平均碼長達(dá)之間的關(guān)系，同時也指出可已通過編碼使平均碼長達(dá)到極限值，因此，香農(nóng)第一定理是一個極限定理。到極限值，因此，香農(nóng)第一定理是一個極限定理。 但定理中并沒有告訴我們?nèi)绾蝸順?gòu)造這種碼。但定理中并沒有告訴我們?nèi)绾蝸順?gòu)造這種碼。 最佳變長碼最佳變長碼：凡是能載荷一定的信息量，且碼字的平：凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合稱為最佳變均長度最短，可分離的變

8、長碼的碼字集合稱為最佳變長碼。長碼。9 我們學(xué)習(xí)三種編碼方法：我們學(xué)習(xí)三種編碼方法：香農(nóng)碼香農(nóng)碼、霍夫曼碼霍夫曼碼以及以及費(fèi)諾碼費(fèi)諾碼。 這三種碼的平均碼長都比較短。這三種碼的平均碼長都比較短。 因?yàn)槠骄a長是各個碼的概率平均，可以想象，因?yàn)槠骄a長是各個碼的概率平均，可以想象，應(yīng)該使出現(xiàn)概率大的信源符號編碼后碼長盡量短一應(yīng)該使出現(xiàn)概率大的信源符號編碼后碼長盡量短一些。三種編碼方法的出發(fā)點(diǎn)都是如此。些。三種編碼方法的出發(fā)點(diǎn)都是如此。10香農(nóng)編碼香農(nóng)編碼 香農(nóng)編碼嚴(yán)格意義上來說不是最佳碼。香農(nóng)編碼嚴(yán)格意義上來說不是最佳碼。 香農(nóng)編碼是采用信源符號的香農(nóng)編碼是采用信源符號的累計(jì)概率累計(jì)概率分布函數(shù)

9、來分布函數(shù)來分配碼字。分配碼字。8.1 霍夫曼碼霍夫曼碼11香農(nóng)編碼方法如下：香農(nóng)編碼方法如下：(1)將信源消息符號按其出現(xiàn)的概率大小依次排列：將信源消息符號按其出現(xiàn)的概率大小依次排列：(2)確定滿足下列不等式的整數(shù)碼長確定滿足下列不等式的整數(shù)碼長Ki：(3)為了編成唯一可譯碼，計(jì)算第為了編成唯一可譯碼，計(jì)算第i個消息的個消息的累加概率累加概率)()()(21nxpxpxp1)(log)(log22iiixpKxp11)(ikkixpP12(4)將累加概率將累加概率Pi變換成二進(jìn)制數(shù)。變換成二進(jìn)制數(shù)。(5)取取Pi二進(jìn)制數(shù)的小數(shù)點(diǎn)后二進(jìn)制數(shù)的小數(shù)點(diǎn)后Ki位即為該消息符號的位即為該消息符號的二進(jìn)

10、制碼字。二進(jìn)制碼字。 可以證明，這樣得到的編碼一定是唯一可譯碼，可以證明，這樣得到的編碼一定是唯一可譯碼，且碼長比較短，接近于最佳編碼。且碼長比較短，接近于最佳編碼。13信源消息符號信源消息符號xi符號概率符號概率p(xi)x1 0.20 x2 0.19x3 0.18x4 0.17x5 0.15x6 0.10 x7 0.01 例：例： 設(shè)信源共有設(shè)信源共有7個符號組成，其概率如表所示，個符號組成，其概率如表所示，求其香農(nóng)碼。求其香農(nóng)碼。1415 以以i=4為例，為例， 累加概率累加概率Pi=0.57，變成二進(jìn)制數(shù)，為，變成二進(jìn)制數(shù)，為0.1001。 轉(zhuǎn)換的方法轉(zhuǎn)換的方法是：用是：用Pi乘以乘以

11、2，如果整數(shù)部分有進(jìn)位，如果整數(shù)部分有進(jìn)位，則小數(shù)點(diǎn)后第一位為則小數(shù)點(diǎn)后第一位為1，否則為，否則為0，將其小數(shù)部分，將其小數(shù)部分再做同樣的處理，得到小數(shù)點(diǎn)后的第二位，依此再做同樣的處理，得到小數(shù)點(diǎn)后的第二位，依此類推，直到得到了滿足要求的位數(shù)，或者沒有小類推，直到得到了滿足要求的位數(shù)，或者沒有小數(shù)部分了為止。數(shù)部分了為止。 356.356.2117.0log17.0log44242KKK，因此即16 例如現(xiàn)在例如現(xiàn)在Pi=0.57，乘以，乘以2為為1.14，整數(shù)部分有進(jìn)，整數(shù)部分有進(jìn)位，所以小數(shù)點(diǎn)后第一位為位，所以小數(shù)點(diǎn)后第一位為1，將小數(shù)部分即，將小數(shù)部分即0.14再乘以再乘以2，得，得0.

12、28，沒有整數(shù)進(jìn)位，所以小數(shù)點(diǎn)后，沒有整數(shù)進(jìn)位，所以小數(shù)點(diǎn)后第二位為第二位為0，依此類推，可得到其對應(yīng)的二進(jìn)制，依此類推，可得到其對應(yīng)的二進(jìn)制數(shù)為數(shù)為0.1001。 可以看出，編碼所得的碼字，沒有相同的，所以可以看出，編碼所得的碼字，沒有相同的，所以是非奇異碼，也沒有一個碼字是其它碼字的前綴，是非奇異碼，也沒有一個碼字是其它碼字的前綴，所以是即時碼，也是唯一可譯碼。所以是即時碼，也是唯一可譯碼。17 平均碼長平均碼長為：為： 平均信息傳輸效率平均信息傳輸效率為為符號碼元/14. 3)(71iiiKxpK碼元/831. 014. 361. 2)(bitKXHR18 注意注意：此例中，：此例中，X

13、6與與X7的碼字完全可以采用長度為的碼字完全可以采用長度為3的其他的碼字代替，而沒有必要采用碼長的其他的碼字代替，而沒有必要采用碼長4和和7。19 香農(nóng)編碼的效率不高，實(shí)用意義不大，但對其它編香農(nóng)編碼的效率不高，實(shí)用意義不大，但對其它編碼方法有很好的理論指導(dǎo)意義。碼方法有很好的理論指導(dǎo)意義。 一般情況下，按照香農(nóng)編碼方法編出來的碼，其平一般情況下，按照香農(nóng)編碼方法編出來的碼，其平均碼長不是最短的，也即不是緊致碼均碼長不是最短的，也即不是緊致碼(最佳碼最佳碼)。只有。只有當(dāng)信源符號的概率分布使不等式左邊的等號成立時，當(dāng)信源符號的概率分布使不等式左邊的等號成立時，編碼效率才達(dá)到最高。編碼效率才達(dá)到

14、最高。20 1952年霍夫曼提出了一種構(gòu)造最佳碼的方法。它是一年霍夫曼提出了一種構(gòu)造最佳碼的方法。它是一種最佳的逐個符號的編碼方法。其編碼步驟如下：種最佳的逐個符號的編碼方法。其編碼步驟如下： (1) 將信源消息符號按其出現(xiàn)的概率大小依次排列將信源消息符號按其出現(xiàn)的概率大小依次排列)()()(21qxpxpxp8.1.1 二元霍夫曼碼二元霍夫曼碼 (2) 用用“0”和和“1”碼符號分別代表概率最小的兩個碼符號分別代表概率最小的兩個信源符號，并將這兩個概率最小的符號相加合并成信源符號，并將這兩個概率最小的符號相加合并成一個新的符號，新的符號概率為兩個符號概率之和，一個新的符號，新的符號概率為兩個

15、符號概率之和，然后與未分配的符號重新排隊(duì)，從而得到只包含然后與未分配的符號重新排隊(duì)，從而得到只包含q-1個符號的新信源，稱為個符號的新信源，稱為縮減信源縮減信源。21 (3) 重復(fù)步驟重復(fù)步驟(2)：把縮減信源的符號仍舊按概率大：把縮減信源的符號仍舊按概率大小以遞減次序排列，再將其概率最小的兩個信源符小以遞減次序排列，再將其概率最小的兩個信源符號分別用號分別用“0”和和“1”表示，并將其合并成一個符號，表示，并將其合并成一個符號，概率為兩符號概率之和，這樣又形成了概率為兩符號概率之和，這樣又形成了q-2個符號個符號的的縮減信源縮減信源。 (4) 不斷繼續(xù)上述過程，直至信源只剩下兩個符號不斷繼續(xù)

16、上述過程，直至信源只剩下兩個符號為止。將這最后兩個信源符號分別用為止。將這最后兩個信源符號分別用“0”和和“1”表表示。示。 (5) 然后從最后一級縮減信源開始，向前返回然后從最后一級縮減信源開始，向前返回(逆向逆向) ，就得出各信源符號所對應(yīng)的碼符號序列，即對應(yīng)的就得出各信源符號所對應(yīng)的碼符號序列，即對應(yīng)的碼字。碼字。22例例8.1: 對離散無記憶信源對離散無記憶信源 進(jìn)行霍夫曼編碼。進(jìn)行霍夫曼編碼。 解解:編碼過程如表所示，編碼過程如表所示， 1)將信源符號按概率大小由大至小排序。將信源符號按概率大小由大至小排序。 2)從概率最小的兩個信源符號和開始編碼，并按一從概率最小的兩個信源符號和開

17、始編碼，并按一定的規(guī)則賦予碼符號，如下面的信源符號（小概率）定的規(guī)則賦予碼符號，如下面的信源符號（小概率）為為“1”，上面的信源符號（大概率）為，上面的信源符號（大概率）為“0”。若兩。若兩支路概率相等，仍為下面的信源符號為支路概率相等，仍為下面的信源符號為“1” 上面的上面的信源符號為信源符號為“0”。 12345()0.40.20.20.10.1iSsssssp s 233)將已編碼兩個信源符號概率合并，重新排隊(duì)，編碼。將已編碼兩個信源符號概率合并，重新排隊(duì)，編碼。4)重復(fù)步驟重復(fù)步驟3）直至合并概率等于）直至合并概率等于“1.0”為止。為止。5)從概率等于從概率等于“1.0”端沿合并路線

18、逆行至對應(yīng)消息編碼。端沿合并路線逆行至對應(yīng)消息編碼。24碼的性能分析：碼的性能分析： 信源的熵為：信源的熵為： (比特符號比特符號) 可得平均碼長為：可得平均碼長為： 編碼效率為：編碼效率為：( )2.61H S 96.0)(LSH2 . 241 . 041 . 032 . 022 . 014 . 0)(51iiilspL2526按霍夫曼碼的編碼方法，可知這種碼有如下特征：按霍夫曼碼的編碼方法，可知這種碼有如下特征：它是一種分組碼：各個信源符號都被映射成一組它是一種分組碼：各個信源符號都被映射成一組固定次序的碼符號；固定次序的碼符號；它是一種惟一可解的碼：任何碼符號序列只能以它是一種惟一可解的

19、碼：任何碼符號序列只能以一種方式譯碼；一種方式譯碼；27它是一種即時碼：由于代表信源符號的節(jié)點(diǎn)都是它是一種即時碼：由于代表信源符號的節(jié)點(diǎn)都是終端節(jié)點(diǎn)，因此其編碼不可能是其它終端節(jié)點(diǎn)對終端節(jié)點(diǎn)，因此其編碼不可能是其它終端節(jié)點(diǎn)對應(yīng)的編碼的前綴，霍夫曼編碼所得的碼字一定是應(yīng)的編碼的前綴，霍夫曼編碼所得的碼字一定是即時碼。所以一串碼符號中的每個碼字都可不考即時碼。所以一串碼符號中的每個碼字都可不考慮其后的符號直接解碼出來。慮其后的符號直接解碼出來。 霍夫曼碼的譯碼霍夫曼碼的譯碼：對接收到的霍夫曼碼序列可通：對接收到的霍夫曼碼序列可通過從左到右檢查各個符號進(jìn)行譯碼。過從左到右檢查各個符號進(jìn)行譯碼。28說

20、明：說明： 霍夫曼碼是一種即時碼，可用碼樹形式來表示。霍夫曼碼是一種即時碼，可用碼樹形式來表示。 每次對縮減信源最后兩個概率最小的符號，用每次對縮減信源最后兩個概率最小的符號，用“0”和和“1”碼是可以任意的，所以可得到不同的碼，但碼碼是可以任意的，所以可得到不同的碼，但碼長不變，平均碼長也不變。長不變，平均碼長也不變。 當(dāng)縮減信源中縮減合并后得到的新符號的概率與其當(dāng)縮減信源中縮減合并后得到的新符號的概率與其他信源符號概率相同時，從編碼方法上來說，它們概他信源符號概率相同時，從編碼方法上來說，它們概率的排序是沒有限制的，因此也可得到不同的碼。率的排序是沒有限制的，因此也可得到不同的碼。即對給定

21、信源，用霍夫曼編碼方法得到的碼并非是惟即對給定信源，用霍夫曼編碼方法得到的碼并非是惟一，但平均碼長不變。一，但平均碼長不變。2930可得平均碼長為：可得平均碼長為：2 . 23) 1 . 01 . 0(2)2 . 02 . 04 . 0()(51iiilspL313233 從以上的編碼實(shí)例中可以看出，霍夫曼編碼具有從以上的編碼實(shí)例中可以看出，霍夫曼編碼具有以下特點(diǎn)：以下特點(diǎn)： (1)霍夫曼編碼方法保證了概率大的符號對應(yīng)于短碼，霍夫曼編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，充分利用了短碼；概率小的符號對應(yīng)于長碼，充分利用了短碼； (2)每次縮減信源的最后兩個碼字總是前面各位

22、碼元每次縮減信源的最后兩個碼字總是前面各位碼元相同、最后一位碼元不同，從而保證了霍夫曼碼是即相同、最后一位碼元不同，從而保證了霍夫曼碼是即時碼。時碼。 (3)每次縮減信源的最長兩個碼字有相同的碼長。每次縮減信源的最長兩個碼字有相同的碼長。 這三個特點(diǎn)保證了所得的霍夫曼編碼一定是最佳碼這三個特點(diǎn)保證了所得的霍夫曼編碼一定是最佳碼。34 霍夫曼編碼的效率相當(dāng)高，但是如果要達(dá)到很霍夫曼編碼的效率相當(dāng)高，但是如果要達(dá)到很高的編碼效率仍然需要引入較長的序列才能降低高的編碼效率仍然需要引入較長的序列才能降低平均碼字長度（碼字信息率）。平均碼字長度（碼字信息率）。358.1.2 r元霍夫曼碼元霍夫曼碼 對二

23、元霍夫曼碼的編碼方法同樣可以推廣到對二元霍夫曼碼的編碼方法同樣可以推廣到r元元編碼中。不同的只是每次把概率最小的個符號合并編碼中。不同的只是每次把概率最小的個符號合并成一個新的信源符號，并分別用成一個新的信源符號，并分別用0，1， r-1，等碼元表示。等碼元表示。 為了使短碼得到充分利用，使平均碼長為最短，為了使短碼得到充分利用，使平均碼長為最短，必須使最后一步的縮減信源有必須使最后一步的縮減信源有r個信源符號。個信源符號。36 因此對于因此對于r元編碼，信源元編碼，信源S的符號個數(shù)的符號個數(shù)q必須滿足：必須滿足： 其中，其中， 表示縮減的次數(shù)，表示縮減的次數(shù)，r-1為每次縮減所減少的信為每次

24、縮減所減少的信源符號個數(shù)。源符號個數(shù)。 對于二元碼（對于二元碼（r=2），信源符號個數(shù)），信源符號個數(shù)q必須滿足：必須滿足： 因此，因此，q可等于任意整正數(shù)時，總能找到一個可等于任意整正數(shù)時，總能找到一個 滿足滿足上式。上式。rrq) 1(2q37注意注意: 對于對于r元碼時，不一定能找到一個使式元碼時，不一定能找到一個使式 成立。在不滿足上式時，可假設(shè)一些信源符號：成立。在不滿足上式時，可假設(shè)一些信源符號： 作為虛擬的信源，并令它們對應(yīng)作為虛擬的信源，并令它們對應(yīng)的概率為零，即：的概率為零，即： 而使而使 能成立，這樣處理后得到能成立，這樣處理后得到的的r元霍夫曼碼可充分利用短碼，一定是緊致

25、碼。元霍夫曼碼可充分利用短碼，一定是緊致碼。rrq) 1(tqqqsss,.,210.21tqqqppprrtq) 1(38例例8.2 對信源進(jìn)行四元霍夫曼碼編碼。表列出了對信源進(jìn)行四元霍夫曼碼編碼。表列出了四元霍夫曼碼的編碼方法及其對應(yīng)的碼字。四元霍夫曼碼的編碼方法及其對應(yīng)的碼字。rrq) 1(rrtq) 1(39 從圖可知，當(dāng)信源從圖可知，當(dāng)信源符號個數(shù)符號個數(shù)q不滿足式不滿足式8.4時，所得的樹一定時，所得的樹一定是非整樹。是非整樹。 這種編碼方法是盡量把短碼都利用上。這種編碼方法是盡量把短碼都利用上。首先，把一階節(jié)點(diǎn)全都用上，如果碼字不夠首先，把一階節(jié)點(diǎn)全都用上，如果碼字不夠時，再從某

26、個節(jié)點(diǎn)伸出若干枝，引出二階節(jié)時，再從某個節(jié)點(diǎn)伸出若干枝，引出二階節(jié)點(diǎn)作為碼字。再不夠時，再伸出三階節(jié)點(diǎn)。點(diǎn)作為碼字。再不夠時，再伸出三階節(jié)點(diǎn)。 顯然，這樣得到的平均碼長最短。顯然，這樣得到的平均碼長最短。408.1.3 霍夫曼碼的最佳性霍夫曼碼的最佳性41428.2 費(fèi)諾碼費(fèi)諾碼 費(fèi)諾編碼屬于概率匹配編碼。它不是最佳的費(fèi)諾編碼屬于概率匹配編碼。它不是最佳的編碼方法，只有當(dāng)信源的概率分布呈現(xiàn)編碼方法，只有當(dāng)信源的概率分布呈現(xiàn) 分布形式的條件下，才能達(dá)到最佳碼的性能。分布形式的條件下，才能達(dá)到最佳碼的性能。( )ilip sr 43 二元費(fèi)諾碼的編碼步驟如下：二元費(fèi)諾碼的編碼步驟如下： 1）信源符

27、號以概率遞減的次序排列起來；信源符號以概率遞減的次序排列起來； 2）將排列好的信源符號按概率值劃分成兩大組，使每將排列好的信源符號按概率值劃分成兩大組，使每組的概率之和接近于相等，并對每組各賦予一個二元碼組的概率之和接近于相等，并對每組各賦予一個二元碼符號符號“0”和和“1”； 3）將每一大組的信源符號再分成兩組，使劃分后的兩將每一大組的信源符號再分成兩組，使劃分后的兩個組的概率之和接近于相等，再分別賦予一個二元碼符個組的概率之和接近于相等，再分別賦予一個二元碼符號；號； 4）依次下去，直至每個小組只剩一個信源符號為止；依次下去，直至每個小組只剩一個信源符號為止； 5）信源符號所對應(yīng)的碼字即為

28、費(fèi)諾碼。信源符號所對應(yīng)的碼字即為費(fèi)諾碼。44 例例8.3 離散無記憶信源離散無記憶信源S， 這種碼是緊致碼，碼的效率等于這種碼是緊致碼，碼的效率等于1。之所。之所以能達(dá)到最佳，是因?yàn)樾旁捶柕母怕史植家阅苓_(dá)到最佳，是因?yàn)樾旁捶柕母怕史植颊脻M足式正好滿足式(5.70)45 例例8.4 離散無記憶信源離散無記憶信源S， 信源的熵為信源的熵為2.35比特比特/信源符號，碼的平信源符號，碼的平均碼長為均碼長為2.32，因此效率為，因此效率為0.987。46 費(fèi)諾碼具有如下的性質(zhì)：費(fèi)諾碼具有如下的性質(zhì)： 費(fèi)諾碼的編碼方法實(shí)際上是一種構(gòu)造碼樹的方費(fèi)諾碼的編碼方法實(shí)際上是一種構(gòu)造碼樹的方法，所以費(fèi)諾碼是

29、即時碼。法，所以費(fèi)諾碼是即時碼。 費(fèi)諾碼考慮了信源的統(tǒng)計(jì)特性，使概率大的信費(fèi)諾碼考慮了信源的統(tǒng)計(jì)特性，使概率大的信源符號能對應(yīng)碼長較短的碼字，從而有效地提高源符號能對應(yīng)碼長較短的碼字，從而有效地提高了編碼效率。了編碼效率。 47 費(fèi)諾碼不一定是最佳碼。因?yàn)橘M(fèi)諾碼編碼方法費(fèi)諾碼不一定是最佳碼。因?yàn)橘M(fèi)諾碼編碼方法不一定能使短碼得到充分利用不一定能使短碼得到充分利用:當(dāng)信源符號較多時，當(dāng)信源符號較多時，若有一些符號概率分布很接近時，分兩大組的組若有一些符號概率分布很接近時，分兩大組的組合方法就會很多?？赡苣撤N分大組的結(jié)果，會使合方法就會很多?？赡苣撤N分大組的結(jié)果，會使后面小組的后面小組的“概率和概率和”相差較遠(yuǎn)，從而使平均碼相差較遠(yuǎn)，從而使平均碼長增加。長增加。 r 元費(fèi)諾碼元費(fèi)諾碼 前面討論的費(fèi)諾碼是二元費(fèi)諾碼，對前面討論的費(fèi)諾碼是二元費(fèi)諾碼，對r元費(fèi)諾碼，元費(fèi)諾碼，與二元費(fèi)諾碼編碼方法相同，只是每次分組時應(yīng)與二元費(fèi)諾碼編碼方法相