1、信息论与编码理论第4章无失真信源编码习题解答1202信息论与编码理论-第4章无失真信源编码-习题解答-20071202 信息论与编码理论 第4章 无失真信源编码 习题及其参考答案 4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F （1）求这些码中哪些是唯一可译码； （2）求哪些码是及时码； （3）对所有唯一可译码求出其平均码长。 ?X?s1 4-2 设信源?p(s)P(X)?1s6? p(s2)?p(s6)? ? s2 ?p(s)?1。对此次能源进行m元唯一 i i?1 6 可译编码，其对应的码长为（l1,l2,l6）=(1,1,2,3,2,
2、3)，求m值的最好下限。（提示：用kraft不等式） ?s ?X?1 4-3设信源为?1? ?p(X)?2? （1）信源的符号熵； （2）这种码的编码效率； s2 14s3s411816s5132s6s7s8? ，编成这样的码：（000，001，111?64128128? 010，011，100，101，110，111）。求 （3）相应的仙农码和费诺码。 4-4求概率分布为(, 11122 信)源的二元霍夫曼编码。讨论此码对于概率分布为3551515 11111 (,)的信源也是最佳二元码。 55555 4-5有两个信源X和Y如下： 1 信息论与编码理论 s2s3s4s5s6s7?X?s1 ?
3、p(X)?0.200.190.180.170.150.100.01? ?s2s3s4s5s6s7s8s9?Y?s1?p(Y)?0.490.140.140.070.070.040.020.020.01? ? （1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X和Y进行编码，并计算其平均码长和编码效率； （2）从X，Y两种不同信源来比较三种编码方法的优缺点。 4-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这样 霍夫曼码的信源的所有概率分布。 4-7设信源为?码。 4-8若某一信源有N个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当N=
4、2i和N=2i+1（i是正整数）时，每个码值的长度是多少？平均码长是多少？ 4-9现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。表中数字为相应像素上的灰度级。 （1）不考虑图像的任何统计特性，对图像进行二元等长编码，这幅图像共需要多少个二元符号描述？ （2）若考虑图像的统计特性，求这幅图像的信源熵，并对每个灰度级进行二元霍夫曼编码，问平均每个像素需用多少二元符号表示。 4-10在MPEG中为了提高数据压缩比，采用了_方法。 A运动补偿与运行估计 B.减少时域冗余与空间冗余 C帧内图像数据与帧间图像数据压缩 D.向前预测与向后预测 2 s2s3s4s5s6s7s8?X?s1 ?
5、0.40.20.10.10.050.050.050.05?，求其三元霍夫曼编 p(X)? 信息论与编码理论 4-11 JPEG中使用了_熵编码方法。 A.统计编码和算术编码 B.PCM编码和DPCM编码 C.预测编码和变换编码 D.哈夫曼编码和自适应二进制算术编码 4-12 简述常用信息编码方法的两类。 4-13 简述等长编码和变长编码的特点，并举例说明。 4-14已知信源Xx1=0.25,x2=0.25,x3=0.2,x4=0.15,x5=0.10,x6=0.05，试对其进行Huffman编码。 4-15已知信源Xx11/4，x23/4，若x11,x2，试对1011进行算术编码。 4-16离
6、散无记忆信源发出A，B，C三种符号，其概率分布为5/9，1/3，1/9，应用算术编码方法对序列CABA进行编码，并对结果进行解码。 4-17给定一个零记忆信源，已知其信源符号集为A=a1，a20，1，符号产生概率为P(a1)1/4，P(a2)3/4。对二进制序列11111100，求其二进制算术编码码字。 4-18有四个符号a，b，c，d构成的简单序列Sabdac，各符号及其对应概率如表所示。应用算术编码方法对S进行编码，并对结果进行解码。 符号 a b c d 4-19简述游程编码的思想和方法。 4-20简述JEPG算法的主要计算步骤，并详细说明每个步骤。 4-21设二元信源的字母概率为P(0
7、)=1/4,P(1)=3/4。若信源输出序列为1011011110110111 （a） 对其进行算术编码并计算编码效率。 （b） 对其进行LZ编码并计算编码效率。 4-22设有二元信源符号集，输入信源符号序列为a1a0a1a0a0a0a1a1a0a1a1a0?,求其序列的字典编码。 4-23一个离散记忆信源A=a,b,c,发出的字符串为bccacbcccccccccccaccca。试用LZ算法对序列编码，给出编码字典及发送码序列。 4-24 用LZ算法对信源A=a,b,c编码，其发送码字序列为：2，3，3，1，3，4，5，10，11，6，10。试据此构建译码字典并译出发送序列。 符号概率pi
8、1/2 1/4 1/8 1/8 习题参考答案 3 信息论与编码理论 4-1： (1) A、B、C、E编码是唯一可译码。 (2) A、C、E码是及时码。 (3) 唯一可译码的平均码长如下： 111111 lA?p(si)li?3?(?)?3 码元/信源符号 2416161616i?1 111111 lB?p(si)li?1?2?3?4?5?6?2.125码元/信源符号 2416161616i?1111111 lC?p(si)li?1?2?3?4?5?6?2.125码元/信源符号 2416161616i?1111111 lE?p(si)li?1?2?(?)?4?2码元/信源符号 241616161
9、6i?1 4-3： (1) 666 6 H(X)=-?p(xi)logp(xi) i=1 8 1111111111=-log-log-log-log-log22448816163232 111111 -log-log-log 646412812812812863 =1bit/符64 (2) 平均码长： 11111111 l?p(si)li?3?(?)?3码元/信源符号 248163264128128i?1 所以编码效率：?4 6 H(X) ?0.6615 l 信息论与编码理论 4-5： (1) 霍夫曼编码： l?0.2?2?0.19?2?0.18?3?0.17?3?0.15?3?0.1?4?0
10、.01?4?2.72码元/信源符号 5 信息论与编码理论 7 H(X)?pilogpi?2.61 码元/符号 i?1 ? H(X)2.61 ?0.9596 2.72l 平均码长： l?0.49?1?0.14?3?2?0.07?4?2?0.04?4?0.02?5?0.02?6?0.01?6?2.23码元/信源符 H(Y)?pilogpi?2.31码元/符号 i?19 编码效率：? H(Y)2.31 ?0.9914 2.33l (2) 仙农编码： 6 信息论与编码理论 平均码长： l?0.2?3?0.19?3?0.18?3?0.17?3?0.15?3?0.1?4?0.01?7?3.14 码元/信源
11、符 ? H(X)2.61 ?0.8312 3.14l 平均编码长度： l?0.49?2?0.14?2?0.07?4?2?0.04?5?0.02?6?2?0.02?6?0.01?7?2.89码元/信源符 编码效率：? H(Y)2.31 ?0.7993 2.89l (3) 费诺编码： 对X的费诺编码： l?0.2?2?0.19?3?0.18?3?0.17?2?0.15?3?0.1?4?0.01?4?2.74 码元/信源符号 编码效率：? H(X)2.61 ?0.9526 2.74l 对Y进行费诺编码： 7 信息论与编码理论 l?0.49?1?0.14?2?3?0.07?4?2?0.04?4?0.0
12、2?5?0.02?6?0.01?6?2.33码元/信源符 号 编码效率：? H(Y)2.31 ?0.9914 2.33l (4) 由三种编码的编码效率可知： 仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码效率最高，费诺码居中。 4-7： 由三元编码方式可知：R=DB=RD-1(K2)+2 由本题可知D=3，K=8，R=2，所以，首先合并最后两个信源概率，其中一种编码方式如下： 8 信息论与编码理论 译码： 673?8?0.9292?,1?729?9? ?第一字符是:CF(u4)? 6738?0.3628? 0,5?89?1?9 ?第二字符是:A 0.3628?0?58?
13、0.6530?,?5?99?19 ?第二字符是:B 5 ?0.3628?0,5?9?99 ?第二字符是:A0.6530? 所以译码结果是：CABA 4-21： 1011 0111 1011 0111 p(s?1011 0111 1011 0111) 31214124?p(1)p(0)?()()?0.000123744 9 信息论与编码理论 算术码的码长l?logp(s)?13 由序列S的分布函数F（S）由二元整树图来计算： F(S)?1?p(11)?p(10111)?p(1011011111)?p(1011011110111)?p(1011011110110111)331313131?1?()
14、2?()4()?()8()2?()10()3?()12()4.010* 所以算术编码为：0100 0011 0011 平均码长及编码效率如下： l? 13 ?0.8125码元/符号 16 H(S)?p(1)logp(1)?p(0)logp(0)?0.8113 bit/符号 ? (2) H(S) ?0.9985 l 由于信源符号集中共有2个元素，因此只需要?log2?1位二进制数就可以表示其编码，该符号集的编码表如下： 按照分段规则，分段为：1 0 11 01 111 011 0111 短语数为7，可用n?log7?3位来表示段号； 每个信源符号编码长度为1，所以短语长度为：3+1=4，具体编码过程如下： 平均编码长度：l? ?1.75码元/符号 16 H(S)0.8113 ?0.4636 编码效率为：? 1.7510
