信息理论编码课程PPT 第4章 信源无失真编码

1、信源编码复习信源编码复习2XYWWUU3UWWU4 12, ,qu uu12, ,rx xxWU12, ,qw wwX:,1,2,iifuwiq 11()()qqiiiiiilP w lP u l 1()qiilP u ll 512341 21 41 81 8UUuuuuP 21112222223332444()0 ,1()10 ,2:()110 ,3()111,3fuwlfuwlffuwlfuwl 411111()222224882iiilP u l 411111()123324881.75iiilP u l 11111222113331444()00 ,2()01 ,2:()10 ,2()

2、11 ,2f uwlf uwlff uwlf uwl 。 。12, ,qu uu01，WU12, ,qw wwX6 iiP wP uiq ()()1,2, ,H WH U ()() H WH UH Xll ()()()H WH UH Xll ()()()R X, ,12rx xx12, ,qu uu12, ,rx xxWU12, ,qw wwX7 maxmax()()()()loglogcRH XH UlH URHXrlr1cc X, ,12rx xx12, ,qu uu12, ,rx xxWU12, ,qw wwX8f1f UWWU9105种不同的码种不同的码iP uWWWWWUuuuu35

3、1241234()1 200001001 401000010011 81010011100111 8111110111111W1：定长码。：定长码。W3：变长码。：变长码。奇异码。奇异码。定长非奇异码肯定是定长非奇异码肯定是UDC。u u u uu u u uu u u u u12434321121211,00,10,01100100110,01,00,11,00,1,00,1W2：定长码。：定长码。W4：变长码。：变长码。W5：变长码。：变长码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。非奇异码。续长码。续长码。非续长码。非续长码。续长码。续长码。及时码。及时码。

4、非及时码。非及时码。奇异码肯定不是奇异码肯定不是UDC。不是不是UDC。非续长码肯定是非续长码肯定是UDC。是是UDC。非及时码。非及时码。非续长码。非续长码。11码码奇异码奇异码非奇异码非奇异码非唯一可译码非唯一可译码唯一可译码唯一可译码定长非奇异码定长非奇异码变长非续长码变长非续长码（部分）变长续长码（部分）变长续长码12 00114w3w2w1w010001114w3w2w1w01114111w 10w 113011w 201w 13r12 ,ql ll11iqlir r412331222221ili 14 r12 ,ql ll11iqlir r15 12, ,qu uu12, ,rx

5、xxWU12, ,qw wwXX12, ,rx xx12, ,Nq 12, ,rx xxWNU12, ,Nqw wwXX12, ,rx xx12iiiiNu uu 1212,iiiNquuuu uu 16NlrNlNrq maxmax()log()loglogNrHUlqHUNrr()()/NH URH XlNmax()()()logcNH XH UlHXrN 12, ,Nq 12, ,rx xxWNU12, ,Nqw wwXX12, ,rx xx17。()()logNrlH UH UNr ()2()2logNrlH UH UNr 18123456723456611111112222222Uu

6、uuuuuuUP 1234567:001010011100101110111UuuuuuuuW7163()()log()32iiiH UP uP u 6332()65.625%log3 log2cH Ulr 3ll loglog72.8loglog2NlqlNr19()NrlH UN 1()NrlH UNNrUNNNlNlNllimlim()NrNNllH UN()()limlimlim100%logrcNNNH UH Ulrl 20例：对二元例：对二元DMS进行无失真编码：进行无失真编码：N=1414321uuPU符号/811. 034log434log41)43,41()(bitHUH若用

7、二元码符号若用二元码符号(0，1)进行定长编码：进行定长编码： 。平均码长平均码长 1 码元码元/信源符号信源符号1,021uul码元/811. 0)()(bitlUHXHR编码效率为编码效率为输出的信息效率输出的信息效率811. 0log)()()(max1rlUHXHXH要求：对比定长编码与变长编码的编码效率（要求：对比定长编码与变长编码的编码效率（N=2,3,4）。）。练习题21对对U的二次扩展信源进行定长编码，码表如下表的二次扩展信源进行定长编码，码表如下表 ：uip(ui)码字u1u19/1600u1u23/1601u2u13/1610u2u21/1611信源序列码元/2Nl编码效率

8、为编码效率为码字平均长度码字平均长度811. 0log)()()(max2rlUHXHXH单个符号的平均码长单个符号的平均码长信源符号码元/122NllNN=2N=3,4时，811. 04322对对U的二次扩展信源进行变长编码，码表如下表的二次扩展信源进行变长编码，码表如下表 ：uip(ui)码字u1u19/160u1u23/1610u2u13/16110u2u21/16111N=2信源序列码元/688. 13161316321631169Nl编码效率为编码效率为码字平均长度码字平均长度961. 0844. 0811. 0log)()()(max2rlUHXHXH单个符号的平均码长单个符号的平

9、均码长信源符号码元/844. 02688. 1NllNN=3,4时，991. 0,985. 04323分析：分析：1、比较定长编码与变长编码的编码效率可知，尤其在、比较定长编码与变长编码的编码效率可知，尤其在N较大时变长编码的效率远大于定长编码。较大时变长编码的效率远大于定长编码。N定长变长20.8110.96130.8110.98540.8110.991242、若对定长编码与变长编码同样要求编码效率达到、若对定长编码与变长编码同样要求编码效率达到96%，允许的译码错误概率允许的译码错误概率 时，定长编码所需序列长度时，定长编码所需序列长度N：510所需的信源序列长度：所需的信源序列长度：qi

10、iiUHuPuPU12224715. 0)()()log()(7522222221013. 410)96. 01 ()811. 0()96. 0(4715. 0)1 ()()(ccUHUN同样的编码效率，变长编码信源序列长度同样的编码效率，变长编码信源序列长度N=2时即可满足时即可满足编码效率达到编码效率达到96%的要求。随着的要求。随着N的增加，编码效率趋近的增加，编码效率趋近于于1。2526271101200130001400001500000160000006iu1 2u1u2u3u4u5u6u7()iP u41 251 261 261 221 231 24121221231251200

11、0000111111. 100123456723456611111112222222UuuuuuuuUP l2345661111111631234566222222232 cH Ulr63326332()100%loglog2 码元码元/符号符号 2829()63 32H U 3ll max()0.6562565.625%()log2cH XHX 63 32l max()1100%()log2cH XHX ()63 32()0.656253H UH Xl ()63 32()163 32H UH Xl max()63 32110.3()log7H UHU 10.34375cc 10cc 定长编码

12、：定长编码：001，010，011，100，101，110，111变长编码：变长编码：1，01，001，0001，00001，000001，000000123456723456611111112222222UuuuuuuuUP 30码字不唯一码字不唯一31 上例另一种霍夫曼编码：上例另一种霍夫曼编码：321101200130001400001500000160000006iuu1u2u3u4u5u6u7()iP u 12345670.350.3040.0050.005UUuuuuuuuP . 005. 065. 035. 015. 001. 100000000111111

13、.l 0 35 10 3020 2030 10 40 04 50 005 60 005 62 2133112102012001300014000015000005 .l 0 35 20 30 20 20 20 10 30 04 40 005 50 005 52 21. 005. 065. 035. 015. 001. 10000000011111112345670.350.3040.0050.005UUuuuuuuuP iuu1u2u3u4u5u6u7()iP u3411012001300014000015000001600000061121020120013000140

14、00015000005qiiiilE llP ull2221( )() ()() 码长方差：码长方差：l21( )1.4259 l22( )0.3059 码字不同，码长也不同，但码字不同，码长也不同，但平均码长相同，因此编码效平均码长相同，因此编码效率相同。率相同。3536211102201200230013 UUuuuuuuP1234560.360.080.04 qrr(1)23(0.12)(0.46)(1.00)0121201020.32 10.22 10.1820.1620.0830.0431.58l cH Ulr()2.3593.8%log1.58 log3 i

15、uu1u2u3u4u5u67u()iP u371230.450.350.20UUuuuP ()1.518H U 1001(1.00)(0.55)31()0.45 10.3520.2021.55iiilP u l ()1.51897.9%log1.55 log2cH Ulr 38. 016. 028. 01100001111. 0201. 10000. 04025. 059750011. 031751921()3.0675jjjlP u l 22()2 1.51899.0%log3.0675 log2cH Ulr 39400020103011310211031110411114 12345670

16、.1UUuuuuuuuP 00100001111171()0.20 20.19 30.18 30.1720.15 30.10 40.01 42.7 4iiilP u l ()2.6195%log2.74 log2cH Ulr 71()()log()2.61iiiH UP uP u 41log()log()1iiiP ulP u 1110()2,3,iikkPPP uiq 42消息符号消息符号ui消息概率消息概率pi-logpi码长码长li累加概率累加概率码字码字wiu10.202.3430000u20.192.4130.2001u30.182.

17、4830.39011u40.172.5630.57100u50.152.7430.74101u60.103.3440.891110u70.016.6670.991111110 对给定信源对给定信源 进行进行r =2进制香农编码。进制香农编码。1234567( )0.2 0.19 0.18 0.17 0.15 0.10 0.01iUuuuuuuuP u 3.14l 83.1%c 43比比 较较12345600.01UUuuuuuuuP 霍夫曼编码霍夫曼编码 费诺编码费诺编码 香农编码香农编码平均码长（码元平均码长（码元/符号）符号）2.722.74

18、3.14编码效率编码效率95.96%95.3%83.1%44用二元符号表用二元符号表 对其进行定长编码，若所对其进行定长编码，若所编的码为编的码为000，001，010，011，100，101，（1）对编码器输出码元的一维概率）对编码器输出码元的一维概率P(x1)与与P(x2)。（2）用二元符号表）用二元符号表 ，写出利用霍夫曼编，写出利用霍夫曼编码后的编码，并求编码后的码元的一维概率码后的编码，并求编码后的码元的一维概率P(x1)与与P(x2)、平均码长。平均码长。 设设DMS为为03. 007. 010. 018. 025. 037. 0654321uuuuuuPUU 1, 021xxX

19、1, 021xxX对对U进行霍夫曼编码，并求出平均码长进行霍夫曼编码，并求出平均码长 和编码效率和编码效率 。注：注： 设设DMS为为1 . 01 . 02 . 02 . 04 . 054321uuuuuPUUl322. 14 . 0log,322. 22 . 0log,322. 31 . 0log习题习题45用二元符号表用二元符号表 对其进行定长编码，对其进行定长编码，（1）求无失真定长编码的最小码长和编码效率。）求无失真定长编码的最小码长和编码效率。（2）将编码器的输出视为新信源）将编码器的输出视为新信源X，求，求H(X)；（3）若所编的码为）若所编的码为000，001，010，011，1

20、00，101，求，求编码器输出码元的一维概率编码器输出码元的一维概率P(x1)与与P(x2)。（4）若引入失真，要求差错率为）若引入失真，要求差错率为Pe=10-6，编码效率为，编码效率为90%，则需要对多长的信源符号序列进行编码？，则需要对多长的信源符号序列进行编码？（5）用二元符号表）用二元符号表 ，写出利用霍夫曼编，写出利用霍夫曼编码后的编码，并求平均码长、编码效率、编码后的码元的码后的编码，并求平均码长、编码效率、编码后的码元的一维概率一维概率P(x1)与与P(x2)。 设设DMS为为03. 007. 010. 018. 025. 037. 0654321uuuuuuPUU 1, 02

21、1xxX 1, 021xxX习题习题46对对U进行霍夫曼编码，并求出平均码长进行霍夫曼编码，并求出平均码长 和编码效率和编码效率 。注：注： 设设DMS为为1 . 01 . 02 . 02 . 04 . 054321uuuuuPUUl322. 14 . 0log,322. 22 . 0log,322. 31 . 0log习题习题47信源编码信源编码由于信源符号之间存在分布由于信源符号之间存在分布不均匀和相关性不均匀和相关性，使得信源存在，使得信源存在冗余度冗余度，的主要任务就是减少冗余，提高编码效率，提高通信的的主要任务就是减少冗余，提高编码效率，提高通信的；而；而的目的是降低差错率，提高传送的的目的是降低差错率，提高传送的。信源编码的基本途径有两个：信源编码的基本途径有两个： 使序列中的各个符号尽可能地互相独立，即解除相关性；使序列中的各个符号尽可能地互相独立，即解除相关性； 使编码中各个符号出现的概率尽可能地相等，即概率均匀化。使编码中各个符号出现的概率尽可能地相等，即概率均匀化。 无失真编