信息论与纠错编码编码习题答案

1第1章信息论基础1.736136236336436536636536436336236112111098765432)(XqX1.8p(s0)=0.8p(s0)+0.5p(s2)p(s1)=0.2p(s0)+0.5p(s2)p(s2)=0.5p(s1)+0.3p(s3)p(s3)=0.5p(s1)+0.7p(s3)p(s0)+p(s1)+p(s2)+p(s3)=1p(s0)=3715，p(s1)=p(s2)=376，p(s3)=37101.9Pe=q(0)p+q(1)p=0.06(1-0.06)﹡1000﹡10=94009500不能1.1022222222)1(0)1()1(00000)1(0)1()1(000000)1()1(0)1(00000)1()1(0)1(ppppppppppppppppppppppppP第2章信息的度量2.4logk2.5I(X;YZ)=I(X;Y)+I(X;Z∣Y)2.7010434()()()111111pspspsH=0.25(Bit/符号)2.8H=0.82(Bit/符号)2.10（1）1()log225.6()52!iIxBit（2）1352!()log()log413!39!iiIxqx（3）)/(4.713log234log52log521log)(符号－BitUH（4）)/(7.313log131log)(符号BitXH2.11（1）H(X)=log6=2.58(Bit/符号)（2）H(X)=2.36(Bit/符号)（3）I(A+B=7)=-log1/6=log6=2.585(Bit)2.12（1）I(xi)=-log1/100=log100（2）H(X)=log100.22.13039.0log)(YXI2.14Rt=1000/4(码字/秒)×H(U)=250×9＝2250（Bit/秒）2.15―logp=log55/44。2.16I(X;Y)=1.82(Bit/符号)2.17（1）)1(2log100;14puI（2）)1(2log2100;104puI（3）)1(2log3100;1004puI2.20kBkkAAACeq111时，H(U)取得最大值。0110)1(log)1(1log)(kkkkkkkmAAAAkqqUH2.30（1）H(X)=1.69(Bit/符号)（2）H(Y)=1.57(Bit/符号)(3)符号/76.0)(BitXYH(4)(Bit/2.45)(符号XYH（5）I(X;Y)=0.81(Bit/符号)第3章离散信源无失真编码3.6（1）2位（2）取码长n1=1、n1=2、n1=3、n1=3就能得到紧致码。3.13（1）H(X)=-0.9log0.9-0.1log0.1=log10-0.9log9（2）7.5l（3）7.2n3.14（1）x1→0，x2→11，x3→105.1n99.0（2）x1x1→01，x1x2→110，x2x1→101，x1x3→011，x3x1→010，x2x2→1111，x2x3→1110，x3x2→10013n99.03.15（1）)(112pHpH3（2）pn113.16（1）当M=2i，这种情况下得到的是等长码，码长为i。（2）当M=2i+1平均码长为122)1(1221212iiiiiiin3.17方法一：概率之和与原信源某概率相等，概率之和往上排：方法二：概率之和与原信源某概率相等，概率之和往下排：两种方法得到的码集都是最佳的。3.18（1）shannon编码，D=2消息x1x2x3x4x5x6x7x8码字00000101110001010101111011110（2）Fano编码，D=2消息x1x2x3x4x5x6x7x8码字0001001110010111011101111（3）Huffman编码，D＝3消息x1x2x3x4x5x6x7x8码字02120121110221220（4）Huffman编码，D＝4消息x1x2x3x4x5x6x7x8码字203332313011103.21（1）D=2消息x1x2x3x4x5x6x7x8x9x10码字1111011000110010001101110001010100（2）D=3消息x1x2x3x4x5x6x7x8x9x10码字22212012100201001111103.22方法一：概率之和与原信源某概率相等，概率之和往上排；方法二：概率之和与原信源某概率相等，概率之和往下排；第一种方法对实用更好3.24（1）H(X)=(1/4)log4+(3/4)log(4/3)=0.811966.2n984.0467.3n842.0967.1n937.0633.1n89.026.3n99.011.2n966.04(2）q(0)＝1/4，q(1)=3/4（3）扩展信源16/916/316/316/111011000xxxxxxxxFano编码消息x0x0x0x1x1x0x1x1码字111110100(4)扩展信源64/2764/964/964/364/964/364/364/1111011101001110010100000xxxxxxxxxxxxxxxxxxxxxxxxHuffman编码D=2消息x1x1x1x1x1x0x1x0x1x0x1x1x1x0x0x0x1x0x0x0x1x0x0x0码字0101101100111111111011101111003.25（1）Shannon编码D＝2消息x1x2x3x4码字010110111(2)Huffman编码D=2，得到的编码与（1）一致（3）之所以得到这种结果，是因为消息的每个概率都可以写成D–ni的形式，取每个码字的码长分别为ni即可。第4章离散信道的信道容量4.7（1）)(3log2pHC（2）)(2log2pHC（3）)/(322.0符号BitC（4）C=e2-(3/2)（5）)/(083.0符号BitC(6))/(082.0符号BitC4.8（1）)/(918.2符号BitC（2）2.0log2.05.0log5.035.0log7.0C4.9(1))()1();(2HqYXI(2)α＝0.5时，I(X;Y)取得最大值2log)1(qC96.06875.1n985.047.2n5(3)2log)0;0(I0);0()0;1(eII4.11符号）（/0312.0BitC4.12（1）log)1log()1()1()1log()1(－－－C（2）2/)1(1logI(1;1)2/)1(logI(1;0)4.14（1）)(221lnHeC（2）3ln]21ln[21ln0)(0)(2eeCH3ln]21ln[21ln1)(0)(2eeCH)2ln21ln0.5)(eC4.15C=0.322(Bit/码符)4.16（1）I(X;Y)=1.5(Bit/符号)（2）I(X;Z)=1.5(Bit/符号)（3）I(X;Z)和I(X;Y)二者相等第5章习题5.10（1）采用极大后验概率译码准则：y1→x1，y2→x2，y3→x1pe1＝11/24(2)信源等概分布，采用极大似然译码准则：y1→x1，y2→x2，y3→x3pe1=1/25.11译码：y1→x1，y2→x3，y3→x2pe1＝21/425.12（1）编码x0：00，x1：11，x2：22，x3：33，x4：44译码00,01,10→00，11,12,21→11，22,23,32→22，33,34,43→33，40,44,04→44pe＝1/4（2）编码：x0：02，x1：14，x2：21，x3：33，x4：40根据最大似然函数译码准则译码：02,03,12,13→02，10,14,29,24→14，21,22,31,32→21，33,34,43,44→33，00,01,40,41→40pe＝05.13（1）最佳分布q(x0)=q(x1)=1/2(2)102ln)25(2ln2ln)2(2),(0qE5.14（1）)1(4)ln),1(1021200ppqqqqqE－)1(21ln),1(max)1(05.00ppqEEq（2）21102002ln,1qpqqqqE）（pE121ln)1(065.15（1）])1(3)1(3[22ppppppe＝（2）2232)1(3)1(2)1(533ppppppppppe(3)计算繁5.17根据最大似然译码准则，译码如下：y0→x1；y1→x1,x3；y2→x1,x3；y3→x3；y4→x1,x2；y5→x0,x1,x2,x3；y6→x0,x1,x2,x3；y7→x0；y8→x1,x2；y9→x0,x1,x2,x3；y10→x0,x1,x2,x3；y11→x0,x3；y12→x2；y13→x0,x2；y14→x0,x2；y15→x0。这样可以得到最小错误概率。5.18（1）)/(322.1符号BitC（2）编码x0：00，x1：11，x2：22，x3：33，x4：44根据最大似然函数译码准则译码：00,01,10→00；11,12,21→11；22,23,32→22；33,34,43→33；40,44,04→44pe=(1/5)[(1/4)+(1/4)+(1/4)+(1/4)+(1/4)]=1/4第6章率失真编码6.5定义域：0≤D≤0.5值域：0≤R(D)≤H(X)=1.5(Bit/符号)6.6定义域：0≤D≤1值域：0≤R(D)≤H(X)=2(Bit/符号)6.7（1）选择信道105.05.001P，可使平均失真min1DD（2）选择信道为0.50.55.05.00.50.5P，可使平均失真34DDmax（说明：题有误，应为34D1Dmaxmin，）6.12DDDDijpDDDHDR11)]([21021012log)(26.132220)()()(DDHHDR反向信道DDDDyx11)]([6.15（1）R(D)=log2-H2[1-(D/β)]（2）当α≥1/2，β=1时，Dmin＝0，Dmax＝min{/2,,/2}=1/272/102/10)(2log)(2DDDHDR6.2110102log)1()(DDDDRDDDD1001P第7章纠错编码代数基础7.1不可构成加群和乘群，无逆元7.2可构成交换加群G={0000，0001，0010，0011，0100，0101，…，1110，1111}G′={0000，0001，0010，0011}0100+G′={0100，0101，0110，0111}1000+G′={1000，1001，1010，1011}1100+G′={1100，1101，1110，1111}7.3无子群7.4构成乘群，不构成加群7.5构成加群，不构成乘群7.630个本原元，本原多项式：x5+x2+1，x5+x4+x3+x2+1，x5+x4+x2+x+1，x5+x3+x2+x+1，x5+x3+1，x5+x4+x3+x+17.7（x+1）（x5+x2+1）（x5+x4+x3+x2+1）（x5+x4+x2+x+1）（x5+x3+x2+x+1）（x5+x