信息论与编码理论第4章无失真信源编码习题解答20071202

1、信息论与编码理论 # 信息论与编码理论 #第4章无失真信源编码习题及其参考答案4-1有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F（1）求这些码中哪些是唯一可译码；（2）求哪些码是及时码；消息概率ABCDEFS1/200000000S21/400101101010100S31/160100111101101100101S1/160110111111011101101110S51/16100011111111010111110111S61/1610101111111111011011111011（3）对所有唯一可译码求出其平均码长l。_X，P(X)_

2、4-2设信源ss12p(s)p(s)12s6p(s)6可译编码，其对应的码长为（人）=（1，1，2,3,2,3），求_X，p(X)_4-3设信源为sss123111248sss64561113264艺p（s）1。对此次能源进行m元唯一ii=1m值的最好下限。（提示：用kraft不等式），编成这样的码：（000,001,010，011，100，101，110，111）。求（1）信源的符号熵；（2）这种码的编码效率；（3）相应的仙农码和费诺码。4-4求概率分布为（3,|,1,15，1|）信源的二元霍夫曼编码。讨论此码对于概率分布为（5,5,5,5,5）的信源也是最佳二元码。4-5有两个信源X和Y如

3、下:信息论与编码理论 # 信息论与编码理论 # #p(Y)Xsssssss,1234567p(X)0.200.190.180.170.150.100.01sssssssss,1234567890.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)，求出可以编得这样霍夫曼码的信源的所有概率分布。x1ssssssss4-7设信源为,123

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

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

6、举例说明。4-14已知信源X=x1=0.25,x2=0.25,x3=0.2,x4=0.15,x5=0.10,x6=0.05，试对其进行Huffman编码。4-15已知信源X=x1=1/4,x2=3/4,若x1=1,x2=0,试对1011进行算术编码。4-16离散无记忆信源发出A,B,C三种符号，其概率分布为5/9,1/3,1/9，应用算术编码方法对序列CABA进行编码,并对结果进行解码。4-17给定一个零记忆信源，已知其信源符号集为A=a1,a2=0,1,符号产生概率为P(aJ=1/4,P(a2)=3/4。对二进制序列11111100,求其二进制算术编码码字。4-18有四个符号a,b,c,d构

7、成的简单序列S=abdac，各符号及其对应概率如表所示。应用算术编码方法对S进行编码，并对结果进行解码。符号符号概率Pia1/2b1/4c1/8d1/84-19简述游程编码的思想和方法。4-20简述JEPG算法的主要计算步骤，并详细说明每个步骤。4-21设二元信源的字母概率为P(0)=1/4,P(1)=3/4。若信源输出序列为1011011110110111对其进行算术编码并计算编码效率。对其进行LZ编码并计算编码效率。4-22设有二元信源符号集，输入信源符号序列为aaaaaaaaaaaa,求其序列的字典编码。1010001101104-23一个离散记忆信源A=a,b,c,发出的字符串为bcc

8、acbcccccccccccaccca。试用LZ算法对序列编码,给出编码字典及发送码序列。4-24用LZ算法对信源A=a,b,c编码，其发送码字序列为：2,3,3,1,3,4,5,10,11,6,10。试据此构建译码字典并译出发送序列。习题参考答案4-1：A、B、C、E编码是唯一可译码。A、C、E码是及时码。唯一可译码的平均码长如下：Aiii1厂p(s)l3X(2，4，22，11-，召3码元/信源符号241616161661111111P(s)lX1X2+X3+X4+X5+X62125码元/信源符号Bii2416161616i161111111p(s)1X1+X2+X3+X4+X5+X62.1

9、25码元/信源符号Cii2416161616i161V1c/1111、/C一，亠、左1乙p(s)1X1+tx2+(+)X42码兀/信源符号Eii2416161616i14-3：(1)工一bit/符(2)平均码长：611111111、一亠、1p(S)13X(,，,，)3码元/信源符号ii248163264128128i1所以编码效率：H(X)0.66151(3)仙农编码：信源符号S符号概率P(S)加概率码长码字S12010S242210S333110S416741110S513215岳511110S616431药6111110S71128636471111110S8112812712871111

10、111费诺码：4-5：(1)霍夫曼编码对X的霍夫曼编码如下:信源符号Si符号概率p(S)i编码过程码长码字S10.20.20.260.350.390.610102S20.190.190.20.260.350/F0.391112S30.180.180.190.20/0.26z10003S40.170.170.1800.1910013S50.150.1500.1710103S60.10吹10.11101104S70.0101114l0.2x2,0.19x2,0.18x3,0.17x3,0.15x3,0.1x4,0.01x4=2.72码元/信源符号H(X)工plogp2.61码元/符号iii1H(X

11、)l2.720-9596信息论与编码理论 # #信息论与编码理论 Y的二元霍夫曼编码：信源符号Si符号概率p(S)i编码过程码字码长S10.490.490.490.490.490.490.490.51011S20.140.140.140.140.14f0.23/0.2800.4910003S30.140.140.140.140.140.14/00.2310013S40.070.070.070.09r0.1400.14101004S50.070.070.07/0.07.0.09101014S60.040.04/0.0500.07101114S70.020.03X0.041011015S80.02

12、/0.0210110006S90.0110110016平均码长：l0.49x10.14x3x20.07x4x20.04x40.02x50.02x60.01x6=2.23码元/信源符H(Y)Xplogp2.31码元/符号iii1编码效率：,H(Y)l2.31一_0.99142.33(2)仙农编码：对X的仙农编码:信源符号Si符号概率p(S)i和概率码长码字S10.203000S20.190.23001S30180.393011S40.170.573100S50.150.743101S60.100.8941110S70.010.9971111110平均码长：l0.2x3,0.19x3,0.18x3

13、,0.17x3,0.15x3,0.1x4,0.01x7=3.14码元/信源符-H(X)2618312对Y的仙农编码:信源符号Si符号概率p(S)i和概率码长码字S10.490200S20.140.493011S30.140.633101S40.070.7741100S50.070.8441101S60.040.91511101S70.020.956111100S80.020.976111110S90.010.9971111110平均编码长度：/0.49x2,0.14x2,0.07x4x2,0.04x5,0.02x6x2,0.02x6,0.01x7=2.89码元/信源符编码效率：n=H(Y)l2

14、.31=0.79932.89信息论与编码理论 # #信息论与编码理论 # #(3)费诺编码：对X的费诺编码：信源符号Si符号概率p(S)i编码码字码长S10.200002S20.19100103S30.1810113S40.1710102S50.15101103S60.101011104S70.01111114平均编码长度：l=0.2x2+0.19x3+0.18x3+0.17x2+0.15x3+0.1x4+0.01x4=2.74码元/信源符号编码效率：n=H:)lIS9526信息论与编码理论 # #信息论与编码理论 # #对Y进行费诺编码：信息论与编码理论 信源符号Si符号概率p(S)i编码码

15、字码长S10.49001S20.14001003S30.1411013S40.070011004S50.071111014S60.041011104S70.0210111105S80.021101111106S90.0111111116平均码长：l0.49x1,0.14x2x3,0.07x4x2,0.04x4,0.02x5,0.02x6,0.01x6=2.33码元/信源符编码效率：=日J=0.9914l由三种编码的编码效率可知：仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码效率最高，费诺码居中。4-7：由三元编码方式可知：R=DB=RD-1(K2)+2由本题可知D=3,

16、K=8,R=2，所以，首先合并最后两个信源概率，其中一种编码方式如下:信源符号Si符号概率p(S)i编码码字码长S10.40.40.40.4001S20.20.20.2*0.4121S30.10.10.20.22112S40.10.10.11122S50.05/0.10.121013S60.050.0511023S70.050.05210004S80.051100144-16：符号UiP(Ui)F(ui)码长一进制表示CC198940.1110ACA5818950.11100BCAB524367372960.111011ACABA567390.1110110002187729信息论与编码理论

17、#信息论与编码理论 # 符号分布概率：F(u4)=673729673-8729-9L9第二字符是A=0.36280,59丿0.3628-0“58,=0.6530el5-1L99丿9第二字符是B0.6530-5959=0.3628e所以译码结果是：CABA0,5符号概率分布区间00.25【0,0.25)10.75【0.25,1)4-21：(1)由题目可知信源符号为1011011110110111P(s=)=p(1)12p(0)4=(1)12(1)4=0.0001237信息论与编码理论 #算术码的码长l-logp(s)13由序列S的分布函数F(S)由二元整树图来计算：F(S)=1-p(11)p(10111)p(1011011111)p(1011011110111)p(1011011110110111)=1(4)22-A434信息论与编码理论 # #0.35114030.0101100110011所以算术编码为：010000110011平均码长及编码效率如下：-13l0.8125码元/符号16H(S)plogp(1)p(0)