彭代渊王玲-信息论与编码理论-第四章习题解答.pdf

信息论与编码理论 1 第第 4 章章 无失真信源编码无失真信源编码 4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码 A、B、C、 D、E 和 F （1）求这些码中哪些是唯一可译码； （2）求哪些码是及时码； （3）对所有唯一可译码求出其平均码长l。 消息 概率 A B C D E F S1 1/2 000 0 0 0 0 0 S2 1/4 001 01 10 10 10 100 S3 1/16 010 011 110 110 1100 101 S4 1/16 011 0111 1110 1110 1101 110 S5 1/16 100 01111 11110 1011 1110 111 S6 1/16 101 011111 111110 1101 1111 011 4-2 设信源 6 126 1 126 ( )1 ( )()()() i i sssX p s p sp sp sP X 。对此次能源进行 m 元唯一 可译编码，其对应的码长为（l1,l2,l6）=(1,1,2,3,2,3)，求 m 值的最好下限。 （提示：用 kraft 不等式） 4-3 设信源为 12345678 11111111 () 248163264128128 ssssssss X p X ，编成这样的码： （000，001， 010，011，100，101，110，111） 。求 （1）信源的符号熵； （2）这种码的编码效率； （3）相应的仙农码和费诺码。 4-4 求概率分布为 1 1 122 (,) 3 5 5 15 15 信源的二元霍夫曼编码。讨论此码对于概率分布为 1 1 1 1 1 ( , ) 5 5 5 5 5 的信源也是最佳二元码。 4-5 有两个信源 X 和 Y 如下： 1234567 ()0.200.190.180.170.150.100.01 Xsssssss p X 123456789 ( )0.490.140.140.070.070.040.020.020.01 Ysssssssss p Y （1）用二元霍夫曼编码、仙农编码以及费诺编码对信源 X 和 Y 进行编码，并计算其平均码长和 信息论与编码理论 2 编码效率； （2）从 X，Y 两种不同信源来比较三种编码方法的优缺点。 4-6 设二元霍夫曼码为（00，01，10，11）和（0，10，110，111） ，求出可以编得这样 霍夫曼码的信源的所有概率分布。 4-7 设信源为 12345678 ()0.40.20.10.10.050.050.050.05 Xssssssss p X ，求其三元霍夫曼编 码。 4-8 若某一信源有 N 个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当 N=2i和 N=2i+1（i 是正整数）时，每个码值的长度是多少？平均码长是多少？ 4-9 现有一幅已离散量化后的图像，图像的灰度量化分成 8 级，如下表所示。表中数字为相应像素 上的灰度级。 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 8 8 8 8 8 （1）不考虑图像的任何统计特性，对图像进行二元等长编码，这幅图像共需要多少个二元符号 描述？ （2）若考虑图像的统计特性，求这幅图像的信源熵，并对每个灰度级进行二元霍夫曼编码，问 平均每个像素需用多少二元符号表示。 4-10 在 MPEG 中为了提高数据压缩比，采用了_方法。 A运动补偿与运行估计 B.减少时域冗余与空间冗余 C帧内图像数据与帧间图像数据压缩 D.向前预测与向后预测 4-11 JPEG 中使用了_熵编码方法。 A.统计编码和算术编码 B.PCM 编码和 DPCM 编码 C.预测编码和变换编码 D.哈夫曼编码和自适应二进制算术编码 4-12 简述常用信息编码方法的两类。 4-13 简述等长编码和变长编码的特点，并举例说明。 信息论与编码理论 3 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 离散无记忆信源发出 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 进行编码，并对结果进行解码。 符号 符号概率 pi a 1/2 b 1/4 c 1/8 d 1/8 4-19 简述游程编码的思想和方法。 4-20 简述 JEPG 算法的主要计算步骤，并详细说明每个步骤。 4-21 设二元信源的字母概率为 P(0)=1/4,P(1)=3/4。若信源输出序列为 1011011110110111 （a） 对其进行算术编码并计算编码效率。 （b） 对其进行 LZ 编码并计算编码效率。 4-22 设有二元信源符号集，输入信源符号序列为 10 1000 1 10 1 10 ,a a a a a a a a a a a a求其序列的字典编码。 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。 试据此构建译码字典并译出发送序列。 习题习题参考答案参考答案 4-1： (1) A、B、C、E 编码是唯一可译码。 (2) A、C、E 码是及时码。 (3) 唯一可译码的平均码长如下： 信息论与编码理论 4 6 1 111111 ( )3 ()3 2416161616 Aii i lp s l 码元/信源符号 6 1 111111 ( )1234562.125 2416161616 Bii i lp s l 码元/信源符号 6 1 111111 ( )1234562.125 2416161616 Cii i lp s l 码元/信源符号 6 1 111111 ( )12() 42 2416161616 Eii i lp s l 码元/信源符号 4-3： (1) /bit 8 ii i=1 H(X)=-p(x )logp(x ) 1111111111 =- log- log- log-log-log 224488 16163232 111111 -log-log-log 6464 128128 128128 63 =164符 (2) 平均码长： 6 1 11111111 ( )3 ()3 248163264128128 ii i lp s l 码元/信源符号 所以编码效率： () 0.6615 H X l (3) 仙农编码： 信源符号 i S 符号概率() i p S 加概率 码长 码字 S1 1 2 0 1 0 S2 1 4 1 2 2 10 S3 1 8 3 4 3 110 S4 1 16 7 8 4 1110 S5 1 32 15 16 5 11110 S6 1 64 31 32 6 111110 信息论与编码理论 5 S7 1 128 63 64 7 1111110 S8 1 128 127 128 7 1111111 费诺码： 信源符号 i S 符号概率() i p S 编码 码字 码长 S1 1 2 0 0 1 S2 1 4 1 0 10 2 S3 1 8 1 0 110 3 S4 1 16 1 0 1110 4 S5 1 32 1 0 11110 5 S6 1 64 1 0 111110 6 S7 1 128 1 0 1111110 7 S8 1 128 1 1111111 7 4-5： (1) 霍夫曼编码： 对 X 的霍夫曼编码如下： 信源 符号 i S 符号概 率 () i p S 编码过程 码长 码 字 S1 0.2 0.2 0.26 0.35 0.39 0.61 0 10 2 S2 0.19 0.19 0.2 0.26 0.35 0 0.39 1 11 2 S3 0.18 0.18 0.19 0.2 0 0.26 1 000 3 S4 0.17 0.17 0.18 0 0.19 1 001 3 S5 0.15 0.15 0 0.17 1 010 3 S6 0.10 0 1 0.11 1 0110 4 S7 0.01 0111 4 0.2 20.19 20.18 3 0.17 3 0.15 3 0.1 40.01 42.72l 码元/信源符号 7 1 ()log2.61 ii i H Xpp 码元/符号 信息论与编码理论 6 ()2.61 0.9596 2.72 H X l Y 的二元霍夫曼编码： 信 源 符 号 i S 符号 概率 () i p S 编码过程 码字 码 长 S1 0.49 0.49 0.49 0.49 0.49 0.49 0.49 0.51 0 1 1 S2 0.14 0.14 0.14 0.14 0.14 0.23 0.28 0 0.49 1 000 3 S3 0.14 0.14 0.14 0.14 0.14 0.14 0 0.23 1 001 3 S4 0.07 0.07 0.07 0.09 0.14 0 0.14 1 0100 4 S5 0.07 0.07 0.07 0.07 0 0.09 1 0101 4 S6 0.04 0.04 0.05 0 0.07 1 0111 4 S7 0.02 0.03 0 0.04 1 01101 5 S8 0.02 0 0.02 1 011000 6 S9 0.01 1 011001 6 平均码长： 0.49 1 0.14 3 20.07 4 20.04 40.02 50.02 60.01 62.23l 码元/信源符 9 1 ( )log2.31 ii i H Ypp 码元/符号 编码效率： ( )2.31 0.9914 2.33 H Y l (2) 仙农编码： 对 X 的仙农编码： 信源符号 i S 符号概率() i p S 和概率 码长 码字 S1 0.2 0 3 000 S2 0.19 0.2 3 001 S3 018 0.39 3 011 S4 0.17 0.57 3 100 S5 0.15 0.74 3 101 S6 0.10 0.89 4 1110 S7 0.01 0.99 7 1111110 平均码长： 0.2 3 0.19 3 0.18 3 0.17 3 0.15 3 0.1 40.01 73.14l 信息论与编码理论 7 码元/信源符 ()2.61 0.8312 3.14 H X l 对 Y 的仙农编码： 信源符号 i S 符号概率() i p S 和概率 码长 码字 S1 0.49 0 2 00 S2 0.14 0.49 3 011 S3 0.14 0.63 3 101 S4 0.07 0.77 4 1100 S5 0.07 0.84 4 1101 S6 0.04 0.91 5 11101 S7 0.02 0.95 6 111100 S8 0.02 0.97 6 111110 S9 0.01 0.99 7 1111110 平均编码长度： 0.49 20.14 20.07 4 20.04 50.02 6 20.02 60.01 72.89l 码元/信源符 编码效率： ( )2.31 0.7993 2.89 H Y l (3) 费诺编码： 对 X 的费诺编码： 信源符号 i S 符号概率() i p S 编码 码字 码长 S1 0.2 0 0 00 2 S2 0.19 1 0 010 3 S3 0.18 1 011 3 S4 0.17 1 0 10 2 S5 0.15 1 0 110 3 S6 0.10 1 0 1110 4 S7 0.01 1 1111 4 平均编码长度： 0.2 20.19 3 0.18 3 0.17 20.15 3 0.1 40.01 42.74l 码元/信源符号 编码效率： ()2.61 0.9526 2.74 H X l 对 Y 进行费诺编码： 信源符号 i S 符号概率() i p S 编码 码字 码长 S1 0.49 0 0 1 S2 0.14 1 0 0 100 3 信息论与编码理论 8 S3 0.14 1 101 3 S4 0.07 1 0 0 1100 4 S5 0.07 1 1101 4 S6 0.04 1 0 1110 4 S7 0.02 1 0 11110 5 S8 0.02 1 0 111110 6 S9 0.01 1 111111 6 平均码长： 0.49 1 0.14 2 3 0.07 4 20.04 40.02 50.02 60.01 62.33l 码元/信源符 号 编码效率： ( )2.31 0.9914 2.33 H Y l (4) 由三种编码的编码效率可知： 仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码效率最高，费诺 码居中。 4-7： 由三元编码方式可知：R=DB=RD-1(K2)+2 由本题可知 D=3，K=8，R=2，所以，首先合并最后两个信源概率，其中一种编码方式如下： 信源符号 i S 符号概率() i p S 编码 码字 码长 S1 0.4 0.4 0.4 0.4 0 0 1 S2 0.2 0.2 0.2 0.4 1 2 1 S3 0.1 0.1 0.2 0 0.2 2 11 2 S4 0.1 0.1 0.1 1 12 2 S5 0.05 0.1 0 0.1 2 101 3 S6 0.05 0.05 1 102 3 S7 0.05 0 0.05 2 1000 4 S8 0.05 1 1001 4 4-16： 符号 ui P(ui) F(ui) 码长 二进制表示 C C 1 9 8 9 4 0.1110 A CA 5 81 8 9 5 0.11100 B CAB 5 243 673 729 6 0.111011 A CABA 5 2187 673 729 9 0.111011000 符号分布概率： 符号 概率 分布区间 信息论与编码理论 9 A 9 5 9 5 , 0 B 1 3 5 8 , 9 9 C 1 9 8 ,1 9 译码： 4 6738 ()0.9292,1 7299 6738 5 7299 0.36280, 8 9 1 9 0.362805 8 0.6530, 5 9 9 1 9 5 0.6530 5 9 0.36280, 85 9 99 F u 第一字符是: C 第二字符是: A 第二字符是: B 第二字符是: A 所以译码结果是：CABA 4-21： (1) 符号 概率 分布区间 0 0.25 0,0.25 1 0.75 0.25,1 由题目可知信源符号为： 1011 0111 1011 011