信息论与编码理论第4章无失真信源编码习题解答(共10页)

1、精选优质文档-倾情为你奉上第4章 无失真信源编码习题及其参考答案4-1 有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F（1）求这些码中哪些是唯一可译码；（2）求哪些码是及时码；（3）对所有唯一可译码求出其平均码长。消息概率ABCDEFS11/200000000S21/400101101010100S31/160100111101101100101S41/160110111111011101101110S51/16100011111111010111110111S61/1610111011111011 4-2 设信源。对此次能源进行m元唯一可译编码，

2、其对应的码长为（l1,l2,l6）=(1,1,2,3,2,3)，求m值的最好下限。（提示：用kraft不等式） 4-3设信源为，编成这样的码：（000，001，010，011，100，101，110，111）。求（1）信源的符号熵；（2）这种码的编码效率；（3）相应的仙农码和费诺码。4-4求概率分布为信源的二元霍夫曼编码。讨论此码对于概率分布为的信源也是最佳二元码。4-5有两个信源X和Y如下：（1）用二元霍夫曼编码、仙农编码以及费诺编码对信源X和Y进行编码，并计算其平均码长和编码效率；（2）从X，Y两种不同信源来比较三种编码方法的优缺点。4-6设二元霍夫曼码为（00，01，10，11）和（0，

3、10，110，111），求出可以编得这样霍夫曼码的信源的所有概率分布。4-7设信源为，求其三元霍夫曼编码。4-8若某一信源有N个符号，并且每个符号等概率出现，对这个信源进行二元霍夫曼编码，问当N=2i和N=2i+1（i是正整数）时，每个码值的长度是多少？平均码长是多少？4-9现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。表中数字为相应像素上的灰度级。1111111111111111111111111111111111111111222222222222222223333333333444444444455555556666667777788888（1）不考虑图像的任何统计特性

4、，对图像进行二元等长编码，这幅图像共需要多少个二元符号描述？（2）若考虑图像的统计特性，求这幅图像的信源熵，并对每个灰度级进行二元霍夫曼编码，问平均每个像素需用多少二元符号表示。4-10在MPEG中为了提高数据压缩比，采用了_方法。 A运动补偿与运行估计 B.减少时域冗余与空间冗余 C帧内图像数据与帧间图像数据压缩 D.向前预测与向后预测4-11 JPEG中使用了_熵编码方法。 A.统计编码和算术编码 B.PCM编码和DPCM编码C.预测编码和变换编码 D.哈夫曼编码和自适应二进制算术编码4-12 简述常用信息编码方法的两类。4-13 简述等长编码和变长编码的特点，并举例说明。4-14已知信源

5、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。对二进制序列，求其二进制算术编码码字。4-18有四个符号a，b，c，d构成的简单序列Sabdac，各符号及其对应概率如表所示。应用算

6、术编码方法对S进行编码，并对结果进行解码。符号符号概率pia1/2b1/4c1/8d1/84-19简述游程编码的思想和方法。4-20简述JEPG算法的主要计算步骤，并详细说明每个步骤。4-21设二元信源的字母概率为P(0)=1/4,P(1)=3/4。若信源输出序列为10111（a） 对其进行算术编码并计算编码效率。（b） 对其进行LZ编码并计算编码效率。4-22设有二元信源符号集，输入信源符号序列为求其序列的字典编码。4-23一个离散记忆信源A=a,b,c,发出的字符串为bccacbcccccccccccaccca。试用LZ算法对序列编码，给出编码字典及发送码序列。4-24 用LZ算法对信源A

7、=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-3：(1)(2) 平均码长：码元/信源符号所以编码效率：(3) 仙农编码：信源符号符号概率加概率码长码字S1010S2210S33110S441110S5511110S66S77S87费诺码：信源符号符号概率编码码字码长S1001S210102S3101103S41011104S5101111

8、05S6106S7107S8174-5：(1) 霍夫曼编码：对X的霍夫曼编码如下：信源符号符号概率编码过程码长码字S10.20.20.260.350.390.610102S20.190.190.20.260.3500.391112S30.180.180.190.200.2610003S40.170.170.1800.1910013S50.150.1500.1710103S60.10010.11101104S70.0101114码元/信源符号 码元/符号Y的二元霍夫曼编码：信源符号符号概率编码过程码字码长S10.490.490.490.490.490.490.490.51011S20.140.1

9、40.140.140.140.230.2800.4910003S30.140.140.140.140.140.1400.2310013S40.070.070.070.090.1400.14101004S50.070.070.070.0700.09101014S60.040.040.0500.07101114S70.020.0300.041011015S80.0200.0216S90.0116平均码长：码元/信源符码元/符号编码效率：(2) 仙农编码：对X的仙农编码：信源符号符号概率和概率码长码字S10.203000S20.190.23001S30180.393011S40.170.573100

10、S50.150.743101S60.100.8941110S70.010.997平均码长：码元/信源符对Y的仙农编码：信源符号符号概率和概率码长码字S10.490200S20.140.493011S30.140.633101S40.070.7741100S50.070.8441101S60.040.91511101S70.020.956S80.020.976S90.010.997平均编码长度：码元/信源符编码效率：(3) 费诺编码：对X的费诺编码：信源符号符号概率编码码字码长S10.200002S20.19100103S30.1810113S40.1710102S50.15101103S60.

11、101011104S70.01111114平均编码长度：码元/信源符号编码效率：对Y进行费诺编码：信源符号符号概率编码码字码长S10.49001S20.141001003S30.1411013S40.0710011004S50.07111014S60.041011104S70.0210111105S80.02106S90.0116平均码长：码元/信源符号编码效率：(4) 由三种编码的编码效率可知：仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码效率最高，费诺码居中。4-7： 由三元编码方式可知：R=DB=RD-1(K2)+2由本题可知D=3，K=8，R=2，所以，首先合并

12、最后两个信源概率，其中一种编码方式如下：信源符号符号概率编码码字码长S10.40.40.40.4001S20.20.20.20.4121S30.10.10.200.22112S40.10.10.11122S50.050.100.121013S60.050.0511023S70.0500.05210004S80.051100144-16：符号uiP(ui)F(ui)码长二进制表示CC40.1110ACA50.11100BCAB60.ACABA90.符号分布概率：符号概率分布区间ABC译码：所以译码结果是：CABA4-21：(1)符号概率分布区间00.2510.75由题目可知信源符号为：1011 0111 1011 0111算术码的码长由序列S的分布函数F（S）由二元整树图来计算： 所以算术编码为：0100 0011 0011平均码长及编码效率如下：码元/符号 bit/符号(2)由于信源符号集中共有2个元素，因此只需要位二进制数