信息论讲义_第十四讲

《信息论讲义_第十四讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息理论基础信息理论基础（第十四讲）（第十四讲）授课教师：于泽电子信息工程学院201教研室第五章无失真信源编码内容提要5.1编码器5.2分组码5.3定长编码5.4变长编码5.5变长编码方法—香农(Shannon)编码—霍夫曼(Huffman)编码—费诺(Fano)编码25.5.2霍夫曼编码(r元霍夫曼码)消息s概率码字码长ip(si)S1S2S3S4Wilis10.40.40110.4s20.20.210020.2s30.10.10.20020220.10.1s40.1012020.1s0.050.120025212s60.050.0521222s0.050.057010220103

2、s80.050110113s0390125.5.2霍夫曼编码(r元霍夫曼码)q平均码长Lp==∑()1.7siil三元码元/信源符号i=1编码速率R=⋅Lrlog=2.69比特/信源符号编码效率η=H()/SR=2.52/2.69=93.6%信息传输速率R=HSL()/=1.48比特/三元码元02102021110000220212210100114三元霍夫曼码树5.5.2霍夫曼(Huffman)编码（续）小结(1)Huffman码是唯一可译码，是紧致码。(2)Huffman码不是唯一的，但编码效率相同，且都是紧致码。评价Huffman码性能优劣—码方差q222σli=−=E[(lL

3、)]∑pslL()[(−)]iii=1(3)Huffman码只有在l=-logp(s)/logr时,达到下界ii(4)Huffman编码中，信源符号个数q同码符号个数r以及信源缩减次数θ存在如下关系:qr=(1−+)θr55.5.2霍夫曼(Huffman)编码（续）例设一个离散无记忆信源⎡⎤S⎡ss12=0=1⎤⎢⎥=⎢⎥⎣⎦P⎣0.90.1⎦试对以下三种情况将信源输出进行二进制霍夫曼编码，并求每个信源符号平均码长和编码效率①对每个信源符号进行编码②对每二个信源符号进行编码③对每三个信源符号进行编码65.5.2霍夫曼(Huffman)编码（续）⑴每个符号进行信源编码sp=0.9011

4、sp=0.1122平均码长：L=0.910.111×+×=12信源信息熵：H()Sp=−∑iilogp=0.4690biti=1HS()0.469编码效率：η===46.9%L1175.5.2霍夫曼(Huffman)编码（续）⑵对每二个信源（二维扩展）符号进行编码信源概率编码ss0.8100110.810.81ss101120.090.100.1911ss0.0910011100210.09ss101220.011011平均码长：L2=()0.8110.0920.0930.013×+×+×+×=0.6452编码效率：HS()0.4690η===73.86%L0.645285.5.2霍

5、夫曼(Huffman)编码（续）⑶对每三个信源（三维扩展）符号进行编码信源概率码字sss0.7290.7290.7290.7290.7290.7290.72900111sss0.0810.0810.0810.0810.1090.16200.271111210001sss1210.0810.0810.0810.0810.0810.1091011sss0.08100.0812110.0810.0810.08111001sss1220.0090.010.0180.02811100sss012120.0090.0090.01111011sss2210.00900.009111101sss22

6、20.0011111195.5.2霍夫曼(Huffman)编码（续）所以可计算出：平均码长：1L=()0.72910.081330.009530.0015×+××+××+×=0.532733编码效率：HU()0.4690η===88.04%L0.53273105.5.2霍夫曼(Huffman)编码（续）如果信源输出序列为ssssssssssss121111111121三次扩展信源编码后输出序列为10100101ssssssssssssggggg121111111121jgggggjgggggjgggggj115.5.2霍夫曼(Huffman)编码（续）¾霍夫曼编码是先给每一符号一片树

7、叶,逐步合并成节点直到树根。¾费诺码是从树根开始,把各节点分给某子集,若子集已是单点集,它就是一片树叶而作为码字。125.5.3费诺码消息si概率第一次第二次第三次第四次二元代码长p(s)分组分组分组分组码组is10.200002s20.190001031s30.1810113s40.170102s50.15011031s60.1010111041s70.01111114135.5.3费诺码（续）平均码长7Lp==∑()siil2.74二元码元/信源符号i