东南大学《信息论与编码》课后答案.pdf 62页

'习题（第1章）1.一位朋友很不赞成“通信的目的是传送信息”及“消息中未知的成分才算是信息”这些说法。他举例说：我多遍地欣赏梅兰芳大师的同一段表演，百看不厌，大师正在唱的正在表演的使我愉快，将要唱的和表演的我都知道，照你们的说法电视里没给我任何信息，怎么能让我接受呢？请从信息论的角度对此做出解释。（主要从狭义信息论与广义信息论研究的内容去理解和解释）答：从狭义信息论角度说，虽然将要表演的内容观众已知，但每一次演出不可能完全相同。而观众在欣赏的同时也在接受着新的感观和视听享受。从这一角度来说观众还是可以得到新的信息的。另一种解释可以从广义信息论角度来说，它涉及了信息的社会性，实用性等主观因素，同时受知识水平、文化素质的影响。京剧朋友们在欣赏京剧时也因为主观因素而获得了享受，因此属于广义信息论范畴。2．利用图1.2所示的通信系统分别传送同样时间（例如十分钟）的重大新闻公告和轻音乐，它们在接收端各方框的输入中所含的信息是否相同，为什么？答：重大新闻是语言，频率为300-3400Hz,而轻音乐的频率为20-20000Hz。同样的时间内轻音乐的采样编码的数据要比语音的数据量大，按码元熵值，音乐的信息量要比新闻大。但在信宿端，按信息的不确定量度信息量就应分别对待，对于新闻与音乐的信息量大小在广义来说因人而异。1 习题（第2章）1．一珍珠养殖场收获240颗外观及重量完全相同的特大珍珠，但不幸被人用外观相同但重量仅有微小差异的假珠换掉1颗。（1）一人随手取出3颗，经测量恰好找出了假珠，问这一事件大约给出了多少比特的信息量；（2）不巧假珠又滑落进去，那人找了许久却未找到，但另一人说他用天平最多6次能找出，结果确是如此，问后一事件给出多少信息量；（3）对上述结果作出解释。解：（1）从240颗珠子中取3颗，含1颗假珠的概率为2CP=239=1C380240I=−logP=log80=.632(bit)22（2）240颗中含1颗假珠，用天平等分法最多6次即可找到假珠，是必然事件，因此信息量为0。（3）按照shannon对信息量的定义，只有事件含有不确知成分，才有信息量，且不确知成分越大，信息量越大，必然事件则没有信息量。但从广义信息论来说，如果那人不知用天平二分法找假珠，另一人告之此事，使他由不知到知，也应该含有一定的信息量。52．每帧电视图像可以认为是由3×10个象素组成，所有象素均独立变化，且每一象素又取128个不同的亮度电平，并设亮度电平等概率出现。问每帧图像含有多少信息量？如果一个广播员在约10000个汉字的字汇中选取1000个字来口述此电视图像，试问广播员描述此图像所广播的信息量是多少（假设汉字字汇是等概率分布，且彼此独立）？若要恰当地描述此图像，广播员在口述中至少需用多少汉字？解：设电视图像每个像素取128个不同的亮度电平，并设电平等概率出现，则每个像素亮度含有的信息量为H(X)=lb128=7比特/像素一帧中像素均是独立变化的，则每帧图像信源就是离散亮度信源的无记忆N次扩展信源。得每帧会图像含有的信息量为N6H(X)=NH(X)=1.2×10比特/每帧广播口述时，广播员是从10000个汉字字汇中选取的，假设汉字字汇是等概率分布的，则汉字字汇中每个汉字含有的信息量1 HY()==lb1000013.29比特/字广播员口述电视图像是从此汉字字汇信源中独立地选取1000个字来描述的。所以，广播员描述此帧图像所广播的信息量为N44H(Y)=NH(Y)=1000lb10=.1329×10比特/千字若广播员仍从此汉字字汇信源Y中独立地选取汉字来描述电视图像，每次口述一N个汉字含有信息量是H(Y)，每帧电视图像含有的信息量是H(X)，则广播员口述此图像至少需要的汉字数等于N6H(X)1.2×105==.158×10=158000字H(Y)13.293．已知X：1,0P(X)：p,1–p(1)求证：H(X)=H(p)(2)求H(p)并作其曲线，解释其含义。（1）证明H(X)=pI(1)+(1−p)I(0)=−plbp−(1−p)lb(1−p)=H(p)（2）H(p)100.51p该H(p)曲线说明，当0与1等概出现时，即p=0.5时，熵最大。当p由0.5分别趋向于0和1时，熵逐渐减小至0。4．证明H(X3|X1X2)≤H(X2|X1)，并说明等式成立的条件。证明：设离散平稳信源输出的随机符号序列为…X1,X2,X3,…。又设2 x∈X,x∈X,x∈X,而且x,x,x都取自于同一符号集112233123A={a,a,",a}，并满足有12g∑P(x2|x1)=,1∑P(x3|x2)=,1∑P(x3|x1x2)=,1X2X3X3∑P(x1)=∑P(x2)=∑P(x3)=1X1X2X3∑∑P(x1x2)=∑∑P(x2x3)=∑∑P(x1x3)=1XX12XX23XX13∑∑∑P(x1x2x3)=1XXX123∑P(x1x2x3)=P(x2x3)X1∑P(x1x2x3)=P(x1x3)X2∑P(x1x2x3)=P(x1x2)X3在区域[0，1]内设f(x)=－xlogx,f(x)在[0，1]内是∩型凸函数，所以满足詹森不等式qqq∑∑Pif(xi)≤f(Pixi)其中∑Pi=1i==11ii=1现今x=P(x|xx),设其概率空间为P(x|x)，并满足i32112∑P(x1|x2)=1X1所以根据詹森不等式得∑P(x1|x2)[−xilogxi]≤−[∑P(x1|x2)xi]log[∑P(x1|x2)xi]X1X1X1−∑P(x1|x2)P(x3|x1x2)logP(x3|x1x2)X1≤−∑P(x1|x2)P(x3|x1x2)log∑P(x1|x2)P(x3|x1x2)X1X1所以3 ∑P(x1x2x3)=P(x2x3)X1∑P(x1x3|x2)P(x2)=P(x3|x2)P(x2)X1上式对所有x,x,x的取值都成立，所以123∑P(x1x3|x2)=P(x3|x2)X1∑P(x1|x2)P(x3|x1x2)=P(x3|x2)X1所以−∑P(x1x3|x2)logP(x3|x1x2)≤−P(x3|x2)logP(x3|x2)X1因为0≤P(x)≤,1x∈X，所以上式两边相乘，等号不变。有222−∑P(x2)P(x1x3|x2)logP(x3|x1x2)≤−P(x2)P(x3|x2)logP(x3|x2)X1上式对所有x,x都成立，所以对所有x,x求和下式也成立2323−∑∑∑P(x1x2x3)logP(x3|x1x2)≤−∑∑P(x2x3)logP(x3|x2)XXX123XX23因为H(X3|X1X2)≤H(X3|X2)所以是平稳信源H(X3|X2)=H(X2|X1)得H(X3|X1X2)≤H(X2|X1)只有当P(x|xx)=P(x|x)(对所有x,x,x)时等式成立。31232123"5．设有一概率空间，其概率分布为{p1,p2,…,pq}，且p1>p2。若取p1=p1−ε，"p2=p2+ε，其中0<2ε≤p1–p2，而其它概率值不变。证明由此得到的新的概率空间的熵是增加的，并用熵的物理意义加以解释。εp−p−ε12证明：令a=>0的小数1−a=p−pp−p1212得4 εpp−−ε12ap+−(1ap)=p+p=+pε12122pp−−pp1212pp−−εε12(1−+=apap)p+p=−pε12121pp−−pp1212因为f(x)=－xlogx是∩型函数，根据∩型凸函数的定义有f[ap+1(−a)p]≥af(p)+1(−a)f(p)1212所以f(p+ε)≥af(p)+1(−a)f(p)212εp−p−ε12即−(p+ε)log(p+ε)≥−[plogp+plogp]221122p−pp−p1212同理得p−p−εε12−(p−ε)log(p−ε)≥−[plogp+plogp]111122p−pp−p1212以上两不等式两边相加，不等号不变。所以得−−(pε)log(pppp−−+εεε)()log(+≥)−logp−plogp112211226．某办公室和其上级机关的自动传真机均兼有电话功能。根据多年来对双方相互通信次数的统计，该办公室给上级机关发传真和打电话占的比例约为3:7，但发传真时约有5%的次数对方按电话接续而振铃，拨电话时约有1%的次数对方按传真接续而不振铃。求：（1）上级机关值班员听到电话振铃而对此次通信的疑义度；（2）接续信道的噪声熵。解：设发传真和打电话分别为事件X1与X2,对方按传真和按电话接续分别为事件Y1和Y2,则P(X1)=30%,P(X2)=70%P(Y1|X1)=95%,P(Y2|X1)=5%,P(Y1|X2)=1%,P(Y2|X2)=99%P(X1Y1)=0.285,P(X1Y2)=0.015P(X2Y1)=0.007,P(X2Y2)=0.693P(Y1)=P(X1Y1)+P(X2Y1)=0.292P(Y2)=1－P(Y1)=0.7085 H(X)=－P(X1)lbP(X1)－P(X2)lbP(X2)=0.8814bit/符号H(Y)=－P(Y1)lbP(Y1)－P(Y2)lbP(Y2)=0.8713bit/符号22H(XY)==1.0239bit/−∑∑P(XiYj)lbP(XiYj)两个信符i=1j=1I(X;Y)=H(X)+H(Y)－H(XY)=0.7288bit/信符（1）听到电话振铃的疑义度H(X|Y2)=－P(X1Y2)lbP(X1Y2)－P(X2Y2)lbP(X2Y2)=0.4575bit/信符（2）接续信道的噪声熵H(Y|X)=H(Y)－I(X;Y)=0.1425bit/信符7．四个等概分布的消息M1，M2，M3，M4被送入如图所示的信道进行传输，通过编码使M1=00，M2=01，M3=10，M4=11。求输入是M1和输出符号是0的互信息量是多少？如果知道第2个符号也是0，这时带来多少附加信息量？XYp00pp11p图2.6解：信源P(M1)=P(M2)=P(M3)=P(M4)=1/4,信道为二元对称无记忆信道，消息Mi与码字一一对应，所以设Mi=(xi1xi2)设接收序列为Y=(y1y2)接收到第一个数字为0，即y1=0。那么，接收到第一个数字0与M1之间的互信息为P(y=|0M)11I(M;y=)0=log11P(y=)01因为信道为无记忆信道，所以P(y=|0M)=P(y=|0xx=00)1111112=P(y=|0x=)0=P)0|0(=p111同理，得I(y=|0M)=P(y=|0xx)=P(y=|0x)1i1i1i21i1输出第一个符号是y1=0时，有可能是四个消息中任意一个第一个数字传送来的。6 所以4P(y1=)0=∑P(Mi)(y1=|0Mi)i=11=[P(y=|0x=)0+P(y=|0x=)0+P(y=|0x=)1+P(y=|0x=1)]41111211311411=2故得I(M;y=)0=1+lbp比特11接收到第二个数字也是0时，得到关于M1的附加互信息为I(M;y=|0y=)0=I(M;yy=00)−I(M;y=)012111211P(yy=00|M)121其中I(M;yy=00)=log112P(yy=00)12同理，因为信道是无记忆信道，所以P(yy=00|M)=P(yy=00|xx)12i12i1i2=P(y=|0x)P(y=|0x)1i12i2P(yy=00|M)=P(y=|0x=)0P(y=|0x=)0121111212得2=P)0|0(P)0|0(=p输出端出现第一个符号和第二个符号都为0的概率为4P(y1y2=00)=∑P(Mi)(y1y2=00|Mi)i=11=[P(y1=|0x11=)0P(y2=|0x12=)0+P(y1=|0x21=)0P(y2=|0x21=)14+P(y=|0x=)1P(y=|0x=)0+P(y=|0x=)1P(y=|0x=1)]1312311412411=42p所以I(M;yy=00)=log=1(2+lbp)比特112147 得附加互信息为I(M;y=|0y=)0=1+lbp比特1218．证明若随机变量X，Y，Z构成马氏链，即X→Y→Z，则有Z→Y→X。证明：因为(X,Y,Z)是马氏链，有P(z|xy)=P(z|y),对所有x∈X,y∈Y,z∈Z成立，而P(x|yz)=P(xyz)/P(yz)=P(z|xy)P(xy)/P(y)P(z|y)=P(z|xy)P(y)P(x|y)/P(y)P(z|y)对所有x∈X,y∈Y,z∈Z成立故得P(x|yz)=P(x|y)对所有x∈X,y∈Y,z∈Z成立所以(Z,Y,X)也是马氏链。8 习题（第3章）21．发出二重符号序列消息的信源熵为H(X)，而一阶马尔可夫信源的信源熵为H(X/X)。试比较这两者的大小，并说明原因。2．设随机变量序列(XYZ)是马氏链，且X：{a1,a2,…,ar}，Y：{b1,b2,…,bs}，Z：{c1,c2,…,cL}。又设X与Y之间的转移概率为p(bj/ai)(i=1,2,…,r；j=1,2,…,s)；Y与Z之间的转移概率为p(ck/bj)(j=1,2,…,s；k=1,2,…,L)。试证明X与Y之间的转移概率为sp()c/a=∑p()b/ap(c/b)kijikjj=13．有一个马尔可夫信源，已知p(xx)=2，p(xx)=1，p(xx)=1，11321312p(xx)=0，试画出该信源的香农线图，并求出信源熵。2221一步转移矩阵为P，P=[33]10⎧2Q(x)=Q(x)+Q(x)⎪1123⎪⎪1可得⎨Q(x2)=Q(x1)⎪3Q(x)+Q(x)=1⎪21⎪⎩3Q(x)=14故{1Q(x)=24所以，信源熵为1 22H∞=H2=−∑∑Q(Ei)P(ak|Ei)logP(ak|Ei)ik==11221=∑Q(Ei)H(ak|Ei)=Q(x1)H(,)+Q(x2)H)0,1(i=1333231=[log+log]3=.06887比特/符号43234．一个马尔科夫链的基本符号为0，1，2三种，他们以等概率出现，且具有相同的转移概率，没有任何固定约束，试（1）画出单纯马尔科夫链信源的香农线图，并求稳定状态下的信源熵H1。（2）画出二阶马尔科夫链信源的香农线图，并求稳定状态下的信源熵H2。1解：（1）由已知得P(j|i)=i,j=2,1,0则香农线图如下31/31/31/3101/31/31/31/31/321/31稳定时H(X)=3×log3=.1585bit/符号32（2）二阶马尔可夫信源，初始状态有3=9个，等概分布1P(m|ij)=3222H2=∑∑∑P(m|ij)logP(m|ij)=.1585bit/符号ijm===0002 010200102211211220图中每条路径概率均为1/35．某一阶马尔可夫信源的状态转移如图3.4所示，信源符号集为X：{0,1,2}，并定义p=1−p。试求：（1）信源的极限熵H∞；（2）p取何值时H∞取最大值。ppp/210p/2p/2p/2p/2p/22p图3.4解：（1）⎡pp⎤p⎢22⎥⎢pp⎥一步转移矩阵为P，P=p⎢22⎥⎢pp⎥p⎢⎣22⎥⎦⎧ppQ(0)=pQ(0)+Q(1)+Q(2)⎪22⎪pp⎪Q(1)=Q(0)+pQ(1)+Q(2)可得⎨22⎪pp⎪Q(2)=Q(0)+Q(1)+pQ(2)22⎪⎩Q(0)+Q(1)+Q(2)=13 1计算得Q)0(=Q)1(=Q)2(=31则得P)0(=P)1(=P)2(=3所以，信源熵为2H∞=H2=∑Q(Ei)H(X|Ei)i=1=P)0(H(X)0|+P)1(H(X)1|+P)2(H(X)2|1pp1pp1pp=H(p,,)+H(,p,)+H(,,p)322322322=−plogp−plogp+p比特/符号（2）因为H=−1(−p)log(1−p)−plogp+p∞求其对p的一阶导数∂H11∞=log(1−p)+−logp−+1∂pln2ln21(2−p)=log(1−p)−logp+log2=logp∂H1(2−p)∞令=,0得log=0∂pp所以当p=2/3时，信源的极限熵达到最大值。6．设随机变量序列X=X1X2…XN通过某离散信道{X;P(Y/X);Y}，其输出序列为Y=Y1Y2…YN。试证明若（1）p(bjN/ai1ai1…aiN；bj1bj2…bjN–1)=p(bjN/aiN)；（2）p(bj1bj2…bjN–1/ai1ai1…aiN)=p(bj1bj2…bjN–1/ai1ai1…aiN–1)则该信道的转移概率为NP(X/Y)=p()bb?b/aa?a=∏p(b/a)j1j2jNi1i2iNjkikk=1证明：4 P(X/Y)=p(bb?b/aa?a)j1j2jNi1i2iN=p()bb?b/aa?a×p(b/aa?a;bb?b)j1j2jN−1i1i2iNjNi1i2iNi1i2iN−1=p()bb?b/aa?a×p(b/a)j1j2jN−1i1i2iN−1jNiN=p()bb?b/aa?a×p(b/a)×p(b/a)j1j2jN−2i1i2iN−2jN−1iN−1jNiNN=...=∏p()b/ajkikk=17．设信源X的N次扩展信源X=X1X2…XN通过信道{X;P(Y/X);Y}，其输出序列为Y=Y1Y2…YN。试证明（1）当信源为无记忆信源，即X1X2…XN之间统计独立时，有N∑I()Xk;Yk≥I(X;Y)；k=1N（2）当信道无记忆时，有∑I()Xk;Yk≥I(X;Y)；k=1NNN（3）当信源、信道均为无记忆时，有∑I()Xk;Yk=I()X;Y=NI()X;Y；k=1（4）用熵的概念解释以上3种结果。证明：（1）设信道输入连续型随机序列X=(X1X2…XN),输出也是连续型随机序列Y=(Y1Y2…YN)，信道的传递概率密度函数为p(y|x)=p(yy?y|xx?x)12N12Nx∈X,y∈Y,y∈Y,x∈X(i=,2,1?,N)iiii因为信源无记忆，即随机序列X中各分量彼此互相独立，因而有Np(x)=∏p(xi)xi∈Xi,x∈Xi=1可得5 p(x|y)I(X;Y)=E[log]X,Yp(x)p(x|y)=[log]ENX,Y∏p(xi)i=1x∈X,y∈Y,x∈Xii另外NNp(x|y)ii∑∑I(Xi;Yi)=∫∫p(xiyi)logdxidyii==11iRRp(xi)p(x|y)11=p(xy)logdxdy∫∫1111p(x)R1p(x|y)22+p(xy)logdxdy∫∫2222p(x)R2p(x|y)NN+?+p(xy)logdxdy∫∫NNNNp(x)RN其中R为实数集。因为????p(x?xy?y)dx?dxdx?dxdy?dydy?dy∫∫∫∫∫∫∫∫1N1N1i−1i+1N1i−1i+1NXX11Xi−1i+XNY1Yi−1Yi+1YN=p(xy)ii所以N∑I(Xi,Yi)i=1p(x|y)?p(x|y)11NN=?p(x?xy?y)logdx?dxdy?dy∫∫∫∫1N1N1N1Np(x)?p(x)XY1Y1XNN1NNN∏p(xi|yi)∏p(xi|yi)i=1i=1=p(xy)logdxdy=[log]∫∫NENXYX,Y∏p(xi)∏p(xi)i=1i=16 NN∏p(xi|yi)i=1∑I(Xi;Yi)−I(X;Y)=E[log]i=1X,Yp(x|y)N∏p(xi|yi)i=1≤logE[]..................................................................()1p(x|y)X,YN∏p(xi|yi)i=1=log∫∫p(xy)dxdyp(x|y)XY因此，=logp(y)p(x|y)?p(x|y)dx?dxdy∫∫11NN1NXY=logp(y)dyp(x|y)dxp(x|y)dx?p(x|y)dx∫∫111∫222∫NNNYX1X2XN=log∫p(y)dy.................................................................................()2Y=log1=0其中（1）式是根据詹森不等式。（2）式是因为p(y)=p(xy)dx=p(y)p(x|y)dxi∫iii∫iiiiXiXi所以p(x|y)dx=1∫iiiXi所以证得N∑I(Xi;Yi)−I(X;Y)≤0i=1N∑I(Xi;Yi)≤I(X;Y)i=1（2）设信道输入连续型随机序列X=(XX?X)，输出连续型随机序列12NY=(YY?Y)。因为信道无记忆，有12NNp(y|x)=∏p(yi|xi)i=17 x∈X,y∈Y,x∈X,y∈YiiiiX和Y的平均互信息NN∏p(yi|xi)P(y|x)i=1]∑I(Xi,Yi)=E[log]=E[logi=1X,Yp(y)X,Yp(y)NNp(y|x)而ii∑I(Xi,Yi)=∑∫∫p(xiyi)logdxidyii=1i=1XiYip(yi)NN∏p(yi|xi)与前半题同理得∑I(X,Y)=[logi=1]iiENi=1X,Y∏p(yi)i=1因此NN∏p(yi)i=1I(X;Y)−∑I(Xi,Yi)=E[log]i=1X,Yp(y)N∏p(yi)i=1=∫∫p(xy)logdxdyp(y)XY根据詹森不等式，有N∏p(yi)i=1≤log∫∫p(xy)dxdyp(y)XY=log∫p(x|y)dx∫?∫p(y1)?p(yN)dy1?dyNXY1YN=log?p(y)?p(y)dy?dy∫∫1N1NY1YN=log1=0∫p(x|y)dx=1X其中因为p(y)dy=1∫iiYi8 N由此证得∑I()Xk;Yk≥I(X;Y)k=1（3）设X和Y的一个取值为α=(αα?α),α∈{a,a,?,a}(i=,2,1?,N)kk1k2kNki12rβ=(bb?b),b∈{b,b,?,b}(i=,2,1?,N)hh1h2hNhi12s信源无记忆时满足NP(a)=P(a)P(a)?P(a)k=,2,1?r（1）kk1k2kN∑P(ak)=∑P(ak1)?∑P(akN)=1N1NXXX而信道无记忆时满足NP(βh|αk)=∏P(bhi|aki)（2）i=1NN及∑P(βh|αk)=1k=,2,1?,r,h=,2,1?,sNY所以当信道和信源都是无记忆时，不但上面（1）和（2）式满足，同时满足P(βh)=∑P(αkβh)=∑P(αk)P(βh|αk)NNXX=∑P(αk1)?P(αkN)P(bh1|ak1)?P(bhN|akN)NX=∑P(ak1)P(bh1|ak1)?∑P(akN)P(bhN|akN)X1XN=∑P(ak1bh1)?∑P(akNbhN)X1XN=P(b)?P(b|)......................................................................)3(h1hNNNN同理P(αkβh)=∏P(akibhi)k=,2,1?,r,h=,2,1?,s……….(4)i=1根据平均互信息的表达式得NNP(βh|αk)I(X;Y)=I(X;Y)=∑P(αkβh)logNNP(β)XYh所以信道和信源都是无记忆的。将(2),(3),(4)式代入得9 NNI(X;Y)=∑?∑∑?∑P(ak1bh1)?P(akNbhN)XX11NNYYP(b|a)?P(b|a)P(b|a)logh1k1hNkN=∑∑P(ab)logh1k1P(b)?P(b)k1h1P(b)h1hNXY11h1P(b|a)+?+∑∑P(ab)loghNkNkNhNP(b)XYNNhN=I(X;Y)+I(X;Y)+?+I(X;Y)1122NN因为Xi(i=1,2,…,N)取自同一信源X，a∈{a,a,?,a}(i=,2,1?,N)，而又ki12r通过同一信道，输出Yi(i=1,2,…,N)，Yi也属同一信源Y,b∈{b,b,?,b}(i=,2,1?,N)又信道的传递概率与i无关（时不变信道），hi12s即P(b|a)=P(b|a)=?=P(b|a)=P(b|a)⎫h1k1h2k2hNkNhk⎪P(ak1bh1)=P(ak2bh2)=?=P(akNbhN)=P(akbh)⎬⎪P(b)=P(b)=?=P(b)=P(b)h1h2hNh⎭其中a,a∈{}a,a,?,akki12rb,b∈{}b,b,?,bhhi12s(i=,2,1?,N)得I(X,Y)=I(X;Y)=?=I(X;Y)=I(X;Y)1122NNNNN所以∑I()Xk;Yk=I()X;Y=NI()X;Yk=110 1.简述信源译码的错误扩展现象。答：由于信道的干扰作用，造成了一定量的错误，这些错误在译码时又造成了更多的错误，这就是通信译码的错误扩展现象。2.针对某种应用，给出一种你认为是有价值的减小信源译码错误扩展的方法。答：在信源编码的每个码字施加和码字等长的附加位，编码时将要写入的信息在新码字上顺序写两边，译码时先译前半段，若码长无误则译后半段，若前后不一致则要求重发，在带宽充足的条件下可以采用这种方法。3.试说明已有的解决信源译码错误扩展问题的方法，简述其基本思路及利弊。答：信道编码的方法优点：加入了纠错码，减少了译码错误的可能性，减少了发生错误扩展的概率。]缺点：需要对发送的码字加入冗余，是一种降低效率来换取可靠性的方法。4.某通信系统使用文字字符共10000个，据长期统计，使用频率占80%的共有500个，占90%的有1000个，占99%的有4000个，占99.9%的7000个。（1）求该系统使用的文字字符的熵；（2）请给出该系统一种信源编码方法并作简要评价。解：8.01.0.009.0009H(X)=−8.0log−1.0log−.009log−.0009log(1)50050030003000.0001−.0001log=10.198比特/信符3000(2)可以使用huffman编码的方法，为使压缩效果理想，可以使用扩展信源的方法。5.一通信系统传送的符号只有3个，其使用概率分别为0.2、0.3和0.5，但传送时总是以3个符号为一个字，故该系统的信源编码以字为基础并采用二进制霍夫曼编码。根据字的概率大小，编码结果为：概率在(0，0.020)，采用6比特；在(0.020，0.045]，采用5比特，但允许其中一个用4比特；在(0.045，0.100]，在0.100以上，采用3比特。求该种信源编码的效率。解：假设三个符号分别为abc，则p(a)=0.2,p(b)=0.3,p(c)=0.5下面对每个字可能出现的情况加以讨论。33个符号都为a则P=2.0=.0008编6bit码，共1种33个符号都为b则P=3.0=.0027编5bit码，共1种33个符号都为c则P=5.0=.0125编3bit码，共1种23个符号有2个a，1个b则P=2.0×3.0=.0012编6bit码，共3种23个符号有2个a，1个c则P=2.0×5.0=.002编5bit码，共3种23个符号有2个b，1个a则P=3.0×2.0=.0018编6bit码，共3种23个符号有2个b，1个c则P=3.0×5.0=.0045编5bit码，共3种23个符号有2个c，1个a则P=5.0×2.0=.005编4bit码，共3种23个符号有2个c，1个b则P=5.0×3.0=.0075编4bit码，共3种3个符号有1个a，1个b,1个c则P=2.0×3.0×5.0=.003编5bit码，共6种平均码长为⎛.0012×6+.002×5+.0018×6⎞.0008×6+.0027×5+.0125×3+⎜⎜⎟⎟×3+.003×5×6⎝+.0045×5+.005×4+.0075×4⎠＝4.488bit/字sH(X)=（−∑PilogPi）×3=(−2.0log22.0−3.0log23.0−5.0log2)5.0×3i=1=.4455bit/字η1=R1/C=4.455/4.488=99.26% 6.设有一个无记忆信源发出符号A和B，已知p(A)=1/4,p(B)=3/4。（1）计算该信源熵；（2）设该信源改为发出二重符号序列消息的信源，采用费诺编码方法，求其平均信息传输速率；（3）又设该信源改为发三重序列消息的信源，采用霍夫曼编码方法，求其平均信息传输速率。解：（1）该离散无记忆信源的熵为sH(X)=−∑PilogPi=−.025log2.025−.075log2.075=.0811bit/符号i=1（2）费诺编码消息符码组消息概第一次第二次第三次二进制号序号长度率pi分解分解分解代码组(i)biBB9/16(9/16)001AB3/16(3/16)0102BA3/16(7/16)1(3/16)01103AA1/16(4/16)1(1/16)111139331编码的平均长度为b=+×2+×3+×3=.16875码元/符号16161616H(X).261平均传输速率为R===.0953比特/时间b.274（3）霍夫曼编码0BBB27/640100BAA9/640(18/64)01.0101BAB9/6411110ABB9/640(37/64)11100AAB3/640(6/64)0(19/64)111101ABA3/641(10/64)111110BAA3/640(1/16)111111AAA1/64127931编码的平均长度为b=+×3×3+×5×3+×5=.246875码元/符号64646464H(X)平均传输速率为R==.09855比特/时间b7.已知一个信源包含8个符号消息，它们的概率分布如下表：ABCDEFGH0.10.180.40.050.060.10.070.04（1）信源每秒钟内发出一个符号，求该信源的熵及信息传输速率；（2）对这8个符号作二进制码元的霍夫曼编码，写出各个代码组，并求出编码效率。8解：（1）该信源的熵H(X)=−∑PilogPi=.255bit/符号i=1信息传输速率R=2.55bit/s （2）霍夫曼编码C0.40B0.1801.0A0.100.230F0.1010.3710.611G0.0700.13E0.0610.191D0.0500.091H0.041编码结果：CBAFGEDH0110100111010101011111011111b=0.4+.018×3+1.0×3+1.0×4+.007×4+.006×4平均码长为：+.005×5+.004×5=.261码元/符号.255所以编码效率为η==978.%.2618.设信道基本符号集合A={a1,a2,a3,a4,a5}，它们的时间长度分别为t1=1,t2=2,t3=3,t4=4,t5=5（各码元时间）用这样的信道基本符号编成消息序列，且不能出现aa,aa,aa,aa这四种符号相连的11222112情况。（1）求这种编码信道的信道容量；（2）若信源的消息集合X={x1,x2,…,x7}，它们的出现概率分别是P(x1)=1/2,P(x2)=1/4,P(x3)=1/8,…,P(x6)=P(x7)=1/64,试求按最佳编码原则利用上述信道来传输这些消息时的信息传输速率；（3）求上述信源编码的编码效率。解：（1）这是一个有固定约束的不均匀编码的信道，有约束条件（即不能出现a1a1,a2a2,a2a1,a1a2），可以把a1,a2作为状态1，a3,a4,a5作为状态2，得香农线图时间长度分别为b11=∞,b12(a3)=3,b12(a4)=4,b12(a5)=5,b21(a1)=1,b21(a2)=2,b22(a3)=3,−3−4−5−6−7b22(a5)=5,写出行列式，可得特征方程为1−w−2w−3w−2w−w解方程可得w=.1597max所以C=logw=.0675bit/码元时间2max（2）因为规定a1a2不能连用，故不能用和做码字，根据最佳编码的两个原则，及单译可译定理，出现概率大的消息用短码的原则，可用x1x2x3x4x5x6x71/21/41/81/161/321/641/64a3a4a1a3a5a1a4a2a3a2a43445556sH(X)=−∑PilogPi=.1969bit/符号i=1b=∑Pibi=.3641码元IH(x)R==.0541bit/码元时间b （3）编码效率为η=R/C=0.541/0.675=80% 45．1H(X)=H(Y)=−∑P(Xi)log2P(Xi)=2i=144H(XY)=∑∑P(xy)lbP(xy)=4×（1log8+3×1log24）=.379比特/符号ijij82242ij==11I(X;Y)=H(X)+H(Y)−H(XY)=.021比特命题得证。5．2H(X)=5log8+3log8=.09544比特/符号825823H(Y)=1log2+1log2=1比特/符号222222H(Y|X)=−∑∑P(x)P(y|x)logP(y|x)=（53log5+2log5）iji2ji8523522ij==11+（31log3+2log3）=.0951比特/符号832322I(X;Y)=H(Y)−H(Y|X)=.0049比特/符号R=0.049*1000=49比特5．3H(X)=2×log2=1比特/符号2H(Y)=2log3+1log3=.0918比特/符号32232H(XY)=5log12+1log12+1log4+1log4=.1825比特/符号12251224242I(X;Y)=H(X)+H(Y)−H(XY)=.0093比特/符号5．4C=1(+1log100+99log100)×1000=919比特/符号10021002995．5（1）由图可知这是个对称信道，当输入符号等概时，C=maxI(X;Y),p(xy)=P(x)P(y|x),1/81/800P(xy)=01/81/80001/81/81/8001/84C=log24+∑P(yj|xi)log2P(yj|xi)对任意x均成立j=1所以，C=1比特/符号。（2）由图可知，信道亦为对称信道，C=maxI(X;Y) P(xy)=P(x)P(y|x)=1/61/61/121/121/121/121/61/64C=log24+∑P(yj|xi)log2P(yj|xi)=0.0817比特/符号j=1（3）同上，信道为对称离散信道，P(xy)=1/61/91/181/181/61/91/91/181/633C=log23+∑∑P(yjxi)log2P(yj|xi)=.0126比特/符号。i=1j=15．6设P(x)=P(x)=a，则P(x)=1−2a，P(y)=1−2a,3211据对称性P(y)=P(y)=a,32I(X;Y)=H(Y)−H(Y|X)""=−[(1−2a)ln(1−2a)+2alna]−2a(εlnε+εlnε)−0],1由∂I/a=0，得a=1/[2+]，εε"εε"εε"代入I(X;Y)=ln(1+2εε")εε"所以C=ln(1+2εε")奈特/符号。5．7该信道可看成4个BSC信道串联而成，π=1-εε1ε1-ε4π=π=1-4ε(1-ε)[1-2ε(1-ε)]4ε(1-ε)[1-2ε(1-ε)]14ε(1-ε)[1-2ε(1-ε)]1-4ε(1-ε)[1-2ε(1-ε)]级联后的信道仍是对称信道，可代入公式：C=1+εlogε+1(−ε)log(1−ε)bsc其中ε--〉4ε(1-ε)[1-2ε(1-ε)]1-ε--〉1-4ε(1-ε)[1-2ε(1-ε)]则C"=1+4ε(1-ε)[1-2ε(1-ε)]log{4ε(1-ε)[1-2ε(1-ε)]}+1-4ε(1-ε)[1-2ε(1-ε)]log{4ε(1-ε)[1-2ε(1-ε)]}−4代入ε=10，得C’=0.9949所以信道容量C’=C*1024=1018.8kbps。5．8由图可知信道为对称信道，且信源的符号消息等概分布，因此C=lb3=.158比特/符号。 P(xy)5．9后验概率P(x|y)=，又P(xy)=P(x)P(y|x),根据题目所给的数据得P(y)1/41/61/12P(xy)=1/241/81/121/121/241/8由P(y)=∑P(xy),得XP(y)=[3/81/37/24]所以2/31/22/7P(x|y)=1/93/82/72/91/83/7根据最小错误概率准则，应作如下译码：y−>x,y−>x,y−>x112133错误概率为P=1−P=1−{P(x)P(y|x)+P(x)P(y|x)+P(x)P(y|x)}Ec111121333=1−2/1{×2/1+2/1×3/1+4/1×}2/1=1−13/24=11/24LM15．10（1）PE=∑∑P(yj|xi)=(2/1P(y1|x2)+P(y2|x1))=pMj=1i=1i≠*LM1（2）PE=∑∑P(yj|xi)=2/1P(y1|x2)=p2/Mj=1i=1i≠*LM1（3）PE=∑∑P(yj|xi)=(2/1P(y2|x2)+P(y2|x1))=pMj=1i=1i≠*5．11？？5．12（1）对信源四个消息进行编码，选择码长n=4，这组码为C:{(x,x2/1,2/1,)}x=0或1i=(1,2)12i编码后的信息传输率log41R==比特/符号42（2）设接收序列β=(yyyy)y∈1,0{}(i=)4,3,2,1根据信道的传输特性，输入序列1234iβ共有16个，正好分成4个互不相交的子集，每个码字只传输到其中对应的一个子集：α=(001/21/2)Æ(00yy)α=(011/21/2)Æ(01yy)134234α=(101/21/2)Æ(10yy)α=(111/21/2)Æ(11yy)334434 所以根据选择的译码规则f(yyyy)=(yy1/21/2)123412正好将接收序列译成所发送的码字，可计算每个码字引起的错误概率(i)Pe=[∑P(β|αi)F(β)≠αi]=0Yi所以有PE=∑P(αi)Pe=0。CP(xy)513(1)P(x|y)=，又P(xy)=P(x)P(y|x),P(y)=∑P(xy),根据题目所给的数据得P(y)XP(y)=[7/125/12]P(x|y)=6/73/51/72/5又H(X)=−∑P(x)logP(x)≈.0811比特/符号XH(X|Y)=−∑∑P(x)P(x|y)logP(x|y)=XY[−4/3×3/2log3/2−4/1×3/1log3/1−4/3×3/1log3/1−4/1×3/2log]3/2=−3/2log3/2−3/1log3/1≈.039+.0528≈.0918所以I(X;Y)=H(X)−H(X|Y)≈.0062比特/符号(2)此信道为二元对称信道，所以信道容量C=1−H(p)=1−H)3/2(=.0082比特/符号根据二元对称信道的性质可知，输入符号为等概分布，即P(0)=P(1)=1/2时信道的信息传输率才能达到这个信道的容量值。5．14（1）由P(y)=∑P(xy),得XP(y)=[1/21/4+1/4a1/4-1/4a]3H(Y)=−∑P(yi)logP(yi)=2/1−4/1(+4/1a)log(4/1+4/1a)−所以i=14/1(−4/1a)log(4/1−4/1a),H(Y|X)=−∑∑P(x)P(y|x)logP(y|x)=a2/1(log2+2/1log)2XY（2）+1(−a)(2/1log2+4/1log)4+1(−a4/1)log4=2/3−2/1a比特/符号H(Y)−H(Y|X)=−1+2/1a−1(4/1+a)log(4/1+4/1a)−(3)C=1(4/1−a)log(4/1−4/1a) 6.1(1)收到传真的概率为8/(4+8+3+1)*2/(7+1+2)=1/10I=-log1/10=3.3比特（2）可采取压缩编码，安最佳编码原则编码等措施（3）编码时码长尽可能长，这样根据香浓第二定理，总存在一种编码，只要码长足够长，总存在一种编码，是错误概率任意小。最好结合实际分析如何克服随机，突发干扰。2.1（4）C=Blog(1+S/N)=2.048log(1+10)=8.34Mbps，不失真条件下，该信道允许最大信息传输速率为8.34Mbps。26.2（1）h(x)=−p(x)logp(x)dx=2/1log2(πeσ)比特/样值∫2（2）对样值进行256级量化，当其服从均匀分布时，信源有最大熵，H=log256=8比特/符号（3）f=120KHz−12KHz=108KHzsB=8f2/=432KHzs所以C=Blog1(+S/N)=.431M。2（4）S/N=36dB,C=5.17Mbps所以S=.5(17−.431.4/)31=20%。c26.3(1)h(x)=2/1log2(πeσ)比特/样值28×8K−.855K（2）冗余度=×100%=866.%8×8K（3）C=Blog1(+S/N)其中C=9.6KB=1.2288*2Mbps,2得S/N=-25.7dB3.0(4)C=Blog1(+S/N)=2.4576log1(+10)=.388Mbps2216.4由于P(x)=1/2=,所以电压为1V~(-1)V上的均匀分布，1−(−)1又n=2ϖT",所以10=2ϖ，ϖ=5000h=2ϖ*（1/2）lb(4Ps)=ϖlb(4*1)=2ϖ=10bit/st0006.51h(x)=−p(x)lnp(x)dxp∫−11=−∫1(−|x|)ln(1−|x|)dx−11=−2∫1(−x)ln(1−x)dx−又n=2ϖT",所以10=2ϖ，ϖ=5000 1所以h=2ϖh(x)=−201(−x)ln(1−x)dxt0p∫06.62h(x)=−∫p(x)lnp(x)dx02=−∫kxln(kx)dx0366.7C=Blog1(+S/N)=Blog1(+10)=30×30×10×log10=B*.9972227所以B=3×10Hz.586.8(1)C=log64×log16×5×10×25=6×10bit22(2)又C=Blog1(+S/N)2S而10log=30dB，10N3所以S/N=10,3所以C=Blog1(+10)=9.97B27B=6×10Hz6.9C=Blog1(+S/N)2PP所以6.5=4log1(+)=1(4+)2NnB0−5所以P=2.3×10W.Sn0BS6.10C=Blog1(+S/N)=log1(+)22nSnB00n0BSS所以limC=lim[log1(+)]()（2）2B−>∞B−>∞SnBn00利用关系式lim/1xlog1(+x)=loge≈.144，22x−>0SS所以式（2）变为limC=loge≈.144，为一常量。2B−>∞nn00π2/6.11H(X)=−∫−AcosxlnAcosxdxπ2/ π2/π2/=−AlnA∫−π2/cosxdx−∫−π2/Acosxlncosxdx再由逐步分布积分得H(X)=-2AlnA-2Aln2+2A.π2/因为∫−p(x)dx=1，所以2A=1A=1/2π2/所以H(X)=1奈特/自由度a6.12（1）H(X)=−∫p(x)logp(x)dx0a22=−∫bxlogbxdx0aa2=-logb∫p(x)dx-2b∫xlogxdx00332ba2ba=loge−loga−logb93a3因为∫p(x)dx=1，所以b=8/1。0a3故H(X)=2/3loge+loga-log3dX(2)若Y=X+A，则=1,所以H(Y)=2/3loge+loga-log3dYdX(3)若Y=2X，则=2/1，所以H(Y)=H(X)-log1/2=2/3loge+loga-log3/2。dY676.13C=Blog1(+S/nB)=5.6×10log1(+45)5.6/5.=.195×10bit/s2026.14C=Blog1(+S/N)266(1)C=10×log1(+10)=.346×10bit/s266(2)10×log1(+10)=Blog1(+)5所以B=.134×10Hz2266(3)10×log1(+10)=5.0×10log1(+S/N)所以S/N=12022 第七章习题1.设某二址接入信道，输入X1,X2和输出Y的条件概率为P(Y/X1X2)，其值是：p(0/00)=1–εp(0/01)=1/2p(0/10)=1/2p(0/11)=εp(1/00)=εp(1/01)=1/2p(1/10)=1/2p(1/11)=1–ε其中ε<1/2，试求其容量界限。2.设某广播信道，其输入X和输出Y1、Y2之间的条件概率P(Y1/X)和P(Y2/X)的具体值是：pYX(/):(0/0)1p=−===εp(1/0)εεp(0/1)p(1/1)1−ε11111pYX(/):(0/0)1p=−===εp(1/0)εεp(0/1)p(1/1)1−ε22222其中ε1<1/2,ε2<1/2，试求其容量界限。3.计算图7.12中二址接入信道的容量。X1X2Y100001121101111图7.16167 第8章习题1.设输入符号表与输出符号表为X=Y={0,1,2,3}，且输入信号的分布为p(X=i)=1/4,i=0,1,2,3设失真矩阵为⎛⎞0111⎜⎟1011d=⎜⎟⎜⎟1101⎜⎟⎜⎟⎝⎠1110求D和D及RD()。maxminmax⎡X⎤⎡0123⎤⎢⎥=⎢⎥⎣P(X)⎦⎣14141414⎦rD=∑p(a)⋅{mind()a,b}miniijji=1r⎧⎫Dmax=min⎨∑p(ai⋅)d()ai,bj⎬j⎩i=1⎭⎡0111⎤⎢⎥1011[]D=⎢⎥⎢1101⎥⎢⎥⎣1110⎦D=0min⎧3333⎫3Dmax=min⎨,,,⎬=⎩4444⎭4R()D=0max⎛⎞12⎛X⎞⎛−101⎞⎜⎟2.设无记忆信源⎜⎜⎟⎟=⎜⎜⎟⎟，接收符号AY={1/2,1/2}，失真矩阵D=⎜⎟11。⎝p(X)⎠⎝3/13/13/1⎠⎜⎟⎝⎠21试求：Dmax和Dmin及达到Dmax和Dmin时的转移概率矩阵。⎡X⎤⎡−101⎤⎢⎥=⎢111⎥⎣P(X)⎦⎢⎣333⎥⎦⎡12⎤[]⎢⎥D=11⎢⎥⎢⎣21⎥⎦⎧44⎫4Dmin=1,Dmax=min⎨,⎬=⎩33⎭3在D时，min⎧⎪∑p()bjai=1由于⎨j∈Ji，所以⎪p()ba,j∉J⎩jii1 ⎡10⎤[]P=⎢11⎥⎢22⎥⎢⎣01⎥⎦在D时，max由于p(ba)=P(b)，所以jij⎡10⎤[]⎢⎥P=10⎢⎥⎢⎣10⎥⎦3.三元信源的概率分别为p(0)=0.4,p(1)=0.4,p(2)=0.2，失真函数dij为：当i=j时，dij=0；当i≠j时，dij=1(i,j=0,1,2)，求信息率失真函数R(D)。⎡X⎤⎡012⎤⎢⎥=⎢⎥⎣P(X)⎦⎣4.04.02.0⎦⎡011⎤[]⎢⎥D=101⎢⎥⎢⎣110⎥⎦D=0，R()0=H(X)=2lb5+2lb5+1lb5=lb5−8.0≈.152min52525D=min{}8.0,6.0,6.0=6.0maxR()D=0max由定义知：R(D)=min{}I(X;Y)，I(X;Y)=H(X)−H(X|Y)P()bj/ai∈BD平均失真度一定与试验信道的平均错误概率Pe有关，即rsD=∑∑P(ai)P(bj/ai)d(ai,bj)i==11js=∑P(ai)P(bj/ai)=Pei≠j根据保真度准则，应有Pe≤D根据Fano不等式H(X/Y)≤H(Pe)+Pelog(r–1)⇒H()(X|Y≤HP)+Plb2ee⇒H()(X|Y≤HP)+P≤H(D)+Dee∴R()D=H()X−H(D)−D=lb5−8.0−H()D−D⎧lb5−8.0−D−H()D0≤D≤0.6R()D=⎨⎩0D>0.624.设有一连续信源，其均值为0，方差为σ，熵为H(X)，定义失真函数为“平方误差”失真，即X2dxy(,)(=−xy)。证明其率失真函数满足下列关系式：211σXH(X)−log2πeD≤R(D)≤log22D当输入信源为高斯分布时等号成立。证明：（1）证明上界：2 1R(D)≥H(X)−log2πeD2连续信源R(D)函数是在⎧()px|y≥0⎪⎪∞⎨∫p()x|ydx=1−∞⎪∞⎪D=∫∫p()(xpx|y)(dx,y)dxdy=D⎩−∞约束条件下，求平均互信息：∞∞p()x|yI()X;Y=p(x)p()x|ylbdxdy∫∫−∞−∞p()x引入参量S和待定函数λ()x。在失真不超过D时，I(X;Y)为下确界的试验信道满足⎧⎪()()()Sd()x,ypx|y=pyλxe00⎪⎪∞Sd()x,y⎨∫λ()()xpxedx=1−∞⎪−1∞⎪λ()x=⎡p()yeSd()x,ydy⎤⎪⎩⎢⎣∫−∞0⎥⎦∞∞()()()()()Sdx,y()Ds=pxpyλxedx,ydxdy∫∫0−∞−∞∞R()S=SD()S+∫p()()xlbλxdx−∞由泛函分析中的变分法求I(X;Y)的条件极值2令x−y=θ,d()()x,y=dθ=θ由于以上规定了下确界，则∞()()()Sdx,y∫λxpxedx≤1（1）−∞设集合∞(){Sdx,y}Λ=λ()x:λ()()xpxedx≤,1任意ys∫−∞∞则有R()D=sup⎡SD()S+∫p()()xlbλxdx⎤（2）⎢⎣−∞⎥⎦s≤,0λ()x∈ΛsK()S令λ()x=p()x−1∞()其中K()S=⎡eSdθdθ⎤⎢⎣∫−∞⎥⎦∞()Sdx,y由（1）得K()S⋅∫edx≤1−∞∞()Sdθ即K()S⋅∫edθ≤1−∞2当d()θ=θ时，且S<0，∞2∞2得eSθdθ=2eSθdθ=π<∞∫−∞∫−∞−S由（2）（3）两式，有3 ∞K(S)R()D≥SD+∫p()xlbdx−∞p()x∞1∞1=SD+∫p()xlbdx−∫p()xlbdx−∞p()x−∞K()S（4）∞∞()=SD+H()X−p()x⎡lbeSdθdθ⎤dx∫−∞⎢⎣∫−∞⎥⎦∞()()Sdθ=SD+HX−lb∫edθ−∞由对数得换底公式，有∞()()()Sdθln2⋅RD≥SD+HX−ln∫edθ=R（5）−∞若要（1）式等号成立，则等效于（5）式等号成立。Sd()θ∞eR′=D−∫d()θdθ−∞∞Sd()θ∫edθ−∞Sd()θe令g()θ=S∞Sd()θ∫edθ−∞∞则R′=D−g()()θdθdθ∫S−∞然后再求二阶导数，得2∞∞R′′=−g()()θd2θdθ+⎡g()()θdθdθ⎤∫−∞S⎢⎣∫−∞S⎥⎦{}[]2()2[]()=−Edθ−Edθ由于g()θ是d()θ得概率密度函数S∞Sd()θ∞∫edθ−∞且g()θdθ==1∫−∞S∞Sd()θ∫edθ−∞所以R′′≤0，即（5）式右边为上凸函数，在R′=0的S上确极大值，有∞D=∫g()()θdθdθS−∞2代入d()θ=θ得()−SSθ2gθ=eSπ∞−S2Sθ21D=∫θedθ=−（6）−∞π2S由式（5）得∞2()1()Sθln2⋅RD≥−+HX−lnedθ2∫−∞=H()X−1lne−lnπ2−S=H()X−1lne−1ln2Dπ22=H()X−1ln2πeD2即R()D≥=H()X−1ln2πeD24 21σX（2）证明上界R(D)≤log2D设信道的传递函数的概率为：1⎡12⎤p′()y|x=exp⎢−()y−βx⎥2πβD⎣2βD⎦β=1−D。它是已知X=x时y的概率分布，即均值为βx，方差为βD的高斯分布，其中2δ∞∞D=∫∫p()(xp′y|x)(dx,y)dxdy−∞−∞∞∞2=∫p()xdx∫(y−x)(p′y|x)dy−∞−∞∞∞222=∫p()xdx{}∫[](y−βx)−2xy(1−β)+x()1−βp′()y|xdy−∞−∞∞∞⎧()()y−βx2p′y|xdy−2xy()()1−βp′y|xdy⎫∞⎪∫−∞∫−∞⎪=∫−∞p()xdx⎨∞⎬22⎪+x()1−β∫p′()y|xdy⎪⎩−∞⎭∞22=∫{}βD−2x()1−ββx+x()1−βp()xdx−∞∞[]()22()=∫βD+1−βxpxdx−∞∞()22()=βD+1−β∫xpxdx−∞()22=βD+1−βσX=D设B={}p()y|x:D≤D，p′()y|x∈BDD由于R()D=Inf{I()X;Y}p()x|y∈BD所以R()(D≤I′X;Y)I()(X;Y=HY)−H(Y|X)=H()Y−1lb2πeβD2输出信号Y=β()X+Z，E{}Y=β{}E()X+E(Z)=0{2}2{(2)(2)}222EY=βEX+EZ=βσX+βD=σX−D2于是Y时均值为零，方差为(σ−D)的随即变量。X当方差受限时，高斯随即变量的差熵最大，有()1(2)HY≤lb2πeσ−D2XI()X;Y≤1lb2πe()σ2−D−1lb2πeβD2X21()σ2−D1σ2XX=lb=lb2βD2D21σ()()XRD≤I′X;Y≤lb2D当且仅当p()x是高斯分布时，上式等号成立。5 211σX综上所述，H(X)−log2πeD≤R(D)≤log22Da−ax||5.随机变量X服从对称指数分布px()=e，失真函数为d(x,y)=|x–y|，求信源的R(D)。2()a−axpx=e，d()x,y=x−yX2令θ=x−y，得d()θ=θSd()θSθee且g()θ==S∞∞Sd()θSθ∫edθ∫edθ−∞−∞∞∞SθSθ2∫edθ=2∫edθ=−∞0SSSθ得g()θ=eS2∞D=g()()θdθdθ∫S−∞S∞Sθ=∫θedθ2−∞S∞Sθ=⋅2∫θedθ20S11=⋅2⋅=22SS对g()θ进行傅立叶变换S∞()()−jωθGω=gθedθS∫S−∞2S=22S+ω22S+ωQ()ω=P()ω2S2ω=P()ω+P()ω2S1∞()∫()−jωypy=QωedωY2π−∞()()2()py=px=y−Dp′′x=yYXX3()a−aya2−ay∴py=e−DeY22()22a−ay=1−aDe21由p()y≥0，得D≤Ya6 ∞D=Infp()(xdx,y)dxmax∫X−∞y∞a−ax且=Inf∫x−yedxy−∞21=a1当0≤D≤D=时maxaR()D=R()D=H(X)(−Hg)LS2e=lb−lb2eDa1=−lbaD,0≤D≤a⎧A,||fF≤16.设有平稳高斯信源X(t)，其功率谱为Gf()=⎨，失真度量取⎩0,|f|>F12dxy(,)(=−xy)，容许的样值失真为D。试求：（1）信息率失真函数R(D)；N0（2）用一独立加性高斯信道（带宽为F，限功率为P，噪声的双边功率谱密度为）来传送22上述信源时，最小可能方差与F的关系。2（1）对于时间连续的平稳高斯信源，当功率谱密度已知时，1∞R()D=∫max{},0lb()−2SG()ωdω4π−∞1∞⎧1⎫R()D=∫min⎨−,G()ω⎬dω2π−∞⎩2S⎭在本题中1∞⎧1⎫R()D=∫min⎨−,G()ω⎬dω2π−∞⎩2S⎭∞⎧1⎫=∫min⎨−,G()f⎬df−∞⎩2S⎭F11=∫−df−F12SF1⎛1⎞=−⎜设A>-⎟S⎝2S⎠F1即S=−D7 1∞R()D=∫max{},0lb()−2SG()ωdω4π−∞1∞=∫max{},0lb()−2SG()fdf2−∞1F1=∫lb()−2SAdf2−F1=Flb()−2SA12AF1=Flbbit/s1D0≤D≤2AF1⎛P⎞（2）信道容量为C=Flb⎜1+⎟bit/s2⎜FN⎟⎝20⎠由定理可知，当C≥R(D)时，可以采用最佳编码，其硬气的错误小于等于D。取R()D=C,求得最小均方误差D。2AF⎛P⎞1⎜⎟Flb=Flb1+1D2⎜FN⎟⎝20⎠−F2⎛P⎞F1∴D=2FA⎜1+⎟1⎜FN⎟⎝20⎠D令β=F2F1，α=FN10−βD⎛α⎞得=⎜⎜1+⎟⎟2F1A⎝β⎠Dβ=0时，=12FA1D−1β=1时，=()1+α2FA1−β⎛α⎞−αβ→∞时，由于lim⎜⎜1+⎟⎟=eβ→∞⎝β⎠D−α所以→e如下图：2FA18 D2FA1()−11+α−αeβ−1F2β=F17.某工厂的产品合格率为99%，废品率为1%。若将一个合格产品作为废品处理，将损失1元；若将一个废品当作合格产品出厂，将损失100元；若将合格品出厂，废品报废，不造成损失。试分析质量管理中各种情况造成的损失及付出的代价。解根据题意有信源空间：好（合格）废（废品）P(好)=0.99P(废)=0.01选择失真函数为d(好，好)=0d(废，废)=0d(好，废)=10d(废，好)=100失真矩阵为好废好⎡01⎤[]D=⎢⎥废⎣1000⎦可将产品检验分成如下4种情况：全部产品都当合格品，全部产品都当废品，完美的检验和允许出错的检验。下面分别进行讨论。情况1全部产品不经检验而出厂——都当合格品。把这一过程看作是一个“信道”，其“传递概率”为P(好/好)=1P(废/好)=0P(好/废)=1P(废/废)=0信道矩阵为好废好⎡10⎤Π=⎢⎥废⎣10⎦这种情况的平均损失，即平均失真度，为D=∑∑P(ai)P(bj/ai)d(ai,bj)ij=P(好)⋅P(好/好)⋅d(好,好)+P(好)⋅P(废/好)⋅d(好,废)+P(废)⋅P(好/废话)⋅d(废,好)+P(废)⋅P(废/废)⋅d(废,废)=0.01×1×100=1元/个情况2全部产品不经检验全部报废——都当废品这时的信道传输概率为P(好/好)=0P(废/好)=1P(好/废)=0P(废/废)=1信道矩阵为9 好废好⎡01⎤Π=⎢⎥废⎣01⎦平均失真度为D=∑∑P(ai)P(bj/ai)d(ai,bj)ij=P(好)⋅P(好/好)⋅d(好,好)+P(好)⋅P(废/好)⋅d(好,废)+P(废)⋅P(好/废)⋅d(废,好)+P(废)⋅P(废/废)⋅d(废,废)=0.99×1×1=0.99元/个D=.099maxR(D)=0max全部报废造成损失小于全部出厂造成的损失。情况3经过检验能正确无误地判断合格品和废品——完美的检验这相当于无噪信道的情况，信道矩阵为好废好⎡10⎤Π=⎢⎥废⎣01⎦平均失真度为D=0即这种情况不会另外造成损失。情况4检测时允许有一定的错误——非完美的检验设检验的正确率为p，则信道的传输概率为P(好/好)=pP(废/好)=1-pP(好/废)=1-pP(废/废)=p信道矩阵为好废好⎡pp-1⎤Π=⎢⎥废⎣p-1p⎦平均失真度为D=∑∑P(ai)P(bj/ai)d(ai,bj)ij=P(好)⋅P(废/好)⋅d(好,废)+P(废)⋅P(好/废)⋅d(废,好)=0.99×(1-p)×1+0.01×p×100=1.99(1-p)元/个8.设输入符号表为X={0,1}，输出符号表为Y={0,1}。定义失真函数为：d(0,0)=d(1,1)=0d(0,1)=d(1,0)=1试求失真矩阵[D]。d()()0,0=d1,1=010 d()()1,0=d0,1=1⎡01⎤[]D=⎢⎥⎣10⎦9.某二元信源X的信源空间为[]⎧X:a1,a2X⋅P=⎨⎩P(X:)w1,−w其中w<1/2，其失真矩阵为⎡0d⎤[]D=⎢⎥⎣d0⎦（1）试求D和RD()；maxmax（2）试求D及RD()；minmin（3）试求R()D；（4）写出取得R()D的试验信道的各传递概率；（5）当d=1时，写出与试验信道相对应的反向试验信道的信道矩阵。⎡X⎤⎡a1a2⎤解：⎢⎥=⎢⎥⎣P(X)⎦⎣ω1−ω⎦⎡0d⎤[]D=⎢⎥⎣d0⎦（1）D=min{}dω,d()1−ω=dω（因为ω<2/1）maxR()D=0max（2）D=0minR()(D=HX)=−ωlbω−()1−ωlb(1−ω)=H(ω)minSdij（3）由于∑λiP()xie=1iSd令e=β，则⎡1β⎤[]ωλ,()1−ωλ⎥=[1,1]12⎢⎣β1⎦⎡1⎤⎡ωλ1⎤⎢1+β⎥得到⎢⎥=⎢⎥⎣()1−ωλ2⎦⎢1⎥⎢⎥⎣1+β⎦11 ⎧1λ=⎪1()⎪1+βω⎨⎪1λ=2()()⎪⎩1+β1−ω⎧1P()b=[]ω−()1−ωβ⎪1⎪1−β⎨⎪()1[]()Pb=1−ω−ωβ2⎪⎩1−β()()()()SdijDS=∑∑PaiPbjdai,bjeij[]()1−ω−ωββ[]ω−()1−ωββ=dω⋅+d()1+ω⋅1−β()1+βω1−β()1+β(1−ω)Sddβde==Sd1+β1+eSdβR()S=+H()(ω−lb1+β)1+βSdD得到β=e=d−D1DS=lndd−DDDdR()D=ln+H()ω−lndd−Dd−D()⎡DD()⎤=Hω+lnD−lnd−D−lnd+lnd−D⎢⎥⎣dd⎦()⎧D⎛D⎞()⎡D⎛D⎞⎤⎫=Hω+⎨lnD−⎜1−⎟lnd−D−⎢+⎜1−⎟⎥lnd⎬⎩d⎝d⎠⎣d⎝d⎠⎦⎭()⎡DD⎛D⎞⎛D⎞⎤=Hω+⎢ln+⎜1−⎟ln⎜1−⎟⎥⎣dd⎝d⎠⎝d⎠⎦()⎛D⎞=Hω−H⎜⎟⎝d⎠D=0时，R()0=H()ωD=dω时，R()dω=012 ⎧()⎛D⎞⎪Hω−H⎜⎟0≤D≤dω所以R()D=⎨⎝d⎠⎪⎩0D>dωSdij（4）p()(bj|ai=pbj)λie()()0()pb|a=pbλe=pbλ11111111=[]ω−()1−ωβ⋅1−β()1+βω[]ω−()1−ωβ=()21−βω()()Sd()pb|a=pbλe=pbλβ12121211=[]ω−()1−ωβ⋅⋅β1−β()1+β()1−ω[]ω−()1−ωβ=⋅β()2()1−β1−ω()()Sd()pb|a=pbλe=pbλβ21212111=[]()1−ω−ωβ⋅⋅β1−β()1+βω[]()1−ω−ωβ=⋅β()21−βω()()0()pb|a=pbλe=pbλ22222211=[]()1−ω−ωβ⋅1−β()1+β(1−ω)[]()1−ω−ωβ=()2()1−β1−ωD（5）d=1时，β=1−D1β=1−D，=D1+β1+βp()a⋅p(b|a)()111()pa|b==λpa11()11pb111=⋅ω==1−D()1+βω()1+β13 p()a⋅p(b|a)()121()pa|b==λβpa12()11pb21β=⋅β⋅ω==D()1+βω()1+βp()a⋅p(b|a)()212()pa|b==λβpa21()22pb11β=⋅β⋅()1−ω==D()1+β()1−ω()1+βp()a⋅p(b|a)()222()pa|b==λpa22()22pb211=⋅()1−ω==1−D()1+β()1−ω()1+β14 第9章习题1.对(2,1),(3,1),(4,1),(5,1)，讨论其纠检错能力，对用完备译码、不完备译码以及不完备译码＋ARQ等方法译码，求译码错误概率。解：对(2,1)码，若d=1，能纠检错0个；若d=2,能检1个错，纠0个错对(3,1)码，若d=1，能纠检错0个；若d=2,能检1个错，纠0个错；若d=3，能检2个错，纠1个错对(4,1)码，若d=1，能纠检错0个；若d=2,能检1个错，纠0个错；若d=3，能检2个错，纠1个错，若d=4,能检3个错，纠1个错对(5,1)码，若d=1，能纠检错0个；若d=2,能检1个错，纠0个错；若d=3，能检2个错，纠1个错；若d=4,能检3个错，纠1个错；若d=5,能检4个错，纠2个错2.为什么d=2的(n,n–1)码能检测奇数个错误？解:d=2，能检1个错，又因为(n,n–1)码是奇偶校验码，即对于奇校验码：C⊕C⋅⋅⋅⊕C=0n−1n−20偶校验码：C⊕C⋅⋅⋅⊕C=1n−1n−20当出现一个错或者奇数个错时，在接收端奇校验码：C⊕C⋅⋅⋅⊕C=1n−1n−20偶校验码：C⊕C⋅⋅⋅⊕C=0n−1n−20都能检测到错误，故d=2的(n,n–1)码能检测奇数个错误。3.设C={11100,01001,10010,00111}是一个二元码，求码C的最小距离d。解：d(11100,01001)=3d(11100,10010)=3d(11100,00111)=4d(01001,10010)=4d(01001,00111)=3d(10010,00111)=3故码C的最小距离d=3218 4．设C={00000000,00001111,00110011,00111100}是一个二元码。（1）计算码C中所有码字之间的距离及最小距离；（2）在一个二元码中，如果把某一个码字中的0和1互换，即0换为1，1换为0，所得的字称为此码字的补。所有码字的补构成的集合称为此码的补码。求码C的补码以及补码中所有码字之间的距离和最小距离，它们与（1）中的结果有什么关系？（3）把（2）中的结果推广到一般的二元码。解：（1）d(00000000,00001111)=4d(00000000,00110011)=4d(00000000,00111100)=4d(00001111,00110011)=4d(00001111,00111100)=4d(00110011,00111100)=4故码C的最小距离d=4（2）码C的补码是{11111111,11110000,11001100,11000011}d(11111111,11110000)=4d(11111111,11001100)=4d(11111111,11000011)=4d(11110000,11001100)=4d(11110000,11000011)=4d(11001100,11000011)=4故C补码的最小距离d=4（3）推广到一般的二元码也有以上的结论设码C中任意两码字的距离为d,即两码字有d位不同，n-d位相同。变补后，仍有d位不同，n-d位相同，所以任意两码字的距离不变，最小距离当然不变。219 1.设p是一个素数，p（1）在GF(p)上把x−1分解成不可约因式的乘积；p−1（2）在GF(p)上把x−1分解成不可约因式的乘积。42.在GF(3)上把x−1分解成不可约多项式的乘积，确定所有码长是4的三元循环码，并写出每一个码的生成矩阵和校验矩阵。4解：因x–1=n3.设在GF(q)上x−1可分解成t个不同的不可约多项式的乘积，试问有多少个码长为n的q元循环码？4.设C是一个二元循环码，证明分量全为1的向量(11…1)∈C的充分必要条件是C包含一个重量为奇数的码字。证：用反证法75.在GF(2)上x−1能分解成不可约因式的乘积：7332x−1=−(xxxxx1)(++1)(++1)确定所有码长为7的循环码，并且准确描述这些码的特性。解：由题知n=7,k=6,4(1)当k=6时g(x)=x-1332(2)当k=4时g(x)=x+x+1或x+x+1可进一步写出G和H6.请对任意一个21-bit的数据，例如使用自己的学号化成2进制数，高位补“0”或某些随机数）（1）给出BCH(31,21)码的码多项式；（2）假设传输过程中错了一位（可以任意设定），请译码；（3）假设传输过程中错了两位（可以任意设定），请译码；（4）假设传输过程中错了三位（可以任意设定），请译码。解：（1）我们可以任选一个21-bit的数据，假设所选数据为020321，其二进制数表示为：00010000000110010000121位码261 查表可知（31，21）码的本原多项式为：17985g(x)=x+x+x+x+1输入多项式为：17985u(x)=x+x+x+x+1所以输出码多项式为：v(x)=u(x)g(x)179851098653=(x+x+x+x+1)(x+x+x+x+x+x+1)2726252322201917161412863=x+x+x+x+x+x+x+x+x+x+x+x+x+x+1(2)假设接收到的多项式为：27252322201917161412863r(x)=x+x+x+x+x+x+x+x+x+x+x+x+x+126则可得：σ（x）=αx+1即错误位置为26，可以纠正。(3)假设接收到的多项式为：2726232220191716141286r(x)=x+x+x+x+x+x+x+x+x+x+x+x+1253则可得：σ（x）=（αx+1）（αx+1）-25-3所以：β1=αβ2=α325即错误位置为x和x，可以纠正。(4)假设接收到的多项式为：2726251917161412863r(x)=x+x+x+x+x+x+x+x+x+x+x+1出现了3个错误，接收端能检出错误，但无法纠正。57.已知GF(2)中元素的几种表示如表11.8所示，有关元素的最小多项式如下：5243φ1(x)=x+x+1,φ3(x)=φ1(x)+x+x,343φ5(x)=φ3(x)+x+x,φ7(x)=φ5(x)+x+x,424φ11(x)=φ7(x)+x+x,φ15(x)=φ11(x)+x+x。现欲对上题信源编码输出进行扩展的BCH(32,16)信道编码再传送。（1）对于消息(1000111111101010)给出信道编码的输出码字；（2）若接收矢量为(10001111111010100110100100111101)，试判断是否有错，如只有一个错请纠正之，如有两个或三个错请说明纠正的方法。552表11.8GF(2)域元素的两种表示（本原多项式p(x)=x+x+1）81624100001α01101α11011α1111091725α00010α11010α10011α11001262 2101826α00100α10001α00011α101113111927α01000α00111α00110α010114122028α10000α01110α01100α101105132129α00101α11100α11000α010016142230α01010α11101α10101α100107152331α10100α11111α01111α000015解：由题知：m=5，n=2-1=31扩展的BCH(31+L,K)码，则L=1(即加了1为奇偶校验位)，K=1652（1）若可以纠1个错，则g(x)=p(x)=x+x+1则编码输出为：u(x)g(x)=（2）1085428.令g()xxxxxxx=++++++1是(15,5)循环码的生成多项式，（1）求出该码的校验多项式；（2）写出该码的系统码形式的G和H矩阵；（3）构造k级编码器。解：由题可得：108542x=g(x)+x+x+x+x+x+11196532x=xg(x)+x+x+x+x+x+x1221076432x=xg(x)+x+x+x+x+x+x287653=(x+1)g(x)+x+x+x+x+x+x+1133987642x=(x+x)g(x)+x+x+x+x+x+x+x144210987532x=(x+x)g(x)+x+x+x+x+x+x+x429743=(x+x+1)g(x)+x+x+x+x+x+1所以可得：8542bo(x)=x+x+x+x+x+196532b1(x)=x+x+x+x+x+x263 87653b2(x)=x+x+x+x+x+x+1987642b3(x)=x+x+x+x+x+x+x9743b4(x)=x+x+x+x+x+1进而有：⎡100000100110111⎤⎢⎥010001001101110⎢⎥G=⎢001000111101011⎥⎢⎥⎢000101111010110⎥⎢⎣000011010011011⎥⎦⎡010111000000000⎤⎢⎥101100100000000⎢⎥⎢001110010000000⎥⎢⎥⎢011100001000000⎥⎢111000000100000⎥⎢⎥H=⎢100110000010000⎥⎢011010000001000⎥⎢⎥⎢110100000000100⎥⎢⎥111110000000010⎢⎥⎢101010000000001⎥⎢⎥⎣⎦K级编码器为如下图：g1g2gnk−−1DD?Dnk−−101nk−xux()264 539.求GF(2)上以α,α为根的二进制循环码：（1）写出生成多项式g(x)，确定码长n和信息位个数k；（2）写出该码系统码形式的G和H矩阵；（3）求出该码的R和最小距离。52解：（1）查表可得本原多项式为：p(x)=x+x+1又g(x)=LCM{Φ1(x),Φ3(x)}--3当β1=αβ2=α用matlab函数gfminpol(1，5)和gfminpol(3，5)分别得：53Φ1(x)=x+x+1532Φ3(x)=x+x+x+x+110752所以g(x)=Φ1(x)Φ3(x)=x+x+x+x+x+15所以n=2-1=31，k=31-10=21（2）同样由上题的方法可求出系统码形式的G和H矩阵10752x=g(x)+x+x+x+x+1118632x=xg(x)+x+x+x+x+x……….31X=………可进一步写出bo(x)……b21(x)，从而写出G，HG=H=（3）n10.令n是g(x)|(x–1)|的最小正数。现用该g(x)生成位n的循环码，证明码的最小距离至少为3。1085411.构造(15,5,7)码的译码器，它的生成多项式g(x)=x+x+x+x+2x+x+1，该码能纠正3个错误。设用简单的捕错译码器译码。（1）证明所有2个错误能被捕获；（2）能捕获所有3个错误的图样吗？若不能，则有多少种3个错误图样不能被捕获；（3）作出该码的简单捕获译码器。m≥,3t<2m−12m+112.对，存在有一个长为纠t个错误的二进制本原BCH码吗？若有找出它的g(x)。265 习题1.试画出k=3，效率为1/3，生成多项式如下所示的编码状态图、树状图和网格图：2g1(X)=X+Xg2(X)=1+X2g3(X)=1+X+X22解：g1(D)=D+D，g2(D)=1+D，g3(D)=1+D+D所以可得状态图如下：其中（s0:00，s1:01，s2:10，s3:11）0/000s0010/10/010s2s31/100111/1101000//11s1树状图如下：299 001100010………01111111010111010000111………网格图为：0000111111111111001111111111010100001010002.假定寻找从伦敦到维也纳坐船或坐火车的最快路径，图12.25给出了各种安排，各条分支上标注的是所需时间。采用维特比算法，找到从伦敦到维也纳的最快路线，解释如何应用该算法，需做哪些计算，以及该算法要求在存储器里保存什么信息。300 伦敦阿姆斯特丹慕尼黑维也纳10988107138巴黎贝塞尔图12.25解：从伦敦到维也纳的最快路线为：伦敦——巴黎——慕尼黑——维也纳此算法需计算从伦敦到维也纳中间所可能经过的各节点离伦敦的时间，保留其中最短的，去除其它的。需要记录下各中间节点离伦敦的最短时间，其算法的实现就是Dijkstra算法。3.考虑图12.26中的卷积码。（a）写出编码器的连接矢量和连接多项式。（b）画出状态图、树状图和网格图。输入输出图12.26(1)(2)解：（1）由图可知：连接矢量为：g=[1,0,1]g=[0,1,1](1)2(2)2连接多项式为：g（D）=1+Dg（D）=D+D（２）状态图为：其中（s0:00，s1:01，s2:10，s3:11）301 0/00s0011/s1/11ss1/0021/010/11330/100/01s1树状图为：001110………010101111000………302 网格图为：11010100001101010111111110104.下列码率为1/2的编码中哪些会引起灾难性错误传播？23（a）g1(X)=X，g2(X)=1+X+X23（b）g1(X)=1+X，g2(X)=1+X234（c）g1(X)=1+X+X，g2(X)=1+X+X+X3424（d）g1(X)=1+X+X+X，g2(X)=1+X+X461034（e）g1(X)=1+X+X+X，g2(X)=1+X+X3424（f）g1(X)=1+X+X，g2(X)=1+X+X+X解：会引起灾难性错误传播的有：（ｂ）有公因子（１＋ｘ）２（ｃ）有公因子（１＋ｘ＋ｘ）２（ｄ）有公因子（１＋ｘ＋ｘ）故此三个会引起会引起灾难性错误传播。5.不查表，使用功能强大的PC机，设计一个(2,1,2)卷积码。(1,1)(1,2)6.已知(2,1,3)码的子生成元g=(1101),g=(1110)。（1）求出该码的G(D)和H(D)矩阵，以及G∞和H∞矩阵；（2）画出该码的编码器；（3）求出相应于信息序列M=(11001)的码序列；303 （4）此码是否是系统码？(1,1)３(1,2)２解：（１）因g（Ｄ）=１＋Ｄ＋Ｄg（Ｄ）＝１＋Ｄ＋Ｄ３２所以Ｇ（Ｄ）＝［１＋Ｄ＋Ｄ，１＋Ｄ＋Ｄ］Ｈ（Ｄ）＝（２）编码器如图：（１）（３）ｖ＝（１１００１）＊（１１０１）＝１０１１０１０１（２）ｖ＝（１１００１）＊（１１１０）＝１００１１１１０交织得：ｖ＝（１１，００，１０，１１，０１，１１，０１，１０）可知该码为非系统码。7.在图12.16所示的Turbo编码器中采用了两个RSC编码器。（a）对此编码器进行扩展，使之包含有M个交织器。（b）画出Turbo译码器的原理方框图，要求译码器采用由扩展生成的M组奇偶校验比特。(1,3)23(2,3)8.设有一个(3,2,3)系统码的子生成元分别为：g(D)=1+D+D,g(D)3=1+D+D，问（1）此码是恶性码吗？为什么？（2）画出该码的编码器和对偶码的编码器；（3）画出有4个分支长的树图；（4）求出此码的最小距离dm；（5）求出此码的自由距离。(1,3)23(2,3)3解：因g(D)=1+D+D和g(D)=1+D+D(1,1)(1,2)2(1,3)9.已知有一个(3,1,2)码的子生成元是：g=1+D,g=1+D和g=12+D+D。（1）求出该码的G(D)和H(D)；304 （2）画出该码的编码电路；–1（3）该码是否是恶性码？找出有最小延迟前馈的逆矩阵G(D)。２２解：（１）G(D)＝［１＋Ｄ，１＋Ｄ，１＋Ｄ＋Ｄ］Ｈ（Ｄ）＝（２）该编码电路为：（３）10.Turbo译码需要依靠外部信息的反馈。在Turbo译码器中采用的基本原则是避免反馈某一个译码段自身生成的译码段信息。试从概念上解释这个原则的正确性。11.设码率为1/2的Turbo码的生成矩阵分别为4状态编码器：⎡1+D+D2⎤g(D)=⎢,1⎥2⎢⎣1+D⎥⎦8状态编码器：⎡1+D+D2+D3⎤g(D)=⎢,1⎥23⎢⎣1+D+D+D⎥⎦16状态编码器：⎡1+D4⎤g(D)=⎢,1⎥234⎢⎣1+D+D+D+D⎥⎦（a）试画出这些RSC编码器的方框图。（b）求出每个编码器对应的奇偶校等式。解：RSC编码器的方框图如下：305 （1）（2）（3）消息比特m系统比特m++校验比特z306 1.若已知DES体制中8个S盒之一的S盒选择压缩函数如下：列号0123456789101112131415行号0144131215118310612590710157414213110612119538241148136211151297310503512824917511214100613假设输入S盒的输入矢量为M=(M0M1…M5)。试求通过选择压缩函数S变换后的输出矢量。解：M通过S盒时，代换表将选出一个相应的输出矢量。可以将矢量中的首尾两项M0M5看作是控制盒S中采用的不同行号，而将其余的四项看作是不同列号的一种。这样每个M就有唯一的Y相对应。如输入M＝（101100）则输出Y为第2行，第6列，结果为2即00102.试用公开密钥（e,n）=（5,51）将报文ABE，DEAD用A=01,B=02,…，进行加密。e解：用加密方程C=(M模n,)将ABE，DEAD分别代入可得结果为1，32，14，4，14，1，43.试用秘密密钥（d,n）=（13,51）将报文4,1,5,1解密。e解：用解密方程M=(C模n,)将4,1,5,1分别代入可得结果为4，1，20，14.试用公开密钥（e,n）=（3,55）将报文BIDHIGH用A=01,B=02,…，进行加密。e解：用加密方程C=(M模n,)将BIGHIGH分别代入可得结果为8，14，9，17，14，13，175.用秘密密钥（d,n）=（5,51）将报文4,20,1,5,20,5,4解密。e解：用解密方程M=(C模n,)将4,20，1，5，20，5，4分别代入可得结果为4，5，1，4，5，14，46.一个英文加密系统使用10个随机字母组成的密钥序列，计算其惟一性距离。（1）每个密钥字符可以是26个字母中的任意一个，字母可以重复。（2）密钥符号不能重复。如果密钥序列由0~999整数中的10个随机整数组成，重新计算惟一性距离。10解：（1）密钥熵为H（K）=log(26)=47bit2英语的绝对码率：r’=log226=4.7比特/字符英语实际码率：r=1.5比特/字符冗余：D=r’–r=3.2比特/字符单一性距离：N=H(K)/D=47/3.2≈15字符（2）密钥符号不能重复时 ⎛10⎞密钥熵为H（K）=log⎜⎟=44.13bit2⎜⎟⎝26⎠单一性距离：N=H(K)/D=44.13/3.2≈14字符10（3）密钥熵为H（K）=log(1000)=99.66bit2单一性距离：N=H(K)/D=99.66/3.2≈32字符7.使用RSA加密消息M=3,质数p=5,q=7。解密密钥d选为11，计算加密密钥e的值。解：φ(n)=4×6=24解同余方程ed=1(模φ(n))可得11×11=121=1（模24）；所以e=118.考虑以下RSA算法：(a)如果质数是p=7,q=11，试举出5个允许的解密密钥d。(b)如果质数是p=13,q=31，解密密钥d=37，试求加密密钥e，并加密单词“DIGITAL”。解：(a)11×11模60=1，19×19模60=1，29×29模60=1，31×31模60=1，49×49模60=1，得5个允许的d为11，18，29，31，49(b)37×251模360=1，所以e为251e用加密方程C=(M模n,)将DIGTAL分别代入可得结果为9.下面一段密文本来是连续的字符串，只是为了便于阅读将它分成每5个字符一组。明文是一般计算机教科书中的一段话，因此也许会有“COMPUTER”这个单词出现。加密采用的是Polybius方阵密码系统（参见14.1.3节）。明文中无安全可靠信道，无标点符号，试对此密文进行破译。AAUANCVIRERURNNDLTMEAEEPBYTUSTICEATNPMEYIICGOGORCHSRSOCNNTIIIMIHAOOFPAGSIVTTPSITLBOLROTOEX10.英文字母的替代密码的一般形式为C=αM+β(模26)其中这M为明文的字母，C为密文的字母，α为与26互素的整数，β为0~25中的任意一个整数。试分析（1）α=1，称为加法密码和（2）β=0，称为乘法密码的特点及存在的问题。'