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

1、第4章无失真信源编码习题及其参考答案4-1有一信源，它有六个可能的输出，其概率分布如下表所示，表中给出了对应的码A、B、C、D、E和F(1)求这些码中哪些是唯一可译码；(2)求哪些码是及时码；(3)对所有唯一可译码求出其平均码长。消息概率ABCDEFS11/200000000S21/400101101010100S31/160100111101101100101S41/160110111111011101101110S51/16100011111111010111110111S61/1610101111111111011011111011Xsss64-2设信源|Zp(s)=1。对此次能源进行m

2、兀唯一>(x)j1p(s)p(s2)rnpg)一i可译编码，其对应的码长为di,l2,-J)=(1,1,2,3,2,3),求m值的最好下限。(提示：用kraft不等式)4-3设信源为bX)s214S318s4s5s6s71111163264128SI1128,编成这样的码:(000,001,010,011,100,101,110,111)。求(1)信源的符号嫡；(2)这种码的编码效率；(3)相应的仙农码和费诺码。，、八一11124-4求概率分布为(一，一，一,3551515)言源的二元霍夫曼编码。讨论此码对于概率分布为(1,1,1,1,1)的信源也是最佳二元码。555554-5有两个信源

3、X和Y如下：X_S1s2s3s4p(X)1(0.200.190.180.17s5s6s70.150.100.01；Y1_；5s2s3s4与%(丫)_卜.490.140.140.070.07s6s70.040.02s840.020.01X和Y进行编码,f算其平均码长和(1)用二元霍夫曼编码、仙农编码以及费诺编码对信源编码效率；(2)从X,Y两种不同信源来比较三种编码方法的优缺点。4-6设二元霍夫曼码为(00,01,10,霍夫曼码的信源的所有概率分布。11)和(0,10,110,111),求出可以编得这样码。4-7设信源为X5!p(X)10.40.2S30.1s4S50.10.05s6s7&quo

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

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

6、,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,32=0,1,符号产生概率为P(a1)=1/4,P(a2)=3/4。对二进制序列11111100,求其二进制算术编码码字。4-18有四个符号a,b,c,d构成的简单序列S=abdac,各符号及其对应概率如表所示。使用算术编码方法对S进行编码，并对结果进行解码。

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

8、信源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码是及时码。_61a='p(s)lii1(3)唯一可译码的平均码长如下：)=3码元/信源符号:3(1.1.±.±.±.±24161616166二p(s)lii1=1123451616161+x62.125码兀/信源将节1661C=ZP(si)lii1111111二一父1+父2+*3+乂4+x5+x6=2.125码兀/信源付节2416161616_

9、617=Ep(s)ii4111111=_父1+_父2+(+)x4=2码兀/信源符号24161616164-3:8H(X)=-p(xj10gp(xi)i=11111111111=-log-log-log-log一一一log22448816163232111111-log-log-log6464128128128128.634=1bit/符64平均码长：l=Ep(si)li=3父(一十一十一十十十十+)=3码兀/信源符号y248163264128128所以编码效率：=旦3=0.6615l(2)仙农编码:信源符号Si符号概率p(Si)加概率码长码字Si12010S21412210S383431101

10、7S416841110S51321516511110S616431326111110S7163712864S811281271287费诺码:信源符号Si符号概率p(Si)编码码字码长Si12001S21410102S318101103S41161011104S513210111105S6164101111106S71128107S81128174-5:霍夫曼编码：对X的霍夫曼编码如下:信源符号Si符号概率P(S)编码过程码长码字Si0.20.2r0.260.350.390.61.0102S20.190.190.20.2600.35_0/尸0.391112S30.180.180.190.20/0

11、.2610003S40.170.170.18I100.1910013S50.150.1500.17110103S60.1010.11101104S70.0101114l=0.2父2+0.19父2+0.18父3+0.17父3+0.15父3+0.1父4+0.01父4=2.72码元/信源符号7H(X)=£Pi10gpi=2.61码元/符号i1=3=型=0.95962.72Y的二元霍夫曼编码:信源符号Si符号概率P(Si)编码过程码字码长S10.4940.490.49/0.4920.49/0.49/0.4900.51011S20.140.140.140.140.1400.230.280.49

12、10003S30.140.140.140.140.140.14,/00.2310013S40.070.070.07.0.09,0.1400.14101004S50.070.070.0700.07,分0.09101014S60.040.040.0500.07101114S70.02<0.030.041011015S80.02/0.0210110006S90.0110110016平均码长：l=0.49父1+0.14父3父2+0.07x4x2+0,04x4+0,02x5+0,02x6+0.01父6=2.23码元/信源符9H(Y)=£plogPi=2.31码元/符号i44H(Y)2.3

13、1编码效率：=M=0.9914l2.33(2)仙农编码：对X的仙农编码：信源符号S符号概率p(S)和概率码长码字S10.203000S20.190.23001S30180.393011S40.170.573100S50.150.743101S60.100.8941110S70.010.997平均码长：1=0,230,1930.1830.1730.1530.140,017=3.14码元/信源符H(X)2.61=0.831213.14对Y的仙农编码：信源符号S符号概率p(S)和概率码长码字S10.490200S20.140.493011S30.140.633101S40.070.7741100S5

14、0.070.8441101S60.040.91511101S70.020.956111100S80.020.976111110S90.010.997平均编码长度:=0.49m2+0.14=<2+0,07x4x2+0,04x5+0.02父6黑2+0.02黑6+0.01x7=2.89码元/信源符H(Y)2.31编码效率：n=07993l2.89费诺编码：对X的费诺编码:信源符号S符号概率p(Si)编码码字码长S10.200002S20.19100103S30.1810113S40.1710102S50.15101103S60.101011104S70.01111114平均编码长度:1=0,2

15、20,1930.1830.1720.1530.140,014=2.74码元/信源符号"力斗多H(X)2.61编码效率："=0.9526l2.74对Y进行费诺编码:信源符号Si符号概率p(S)编码码字码长S10.49001S20.141001003S30.1411013S40.0710011004S50.07111014S60.041011104S70.0210111105S80.02101111106S90.0111111116平均码长:l=0,49父1+0,14父2父3+0,07父4父2+0,04父4+0,02父5+0,02父6+0.01父6=2.33码元/信源符编码效率

16、：H(Y)2.31=0.99142.33(4)由三种编码的编码效率可知：仙农编码的编码效率为最低，平均码长最长；霍夫曼编码的编码长度最短，编码效率最高，费诺码居中。4-7:由三元编码方式可知：R=D-B=Rd-i(K-2)+2由本题可知D=3,K=8,R=2,所以，首先合并最后两个信源概率，其中一种编码方式如下:信源符号S符号概率p(S)编码码字码长Si0.40.40.40.4001S20.20.20.200.4121S30.10.110.20.22112S40.10.10.11122S50.0540.1/0.121013S60.05i0.0511023S70.0500.05210004S80

17、.051100144-16:符号uiP(ui)F(ui)码长一进制表小CC198940.1110ACA5818950.11100Bcab524367372960.111011Acaba5218767372990.111011000符号分布概率:符号概率分布区间A5910，9；b13b,9C19对译码:F(u4)6737290.92928,1_9二第一字符是：C6738729。9=0.36280,518.99二第二字符是:A0.3628-0一581=0.6530wI-,一5119,9；9二第二字符是:Bcccc50.653059=0.36280,58_5一999.第二字符是：A所以译码结果是：C

18、ABA4-21:符号概率分布区间00.250,0.25)10.7510.25,1)由题目可知信源符号为:1011011110110111p(s=1011011110110111)12431214=p(1)p(0)4=()12()4-0.000123744算术码的码长l=-logp(s)=13由序列S的分布函数F(S)由二元整树图来计算：F(S)=1-p(11)-p(10111)-p(1011011111)-p(1011011110111)-p(1011011110110111)3234138123101331214=1一(R(G(G-(:)(G-(二)(二)一十(G444444444=0.3511403=0.0101100110011所以算术编码为：010000110011平均码长及编码效率如下：-13一l=0.8125码兀/符号16H(S)=p(1)logp(1)-p(0)l