个人收集整理-仅供参考 1 / 12 Equation Chapter 1 Section 1 第4章 无失真信源编码
习题及其参考答案 4-1 有一信源，它有六个可能地输出，其概率分布如下表所示，表中给出了对应地码A、B、C、D、E和F （1）求这些码中哪些是唯一可译码； （2）求哪些码是及时码；
（3）对所有唯一可译码求出其平均码长. 消息 概率 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 设信源.对此次能源进行m元唯一可译编码，其对应地码长为（l1,l2,…,l6）=(1,1,2,3,2,3)，求m值地最好下限.（提示：用kraft不等式） b5E2R。
4-3设信源为，编成这样地码：（000，001，010，011，100，101，110，111）.求 （1）信源地符号熵； （2）这种码地编码效率； （3）相应地仙农码和费诺码.
4-4求概率分布为信源地二元霍夫曼编码.讨论此码对于概率分布为
地信源也是最佳二元码. 4-5有两个信源X和Y如下： 个人收集整理-仅供参考 2 / 12 （1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X和Y进行编码，并计算其平均码长和编码效率； （2）从X，Y两种不同信源来比较三种编码方法地优缺点. 4-6设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这样 霍夫曼码地信源地所有概率分布.
4-7设信源为，求其三元霍夫曼编码. 4-8若某一信源有N个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当N=2i和N=2i+1（i是正整数）时，每个码值地长度是多少？平均码长是多少？p1Ean。
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）若考虑图像地统计特性，求这幅图像地信源熵，并对每个灰度级进行二元霍夫曼编码，问平均每个像素需用多少二元符号表示.DXDiT。
4-10在MPEG中为了提高数据压缩比，采用了____方法.
A．运动补偿与运行估计 B.减少时域冗余与空间冗余 C．帧内图像数据与帧间图像数据压缩 D.向前预测与向后预测 4-11 JPEG中使用了____熵编码方法. 个人收集整理-仅供参考 3 / 12 A.统计编码和算术编码 B.PCM编码和DPCM编码 C.预测编码和变换编码 D.哈夫曼编码和自适应二进制算术编码 4-12 简述常用信息编码方法地两类. 4-13 简述等长编码和变长编码地特点，并举例说明. 4-14已知信源X＝[x1=0.25,x2=0.25,x3=0.2,x4=0.15,x5=0.10,x6=0.05]，试对其进行Huffman编码.RTCrp。
4-15已知信源X＝[x1＝1/4，x2＝3/4]，若x1＝1,x2＝０，试对1011进行算术编码. 4-16离散无记忆信源发出A，B，C三种符号，其概率分布为5/9，1/3，1/9，应用算术编码方法对序列CABA进行编码，并对结果进行解码.5PCzV。
4-17给定一个零记忆信源，已知其信源符号集为A=｛a1，a2｝＝｛0，1｝，符号产生概率为P(a1)＝1/4，P(a2)＝3/4.对二进制序列11111100，求其二进制算术编码码字.jLBHr。
4-18有四个符号a，b，c，d构成地简单序列S＝abdac，各符号及其对应概率如表所示.应用算术编码方法对S进行编码，并对结果进行解码.xHAQX。
符号 符号概率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.若信源输出序列为1011011110110111LDAYt。
（a） 对其进行算术编码并计算编码效率. （b） 对其进行LZ编码并计算编码效率. 4-22设有二元信源符号集，输入信源符号序列为求其序列地字典编码. 4-23一个离散记忆信源A={a,b,c},发出地字符串为bccacbcccccccccccaccca.试用LZ算法对序列编码，给出编码字典及发送码序列.Zzz6Z。
4-24 用LZ算法对信源A={a,b,c}编码，其发送码字序列为：2，3，3，1，3，4，5，10，11，6，10.试据此构建译码字典并译出发送序列.dvzfv。
习题参考答案 个人收集整理-仅供参考 4 / 12 4-1： (1) A、B、C、E编码是唯一可译码. (2) A、C、E码是及时码. (3) 唯一可译码地平均码长如下：
码元/信源符号
码元/信源符号 码元/信源符号 码元/信源符号 4-3： (1)
(2) 平均码长： 码元/信源符号
所以编码效率： (3) 仙农编码： 信源符号 符号概率 加概率 码长 码字
S1 0 1 0 S2 2 10 S3 3 110 S4 4 1110 个人收集整理-仅供参考 5 / 12 S5 5 11110 S6 6 111110 S7 7 1111110 S8 7 1111111 费诺码： 信源符号 符号概率 编码 码字 码长
S1 0 0 1 S2 1 0 10 2 S3 1 0 110 3 S4 1 0 1110 4 S5 1 0 11110 5 S6 1 0 111110 6 S7 1 0 1111110 7 S8 1 1111111 7
4-5： (1) 霍夫曼编码： 对X地霍夫曼编码如下： 信源符号 符号概率 编码过程 码长 码字
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
码元/信源符号 个人收集整理-仅供参考 6 / 12 码元/符号
Y地二元霍夫曼编码： 信源符号 符号概率 编码过程 码字 码长
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
平均码长： 码元/信源符
码元/符号
编码效率： (2) 仙农编码： 对X地仙农编码：
信源符号 符号概率 和概率 码长 码字
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 个人收集整理-仅供参考 7 / 12 平均码长：
码元/信源符
对Y地仙农编码： 信源符号 符号概率 和概率 码长 码字
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 平均编码长度：
码元/信源符
编码效率： (3) 费诺编码： 对X地费诺编码：
信源符号 符号概率 编码 码字 码长
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 平均编码长度：
码元/信源符号 编码效率： 对Y进行费诺编码：