第五章_信源編碼

1、1第五章信源編碼5.1.1 碼字唯一可譯的條件碼字唯一可譯的條件5.1.2 香農(nóng)編碼香農(nóng)編碼5.1.3 費諾編碼費諾編碼5.1.4 赫夫曼編碼赫夫曼編碼5.1.5 游游程程編碼編碼5.1.6 冗余位編碼冗余位編碼2信源編碼概述編碼是為了優(yōu)化通信系統(tǒng)，一般的通信系統(tǒng)的主要性編碼是為了優(yōu)化通信系統(tǒng)，一般的通信系統(tǒng)的主要性能指標(biāo)：有效性、可靠性和安全性能指標(biāo)：有效性、可靠性和安全性信源編碼的目的：提高通信系統(tǒng)的有效性，通常通過信源編碼的目的：提高通信系統(tǒng)的有效性，通常通過壓縮信源的冗余度來實現(xiàn)，即壓縮每個信源符號的信壓縮信源的冗余度來實現(xiàn)，即壓縮每個信源符號的信息量，使得同樣多的信息用較少的信息傳輸

2、率來傳送息量，使得同樣多的信息用較少的信息傳輸率來傳送信源編碼的思路：根據(jù)信源輸出符號序列的統(tǒng)計特性，信源編碼的思路：根據(jù)信源輸出符號序列的統(tǒng)計特性，尋找一定的把信源輸出符號序列變換為最短碼字序列尋找一定的把信源輸出符號序列變換為最短碼字序列的方法的方法信源編碼的基本途徑：使編碼后的符號序列中的各個信源編碼的基本途徑：使編碼后的符號序列中的各個符號盡可能地相互獨立，即解除相關(guān)性；使編碼后各符號盡可能地相互獨立，即解除相關(guān)性；使編碼后各個符號出現(xiàn)的概率盡可能的相等，即概率均勻化。個符號出現(xiàn)的概率盡可能的相等，即概率均勻化。信源編碼的基礎(chǔ)：無失真編碼定理和限失真編碼定理信源編碼的基礎(chǔ)：無失真編碼定

3、理和限失真編碼定理35.1 離散信源 5.1.1 碼字唯一可譯的條件碼的分類碼的分類 定定長長碼碼碼碼變變長長碼碼 奇奇異異碼碼非非唯唯一一可可譯譯碼碼碼碼非非奇奇異異碼碼非非即即時時碼碼唯唯一一可可譯譯碼碼即即時時碼碼按碼長分類按碼長分類定長碼：碼中所有碼字的碼長都相等定長碼：碼中所有碼字的碼長都相等奇異碼：碼中存在有相同的碼字奇異碼：碼中存在有相同的碼字( (對應(yīng)不同的信源符號對應(yīng)不同的信源符號) )唯一可譯碼：由碼的碼字組成任意有限長的碼字序列只能被唯一可譯碼：由碼的碼字組成任意有限長的碼字序列只能被唯一地譯為對應(yīng)的信源符號序列唯一地譯為對應(yīng)的信源符號序列即時碼：譯碼器收到一個完整的唯一

4、可譯碼字以后，無需參即時碼：譯碼器收到一個完整的唯一可譯碼字以后，無需參考后續(xù)的碼字考后續(xù)的碼字( (碼元碼元) )就能立即譯碼就能立即譯碼定長碼定長碼非奇異碼非奇異碼&唯一可譯碼唯一可譯碼45.1.1 碼字唯一可譯的條件1001001碼碼 C11100100碼碼 B11100000碼碼 A50.50概概 率率信信 源源碼碼 F碼碼 E碼碼 D00110011011001110011111110001x2x3x4x碼碼 A：奇異碼、定長碼、非唯一可譯碼：奇異碼、定長碼、非唯一可譯碼碼碼 B：非奇異碼、定長碼、唯一可譯碼：非奇異碼、定長碼、唯一可譯碼碼碼 C：非奇異

5、碼、非唯一可譯碼：非奇異碼、非唯一可譯碼碼碼 D：唯一可譯碼：唯一可譯碼碼碼 E：非即時碼：非即時碼碼碼 F：即時碼：即時碼1423112211, 10, 00, 0111000011, 1, 00, 00, 1x x x xx x x x x 01010001 已已譯譯碼碼2301xx 即時碼中即時碼中任何一個任何一個碼字均不碼字均不是其它碼是其它碼字的前綴字的前綴變長碼變長碼即時碼即時碼&唯一可譯碼唯一可譯碼5定義：如果一個碼組中的任一個碼字都不是另一個碼字的延定義：如果一個碼組中的任一個碼字都不是另一個碼字的延長或者找不到任何一個碼字是另一個碼字的前綴，或者說，長或者找不到任何一

6、個碼字是另一個碼字的前綴，或者說，任何一個碼字后加上若干碼元后都不是碼組中另一個碼字，任何一個碼字后加上若干碼元后都不是碼組中另一個碼字，則稱為則稱為即時碼或非延長碼即時碼或非延長碼。也叫前綴條件碼。也叫前綴條件碼/ /異前置碼異前置碼/ /異字異字頭碼頭碼/ /逗點碼逗點碼所有的碼所有的碼非奇異碼非奇異碼唯一可譯碼唯一可譯碼即時碼即時碼5.1.1 碼字唯一可譯的條件65.1.1 碼字唯一可譯的條件用樹圖法可以方便地構(gòu)造即時碼。從樹根開始，樹中每個中間用樹圖法可以方便地構(gòu)造即時碼。從樹根開始，樹中每個中間節(jié)點都伸出節(jié)點都伸出 1 至至 r 個樹枝，不同的樹枝標(biāo)記不同的碼元。個樹枝，不同的樹枝標(biāo)

7、記不同的碼元。將所有的碼字都安排在將所有的碼字都安排在終端節(jié)點上就可以得到即時碼上就可以得到即時碼每個中間節(jié)點都正好有每個中間節(jié)點都正好有 r 個分枝的樹稱為整樹個分枝的樹稱為整樹( (滿樹滿樹) )所有終端節(jié)點的階數(shù)都相等的樹為完全樹，對應(yīng)于定長碼所有終端節(jié)點的階數(shù)都相等的樹為完全樹，對應(yīng)于定長碼2r 75.1.1 碼字唯一可譯的條件二元滿樹二元滿樹二元非滿樹二元非滿樹三元非滿樹三元非滿樹三元滿樹三元滿樹8唯一可譯定長碼存在的條件對于定長碼，非奇異碼一定是唯一可譯碼對于定長碼，非奇異碼一定是唯一可譯碼lnr logloglnNr Nlnr loglognlr 1212, ,nrXx xxnC

8、c ccl 單單符符號號離離散散信信源源信信源源符符號號集集中中共共有有個個符符號號碼碼元元集集定定長長碼碼碼碼長長為為12(,)NNNXXXn X次次擴(kuò)擴(kuò)展展得得到到的的多多符符號號離離散散信信源源信信源源符符號號集集共共有有個個符符號號注意注意：上述條件是：上述條件是，而而非充分條件非充分條件平均每個單信平均每個單信源符號所需要源符號所需要碼元的個數(shù)碼元的個數(shù)9maxmax()jijijjllllljilll 此此外外，對對應(yīng)應(yīng)于于碼碼長長的的階階節(jié)節(jié)點點，它它不不能能是是的的祖祖先先節(jié)節(jié)點點或或子子孫孫節(jié)節(jié)點點， 因因此此由由延延伸伸到到階階的的終終端端節(jié)節(jié)點點必必與與延延伸伸到到階階的

9、的終終端端節(jié)節(jié)點點不不同同；克拉夫特(Kraft)不等式12121,1innlninrY YYrl ll 對對符符號號數(shù)數(shù)為為的的信信源源進(jìn)進(jìn)行行進(jìn)進(jìn)制制變變長長編編碼碼，其其碼碼字字為為，相相應(yīng)應(yīng)的的碼碼長長分分別別為為，若若編編碼碼是是即即時時碼碼，必必有有：反反之之，若若碼碼長長滿滿足足上上述述不不等等式式，則則一一定定存存在在具具有有這這樣樣碼碼長長的的即即時時碼碼maxmaxmax12maxmax ,iinliilllll llrlrlllr ：記記，則則可可構(gòu)構(gòu)造造一一個個 元元階階滿滿樹樹其其終終端端節(jié)節(jié)點點數(shù)數(shù)為為。 即即時時碼碼中中碼碼長長為為 的的碼碼字字安安排排于于碼碼樹

10、樹的的第第 階階中中的的某某個個節(jié)節(jié)點點，由由即即時時碼碼的的條條件件可可知知，以以此此節(jié)節(jié)點點延延伸伸樹樹枝枝至至階階的的終終端端節(jié)節(jié)點點數(shù)數(shù)有有，它它們們不不能能安安排排碼碼字字。證證maxlr maxmax1illnilr 所所有有延延伸伸至至階階的的終終端端節(jié)節(jié)點點數(shù)數(shù)為為：KraftKraft？是是即即時時碼碼不不等等式式成成立立不不等等式式成成立立是是即即時時碼碼Kraft唯唯一一可可譯譯碼碼也也滿滿足足不不等等式式，且且任任何何唯唯一一可可譯譯碼碼可可用用具具有有相相同同碼碼長長的的某某個個即即時時碼碼替替代代反反向向如如何何證證明明？10唯一可譯碼判別準(zhǔn)則01210jiij11

11、0n-01-01n 1SS ,SSSWWW =W AASSAS ,1,WSSUS,SUSWSW=UASnnnnUWA為原始碼字的集合。再構(gòu)造一系列集合。為得到集合，首先考察中所有的碼字。若碼字是碼字的前綴，即，則將其后綴列為中的元素，就是由所有具有這種性質(zhì)的構(gòu)成的集合。一般地則將比較。如有碼字，且W是的前綴，即則取后綴為中的元素。同樣，如有碼字是的前綴，即與，120S ,SASSSnn一種碼是唯一可譯碼的充要條則也是中的元素。如此便可件是： 中沒有一個構(gòu)成集合。則有下面命含有中題:的碼字。11唯一可譯碼判別準(zhǔn)則舉例設(shè)信源消息集合設(shè)信源消息集合x1,x2, x3,x4, x5,x6,x7，它們分

12、別被編碼，它們分別被編碼為為a,c,ad,abb, bad,deb,bbcde，可構(gòu)造出下表所示的，可構(gòu)造出下表所示的嗎符號集序列嗎符號集序列S0S1S2S3S4S5S6S7adebdebaddebcbbcdebcdeadabbbaddebbbcde當(dāng)n7時，sn是空集，而s5都包含s0中的元素，因此不是唯一可譯碼125.1.2香農(nóng)編碼香農(nóng)編碼是采用信源符號的累計概率分布函數(shù)來分配碼字的香農(nóng)編碼是采用信源符號的累計概率分布函數(shù)來分配碼字的設(shè)某離散無記憶信源設(shè)某離散無記憶信源 2 進(jìn)制香農(nóng)編碼步驟：進(jìn)制香農(nóng)編碼步驟：1212()()()()nnxxxXP Xp xp xp x 將信源符號以概率遞

13、減的次序排列起來，為方便起見，令：將信源符號以概率遞減的次序排列起來，為方便起見，令：12()()()np xp xp x 按下式求按下式求 x i 對應(yīng)碼字的碼長對應(yīng)碼字的碼長 l i ：log()log()1iiip xlp x 按下式逐步求信源符號按下式逐步求信源符號 x i 的概率累加和的概率累加和 P i ：1110,()2,3,iikkPPp xin 將所有的累加和概率將所有的累加和概率 P i 變換成變換成 2 進(jìn)制數(shù)；取小數(shù)點后進(jìn)制數(shù)；取小數(shù)點后 P i 位作位作為信源符號為信源符號 x i 的的 2 進(jìn)制碼字進(jìn)制碼字()iilI x 13編碼所得的碼字，沒有相同的，所以是非奇

14、異碼，也沒有一編碼所得的碼字，沒有相同的，所以是非奇異碼，也沒有一個碼字是其它碼字的前綴，所以是即時碼。個碼字是其它碼字的前綴，所以是即時碼。香農(nóng)碼的效率不高，其冗余度較大，不是最佳碼，香農(nóng)碼的效率不高，其冗余度較大，不是最佳碼，實用性受實用性受到較大限制到較大限制xip ( xi )Pi loglog p ( xi )li碼字x10.3701.434200 x20.160.372.6443010 x30.140.582.8373100 x40.130.672.9433101x50.070.803.83741100 x60.060.874.059511011x70.040.934.644511

15、101x80.030.975.059611111081()2.99 /iiilp x l ：碼碼元元 符符號號平均碼長81()()log ()2.583bi /iiiH Xp xp xt ：符符號號信源熵()2.58386.4%log2.99H Xlr 編碼效率：12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 14例：有一單符號離散無記憶信源例：有一單符號離散無記憶信源123456,()05XxxxxxxP X練習(xí)練習(xí)二進(jìn)制香農(nóng)編碼二進(jìn)制香農(nóng)編碼 xi p(xi) pa(xj

16、) ki 碼字碼字 x1 0.25 0.000 2 00(0.000)2 x2 0.25 0.250 2 01(0.010)2 x3 0.20 0.500 3 100(0.100)2 x4 0.15 0.700 3 101(0.101)2 x5 0.10 0.850 4 1101(0.1101)2 x6 0.05 0.950 5 11110(0.11110)2 對該信源編二進(jìn)制香農(nóng)碼。其編碼過程如下表所示。對該信源編二進(jìn)制香農(nóng)碼。其編碼過程如下表所示。155.1.3費諾編碼費諾編碼又稱為子集分解法，通過將信源符號的概率分組，費諾編碼又稱為子集分解法，通過將信源符號的概率分組，對每個組分配相應(yīng)的

17、碼元來實現(xiàn)編碼，其編碼步驟如下：對每個組分配相應(yīng)的碼元來實現(xiàn)編碼，其編碼步驟如下：將信源符號以概率遞減的次序排列起來，為方便起見，令將信源符號以概率遞減的次序排列起來，為方便起見，令:12()()()np xp xp x 將依次排列的信源符號按概率分成將依次排列的信源符號按概率分成 r 組，使每個組的信源符組，使每個組的信源符號的概率和盡可能接近或相等，然后賦予每組一個號的概率和盡可能接近或相等，然后賦予每組一個 r 元碼符元碼符號；例如編號；例如編 2 進(jìn)制費諾碼，則每次分組均分成兩組，每個組進(jìn)制費諾碼，則每次分組均分成兩組，每個組分別賦予一個分別賦予一個 2 元碼元碼符號符號“0”或或“1

18、”將每一大組的信源符號按概率和遞減的次序再分成將每一大組的信源符號按概率和遞減的次序再分成 r 組，使組，使同一大組細(xì)分的同一大組細(xì)分的 r 個小組的信源符號的概率和盡可能接近或個小組的信源符號的概率和盡可能接近或相等，并分別賦予每小組一個相等，并分別賦予每小組一個 r 元碼符號；元碼符號；重復(fù)上述的分組，分配重復(fù)上述的分組，分配 r 元碼符號的過程，直至最個分得的元碼符號的過程，直至最個分得的每個小組只剩一個信源符號為止，最后每個信源符號所對應(yīng)每個小組只剩一個信源符號為止，最后每個信源符號所對應(yīng)的碼元序列就是相應(yīng)的碼字的碼元序列就是相應(yīng)的碼字16xip ( xi )費諾編碼碼字lix10.3

19、700002x20.161012x30.141001003x40.1311013x50.0710011004x60.06111014x70.041011104x80.0311111481()2.67 /iiilp x l ：碼碼元元 符符號號平均碼長()2.583bi /H Xt 信源熵：符符號號2.58396.7%2.67 編碼效率：香香農(nóng)農(nóng)碼碼：2.99 /碼碼元元 符符號號86.4%12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 17費諾編碼的碼樹圖費諾編碼的碼樹圖實質(zhì)上是一種構(gòu)造碼實質(zhì)上是一種構(gòu)造碼樹的方法，所

20、以費諾樹的方法，所以費諾碼是即時碼碼是即時碼概率大，則分解的次概率大，則分解的次數(shù)??；概率小數(shù)??；概率小, 則分則分解的次數(shù)多解的次數(shù)多碼字集合是唯一的碼字集合是唯一的分解完后，碼字與碼分解完后，碼字與碼長便確定了長便確定了費諾碼考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)費諾碼考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)短碼字，但是不一定能使短碼得到充分利用，尤其當(dāng)信源符短碼字，但是不一定能使短碼得到充分利用，尤其當(dāng)信源符號較多時，若有一些符號概率分布很接近時，分兩大組的組號較多時，若有一些符號概率分布很接近時，分兩大組的組合方法就會很多?？赡苣撤N分大組的結(jié)果，會使后面小組的合方法就會很

21、多?？赡苣撤N分大組的結(jié)果，會使后面小組的“概率和概率和”相差較遠(yuǎn)，從而使平均碼長增加。相差較遠(yuǎn)，從而使平均碼長增加。費諾編碼特點費諾編碼特點12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 18xip ( xi )費諾編碼碼字lix10.2500002x20.251012x30.1251001003x40.12511013x50.062510011004x60.0625111014x70.06251011104x80.06251111141234567811111111()448816161616xxxxxxxxXP X

22、 ()2.75bi /H Xt 信源熵：符符號號1114816222344l 平均碼長：2.752.75100% 編碼效率：費諾碼適合于每次分組概率費諾碼適合于每次分組概率都很接近的信源。特別是對都很接近的信源。特別是對每次分組概率都相等的信源每次分組概率都相等的信源進(jìn)行編碼時，可達(dá)到理想的進(jìn)行編碼時，可達(dá)到理想的編碼效率編碼效率費諾碼考慮了信源的統(tǒng)計特性，使概率大的信源符號能對應(yīng)碼費諾碼考慮了信源的統(tǒng)計特性，使概率大的信源符號能對應(yīng)碼長短的碼字，從而有效地提高了編碼效率長短的碼字，從而有效地提高了編碼效率。一般而言，費諾編碼不是最佳編碼，它的編碼效率一般而言，費諾編碼不是最佳編碼，它的編碼效

23、率( (優(yōu)于香農(nóng)碼優(yōu)于香農(nóng)碼) )要比赫夫曼編碼效率稍低要比赫夫曼編碼效率稍低2.75 / 碼碼元元 符符號號19例：設(shè)有一單符號離散信源 對該信源編二進(jìn)制費諾碼。123456,()0.360.080.04XxxxxxxP X練習(xí)練習(xí)205.1.4赫夫曼編碼赫夫曼編碼是一種最佳的逐個符號的編碼方法，所得的碼是即赫夫曼編碼是一種最佳的逐個符號的編碼方法，所得的碼是即時碼，其平均碼長最短，因而是最佳編碼時碼，其平均碼長最短，因而是最佳編碼2 進(jìn)制赫夫曼編碼的步驟如下：進(jìn)制赫夫曼編碼的步驟如下：將信源符號以概率遞減的次序排列起來，為方便起見，令將信源符號以概率遞減的次序排列起

24、來，為方便起見，令:12()()()np xp xp x 將兩個概率最小的信源符號將兩個概率最小的信源符號 x n 1, x n 各分配一個碼元各分配一個碼元“0”和和“1”，并將這兩個符號合并成一個新符號，合并后新符號，并將這兩個符號合并成一個新符號，合并后新符號概率為原來兩個符號概率之和，從而得到包含概率為原來兩個符號概率之和，從而得到包含 n 1 個符號個符號的縮減信源的縮減信源 S1 把縮減信源把縮減信源 S1 的符號仍按概率遞減次序排列，重復(fù)步驟的符號仍按概率遞減次序排列，重復(fù)步驟 2 得得到只含有到只含有 n 2 個信源符號的縮減信源個信源符號的縮減信源 S2 重復(fù)上述步驟，直至縮

25、減信源只剩重復(fù)上述步驟，直至縮減信源只剩 1 個信源符號為止；然后個信源符號為止；然后從最后一級縮減信源開始，依編碼路徑向前返回，就得到各從最后一級縮減信源開始，依編碼路徑向前返回，就得到各信源符號所對應(yīng)的碼元序列，即對應(yīng)的碼字信源符號所對應(yīng)的碼元序列，即對應(yīng)的碼字21xip(xi)縮減信源碼字liS1S2S3S4S5S6S7x10.37x20.16x30.14x40.13x50.07x60.06x70.04x80.030.0701070.360.631.00101010101000110001001110110000001000115544433112345678()

26、0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 22赫夫曼編碼的碼樹赫夫曼編碼的碼樹12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X ()2.583 bi /H Xt 符符號號81()2.66 /iiilp x l ：碼碼元元 符符號號平均碼長2.5832.6697.1% ：編碼效率2.99 /香香農(nóng)農(nóng)碼碼：碼碼元元 符符號號2.67 /費費諾諾碼碼：碼碼元元 符符號號86.4%香香農(nóng)農(nóng)碼碼：96.7%費費諾諾碼碼：赫夫曼編碼的特點赫夫曼編碼的特點概率大的符號安排在

27、離概率大的符號安排在離根節(jié)點較近的終端節(jié)點根節(jié)點較近的終端節(jié)點保證了概率大的符號對保證了概率大的符號對應(yīng)于短碼，概率小的符應(yīng)于短碼，概率小的符號對應(yīng)于長碼號對應(yīng)于長碼每次縮減信源的最長兩每次縮減信源的最長兩個碼字具有相同碼長個碼字具有相同碼長每次縮減信源的最后兩每次縮減信源的最后兩個碼字總是最后一位碼個碼字總是最后一位碼元不同，前面各位碼元元不同，前面各位碼元相同相同( (2 元碼情況元碼情況) )編碼不具有惟一性編碼不具有惟一性赫夫曼編碼是最佳碼赫夫曼編碼是最佳碼23方差越小，各碼字長度方差越小，各碼字長度就越接近平均碼長，設(shè)就越接近平均碼長，設(shè)計的編碼器也就越簡單計的編碼器也就越簡單赫夫曼

28、編碼的非唯一性每次對縮減信源兩個概率最小的符號分配每次對縮減信源兩個概率最小的符號分配“0”或或“1”碼元碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字，即能得到可分離碼字不同的碼元分配，得到的具體碼字不同，但碼長不同的碼元分配，得到的具體碼字不同，但碼長 li 不變，平均不變，平均碼長也不變，所以沒有本質(zhì)區(qū)別碼長也不變，所以沒有本質(zhì)區(qū)別縮減信源時，若合并后新符號的概率與其它符號概率相等，縮減信源時，若合并后新符號的概率與其它符號概率相等，從編碼方法上來說，這幾個符號的次序可任意排列，編出的從

29、編碼方法上來說，這幾個符號的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長度字長度 li 也不盡相同，但平均碼長仍不變也不盡相同，但平均碼長仍不變對同一信源的多種赫夫曼編碼，除了用平均碼長來衡量外，對同一信源的多種赫夫曼編碼，除了用平均碼長來衡量外，當(dāng)平均碼長相同時，可以碼長當(dāng)平均碼長相同時，可以碼長 li 偏離平均碼長的方差來判斷：偏離平均碼長的方差來判斷：22() iE ll 22() ( )iiE lE l 21()()niiillp x 22()iE ll 24xip(xi)編碼過程碼字lix10.37

30、x20.16x30.14x40.13x50.07x60.06x70.04x80.030.070.370.160.1 0.130.070.060.130.330.070.200.330.270.360.370.270.630.370101010101011.00011001010000001110110000100001113344455方案一12345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 25xip(xi)縮碼過程碼字lix10.37x20.16x

31、30.14x40.13x50.07x60.06x70.04x80.030.030.270.360.370.270.630.370101010101011.000110010100110000100010000000000011333546612345678()0.37 0.16 0.14 0.13 0.07 0.06 0.04 0.03xxxxxxxxXP X 0.070.370.160.1 0.130.060.130.37方案二26赫夫曼編碼的非唯一性（續(xù)）xip(xi)碼長 li方案一方案二x1

32、0.3711x20.1633x30.1433x40.1343x50.0744x60.0645x70.0456x80.0356平均碼長2.66 /碼碼元元 符符號號20.37 1(3)30.0740.065(0.040.03) 62.66 /l 碼碼元元 符符號號222122()0.37 1(0.160.14) 3(0.130.070.06) 4(0.040.03) 58.98iE l 2229.382.662.304 2222222()0.37 1(3)30.0740.06 5(0.040.03) 69.38iE l 2218.982.661.904

33、 方案一較好，其方案一較好，其碼長變化較小碼長變化較小在赫夫曼編碼過程中，當(dāng)縮減信源符號按概率大小，以遞減次序自上而下在赫夫曼編碼過程中，當(dāng)縮減信源符號按概率大小，以遞減次序自上而下重新排列時，應(yīng)把合并后的新符號重新排列時，應(yīng)把合并后的新符號盡量置于縮減信源中具有相同概率的其它符號之上，減少合并后的新符號被重復(fù)賦予碼元的次數(shù)，進(jìn)而減小碼字，減少合并后的新符號被重復(fù)賦予碼元的次數(shù)，進(jìn)而減小碼字長度相對于平均碼長的擺動長度相對于平均碼長的擺動上述方法不會引起平均碼長的變化，可以使短碼得到充分利用上述方法不會引起平均碼長的變化，可以使短碼得到充分利用27r 進(jìn)制赫夫曼編碼r 進(jìn)制赫夫曼編碼是進(jìn)制赫夫

34、曼編碼是 2 進(jìn)制編碼的推廣；求縮減信源時需要求進(jìn)制編碼的推廣；求縮減信源時需要求 r 個信源符號使其概率和最小，并對個信源符號使其概率和最小，并對 r 個信源符號分別分配碼元個信源符號分別分配碼元0,1, r 1，然后將它們縮減為一個新符號，重復(fù)上述縮減和，然后將它們縮減為一個新符號，重復(fù)上述縮減和分配碼元的步驟直至縮減信源中只剩下一個符號為止分配碼元的步驟直至縮減信源中只剩下一個符號為止 r 進(jìn)制霍夫曼編碼，如果從一始就每進(jìn)制霍夫曼編碼，如果從一始就每 r 個符號縮減為一個新符個符號縮減為一個新符號，則縮減到最后時剩下的信源符號可能不到號，則縮減到最后時剩下的信源符號可能不到 r 個，為了

35、使平個，為了使平均碼長最短，必須使最后一步縮減信源有均碼長最短，必須使最后一步縮減信源有 r 個信源符號個信源符號全樹全樹非全樹非全樹碼樹圖中至少有一個中間節(jié)碼樹圖中至少有一個中間節(jié)點的后續(xù)枝數(shù)不足點的后續(xù)枝數(shù)不足 r碼樹圖中每個中間節(jié)碼樹圖中每個中間節(jié)點后續(xù)枝數(shù)為點后續(xù)枝數(shù)為 r2 進(jìn)制碼不進(jìn)制碼不存在非全樹存在非全樹的情況，因的情況，因為后續(xù)枝數(shù)為后續(xù)枝數(shù)是是 1 時，這時，這個枝就可以個枝就可以去掉使碼字去掉使碼字長 度 縮 短長 度 縮 短28r 進(jìn)制赫夫曼編碼(續(xù))對對 r 進(jìn)制編碼，若所有碼字構(gòu)成全樹，可分離的碼字?jǐn)?shù)必為：進(jìn)制編碼，若所有碼字構(gòu)成全樹，可分離的碼字?jǐn)?shù)必為：k 為信源

36、縮減次數(shù)為信源縮減次數(shù) 1(1)rk r 若信源所含的符號數(shù)若信源所含的符號數(shù) n 不能構(gòu)成不能構(gòu)成 r 進(jìn)制全樹，必須增加進(jìn)制全樹，必須增加 s 個不個不用的碼字形成全樹，且用的碼字形成全樹，且 s r 1若若 s r 1，意味著某個中間節(jié)點之后只有一個分枝，為了，意味著某個中間節(jié)點之后只有一個分枝，為了節(jié)約碼長，這一分枝可以省略節(jié)約碼長，這一分枝可以省略為了使平均碼長最短，當(dāng)碼樹為非全樹時，有為了使平均碼長最短，當(dāng)碼樹為非全樹時，有 s 個碼字不用：個碼字不用：第一次對最小概率和的符號分配碼元時只取第一次對最小概率和的符號分配碼元時只取 r s 個，分別賦個，分別賦予碼元予碼元 0,1,

37、r s 1，把這些符號的概率相加作為一個新符，把這些符號的概率相加作為一個新符號的概率，與其它符號一起重新排列號的概率，與其它符號一起重新排列 以后每次就可以取以后每次就可以取 r 個符號，分別賦予碼元個符號，分別賦予碼元 0,1, r 1；如；如此下去直至縮減至此下去直至縮減至 1 個信源符號，得到各符號的個信源符號，得到各符號的 r 進(jìn)制碼字進(jìn)制碼字29可見，要發(fā)揮赫夫曼編碼的優(yōu)勢，一般情況下，信源符號集的符可見，要發(fā)揮赫夫曼編碼的優(yōu)勢，一般情況下，信源符號集的符號數(shù)應(yīng)遠(yuǎn)大于碼元數(shù)號數(shù)應(yīng)遠(yuǎn)大于碼元數(shù)8n 信信源源符符號號數(shù)數(shù)：xip(xi)3 進(jìn)制赫夫曼縮碼過程碼字 lix10.37x20

38、.16x30.14x40.13x50.07x60.06x70.04x80.030.43xip(xi) 4 進(jìn)制赫夫曼縮碼過程 碼字 lix10.37x20.16x30.14x40.13x50.07x60.06x70.04x80.030.070.201.0021100012220120002212223320.070.331.00120231311111010211123320.370.160.1 0.070.060.130.340.370.200.370.160.1 0.070.060.130.370.160.140132103210210210102103, 3(31

39、)8,rks 4, 4(41)8,rks 25,ks1,3,sk 2rs34ks ，2,2,sk2rs()2.583 bi /H Xt 符符號號81()1.7 /iiilp x l ：三三元元碼碼元元 符符號號平均碼長2.58395.9%1.7log3 ：編碼效率81()1.4 /iiilp x l ：四四元元碼碼元元 符符號號平均碼長2.58392.3%1.4log4 ：編碼效率30練習(xí)練習(xí)設(shè)單符號離散無記憶信源如下，要求對信源編二進(jìn)設(shè)單符號離散無記憶信源如下，要求對信源編二進(jìn)制霍夫曼碼。制霍夫曼碼。12345678,( )0.4 0.18 0.1 0.1 0.07 0.06 0.05 0.

40、04XxxxxxxxxP Xn在圖中讀取碼字的時候，一定要從后向前讀，此時編出來的碼字才是可分離的異前置碼。若從前向后讀取碼字，則碼字不可分離。31香農(nóng)碼、費諾碼和赫夫曼碼總結(jié)香農(nóng)碼、費諾碼、赫夫曼碼都考慮了信源的統(tǒng)計特性，香農(nóng)碼、費諾碼、赫夫曼碼都考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平使經(jīng)常出現(xiàn)的信源符號對應(yīng)較短的碼字，使信源的平均碼長縮短，從而實現(xiàn)了對信源的壓縮。均碼長縮短，從而實現(xiàn)了對信源的壓縮。香農(nóng)碼編碼結(jié)果唯一，但在很多情況下編碼效率不是香農(nóng)碼編碼結(jié)果唯一，但在很多情況下編碼效率不是很高很高費諾碼和赫夫曼碼的編碼方法都不唯一費諾碼和赫夫曼碼的編碼方法都不

41、唯一費諾碼比較適合于對分組概率相等或接近的信源編碼費諾碼比較適合于對分組概率相等或接近的信源編碼赫夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率赫夫曼碼對信源的統(tǒng)計特性沒有特殊要求，編碼效率比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性比較高，對編碼設(shè)備的要求也比較簡單，因此綜合性能優(yōu)于香農(nóng)碼和費諾碼能優(yōu)于香農(nóng)碼和費諾碼赫夫曼碼通常適用于多元信源，對于二元信源，必須赫夫曼碼通常適用于多元信源，對于二元信源，必須采用合并符號的方法，才能得到較高的編碼效率采用合并符號的方法，才能得到較高的編碼效率325.1.5 游程編碼概述香農(nóng)碼、費諾碼、赫夫曼碼主要是針對無記憶信源；當(dāng)信源香農(nóng)碼、費諾碼、赫夫曼碼

42、主要是針對無記憶信源；當(dāng)信源有記憶時上述編碼的效率不高有記憶時上述編碼的效率不高游程編游程編碼是一種對相關(guān)信源較為有效的擴(kuò)展符號集的編碼方碼是一種對相關(guān)信源較為有效的擴(kuò)展符號集的編碼方法，是赫夫曼編碼的改進(jìn)和應(yīng)用，主要用于只有黑、白二值法，是赫夫曼編碼的改進(jìn)和應(yīng)用，主要用于只有黑、白二值灰度的文灰度的文件傳真，如文件、報紙、表格、手寫體字、圖紙等件傳真，如文件、報紙、表格、手寫體字、圖紙等文件傳真是把一頁文件掃描為文件傳真是把一頁文件掃描為 n m 個像素。由于黑、白個像素。由于黑、白二值文件只有兩個灰度值，因此采用二值文件只有兩個灰度值，因此采用 2 進(jìn)制編碼。進(jìn)制編碼。如果每一個像素用一位

43、二進(jìn)制碼如果每一個像素用一位二進(jìn)制碼( (0：白色，：白色，1：黑色：黑色) )表示，表示，顯然一頁文件的碼元數(shù)就等于該頁文件的像素數(shù)顯然一頁文件的碼元數(shù)就等于該頁文件的像素數(shù)例如，參照國際標(biāo)準(zhǔn)，一張例如，參照國際標(biāo)準(zhǔn)，一張 A4 幅面幅面( (210 mm 297 mm) )的的二值文件掃描的辨率為：二值文件掃描的辨率為：1728像素像素/ /行行，4行行/ /mm即一幅即一幅 A4 頁面共可分為頁面共可分為 1188 行，每行行，每行 1728 像素。整幅共像素。整幅共有有 2.05 M 個像素，若用個像素，若用 4800 bit/s 的信息傳輸率進(jìn)行傳輸?shù)男畔鬏斅蔬M(jìn)行傳輸約需約需 7.

44、2 分鐘，直接傳真將需耗費大量的通信時間分鐘，直接傳真將需耗費大量的通信時間33游程編碼概述(續(xù))統(tǒng)計表明，此類傳真文件黑白兩個灰度值出現(xiàn)的概率為：統(tǒng)計表明，此類傳真文件黑白兩個灰度值出現(xiàn)的概率為：()93.3%()6.7%pp 白白，黑黑()()log()()log()0.933log0.9330.067log0.0670.3546 bit / H Xpppp 像像素素熵熵：白白白白黑黑黑黑像像素素()log2110.354664.54%H X 冗冗余余度度：顯然一個像素用一位二進(jìn)制編碼，會有很大冗余度，要提高顯然一個像素用一位二進(jìn)制編碼，會有很大冗余度，要提高傳真效率，必須去除冗余傳真效率

45、，必須去除冗余對于二值灰度的文件，每一掃描行均是由若干個連白對于二值灰度的文件，每一掃描行均是由若干個連白( (0) )像素像素序列及若干個連黑序列及若干個連黑( (1) )像素序列組合而成，且同類像素連續(xù)出像素序列組合而成，且同類像素連續(xù)出現(xiàn)的概率很大，因此可通過像素類別現(xiàn)的概率很大，因此可通過像素類別( (黑或白黑或白) )加重復(fù)次數(shù)來加重復(fù)次數(shù)來表示，由此思想構(gòu)成的編碼稱為游程編碼表示，由此思想構(gòu)成的編碼稱為游程編碼重復(fù)出現(xiàn)的同類像素的長度稱為重復(fù)出現(xiàn)的同類像素的長度稱為游程長度；白白( (0) )像素序列稱像素序列稱為白為白( (0) )游程，游程， 黑黑( (1) )像素序列稱為黑像

46、素序列稱為黑( (1) )游程游程34游程編碼概述(續(xù))游程編碼的基本結(jié)構(gòu)是編碼單元：游程編碼的基本結(jié)構(gòu)是編碼單元：符號碼標(biāo)識碼游程長度像素序列：白白黑黑黑黑白白白白白白黑黑黑像素序列：白白黑黑黑黑白白白白白白黑黑黑游程編碼：白游程編碼：白#2黑黑#4白白#6黑黑#3實際上，每一掃描行的白像素序列和黑像素序列是交替出現(xiàn)實際上，每一掃描行的白像素序列和黑像素序列是交替出現(xiàn)的，若規(guī)定第一游程為白游程的，若規(guī)定第一游程為白游程( (若第一游程為黑游程，則在黑游若第一游程為黑游程，則在黑游程前插入一個游程長度為程前插入一個游程長度為 0 的白游程的白游程) )，則可將編碼中的，則可將編碼中的“符號符號

47、碼碼”和和“標(biāo)識碼標(biāo)識碼”均省略，均省略，這樣就可把像素序列變換為游程長度這樣就可把像素序列變換為游程長度序列，且二者是可逆的。例如：序列，且二者是可逆的。例如：像素類別：像素類別：“白白”( (0) )“黑黑”( (1) )符號碼和游符號碼和游程長度之間程長度之間的 分 割 符的 分 割 符游程長度序列：游程長度序列：45287613321黑白像素序列：黑白像素序列：0000111110011111111000000011111101110001104528761 33 2 1游程長度是隨機的，取值為游程長度是隨機的，取值為1,2,直直至無窮至無窮一一對應(yīng)的可逆變換35游程：數(shù)字序列中連續(xù)出

48、現(xiàn)相同符號的一段游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段二元序列的游程：只有二元序列的游程：只有“0”和和“1”兩兩種符號種符號連連“0”這一段稱為這一段稱為“0”游程，游程長度：游程，游程長度：L(0)連連“1”這一段稱為這一段稱為“1”游程，游程長度：游程，游程長度：L(1) 在二元序列中，在二元序列中，“0”游程和游程和“1”游程總是交替出現(xiàn)的游程總是交替出現(xiàn)的游程變換將二元序列變換成了多元序列，減弱了原序列符號間的相關(guān)游程變換將二元序列變換成了多元序列，減弱了原序列符號間的相關(guān)性，這樣就適合于用其它方法，如赫夫曼編碼，進(jìn)一步壓縮信源，提性，這樣就適合于用其它方法，如赫夫曼編碼，進(jìn)一步壓縮

49、信源，提高通信效率高通信效率r 元序列同樣也可以變換游程長度序列，但是元序列同樣也可以變換游程長度序列，但是 r 元序列，總共有元序列，總共有 r 種游程，種游程，為能保證一一對應(yīng)的可逆變換性，必須再加一些分隔標(biāo)志符號，才能區(qū)分為能保證一一對應(yīng)的可逆變換性，必須再加一些分隔標(biāo)志符號，才能區(qū)分游程長度序列中的某一個長度是游程長度序列中的某一個長度是 r 種游程中的哪一個長度；增加分隔標(biāo)志種游程中的哪一個長度；增加分隔標(biāo)志符號可能會抵消壓縮編碼得到的好處，故一般不對多元序列進(jìn)行游程編碼符號可能會抵消壓縮編碼得到的好處，故一般不對多元序列進(jìn)行游程編碼游程編碼的方法：游程編碼的方法：首先測定首先測定“

50、0”游程長度和游程長度和“1”游程長度的概率分布，即以游程長度游程長度的概率分布，即以游程長度為元素，構(gòu)造一個新的信源為元素，構(gòu)造一個新的信源對新的信源對新的信源( (游程長度序列游程長度序列) )進(jìn)行赫夫曼編碼進(jìn)行赫夫曼編碼游程編碼一般規(guī)定二元序列一般規(guī)定二元序列總是從總是從“0”開始開始36二元獨立序列的游程長度序列(0) 101 (0)(0)1,2,3,Lp LppL 注：在計算注：在計算 p L( 0 ) 時第一個信源符號必然是時第一個信源符號必然是“0”，否則就不，否則就不是是“0”游程，若下一個符號是游程，若下一個符號是“1”，則游程長度為，則游程長度為 1，其，其概率是概率是 p

51、1 1 1 p0；若下一個符號為；若下一個符號為“0”、再下一個符號、再下一個符號為為“1”，則游程長度為，則游程長度為 2，其概率為，其概率為 p0 p1；依此類推；依此類推(1) 110 (1)Lp Lpp 同理可得：同理可得：(0) 101(0) 1(0) 1 (0)LLLp Lpp 1 10010(1)1pppp 101pp 1 0(1) 11 (1)11Lpp Lp 若二元獨立序列的概率特性已知，由于二元獨立序列與游程若二元獨立序列的概率特性已知，由于二元獨立序列與游程長度序列的一一對應(yīng)性，可計算出游程長度序列的概率特性長度序列的一一對應(yīng)性，可計算出游程長度序列的概率特性設(shè)二元獨立序

52、列中符號設(shè)二元獨立序列中符號“0”和和“1”出現(xiàn)的概率分別為出現(xiàn)的概率分別為 p0 和和 p1 ，則則“0”游程長度游程長度 L(0) 的概率為：的概率為：37“0”游程長度序列的熵：游程長度序列的熵：(0) 101(0) 1(1) 110(1) 1 (0)(0)1,2,3, (0)1 (1)(1)1,2,3, (1)1LLLLp LppLp Lp LppLp L (0) 1 (0) (0)log (0)LH Lp Lp L “1”游程長度序列的熵：游程長度序列的熵：10 (1)()HH pLp 同理可得：同理可得： (0) 1(0) 1(0) 1010(0) 1011 (0)1loglogL

53、LLLLpppppp (0) 2(0) 1010(0) 101(0) 101(log) (0)1(log)LLLLp ppLpppp (0) 1010(0) 101(log)logLLp pppp (0) 1010(0) 101(log)logLLp pppp 010100d1(log)logd1p ppppp 1001111(log)logpppppp (0) 1(0) 1(0) 10101logLLLpppp 0101201(log)log(1)p pppp 001111(log)(log)ppppp 01()H pp 38“0”游程的平均長度：游程的平均長度：(0) 101(0) 101

54、(1) 110(1) 110 (0) (0)1 (0)() (1) (1)1 (1)()LLLLp Lppp LH LH ppp Lppp LH LH pp “1”游程的平均長度：同理可得游程的平均長度：同理可得011lp 二元獨立序列的熵：二元獨立序列的熵：“0”游程長度序列的熵與游程長度序列的熵與“1”游程長度序列的熵之和除以它們的平均游程長度序列的熵之和除以它們的平均游程長度之和，即為對應(yīng)的原二元獨立序列的熵游程長度之和，即為對應(yīng)的原二元獨立序列的熵 H ( X )01 (0) (1)()H LH LH Xll 游程變換后符號熵保持不變。因為游程變換是一一對應(yīng)的可逆變換游程變換后符號熵保

55、持不變。因為游程變換是一一對應(yīng)的可逆變換000111()(log)(log)()H pppppH p 0(0) 1 (0)(0) (0)LlE LLp L (0) 1(0) 101(0)LLLpp (0)1(0) 100ddLLppp 100d11d1ppp (0)1(0) 100ddLLppp 0100dd1pppp 100d1d1ppp 1201(1)pp 11p 011010()()11H pH ppppp 001101()()p H pp H ppp 0()H p 1()H p 39游程編碼的編碼效率根據(jù)編碼效率的定義和前述分析可得二元序列的編碼效率：根據(jù)編碼效率的定義和前述分析可得二

56、元序列的編碼效率：01 (0) (1) (0) (1)H LH LH LH L 假設(shè)假設(shè) 0 1，易知：，易知： 0 1當(dāng)當(dāng)“0”游程和游程和“1”游程的編碼效率都很高時，采用游程編碼游程的編碼效率都很高時，采用游程編碼的整體編碼效率也很高，至少不會低于較小的那個游程的編的整體編碼效率也很高，至少不會低于較小的那個游程的編碼效率碼效率要想游程的整體編碼效率盡可能高，應(yīng)盡可能提高熵值較大要想游程的整體編碼效率盡可能高，應(yīng)盡可能提高熵值較大的游程的編碼效率的游程的編碼效率0101 (0) (1),H LH LRR 假設(shè)假設(shè)“0”游程長度和游程長度和“1”游游程長度的赫夫曼編碼效率分程長度的赫夫曼編

57、碼效率分別為別為 1, 2，即：，即：40游程編碼的截斷處理盡管游程長度可以從盡管游程長度可以從 1 一直到無窮長，但建立游程長度與赫夫一直到無窮長，但建立游程長度與赫夫曼碼字之間的一一對應(yīng)碼表將是非常困難曼碼字之間的一一對應(yīng)碼表將是非常困難游程越長，其出現(xiàn)的概率就越小，所以：游程越長，其出現(xiàn)的概率就越小，所以： (0 1) (0,1)0Lp L ，由赫夫曼碼的編碼規(guī)則，概率越小，碼字越長；但小概率對由赫夫曼碼的編碼規(guī)則，概率越小，碼字越長；但小概率對應(yīng)的長碼字對平均碼長影響很小，故對較長的二元序列，游應(yīng)的長碼字對平均碼長影響很小，故對較長的二元序列，游程編碼一般需采用截斷處理，以下為一種截斷

58、處理方法程編碼一般需采用截斷處理，以下為一種截斷處理方法選取適當(dāng)?shù)倪x取適當(dāng)?shù)?n 值，將游程長度分別為值，將游程長度分別為 的游程進(jìn)的游程進(jìn)行赫夫曼編碼，得到相應(yīng)的碼表行赫夫曼編碼，得到相應(yīng)的碼表 1,2,3,21n 所有游程長度大于等于所有游程長度大于等于 的游程，將其編碼為多個固定的碼的游程，將其編碼為多個固定的碼字字 C 串接游程長度減去串接游程長度減去 所得余數(shù)的二進(jìn)制表示，具體為：所得余數(shù)的二進(jìn)制表示，具體為：2n2n游程長度：游程長度： ，則游程編碼為，則游程編碼為 CA，其中，其中 A 為游程為游程長度減去長度減去 所得余數(shù)補足為所得余數(shù)補足為 n 位的二進(jìn)制表示，位的二進(jìn)制表示

59、，12 21nn 2n游程長度：游程長度： ，則游程編碼為，則游程編碼為 C000CA，其，其中中 A 為游程長度減去為游程長度減去 所得余數(shù)的二進(jìn)制表示，依此類推所得余數(shù)的二進(jìn)制表示，依此類推112 221nnn12n n 個個41游程編碼的截斷處理(續(xù))例如：如選擇例如：如選擇 n 8，則可用，則可用 255 個碼字構(gòu)成的赫夫曼碼表對應(yīng)個碼字構(gòu)成的赫夫曼碼表對應(yīng)于游程長度不超過于游程長度不超過 255 的游程；如用的游程；如用 C 表示所有游程長度超過表示所有游程長度超過 255 的游程對應(yīng)的碼字的前半部分，則：的游程對應(yīng)的碼字的前半部分，則：游程長度編碼260C00000100516C0

60、0000000C00000100772C00000000C000000000C00000100“0”游程和游程和“1”游程當(dāng)分別編碼，建立各自的碼表游程當(dāng)分別編碼，建立各自的碼表兩個碼表中的碼字可以有重復(fù)，但兩個碼表中的碼字可以有重復(fù)，但 C 碼必須不同，即分別用碼必須不同，即分別用 C0 , C1 編碼編碼“0”游程和游程和“1”游程游程譯碼器要根據(jù)后面的碼字來判斷當(dāng)前游程的長度譯碼器要根據(jù)后面的碼字來判斷當(dāng)前游程的長度000000101nC 個個(0)25nL 0C(0)25nL 繼續(xù)考察更后面的碼字繼續(xù)考察更后面的碼字 1C后面碼后面碼字為：字為： 42MH 碼MH 碼是黑白二值文件、傳真類數(shù)據(jù)壓縮編碼