第五章信源編碼

1、第五章第五章 信源編碼信源編碼第一節(jié)第一節(jié) 編碼的定義編碼的定義第二節(jié)第二節(jié) 無失真信源編碼無失真信源編碼第三節(jié)第三節(jié) 限失真信源編碼定理限失真信源編碼定理第四節(jié)第四節(jié) 常用編碼方法常用編碼方法引言引言 限失真信源編碼限失真信源編碼：熵壓縮，信息量減少。：熵壓縮，信息量減少。 的條件下，的條件下，盡量降低信息率盡量降低信息率, ,最小值為最小值為R(D).R(D).主要用于連續(xù)信源或模擬信主要用于連續(xù)信源或模擬信號，如語音、圖像等信號。號，如語音、圖像等信號。DD _回顧：冗余度的概念、定義及產(chǎn)生的原因回顧：冗余度的概念、定義及產(chǎn)生的原因無失真信源編碼則是（無失真信源編碼則是（1）解相關(guān)（）解

2、相關(guān)（2）使新的符號等概出現(xiàn)）使新的符號等概出現(xiàn)無失真信源編碼無失真信源編碼：保熵編碼，信息量不變，無失真壓縮冗余：保熵編碼，信息量不變，無失真壓縮冗余適用于離散信源或數(shù)字信號。適用于離散信源或數(shù)字信號。本章以無失真信源編碼為主，介紹相關(guān)的編碼定理和編碼方本章以無失真信源編碼為主，介紹相關(guān)的編碼定理和編碼方法。法。信源編碼分為信源編碼分為無失真信源編碼無失真信源編碼和和限失真信源編碼限失真信源編碼。第一節(jié) 編碼的定義一、編碼：對信源輸出的原始符號按一定的一、編碼：對信源輸出的原始符號按一定的數(shù)學(xué)規(guī)則數(shù)學(xué)規(guī)則進(jìn)行進(jìn)行變換變換.信源編碼：變換成適合在信道中傳輸?shù)姆?，并進(jìn)行冗余壓縮信源編碼：變換成

3、適合在信道中傳輸?shù)姆?，并進(jìn)行冗余壓縮 或熵壓縮。或熵壓縮。信道編碼：變換后，能在接收端進(jìn)行檢錯(cuò)或糾錯(cuò)信道編碼：變換后，能在接收端進(jìn)行檢錯(cuò)或糾錯(cuò)二、信源編碼的數(shù)學(xué)描述：（單符號信源編碼）二、信源編碼的數(shù)學(xué)描述：（單符號信源編碼）iiijiwaf n21iwm21jbn21ia-:.,.,.,。構(gòu)成的碼字成由碼元射規(guī)則轉(zhuǎn)換根據(jù)某種變換規(guī)則或映，將輸入符號信源編碼碼字集碼字集W：碼字構(gòu)成的集合。：碼字構(gòu)成的集合。 某種映射規(guī)則某種映射規(guī)則f下產(chǎn)生一種碼字集，簡稱為碼。不同的映射規(guī)下產(chǎn)生一種碼字集，簡稱為碼。不同的映射規(guī)則產(chǎn)生不同的碼（碼字集）。所有的碼字集構(gòu)成碼表。則產(chǎn)生不同的碼（碼字集）。所有的

4、碼字集構(gòu)成碼表。編碼也可以這樣描述：編碼也可以這樣描述： 選擇不同的碼表即選擇不同的映選擇不同的碼表即選擇不同的映射規(guī)則射規(guī)則f,從而產(chǎn)生不同的碼。從而產(chǎn)生不同的碼。0100111001yaaaaax11100,01,10,W11wa10wa 01wa00waf10bbBaa,aaAX23412443322111214321時(shí)，輸出序列為：當(dāng)輸入序列為，稱為碼那么，碼字集為，為：若映射規(guī)則，碼元集：信源符號集,舉例10100110010yaaaaax20110,01,001,W011wa001wa 01wa0waf23412443322112時(shí)，輸出序列為：當(dāng)輸入序列為，稱為碼那么，碼字集為，

5、為：若映射規(guī)則n1iiii_iKaPWEK /W)( 平均碼長信源符號的個(gè)數(shù)）。碼元的長度（碼字所含碼元碼字碼長碼長Ki及其意義及其意義意義：衡量意義：衡量碼的性能碼的性能的重要參數(shù)的重要參數(shù) 對于無失真信源編碼，平均碼長對于無失真信源編碼，平均碼長 越短，說明通過編碼壓越短，說明通過編碼壓縮去的冗余越多。反之，冗余壓縮越少?？s去的冗余越多。反之，冗余壓縮越少。_K 這是因?yàn)闊o失真編碼前后，信息量不變，這是因?yàn)闊o失真編碼前后，信息量不變， 越小說明每個(gè)越小說明每個(gè)碼元攜帶的信息量越大，冗余越小，壓縮掉的冗余就越多。碼元攜帶的信息量越大，冗余越小，壓縮掉的冗余就越多。_K三、幾種常見的碼：三、幾

6、種常見的碼： 1、定長碼和非定長碼：、定長碼和非定長碼：Wi=Wj，i,j=1,2.n。則為定長碼。則為定長碼 2、奇異碼和非奇異碼：、奇異碼和非奇異碼：ij,則則WiWj；或：；或：ai與與Wi一一對應(yīng)一一對應(yīng)信源符號信源符號碼碼1碼碼2碼碼3碼碼4碼碼5a1a2a3a400011011000010111000110110110111101011111碼碼1 1、碼、碼2 2為定長碼為定長碼碼碼3 3、4 4、5 5非定長碼非定長碼碼碼1 1、3 3、4 4、5 5是非奇是非奇異碼，碼異碼，碼2 2是奇異碼是奇異碼舉例：碼舉例：碼w1,w2,w3=0,10,11 ，惟一可譯，惟一可譯 碼碼w

7、1,w2,w3 , w4=1,00,01,10 ，非惟一可譯（舉出一個(gè)反，非惟一可譯（舉出一個(gè)反例即可）例即可） 注：奇異碼一定非惟一可譯。（非奇異碼則不一定）注：奇異碼一定非惟一可譯。（非奇異碼則不一定） 3、惟一可譯碼和非惟一可譯碼：、惟一可譯碼和非惟一可譯碼： 從編碼器輸出的碼元序列（碼字序列）能惟一地恢復(fù)出輸入從編碼器輸出的碼元序列（碼字序列）能惟一地恢復(fù)出輸入的信源符號序列；或者說，任意有限長的碼元序列只能惟一地的信源符號序列；或者說，任意有限長的碼元序列只能惟一地分割成一個(gè)個(gè)的碼字。稱為惟一可譯。分割成一個(gè)個(gè)的碼字。稱為惟一可譯。任一任一有限長的碼元序列，如：有限長的碼元序列，如：

8、1 0 0 1 1 1 0 0 0 只能分割成只能分割成1 0 0 1 1 1 0 0 0 即：即：w2, w1, w3,w2,w1, w1 如：如：1 0 0 1 0 0 1可以分割成可以分割成 1 00 10 01 =w1, w2, w4,w3;或者或者10 01 00 1=w4, w3 w2, w1；或者；或者= 1 00 1 00 1=w1,w2 ,w1 ,w2,w1 4、即時(shí)碼和非即時(shí)碼：、即時(shí)碼和非即時(shí)碼： 收到一個(gè)完整的碼字后能立即譯碼，或曰及時(shí)可譯收到一個(gè)完整的碼字后能立即譯碼，或曰及時(shí)可譯-即時(shí)碼即時(shí)碼收到一個(gè)完整的碼字后不能立即譯碼，還需要根據(jù)下一個(gè)碼字收到一個(gè)完整的碼字后

9、不能立即譯碼，還需要根據(jù)下一個(gè)碼字才能判斷是否可譯才能判斷是否可譯-非即時(shí)碼。非即時(shí)碼。 如：碼如：碼1,10,100,1000 ，為非即時(shí)碼。延長碼，前綴碼，為非即時(shí)碼。延長碼，前綴碼 如：碼如：碼1,01,001,0001 ，為立即碼。非延長碼，異前綴碼，為立即碼。非延長碼，異前綴碼且惟一可譯。且惟一可譯。碼碼非分組碼非分組碼分組碼分組碼奇異碼奇異碼非奇異碼非奇異碼非唯一可譯碼非唯一可譯碼唯一可譯碼唯一可譯碼非即時(shí)碼非即時(shí)碼即時(shí)碼即時(shí)碼分組碼分組碼：將信源符號序列分成：將信源符號序列分成若干組或塊，再進(jìn)行編碼若干組或塊，再進(jìn)行編碼四、碼樹和四、碼樹和kraft不等式不等式1、 即時(shí)碼可以用

10、碼樹來構(gòu)造，如用二進(jìn)制碼樹。即時(shí)碼可以用碼樹來構(gòu)造，如用二進(jìn)制碼樹。樹根樹根A(倒著長）倒著長）二進(jìn)制二進(jìn)制-兩個(gè)樹枝，兩個(gè)樹枝，標(biāo)號標(biāo)號0，1；產(chǎn)生兩個(gè)；產(chǎn)生兩個(gè)一級節(jié)點(diǎn)。一級節(jié)點(diǎn)。第第n級級,2n個(gè)個(gè)n級節(jié)點(diǎn)級節(jié)點(diǎn)終端節(jié)點(diǎn)終端節(jié)點(diǎn)-不再長不再長出分枝的節(jié)點(diǎn)。出分枝的節(jié)點(diǎn)。例如：例如：n=4,共共16個(gè)終端節(jié)點(diǎn)，可以表示符號數(shù)為個(gè)終端節(jié)點(diǎn)，可以表示符號數(shù)為16 的信源的的信源的每一個(gè)符號每一個(gè)符號a1,a2,a3 a4 a5 a16。用樹根到每個(gè)終端節(jié)點(diǎn)的樹枝用樹根到每個(gè)終端節(jié)點(diǎn)的樹枝標(biāo)號構(gòu)成的序列作為該節(jié)點(diǎn)信源符號的編碼輸出標(biāo)號構(gòu)成的序列作為該節(jié)點(diǎn)信源符號的編碼輸出（即碼字）（即碼字）若信

11、源符號數(shù)小于若信源符號數(shù)小于16，可以去掉幾個(gè)節(jié)點(diǎn)，碼樹為非滿樹，可以去掉幾個(gè)節(jié)點(diǎn)，碼樹為非滿樹（只有部分樹枝延伸到最后一級）（只有部分樹枝延伸到最后一級）r 進(jìn)制進(jìn)制 -每個(gè)節(jié)點(diǎn)長出每個(gè)節(jié)點(diǎn)長出r個(gè)樹枝。個(gè)樹枝。如如r=3,三進(jìn)制碼樹三進(jìn)制碼樹0120000011111222222、kraft(克勞夫特克勞夫特)不等式不等式 惟一可譯碼惟一可譯碼存在的存在的充分和必要條件是，各碼字的長度充分和必要條件是，各碼字的長度Ki應(yīng)符合克勞夫特不等式：應(yīng)符合克勞夫特不等式： 11niKimm是進(jìn)制數(shù)是進(jìn)制數(shù)(碼元集中碼符號的個(gè)數(shù)）碼元集中碼符號的個(gè)數(shù)）n是信源符號數(shù)。是信源符號數(shù)。 強(qiáng)調(diào)強(qiáng)調(diào)：作為必要

12、條件，滿足不等式，則一定存在相應(yīng)碼長：作為必要條件，滿足不等式，則一定存在相應(yīng)碼長Ki的惟一可譯碼。但不能作為某種碼是否惟一可譯的判據(jù)。的惟一可譯碼。但不能作為某種碼是否惟一可譯的判據(jù)。例題例題5-1 二進(jìn)制編碼二進(jìn)制編碼的惟一可譯碼。、編碼，不存在長度為對四元符號進(jìn)行二進(jìn)制，則：若；32211893K2K2K1K12m10B4naaaaAX143214321niKim,)(,的惟一可譯碼。、編碼，存在長度為對四元符號進(jìn)行二進(jìn)制，滿足不等式，則：若332113K3K2K1K214321niKim,)(用碼樹驗(yàn)證以上結(jié)果：用碼樹驗(yàn)證以上結(jié)果：無論如何也不能構(gòu)造出長無論如何也不能構(gòu)造出長度為度為1

13、、2、2、3的即時(shí)碼的即時(shí)碼第二節(jié) 無失真信源編碼定理1、符號序列編碼、符號序列編碼:對信源符號序列進(jìn)行編碼對信源符號序列進(jìn)行編碼(而非對單符號編碼而非對單符號編碼)iiLijLif n21i m21jb n21i L-yxyx:.,(.,.,。也稱為碼字）構(gòu)成的碼元序列元或映射規(guī)則轉(zhuǎn)換成由碼根據(jù)某種變換規(guī)則，長輸入符號序列將信源編碼LL_LLL2L1in1iLiL_LLiKKKKKKPKK n21iKLnL，定長編碼：符號序列碼元；平均碼長：，碼長./)(.,y2、碼長的意義：衡量、碼長的意義：衡量碼的性能碼的性能的重要參數(shù)的重要參數(shù) 對于無失真信源編碼，平均碼長對于無失真信源編碼，平均碼長

14、 越長，說明通過編碼越長，說明通過編碼壓縮去的冗余越少。反之平均碼長壓縮去的冗余越少。反之平均碼長 越短，冗余壓縮越多。越短，冗余壓縮越多。LK_ 平均碼長平均碼長 最小是多少呢？最小是多少呢？ （小于此值，就會(huì)產(chǎn)生失（小于此值，就會(huì)產(chǎn)生失真）。有下面的定理：真）。有下面的定理： LK_一、定長編碼定理：一、定長編碼定理： 。就可以輸出惟一可譯碼；顯然，只要序列總數(shù)為個(gè)，而被編碼的符號進(jìn)制定長非奇異碼共有的碼長為,.LKLKLnm nm mKLL：稍加整理即是如下定理又兩邊取對數(shù)，整理后有不等式對 )X(HLK )X(Hn nLK nm LLLLLKLmmloglogloglog 由由L個(gè)符號

15、組成的、每個(gè)符號的熵為個(gè)符號組成的、每個(gè)符號的熵為 的無記憶平穩(wěn)的無記憶平穩(wěn)信源符號序列信源符號序列 ,可用可用KL個(gè)符號個(gè)符號 （每個(gè)符號有（每個(gè)符號有m種可能值）進(jìn)行定長編碼。對任意的種可能值）進(jìn)行定長編碼。對任意的 只要只要 ，則：當(dāng)，則：當(dāng)L足夠大時(shí)，必可使譯碼差足夠大時(shí)，必可使譯碼差 錯(cuò)小于錯(cuò)小于 （幾乎無失真編碼）；（幾乎無失真編碼）；Ll21XXXXLKk21Y,Y,Y,Y0, 0logm)X(HLKLL)X(HL 反之，當(dāng)反之，當(dāng) 時(shí)，譯碼差錯(cuò)一定是有限值，而當(dāng)時(shí)，譯碼差錯(cuò)一定是有限值，而當(dāng)L足夠大時(shí)，譯碼幾乎必定足夠大時(shí)，譯碼幾乎必定 出錯(cuò)（譯碼錯(cuò)誤概率接近于出錯(cuò)（譯碼錯(cuò)誤概

16、率接近于1 1）。）。 logm2)X(HLKLL1、解釋：、解釋： KL/L-編碼時(shí)，每個(gè)信源符號輸出的編碼時(shí)，每個(gè)信源符號輸出的 碼長。即每個(gè)信源符碼長。即每個(gè)信源符號用號用KL/L 個(gè)碼元來表示。個(gè)碼元來表示。 )()()()()(XHaPlogaPlogmalogPaPlogmH(X) logm)X(HmiimiiiiL平穩(wěn)平均平均m進(jìn)制符號熵。進(jìn)制符號熵。編碼時(shí)，編碼時(shí)，KL/L，越小越好。只要，越小越好。只要KL/L比平均比平均m進(jìn)制熵稍大一點(diǎn)，進(jìn)制熵稍大一點(diǎn)，那么當(dāng)那么當(dāng)L足夠大時(shí)，編碼就可以做到幾乎無失真。否則，不可能足夠大時(shí)，編碼就可以做到幾乎無失真。否則，不可能實(shí)現(xiàn)無失真編

17、碼，且當(dāng)實(shí)現(xiàn)無失真編碼，且當(dāng)L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。足夠大時(shí)，譯碼幾乎必定出錯(cuò)。另一種解釋：另一種解釋： )X(HlogmLK )X(HLKLLLLmlog或者稱為編碼器容許的輸出信息率?；蛘叻Q為編碼器容許的輸出信息率。以以2為底時(shí)，單位是為底時(shí)，單位是bit/信源符號，所信源符號，所以它表示了每個(gè)信源符號在編碼時(shí)用多少以它表示了每個(gè)信源符號在編碼時(shí)用多少bie來表示。來表示。（教材也稱之為每個(gè)信源符號所必須輸出的碼長）（教材也稱之為每個(gè)信源符號所必須輸出的碼長）編碼時(shí)，編碼時(shí)， 越小越好。只要越小越好。只要 比平均符號熵稍大一點(diǎn)，那么當(dāng)比平均符號熵稍大一點(diǎn)，那么當(dāng)L足夠大時(shí)，編碼就可以

18、做到幾乎無失真。否則，不可能實(shí)現(xiàn)無足夠大時(shí)，編碼就可以做到幾乎無失真。否則，不可能實(shí)現(xiàn)無失真編碼，且當(dāng)失真編碼，且當(dāng)L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。足夠大時(shí)，譯碼幾乎必定出錯(cuò)。_K_K 由于碼元有由于碼元有m種取值，長度為種取值，長度為KL的碼字的最大信息量為的碼字的最大信息量為KLlogm。用該碼字表示。用該碼字表示L長的信源序列長的信源序列,則則平均送出一個(gè)信源平均送出一個(gè)信源符號符號所需要的最大信息率為所需要的最大信息率為:logmLKKL_又一種解釋：又一種解釋：其中：左邊其中：左邊-KL長碼字所能攜帶的最大信息量，長碼字所能攜帶的最大信息量， 右邊右邊-L長信源序列攜帶的信息量。長信源

19、序列攜帶的信息量。定理表明，只要碼字所能攜帶的信息量大于信源序列輸出的信定理表明，只要碼字所能攜帶的信息量大于信源序列輸出的信息量，則可以實(shí)現(xiàn)幾乎無失真編碼，當(dāng)然條件是息量，則可以實(shí)現(xiàn)幾乎無失真編碼，當(dāng)然條件是L足夠大。足夠大。反之，不可能實(shí)現(xiàn)無失真的編碼，也就是不可能做一種編碼反之，不可能實(shí)現(xiàn)無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時(shí)差錯(cuò)概率趨于零。器，能使收端譯碼時(shí)差錯(cuò)概率趨于零。LLLL)XH()X(LHlogmK )X(HLKmlog2、舉例：、舉例：信源符號。，等概分布單符號信源，/)()(,3bitlb8XHXH1L8n.aaaAX(1)1821實(shí)現(xiàn)無失真編碼。信源符號

20、，就可以碼元要仍進(jìn)行二進(jìn)制編碼，只信源符號。計(jì)算得分布，上例中，符號不再等概/)(/)()(.,.,.,.,.,.,.,.)( 2.55logmXHK2.55bitXHXH04,00500660070101018040aP(2)L1i無失真編碼。信源符號，就可以實(shí)現(xiàn)碼元，據(jù)定理，只要若進(jìn)行二進(jìn)制編碼，/)(,3logmXHKLK2m10BLL種信源符號。示位二進(jìn)制碼確實(shí)可以表事實(shí)上，83無失真編碼。幾乎所謂小，即碼），差錯(cuò)概率會(huì)足夠足夠大時(shí)（符號序列編但是，當(dāng)來失真。種信源符號，編碼會(huì)帶，只能區(qū)分然而，L5586522.55 .那么，那么，L的取值多大，才得到滿意的譯碼差錯(cuò)概率？的取值多大，才

21、得到滿意的譯碼差錯(cuò)概率？E222P)XL)X0 差錯(cuò)率由編碼效率確定），（為需要給定的正數(shù)，那么：當(dāng)，號序列的自信息方差為的很小的實(shí)數(shù)，信源符是大于設(shè),(2n1i2ii2i2i2iii2ii)XH(logPPIEIEIEIEDI)XlogPIL()()()()()(),()(xxxxxxx那么自信息量為注：某信源符號序列的3、編碼效率：、編碼效率：)(長每個(gè)信源符號輸出的碼息率為編碼器容許的輸出信熵為序列信源的平均符號其中：，logmLKK)XH K)XHL_L_L碼器的編碼效率表示了信源編低。所以越大，說明編碼效率越碼效率越高。反之，的冗余越多，也就是編越小，說明編碼壓縮掉 K K_)XH)

22、XH11)XH)XHK)XH)XHKLLLL_LL_(最佳編佳編碼(，有最大值，稱為取等號時(shí)，的信源編碼是存在的。碼效率接近于是很小的正數(shù)，說明編由編碼定理，)(22L2222LLL_L-)(1XH)X)XL)XH1 logmLK)XHK)XH）（由最佳編碼效率推出而，很大組長度）信源符號序列長度（分很小的編碼方法，要求很大而譯碼錯(cuò)誤概率想要獲得編碼效率L%.,/.)(.9010B55bit2XH0.0405006007010101800.4aaaaaaaaPX2587654322要求編碼效率為碼，對它進(jìn)行定長二進(jìn)制編信源符號計(jì)算得：信源例題符號即單符號編碼。若取/.(,)(83bit2905

23、52X)H)XHK1L1L_不能應(yīng)用。序列編碼。太大。的錯(cuò)誤概率為編碼會(huì)帶來失真，最小沒有對應(yīng)的碼字號種信源符號，有一種符，只能區(qū)分和表示然而，,040777.1122.83?)(L1090%26，計(jì)算且譯碼錯(cuò)誤概率若要求難以實(shí)現(xiàn)難以實(shí)現(xiàn)72222n1i2iiii2LL1089)XLbit827X)H(logPPDIDI)X280X)HX)H )XH)XH.()(.()()(.(xx得：平穩(wěn)由：二、變長編碼定理二、變長編碼定理 若一離散無記憶信源的符號熵為若一離散無記憶信源的符號熵為H（X），每個(gè)信源符號），每個(gè)信源符號用用m進(jìn)制碼元進(jìn)行變長編碼，一定存在一種無失真編碼方法進(jìn)制碼元進(jìn)行變長編碼

24、，一定存在一種無失真編碼方法其平均碼長其平均碼長 滿足下列不等式：滿足下列不等式： 1logmH(X)KlogmH(X)_n1iiii_KaPWEK)(1、單符號變長編碼定理、單符號變長編碼定理2、離散平穩(wěn)無記憶序列變長編碼定理（、離散平穩(wěn)無記憶序列變長編碼定理（香農(nóng)第一極限定理香農(nóng)第一極限定理）)(:.,.,長每個(gè)信源符號輸出的碼的輸出信息率為編碼器容許平均碼長構(gòu)成的碼字元由碼，長輸入符號序列l(wèi)ogmLKK KPKEKf n21ib n21i LL_n1iiLiiLL_iiLijLiLyxyx是任意小的正數(shù)。，滿足不等式：法，使平均信息率一種無失真信源編碼方，必存在的離散平穩(wěn)無記憶信源對于平

25、均符號熵為 )X(HK)X(HK )X(H LLL_Ln1iiLiiLL_L_n1iiii_LLKPKEKlogmLKK KaPWEK )X(HK)X(H 1logmH(X)KlogmH(X) K )(注：_，平穩(wěn)序列變長變碼單符號變長變碼定理的區(qū)別兩個(gè)定理中 1logm)XH(K logm)XH( 1logmH(X)KlogmH(X) L_平穩(wěn)序列變長變碼單符號變長變碼定理樣的其實(shí)，二者本質(zhì)上是一3、編碼效率、編碼效率 定義）（同定長編碼的 K)XH_L(）（定長編碼代入定理中的不等式，1 1 )XH)XHLL()X(HK)X(H Llogm Llogm)X(HK)X(H logmLKK),

26、X(LH)XH(LLLL_L_L_/得：取代入右式，和將 logPPKEK , logmKX)H niiii_(注這里，：對于單符號變長變碼logmKX)H X)H)XHKK1,L logmLK)XH K)XH _L_L_L_L_L(,(單符號編碼有4、剩余度、剩余度 縮的冗余的多少。亦即：編碼后尚未被壓編碼的差距，表示了編碼方法與最佳 K)XH1 -1 _L(復(fù)習(xí)一、信源編碼的模型：一、信源編碼的模型：單符號編碼和符號序列編碼單符號編碼和符號序列編碼n1iiii_iKaPWEK /W)( 平均碼長信源符號的長度。碼元碼字單符號編碼：1、碼長及其意義：、碼長及其意義：意義：衡量意義：衡量碼的性

27、能碼的性能的重要參數(shù)的重要參數(shù) 對于無失真信源編碼，平均碼長對于無失真信源編碼，平均碼長 越短，說明通過編碼壓越短，說明通過編碼壓縮去的冗余越多。反之，冗余壓縮越少。縮去的冗余越多。反之，冗余壓縮越少。_KLL_LLL2L1in1iLiL_LLiKKKKKKPKK n21iK LnL，定長編碼：符號序列碼元平均碼長：；，符號序列編碼：碼長./)(.,y碼碼非分組碼非分組碼分組碼分組碼奇異碼奇異碼非奇異碼非奇異碼非唯一可譯碼非唯一可譯碼唯一可譯碼唯一可譯碼非即時(shí)碼非即時(shí)碼即時(shí)碼即時(shí)碼3、碼樹和、碼樹和kraft不等式不等式 惟一可譯碼惟一可譯碼存在的存在的充分和必要條件是，充分和必要條件是，各碼

28、字的長度各碼字的長度Ki應(yīng)符合克勞夫特不等式：應(yīng)符合克勞夫特不等式： 11niKim2、分類：、分類： 由由L個(gè)符號組成的、每個(gè)符號的熵為個(gè)符號組成的、每個(gè)符號的熵為 的無記憶平穩(wěn)的無記憶平穩(wěn)信源符號序列信源符號序列 ,可用可用KL個(gè)符號個(gè)符號 （每個(gè)符號有（每個(gè)符號有m種可能值）進(jìn)行定長編碼。對任意的種可能值）進(jìn)行定長編碼。對任意的 只要只要 ，則：當(dāng)，則：當(dāng)L足夠大時(shí)，必可使譯碼差足夠大時(shí)，必可使譯碼差 錯(cuò)小于錯(cuò)小于 （幾乎無失真編碼）；（幾乎無失真編碼）；Ll21XXXXLKk21Y,Y,Y,Y0, 0logm)X(HLKLL)X(HL二、定長編碼定理二、定長編碼定理 反之，當(dāng)反之，當(dāng)

29、時(shí)，譯碼差錯(cuò)一定是有限值，而當(dāng)時(shí)，譯碼差錯(cuò)一定是有限值，而當(dāng)L足夠大時(shí)，譯碼幾乎必定足夠大時(shí)，譯碼幾乎必定出錯(cuò)（譯碼錯(cuò)誤概率接近于出錯(cuò)（譯碼錯(cuò)誤概率接近于1 1）。）。 logm2)X(HLKLL )X(HK L_平均送出一個(gè)信源符號所需要的最大信息率平均送出一個(gè)信源符號所需要的最大信息率編碼器容許的輸出信息率編碼器容許的輸出信息率每個(gè)信源符號所必須輸出的碼長每個(gè)信源符號所必須輸出的碼長logmLKKL_編碼時(shí)，編碼時(shí)， 越小越好。只要越小越好。只要 比平均符號熵稍大一點(diǎn)，那么當(dāng)比平均符號熵稍大一點(diǎn)，那么當(dāng)L足夠大時(shí)，編碼就可以做到幾乎無失真。否則，不可能實(shí)現(xiàn)無足夠大時(shí)，編碼就可以做到幾乎無失

30、真。否則，不可能實(shí)現(xiàn)無失真編碼，且當(dāng)失真編碼，且當(dāng)L足夠大時(shí)，譯碼幾乎必定出錯(cuò)。足夠大時(shí)，譯碼幾乎必定出錯(cuò)。_K_K2、L的取值：的取值：E222P)XL)X0 錯(cuò)率由編碼效率確定），差（為需要給定的正數(shù)，那么：當(dāng)方差為號序列的自信息的很小的實(shí)數(shù)，信源符是大于設(shè),(_LK)XH (3、編碼效率：、編碼效率：1 1、解釋、解釋：無法物理實(shí)現(xiàn)計(jì)算得：譯碼錯(cuò)誤概率要求編碼效率為碼，對它進(jìn)行定長二進(jìn)制編舉例：信源 1089)XL 109010B0.0405006007010101800.4aaaaaaaaPX722687654322.(%,.,.二、變長編碼定理二、變長編碼定理1、單符號變長編碼定理、

31、單符號變長編碼定理 無失真編碼的平均碼長無失真編碼的平均碼長 滿足不等式：滿足不等式： 1logmH(X)KlogmH(X)_n1iiii_KaPWEK)(2、離散平穩(wěn)無記憶序列變長編碼定理（、離散平穩(wěn)無記憶序列變長編碼定理（香農(nóng)第一極限定理香農(nóng)第一極限定理）是任意小的正數(shù)。，滿足不等式：法，使平均信息率一種無失真信源編碼方，必存在的離散平穩(wěn)無記憶信源對于平均符號熵為 )X(HK)X(HK )X(H LLL_)(長每個(gè)信源符號輸出的碼的輸出信息率為編碼器容許平均碼長logmLKK KPKEKL_n1iiLiiLL_L K)XH_L() logPPKEK , logmKX)H niiii_(，單

32、符號時(shí)Go on5、舉例、舉例5-3 %.(,;,:)(/)()(/_181KX)H 2m logmKX)H ; 1KEK1KK1a0af10.811bitXHXH413/4aaPX_i2121121平均碼長二元定長編碼信源符號。，計(jì)算得信源碼元信源符號碼元信源符號編碼器輸出的信息率：/.(/(811bit0KX)H 1L / bit/ LK )XH R_L_L的二元序列變長編碼2L2)(碼元961bit/03227X)H LK )XH R 96.13227X)HK)XHL_L2_L2./(/(%/(符號比特平均信息率符號序列碼元平均碼長/3227lb221627logmLKK /27/16

33、KPKEKL_41iiLiiLL_/ 99.1 98.543L43%時(shí)、同理：9510134L10963.%)(計(jì)算得，）若要求定長編碼（上一節(jié)內(nèi)容性能比較：性能比較： 定長編碼定長編碼 非定長編碼非定長編碼 0 99.1 4L 10 96 104L 0 96 2L 0 81.1 1L 5-7，%哪個(gè)性能更好？哪個(gè)性能更好？6、補(bǔ)充說明：、補(bǔ)充說明： 以上編碼定理以上編碼定理,適用于離散無記憶平穩(wěn)信源適用于離散無記憶平穩(wěn)信源,只考慮了信源符號只考慮了信源符號分布不均勻性造成的冗余分布不均勻性造成的冗余,而未考慮符號間的相關(guān)性造成的冗余而未考慮符號間的相關(guān)性造成的冗余三、最佳變長編碼方法三、最佳

34、變長編碼方法1、最佳碼最佳碼的定義的定義：凡是能載荷一定的信息量，且碼字的凡是能載荷一定的信息量，且碼字的平均平均長度最短長度最短（壓縮后冗余最少），可分離的變長碼的碼字集合（壓縮后冗余最少），可分離的變長碼的碼字集合都可稱為最佳碼。都可稱為最佳碼。2、最佳編碼的指導(dǎo)思想：、最佳編碼的指導(dǎo)思想： 將概率大的信息符號編以短的碼字，概率小的符號編以長將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長度最短。的碼字，使得平均碼字長度最短。3、最佳編碼的主要方法最佳編碼的主要方法 ：香農(nóng)（：香農(nóng)（Shannon）、費(fèi)諾（）、費(fèi)諾（Fano）、）、 哈夫曼（哈夫曼（Huffman）

35、編碼等。）編碼等。 1logm)XH(K logm)XH( L_:序列熵之間的關(guān)系均碼長和信源了無失真信源編碼時(shí)平香農(nóng)第一極限定理給出 以下主要介紹單符號編碼時(shí)，香農(nóng)、費(fèi)諾以下主要介紹單符號編碼時(shí)，香農(nóng)、費(fèi)諾 、哈夫曼等編碼方法、哈夫曼等編碼方法 1、香農(nóng)編碼：、香農(nóng)編碼：1)XH(K)XH(2m L_），有：如果是二進(jìn)制編碼（長碼叫做香農(nóng)碼。這樣確定的無失真不定：確定每個(gè)碼字的長度?？砂凑者@一關(guān)系對于單符號編碼則有：1I(aKI(a K1H(X)KH(X)iiii_)(1)將信源符號按其出現(xiàn)的概率大小依次排列：將信源符號按其出現(xiàn)的概率大小依次排列： P1P2P3. Pn （指導(dǎo)思想）（指導(dǎo)思

36、想）(2)確定滿足下列不等式的整數(shù)碼長確定滿足下列不等式的整數(shù)碼長Ki)(iiiiiaPP 1-lbPKlbP- ，(3)為了編成唯一可譯碼，計(jì)算第為了編成唯一可譯碼，計(jì)算第i個(gè)符號的累加概率個(gè)符號的累加概率1i1kkiPP(4)將累加概率將累加概率Pi 變換成二進(jìn)制數(shù)。變換成二進(jìn)制數(shù)。 (乘乘2取整）取整）(5)取取Pi二進(jìn)數(shù)的小數(shù)點(diǎn)后二進(jìn)數(shù)的小數(shù)點(diǎn)后Ki位即為該信源符號的二進(jìn)制碼字。位即為該信源符號的二進(jìn)制碼字。 具體編碼步驟：具體編碼步驟： 例題例題5-4：設(shè)信源共：設(shè)信源共7個(gè)符號，其概率和累加概率如下表所示。個(gè)符號，其概率和累加概率如下表所示。以以i=4為例，為例， 3K563562

37、 1170lbK170lb444,.K，累加概率累加概率P4=0.57，變換成二進(jìn)制為，變換成二進(jìn)制為0.1001，由于，由于K4=3，所以，所以第第4個(gè)消息的編碼碼字為個(gè)消息的編碼碼字為100。其它的碼字可用同樣方法求得。其它的碼字可用同樣方法求得。 （1） （3） （2） （4、5）碼字集為碼字集為000,001,011,100,101,1110,1111110惟一可譯碼；且是即時(shí)碼（惟一可譯碼；且是即時(shí)碼（7個(gè)碼字都不是延長碼）個(gè)碼字都不是延長碼）%./.(183143612KX)H 2m logmKX)H / 3.14KPK _71iii編碼效率：符號碼元：單符號編碼，平均碼長（數(shù)學(xué)可

38、以證明）。說明香農(nóng)碼不是最佳碼更短的惟一可譯碼其實(shí)，可以構(gòu)造出碼長。香農(nóng)編碼輸出為，信源例題,.)(,11100110100W104050aPaaaAX 5-5i321碼元編碼輸出的信息率：/./.(0.831bit 143612 K X)H R 2、費(fèi)諾編碼：、費(fèi)諾編碼：(1)將信源符號按其出現(xiàn)的概率大小依次排列：將信源符號按其出現(xiàn)的概率大小依次排列： P1P2P3. Pn （指導(dǎo)思想）（指導(dǎo)思想）(2)將依次排列的信源符號按概率值分為兩大組，使兩個(gè)組的將依次排列的信源符號按概率值分為兩大組，使兩個(gè)組的概率之和近于相同，并對各組賦予一個(gè)二進(jìn)制碼元概率之和近于相同，并對各組賦予一個(gè)二進(jìn)制碼元“

39、0”和和“1”。(3)將每一大組的信源符號進(jìn)一步再分成兩組，使劃分后的兩將每一大組的信源符號進(jìn)一步再分成兩組，使劃分后的兩個(gè)組的概率之和近于相同，并又賦予兩個(gè)組一個(gè)二進(jìn)制符號個(gè)組的概率之和近于相同，并又賦予兩個(gè)組一個(gè)二進(jìn)制符號“0和和“1”。(4)如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號為止。如此重復(fù)，直至每個(gè)組只剩下一個(gè)信源符號為止。(5)信源符號所對應(yīng)的碼字即為費(fèi)諾碼。信源符號所對應(yīng)的碼字即為費(fèi)諾碼。 例題例題5-6：信源同例題：信源同例題5-4，進(jìn)行費(fèi)諾編碼，進(jìn)行費(fèi)諾編碼實(shí)際上，費(fèi)諾編碼構(gòu)造了一個(gè)碼樹（根在左邊）。非滿樹。實(shí)際上，費(fèi)諾編碼構(gòu)造了一個(gè)碼樹（根在左邊）。非滿樹。7個(gè)端點(diǎn)，表示個(gè)

40、端點(diǎn)，表示7個(gè)信源符號。個(gè)信源符號。%/.( 95.32.74612KX)H 2m logmKX)H / 2.74KPK _71iii編碼效率：符號碼元：單符號編碼，平均碼長碼元編碼輸出的信息率：/.(0.953bit 2.74612 K X)H R 比較：優(yōu)于香農(nóng)碼。對于該信源，香農(nóng)碼的編碼效率為比較：優(yōu)于香農(nóng)碼。對于該信源，香農(nóng)碼的編碼效率為83.1%3、哈夫曼編碼：、哈夫曼編碼： 最佳編碼最佳編碼，碼長最短，碼長最短(1)將信源符號按其出現(xiàn)的概率大小依次排列：將信源符號按其出現(xiàn)的概率大小依次排列： P1P2P3. Pn （指導(dǎo)思想）（指導(dǎo)思想）(2)取兩個(gè)概率最小的符號，分別賦以碼元取兩

41、個(gè)概率最小的符號，分別賦以碼元0和和1，并將這兩個(gè)，并將這兩個(gè)概率相加作為一個(gè)概率相加作為一個(gè)“新符號新符號”的概率。的概率。(3) “新符號新符號”與其它符號構(gòu)成縮減信源。按概率大小進(jìn)行重新與其它符號構(gòu)成縮減信源。按概率大小進(jìn)行重新排列，重復(fù)（排列，重復(fù)（2）的操作）的操作 ，直到最后只剩下兩個(gè)符號。，直到最后只剩下兩個(gè)符號。(4)從最后一級開始，向前返回得到各個(gè)信源符號所對應(yīng)的碼字。從最后一級開始，向前返回得到各個(gè)信源符號所對應(yīng)的碼字。 例題例題5-7：信源同例題：信源同例題5-4，進(jìn)行霍夫曼編碼，進(jìn)行霍夫曼編碼實(shí)際上，霍夫曼編碼也構(gòu)造了一個(gè)碼樹實(shí)際上，霍夫曼編碼也構(gòu)造了一個(gè)碼樹(根在右邊

42、根在右邊);非滿樹非滿樹.7個(gè)個(gè)端點(diǎn)端點(diǎn),表示表示7個(gè)信源符號。所以讀碼時(shí)，從最后一級向前返回。個(gè)信源符號。所以讀碼時(shí)，從最后一級向前返回。如：如： 從最右邊的從最右邊的“1”開始：開始：1(0.39)0(0.20)不再分，得不再分，得10是符號是符號a1的碼字；的碼字；1(0.39)1(0.19)不再分，得不再分，得11是符號是符號a2的碼字；的碼字；從最右邊的從最右邊的“0”開始：開始：0(0.61)1(0.26)1(0.11)0(0.10)，得，得0110是符號是符號a6的碼字的碼字碼元編碼輸出的信息率：/.(0.96bit 2.72612 K X)H R 比較：優(yōu)于香農(nóng)碼和費(fèi)諾碼。對于

43、該信源，香農(nóng)碼的編碼效率比較：優(yōu)于香農(nóng)碼和費(fèi)諾碼。對于該信源，香農(nóng)碼的編碼效率為為83.1%；費(fèi)諾碼編碼效率為；費(fèi)諾碼編碼效率為95.3%數(shù)學(xué)上可以證明霍夫曼碼是最佳編碼。數(shù)學(xué)上可以證明霍夫曼碼是最佳編碼。%/.( 962.72612KX)H 2m logmKX)H / 2.72KPK _71iii編碼效率：符號碼元：單符號編碼，平均碼長原因：原因：A.每次對信源縮減時(shí)，賦予信源最后兩個(gè)概率最小的符每次對信源縮減時(shí)，賦予信源最后兩個(gè)概率最小的符號，用號，用0和和1是可以任意的，所以可以得到不同的哈夫曼碼，但是可以任意的，所以可以得到不同的哈夫曼碼，但不會(huì)影響碼字的長度。不會(huì)影響碼字的長度。B.

44、對信源進(jìn)行縮減時(shí)，兩個(gè)概率最小的符號合并后的概率與其對信源進(jìn)行縮減時(shí)，兩個(gè)概率最小的符號合并后的概率與其它信源符號的概率相同時(shí)，這兩者在縮減信源中進(jìn)行概率排序，它信源符號的概率相同時(shí)，這兩者在縮減信源中進(jìn)行概率排序，其位置放置次序是可以任意的，故會(huì)得到不同的哈夫曼碼其位置放置次序是可以任意的，故會(huì)得到不同的哈夫曼碼,此此時(shí)將影響碼字的長度。時(shí)將影響碼字的長度。（2）信源縮減時(shí)，若合并后的新符號的概率與其它符號的概）信源縮減時(shí)，若合并后的新符號的概率與其它符號的概率相等，重新排序時(shí)，將新符號放置在上面，以減少再次合并率相等，重新排序時(shí)，將新符號放置在上面，以減少再次合并的次數(shù)，充分利用短碼，獲得

45、碼字長度方差較小的碼，提高碼的次數(shù)，充分利用短碼，獲得碼字長度方差較小的碼，提高碼的質(zhì)量。的質(zhì)量。 4、霍夫曼編碼的進(jìn)一步討論：、霍夫曼編碼的進(jìn)一步討論：（1）霍夫曼編碼方法得到的碼并非是唯一的）霍夫曼編碼方法得到的碼并非是唯一的例題例題5-8：如下信源，進(jìn)行霍夫曼編碼。信源縮減時(shí)新符號的概：如下信源，進(jìn)行霍夫曼編碼。信源縮減時(shí)新符號的概率與某一符號相同。重新排序時(shí)，新符號分別放置在該符號的率與某一符號相同。重新排序時(shí)，新符號分別放置在該符號的上面和下面，比較得到的編碼輸出有何區(qū)別。上面和下面，比較得到的編碼輸出有何區(qū)別。%( 96.5 K X)H / 2.2KPK 51iii符號；碼元兩種方

46、法都有：360K(KPKKE 361K(KPKKE 251iii2iK251iii2iKii.)(.)(：第二種方法的碼長方差：第一種方法的碼長方差 碼方差越大，說明碼長越分散，需要大容量的存儲(chǔ)器來緩碼方差越大，說明碼長越分散，需要大容量的存儲(chǔ)器來緩沖碼字長度的差異，給編碼器的實(shí)現(xiàn)增加難度。沖碼字長度的差異，給編碼器的實(shí)現(xiàn)增加難度。5、m進(jìn)制的霍夫曼編碼（如進(jìn)制的霍夫曼編碼（如m=3) 如果縮減到最后是剩下不到如果縮減到最后是剩下不到m個(gè)符號，就要添加無用的符個(gè)符號，就要添加無用的符號（使其概率為號（使其概率為0）。該例中）。該例中a7就是添加的符號。就是添加的符號。碼元編碼輸出的信息率：/.

47、(1.49bit 1.58352 K X)H R %.( 93.8lb3581352logmKX)H / 1.58KPK _71iii編碼效率：符號碼元：單符號編碼，平均碼長第三節(jié)第三節(jié) 限失真信源編碼定理限失真信源編碼定理即：香農(nóng)第三定理即：香農(nóng)第三定理 設(shè)有一離散、平穩(wěn)、無記憶信源，其率失真函數(shù)為設(shè)有一離散、平穩(wěn)、無記憶信源，其率失真函數(shù)為R(D)，則對任意選定的則對任意選定的D0，當(dāng)傳信率，當(dāng)傳信率RR(D)時(shí)，時(shí)， 只要信源序列長只要信源序列長度度L足夠長，必存在一種編碼方式足夠長，必存在一種編碼方式C，使譯碼后的失真，使譯碼后的失真 D+, 為任意小的正數(shù)為任意小的正數(shù) 。 反之反之

48、, 若若R0，平均碼長滿足不，平均碼長滿足不等式：等式：R(D)K R(D)解釋：在失真限度內(nèi)，使得信息率接近解釋：在失真限度內(nèi)，使得信息率接近R(D)的編碼方法是存的編碼方法是存在的。在的。R(D)是滿足保真度準(zhǔn)則的最小信息率。是滿足保真度準(zhǔn)則的最小信息率。n香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼主要是針對無香農(nóng)編碼、費(fèi)諾編碼、哈夫曼編碼主要是針對無記憶信源。當(dāng)信源有記憶時(shí)上述編碼效率不高；記憶信源。當(dāng)信源有記憶時(shí)上述編碼效率不高；n游程編碼、算術(shù)編碼等對相關(guān)信源編碼更有效；游程編碼、算術(shù)編碼等對相關(guān)信源編碼更有效； 游程編碼實(shí)際上是對哈夫曼編碼的改進(jìn)。游程編碼實(shí)際上是對哈夫曼編碼的改進(jìn)。n預(yù)測編碼

49、、矢量量化等是限失真編碼預(yù)測編碼、矢量量化等是限失真編碼n主要介紹游程編碼主要介紹游程編碼第四節(jié) 常用信源編碼方法簡介*一、游程編碼一、游程編碼n游程游程：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。：數(shù)字序列中連續(xù)出現(xiàn)相同符號的一段。n二元序列的游程：只有二元序列的游程：只有“0”和和“1”兩種符號。兩種符號。連連“0”這一段稱為這一段稱為“0”游程，它的長度稱為游程，它的長度稱為游程長度游程長度L(0)；連連“1”這一段稱為這一段稱為“1”游程，它的游程長度用游程，它的游程長度用L(1)表示。表示。1、二元獨(dú)立序列游程長度概率、二元獨(dú)立序列游程長度概率n若規(guī)定二元序列總是從若規(guī)定二元序列總是從“0”

50、開始。開始。n對于隨機(jī)序列對于隨機(jī)序列,游程長度是隨機(jī)的其取值可為游程長度是隨機(jī)的其取值可為1,2,3,直至無窮直至無窮n游程長度序列游程長度序列/游程序列：用交替出現(xiàn)的游程序列：用交替出現(xiàn)的“0”游程和游程和“1”游程長游程長度表示任意二元序列。度表示任意二元序列。n游程變換：是一種一一對應(yīng)的變換，也是可逆變換。游程變換：是一種一一對應(yīng)的變換，也是可逆變換。 例如：二元序列：例如：二元序列：000101110010001，可變換成如下游程序，可變換成如下游程序列：列：31132131n游程變換減弱了原序列符號間的相關(guān)性。游程變換減弱了原序列符號間的相關(guān)性。n游程變換將二元序列變換成了游程變換

51、將二元序列變換成了多元序列多元序列；這樣就適合于用其；這樣就適合于用其他方法，如哈夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。他方法，如哈夫曼編碼，進(jìn)一步壓縮信源，提高通信效率。n編碼方法：編碼方法：n首先測定首先測定“0”游程長度和游程長度和“1”游程長度的概率分布，即游程長度的概率分布，即以游程長度為元素，構(gòu)造一個(gè)新的信源；以游程長度為元素，構(gòu)造一個(gè)新的信源；n對新的信源（游程序列）進(jìn)行哈夫曼編碼。對新的信源（游程序列）進(jìn)行哈夫曼編碼。2、 二元獨(dú)立序列游程長度的熵二元獨(dú)立序列游程長度的熵n若二元序列的概率特性已知，由于二元序列與游程變換序列若二元序列的概率特性已知，由于二元序列與游程變換序列

52、的一一對應(yīng)性，可計(jì)算出游程序列的概率特性。的一一對應(yīng)性，可計(jì)算出游程序列的概率特性。n令令“0”和和“1”的概率分別為的概率分別為p0和和p1，則，則“0”游程長度游程長度L(0)的的概率為概率為 pL(0)=p0L(0)1p1 式中式中L(0)=1,2, 在計(jì)算在計(jì)算pL(0)時(shí)必然已有時(shí)必然已有“0”出現(xiàn)，否則就不是出現(xiàn)，否則就不是“0”游程，游程，若下一個(gè)符號是若下一個(gè)符號是“1”，則游程長度為，則游程長度為1，其概率是，其概率是p1 =1p0；若下一個(gè)符號為若下一個(gè)符號為“0”、再下一個(gè)符號為、再下一個(gè)符號為“1”，則游程長度為，則游程長度為2，其概率將為，其概率將為p0p1 ；依此類

53、推。；依此類推。n同理可得同理可得“1”游程長度游程長度L(1)的概率為：的概率為：PL(1)=p1L(1)-1p002(0) 11() (0) (0)log (0)LH pH Lp Lp Lp n“0”游程長度的熵：游程長度的熵：3、 二元獨(dú)立序列的平均游程長度二元獨(dú)立序列的平均游程長度n“0”游程序列的平均游程長度游程序列的平均游程長度n同理可得同理可得“1”游程長度的熵和平均游程長度游程長度的熵和平均游程長度(0) 1001(0) 1(0) 1(0)10(0) 1011234 (0)(0) (0)(0)1(1)1LLLLLlE LLp LLppdppdppxxxxx 0100()1 (1

54、) (1)H pH LlE Lpp4、 二元獨(dú)立序列的熵二元獨(dú)立序列的熵n“0”游程序列的熵與游程序列的熵與“1”游程長度的熵之和除以它們的平均游程游程長度的熵之和除以它們的平均游程長度之和，即為對應(yīng)原二元序列的熵長度之和，即為對應(yīng)原二元序列的熵H(X)n游程變換后符號熵沒有變。因?yàn)橛纬套儞Q是一一對應(yīng)的可逆變換，游程變換后符號熵沒有變。因?yàn)橛纬套儞Q是一一對應(yīng)的可逆變換，所以變換后熵值不變。所以變換后熵值不變。0101 (0) (1)()()()H LH LH XH pH plln游程變換有較好的去相關(guān)效果，因而對游程序列進(jìn)行哈夫曼游程變換有較好的去相關(guān)效果，因而對游程序列進(jìn)行哈夫曼編碼可獲得較

55、高的編碼效率。編碼可獲得較高的編碼效率。n假設(shè)假設(shè)“0”游程長度的哈夫曼編碼效率為游程長度的哈夫曼編碼效率為0，“1”游程長度的游程長度的哈夫曼編碼效率為哈夫曼編碼效率為1，由編碼效率的定義可得對應(yīng)二元序列，由編碼效率的定義可得對應(yīng)二元序列的編碼效率（信源熵和信息率之比為編碼效率的編碼效率（信源熵和信息率之比為編碼效率=H(X)/R）n當(dāng)當(dāng)“0”游程和游程和“1”游程的編碼效率都很高時(shí)，采用游程編游程的編碼效率都很高時(shí)，采用游程編碼的效率也很高，至少不會(huì)低于較小的那個(gè)效率。要想編碼的效率也很高，至少不會(huì)低于較小的那個(gè)效率。要想編碼效率盡可能高，應(yīng)盡可能提高熵值較大的游程編碼效率。碼效率盡可能高

56、，應(yīng)盡可能提高熵值較大的游程編碼效率。01 (0) (1)0101 (0) (1)H LH LH LH L假設(shè)，則有n算術(shù)編碼不同于哈夫曼碼，它算術(shù)編碼不同于哈夫曼碼，它是非分組（非塊）碼。是非分組（非塊）碼。它從全序它從全序列出發(fā)，考慮符號之間的關(guān)系來進(jìn)行編碼。列出發(fā)，考慮符號之間的關(guān)系來進(jìn)行編碼。n算術(shù)編碼利用了算術(shù)編碼利用了累積概率累積概率的概念。的概念。n算術(shù)碼主要的編碼方法是算術(shù)碼主要的編碼方法是計(jì)算輸入信源符號序列所對應(yīng)的區(qū)間計(jì)算輸入信源符號序列所對應(yīng)的區(qū)間n因?yàn)樵诰幋a過程中，每輸入一個(gè)符號要進(jìn)行乘法和加法運(yùn)算，因?yàn)樵诰幋a過程中，每輸入一個(gè)符號要進(jìn)行乘法和加法運(yùn)算，所以稱此編碼方法

57、為算術(shù)編碼所以稱此編碼方法為算術(shù)編碼二、算術(shù)編碼二、算術(shù)編碼1、設(shè)信源符號集、設(shè)信源符號集A=a1,a2,an，其相應(yīng)概率分布為，其相應(yīng)概率分布為P (ai)， P (ai) 0(i=1,2, ,n)n信源符號的累積分布函數(shù)為：信源符號的累積分布函數(shù)為： 所得累積分布函數(shù)為每臺(tái)級的下界值，則其區(qū)間為所得累積分布函數(shù)為每臺(tái)級的下界值，則其區(qū)間為0,1)左左閉右開區(qū)間。閉右開區(qū)間。 F (a1)=0 F (a2)=P (a1) F (a3)=P (a1)+P (a2) n當(dāng)當(dāng)A=0,1二元信源時(shí)：二元信源時(shí)： F (0)= 0，F(xiàn) (1)=P (0)n計(jì)算計(jì)算二元無記憶信源序列二元無記憶信源序列的

58、累積分布函數(shù)的累積分布函數(shù)n初始時(shí)：在初始時(shí)：在0,1)區(qū)間內(nèi)由區(qū)間內(nèi)由F (1)劃分成二個(gè)子區(qū)間劃分成二個(gè)子區(qū)間0,F (1)和和F (1),1)， F (1)= P (0)。n子區(qū)間子區(qū)間0,F (1)的寬度為的寬度為A(0)= P (0)，對應(yīng)于信源，對應(yīng)于信源符號符號“0”；n子區(qū)間子區(qū)間F (1),1)的寬度為的寬度為A(1)= P (1)，對應(yīng)于信源，對應(yīng)于信源符號符號“1”；n若輸入符號序列的第一個(gè)符號為若輸入符號序列的第一個(gè)符號為s s=“0”，落入，落入0,F (1)區(qū)間，得累積分布函數(shù)區(qū)間，得累積分布函數(shù)F (s s=“0”)= F (0)=0； n輸入第二個(gè)符號為輸入第二

59、個(gè)符號為“1”，s s=“01”ns s=“01”所對應(yīng)的區(qū)間是在區(qū)間所對應(yīng)的區(qū)間是在區(qū)間0,F (1)中進(jìn)行分割中進(jìn)行分割n符號序列符號序列“00”對應(yīng)的區(qū)間寬度為對應(yīng)的區(qū)間寬度為: A(00)=A(0)P (0)=P (0)P (0)=P (00)；n對應(yīng)的區(qū)間為對應(yīng)的區(qū)間為0,F (s=“01”)。n符號序列符號序列“01”對應(yīng)的區(qū)間寬度為對應(yīng)的區(qū)間寬度為 A(01)=A(0)P (1)=P (0)P (1)=P (01)= A(0)A(00)；n對應(yīng)的區(qū)間為對應(yīng)的區(qū)間為F (s=“01”),F (1)。n累積分布函數(shù)累積分布函數(shù)F (s s=“01”)=P (00)= P (0)P (

60、0) 輸入第三個(gè)符號為輸入第三個(gè)符號為“1”：n輸入序列可記做輸入序列可記做s s1=“011”（若第三個(gè)符號輸入為（若第三個(gè)符號輸入為“0”，可記做，可記做s s0=“010”）；）；n現(xiàn)在，輸入序列現(xiàn)在，輸入序列s s1=“011”對應(yīng)的區(qū)間是對區(qū)間對應(yīng)的區(qū)間是對區(qū)間F(s s),F(1)進(jìn)行分割；進(jìn)行分割；n序列序列s s0=“010”對應(yīng)的區(qū)間寬度為對應(yīng)的區(qū)間寬度為 A(s s=“010”)=A(s s=“01”) P(0)=A(s s) P(0) 其對應(yīng)的區(qū)間為其對應(yīng)的區(qū)間為F(s s), F(s s)+ A(s s) P(0)；n序列序列s s1=“011”對應(yīng)的區(qū)間寬度為對應(yīng)的區(qū)