信息论与编码习题解答

（有问题请更正并通知XIEZGNTUEDUCN）第二章信息的度量1一珍珠养殖场收获240颗外观及重量完全相同的特大珍珠，但不幸被人用外观相同但重量仅有微小差异的假珠换掉1颗。（1）一人随手取出3颗，经测量恰好找出了假珠，问这一事件大约给出了多少比特的信息量；（2）不巧假珠又滑落进去，那人找了许久却未找到，但另一人说他用天平最多6次能找出，结果确是如此，问后一事件给出多少信息量；（3）对上述结果作出解释。解（1）从240颗珠子中取3颗，含1颗假珠的概率为（2）240颗中含1颗假珠，用天平等分法最多6次即可找到假珠，是必然事件，因此信息量为0。（3）按照SHANNON对信息量的定义，只有事件含有不确知成分，才有信息量，且不确知成分越大，信息量越大，必然事件则没有信息量。但从广义信息论来说，如果那人不知用天平二分法找假珠，另一人告之此事，使他由不知到知，也应该含有一定的信息量。2每帧电视图像可以认为是由3105个象素组成，所有象素均独立变化，且每一象素又取128个不同的亮度电平，并设亮度电平等概率出现。问每帧图像含有多少信息量如果一个广播员在约10000个汉字的字汇中选取1000个字来口述此电视图像，试问广播员描述此图像所广播的信息量是多少（假设汉字字汇是等概率分布，且彼此独立）若要恰当地描述此图像，广播员在口述中至少需用多少汉字解设电视图像每个像素取128个不同的亮度电平，并设电平等概率出现，则每个像素亮度含有的信息量为7128HLBX比特/像素一帧中像素均是独立变化的，则每帧图像信源就是离散亮度信源的无记忆N次扩展信源。得每帧会图像含有的信息量为61012XNHXHN比特/每帧广播口述时，广播员是从10000个汉字字汇中选取的，假设汉字字汇是等概率分布的，则汉字字汇中每个汉字含有的信息量29131000LBYH比特/字广播员口述电视图像是从此汉字字汇信源中独立地选取1000个字来描述的。所以，广播员描述此帧图像所广播的信息量为32680LOGLOG22BITPI80132402239CCP44103291101000LBYNHYHN比特/千字若广播员仍从此汉字字汇信源Y中独立地选取汉字来描述电视图像，每次口述一个汉字含有信息量是HY，每帧电视图像含有的信息量是NXH，则广播员口述此图像至少需要的汉字数等于158000105812913101256YHXHN字3已知X1,0PXP,1P1求证HXHP2求HP并作其曲线，解释其含义。（1）证明（2）该HP曲线说明，当0与1等概出现时，即P05时，熵最大。当P由05分别趋向于0和1时，熵逐渐减小至0。4证明HX3|X1X2HX2|X1，并说明等式成立的条件。证明设离散平稳信源输出的随机符号序列为X1,X2,X3,。又设11XX,22XX,33XX,而且321,XXX都取自于同一符号集GAAAA,21，并满足有1,1|,1|,1|3213323212132312XXXXXXXPXPXPXXXPXXPXXPHP10510P011IPPIXH11PHPLBPPLBP11213213132132321321313221321123132312XXPXXXPXXPXXXPXXPXXXPXXXPXXPXXPXXPXXXXXXXXXXXX在区域0，1内设FXXLOGX,FX在0，1内是型凸函数，所以满足詹森不等式QIQIIIIIXPFXFP11其中11IQIP现今|123XXXPXI,设其概率空间为|21XXP，并满足11|21XXXP所以根据詹森不等式得|LOG|LOG|LOG|LOG|213212132121321321212121111111XXXPXXPXXXPXXPXXXPXXXPXXPXXXPXXXPXXXXPXXXXIXIXII所以|22322313232111XPXXPXPXXXPXXPXXXPXX上式对所有321,XXX的取值都成立，所以|LOG|LOG|2323213231232132123231111XXPXXPXXXPXXXPXXPXXXPXXPXXPXXXPXXX所以因为222,10XXXP，所以上式两边相乘，等号不变。有|LOG|LOG|2323221323121XXPXXPXPXXXPXXXPXPX上式对所有32,XX都成立，所以对所有32,XX求和下式也成立23123|LOG|LOG2332213321XXXXXXXPXXPXXXPXXXP因为HX3|X1X2HX3|X2所以是平稳信源HX3|X2HX2|X1得HX3|X1X2HX2|X1只有当|23213XXPXXXP对所有321,XX时等式成立。5设有一概率空间，其概率分布为P1,P2,PQ，且P1P2。若取11PP，22PP，其中0114证明对于一个二元线性码L一定满足下列条件之一（1）码L中所有码字具有偶数重量；（2）码L中一半的码字具有偶数重量，另一半的码字具有奇数重量。证明（反证法）奇奇数重量，偶偶数重量；由题意奇奇奇偶偶偶偶奇奇假设KN,线性码有K2个码字，其中M个是偶数重量，MK2个是奇数重量。且MMK2若1）偶数个数大于奇数个数，则MMK2；若2）偶数个数小于奇数个数，则MMK2。情况1）成立，则第MMK12个偶数重量的码字与奇数重量的码字相加时，结果应是第MMK12个奇数重量的码字。这与情况1）相矛盾。同理，可以推出情况2）时的矛盾。由此可得，原假设不成立。原命题得证。5设二元线性码L的生成矩阵为100110010101111G，求码L的最小距离。因为CMIN,MIN,MINWYXDDKNYX所以2MIND。6设3元线性码L的生成矩阵为10110112G，求码长L的最小距离并且证明L是完备的。3MIND121321MINDT题中由生成矩阵知，该线性码是2,4码，2,2,4KNKN陪集首的个数为422，能纠正3个错误。而1BIT错误图样的个数为414C，又34，所以线性码是完备的。7设二元线性码L的生成矩阵为1101001010G，建立码L的标准阵并且对字11111和10000分别进行译码。01010000010101001011G100000101000100KNTIPH共4222K个码字。1101011100001001010010000000码字消息标准阵为00010010001001011000100111100100001010010101000000110101000010010110000001001000111101010001110001001100010010010000001011011100010101100001110101000001010000002MIND021221MINDT译码得111111110100008设5元线性码L的生成矩阵为124030214120314G。（1）确定码L的标准型生成矩阵；（2）确定码L的标准型校验矩阵；（3）求码L的最小距离。1000010110013320001040440013320001440411412041302304211412041302141203042121G01310130121H4MIND9设有码如下所示信息码字0000000010110110101111111010（1）找出生成矩阵G与监督矩阵H；（2）在二元对称信道下给出最大似然译码的译码表；（3）求正确译码的概率。（1）设信息位21MM，码字01234CCCCCC由编码规则210112122314MMCMCMMCMCC00003414234CCCCCCCC100110100100111H1011011101G（2）译码表10001001101101010000011011100001110100010100100100000100100000100100000000错误图样伴随式（3）正确译码的概率为54322355544532352315110181111811PPPPPPPPCPPCPPCPPPE10建立二元汉明码HAM7,4的包含陪集首和伴随式的伴随表，并对收到的字0000011，1111111，1100110，1010101进行译码。（1）TEHS100101101011100010111H100010001110011111101ES10000001010100000111001000011000010000110000100100000001001000000010010000000000陪集首伴随式（2）译码01100000111THS00011111112THS10011001103THS11010101014THS0001011000100000000111V11111112V1100010000010011001103V1000101001000010101014V译码得到结果00011C11112C11003C10004C11设一个7,4码的生成矩阵为1000111010010100100110001110（1）求出该码的全部码矢；（2）求出该码的一致校验矩阵；（3）作出该码的标准译码码表。（1）0111000011101101100110010101101010100101010000111010011001001100100001110000100000000000码矢信息1111111111111100011110110110011011100010110010110101011101010010101001001100110001111000（2）100011101011010011011H（3）100010001011110101111EEHST11110000001010100000011001000011000010001000000100010000001000100000010000000000伴随式陪集首12设一个二进制N,K码C的G矩阵不含全零列，将C的所有码字排成2KN的阵，证明（1）阵中不含有全零列；（2）阵中的每一列由12K个零和12K个1组成；（3）在一特定分量上为0的所有码字构成C的一个子空间，问该子空间的维数是多少（1）KN,码共有K2个码字1包括全零矢量；2任意两个码字的和也是码字；假设组成的2KN阵包含一个全零列，则每个码字重复两次，实际只有12K个不同的码字，与该码的定义相矛盾。所以阵中不含全零列。（2）等效于证每一列中0和1的个数相等。如（3，3）码111011101001110010100000由于任意两个码字的和也是码字，所以码字中奇数和偶数的数目相等。又由习题1042，线性码中一半码字具有偶数重量，另一半码字具有奇数重量，于是每一列中0和1的个数相等。所以，阵中的每一列由12K个零和12K个1组成的命题成立。13一个8,4系统码，它的一致校验方程为0123101220133023CMMMCMMMCMMMCMMM式中0123,MMMM是信息位，0123,CCCC是校验位。找出该码的G和H，并证明该码的最小距离为4。000032033102210132103203310221013210MMMCMMMCMMMCMMMCMMMCMMMCMMMCMMMC01101100010110100011100101110000132103210MMMMCCCC11011000101101000111001011100001H10001101010010110010011100011110G4MIND第十一章循环码1设P是一个素数，（1）在GFP上把1PX分解成不可约因式的乘积；（2）在GFP上把11PX分解成不可约因式的乘积。2在GF3上把14X分解成不可约多项式的乘积，确定所有码长是4的三元循环码，并写出每一个码的生成矩阵和校验矩阵。3设在GFQ上S0S2S3S11/1000/0000/1010/1111/1001/0110/010/110可分解成T个不同的不可约多项式的乘积，试问有多少个码长为N的Q元循环码4设C是一个二元循环码，证明分量全为1的向量111C的充分必要条件是C包含一个重量为奇数的码字。5在GF2上S0S0S0S0S0000000000000S2S2S2S1S1S1S1S3S3S3011011011011100100100111111111101101110110010001001010能分解成不可约因式的乘积S0S2S3S11/000/001/100/100/111/111/010/01S3确定所有码长为7的循环码，并且准确描述这些码的特性。解由题知N7,K6,41当K6时GXX12当K4时GXX3X1或X3X216请对任意一个21BIT的数据，例如使用自己的学号化成2进制数，高位补“0”或某些随机数）（1）给出BCH31,21码的码多项式；（2）假设传输过程中错了一位（可以任意设定），请译码；（3）假设传输过程中错了两位（可以任意设定），请译码；（4）假设传输过程中错了三位（可以任意设定），请译码。解（1）我们可以任选一个21BIT的数据，假设所选数据为020321，其二进制数表示为00010000000110010000121位码查表可知（31，21）码的本原多项式为GXX17X9X8X51输入多项式为UXX17X9X8X51所以输出码多项式为VXUXGXX17X9X8X51X10X9X8X6X5X31X27X26X25X23X22X20X19X17X16X14X12X8X6X312假设接收到的多项式为RXX27X25X23X22X20X19X17X16X14X12X8X6X31则可得（X）26X1即错误位置为26，可以纠正。3假设接收到的多项式为RXX27X26X23X22X20X19X17X16X14X12X8X61则可得（X）（25X1）（3X1）所以12523即错误位置为X3和X25，可以纠正。4假设接收到的多项式为RXX27X26X25X19X17X16X14X12X8X6X31出现了3个错误，接收端能检出错误，但无法纠正。7已知GF25中元素的几种表示如表118所示，有关元素的最小多项式如下S0S003310101022,3413XXXX,XXXX335,3457XXXX,24711XXXX,XXXX41115。现欲对上题信源编码输出进行扩展的BCH32,16信道编码再传送。（1）对于消息1000111111101010给出信道编码的输出码字；（2）若接收矢量为10001111111010100110100100111101，试判断是否有错，如只有一个错请纠正之，如有两个或三个错请说明纠正的方法。表118GF25域元素的两种表示（本原多项式PXX5X21）100001801101161101124111100001091101017100112511001200100101000118000112610111301000110011119001102701011410000120111020011002810110500101131110021110002901001601010141110122101013010010710100151111123011113100001解由题知M5，N25131扩展的BCH31L,K码，则L1即加了1为奇偶校验位，K16（1）若可以纠1个错，则GXPXX5X21则编码输出为UXGX（2）8令1085421GXXXXXXX是15,5循环码的生成多项式，（1）求出该码的校验多项式；（2）写出该码的系统码形式的G和H矩阵；（3）构造K级编码器。解由题可得X10GXX8X5X4X2X1X11XGXX9X6X5X3X2XX12X2GXX10X7X6X4X3X2X21GXX8X7X6X5X3X1X13X3XGXX9X8X7X6X4X2XX14X4X2GXX10X9X8X7X5X3X2X4X21GXX9X7X4X3X1所以可得BOXX8X5X4X2X1B1XX9X6X5X3X2XB2XX8X7X6X5X3X1B3XX9X8X7X6X4X2XB4XX9X7X4X3X1进而有G110110000110100101100001011110010110010001111011100100010011101111000001001H0000110101000000001011111000000010011010000000100001101000001000010011000000000011100000010000001110000100000000111001000000010110010000000001011100009求GF25上以,3为根的二进制循环码（1）写出生成多项式GX，确定码长N和信息位个数K；（2）写出该码系统码形式的G和H矩阵；（3）求出该码的R和最小距离。解（1）查表可得本原多项式为PXX5X21又GXLCM1X,3X当123用MATLAB函数GFMINPOL1，5和GFMINPOL3，5分别得1XX5X313XX5X3X2X1所以GX1X3XX10X7X5X2X1所以N25131，K311021（2）同样由上题的方法可求出系统码形式的G和H矩阵X10GXX7X5X2X1X11XGXX8X6X3X2XX31可进一步写出BOXB21X，从而写出G，HGH（3）10令N是GX|XN1|的最小正数。现用该GX生成位N的循环码，证明码的最小距离至少为3。11构造15,5,7码的译码器，它的生成多项式GXX10X8X5X4X2X1，该码能纠正3个错误。设用简单的捕错译码器译码。（1）证明所有2个错误能被捕获；（2）能捕获所有3个错误的图样吗若不能，则有多少种3个错误图样不能被捕获；（3）作出该码的简单捕获译码器。12对12,3MTM，存在有一个长为12M纠T个错误的二进制本原BCH码吗若有找出它的GX。第十二章卷积码1试画出K3，效率为1/3，生成多项式如下所示的编码状态图、树状图和网格图21XXXGXXG12231XXXG解G1DDD2，G2D1D，G3D1DD2所以可得状态图如下其中（S000，S101，S210，S311）S0S2S3S11/1000/0000/1010/1111/1001/0110/0101/110树状图如下网格图为S0S0S0S0S0000000000000S2S2S2S1S1S1S1S3S3S30110110110111001001001111111111011011101100100010010102假定寻找从伦敦到维也纳坐船或坐火车的最快路径，图1225给出了各种安排，各条分支上标注的是所需时间。采用维特比算法，找到从伦敦到维也纳的最快路线，解释如何应用该算法，需做哪些计算，以及该算法要求在存储器里保存什么信息。解从伦敦到维也纳的最快路线为伦敦巴黎慕尼黑维也纳此算法需计算从伦敦到维也纳中间所可能经过的各节点离伦敦的时间，保留其中最短的，去除其它的。需要记录下各中间节点离伦敦的最短时间，其算法的实现就是DIJKSTRA算法。011000100111001010110101011111103考虑图1226中的卷积码。（A）写出编码器的连接矢量和连接多项式。（B）画出状态图、树状图和网格图。解（1）由图可知连接矢量为G11,0,1G20,1,1连接多项式为G1（D）1D2G2（D）DD2（）状态图为其中（S000，S101，S210，S311）S0S2S3S11/000/001/100/100/111/111/010/01S3树状图为010011010010011110网格图为S0S0S0S0S000000000S3S3S3101010101111110101011111010110000010S2S1S1S1S2S2S24下列码率为1/2的编码中哪些会引起灾难性错误传播（A）G1XX2，G2X1XX3（B）G1X1X2，G2X1X3（C）G1X1XX2，G2X1XX3X4（D）G1X1XX3X4，G2X1X2X4（E）G1X1X4X6X10，G2X1X3X4（F）G1X1X3X4，G2X1XX2X4解会引起灾难性错误传播的有（）有公因子（）（）有公因子（）（）有公因子（）故此三个会引起会引起灾难性错误传播。6已知2,1,3码的子生成元G1,11101,G1,21110。（1）求出该码的GD和HD矩阵，以及G和H矩阵；（2）画出该码的编码器；（3）求出相应于信息序列M11001的码序列；（4）此码是否是系统码解（）因G1,1（）G1,2（）所以（），（）（）（）（）（）（）（）（）（）交织得（，）可知该码为非系统码。8设有一个3,2,3系统码的子生成元分别为G1,3D1D2D3,G2,3D1DD3，问（1）此码是恶性码吗为什么（2）画出该码的编码器和对偶码的编码器；（3）画出有4个分支长的树图；（4）求出此码的最小距离DM；（5）求出此码的自由距离。9已知有一个3,1,2码的子生成元是G1,11D,G1,21D2和G1,31DD2。（1）求出该码的GD和HD；（2）画出该码的编码电路；（3）该码是否是恶性码找出有最小延迟前馈的逆矩阵G1D。解（）GD，第十三章纠突发错误码（缺）第十四章保密通信的理论基础1若已知DES体制中8个S盒之一的S盒选择压缩函数如下列号行号01234567891011121314150144131215118310612590710157414213110612119538241148136211151297310503512824917511214100613假设输入S盒的输入矢量为MM0M1M5。试求通过选择压缩函数S变换后的输出矢量。解M通过S盒时，代换表将选出一个相应的输出矢量。可以将矢量中的首尾两项M0M5看作是控制盒S中采用的不同行号，而将其余的四项看作是不同列号的一种。这样每个M就有唯一的Y相对应。如输入M（101100）则输出Y为第2行，第6列，结果为2即00102试用公开密钥（E,N）（5,51）将报文ABE，DEAD用A01,B02,，进行加密。解用加密方程,NE模MC将ABE，DEAD分别代入可得结果为1，32，14，4，14，1，43试用秘密密钥（D,N）（13,51）将报文4,1,5,1解密。解用解密方程,NE模CM将4,1,5,1分别代入可得结果为4，1，20，14试用公开密钥（E,N）（3,55）将报文BIDHIGH用A01,B02,，进行加密。解用加密方程,NE模MC将BIGHIGH分别代入可得