信息论第5章无失真信源编码

1、北京邮电大学北京邮电大学 信息与通信工程学院信息与通信工程学院一、一、概概述述二、定长码二、定长码三、变长码三、变长码四、哈夫曼编码四、哈夫曼编码五、几种实用的信源编码方法五、几种实用的信源编码方法一、一、信源信源编码编码器器二、二、信源信源编码编码的分的分类类三、分组码三、分组码1 ,qcc1 ,rbb1,qaaiica 编为1 ,qcc1 ,rbb1 ,qaa符号符号 点点 划划 字母间隔字母间隔 单词间隔单词间隔 电平电平 + -+ - - - - - - - 二进代码二进代码 1 0111000000000厚厚 德德 博博 学学敬敬 业业 乐乐 群群n分组码：先分组再编码。在分组码中，

2、每一个码字仅与分组码：先分组再编码。在分组码中，每一个码字仅与当前输入的信源当前输入的信源符号组符号组有关，与其他信源符号无关。有关，与其他信源符号无关。包括：定长码、变长码（包括：定长码、变长码（Huffman编码、费诺编码编码、费诺编码）n非分组码：码序列中的符号与信源序列中的符号无确定非分组码：码序列中的符号与信源序列中的符号无确定的对应关系。例如算术编码。的对应关系。例如算术编码。Y YN N必要条件必要条件Y YN Nkxk1,kkxxxkx)1 (21kjxxxj符号符号 码码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总可以找到所有序列出所有序列出现概率之和现概率之和小于小于序列序列 出现的概率出现的概率 满足：满足：x( )p x)()(log1XHxpN(5.2.3)(5.2.3)证： 我们先证明（我们先证明（5. 2. 3）式。）式。 设信源符号集设信源符号集

4、为为 ， 各符号出现的概率分别为各符号出现的概率分别为 ， 为长度为为长度为 的序列，的序列， 为为 中符号中符号出现的次数。出现的次数。 将信源序列按下列原则分成两将信源序列按下列原则分成两 ： 、 ，其中，其中， ： （5. 2.4） ： 其它其它 根据根据大数定律大数定律，当序列足够长时，信源符号，当序列足够长时，信源符号出现的次数接近出现的次数接近 。因此，。因此， 中的序列的符号出中的序列的符号出 现的次数符合大数定律，称典型序列。现的次数符合大数定律，称典型序列。 12 ,qAa aaip12Nxx xxNiNxia1G2G1G :x,1, iiNpiqN 2G :xiaiNp1G

5、从（从（5. 2. 4）中可以看出，）中可以看出， 随随 的不同而改变。的不同而改变。 设设 ，则对于，则对于 中的信源符号中的信源符号 ，有，有 或或 ，其中，其中 由于信源是无记忆的，所以由于信源是无记忆的，所以 的概率为的概率为 ， 的自信息负值为：的自信息负值为： 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下面证明定理的后半部分。设下面证明定理的后半部分。设 ， 根据（根据（5. 2. 3）式，有）式，有 （5. 2.6）因为信源是无记忆的，所以因为信源是无记忆的，所以 ，得到得到 （5. 2. 7）将（将（5. 2. 7）代入（）代入（5. 2. 6），得），得 （5. 2. 8）2Gx log( )()p xH XN)()()(1NxpxpxpNiixpxp1)(log)(log11log ()()Niip xH XN令令 , 可得可得 , 所以所以根据根据Chebyshev不等式：不等式： ，其中，其中 为随

7、机变量；这样就得到：为随机变量；这样就得到： （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）取取 ，则当，则当 ，)(log2ixpVar22221log( )( )log( )qiiiiEp xH XppH X220N0NN时22220N

8、N有, 1 ,:qipNNxii 0,202N0NN xNxp)(log1Gx设)()(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比信源特符号rlNH(X)RXHlog)(R() (/)NH XRl比码特符号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不现实：编码时延大，信源要求长一、一、异前置码的性质异前置码的性质二、二、变长码变长码信源信源编码编码定理定理全码树图中每个叶子节点都在最底层，从左至右排列)(Kraft 11不等式qilirqlll,21 MlMlr1l11/llllrrrMM121 1()MqMMqiMMMllllllqllllllirrrrrrrrrMlKMllr11MKMKMqqlllllKKrrrrKl 码字码字 码码 个数个数 码码 长长 码码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若若 对信源对信源 是最优的异前置

14、码，则是最优的异前置码，则 对信源对信源 也是最优的异前置码也是最优的异前置码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信源符号 码字 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信源符号码元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信源符号码元l010136. 12 . 241 . 041 . 032 . 022 . 014 . 016. 02 . 231 . 031 . 022 . 022 . 024 . 0)(22222222222222221iiillp000110110111方法1方法2(1)srrm码树图中每个中间节点后续的枝数为m时称满树;, 87654321,aaaaaaaa3r8sq32sm936. 03log7 . 1522. 2log)(rlXH)/(7 . 1信源符号码元l符号比特/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编码编码 状态状态符号符号 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