问题详解~信息论与编码练习

1、1有一个二元对称信道，其信道矩阵如下图所示。设该信道以1500个二元符号/秒的速度传输输入符号。现有一消息序列共有14000个二元符号，并设在这消息中 P(0)=P(1)=1/2 。问从信息传输的角度来考虑，10秒钟能否将这消息序列无失真地传送完？0.980.021即P(0)=P(1)=1/2 ，故信源 的熵为 14000(bit/symbol)。10.98解答：消息是一个二元序列，且为等 概率分布，H(X)=1(bit/symbol)。则该消息序列含有的信息量=下面计算该二元对称信道能传输的最大的信息传输速率: 信道传递矩阵为：0 98 0 02P0.02 0.98信道容量(最大信息传输率)

2、为：C=1-H(P)=1-H(0.98) 0.8586bit/symbol得最大信息传输速率为：Rt疋1500符号/秒X 0.8586 比特/符号1287.9比特/秒沁1.288 X 103比特/秒此信道10秒钟能无失真传输得最大信息量=10X Rt疋1.288 X 104比特可见，此信道10秒能无失真传输得最大信息量小于这消息序列所含有的信息量，故从信息传输的角度来考虑，不可能在10秒钟将这消息无失真的传送完。2、若已知信道输入分布为等概率分布，且有如下两个信道，其转移概率矩阵分别为:12120012120000000121200012120000P1212P212121 000000001

3、200120000001212试求这两个信道的信道容量，并问这两个信道是否有噪声？解答：(1) 由信道1的信道矩阵可知为对称信道故 Glog 2 4 H (舟 舟 0 0) 1bit / symbolH (X ) log 2 4 2bit / symbolC1有熵损失，有噪声。(2) 为对称信道，输入为等概率分布时达到信道容量C2 log 2 8 H (2 f 000000) 2bit / symbolH (X ) C2,无噪声3、已知随即变量 X和Y的联合分布如下所示：一YX0101/83/813/81/8试计算：H( X)、H(Y)、H (XY)、H( X/Y )、H( Y/X )、I(X

4、;Y)解:(1)331H(XY)二-Log(S) + - Log+ - Log+ -Log( = 1 ®11ggSH(X) 1 H(Y) 1H( X/Y) = H (XY) - H (Y) =1.811-1=0.811H( Y/X) = H (XY) - H (X) =1.811-1=0.811(5) I共Y)=HgH凶Y)=l-0 811 - 0.1894、有一个可以旋转的圆盘，盘面上被均匀的分成38份，用1,2,3 ,38数字标示,18份涂黑色，圆盘停转后，盘面上指针指向某一数字和颜色。若仅对颜色感兴趣，计算平均不确定度；若对颜色和数字都感兴趣，计算平均不确定度；如果颜色已知，计

5、算条件熵。其中有2份涂绿色,(1)(2)(3)解:(1)H(Log 十一Lag 33 US / 耳 U3(2) P(3) H(色数)=丄H(色数)=1_谊英)=5.242数/色)=H(色数)-H(色)=|二口H - -II5、在一个二进制信道中，信源消息集X=0,1,且P(0)=P(1),信宿的消息集 丫=0,1,信道传输概率 P (1/2 ) =1/4, P(0/1)=1/8。求：(1、在接收端收到y=0后，所提供的关于传输消息X的平均条件互信息量l(X ; y=0).(2) 该情况所能提供的平均互信息量l(X;Y).解：(1)4 41 7J SjP(ij)=r 31£ I17&l

6、t; 1 WP(i/j)=5八7 917J 9 J£此IdP(yl) = -®16IEi(2)方法 1: IKY)=p(yO)IKyO)+p(y1)l(X;y1) = 艇 + 0-236 = 01101O6某一无记忆信源的符号集为0,1，已知p0=1/4, p仁3/4(1)求符号的平均熵(2、由100个符号构成的序列，求某一特定序列(例如有 m个“0”和(100-m、个“ 1 ”) 的自信息量的表达式。(3、计算(2)中的序列的熵。解: H(X)=13:5 爾 + - Log-=0 81144(2)-Log I :.-：-1:.' ： ,1 I ：1：!-I.

7、9;7、一阶马氏链信源有三个符号u1,u2,u3,转移概率为：P(u1/u2)=1/2,P(u2/u2)=1/2,P(u3/u1)=0,P(u1/u2)=1/3,P(u2/u2)=0,P(u3/u2)=2/3,P(u1/u3)=1/3, P(u2/u3)=2/3, P(u3/u3)=0,画出状态图并求出各符号稳定概率。解：P(j/i)=Wi广 0 .4 AW2=%求得W=033丿I 3 JI8、设有一信源,它在开始时以 p(a)=0.6,p(b)=0.3,P(c)=0.1的概率发出XI,如果X1为a时则X2为a,b,c的概率为1/3;如果X1为b时则X2为a,b,c的概率为1/3;如果X1为c

8、时则X2为a,b的概率为1/2，而为c的概率是0;而且后面发出X的概率只与Xi-i有关。又p(Xi/X-i )=p(X2/ X1),i>3。试利用马儿可夫信源的图示法画出状态转移图，并求出状态转移矩阵和信源熵弘P(j/i)=解方程组W2=W2凹丿得到W1-，WS1 1 13 3 3HpQ/a)= Lo/3 = 1.5&5H(X2F沪 LQgfS) = 1 務Hp3/c)= Log© = 1H«(X)=W1H(X2/4-VV2H0<2/b)+W3H(X3/c)=丄Lo酣)十-Log(3)十-LoO = 1.439§849某信源符号有8个符号u1,

9、u8,概率分别是1/2 , 1/4 ,1/8. ,1/16 ,1/32,1/64,1/128,1/128，编成这样的码:000,001,010,011,100,101,110,111 。求(1) 信源的符号熵H(U)(2) 出现一个“ 1”或一个“ 0”的概率；(3) 这样码的编码效率；(4) 相应的香农码和费诺玛；解:(1)H(U)=1 -Log(2) 2(5) 该码的编码效率？m丄丄丄_ _L2 4 8 16 32 64 128 1281.984111 1 1 1 1Log (4) Log(8)Log (16)Log (32)Log(64)Log (128)Log( 128)4816326

10、4128128每个信源使用3个二进制符号，出现0的次数为3r2r2ri+2i4 + ib=2出现1的次数为-+ 2十 1丄十 1-+ 2 + 3 = 02621632(5412S128P(0)=2.3PSP(1)=0.52.393 4 i0.5g6 _ °'1P6K相应的香农编码信源符号xi符号概率pi累加概率Pi-Logp(xi)码长Ki码字x11/20110x21/40.52210x31/80.7533110x41/160.875441110x51/320.9385511110x61/640.96966111110x71/1280.984771111110x81/1280

11、.9927711111110相应的费诺码信源 符号xi符号概率pi第一 次分 组第二 次分 组第三 次分 组第四 次分 组第五 次分 组第六 次分 组第七 次分 组二元码x11/200x21/41010x31/810110x41/16101110x51/321011110x61/6410111110x71/128101111110x81/128111111110(5)香农码和费诺码相同均码长为 1 斗 2 + -3 +-I-5 -I- -6 + -7 斗 -7 = 1 .晁424 S 16326412S12?nm_ 1晁斗编码效率为：尺-= -= =1IC1.3S410已知符号集x1,x2,x

12、3,为无限离散集合，他们出现的概率分别是i ,。p(x1)=1/2,p(x2)=1/4,p(x3)=1/8,p(xi)=1/2(1)用香农编码方法写出各个符号的码字；(2)计算码字的平均信息传输率。(3)计算信源编码效率。31解：(1) pi=2累加概率为Pi =i-1：E Pli-0累加概率分别为符号x1x1x2x3x4x5x6x7概率1/21/41/81/161/321/641/1281/256累加 概率00.50.750.8750.9380.9690.9840.992码长12345678元码010110111011110111110111111011111110(2 )信源的信息量为Hp

13、<)=- Log® 十-L»g(4)十-Log® 十丄 Lvg(l° 十“”心.十丄 1礎3"十24SC.,i码字的平均信息传输率为(3)编码效率bit/ 码R聾=100 %11该二进制对称信道的概率转移矩阵为2/3 1/31/3 2/3(1 )若 p(x0)=3/4,p(x1)=1/4, 求 H(X),H(X/Y),H(Y/X) 和 l(X;Y)(2)求该信道的信道容量及其达到信道容量时的输入概率分布。(1) p(x0)=3/4 p(x1 )=1/4S 1、 卩(协i戶j :PMj戶<3亍H(XY)=LogfZ) + Lo * L

14、ogflJ'n 4 Log(6) = 1.73 24口6Hp(作HXV)-H(Y> 1.73-05K-0.75H(Y=H(XV)-HCX)= 173- 0 811 = 0510l(X：¥)=H凶”H(X/V二 0.811 -075 = 0.0S12 (2OI口gg+EPijLog®沪 Log( + - Log -313平均码长为：3种符号12、某信源发送端有2个符号，xi,i=1,2,p(xi)=a,每秒发出一个符号。接收端有yj,j=1,2,3,转移概率矩阵如下：1/2 1/2 01/2 1/4 1/4匚吨划罡¥)P(回L(a)-P 1+罠log(

15、l +(X)1 - cz logfl - G )M 1 、41。曲4 kg® )U 2丿=05(1)(2) 解: 计算接收端的平均不确定度；计算由于噪声产生的不确定度H(Y/X);计算信道容量OLLI朴宀知心扑宀p(yD=十 1 (1 - a) - pfy2)= -cc 十十丄 p(y3)=,1(x)2Xi 44接收端的不确定度为：H(Y)=汁购-£i=32M1|T-&. +-LesX4)“Log(l十厲)-411 a. H<44Lag(l - at)4扣.«.)4H(Y/X)= -ac十；蓉5目© 十 0 十 131=一-2 2(1 -

16、Gt)十-(1 - B或涉 + (1 - k) Lq忒関4AIQtY)=H(Y>H(Y/X)=(齐宁囁心宁说一)a得到1 -Lti(l 十 oc)十 ln(l - cc) + 2 ln(Z)m :壬 I I4Oma(IKY)=0.16113发送端有3种等概率符号(x1,x2,x3 ) ,p(xi)=1/3,接收端收到3种符号(y1,y2,y3),fOJ 53信道转移概率矩阵如下:0.3(1) 求接收端收到一个符号后得到的信息量H(Y);(2) 计算噪声熵H(Y/X);计算当接收到端收到一个符号y2的错误率；(4) 计算从接收端看的平均错误率；(5) 计算从发送端看的平均错误率；(6) 从

17、转移矩阵中你能看出信道的好坏吗：(7) 计算发送端的 H(X)和H(X/Y)。解:(i)条件概率<0；030.20.40.303<0.10.P0 7，联合概率< 1 1 1 >卩1261015Fij：=2 1 1，后验概率15 1010§八13 n01 2 o<30 10)U0 5丿p(y0)丄3，p(y1)12，p(y2)H(Y)=4- - Log|(3) 4= 1.4JP3261 1r'10>12 OH(Y/X)=+ -Log61U(2)10+ = Lo4L-0 g|+ LoglCQ 丰If1030101 175x1时正确，如果发的是

18、x1和x3为错误，各自的概率为:13Pe=P(x1/y2)+P(x3/y2)=3 0.85(3)当接收为y2，发为1P(x1/y2)=，P(x2/y2)= -，P(x3/y2)=5一其中错误概率为：平均错误概率为HI1311n1533ID101510(5) 仍为 0.733(6) 此信道不好原因是信源等概率分布，从转移信道来看正确发送的概率x1-y1的概率0.5有一半失真 x2-y2的概率0.3有失真严重x3-y3的概率0完全失真(7)H(X)= Log" .1 $85H(X/Y)=1Log(2)6115Log (5) Log -1015225Log -1521Log (5)1015Log -103Log (10) 3035Log -1031.30114、设离散无记忆信道的输入符号集X:0,1，输出符号集丫：0,1,2，信道矩阵为