《信息论与编码理论》(王育民李晖梁传甲)课后习题答案高等教育出版社

1、信息论与编码理论习题解第二章-信息量和熵22.1解:平均每个符号长为：4 0.2+1332 3每个符号的熵为2 IogY 1 log 3_0.9183比特/符号3所以信息速率为0.91830.4二兰秒152.2解:同步信号均相同不含信息23.15 _ 3.444 比特 /秒4,其余认为等概,每个码字的信息量为3*2=6比特;所以信息速率为6 1000-6000比特/秒2.3解:(a) 对骰子总点数为所以得到的信息量为(b)一对骰子总点数为12的概率是6366Iog 2(-)36的概率是12.585比特所以得到的信息量为og 236比特2.4解:(a)任一特定排列的概率为1 = 5.173611

2、 ,所以给出的信息量为52!1l°g 52! 22558 比特(b)从中任取13张牌,所给出的点数都不相同的概率为13! 413413A5213c1352所以得到的信息量为log2 C5213.21 比特2.5解:易证每次出现i点的概率为413丄,所以1321I(X=i ) = 一IOg 2 丄,i =I,2,3,4,5,621I (X 二 1)二 4.392 比特I (X - 2) - 3.392 比特l(x - 3) - 2.807 比特I (X 二 4)二 2.392 比特I(X5) - 2.070 比特I (X - 6) - 1.807 比特H(X) 二 J i log 2

3、i 二 2.398 比特i 产 21212.6解:可能有的排列总数为12!277203! 4! 5!没有两棵梧桐树相邻的排列数可如下图求得，YXYXYXYXYXYXYXY图中X表示白杨或白桦， 它有 种排法，丫表示梧桐树可以栽V3)C WJP种的位置，它有种排法，所以共有58 * 7 =1960种排法保证没有 BI IK J53两棵梧桐树相邻，因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为Iog2 27720 -Iog 2 1960 =3.822比特2.7 解:X=0表示未录取，X=1表示录取;Y=0表示本市，Y=1表示外地；Z=O表示学过英语，Z=1表示未学过英语，由此得p( X

4、=0)二3 , P(X= 1) = 1 ,44p( y _ 0)二 p( X- 0) p( y 0 X - O) p( X -2 54 25 p( y - 0 -I)113II丄，, LI'. J424105p( y _1) . 1 4 ,55p( Z 二 0)二 p( Y= 0) p(z = 0 y 二 0) p( y 二1) p( Z 二0 y 二1)-1 +4 40 _13 ,55100251312p( z -1) - 1-",252513 13(a) p( X 0 y - 0) - p( y 0 x - 0) p( X 一 0) / p( -O)Ii1104581 y

5、 0)=p( y =0 X=1) p( X=1) / p( y 二 0L 仅1 厶1 二一52 4 58P(X 0 y 0)I ( X ; y - 0) - P(X - 0 y - 0) Iog 2P(X 丄 y 0)-logp( Xy 0)335IOg 28 Iog283 814 4比特 0.4512p( X 0)5p( X 1)(b) p( X Z=O z = 0)-0) P(X - 0) / p( Z 一 0)-(p( Z -0 y 0, X -0) p( y - 0 X - 0) p( Z 亠 0 y - 1, X - 0) p( y-1x1-(一 ÷ 94 ) 3/13 6

6、910 10104 25104p( X 一 1z0)104P( X -0 Z:-0) Iog 2P( X 0)693535I104404Iog 2 -104丄44I ( X ; Z= 0)二 p( X = 0 Z69Iog 210431) / P(Z - 0)0)P(X 1 Z 0)p( =IZ P) Iog 2=(p( z=0 y =0, x=1) p( y P X 1) P(Z 0 y =1 二(一 I 2)丄/U1, x 1) p( y 1 X 1J) p( XP( X 1)0.02698 比特0.8113比特(C) H ( X )=3 Iog 2 * 1 Iog 2 4 =43 4 +

7、=0) Iog 2 p( y 0 X0) p( X 0) p( yp( X 一 1) p( y 一 0 X 一 1) Iog 2 p( y 0 X 刁)p( x 一 1) p( y 刁 X1911'十1乂_ Iog2 2+x_ Iog 2 2H(Y X) p( X 0) p( y 0 X3log 2 10 飞Iog 2 百1 X 0) Iog 2 p( y1x 0) 1) Iog 2 p( y1 x 一 1)0.6017比特2.8 解:令 X A,B,Y- T,F,R ,则P(T) - P(T A)P(A) P(T B)P(B)-0.5 P 0.3 (I-P)-0.3 0.2 P同理

8、P(F ) - 0.5-0.2 p, P(R) - 0.2I ( P) -I ( X ； Y) -H (Y) - H(Y X)-(0.3 - 0.2p) Iog 2 (0.3 0.2 P) (0.5 0.2p) Iog 2 (0.5 0.2 P) 0.2Iog 2 0.2(0.5 P log 2 2 0.3 plog 2 103 0.2 P log 2 50.3(1 P) log2 1030.5(1 P) log 2 20.2(1 P) log2 5)二 0.3log 2 0.3 0.5log 2 0.5- (0.3 0.2p) log 2 (0.3 0.2 p) - (0.5- 0.2 P)

9、 log2 (0.5- 0.2 P) 令，一(0.5 - 0.2 p) _ 得 _I ( P) 0.2 log 2 0.30.2 P 0, P 0.5I ( p)ma I ( P) PT .5 0.03645 比特2.9 & 2.12解:令 X=X 1,Y=X 1+X 2,Z=X 1+X 2+X 3,H(X 1)=H(X 2)=H(X 3)= log26 比特H(X)= H(X 1) = log2 6=2.585比特H(Y)= H(X 2+X 3)12345_12(一 log 2 36 一 log 2飞6Tog 2 飞6 log 26,'' log 2-36 ) log

10、 2 6363623633643656=3.2744 比特H(Z)= H(X 1+X 2+X 3)ENTISTH(>XNI丄 Z)HHN>x)_ 期兰 6 寸 0oooH寸寸&Oo.SSOH(XNI丄 Z)HH(ZX) _ 期兰Oo寸LOV989Z066900H(COX)H I(Z)HH (AZZ)H 丄 Z)HH(z>)_ 期兰908寸寸H989z+996lh(>XN) H+(x) HH(Zx) T期主 989 Z H(AZZ) hh(>xn)h期兰 996v9897+寸寸 Z0cv9g9z H(X、>)工+(>)工(X) HH(AZX) T

11、期兰寸寸 Z0ooH(cox+2 X)H H (XNT 期兰 989Z H(COXIH(AZZ)H期兰Oo669ooHIZ 9L2 92 9LCNN 9LCN( 二O- + W 6O- 二0一9L2 9LCN92 9LCNN 9L 9L2 OL 9L2 9耳Co9耳 9耳 Cxl6o-9l-louCxi60- Q-l÷g-cxl60-+lcxl60- +9L2CXI60-9coL=1.0143 比特l(Y;Z/X)=H(Z/X)-H(ZXY)=H(X 2+X 3)-H(X3) =3.2744-2.585=0.6894 比特I(X;Z/Y)=H(Z/Y)-H(ZXY)=H(Z/Y)-H

12、 (Z/Y)=02.10解:设系统输出10个数字X等概,接收数字为丫,9 191显然 w（ j ）=£ Q（i ） P（ j i ）=,Sp（ j (U1 ;0)- Iog2 -P(O-UL) - log 2rp - 1 log 2(1 P) bitsw(0)2）=10 10 i，10H(Y)=log10p( X, y) 0g2 p( y ) 奇P(X) p( y X) log 2 p( y )H(YX)E-昱 K p( X, y) l0g2 p( y x)y X偶y_ 0_p( x) p( X x) log 2 p( X x)二-i 奇y去奇X 奇-5 F 1 log22 5 4

13、1 1 log2 810 2 10 8 -1比特所以I(X;Y)=log 2 10 - 1 = 2.3219 比特2.11解：（a）接收前一个数字为 0的概率8-÷. - 1w( 0) 一 q(ui ) p( 0 Ui ) 2 i甘1(b)同理W(Oo)-i _Op(OOu)q(u)p(oo U )I (ui;OO) " Iog 2w(OO)(1 P)2丄 log 2 - 2 2 log 2 (1 P)4bits(C)同理 w(OOO)q(Ui) p(OOO U i )81I (ui;OOO) = I0g2 p(OOOU1 ) = log 2 (1_ p)3 兰3 3log

14、 2 (1 _ P)bitsw(OOO)8(d)同理 w(OOOO ) =3； q(ui ) p(OOOO Ui) - 81 (1 p)66 p2 (1 p) 2p4 )i/2.122.13(b)p(OOOOU 1 )Iog2I (U1;OOOO)W(OOOO)log2 81 (1=8(1- P) 4log2 (1 P) 6 6 p2(1 P)4p)6 6 P2 (厂 P) 2p4 )解:见2.9解:(1 P) 2p4bitsI I Z"7 I XZ -" Tk 一 I C 1H(YZ X)-P( xyz)logXyZp( yZ / X)-. X.邑 p( XyZ) log

15、1XyZp( y / X) P(Z / Xy)一p( XyZ) log1 1P(XyZ)log-XyZP( y / X) X yZp( Z / Xy)二 H(Y X) H(Z XY)(C)H (Z / XY )h爲凭 P(Xy)X yZ三 Z X P(Xy)"X yZp( Z / Xy) logp( z/ Xy) log1P(Z / Xy)1(由第二基本不等式)P(Z / X)-H(Z / X)H(ZXY) H(ZX)_ P(Xy厂p( Z Z Xy) IogXyZP(Z / Xy)- p( Xy)艺 p( Z/ Xy) Iog 1X yZp( Z / X)（由第一基P(Z / X)

16、_ p( Xy)- p( ZZ Xy) log X yZp( Z / Xy )p( Xy)-0P(Z / Xy) log e ( P(Z Z X) _ 1)P(Z Z Xy)本不等式）所以H(ZZX Y) H(ZZX)(a)H(Y X) H(Z Z X)- H(Y X)H(ZZXY)- H(YZZX)等号成立的条件为 P(Z Z xy) - p( Z Z X),对所有X X , y Y, Z Z ,即在给定X条件下Y与Z相互独立。2.14 解：(a) H ( X Z Y ) H (Y Z Z ) H ( X Z YZ ) H (Y Z Z) - H ( XY Z Z ) H ( X Z Z)(

17、b)H(X /Y)H(YZ)H(X /Y)H(YZ)+ = 'tH (XY)H (YZ)H (Y) H (X /Y)H (Y) H (Z /Y)H(XY)H(YZ)"工÷H (Y) H (X /Y)H(Z/Y)H (Y) H(Z/Y)H(X /Y)H (X /Y)+ H(Y /Z) H (Y) H(X /Y)帝H (Z /Y)H(X/Y) H(YZ)H(YZ)H (X /Y)H(X /Y)+H( Y/Z)H(X/Y)H(YZ)H(Z) H(X/Y)H(YZ)H(X Z)OJH(Z)-0H(X /Y)H (Y/Z) =*H (XY)H (YZ)H (X /Y) +H(

18、YZ)H (X /Y)H(YZ) H (Z)工H(XZ)H(X Z) H(Z)H(XZ)H (XZ)注:F a2 >0,b -° Eb a2b alb a1討“2b 七1a2T 十工卡aIba2b2.15 解:(a)d(XJ X)-H(X/X) - H(X/X) -0d ( X JY ) -H ( X / Y) H (Y / X )0(b)d ( X JY ) - H ( X / Y) H (Y / X ) -H (Y / X ) H ( X / Y) -d (YJ X )(C)d ( X ,Y ) d (Y, Z ) _H ( X / Y) H (Y / X ) - H (Y

19、 / Z ) H (Z ZY )H(X ZY) H(YZZ) _ H(X ZYZ) H(YZZ) _ H(XYZZ) _ H(X 亿) 同理 H(ZZY) H(YZ X) H(ZZX)d( X ,Y) d (Y, Z) H ( X Z Z) H ( Z Z X ( X , Z )2.16 解:(a)H(X) H(Y) H (XY) H(X) H(Y) H(XY) H(X ZY) H(YZ X)I(X,Y)-二 H (XY)S( X,Y) - -i (X,Y)丄H (XY)1又由互信息的非负性，即 I ( X ;Y)宓0有S(X ;Y) 0，所以S(X; Y) 1(b)I(X,X) H(X) H

20、(XZX)-S(X,X)H(XX)H(XX)H(X)1H(X)(C)当且仅当X和Y独立时，I (X ; Y) =O，所以当且仅当X 和 Y 独立时，S( X ,Y)- I(X,Y)- 0 OH (XY)2.23 解:(a)PX ( x)21 , 1 X 10 ,其它HC(X)1I(b)令 yX2 , dX 二 1dy 2 y_N呈m(e)3cool Hcxl6o2 I9CXI60一 HZP(Z)Zd 6o一 (Z ) Zd 讨09vH丨(X)XdAz ) ZdXPZPXP6寸寸0“ cxi60tl UA.® A- JAP lroO- IHL I-AP(A)Xl 60一 (A )L二

21、H ( xoH$4HO4Ay1A) >d LVlA-TAw( y)PXy (Xy) M 2： PX ( ) PY X ( y x)XX强-PX (X - 1) Py x( y X - 1) PX ( X 1) P Y X ( Y X 1)81 ,一 3 y 冬1H J 411< y：181 ,1 y _ 30, 其它(b)113H (Y) - 81 Iog 2 8dy3,11L 2.5 bits41 log 2 4dy 81-og 2 8dy1311 1 1=2 4 log 2 4dy 2 4 log 2 4dyL3. 1-2 bitsH(Y X)I ( X ;Y ) - H (Y

22、) -H (Y / X ) -0.5 bit(C)由1, y 1v -0；Ty 11, y < 一 1可求得V的分布为_ - 1 0仁V :1 II -11丄424 /41, y > 1再由p( y / x)及v 0, 1 y 1可求得V的条件分布为1, Y j 1/ /21 , (v, X1) (0厂1), (0,1), (IFrP(V / X)I0,(v, X)= 1j1),(11/11H(V) 2 4l log 2 421 Iog2 21.5 bit=V=一H(V / X) 一 p( X-1) P(v/ X-1) log 2 P(V / X-1)p( X _1) P(V /

23、X 1) logVV1 bitI(V;X) H(V) H(V/X) 0.5 bit可见I (X;Y) I(X;V), Y k V变换没有信息损失.2 P(V / X 1)第二章离散信源无失真编码3.1解:长为n码字的数目为Dn ,因此长为N的D元不等长码 至多有:NN D D(D 1)k -1D 13.2 解:(a) 长为100的事件序列中含有两个 和更少个a1的序列数目为M 毛100° +God ±C10(2= 1+1+ 4950= 5051因此在二元等长编码下所需码长为N TIllog 2 5051 12.3 一 13(b) 误组率为长为100的事件序列中含有三个 a1

24、的序列出现的概率,因此有Pet C100 0 0.996 100 C1001 0.996 99 0.004 C 02 0.9962 0.004 2= 7.755 10 33.3 解:3.4 解:(a)码A中,任一码字不是其它码字的字头，是异字头码 .码B不是异字头码但码A和码B均是唯一可译码.(b)对码AI ( a1 ;1)2 p(a1)2 p(a1)对码BI ( a1 ；1klog 2 EHL =P(a1 )log (C)U Jp(a1)a1 ,a2 , a3 ,4P(a1 )对码A,4:EIP(ak 1) _I (U ；1)k =I p(ak 1) Iog 2P(ak )对码B4P(ak

25、1)=I (U ；1)k T p(ak 1) Iog 2P(ak )11.32 bit0 bitP( ail)0 bit1.32 bit3.5 解:(a)二元 HUffman 编码10H(U)p( ak ) Iog 2 p(ak ) 3.234 bitsk 士平均码长- 10n 一 p(ak ) nk 3.26k 1-编码效率H(U) H(U) 3.23499.2%R n log 2 D 3.26(b)三元HUffma n编码注意：K=10为偶数，需要添一个概率为零的虚假符号平均码长10p(ak ) nk 2.11k F编码效率H(U) H(U)3.23496.6%n log 2 D 2.11

26、 Iog 2 33.6解:二元HUffman编码(a) 二元 HUffman 编码3H(U) p( ak ) Iog 2 p(ak ) 1.485 bitsk 1平均码长3n =£ p(ak ) nk =1.5k .一1编码效率H(U) H(U) 1.48599%R n log 2 D 1.5(b)H(U2) 一 H (U 1U2) 2H (U F 2.97 bits 平均码长9n 2 二 p(ak ) nk 二 3.0k _1编码效率H (U2)2H(U)2.9799%R n 2 log 2 D 3.0(C )H(U3) -H (U1U 2U 3) 3H (U ) 4.455 bi

27、ts 平均码长27n 3 p(ak ) nk 一 4.487k编码效率3G H(U3)3H(U)4.45599.32%R n 3 log 2 D 4.4873.10 傅 P186【5.11 】3.11 解：3.12 解：3.13 解:,所以(a)根据唯一可译码的判断方法可知，输出二元码字为异字头码 它是唯一可译码。H (U )二-0.9 Iog 2 0.9 - 0.1 Iog 2 0.1 二 0.469 比特(b)因为信源是二元无记忆信源，所以有P(Si )二 P(Si1 )P(Si 2 ) P(Sin )其中 Si -(Si1 , Si 2 , , Sin ) Si1, Si 2, , Si

28、n 0,1SQ 1,11,01, P(SQ )0.151 -1,11,1-1, P(S1)- 0.0952 =1,1,2 =1, P(S2 )二 0.08153 -1,11,3-1, p(S3)-0.72954 一 1,11,4一 1, P(S4 厂 0.0656155 -1,|1,5-1, p(S5 Y 0.05904956 =1,1,6 =1, P(S6 T 0.053144157 "1,1,<1, p(S7 Y 0.0478296958 -1,11,8-1, p(S8 )- 0.43046721可计算每个中间数字相应的信源数字的平均长度一 8LII P(Si )1,i 一

29、 5.6953信源符号/中间数字i LQ(C)根据表有|I 2,02 ,12,2I 2, 3S,4674, 1,81可计算每个中间数字所对应的平均长度- 8L2 P(Si)12,i 一 2.7086 二元码 /中间数字i 0由L2 04756二元码/信源符号编码效率为 0.4756/0.469=98.6%精选题1. 傅 P191【5.15 】2. 傅 P192【5.16 】信道及其容量作业：4.14.34.54.84.94.104.12 4.144.1 解:(a) 对称信道(b) 对称信道(C)和信道(课堂教学例题)!4.3 解：(a):可先假设一种分布，利用信道其容量的充要条件来计算(课堂教

30、学例题)(b):准对称信道！4.5解：课堂教学例题4.8解：该题概率有误，应把1/32改为1/64每个符号的熵为8H (S)=L Pilog 2 pi = 2 bitsi F采样频率FS为Fs=2W=8000 HZ所以信息速率R为R -FS H(S) -8000 2 -1.6 104 bps4.9解：每象点8电平量化认为各级出现的概率相等，即H(U)=3 bits所以信息速率R为R 尸30 500 600-2.7 107 bps4.10 解:S站W 一 3KHz,-30 dB 1000, T - 3 60 SNC 亠 Wlog 2 (1 S ) 3000 Iog 2 (1 1000) -29.

31、9 kb / SN所以分钟可能传送话音信息为,329.9 1000 3 60 - 5.382 106 bits4.12 解：W 召KHz, =31高斯信道的信道容量为C 高斯二 Wlog 2 (1 S)= 8000 Iog 2 (1 3的 4 10 4 bpsNCR 105 bps 4104 bps 高斯所以,如该信道是高斯信道,不可实现。如该信道不是高斯信道，因此时信道容量C大于高斯信道 的信道容量，即C4 bps但无法判定R与信道容量C的大小关系，故无法判定是否能实现:4 10,如R寻10 4 bps，则一定可以实现，因R C高斯 JC o4.14 解:第五章离散信道编码定理习题5.1解：

32、DMC信道1112七6111P = I丨_ 6231 1【362J有22461F 8w( y )-1 11(1L12 234263111117w( y3 )-銚(-)26432241Q( X1 ),Q ( X2 ) q( X3 ) - 124w( y 1 )= ： fT1(11)- 3因为P( X1 y1)p( X1)p( y1 X1 丄护2w( y1 )8p( X1 ) p(X1 )P( X1 y2 )-丄W(乎)3I p( X ) p( y X1 )条 2P( X1y3 ) - 7- 7w( y3 )24P( X2 y3).p( XZ ) p( X2 ) _ -4 i _ 2 -7 w(

33、y)24_ p( >6 ) p( 3 X3 )P( 3y3 )1142724所以最大后验概率译码为:y1和y2判为X 1 , y3判为X3 。译码错误概率为:Pe 二 Q( X1 )P( y3 X1 )#Q( X2 )÷Q(X3)(1 -p( y 3 X3 )二丄 _1_1(11 )264421124若按最大似然译码准则译码为：y判为Xi , y2判为X 2 , y3判为X 3译码错误概率为：Pe = Q( X )(1 一 P( y Xi )十Q(x2 )(1P( y2 X2 )0 X3 )(1 -p( y3 X3 )二 _1_-1-1_1 _1(1 丄)224242_12可见

34、,最大似然译码的译码错误概率大于最大后验概率译码的译码错 误概率。第七章信道编码1.设(7,3)码的生成矩阵为(1 0 1 1 1 0 o!G = O 1 1 O 1 1 OILoooI 1 1 1 J(1) 写出该码的一致校验矩阵 H ;(2) 写出该码的所有许用码字；(3) .写出该码的“译码表”-标准译码表或简化(伴随式)译码表；(4) 写出接收矢量 R=1OOOOO1的错误图样，并译相应的许用码字；(5) 写出该码在BSC(错误转移概率为P)中传输的(平均)正确译码概 率PC的表达式；写出该码在BSC(错误转移概率为 P)中传输的漏检概率 Pud(也称不可检测错误概率)的表达式.解：(

35、1) G不为系统码形式,我们通过初等行变换变为系统码形式_1011100101 11 001G 二0110110110 10 100001111i(000 11 11Ik»1"-ik101110011010100111001因此：100011o0100011H 二00101010001111(2) 由C=MG得该码的许用码字为Ooooooo,0111001,1101010,1010011,1011100,1100101,0110110,0001111 该码的最小汉明距离为4。(3) 该码的标准阵由16个陪集构成，在BSC(错误转移概率为p<12)应将重量最小的错误图样选作陪集首,故该码的标准译码表为许用码字0000000(陪集首)0111001110101010100111011100110010101101100001111000000101110001101011101001010111011100100011011100011100000010011101111010001010001101111011001110110100000110100001000111101110111010101111011000110000101100100001011禁用码字0001000011000111000101011011101010