信息论与编码习题解答(待校200812).doc 55页

'（有问题请更正并通知xiezg@ntu.edu.cn）第二章信息的度量1．一珍珠养殖场收获240颗外观及重量完全相同的特大珍珠，但不幸被人用外观相同但重量仅有微小差异的假珠换掉1颗。（1）一人随手取出3颗，经测量恰好找出了假珠，问这一事件大约给出了多少比特的信息量；（2）不巧假珠又滑落进去，那人找了许久却未找到，但另一人说他用天平最多6次能找出，结果确是如此，问后一事件给出多少信息量；（3）对上述结果作出解释。解：（1）从240颗珠子中取3颗，含1颗假珠的概率为（2）240颗中含1颗假珠，用天平等分法最多6次即可找到假珠，是必然事件，因此信息量为0。（3）按照shannon对信息量的定义，只有事件含有不确知成分，才有信息量，且不确知成分越大，信息量越大，必然事件则没有信息量。但从广义信息论来说，如果那人不知用天平二分法找假珠，另一人告之此事，使他由不知到知，也应该含有一定的信息量。2．每帧电视图像可以认为是由3´105个象素组成，所有象素均独立变化，且每一象素又取128个不同的亮度电平，并设亮度电平等概率出现。问每帧图像含有多少信息量？如果一个广播员在约10000个汉字的字汇中选取1000个字来口述此电视图像，试问广播员描述此图像所广播的信息量是多少（假设汉字字汇是等概率分布，且彼此独立）？若要恰当地描述此图像，广播员在口述中至少需用多少汉字？解：设电视图像每个像素取128个不同的亮度电平，并设电平等概率出现，则每个像素亮度含有的信息量为比特/像素一帧中像素均是独立变化的，则每帧图像信源就是离散亮度信源的无记忆N次扩展信源。得每帧会图像含有的信息量为比特/每帧广播口述时，广播员是从10000个汉字字汇中选取的，假设汉字字汇是等概率分布的，则汉字字汇中每个汉字含有的信息量比特/字广播员口述电视图像是从此汉字字汇信源中独立地选取1000个字来描述的。所以，广播员描述此帧图像所广播的信息量为 比特/千字若广播员仍从此汉字字汇信源Y中独立地选取汉字来描述电视图像，每次口述一个汉字含有信息量是H(Y)，每帧电视图像含有的信息量是，则广播员口述此图像至少需要的汉字数等于字3．已知X：1,0P(X)：p,1–p(1)求证：H(X)=H(p)(2)求H(p)并作其曲线，解释其含义。（1）证明（2）H(p)10.510p该H(p)曲线说明，当0与1等概出现时，即p=0.5时，熵最大。当p由0.5分别趋向于0和1时，熵逐渐减小至0。4．证明H(X3|X1X2)£H(X2|X1)，并说明等式成立的条件。证明：设离散平稳信源输出的随机符号序列为…X1,X2,X3,…。又设,,,而且都取自于同一符号集，并满足有 在区域[0，1]内设f(x)=－xlogx,f(x)在[0，1]内是型凸函数，所以满足詹森不等式其中现今,设其概率空间为，并满足所以根据詹森不等式得所以上式对所有的取值都成立，所以因为，所以上式两边相乘，等号不变。有上式对所有都成立，所以对所有求和下式也成立 因为H(X3|X1X2)£H(X3|X2)所以是平稳信源H(X3|X2)=H(X2|X1)得H(X3|X1X2)£H(X2|X1)只有当(对所有)时等式成立。5．设有一概率空间，其概率分布为{p1,p2,…,pq}，且p1>p2。若取，，其中0<2e£p1–p2，而其它概率值不变。证明由此得到的新的概率空间的熵是增加的，并用熵的物理意义加以解释。证明：令得因为f(x)=－xlogx是型函数，根据型凸函数的定义有所以即同理得以上两不等式两边相加，不等号不变。所以得6．某办公室和其上级机关的自动传真机均兼有电话功能。根据多年来对双方相互通信次数的统计，该办公室给上级机关发传真和打电话占的比例约为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.708H(X)=－P(X1)lbP(X1)－P(X2)lbP(X2)=0.8814bit/符号H(Y)=－P(Y1)lbP(Y1)－P(Y2)lbP(Y2)=0.8713bit/符号H(XY)==1.0239bit/两个信符I(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，这时带来多少附加信息量？图2.6解：信源P(M1)=P(M2)=P(M3)=P(M4)=1/4,信道为二元对称无记忆信道，消息Mi与码字一一对应，所以设设接收序列为Y=(y1y2)接收到第一个数字为0，即y1=0。那么，接收到第一个数字0与M1之间的互信息为因为信道为无记忆信道，所以同理，得输出第一个符号是y1=0时，有可能是四个消息中任意一个第一个数字传送来的。 所以故得接收到第二个数字也是0时，得到关于M1的附加互信息为其中同理，因为信道是无记忆信道，所以得输出端出现第一个符号和第二个符号都为0的概率为所以比特得附加互信息为比特8．证明若随机变量X，Y，Z构成马氏链，即X→Y→Z，则有Z→Y→X。证明：因为(X,Y,Z)是马氏链，有P(z|xy)=P(z|y),对所有成立，而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)对所有成立 故得P(x|yz)=P(x|y)对所有成立所以(Z,Y,X)也是马氏链。第三章离散信源1.由于，即可以看做是先发出一个符号，再在此基础上发出一个与前一符号相关的符号，而,第二个符号可以看做为具有一阶马尔可夫性，故有。2.由转移到可以认为遍历了每个，故，即有成立。3.香农图略由题转移概率为，由马尔可夫趋于稳定时频率分布不变，故得，即又由代入解得，，又，，，故H=1/2*lb3/2+1/4*lb34香农图略 由题，由得，故H1=lb3,对二阶马尔可夫链有状态为00，01，02，10，11，12，20，21，22，且P（0|00）=P（1|00）=P（2|00）=P（0|01）=P（1|01）=P（2|01）=P（0|02）=P（1|02）=P（2|02）=1/3,由,H2=9*1/9*1/3*lb3=2/3*lb35由于，由图知，由得，，即。（2）对p求导得，令，得，得6记，，则由条件（1）得，由条件（2）得，故，代入上边两式整理有，进行递推有，7由于，当信源为无记忆信源时，，故得 信道为无记忆时，，故得当信源信道都无记忆时有，故有当信源信道中有一个有记忆或两个都有记忆时，信号之间或信道对信号存在干扰，故信宿对信源的不确定性增加了，由于熵是对信源不确定性的平均减少量，是信宿获得的关于信源的平均信息量，由于不确定性的增加使获得的信息量减少，故有，当为无记忆时，传输的信息量能达到理想状态。故有。第四章离散信源的信源编码1.简述信源译码的错误扩展现象。答：由于信道的干扰作用，造成了一定量的错误，这些错误在译码时又造成了更多的错误，这就是通信译码的错误扩展现象。2.针对某种应用，给出一种你认为是有价值的减小信源译码错误扩展的方法。答：在信源编码的每个码字施加和码字等长的附加位，编码时将要写入的信息在新码字上顺序写两边，译码时先译前半段，若码长无误则译后半段，若前后不一致则要求重发，在带宽充足的条件下可以采用这种方法。3.试说明已有的解决信源译码错误扩展问题的方法，简述其基本思路及利弊。答：信道编码的方法优点：加入了纠错码，减少了译码错误的可能性，减少了发生错误扩展的概率。]缺点：需要对发送的码字加入冗余，是一种降低效率来换取可靠性的方法。4.某通信系统使用文字字符共10000个，据长期统计，使用频率占80%的共有500个，占90%的有1000个，占99%的有4000个，占99.9%的7000个。（1）求该系统使用的文字字符的熵；（2）请给出该系统一种信源编码方法并作简要评价。解： (1)(2)可以使用huffman编码的方法，为使压缩效果理想，可以使用扩展信源的方法。1.一通信系统传送的符号只有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下面对每个字可能出现的情况加以讨论。3个符号都为a则编6bit码，共1种3个符号都为b则编5bit码，共1种3个符号都为c则编3bit码，共1种3个符号有2个a，1个b则编6bit码，共3种3个符号有2个a，1个c则编5bit码，共3种3个符号有2个b，1个a则编6bit码，共3种3个符号有2个b，1个c则编5bit码，共3种3个符号有2个c，1个a则编4bit码，共3种3个符号有2个c，1个b则编4bit码，共3种3个符号有1个a，1个b,1个c则编5bit码，共6种平均码长为＝4.488bit/字h1=R1/C=4.455/4.488=99.26%2.设有一个无记忆信源发出符号A和B，已知p(A)=1/4,p(B)=3/4。（1）计算该信源熵；（2）设该信源改为发出二重符号序列消息的信源，采用费诺编码方法，求其平均信息传输速率；（3）又设该信源改为发三重序列消息的信源，采用霍夫曼编码方法，求其平均信息传输速率。解：（1）该离散无记忆信源的熵为（2）费诺编码消息符号序号(i)消息概率pi第一次分解第二次分解第三次分解二进制代码组码组长度biBB9/16(9/16)001AB3/16(7/16)1(3/16)0102BA3/16(3/16)01103 (4/16)1AA1/16(1/16)11113编码的平均长度为码元/符号平均传输速率为（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/641编码的平均长度为码元/符号平均传输速率为1.已知一个信源包含8个符号消息，它们的概率分布如下表：ABCDEFGH0.10.180.40.050.060.10.070.04（1）信源每秒钟内发出一个符号，求该信源的熵及信息传输速率；（2）对这8个符号作二进制码元的霍夫曼编码，写出各个代码组，并求出编码效率。解：（1）该信源的熵信息传输速率R=2.55bit/s（2）霍夫曼编码C0.40B0.1801.0A0.100.230F0.1010.3710.611G0.0700.13E0.0610.191D0.0500.091H0.041 编码结果：CBAFGEDH0110100111010101011111011111平均码长为：所以编码效率为8.设信道基本符号集合A={a1,a2,a3,a4,a5}，它们的时间长度分别为t1=1,t2=2,t3=3,t4=4,t5=5（各码元时间）用这样的信道基本符号编成消息序列，且不能出现这四种符号相连的情况。（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）这是一个有固定约束的不均匀编码的信道，有约束条件（即不能出现），可以把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,b22(a5)=5,写出行列式，可得特征方程为解方程可得所以bit/码元时间（1）因为规定a1a2不能连用，故不能用和做码字，根据最佳编码的两个原则，及单译可译定理，出现概率大的消息用短码的原则，可用x1x2x3x4x5x6x71/21/41/81/161/321/641/64a3a4a1a3a5a1a4a2a3a2a43445556（3）编码效率为h=R/C=0.541/0.675=80%第五章离散信道的信道编码5．1 比特/符号比特命题得证。5．2比特/符号比特/符号比特/符号R=0.049*1000=49比特5．3比特/符号比特/符号比特/符号比特/符号5．4比特/符号5．5（1）由图可知这是个对称信道，当输入符号等概时，,,1/81/800P(xy)=01/81/80001/81/81/8001/8对任意x均成立所以，C=1比特/符号。（2）由图可知，信道亦为对称信道，P(xy)=P(x)P(y|x)=1/61/61/121/12 1/121/121/61/6=0.0817比特/符号（3）同上，信道为对称离散信道，P(xy)=1/61/91/181/181/61/91/91/181/6比特/符号。6.设据对称性由，代入所以奈特/符号。7该信道可看成4个BSC信道串联而成，1-1-==1-4(1-)[1-2(1-)]4(1-)[1-2(1-)]4(1-)[1-2(1-)]1-4(1-)[1-2(1-)]级联后的信道仍是对称信道，可代入公式：其中--〉4(1-)[1-2(1-)]1---〉1-4(1-)[1-2(1-)]则4(1-)[1-2(1-)]log{4(1-)[1-2(1-)]}+1-4(1-)[1-2(1-)]log{4(1-)[1-2(1-)]}代入=，得C’=0.9949所以信道容量C’=C*1024=1018.8kbps。8由图可知信道为对称信道，且信源的符号消息等概分布，因此 比特/符号。9后验概率1/41/61/12P(xy)=1/241/81/121/121/241/8由P(y)=[3/81/37/24]所以2/31/22/7P(x|y)=1/93/82/72/91/83/7根据最小错误概率准则，应作如下译码：错误概率为10（1）（2）（3）5．11？？5．12（1）对信源四个消息进行编码，选择码长n=4，这组码为C:{()}i=(1,2)编码后的信息传输率比特/符号（2）设接收序列根据信道的传输特性，输入序列共有16个，正好分成4个互不相交的子集，每个码字只传输到其中对应的一个子集：(001/21/2)à(00)(011/21/2)à(01) (101/21/2)à(10)(111/21/2)à(11)所以根据选择的译码规则=(1/21/2)正好将接收序列译成所发送的码字，可计算每个码字引起的错误概率所以有。13(1)P(y)=[7/125/12]P(x|y)=6/73/51/72/5又比特/符号所以比特/符号此信道为二元对称信道，所以信道容量比特/符号根据二元对称信道的性质可知，输入符号为等概分布，即P(0)=P(1)=1/2时信道的信息传输率才能达到这个信道的容量值。（1）由P(y)=[1/21/4+1/4a1/4-1/4a]所以（2） (3)第六章连续信源和连续信道第六章6.1(1)收到传真的概率为8/(4+8+3+1)*2/(7+1+2)=1/10I=-log1/10=3.3比特（2）可采取压缩编码，安最佳编码原则编码等措施（3）编码时码长尽可能长，这样根据香浓第二定理，总存在一种编码，只要码长足够长，总存在一种编码，是错误概率任意小。最好结合实际分析如何克服随机，突发干扰。（4）C=Blog(1+S/N)=2.048log(1+)=8.34Mbps，不失真条件下，该信道允许最大信息传输速率为8.34Mbps。6.2（1）比特/样值（2）对样值进行256级量化，当其服从均匀分布时，信源有最大熵，H=log256=8比特/符号（3）所以。（4）S/N=36dB,C=5.17Mbps所以。6.3(1)比特/样值（2）冗余度=（3）其中C=9.6KB=1.2288*2Mbps,得S/N=-25.7dB(4)=2.45766.4由于P(x)=1/2=,所以电压为1V~(-1)V上的均匀分布，又,所以10=2，=5=2*（1/2）lb(4Ps)=lb(4*1)=2=10bit/s 6.5又,所以10=2，=5所以6.66.7所以B=.6.8(1)(2)又而，所以S/N=,所以=9.97BB=66.9所以所以P=.6.10=所以（2） 利用关系式，所以式（2）变为，为一常量。6.11=再由逐步分布积分得H(X)=-2AlnA-2Aln2+2A.因为，所以2A=1A=1/2所以H(X)=1奈特/自由度6.12（1）=b=-logbp(x)dx-2b=因为p(x)dx=1，所以b=。故H(X)=2/3loge+loga-log3(2)若Y=X+A，则,所以H(Y)=2/3loge+loga-log3(3)若Y=2X，则，所以H(Y)=H(X)-log1/2=2/3loge+loga-log3/2。6.136.14(1)(2)所以B=(3)所以S/N=120 第七章网络信息理论简介（略）第八章信息率失真理论及其应用1.设输入符号表与输出符号表为X=Y={0,1,2,3}，且输入信号的分布为p(X=i)=1/4,i=0,1,2,3设失真矩阵为求和及。2.设无记忆信源，接收符号AY={1/2,1/2}，失真矩阵。试求：Dmax和Dmin及达到Dmax和Dmin时的转移概率矩阵。 ,在时，由于，所以在时，由于，所以2.三元信源的概率分别为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)。，由定义知：，平均失真度一定与试验信道的平均错误概率Pe有关，即根据保真度准则，应有Pe£D根据Fano不等式H(X/Y)£H(Pe)+Pelog(r–1)3.设有一连续信源，其均值为0，方差为，熵为H(X) ，定义失真函数为“平方误差”失真，即。证明其率失真函数满足下列关系式：当输入信源为高斯分布时等号成立。证明：（1）证明上界：连续信源R(D)函数是在约束条件下，求平均互信息：引入参量S和待定函数。在失真不超过D时，为下确界的试验信道满足由泛函分析中的变分法求的条件极值令由于以上规定了下确界，则（1）设集合则有（2）令其中由（1）得 即当时，且，得由（2）（3）两式，有（4）由对数得换底公式，有（5）若要（1）式等号成立，则等效于（5）式等号成立。令则然后再求二阶导数，得由于是得概率密度函数且所以，即（5）式右边为上凸函数，在的S上确极大值，有代入得（6）由式（5）得 即（1）证明上界设信道的传递函数的概率为：它是已知时y的概率分布，即均值为，方差为的高斯分布，其中。设，由于所以输出信号，于是时均值为零，方差为的随即变量。当方差受限时，高斯随即变量的差熵最大，有 当且仅当是高斯分布时，上式等号成立。综上所述，2.随机变量X服从对称指数分布，失真函数为d(x,y)=|x–y|，求信源的R(D)。，令，得且得对进行傅立叶变换 由，得且当时2.设有平稳高斯信源X(t)，其功率谱为，失真度量取，容许的样值失真为D。试求：（1）信息率失真函数R(D)；（2）用一独立加性高斯信道（带宽为，限功率为P，噪声的双边功率谱密度为）来传送上述信源时，最小可能方差与的关系。（1）对于时间连续的平稳高斯信源，当功率谱密度已知时，在本题中即 （2）信道容量为bit/s由定理可知，当时，可以采用最佳编码，其硬气的错误小于等于D。取,求得最小均方误差D。令，得时，时，时，由于所以如下图： 7.某工厂的产品合格率为99%，废品率为1%。若将一个合格产品作为废品处理，将损失1元；若将一个废品当作合格产品出厂，将损失100元；若将合格品出厂，废品报废，不造成损失。试分析质量管理中各种情况造成的损失及付出的代价。解　根据题意有信源空间：好（合格）废（废品）P(好)=0.99P(废)=0.01选择失真函数为d(好，好)=0d(废，废)=0d(好，废)=10d(废，好)=100失真矩阵为可将产品检验分成如下4种情况：全部产品都当合格品，全部产品都当废品，完美的检验和允许出错的检验。下面分别进行讨论。情况1　全部产品不经检验而出厂——都当合格品。把这一过程看作是一个“信道”，其“传递概率”为P(好/好)=1P(废/好)=0P(好/废)=1P(废/废)=0信道矩阵为这种情况的平均损失，即平均失真度，为　　　=P(好)×P(好/好)×d(好,好)+P(好)×P(废/好)×d(好,废)+P(废)×P(好/废话)×d(废,好)+P(废)×P(废/废)×d(废,废)=0.01´1´100=1元/个情况2　全部产品不经检验全部报废——都当废品这时的信道传输概率为P(好/好)=0P(废/好)=1P(好/废)=0P(废/废)=1信道矩阵为 平均失真度为　=P(好)×P(好/好)×d(好,好)+P(好)×P(废/好)×d(好,废)+P(废)×P(好/废)×d(废,好)+P(废)×P(废/废)×d(废,废)=0.99´1´1=0.99元/个全部报废造成损失小于全部出厂造成的损失。情况3　经过检验能正确无误地判断合格品和废品——完美的检验这相当于无噪信道的情况，信道矩阵为平均失真度为即这种情况不会另外造成损失。情况4检测时允许有一定的错误——非完美的检验设检验的正确率为p，则信道的传输概率为P(好/好)=pP(废/好)=1-pP(好/废)=1-pP(废/废)=p信道矩阵为平均失真度为　　　=P(好)×P(废/好)×d(好,废)+P(废)×P(好/废)×d(废,好)=0.99´(1-p)´1+0.01´p´100=1.99(1-p)元/个7.设输入符号表为X={0,1}，输出符号表为Y={0,1}。定义失真函数为：d(0,0)=d(1,1)=0d(0,1)=d(1,0)=1试求失真矩阵[D]。 7.某二元信源X的信源空间为其中w<1/2，其失真矩阵为（1）试求和；（2）试求及；（3）试求；（4）写出取得的试验信道的各传递概率；（5）当d=1时，写出与试验信道相对应的反向试验信道的信道矩阵。解：（1）（因为）（2）（1）由于令，则得到 得到D=0时，D=d时，所以 （4）（5）d=1时，， 第九章差错控制的基本概念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)码是奇偶校验码，即对于奇校验码：偶校验码：当出现一个错或者奇数个错时，在接收端奇校验码：偶校验码：都能检测到错误，故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=34．设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位相同，所以任意两码字的距离不变，最小距离当然不变。第十章线性分组码1.已知11次本原多项式p(x)=x11+x2+1，试求GF(211)中元素b=a89及b2,b3,b4,b5的最小多项式。解：的共轭元为： 1.求码长为n的q元重复码的生成矩阵。若n=2,q=2，则有22＝4个码字生成矩阵对于码长为n的q元重复码，生成矩阵是维单位矩阵。2.一个二元(11,24,5)码是线性码吗？为什么？是线性码。13>113.证明对于一个二元线性码L一定满足下列条件之一：（1）码L中所有码字具有偶数重量；（2）码L中一半的码字具有偶数重量，另一半的码字具有奇数重量。证明：（反证法）奇——奇数重量，偶——偶数重量；由题意假设线性码有个码字，其中个是偶数重量，个是奇数重量。且若1）偶数个数大于奇数个数，则； 若2）偶数个数小于奇数个数，则。情况1）成立，则第个偶数重量的码字与奇数重量的码字相加时，结果应是第个奇数重量的码字。这与情况1）相矛盾。同理，可以推出情况2）时的矛盾。由此可得，原假设不成立。原命题得证。5.设二元线性码L的生成矩阵为，求码L的最小距离。因为所以。6.设3元线性码L的生成矩阵为，求码长L的最小距离并且证明L是完备的。题中由生成矩阵知，该线性码是码，陪集首的个数为，能纠正3个错误。而1bit错误图样的个数为，又3<4，所以线性码是完备的。7.设二元线性码L的生成矩阵为，建立码L的标准阵并且对字11111和10000分别进行译码。 共个码字。标准阵为译码得5.设5元线性码L的生成矩阵为。（1）确定码L的标准型生成矩阵；（2）确定码L的标准型校验矩阵；（3）求码L的最小距离。 9.设有码如下所示：信息　　　　　码字0000000010110110101111111010（1）找出生成矩阵G与监督矩阵H；（2）在二元对称信道下给出最大似然译码的译码表；（3）求正确译码的概率。（1）设信息位，码字由编码规则 （2）译码表（3）正确译码的概率为：9.建立二元汉明码Ham(7,4)的包含陪集首和伴随式的伴随表，并对收到的字0000011，1111111，1100110，1010101进行译码。（1） （2）译码译码得到结果11.设一个[7,4]码的生成矩阵为（1）求出该码的全部码矢；（2）求出该码的一致校验矩阵；（3）作出该码的标准译码码表。（1） （2）（3） 12.设一个二进制(n,k)码C的G矩阵不含全零列，将C的所有码字排成的阵，证明：（1）阵中不含有全零列；（2）阵中的每一列由个零和个1组成；（3）在一特定分量上为0的所有码字构成C的一个子空间，问该子空间的维数是多少？（1）码共有个码字1．包括全零矢量；2．任意两个码字的和也是码字；假设组成的阵包含一个全零列，则每个码字重复两次，实际只有个不同的码字，与该码的定义相矛盾。所以阵中不含全零列。（2）等效于证每一列中0和1的个数相等。如（3，3）码由于任意两个码字的和也是码字，所以码字中奇数和偶数的数目相等。又由习题10.4(2)，线性码中一半码字具有偶数重量，另一半码字具有奇数重量，于是每一列中0和1的个数相等。所以，阵中的每一列由个零和个1组成的命题成立。13.一个(8,4)系统码，它的一致校验方程为： 式中是信息位，是校验位。找出该码的G和H，并证明该码的最小距离为4。第十一章循环码1.设p是一个素数，（1）在GF(p)上把分解成不可约因式的乘积； （1）在GF(p)上把分解成不可约因式的乘积。2.在GF(3)上把分解成不可约多项式的乘积，确定所有码长是4的三元循环码，并写出每一个码的生成矩阵和校验矩阵。3.设在GF(q)上可分解成t个不同的不可约多项式的乘积，试问有多少个码长为n的q元循环码？4.设C是一个二元循环码，证明分量全为1的向量(11…1)ÎC的充分必要条件是C包含一个重量为奇数的码字。5.在GF(2)上能分解成不可约因式的乘积：确定所有码长为7的循环码，并且准确描述这些码的特性。解：由题知n=7,k=6,4(1)当k=6时g(x)=x-1(2)当k=4时g(x)=x3+x+1或x3+x2+16.请对任意一个21-bit的数据，例如使用自己的学号化成2进制数，高位补“0”或某些随机数）（1）给出BCH(31,21)码的码多项式；（2）假设传输过程中错了一位（可以任意设定），请译码；（3）假设传输过程中错了两位（可以任意设定），请译码；（4）假设传输过程中错了三位（可以任意设定），请译码。解：（1）我们可以任选一个21-bit的数据，假设所选数据为020321，其二进制数表示为：00010000000110010000121位码查表可知（31，21）码的本原多项式为：g(x)=x17+x9+x8+x5+1输入多项式为：u(x)=x17+x9+x8+x5+1所以输出码多项式为：v(x)=u(x)g(x)=(x17+x9+x8+x5+1)(x10+x9+x8+x6+x5+x3+1) =x27+x26+x25+x23+x22+x20+x19+x17+x16+x14+x12+x8+x6+x3+1(2)假设接收到的多项式为：r(x)=x27+x25+x23+x22+x20+x19+x17+x16+x14+x12+x8+x6+x3+1则可得：σ（x）=α26x+1即错误位置为26，可以纠正。(3)假设接收到的多项式为：r(x)=x27+x26+x23+x22+x20+x19+x17+x16+x14+x12+x8+x6+1则可得：σ（x）=（α25x+1）（α3x+1）所以：β1=α-25β2=α-3即错误位置为x3和x25，可以纠正。(4)假设接收到的多项式为：r(x)=x27+x26+x25+x19+x17+x16+x14+x12+x8+x6+x3+1出现了3个错误，接收端能检出错误，但无法纠正。2.已知GF(25)中元素的几种表示如表11.8所示，有关元素的最小多项式如下：　,,,,,。现欲对上题信源编码输出进行扩展的BCH(32,16)信道编码再传送。（1）对于消息(1000111111101010)给出信道编码的输出码字；（2）若接收矢量为(10001111111010100110100100111101)，试判断是否有错，如只有一个错请纠正之，如有两个或三个错请说明纠正的方法。表11.8GF(25)域元素的两种表示（本原多项式p(x)=x5+x2+1）100001a801101a1611011a2411110a00010a911010a1710011a2511001a200100a1010001a1800011a2610111a301000a1100111a1900110a2701011a410000a1201110a2001100a2810110a500101a1311100a2111000a2901001a601010a1411101a2210101a3010010a710100a1511111a2301111a3100001解：由题知：m=5，n=25-1=31扩展的BCH(31+L,K)码，则L=1(即加了1为奇偶校验位)，K=16（1）若可以纠1个错，则g(x)=p(x)=x5+x2+1则编码输出为：u(x)g(x)=（2） 8.令是(15,5)循环码的生成多项式，（1）求出该码的校验多项式；（2）写出该码的系统码形式的G和H矩阵；（3）构造k级编码器。解：由题可得：x10=g(x)+x8+x5+x4+x2+x+1x11=xg(x)+x9+x6+x5+x3+x2+xx12=x2g(x)+x10+x7+x6+x4+x3+x2=(x2+1)g(x)+x8+x7+x6+x5+x3+x+1x13=(x3+x)g(x)+x9+x8+x7+x6+x4+x2+xx14=(x4+x2)g(x)+x10+x9+x8+x7+x5+x3+x2=(x4+x2+1)g(x)+x9+x7+x4+x3+x+1所以可得：bo(x)=x8+x5+x4+x2+x+1b1(x)=x9+x6+x5+x3+x2+xb2(x)=x8+x7+x6+x5+x3+x+1b3(x)=x9+x8+x7+x6+x4+x2+xb4(x)=x9+x7+x4+x3+x+1进而有：G= H=9.求GF(25)上以a,a3为根的二进制循环码：（1）写出生成多项式g(x)，确定码长n和信息位个数k；（2）写出该码系统码形式的G和H矩阵；（3）求出该码的R和最小距离。解：（1）查表可得本原多项式为：p(x)=x5+x2+1又g(x)=LCM{Φ1(x),Φ3(x)}当β1=α-β2=α-3用matlab函数gfminpol(1，5)和gfminpol(3，5)分别得：Φ1(x)=x5+x3+1Φ3(x)=x5+x3+x2+x+1所以g(x)=Φ1(x)Φ3(x)=x10+x7+x5+x2+x+1所以n=25-1=31，k=31-10=21（2）同样由上题的方法可求出系统码形式的G和H矩阵x10=g(x)+x7+x5+x2+x+1x11=xg(x)+x8+x6+x3+x2+x……….X31=………可进一步写出bo(x)……b21(x)，从而写出G，HG=H=（3）10.令n是g(x)|(xn–1)|的最小正数。现用该g(x)生成位n的循环码，证明码的最小距离至少为3。 10.构造(15,5,7)码的译码器，它的生成多项式g(x)=x10+x8+x5+x4+x2+x+1，该码能纠正3个错误。设用简单的捕错译码器译码。（1）证明所有2个错误能被捕获；（2）能捕获所有3个错误的图样吗？若不能，则有多少种3个错误图样不能被捕获；（3）作出该码的简单捕获译码器。12.对，存在有一个长为纠t个错误的二进制本原BCH码吗？若有找出它的g(x)。第十二章卷积码1.试画出k=3，效率为1/3，生成多项式如下所示的编码状态图、树状图和网格图：解：g1(D)=D+D2，g2(D)=1+D，g3(D)=1+D+D2所以可得状态图如下：其中（s0:00，s1:01，s2:10，s3:11）树状图如下： 011000100111001010110101011111………………10网格图为：1.假定寻找从伦敦到维也纳坐船或坐火车的最快路径，图12.25给出了各种安排，各条分支上标注的是所需时间。采用维特比算法，找到从伦敦到维也纳的最快路线，解释如何应用该算法，需做哪些计算，以及该算法要求在存储器里保存什么信息。解：从伦敦到维也纳的最快路线为：伦敦——巴黎——慕尼黑——维也纳此算法需计算从伦敦到维也纳中间所可能经过的各节点离伦敦的时间，保留其中最短的，去除其它的。需要记录下各中间节点离伦敦的最短时间，其算法的实现就是Dijkstra算法。 1.考虑图12.26中的卷积码。（a）写出编码器的连接矢量和连接多项式。（b）画出状态图、树状图和网格图。解：（1）由图可知：连接矢量为：g(1)=[1,0,1]g(2)=[0,1,1]连接多项式为：g(1)（D）=1+D2g(2)（D）=D+D2（２）状态图为：其中（s0:00，s1:01，s2:10，s3:11）　　　树状图为：0100110100100111………………10 网格图为：1.下列码率为1/2的编码中哪些会引起灾难性错误传播？（a）g1(X)=X2，g2(X)=1+X+X3（b）g1(X)=1+X2，g2(X)=1+X3（c）g1(X)=1+X+X2，g2(X)=1+X+X3+X4（d）g1(X)=1+X+X3+X4，g2(X)=1+X2+X4（e）g1(X)=1+X4+X6+X10，g2(X)=1+X3+X4（f）g1(X)=1+X3+X4，g2(X)=1+X+X2+X4解：会引起灾难性错误传播的有：（ｂ）有公因子（１＋ｘ）（ｃ）有公因子（１＋ｘ＋ｘ２）（ｄ）有公因子（１＋ｘ＋ｘ２）故此三个会引起会引起灾难性错误传播。6.已知(2,1,3)码的子生成元g(1,1)=(1101),g(1,2)=(1110)。（1）求出该码的G(D)和H(D)矩阵，以及G¥和H¥矩阵；（2）画出该码的编码器；（3）求出相应于信息序列M=(11001)的码序列；（4）此码是否是系统码？解：（１）因g(1,1)（Ｄ）=１＋Ｄ＋Ｄ３　　g(1,2)（Ｄ）＝１＋Ｄ＋Ｄ２所以Ｇ（Ｄ）＝［１＋Ｄ＋Ｄ３，１＋Ｄ＋Ｄ２］ Ｈ（Ｄ）＝（２）（３）ｖ（１）＝（１１００１）＊（１１０１）　　　　　＝１０１１０１０１　　　ｖ（２）＝（１１００１）＊（１１１０）　　　　　＝１００１１１１０交织得：ｖ＝（１１，００，１０，１１，０１，１１，０１，１０）可知该码为非系统码。8.设有一个(3,2,3)系统码的子生成元分别为：g(1,3)(D)=1+D2+D3,g(2,3)(D)=1+D+D3，问（1）此码是恶性码吗？为什么？（2）画出该码的编码器和对偶码的编码器；（3）画出有4个分支长的树图；（4）求出此码的最小距离dm；（5）求出此码的自由距离。9.已知有一个(3,1,2)码的子生成元是：g(1,1)=1+D,g(1,2)=1+D2和g(1,3)=1+D+D2。（1）求出该码的G(D)和H(D)；（2）画出该码的编码电路；（3）该码是否是恶性码？找出有最小延迟前馈的逆矩阵G–1(D)。解：（１）G(D)＝［１＋Ｄ，１＋Ｄ２，１＋Ｄ＋Ｄ２］ 第十三章纠突发错误码（缺）第十四章保密通信的理论基础1.若已知DES体制中8个S盒之一的S盒选择压缩函数如下：列号行号01234567891011121314150144131215118310612590710157414213110612119538241148136211151297310503512824917511214100613假设输入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,…，进行加密。解：用加密方程将ABE，DEAD分别代入可得结果为1，32，14，4，14，1，43.试用秘密密钥（d,n）=（13,51）将报文4,1,5,1解密。解：用解密方程将4,1,5,1分别代入可得结果为4，1，20，14.试用公开密钥（e,n）=（3,55）将报文BIDHIGH用A=01,B=02,…，进行加密。解：用加密方程将BIGHIGH分别代入可得结果为8，14，9，17，14，13，175.用秘密密钥（d,n）=（5,51）将报文4,20,1,5,20,5,4解密。解：用解密方程将4,20，1，5，20，5，4分别代入可得结果为4，5，1，4，5，14，4 6.一个英文加密系统使用10个随机字母组成的密钥序列，计算其惟一性距离。（1）每个密钥字符可以是26个字母中的任意一个，字母可以重复。（2）密钥符号不能重复。如果密钥序列由0~999整数中的10个随机整数组成，重新计算惟一性距离。解：（1）密钥熵为英语的绝对码率：r’=log226=4.7比特/字符英语实际码率：r=1.5比特/字符冗余：D=r’–r=3.2比特/字符单一性距离：N=H(K)/D=47/3.2»15字符（2）密钥符号不能重复时密钥熵为单一性距离：N=H(K)/D=44.13/3.2»14字符（3）密钥熵为单一性距离：N=H(K)/D=99.66/3.2»32字符7.使用RSA加密消息M=3,质数p=5,q=7。解密密钥d选为11，计算加密密钥e的值。解：f(n)=4´6=24解同余方程可得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为251用加密方程将DIGTAL分别代入可得结果为9.下面一段密文本来是连续的字符串，只是为了便于阅读将它分成每5个字符一组。明文是一般计算机教科书中的一段话，因此也许会有“COMPUTER”这个单词出现。加密采用的是Polybius方阵密码系统（参见14.1.3节）。明文中无安全可靠信道，无标点符号，试对此密文进行破译。　　　　AAUANCVIRERURNNDLTMEAEEPBYTUSTICEAT NPMEYIICGOGORCHSRSOCNNTIIIMIHAOOFPAGSIVTTPSITLBOLROTOEX7.英文字母的替代密码的一般形式为C=aM+b(模26)其中这M为明文的字母，C为密文的字母，a为与26互素的整数，b为0~25中的任意一个整数。试分析（1）a=1，称为加法密码和（2）b=0，称为乘法密码的特点及存在的问题。第十五章信息理论的广泛应用（缺）'