信息论与编码习题参考答案(全)

1、2002 Copyright EE Lab508信息论与编码习题参考答案第一章 单符号离散信源1.1同时掷一对均匀的子，试求：(1)“2和6同时出现”这一事件的自信息量；(2)“两个5同时出现”这一事件的自信息量；(3)两个点数的各种组合的熵；(4)两个点数之和的熵； (5)“两个点数中至少有一个是1”的自信息量。解： (3)信源空间：X(1,1)(1,2)(1,3)(1,4)(1,5)(1,6)P(X)1/362/362/362/362/362/36X(2,2)(2,3)(2,4)(2,5)(2,6)P(x)1/362/362/362/362/36X(3,3)(3,4)(3,5)(3,6)P

2、(x)1/362/362/362/36X(4,4)(4,5)(4,6)P(x)1/362/362/36X(5,5)(5,6)(6,6)P(x)1/362/361/36(4)信源空间：X23456789101112P(x)1/362/363/364/365/366/365/364/363/362/361/36(5) 1.2如有6行、8列的棋型方格，若有两个质点A和B，分别以等概落入任一方格内，且它们的坐标分别为（Xa，Ya）, （Xb，Yb）,但A，B不能同时落入同一方格内。（1） 若仅有质点A，求A落入任一方格的平均信息量；（2） 若已知A已落入，求B落入的平均信息量；（3） 若A，B是可辨认

3、的，求A，B落入的平均信息量。解：1.3从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为0.5%.如果你问一位男士：“你是否是红绿色盲？”他的回答可能是：“是”，也可能“不是”。问这两个回答中各含有多少信息量？平均每个回答中各含有多少信息量？如果你问一位女士，则她的答案中含有多少平均信息量？解：1.4某一无记忆信源的符号集为0，1，已知（1） 求符号的平均信息量；（2） 由1000个符号构成的序列，求某一特定序列（例如有m个“0”,（1000-m）个“1”）的自信量的表达式；（3） 计算（2）中序列的熵。解：1.5设信源X的信源空间为：求信源熵，并解释为什么H(X)>log

4、6，不满足信源熵的极值性。解：1.6为了使电视图象获得良好的清晰度和规定的对比度，需要用5×105个像素和10个不同的亮度电平，并设每秒要传送30帧图象，所有的像素是独立的，且所有亮度电平等概出现。求传输此图象所需要的信息率（bit/s）。解：1.7设某彩电系统，除了满足对于黑白电视系统的上述要求外，还必须有30个不同的色彩度。试证明传输这种彩电系统的信息率要比黑白系统的信息率大2.5倍左右。证:1.8每帧电视图像可以认为是由3×105个像素组成，所以像素均是独立变化，且每像素又取128个不同的亮度电平，并设亮度电平是等概出现。问每帧图像含有多少信息量？若现在有一个广播员，

5、在约10000个汉字中选1000个字来口述这一电视图像，试问若要恰当地描述此图像，广播员在口述中至少需要多少汉字？解:1.9给定一个概率分布和一个整数m，。定义，证明：。并说明等式何时成立？证：1.10找出两种特殊分布:p1p2p3pn，p1p2p3pm,使H(p1,p2,p3,pn)=H(p1,p2,p3,pm)。解：1.15两个离散随机变量X和Y，其和为ZXY，若X和Y统计独立，求证：(1) H(X)H(Z), H(Y)H(Z)(2) H(XY)H(Z)证明：第二章 单符号离散信道2.1设信源通过一信道，信道的输出随机变量Y的符号集,信道的矩阵：试求：(1) 信源X中的符号a1和a2分别含

6、有的自信息量；(2) 收到消息Yb1，Yb2后，获得关于a1、a2的互交信息量：I(a1;b1)、I(a1;b2)、I(a2;b1)、I(a2;b2)；(3) 信源X和信宿Y的信息熵；(4) 信道疑义度H(X/Y)和噪声熵H(Y/X)；(5) 接收到消息Y后获得的平均互交信息量I(X;Y)。解:2.2某二进制对称信道，其信道矩阵是：设该信道以1500个二进制符号/秒的速度传输输入符号。现有一消息序列共有14000个二进制符号，并设在这消息中p(0)= p(1)=0.5。问从消息传输的角度来考虑，10秒钟内能否将这消息序列无失真的传送完。解:2.3有两个二元随机变量X和Y，它们的联合概率为PX=

7、0,Y=0=1/8，PX=0,Y=1=3/8，PX=1,Y=1=1/8，PX=1,Y=0=3/8。定义另一随机变量Z=XY，试计算：(1) H(X),H(Y),H(Z),H(XZ),H(YZ),H(XYZ);(2) H(X/Y),H(Y/X),H(X/Z),H(Z/X),H(Y/Z),H(Z/Y),H(X/YZ),H(Y/XZ),H(Z/XY);(3) I(X;Y),I(X;Z),I(Y;Z),I(X;Y/Z),I(Y;Z/X),I(X;Z/Y)。解:2.4已知信源X的信源空间为某信道的信道矩阵为： b1 b2 b3 b4试求：(1)“输入a3，输出b2的概率”；(2)“输出b4的概率”；(3

8、)“收到b3条件下推测输入a2”的概率。解：2.5已知从符号B中获取关于符号A的信息量是1比特，当符号A的先验概率P(A)为下列各值时，分别计算收到B后测A的后验概率应是多少。(1) P(A)=10-2；(2) P(A)=1/32；(3) P(A)=0.5。解：2.6某信源发出8种消息，它们的先验概率以及相应的码字如下表所列。以a4为例，试求：消息a1a2a3a4a5a6a7a8概率1/41/41/81/81/161/161/161/16码字000001010011100101110111(1) 在W4011中，接到第一个码字“0”后获得关于a4的信息量I(a4;0)；(2) 在收到“0”的前

9、提下，从第二个码字符号“1”中获取关于a4的信息量I(a4;1/0)；(3) 在收到“01”的前提下，从第三个码字符号“1”中获取关于a4的信息量I(a4;1/01)；(4) 从码字W4011中获取关于a4的信息量I(a4;011)。解：2.13把n个二进制对称信道串接起来，每个二进制对称信道的错误传输概率为p(0<p<1)，试证明：整个串接信道的错误传输概率pn=0.51-(1-2p)n。再证明：n时，limI(X0;Xn)=0。信道串接如下图所示：X0X1XnX2BSCIIBSCNBSCI解：2.18试求下列各信道矩阵代表的信道的信道容量：(1)(2)(3)解：2.19设二进制

10、对称信道的信道矩阵为：(1) 若p(0)=2/3，p(1)=1/3，求H(X)，H(X/Y)，H(Y/X)和I(X;Y)；(2) 求该信道的信道容量及其达到的输入概率分布。解：2.20设某信道的信道矩阵为试求：(1) 该信道的信道容量C；(2) I(a3;Y)；(3) I(a2;Y)。解:2.21设某信道的信道矩阵为试求：(1)该信道的信道容量C；(2)I(a1;Y)；(3)I(a2;Y)。解:2.22设某信道的信道矩阵为试该信道的信道容量C；解:2.23求下列二个信道的信道容量，并加以比较(其中0<p,q<1,p+q=1)(1)(2)解:2.27设某信道的信道矩阵为其中P1,P2

11、，PN是N个离散信道的信道矩阵。令C1，C2，CN表示N个离散信道的容量。试证明，该信道的容量比特/符号，且当每个信道i的利用率pi2Ci-C(i1,2,N)时达其容量C。证明:第三章 多符号离散信源与信道3.1设XX1X2XN是平稳离散有记忆信源，试证明：H(X1X2XN)=H(X1)+ H(X2/ X1)+H(X3/ X1 X2)+H(XN / X1 X2XN-1)。(证明详见p161-p162)3.2试证明：logrH(X) H(X2/ X1) H(X3/ X1 X2) H(XN / X1 X2XN-1)。证明:3.3试证明离散平稳信源的极限熵：(证明详见p165-p167)3.4设随机

12、变量序列(XYZ)是马氏链，且X：a1, a 2, a r，Y：b1,b2, ,bs,Z:c1,c2, ,cL。又设X与Y之间的转移概率为p(bj/ai)(i=1,2, ,r;j=1,2, ,s)；Y与Z之间的转移概率为p(ck/bj)(k=1,2,L;j=1,2, ,s)。试证明：X与Z之间的转移概率：证明:3.5试证明：对于有限齐次马氏链，如果存在一个正整数n01，对于一切i，j1，2，r，都有pij(n0)>0，则对每个j1，2，r都存在状态极限概率：(证明详见:p171175)3.6设某齐次马氏链的第一步转移概率矩阵为：试求：(1) 该马氏链的二步转移概率矩阵；(2) 平稳后状态

13、“0”、“1”、“2”的极限概率。解：3.7设某信源在开始时的概率分布为PX0=0=0.6;P X0=1=0.3; P X0=2=0.1。第一个单位时间的条件概率分布分别是：P X1=0/ X0=0=1/3; PX1=1/ X0=0=1/3; P X1=2/ X0=0=1/3;P X1=0/ X0=1=1/3; P X1=1/ X0=1=1/3; P X1=2/ X0=1=1/3;PX1=0/ X0=2=1/2; P X1=1/ X0=2=1/2; P X1=2/ X0=2=0.后面发出的Xi概率只与Xi-1有关，有P(Xi/Xi-1)=P(X1/ X0)(i2)试画出该信源的香农线图，并计算

14、信源的极限熵H。解：香农线图如下：2011/21/21/31/31/31/31/31/33.8某一阶马尔柯夫信源的状态转移如下图所示，信源符号集为X：0,1,2，并定义012p/2p/2p/2p/2p/2p/2(1) 试求信源平稳后状态“0”、“1”、“2”的概率分布p(0)、p(1)、p(2)；(2) 求信源的极限熵H；(3) p取何值时H取得最大值。解：3.9某一阶马尔柯夫信源的状态转移如下图所示，信源符号集为X：0,1,2。试求：(1)试求信源平稳后状态“0”、“1”、“2”的概率分布p(0)、p(1)、p(2)；(2)求信源的极限熵H；(3)求当p=0,p=1时的信息熵，并作出解释。p

15、pp012解:3.10设某马尔柯夫信源的状态集合S：S1S2S3，符号集X：123。在某状态Si(i=1,2,3)下发发符号k(k=1,2,3)的概率p(k/Si) (i=1,2,3; k=1,2,3)标在相应的线段旁,如下图所示.(1) 求状态极限概率并找出符号的极限概率;(2) 计算信源处在Sj(j=1,2,3)状态下输出符号的条件熵H(X/Sj);(3) 信源的极限熵H.2:1/4S1S2S33:1/22:1/21:11:1/23:1/4解:3.12下图所示的二进制对称信道是无记忆信道,其中,试写出N=3次扩展无记忆信道的信道矩阵P.0 0 p X Y p1 1 解:第五章 多维连续信源

16、与信道5.8设X()是时间函数x(t)的频谱,而函数在T1<t<T2区间以为的值均为零.试证:(频域抽样定理,证明详见p263-p265)5.9设随机过程x(t)通过传递函数为K()的线性网络,如下图所示.若网络的频宽为F,观察时间为T.试证明:输入随机过程的熵h(X)和输出随机过程的熵h(Y)之间的关系为:网络K()x(t)y(t)(证明详见p283-p287)5.11证明:加性高斯白噪声信道的信道容量: 信息单位/N维其中N=2FT,2X是信号的方差(均值为零), 2N是噪声的方差(均值为零).再证:单位时间的最大信息传输速率 信息单位/秒(证明详见p293-p297)5.12

17、设加性高斯白噪声信道中,信道带宽3kHz,又设(信号功率+噪声功率)/噪声功率=10dB.试计算改信道的最大信息传输速率Ct.解:5.13在图片传输中,每帧约有2.25×106个像素,为了能很好的重现图像,需分16个量度电平,并假设量度电平等概率分布,试计算每分钟传输一帧图片所需信道的带宽(信噪功率比为30dB).解:5.14设电话信号的信息率为5.6×104比特/秒.在一个噪声功率谱为N0=5×10-6mW/Hz,限频F、限输入功率P的高斯信道中传送,若F=4kHz,问无差错传输所需的最小功率P是多少W?若F则P是多少W?解:5.15已知一个高斯信道,输入信噪功

18、率比为3dB,频带为3kHz,求最大可能传送的信息率是多少?若信噪比提高到15dB,求理论上传送同样的信息率所需的频带.解:5.17设某加性高斯白噪声信道的通频带足够宽(F),输入信号的平均功率Ps=1W,噪声功率谱密度N0=10-4W/Hz,若信源输出信息速率Rt=1.5×104比特/秒.试问单位时间内信源输出的信息量是否全部通过信道?为什么?解:第六章 无失真信源编码6.3设平稳离散有记忆信源XX1X2XN,如果用r进制符号集进行无失真信源编码.试证明当N时,平均码长(每信源X的符号需要的码符号数)的极限值:其中,Hr表示r进制极限熵.证明:6.4设某信源S:s1,s2,s3,s

19、4,s5,s6,其概率分布如下表所示,表中也给出了对应的码1,2,3,4,5,6.(1)试问表中哪些码是单义可译码?(2)试问表中哪些码是非延长码?(3)求出表中单义可译码的平均码长.sipiW(1)W(2)W(3)W(4)W(5)W(6)s11/200000000s21/400101100110100s31/8010011110001110101s41/160110111111000011110110s41/321000111111110000011011111s61/321010111111111100000011101011解:(1)W(1)是定长非奇异码,单义可译,W(2)是延长码,单

20、义可译, W(3)是即时码,单义可译;(2) W(1)、W(3)是非延长码;(3)6.5某信源S的信源空间为:(1) 若用U:0,1进行无失真信源编码,试计算平均码长的下限值;(2) 把信源S的N次无记忆扩展信源SN编成有效码,试求N=2,3,4时的平均码长;(3) 计算上述N=1,2,3,4,这四种码的信息率. 解:对其进行Huffman编码:码长编码信符010101信符概率10S220.64210S210.163110S120.163111S110.08码长编码信符信符概率010101010110S2220.5123100S2210.1283111S2120.1283110S1220.12

21、8511100S112010.032511101S1210.032511110S211010.032511111S1110.008码长编码信符信符概率0.59040.38560.18080.08840.20480.20480.10240.05120.05120.01280.05120.014410S22220101010101010101010101010101010.40963100S22210.10243101S22120.102441100S21220.102441101S12220.10246111000S21120.02566111001S21210.02566111010S2211

22、0.02566111010S12210.02566111100S12120.02566111101S11220.025671111100S11120.006471111101S11210.006471111110S12110.0064811111110S21110.0064811111111S11110.00016(3)6.6设信源S的信源空间为符号集U:0,1,2,试编出有效码,并计算其平均码长.解:进行Huffman编码:r=3,q=8,因为(q-r)mod(r-1)=5mod2=10,所以插入m=(r-1)- (q-r)mod(r-1)=2-1=1个虚假符号,令其为S9,则:码长编码信符

23、信符概率10S30120120120120.311S10.2220S40.2221S20.13220S50.053221S60.0542220S70.0542221S80.0542222S9（不使用）06.7设信源S的N次扩展信源SN,用霍夫曼编码法对它编码,而码符号U: 1,2,r ,编码后所得的码符号可以看作一个新的信源试证明:当N时,.证明:6.8设某企业有四种可能出现的状态盈利、亏本、发展、倒闭,若这四种状态是等概率的,那么发送每个状态的消息量最少需要的二进制脉冲数是多少?又若四种状态出现的概率分别是:1/2,1/8,1/4,1/8,问在此情况下每消息所需的最少脉冲数是多少?应如何编码

24、?解:设S:S1=“盈利”,S2=“亏本”,S3=“发展”,S4=“倒闭”,(1)若四种情况等概率出现时,即p(S1)=p(S2)=p(S3)=p(S4)=0.25时,用脉冲来表示各信息可视为对信源S进行编码,由平均码长界限定理知:所以发送每个状态的信息最少需要2个二进制脉冲.(2) p(S1)=1/2,p(S2)=1/8,p(S3)=1/4,p(S4)=1/8时,由平均码长界限定理:所以此情况下每消息所需的最少脉冲数是1.75个.达到此下限时要求各消息对应码长ni与出现概率p(Si)关系为:p(Si)=2-ni,则n1=1,n2=3,n3=2,n4=3.对信源进行Huffman编码:码长编码

25、信符信符概率10S11/21/2011/2210S3011/4011/41/23100S21/81/43101S21/8可见上面编码符号最小码长条件,可使发送每信息的脉冲数最少.6.9设某信源的信源空间为:试用U:0,1作码符号集,采取香农编码方法进行编码,并计算其平均码长.解:码长编码信符信符概率10s11/21/21/21/21/2011/2210s21/41/41/4011/4011/41/23110s31/81/81/81/81/441110s41/16011/16011/161/8511110s5011/321/321/166111110s61/641/326111111s71/64

26、第七章抗干扰信道编码7.4设有一离散信道，其信道矩阵为：(1) 当信源X的概率分布为(a1)2/3，(a2)(a3)1/6时，按最大后验概率准则选择译码函数，并计算其平均错误译码概率Pemin(2) 当信源是等概信源时，按最大似然译码准则选择译码函数，并计算其平均错误译码概率Pemin解：7.5某信道的输入符号集X：0，1/2，1，输出符号集Y：0，1，信道矩阵为：现有四个消息的信源通过这信道，设信息等概出现。若对信源进行编码，我们选这样一种码：C:(x1,x2,1/2,1/2)，xi=0,1(i=1,2)其码长n=4，并选取这样的译码原则：(y1,y2,y3,y4)=(y1,y2,1/2,1

27、/2)(1) 这样的编码后信息传输效率等于多少？(2) 证明在选用的编码规则下，对所有码字有Pe0。解：7.6考虑一个码长为4的二进制码，其码字为w1=0000；w2=0011；w3=1100；w4=1111。若码字送入一个二进制对称信道（其单符号的误传概率为p，p<0.01），而码字的输入是不等概率的，其概率为：p(w1)=1/2，p(w2)=1/8，p(w3)=1/8，p(w4)=1/4试找出一种译码规则使平均错误概率Pemin=Pe。解：由于信道为二进制对称信道，所以先验概率等于后验概率，且p<0.01，故可以根据信道输出的24个码字的最大后验概率选择译码规则，即可使平均错误

28、概率Pemin=Pe。 发送概率收到码字w1=0000w2=0011w3=1100w4=1111译码规则0000F(0000)=00000001F(0001)=00000010F(0010)=00000011F(0011)=00110100F(0100)=00000101F(0101)=00000110F(0110)=00000111F(0111)=11111000F(1000)=00001001F(1001)=00001010F(1010)=00001011F(1011)=11111100F(1100)=11001101F(1101)=11111110F(1110)=11111111F(11

29、11)=11117.7设一离散无记忆信道，其信道矩阵为：(1) 计算信道容量C；(2) 找出一个长度为二的码，其信息传输率为0.5log5（即五个字符），如果按最大似然译码准则设计译码器，求译码器输出端平均错误译码的概率Pe（输入字符等概）；(3) 有无可能存在一个长度为2的码而使每个码字的平均误译概率Pe(i)0（i=1,2,3,4,5），也即使平均错译概率Pe0？如存在的话请找出来。解：7.8设有二个等概信息A和B，对它们进行信道编码，分别以w1=000，w2=111表示。若二进制对称信道的正确传递概率p>>错误传递概率p。试选择译码函数，并使平均错误概率Pe=Pemin，写出

30、Pemin的表达式。解： 000 001 010 100 011 101 110 111因为正确传递概率p>>错误传递概率p，所以选择译码函数如下：F(000)=F(010)=F(100) =F(001)=000F(111)=F(011)=F(101) =F(110)=F(111)=1117.9设离散无记忆信道的输入符号集X：0，1，输出符号集Y：0，1，2，信道矩阵为：若某信源输出两个等概消息s1和s2，现在用信道输入符号集中的符号对s1和s2进行信道编码，以w1=00代表s1，w2=11代表s2。试写出能使平均错误译码概率Pe=Pemin的译码规则，并计算Pemin。解：7.1

31、0设某信道的信道矩阵为：其输入符号等概分布，在最大似然译码准则下，有三种不同的译码规则，试求之，并计算出它们对应的平均错误概率。解：输入符号等概分布，在最大似然译码准则下，有三种不同的译码规则:(1) F(b1)=a1，F(b2)=a1，F(b3)=a2(2) F(b1)=a1，F(b2)=a2，F(b3)=a2(3) F(b1)=a1，F(b2)=a3，F(b3)=a2第八章 限失真信源编码8.1设信源X的概率分布P(X):p(a1), p(a2), ,p(ar) ,失真度为d (ai, bj)0,其中(i=1,2,r;j=1,2,s).试证明:并写出取得的试验信道的传输概率选取的原则,其中(证明详见:p468-p470)8.