信息論第5章無失真信源編碼

1、北京郵電大學(xué)北京郵電大學(xué) 信息與通信工程學(xué)院信息與通信工程學(xué)院一、一、概概述述二、定長碼二、定長碼三、變長碼三、變長碼四、哈夫曼編碼四、哈夫曼編碼五、幾種實(shí)用的信源編碼方法五、幾種實(shí)用的信源編碼方法一、一、信源信源編碼編碼器器二、二、信源信源編碼編碼的分的分類類三、分組碼三、分組碼1 ,qcc1 ,rbb1,qaaiica 編為1 ,qcc1 ,rbb1 ,qaa符號(hào)符號(hào) 點(diǎn)點(diǎn) 劃劃 字母間隔字母間隔 單詞間隔單詞間隔 電平電平 + -+ - - - - - - - 二進(jìn)代碼二進(jìn)代碼 1 0111000000000厚厚 德德 博博 學(xué)學(xué)敬敬 業(yè)業(yè) 樂樂 群群n分組碼：先分組再編碼。在分組碼中，

2、每一個(gè)碼字僅與分組碼：先分組再編碼。在分組碼中，每一個(gè)碼字僅與當(dāng)前輸入的信源當(dāng)前輸入的信源符號(hào)組符號(hào)組有關(guān)，與其他信源符號(hào)無關(guān)。有關(guān)，與其他信源符號(hào)無關(guān)。包括：定長碼、變長碼（包括：定長碼、變長碼（Huffman編碼、費(fèi)諾編碼編碼、費(fèi)諾編碼）n非分組碼：碼序列中的符號(hào)與信源序列中的符號(hào)無確定非分組碼：碼序列中的符號(hào)與信源序列中的符號(hào)無確定的對應(yīng)關(guān)系。例如算術(shù)編碼。的對應(yīng)關(guān)系。例如算術(shù)編碼。Y YN N必要條件必要條件Y YN Nkxk1,kkxxxkx)1 (21kjxxxj符號(hào)符號(hào) 碼碼A碼碼B碼碼C碼碼D碼碼E碼碼Fa 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10

3、 10 110 001 011d 10 11 11 111 0001 0111 nr2n一、一、無失真編碼條件無失真編碼條件 二、二、信源序列分信源序列分組組定理定理三、三、定定長碼長碼信源信源編碼編碼定理定理lrq rqNlrqlNloglog 或l227 5755. 427logl，l取00，任意給定都可以分成兩組的信源序列長度為0NN 0N總可以找到所有序列出所有序列出現(xiàn)概率之和現(xiàn)概率之和小于小于序列序列 出現(xiàn)的概率出現(xiàn)的概率 滿足：滿足：x( )p x)()(log1XHxpN(5.2.3)(5.2.3)證： 我們先證明（我們先證明（5. 2. 3）式。）式。 設(shè)信源符號(hào)集設(shè)信源符號(hào)集

4、為為 ， 各符號(hào)出現(xiàn)的概率分別為各符號(hào)出現(xiàn)的概率分別為 ， 為長度為為長度為 的序列，的序列， 為為 中符號(hào)中符號(hào)出現(xiàn)的次數(shù)。出現(xiàn)的次數(shù)。 將信源序列按下列原則分成兩將信源序列按下列原則分成兩 ： 、 ，其中，其中， ： （5. 2.4） ： 其它其它 根據(jù)根據(jù)大數(shù)定律大數(shù)定律，當(dāng)序列足夠長時(shí)，信源符號(hào)，當(dāng)序列足夠長時(shí)，信源符號(hào)出現(xiàn)的次數(shù)接近出現(xiàn)的次數(shù)接近 。因此，。因此， 中的序列的符號(hào)出中的序列的符號(hào)出 現(xiàn)的次數(shù)符合大數(shù)定律，稱典型序列。現(xiàn)的次數(shù)符合大數(shù)定律，稱典型序列。 12 ,qAa aaip12Nxx xxNiNxia1G2G1G :x,1, iiNpiqN 2G :xiaiNp1G

5、從（從（5. 2. 4）中可以看出，）中可以看出， 隨隨 的不同而改變。的不同而改變。 設(shè)設(shè) ，則對于，則對于 中的信源符號(hào)中的信源符號(hào) ，有，有 或或 ，其中，其中 由于信源是無記憶的，所以由于信源是無記憶的，所以 的概率為的概率為 ， 的自信息負(fù)值為：的自信息負(fù)值為： 1G1xGxia,1,iiNpiqN iiiNpN 1ix)(xpqNqNpp11xqiiipNxp1log)(log1()logqiiiiN pp 1( )logqiiiNH XNp所以所以選擇選擇 ，使得，使得 （5. 2. 5） 則式（則式（5. 2. 3）成立。）成立。1log ( )()logqiiip xH Xp

6、N11log( )()loglogqqiiiiip xH XppN1logqiip下面證明定理的后半部分。設(shè)下面證明定理的后半部分。設(shè) ， 根據(jù)（根據(jù)（5. 2. 3）式，有）式，有 （5. 2.6）因?yàn)樾旁词菬o記憶的，所以因?yàn)樾旁词菬o記憶的，所以 ，得到得到 （5. 2. 7）將（將（5. 2. 7）代入（）代入（5. 2. 6），得），得 （5. 2. 8）2Gx log( )()p xH XN)()()(1NxpxpxpNiixpxp1)(log)(log11log ()()Niip xH XN令令 , 可得可得 , 所以所以根據(jù)根據(jù)Chebyshev不等式：不等式： ，其中，其中 為隨

7、機(jī)變量；這樣就得到：為隨機(jī)變量；這樣就得到： （5. 2. 9）其中其中 ， ， 所以，所以， （5. 2. 10）log()iizp x( )()iE zH X 1111log ( )( )( )NNiiiiEp xE zH XNN2( )Varp2211:NriipzzzNN12( ,)Nzz zz11()NiizEzN2( )iVar z22log ( ):( )rp xpxH XNN其中，自信息的方差其中，自信息的方差 （5. 2. 11）取取 ，則當(dāng)，則當(dāng) ，)(log2ixpVar22221log( )( )log( )qiiiiEp xH XppH X220N0NN時(shí)22220N

8、N有, 1 ,:qipNNxii 0,202N0NN xNxp)(log1Gx設(shè))()(logXHNxp)()(log)(XHNxpXHN)()(2)(2XHNXHNxp)(2)(XHNxp)(xp)(2XNHN2)()(log1XHxpNGN1G1)(min2)(xpNNxGXHNG()2NHXGN)(2)(max1XHNGxGNxpN()(1)2N H XGN()()(1)22N H XN H XGN，)(2XNHGN)(2)(XNHxp)(2XNH1log( )()p xH XN()2NH XNqlrNlqr )(2XNHlr 2log q)(logXHrNl)(logXHrNl()2N

9、 H X ( )2lN H Xr)(logXHrNl);(lNYXIrlYlHYHYXHXHllNNlog)()()/()()()(XNHXHN0log)()/(rlXNHYXHlNlog (/)lrRN比信源特符號(hào)rlNH(X)RXHlog)(R() (/)NH XRl比碼特符號(hào)rRlog)(XHR )()1(22222XHN( ) ( )( )( )H XH XH XH X )(1XHlog()lrH XNlog(),lrH XRNR222570.960.4715(1 0.96)0.81110 4.13 10N50.96 , 10811. 041log4143log43)(SH4715.

10、0811. 041log4143log432222)()1(22222XHN4/14/3)(21sssPS不現(xiàn)實(shí)：編碼時(shí)延大，信源要求長一、一、異前置碼的性質(zhì)異前置碼的性質(zhì)二、二、變長碼變長碼信源信源編碼編碼定理定理全碼樹圖中每個(gè)葉子節(jié)點(diǎn)都在最底層，從左至右排列)(Kraft 11不等式qilirqlll,21 MlMlr1l11/llllrrrMM121 1()MqMMqiMMMllllllqllllllirrrrrrrrrMlKMllr11MKMKMqqlllllKKrrrrKl 碼字碼字 碼碼 個(gè)數(shù)個(gè)數(shù) 碼碼 長長 碼碼1碼碼2碼碼3 1 3 2 1 2 3 7 7 3 3 3 3 4

11、3 3 7 5 4 5 4543214443434343234551111113( )( )( )( )( )444444111qilirqlll,21 qkkklpl111Nqk kklp lN1log)(log)(rXHlrXH(1)證明不等式前半部證明不等式前半部iiiiiirlppprlXHlogloglog)(111log(1)log(log )()0iiiiilliiiiqliiippeprprerp110ilip r等式成立條件等式成立條件ilipr(2)證明不等式后半部證明不等式后半部111iililrpr log (1/)irilplog (1 /)irilp1iilpr1

12、log (1/)irilp 11iilpr1111loglogiqqiiiliipppr11(log )()(1)logqqii iiirpp llr1log)(log)1 ()(rXHlrlXHNrXHlrXH1log)(log)(NrXHlrXH1log)(log)(NX)(XHrrlRloglXHR)(1rlXHRXHlog)()(rXHllog)(1log)(rXHlrXHllog)(1(1/ )ilipr( )logH Xrl1201ss，1 11 22 12 20,10,110,111s ss ss ss s()10.811H Xll，1 1()(3/4) (3/4)9/16p s

13、s 1 2() (3/4) (1/4) 3/16p ss 2 1() (1/4) (3/4) 3/16p ss 2 2() (1/4) (1/4) 1/16p s s 27/32()0.811/(27/32)0.961H Xl2/ )16/1316/3316/3216/91 (l一、二一、二元哈夫曼編碼元哈夫曼編碼二、二、多元哈夫曼多元哈夫曼編碼編碼三、三、馬氏源的編碼馬氏源的編碼證明思路：證明思路：)(.)(1qapapqxx,.,11,qqaa11 ,.,qaa11 ,.,qaa12 21,.,qx xx 1,.,2iixxiq，11101qqqqxxxx若若 對信源對信源 是最優(yōu)的異前置

14、碼，則是最優(yōu)的異前置碼，則 對信源對信源 也是最優(yōu)的異前置碼也是最優(yōu)的異前置碼ixSixS11, qllSqllS,1 qqilq-illqii, 1 , 121 ,1qqqiqqiiqiiilplplplpl21111qqqqqqqqiiipplpplpplp111121)(.2SSS 字母信源54321,aaaaa)3 . 0(1a)25. 0(2a)25. 0(3a) 1 . 0(4a) 1 . 0(5a)3 . 0( 1a)25. 0( 2a)25. 0( 3a)2 . 0( 4a)3 . 0( 1a)25. 0( 2a)45. 0( 3a101010)55. 0( 1a)45. 0(

15、 2a101a2a3a4a5a信源符號(hào) 碼字 00 01 10 110 11154321,aaaaa)4 . 0(1a)2 . 0(2a)2 . 0(3a) 1 . 0(4a) 1 . 0(5a010101010001101101111a2a3a4a5a965. 02 . 212. 2)(lSH)/2.2( 231 . 0222 . 024 . 0信源符號(hào)碼元l122. 22) 1 . 0log1 . 0( 2)2 . 0log2 . 0(4 . 0log4 . 0)(SHilip2)4 . 0(1a)2 . 0(2a)2 . 0(3a) 1 . 0(4a) 1 . 0(5a010101011

16、0111011111a2a3a4a5a)/2.2(241 . 032 . 022 . 014 . 0信源符號(hào)碼元l010136. 12 . 241 . 041 . 032 . 022 . 014 . 016. 02 . 231 . 031 . 022 . 022 . 024 . 0)(22222222222222221iiillp000110110111方法1方法2(1)srrm碼樹圖中每個(gè)中間節(jié)點(diǎn)后續(xù)的枝數(shù)為m時(shí)稱滿樹;, 87654321,aaaaaaaa3r8sq32sm936. 03log7 . 1522. 2log)(rlXH)/(7 . 1信源符號(hào)碼元l符號(hào)比特/522. 2)(X

17、H3m9s )4 . 0(1a)2 . 0(2a) 1 . 0(3a) 1 . 0(4a)05. 0(5a)05. 0(6a)05. 0(7a)05. 0(8a01)0(9a21 . 02 . 00124 . 0012)4 . 0(1a)2 . 0(2a) 1 . 0(3a) 1 . 0(4a)05. 0(5a)05. 0(6a)05. 0(7a)05. 0(8a01011122021220221012101/21/21/41/21/40100ss(|),0,1,.,1ip a sj iq) 1,.,1 , 0(JjCjia)( jiy( )( ,)jjiiC a y)()()(,.,1100nnsisisiyyy01nx xx0s0sC00iax )(00siy00,s x1snx0s0sCmbbb.10)(10000.sikybbb)(00siy0ia0ia1s1sCmkkbbb.2100)(2111100.sikkkybbb)(11siy1ia0s01/21/21/41/21/4010編碼編碼 狀態(tài)狀態(tài)符號(hào)符號(hào) a b c a 10 b 0 0 c 1 11 01/2 1/21/4 1/2 1/4010abcabc iiiill，il13145 . 1138113205 . 122411211llllcba，13145 . 1138