西电 信息论习题答案.pdf

信息与编码理论习题解 第二章-信息量和熵 2.1解: 平均每个符号长为: 15 4 4.0 3 1 2.0 3 2  秒 每个符号的熵为 9183.03log 3 1 2 3 log 3 2  比特/符号 所以信息速率为 444.3 4 15 9183.0  比特/秒 2.2 解: 同步信号均相同不含信息,其余认为等概, 每个码字的信息量为 3*2=6 比特； 所以信息速率为 600010006  比特/秒 2.3 解:(a)一对骰子总点数为7的概率是 36 6 所以得到的信息量为 585.2) 36 6 (log 2  比特 (b) 一对骰子总点数为12的概率是 36 1 所以得到的信息量为 17.5 36 1 log 2  比特 2.4 解: (a)任一特定排列的概率为 !52 1 ,所以给出的信息量为 58.225 !52 1 log 2  比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 13 52 13 13 52 13 44!13 CA   所以得到的信息量为 21.13 4 log 13 13 52 2  C 比特. 2.5 解:易证每次出现i点的概率为 21 i ,所以 比特 比特 比特 比特 比特 比特 比特 398.2 21 log 21 )( 807.1)6( 070.2)5( 392.2)4( 807.2)3( 392.3)2( 392.4)1( 6,5,4,3,2,1, 21 log)( 2 6 1 2           ii XH xI xI xI xI xI xI i i ixI i 2.6 解: 可能有的排列总数为 27720 !5!4!3 !12  没有两棵梧桐树相邻的排列数可如下图求得， Y X Y X Y X Y X Y X Y X Y X Y 图中X表示白杨或白桦，它有         3 7 种排法，Y表示梧桐树可以栽 种的位置，它有         5 8 种排法，所以共有         5 8 *         3 7 =1960种排法保证没有 两棵梧桐树相邻，因此若告诉你没有两棵梧桐树相邻时，得到关于树 排列的信息为 1960log27720log 22  =3.822 比特 2.7 解: X=0表示未录取，X=1表示录取； Y=0表示本市，Y=1表示外地； Z=0表示学过英语，Z=1表示未学过英语，由此得 比特 比特 比特 比特 6017.0 2log 2 1 4 1 2log 2 1 4 1 9 10 log 10 9 4 3 10log 10 1 4 3 )11(log)11()1()10(log)10()1( )01(log)01()0()00(log)00()0()( 8113.04log 4 1 3 4 log 4 3 )()( 02698.0 4 1 104 35 log 104 35 4 3 104 69 log 104 69 )1( )01( log)01( )0( )00( log)00()0;( 104 35 25 13 / 4 1 ) 5 2 2 1 2 1 ( )0(/)1())11()1,10()10()1,00(( )01( 104 69 25 13 / 4 3 ) 10 4 10 9 10 1 ( )0(/)0())01()0,10()00()0,00(( )00()( 4512.0 4 1 8 5 log 8 5 4 3 8 3 log 8 3 )1( )01( log)01( )0( )00( log)00()0;( 8 5 5 1 / 4 1 2 1 )0(/)1()10()01( 8 3 5 1 / 4 3 10 1 )0(/)0()00()00()( , 25 12 25 13 1)1( , 25 13 100 40 5 4 5 1 )10()1()00()0()0( , 5 4 5 1 1)1( , 5 1 10 1 4 3 2 1 4 1 )10()1()00()0()0( , 4 1 )1(, 4 3 )0( 2222 22 22 22 22 22 22 22                                     xypxypxpxypxypxp xypxypxpxypxypxpXYH XHc xp zxp zxp xp zxp zxpzXI zpxpxypxyzpxypxyzp zxp zpxpxypxyzpxypxyzp zxpb xp yxp yxp xp yxp yxpyXI ypxpxypyxp ypxpxypyxpa zp yzpypyzpypzp yp xypxpxypxpyp xpxp 2.8 解:令    RFTYBAX ,,,,  ，则 比特 得令 同理 03645.0)()( 5.0,0 2.03.0 )2.05.0( log2.0)( )2.05.0(log)2.05.0()2.03.0(log)2.03.0(5.0log5.03.0log3.0 )5log)1(2.0 2log)1(5.0log)1(3.05log2.0log3.02log5.0( 2.0log2.0)2.05.0(log)2.05.0()2.03.0(log)2.03.0( )()();()( 2.0)(,2.05.0)( 2.03.0 )1(3.05.0 )()()()()( 5.0max 2 2222 2 23 10 223 10 22 222               p pIpI p p p pI pppp p ppppp pppp XYHYHYXIpI RPpFP p pp BPBTPAPATPTP 2.9 Z)=H(Z)-H(Z/Y) =H(Z)- H(X 3 ) = 3.5993-2.585 =1.0143比特 I(X;Z)=H(Z)-H(Z/X) =3.5993- 3.2744 =0.3249比特 I(XY ;Z)=H(Z)-H(Z/XY) =H(Z)-H(Z/Y) =1.0143比特 I(Y;Z/X)=H(Z/X)-H(Z/XY) = H(X 2 +X 3 )-H(X 3 ) =3.2744-2.585 =0.6894比特 I(X;Z/Y)=H(Z/Y)-H(Z/XY) =H(Z/Y)-H(Z/Y) =0 2.10 解:设系统输出10个数字X等概,接收数字为Y, 显然 10 1 )( 10 1 )()()( 9 1 9 0    ijpijpiQjw ii H(Y)=log10 比特 奇 奇奇 奇偶 1 8log 8 1 10 1 452log 2 1 10 1 5 )(log)()()(log)()(0 )(log),()(log),()( 22 , 22 22           xypxypxpxxpxxpxp xypyxpxypyxpXYH xy xi y xy x 所以 I(X;Y)= 3219.2110log 2  比特 2.11 解:（a）接收前一个数字为0的概率 2 1 8 0 )0()()0(    i i i upuqw bitsp p w up uI )1(log1 1 log )0( )0( log)0;( 2 2 1 2 1 21    （b）同理 4 1 8 0 )00()()00(    i i i upuqw bitsp p w up uI )1(log22 )1( log )00( )00( log)00;( 2 4 1 2 2 1 21    （c）同理 8 1 8 0 )000()()000(    i i i upuqw bitsp p w up uI )1(log33 )1( log )000( )000( log)000;( 2 8 1 3 2 1 21    （d）同理 ))1(6)1(()0000()()0000( 4226 8 1 8 0 ppppupuqw i i i    bits pppp p pppp p w up uI 4226 4 2 4226 8 1 4 2 1 21 )1(6)1( )1( 8log ))1(6)1(( )1( log )0000( )0000( log)0000;(       2.12 解:见2.9 2.13 解: (b) )/()/( )/( 1 log)( )/( 1 log)( )/()/( 1 log)( )/( 1 log)()/( XYZHXYH xyzp xyzp xyp xyzp xyzpxyp xyzp xyzp xyzpXYZH x y zx y z x y z x y z        (c) )/( )/( 1 log)/()( )/( 1 log)/()()/( XZH xzp xyzpxyp xyzp xyzpxypXYZH x y z x y z        （由第二基本不等式） 或 0 )1 )/( )/( (log)/()( )/( )/( log)/()( )/( 1 log)/()( )/( 1 log)/()()/()/(              xyzp xzp exyzpxyp xyzp xzp xyzpxyp xzp xyzpxyp xyzp xyzpxypXZHXYZH x y z x y z x y z x y z （由第一基 本不等式） 所以 )/()/( XZHXYZH  (a) )/()/()/()/()/( XYZHXYZHXYHXZHXYH  等号成立的条件为 )/()/( xzpxyzp  ,对所有 ZzYyXx  ,, ,即在给定 X 条件下Y与Z相互独立。 2.14 解: (a) )/()/()/()/()/()/( ZXHZXYHZYHYZXHZYHYXH  (b) )( )/( )()/( )/( )()/()/( )/()/( )( )/( )( )/( 0)(,0)/()/()/( )()/()/( )/()/( )/()( )/()/( )/()/()( )/()/( )/()/()( )/( )/()/()( )/( )/()( )/( )/()( )/( )( )/( )( )/( XZH ZXH ZHZXH ZXH ZHZYHYXH ZYHYXH YZH ZYH XYH YXH ZHZXHZYHYXH ZHZYHYXH ZYHYXH YXHYZH ZYHYXH YZHYXHYH ZYHYXH YXHYZHYH ZYH YZHYXHYH YXH YZHYH ZYH YXHYH YXH YZH ZYH XYH YXH                          注： ba a ba a aabaaababababaa     2 2 1 1 2122112121 0,0 2.15 解: (a) 0)/()/(),( 0)/()/(),(   XYHYXHYXd XXHXXHXXd (b) ),()/()/()/()/(),( XYdYXHXYHXYHYXHYXd  (c) ),()/()/(),(),( )/()/()/( )/()/()/()/()/()/( )/()/()/()/(),(),( ZXdXZHZXHZYdYXd XZHXYHYZH ZXHZXYHZYHYZXHZYHYXH YZHZYHXYHYXHZYdYXd     同理 2.16 解: (a) 1 )( ),( ),( )( )/()/()()()()()()(),(    XYH YXI YXS XYH XYHYXHXYHYHXHXYHYHXHYXI 又由互信息的非负性，即 0);( YXI 有 0);( YXS ，所以 1);(0  YXS (b) 1 )( )( )( )/()( )( ),( ),(    XH XH XXH XXHXH XXH XXI XXS (c) 当且仅当X和Y独立时，I（X；Y）=0，所以 当且仅当X和Y独立时， 0 )( ),( ),(  XYH YXI YXS 。 2.23 解: (a)      其它,0 11, )( 2 1 x xp X 比特1log)( 2 1 1 1 2 1    dxXH C (b) 令 ydy dx xy 2 1 , 2         其它,0 1, 2 1 )( y y yp Y 比特443.0 log1 2 1 log 2 1 )(log)()( 2 1 0 2         e dy yy dyypypXH YYC (c) 令 3 2 3 1 , 3   z dz dx xz          其它,0 1, 6 1 )()( 3 2 zz dz dx xpzp XZ 比特3.0 log26log )6log( 6 1 )6log( 6 1 )(log)()( 22 1 0 0 1 3 3 2 3 2 3 2 3 2            e dzzzdzzz dzzpzpXH ZZC 2.28 解: (a) 由已知，       其它,0 13, )( 4 1 1 y yp x       其它,0 31, )( 4 1 1 y yp x               其它,0 31, 11, 13, )1()1()1()1( )()()()( 8 1 4 1 8 1 y y y xypxpxypxp xypxpxypyw xyxxyx x xyx x xy （b） bits dydydyYH 5.2 8log4log8log)( 2 3 1 8 1 2 1 1 4 1 2 1 3 8 1       bits dydyXYH 2 4log4log)( 2 3 1 4 1 2 1 2 1 3 4 1 2 1     bitXYHYHYXI 5.0)/()();(  (c)由          1,1 11,0 1,1 y y y v 可求得V的分布为           4 1 2 1 4 1 101 V 再由 )/( xyp 及          1,1 11,0 1,1 y y y v 可求得V的条件分布为           )1,1(),1,1(),(,0 )1,1(),1,0(),1,0(),1,1(),(, )/( 2 1 xv xv xvp .),;();( 5.0)/()();( 1 )1/(log)1/()1()1/(log)1/()1()/( 5.12log4log2)( 22 2 2 1 2 4 1 变换没有信息损失可见 VYVXIYXI bitXVHVHXVI bit xvpxvpxpxvpxvpxpXVH bitVH vv       第三章 离散信源无失真编码 3.1解:长为n码字的数目为D n ,因此长为N的D元不等长码至多有： 1 )1( 1      D DD D NN k i 3.2 解:     3 222 100 991 100 1000 100 1 2 2 100 1 100 0 100 1 10755.7 004.0996.0004.0996.0996.01 ,100)( 133.125051log 505149501001 100)(      CCCP ab N CCCM aa e 因此有的序列出现的概率的事件序列中含有三个误组率为长为 所需码长为因此在二元等长编码下 的序列数目为和更少个的事件序列中含有两个长为 3.3 解: 3.4 解:   bit ap ap apUI B bit ap ap apUI A aaaaUc bit ap ap ap ap aI B bit apap ap aI Ab BA BAa k k k k k k k k 0 )( )1( log)1()1;( 32.1 )( )1( log)1()1;( , ,,,)( 0 )( )( log )( )1( log)1;( 32.1 )( 1 log )( )1( log)1;( )( . ,.,,)( 2 4 1 2 4 1 4321 1 1 2 1 1 21 1 2 1 1 21          对码 对码 对码 对码 均是唯一可译码和码但码 不是异字头码码是异字头码的字头任一码字不是其它码字中码 3.5解: （a）二元Huffman编码 %2.99 26.3 234.3 log )()( 26.3)( 234.3)(log)()( 2 10 1 2 10 1        Dn UH R UH napn bitsapapUH k k k k k k  编码效率 平均码长 （b）三元Huffman编码 注意：K=10为偶数，需要添一个概率为零的虚假符号 %6.96 3log11.2 234.3 log )()( 11.2)( 2 2 10 1       Dn UH R UH napn k k k  编码效率 平均码长 3.6解:二元Huffman编码 （a）二元Huffman编码 %99 5.1 485.1 log )()( 5.1)( 485.1)(log)()( 2 3 1 2 3 1        Dn UH R UH napn bitsapapUH k k k k k k  编码效率 平均码长 （b） %99 0.3 97.2 log )(2)( 0.3)( 97.2)(2)()( 2 2 9 1 21 2 2 2      Dn UH R UH napn bitsUHUUHUH k k k  编码效率 平均码长 （c） %32.99 487.4 455.4 log )(3)( 487.4)( 455.4)(3)()( 2 3 27 1 321 3 3 3      Dn UH R UH napn bitsUHUUUHUH k k k  编码效率 平均码长 3.10 傅P186【5.11】 3.11 解: 3.12 解: 对 3.13 解: (a)根据唯一可译码的判断方法可知,输出二元码字为异字头码,所以 它是唯一可译码。 469.01.0log1.09.0log9.0)( 22 UH 比特 (b)因为信源是二元无记忆信源，所以有 )()()()( 21 iniii SPSPSPSP  其中  1,0,,,),,,( 2121  iniiiniii SSSSSSS  43046721.0)(,1,1 04782969.0)(,1,1 0531441.0)(,1,1 059049.0)(,1,1 06561.0)(,1,1 729.0)(,1,1 081.0)(,1,1 09.0)(,1,1 1.0)(,1,1 88,18 77,17 66,16 55,15 44,14 33,13 22,12 11,11 00,10          SplS SplS SplS SplS SplS SplS SplS SplS SplS 可计算每个中间数字相应的信源数字的平均长度 6953.5)( ,1 8 0 1     i i i lSPL 信源符号/中间数字 (c) 根据表有 1,4 8,27,26,25,24,23,22,21,20,2  lllllllll 可计算每个中间数字所对应的平均长度 7086.2)( ,2 8 0 2     i i i lSPL 二元码/中间数字 由 4756.0 _ 1 _ 2  L L 二元码/信源符号 编码效率为0.4756/0.469=98.6% 精选题 1.傅P191【5.15】 2.傅P192【5.16】 信道及其容量 作业：4.1 4.3 4.5 4.8 4.9 4.10 4.12 4.14 4.1解： (a) 对称信道 (b) 对称信道 (c) 和信道(课堂教学例题)! 4.3解： (a): 可先假设一种分布,利用信道其容量的充要条件来计算(课堂教 学例题) (b): 准对称信道！ 4.5解：课堂教学例题 4.8解：该题概率有误，应把1/32改为1/64。 每个符号的熵为 bitsppSH i i i 2log)( 2 8 1    采样频率Fs为 Fs=2W=8000 Hz 所以信息速率R为 bps 101.628000H(S) FsR 4  4.9解：每象点8电平量化认为各级出现的概率相等，即H(U)=3 bits 所以信息速率R为 bps 7 102.760050030R  4.10解： bits skb 6 22 10382.560310009.29 3, /9.29)10001(log3000) N S (1WlogC s603T1000,dB30 N S 3KHz,W    为分钟可能传送话音信息所以 4.12解： 31 N S 8KHz,W  高斯信道的信道容量为 C。CR，bps，R 。，CRbpsC， C。 CbpsbpsR bps     高斯 高斯 高斯 因则一定可以实现如 故无法判定是否能实现的大小关系与信道容量但无法判定即的信道容量 大于高斯信道因此时信道容量如该信道不是高斯信道不可实现如该信道是高斯信道所以 4 4 45 4 22 103 ,104 ,,, 10410 104)311(log8000) N S (1WlogC 4.14解： 第五章 离散信道编码定理 习题5.1 解：DMC信道                  2 1 3 1 6 1 6 1 2 1 3 1 3 1 6 1 2 1 P 有 4 1 )()(, 2 1 )( 3 21  xQxQxQ 24 7 ) 2 1 3 1 ( 4 1 6 1 2 1 )( 3 1 ) 6 1 2 1 ( 4 1 3 1 2 1 )( 8 3 ) 3 1 6 1 ( 4 1 2 1 2 1 )( 3 2 1    yw yw yw 因为 3 2 )( )()( )( 8 3 2 1 2 1 1 111 1 1    yw xypxp yxP 2 1 )( )()( )( 3 1 3 1 2 1 2 121 2 1    yw xypxp yxP 7 2 )( )()( )( 24 7 6 1 2 1 3 131 3 1    yw xypxp yxP 7 2 )( )()( )( 24 7 3 1 4 1 3 232 32    yw xypxp yxP 7 3 )( )()( )( 24 7 2 1 4 1 3 333 33    yw xypxp yxP 所以 最大后验概率译码为： 33121 x,x 判为判为和 yyy 。 译码错误概率为： 24 11 ) 2 1 1( 4 1 4 1 6 1 2 1 ))(1)(()()()( 3332131    xypxQxQxyPxQp e 若按最大似然译码准则译码为： 332211 x,x,x 判为判为判为 yyy 译码错误概率为： 2 1 ) 2 1 1( 4 1 2 1 4 1 2 1 2 1 ))(1)(())(1)(())(1)(( 333222111    xypxQxyPxQxyPxQp e 可见,最大似然译码的译码错误概率大于最大后验概率译码的译码错 误概率。 第七章 信道编码 1. 设(7,3)码的生成矩阵为            1111000 0110110 0011101 G (1) 写出该码的一致校验矩阵H； (2) 写出该码的所有许用码字； (3) .写出该码的“译码表”---标准译码表或简化(伴随式)译码表； (4) 写出接收矢量R=1000001的错误图样,并译相应的许用码字； (5) 写出该码在 BSC(错误转移概率为 p)中传输的(平均)正确译码 概率p c 的表达式； (6) 写出该码在 BSC(错误转移概率为 p)中传输的漏检概率 P ud (也 称不可检测错误概率)的表达式. 解: (1) G不为系统码形式,我们通过初等行变换变为系统码形式            1111000 0110110 0011101 G ~           1111000 0101011 0011101 ~           1001110 0101011 0011101 因此                1111000 1010100 1100010 0110001 H (2) 由C=MG得该码的许用码字为 0000000,0111001,1101010,1010011,1011100,1100101,0110110,0001111 该码的最小汉明距离为4。 (3) 该码的标准阵由16个陪集构成, 在BSC(错误转移概率为p1/2) 应将重量最小的错误图样选作陪集首, 故该码的标准译码表为 许用码字 0000000 (陪集首) 0111001 1101010 1010011 1011100 1100101 0110110 0001111 0000001 0111000 1101011 1010010 1011101 1100100 0110111 0001110 0000010 0111011 1101000 1010001 1011110 1100111 0110100 0001101 0000100 0111101 1101110 1010111 1011000 1100001 0110010 0001011 0001000 0110001 1100010 1011011 1010100 1101101 0111110 0000111 0010000 0101001 1111010 1000011 1001100 1110101 0100110 0011111 0100000 0011001 1001010 1110011 1111100 1000101 0010110 0101111 禁用码字 1000000 1111001 0101010 0010011 0011100 0100101 1110110 1001111 0000011 0111010 1101001 1010000 1011111 1100110 0110101 0001100 0000101 0111100 1101111 1010110 1011001 1100000 0110011 0001010 0001001 0110000 1100011 1011010 1010101 1101100 0111111 0000110 0010001 0101000 1111011 1000010 1001101 1110100 0100111 0011110 0100001 0011000 1001011 1110010 1111101 1000100 0010111 0101110 1000001 1111000 0101011 0010010 0011101 0100100 1110111 1001110 1001000 1110001 0100010 0011011 0010100 0101101 1111110 1000111 1110000 1001001 0011010 0100011 0101100 0010101 1000110 1111111 译码规则为若接收矢量在第 i 列出现,则译码输出为对应列中的码字, 也就是陪集首为可纠正错误图样. 伴随式译码表为 伴随式 陪集首 0000 0000000 0111 0000001 1101 0000010 1011 0000100 0001 0001000 0010 0010000 0100 0100000 1000 1000000 1010 0000011 1100 0000101 0110 0001001 0101 0010001 0011 0100001 1111 1000001 1001 1001000 1110 1110000 (4) 接收矢量 R=1010101 出现在标准译码表的第五列, 译码输出为 1011100, 错误图样为0001001. (5) 该码标准译码表的陪集首重量分布为 A 0 =1,A 1 =7,A 2 =7,A 3 =1,A 4 =A 5 =A 6 =A 7 =0 所以正确译码概率p c 为 432677 7 0 )1(5)1(7)1(7)1()1( pppppppppAP ii i ic     注意：i=0 (6) 该码的重量分布为 A 0 =1,A 1 =A 2 =A 3 =0,A 4 =7,A 5 =A 6 =A 7 =0 所以该码在BSC中传输的漏检概率P ud 为 347 7 1 )1(7)1( ppppAP ii i iud     注意：i=1