答案~信息论与编码练习

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

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

3、两个信道是否有噪声解答：(1)由信道1的信道矩阵可知为对称信道故 G log 2 4 H (f i 0 0) 1bit / symbolH (X ) log 2 42bit / symbolC1有熵损失，有噪声。3、已知随即变量 X和Y的联合分布如下所示:0101/83/813/81/8试计算：H( X)、H(Y)、H (XY)、H( X/Y )、H( Y/X )、I(X;Y)解:(1)331H(XY) = -+ - Log+ - Log+ -Logf = 1 ®118g2乜丿SH(X) 1 H(Y) 1(3) H( X/Y) = H (XY) - H (Y)=(4) H( Y/X)

4、 = H (XY) - H (X)=(5)I共Y)=HgH凶Y>1 - 0.311 - 0.1894、有一个可以旋转的圆盘，盘面上被均匀的分成 38份，用1,2,3 , 其中有2份涂绿色，18份涂黑色，圆盘停转后，盘面上指针指向某一数字和颜色。38数字标示,(1、若仅对颜色感兴趣，计算平均不确定度；(2、若对颜色和数字都感兴趣，计算平均不确定度;(3、如果颜色已知，计算条件熵。解：(1) H(2) P(色数)=H(色数)=Log(38) -H( 数/色)=H(色数)-H(色)= H - - I'5、在一个二进制信道中，信源消息集X=0,1,且P(O)=P(1),信宿的消息集 丫=

5、0,1,信(1) 在接收端收到y=0后，所提供的关于传输消息X的平均条件互信息量 该情况所能提供的平均互信息量l(X;Y).解：'3Pt 3i、(6p(i/n=44Sz79P(ij)=P(i/j)=171717JSj池6l 了9 Jp(曲31 + 7-T P(yl)i =79H> £16加slb16(2) 方法 1:l(X；Y>p(yO)l(XjO!)4p(y1)l(X;y1) = 0.40S + 0.236 = 03111巧166某一无记忆信源的符号集为0,1，已知p0=1/4, p仁3/4(1) 求符号的平均熵(2)由100个符号构成的序列，求某一特定序列(例

6、如有m个“0”和(I(X ； y=0).100-m)个“ 1 ”)的自信息量的表达式。(3) 计算(2)中的序列的熵。(1) H(X)=I3-Lo 的 4- - Log=0.S1144(2) l(X1X2.X100>= -Logs Situ- (100 -Log扌 I :.-：-1:.' ： ,1 I ：1：! -I Tl. -7、一阶马氏链信源有三个符号u1,u2,u3,转移概率为：P(u1/u2)=1/2,P(u2/u2)=1/2,P(u3/u1)=0,P(u1/u2)=1/3,P(u3/u2)=2/3,P(u1/u3)=1/3, P(u2/u3)=2/3, P(u3/u3)

7、=0,画出状态图并求出各符号稳定概率。P(u2/u2)=0,解:解:1= fl"11)一(J222 3 31 n 233解方程组1 “ 22312R0-0U 3丿1了丿P(j/i)=B5 J%求得W=36I 3 /2丿8、设有一信源，它在开始时以p(a)=,p(b)=,p(c)= 的概率发出X1,如果X1为a时则X2为a,b,c的概率为1/3;如果X1为b时则X2为a,b,c的概率为1/3;如果X1为c时则X2为 a,b的概率为1/2，而为c的概率是0;而且后面发出 X的概率只与 X-1有关。又 p(Xi/ X-i )=p(X2/X1),i>3。试利用马儿可夫信源的图示法画出状

8、态转移图，并求出状态转移矩阵和信源熵弘Wl + W2 + m = 1HpQ/罕 5或3 = 1.J35Hp2/b> Log(可=1.JS5HpO/F Log|(2) = 1231H«(X)=W1 H(X2/+W2H(>C2/b)+WsHpG/c)= -Log(3) +- Log(?)+-Lo2)- 1.439S£49某信源符号有8个符号u1,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)

9、出现一个“ 1”或一个“ 0”的概率；(3) 这样码的编码效率；(4) 相应的香农码和费诺玛；解:(1)H(U)=1 -Log(2) 2(5 )该码的编码效率111111 1 12 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)48163264128128(2)每个信源使用3个二进制符号，出现0的次数为3- 4-2-+ 2 -+ + 2 + + = 2.35324 S 16326412?出现1的次数为4十4"待十占十冷T曲P(0)=p(1)=2那2 3

10、58 + O_5S6=0.S04H(U)K相应的香农编码信源符号xi符号概率Pi累加概率Pi-Logp(xi)码长Ki码字x11/20110x21/42210x31/833110x41/16441110x51/325511110x61/6466111110x71/128771111110x81/12877相应的费诺码信源符号概第一第二第三第四第五第六第七二元码符号率pi次分次分次分次分次分次分次分xi组组组组组组组x11/200x21/4010x31/80110x41/1601110x51/3211011110x61/64110111110x71/1281101111110x81/1281(5

11、)香农码和费诺码相同均码长为 1 斗 2 + -3 +-I-5 -I- -6 + -7 斗-7 = 1 .!£42 4 S 16326412S12S1.3K4编码效率为:10已知符号集x1,x2,x3,为无限离散集合，他们出现的概率分别是p(x1)=1/2,p(x2)=1/4,p(x3)=1/8,p(xi)=1/2（1）用香农编码方法写出各个符号的码字；（2）计算码字的平均信息传输率。（3）计算信1i-1= 累加概率为Pi =:工片 累加概率分别为i = 0源编码效率。3解：（1） pi符号x1x1x2x3x4x5x6x7概率1/21/41/81/161/321/641/1281/2

12、56累加概率0码长12345678元码0101101110111101111101111110（2 ）信源的信息量为H凶二-Lg 十-冷）十-LogfS）十丄-“酣。十十-十24SIt._i平均码长为： 1 +3 + 4 4-.十 l +24816码字的平均信息传输率为R =Ibit/ 码K（3）编码效率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)(1) p(x0)=3/4 p(x1 )=1/41、円协i戶；<3亍LH(XY)=(2)求该信道的

13、信道容量及其达到信道容量时的输入概率分布。LogfZ) + Log)4 LogflJ'ii 4 Loh(6) = 1.73 24口6HOZT)=HP<V)-H(Y> 1.73- 0.PS -0.75H(Y/X)=H(XV)-HX)= 1.73-0.811 = 0i510l(X：¥)二 H凶”0.S11 -073 = OlOSI2 f i /1 ® ObgQ)十邛ijLagWi沪 L翻 + -Logj-J + - L碣- J-0.032 嗣=呛1” |每秒发出一个符号。接收端有3种符号12、某信源发送端有2个符号，xi,i=1,2,p(xi)=a.yj,j

14、=1,2,3,转移概率矩阵如下:(1)(2)1/2P 1/21/2 01/4 1/4计算接收端的平均不确定度;计算由于噪声产生的不确定度H(Y/X);计算信道容量 解:ii1OL2沖扑*p(yD=pC>2)= -c 十-(1 _ e) T - tL + -2444P(y3> -(l - a)4l(X;¥)-H(Y)-H(Y/X)= f- - Log(l + 胡- Lcg(l -Kf- - 1.244丿辽 2曲)张) 15 1+ (Llog(l十皿)1 - cz id 吕(1 - G )M 1 、wi才 15)<2=041吨41 口酣 JU 2丿得到接收端的不确定度为

15、H(Y/X)= *LrQgfST)十十。十扣- 口儿嗔2)十-G Sg(书1 -Ltil(L 十 a)十 ln(l - ql) + 2 ln(Z)耳:S 114hr<2)得口 ：=扌3)015113发送端有3种等概率符号(x1,x2,x3 ) ,p(xi)=1/3.接收端收到3种符号(y1,y2,y3 )r0.5 »3 0.2信道转移概率矩阵如下：F:= D.4 0.3 0.3<D.l砧 0丿(1) 求接收端收到一个符号后得到的信息量H(Y);(2) 计算噪声熵H(Y/X);计算当接收到端收到一个符号y2的错误率；(4) 计算从接收端看的平均错误率；(5) 计算从发送端看

16、的平均错误率；(6) 从转移矩阵中你能看出信道的好坏吗：(7) 计算发送端的 H(X)和H(X/Y)。解:(1)0.3条件概率04，联合概率£ 162771<30110±10310丄±101.2，后验概率J.51P(yo) 3， p(y1)1 12，p(y2) 61110H(Y)= 扛口曲丄 5或2)十丄Lo妙 =1.4刃326(2)H(Y/X)=+ -Log61Ur'10>1 2+ LosCS + Log吕)1303；104 Log + 1,0 g| + L-0+ If1010-1 175(3)当接收为y2，发为x1时正确，如果发的是 x1和

17、x3为错误，各自的概率为:1P(x1/y2)= -，P(x2/y2)= -，P(x3/y2)=55其中错误概率为:Pe=P(x1/y2)+P(x3/y2)=30.85(5)(6)此信道不好平均错误概率为1I311 一 + 一 + 一 + 一 +=0.733153310101510仍为原因是信源等概率分布，从转移信道来看正确发送的概率x1-y1的概率有一半失真(7)H(X)= Log" .1(85H(X/Y)=1115Log (2) Log (5) Log6101521.30125Log -1521Log (5)1015Log -1031Log (10)303 5Log -10314、设离散无记忆信道的输入符号集X:0,1，输出符号集 丫：0,1