2022年《信息论、编码与密码学》课后习题答 .pdf

信息论、编码与密码学课后习题答案第 1 章信源编码1.1考虑一个信源概率为 0.30 ，0.25，0.20 ，0.15 ，0.10 的 DMS 。求信源熵H（X） 。解：信源熵512)(log)(kkkppXH H(X)=-0.30*(-1.737)+0.25*(-2)+0.2*(-2.322)+0.15*(-2.737)+0.1*(-3.322) =0.521+0.5+0.464+0.411+0.332 =2.228(bit) 故得其信源熵 H(X)为 2.228bit 1.2证明一个离散信源在它的输出符号等概率的情况下其熵达到最大值。解：若二元离散信源的统计特性为P+Q=1 H(X)=-P*log(P)+(1-P)*log(1-P) 对 H(X)求导求极值，由dH(X)/d(P)=0 可得211101logppppp可知当概率 P=Q=1/2时，有信源熵)(1)(maxbitXH对 于 三 元 离 散 信 源 ， 当 概 率3/1321PPP时 ， 信 源 熵)(5 8 5.1)(maxbitXH，此结论可以推广到N元的离散信源。1.3 证明不等式 ln1xx。 画出曲线1lnyx和21yx的平面图以表明上述不名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 48 页 - - - - - - - - - 等式的正确性。证明：max( )ln1(0)1( )( )01001( )0( )0ln11ln1ln1f xxxxf xxf xxxxf xf xfxxxxxxx令，又有时此时也即当时同理可得此时综上可得证毕绘制图形说明如下可以很明确说明上述不等式的正确性。1.4 证明(;)0I X Y。在什么条件下等号成立？1111(,) (,)( ,)(,)log() ()nmijijijnmijijijijIP x y I x yP x yP x yP x P y（X；Y）=当和相互独立时等号成立。1.5 有一个信源X，它有无穷多个可能的输出，它们出现的概率为P（Xi ）=2i-1,i=1,2,3,., 这个信源的平均自信息H （X）是什么？解：因为 P（Xi）=2i-1,i=1,2,3,所以 H （X）= -1()log()niiip xp x1 x y Y=x-1 Y=lnx 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 48 页 - - - - - - - - - =-log2(2+2.22+3.23+.+n.2n) =2-（1-n）2n+11.6 考虑另一个几何分布的随机变量X，满足 P （Xi）=P （1-P）i-1 i=1,2,3,.,这个信源的 平均自信息 H（X）是什么？解：因为 P（Xi ）= P（1-P）i-1,i=1,2,3, 所以 H （X）= -1()log()niiip xp x=-logp(1-p)p(1-p)+2p(1-p)2+3p(1-p)3+.+np(1-p)n =(1-n)(1-p)n+1-2(1)pp1.7 考虑一个只取整数值的随机变量X ，满足nAnnXP2log1，其中22lo g1nnnA，,.,3,2n。求熵XH。解：为了方便计算，设nnB2log，则21nBA，ABnXP1；根据公式计算自信息量为：ABXPXIlog1log；则熵为：22222211logloglog1nnnnnnBBBBABABABABXIXPXH=？1.8 计算概率分布函数为否则001axaxp的均匀分布随机变量X 的微分熵XH。画出XH相对于参数101.0aa的平面图，并对结果进行评论。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 48 页 - - - - - - - - - 解：根据公式（ 1-21）可知，微分熵为：dxxpxpXHlog当ax0时，1axp，则aaaaxaadxaaXHaalogloglog1log0011当0 x或ax时，0 xp，则XH根据得到的结果可以画出相应的平面图，由图可以看到随着a的增加，即xp的减小，微分熵XH相应的增加。1.9 考虑一个信源的概率为05.0,15.0,20.0 ,25.0,35.0的 DMS 。（1）给出此信源的霍夫曼码。（2）计算出这些码子的平均码长R。（3）这个码的效率是多少？解：1）依题意，由霍夫曼编码的规则，得：11.00 XHa0 0.1 10 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 48 页 - - - - - - - - - 1x 0.35 2x 0.25 3x 0.20 4x 0.15 5x 0.05 表格如下：符号概率自信息码字1x0.35 1.515 1 2x0.25 2.000 01 3x0.20 2.322 000 4x0.15 2.738 0010 5x0.05 4.322 0011 2）由平均码长公式)()(1knkkxpxnR, 代入数据，得：)(3.225.06.06.05.035.0)05.0(5)15.0(4)20.0(3)25.0(2)35.0(1)()(51bitxpxnRkkk3）首先，该信源的熵为：1 0.65 00.40 000.20 011名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 48 页 - - - - - - - - - )(1215.2)1215. 2()2161.04107.04644. 05.05303. 0()322.405.0738.215.0322.220.00. 225.0515.135. 0()05.0log05.015.0log15.020. 0log20.025.0log25. 035.0log35.0(log)(22222251bitppXHkkk该码的效率为：9224.0)300.2/1215.2()(RXH1.10 考虑一个信源概率为 0.35 ，0.20 ，0.15 ，0.15 ，0.10 ，0.10，0.05，0.05的 DMS 。(1) 给出此信源的一种有效定长码。(2) 给出此信源的霍夫曼码。(3) 比较这两种码并给出评论。解：1）空2）依题意，由霍夫曼编码的规则，得: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 48 页 - - - - - - - - - 0.550.35 1.00 0.250.45 0.20 0.10 20. 01x20. 02x15. 03x15. 04x10. 05x10.06x05. 07x05. 08x01000000111111符号概率自信息码字1x0.20 2.322 01 2x0.20 2.322 000 3x0.15 2.738 001 4x0.15 2.738 100 5x0.10 1.000 101 6x0.10 1.000 110 7x0.05 4.322 1110 8x0.05 4.322 1111 3）空1.11 一个 DMS 只有三个输出符号，它们的概率为0.5 ，0.4 ，0.1 。(1) 给出此信源的霍夫曼码并确定编码效率。(2) 每次考虑两个符号时，给出此信源的霍夫曼码并确定编码效率。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 48 页 - - - - - - - - - (3) 每次考虑三个符号时，给出此信源的霍夫曼码并确定编码效率。解：(1) 本题的霍夫曼编码如下图所示：图 1.11 霍夫曼编码则霍夫曼码如下表：符号概率码字x10.5 1 x20.4 00 x30.1 01 该信源的熵为：321222()log(0.5log 0.5 0.4log 0.4 0.1log 0.1)0.5000 0.5288 0.33221.3610()kkkH Xppbit平均每个符号的比特数为：31() ()1(0.5)2(0.4)2(0.1)0.50.80.21.5000(/)kkkRn xp xbit符号该码的效率为：1.3160/1.5000 0.9073（2）把符号每两个分一组，重新应用霍夫曼编码算法，如下表所示：0.5 0.4 0.1 0 1 0.5 1 0 1.0 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 48 页 - - - - - - - - - 符号对概率码字x1x10.25 00 x1x20.20 010 x2x10.20 011 x2x20.16 1010 x1x30.05 100 x3x10.05 110 x2x30.04 1011 x3x20.04 1110 x3x30.01 1111 该信源的熵为：9212()log2.7219()()1.3610()kkkH XppbitH Xbit每个组的平均比特数为: 91() ()2(0.25) 3(0.2) 3(0.2) 4(0.16) 3(0.05) 3(0.05) 4(0.04) 4(0.04) 4(0.01)3.00(/)BkkkRn x P xbit 符号对3.00/21.5000(/)Rbit 符号故该码的效率为：1.3160/1.5000 0.9073(3) 依题意，把符合每三个分成一组，再重新应用霍夫曼编码算法，得: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 48 页 - - - - - - - - - 0.2000 0.2400 0.1600 0.1850 0.5800 0.0500 0.3400 1.0000 0.0450 0.1400 0.0850 0.4200 0.0400 0.2350 0.0400 0.0760 0.1100 0.0360 0.0320 0.1250111xxx0.1000211xxx0.1000112xxx0.1000121xxx0.0800221xxx0.0800212xxx0.0800122xxx0.0640222xxx0.0250311xxx0.0250131xxx0.0250113xxx0.0200321xxx0.0200231xxx0.0200312xxx0.0200132xxx0.0200213xxx0.0200123xxx0.0160322xxx0.0160232xxx0.0160 xxx100101010101001011010101010101010101编码表格如下：符号对概率自信息码字111xxx0.1250 2.7090 100 211xxx0.1000 3.3223 0000 121xxx0.1000 3.3223 0001 112xxx0.1000 3.3223 110 221xxx0.0800 3.6443 011 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 48 页 - - - - - - - - - 符号对概率自信息码字212xxx0.0800 3.6443 0100 122xxx0.0800 3.6443 0101 222xxx0.0640 3.9662 0011 311xxx0.0250 5.3223 10110 131xxx0.0250 5.3223 10111 113xxx0.0250 5.3223 11100 321xxx0.0200 5.6444 11101 231xxx0.0200 5.6444 11110 312xxx0.0200 5.6444 11111 132xxx0.0200 5.6444 001000 213xxx0.0200 5.6444 001001 123xxx0.0200 5.6444 001010 322xxx0.0160 5.9664 001011 232xxx0.0160 5.9664 101000 223xxx0.0160 5.9664 101001 331xxx0.0050 7.6646 1010101 313xxx0.0050 7.6646 10101000 133xxx0.0050 7.6646 10101001 332xxx0.0040 7.9666 10101100 323xxx0.0040 7.9666 10101101 233xxx0.0040 7.9666 10101110 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 48 页 - - - - - - - - - 符号对概率自信息码字333xxx0.0010 9.9668 10101111 1.14 确定下列比特流的Lempel-Ziv码：01001111100101000001010101100110000 从码字流恢复原来的序列。解：根据 Lempel-Ziv 算法列出下表：字典位置字典内容定长码字0001 0 00000 0010 1 00001 0011 00 00010 0100 11 00101 0101 111 01001 0110 001 00111 0111 01 00011 1000 000 00110 1001 0010 01100 1010 10 00100 1011 101 10101 1101 100 10100 1110 110 01000 1111 000 10000 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 48 页 - - - - - - - - - 第 2 章 信道容量和编码2.1 考虑图 2-10 所示的二元信道，设发送二元符号的先验概率为P0和 P1，其中P0+ P1=1，求后验概率(0 |1)P XY和(1|1)P XY。解：0p0XP1p1XPp0X1YPq1X0YPp10X0YPq11X1YP0Y,0XP0X0YP0XP0Y0XP0YP0Y0XP0YP0X0YP0XPqpp1pp1p1000YP1X0YP1XP0X0YP0XPqpp1p101Y, 1XP1X1YP1XP1Y1XP1YP1Y1XP1YP1X1YP1XPq1pppq1p1010X1YP0XP1YP1X1YP1XPq1ppp100 1 P0 0 P1 1 1-q p q1-p 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 48 页 - - - - - - - - - 2.5（1）一个电话信道具有带宽3000Hz,且 SNR=20dB.求信道容量。（2）若 SNR 增加到 25dB,求信道容量。解：(1) SNR=20dB=100 信道容量 =Wlog2 (1+SNR/W) (b/s) =3000*log2 (1+100/3000) =142 (b/s) (2) SNR=25dB=316 信道容量 =Wlog2 (1+SNR/W) (b/s) =3000*log2 (1+316/3000) =413 (b/s) 2.7 假定一个电视每秒钟显示30 个画面，每个画面大约有52 10个像素，每个像素需要 16 比特的彩色显示。假定SNR为 25dB， 计算支持电视信号传输所需要的带宽（利用信息容量定理）解： 根 据 题意， 该 电视 信 号所需 的 信 息容 量 为 ：573021016/9.6 10/Cbitsbits根据 信 息 容 量 定理 ：20log (1)PCWN W， 其 中0PN为信 噪 比 ， 据 题意025PdBN据上式解得带宽71.15 10CHz2.8 考虑图 2-15 所示的 Z 型信道。（1）求获得信道容量所需要的输入概率。（2）若将 N 个这样的信道相级联，证明联合信道可以用一个信道转移概率名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 48 页 - - - - - - - - - 为Np的等价 Z信道表示。（3）当 N时联合信道的容量是什么？图 2-15 解：(1) w 为带宽信道容量)1(log02WNPWC (b/s) )1(log2NSBC(2) 由图可知信道转移概率为P PPP)0 | 1()1 |0(那么 N级级联的信道转移概率WNPP级级联)1 |0(3) 当N时) 1|0(P级联信道的信道容量为每一次使用该信道时的最大平均互信息。其中最大值是在所有可能的输入概率上求得的即：);(max)(yxICjxp)()|(log)|()(max1010)(ijijiqjrijxpyPxyPxyPxPCj2.10 (1)证明对有限方差2，高斯随机变量具有所有随机变量可能获得的最大名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 48 页 - - - - - - - - - 微分熵。(2) 证明该熵由公式221/ 2log (2)e给出。证明：(1) 由题意可知，高斯随机变量获得的微分熵为：221()log (2)2H Xe则有：22()12HXee即其平均功率为：22()12HXee对于有限方差2的高斯随机变量，即当平均功率受限时，有：22( )1,()( ).p x dxxmp x dx即有：2()log2H Xe综上可得，对于平均功率受限的连续随机变量，当服从高斯分布时具有最大微分熵。(2) 随机变量的微分熵为：2()( )log( )HXp xp x dx (1) 对于高斯分布，我们有：2211( )exp() 22p xxm (2) 其中， m为数学期望。将(2) 式代入 (1) 可得：2211()( )ln() 22H Xp xxmdx (3) 由(3) 式可以推出：221()log (2)2H Xe (4) 故(4) 式即为本题所证。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 48 页 - - - - - - - - - 2.11 11()00(|)max() (|)log,()jqrijjijp xjiip yxp xp yxp y写一个程序，它在输入信道转移矩阵后计算出信道容量？解：依据设定情况在一般的二元通信信道输入前只有两种状态， 0和1，假设传输发生错误概率为p, 正确概率为 1-p. 这只是假定的一种情况，其实在程序中可看作这几个参量为个数组。 CP 及WP。再根据计算信道容量公式输出对应的信道容量值。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 48 页 - - - - - - - - - 第 3 章 纠错控制编码3.1 证明1111,0011,1100,0000C是一个线性码。 它的最小距离是什么？证明：由书中的定义3.8 可知，线性码应该满足一下条件：（1） 两个属于该码的码字的和仍然是一个属于该码的码字，（2） 全零字总是一个码字，（3） 两个码字之间的最小距离等于任何非零码字的最小重量，即wd设4321,ccccC，即00001c，11002c，00113c，11114c，首先证明条件（ 1） ：2211100ccc，3310011ccc，4411111ccc，4321111ccc，3420011ccc，2431100ccc，很明显，条件（ 1）是满足的。条件（ 2）也是显然成立的。最后证明条件（ 3） ：不难看出最小距离2d，并且最小重量2w，即wd综上，三个条件都满足，那么C 就是一个线性码，它的最小距离是2。3.3 考虑 GF （2）上的下列生成矩阵010101100100101G3）用此矩阵生成所有可能的码字。4）求奇偶校验矩阵H 。5）求与其等价的一个系统码的生成矩阵。6）构造该码的标准阵列。7）这个码的最小距离是多少。8）这个码能检测多少错误。9）写出这个码能检测的所有错误模式。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 48 页 - - - - - - - - - 10）这个码能纠多少个错误。11）如果我们用此编码方案， 那么符号错误概率是多少？将它与末尾的错误概率进行比较。12）这是一个线性码？解： （1）000c1010101100100101=00000100c2010101100100101=01010010c3010101100100101=11001110c4010101100100101=10011001c5010101100100101=00101101c6010101100100101=01111011c7010101100100101=11100111c8010101100100101=10110此矩阵生成的码为： 00000，01010，10011，11001，10100，11110，00111，01101 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 48 页 - - - - - - - - - （2）010101100100101G1-1-1000101011001110111P101111PT又在二元情况下，11101111PT奇偶校验矩阵可写为：IPHT1010101111 (4 该码的标准阵列1-1-1000101011001G（5）奇偶校验矩阵 H的第 1、3 列的和为零向量，因此，这个码的最小距离为：d*=2。（6）一个码至少可以检测所有重量小于或等于（d*-1 ）的非零错误模式。这个码的最小距离为： d*=2 ，所以重量为 1 的错误模式可以检测得到。（7）这个码能检测的所有错误模式 00001，00010，00100，01000，10000 （8）能纠正不多于 t 个错误应满足12td*又 d*=2 所以12t2即21t这个码能纠 0 个错误（9）才 vv （10）00000，01010，10011，11001，10100，11110，00111，01101 线性码的性质：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 48 页 - - - - - - - - - 1、两个属于该码的码字的和仍是属于该码的码字 00000+01010=01010 00000+11001=11001 00000+10011=10011 00000+10100=10100 00000+11110=11110 00000+00111=00111 00000+01101=01101 01010+10011=11001 01010+11001=10011 01010+10100=11110 01010+11110=10100 01010+00111=01101 01010+01101=00111 10011+11001=01010 10011+10100=00111 10011+11110=01101 10011+00111=10100 10011+01101=11110 11001+10100=01101 11001+11110=00111 11001+00111=11110 11001+01101=10100 10100+11110=01010 10100+00111=10011 10100+01101=11001 11110+00111=11001 11110+01101=10011 00111+01101=01010 满足第一条性质2、全零码字总是一个码字 00000，01010，10011，11001，10100，11110，00111，01101 满足第二条性质名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 48 页 - - - - - - - - - 3、一个线性码的两个码字之间的最小距离等于任何非零码字的最小重量，即 d*=w* D(00000，01010)=2 D(00000，10011)=3 D(00000，11001)=3 D(00000，10100)=2 D(00000，11110)=4 D(00000，00111)=3 D(00000，01101)=3 D(01010，10011)=3 D(01010，11001)=2 D(01010，10100)=4 D(01010，11110)=2 D(01010，00111)=3 D(01010，01101)=3 00000，01010，10011，11001，10100，11110，00111，01101 D(10011，11001)=2 D(10011，10100)=3 D(10011，11110)=3 D(10011，00111)=2 D(10011，01101)=4 D(11001，10100)=3 D(11001，11110)=3 D(11001，00111)=4 D(11001，01101)=2 D(10100，11110)=2 D(10100，00111)=3 D(10100，01101)=3 D(11110，00111)=3 D(11110，01101)=3 D(00111，01101)=2 这个码的最小距离为2 等于该码的最小重量满足第三条性质所以，这个码是线性码。3.4 构造 C=00000，10101，01010，11111的生成矩阵。因为这个G不是唯一名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 48 页 - - - - - - - - - 的，给出另一个能生成这个码字集合的生成矩阵。解：设生成矩阵是G=1111nmmnaaaa，由题知， m=2,n=5, c=iG i=(0,0) (0,1),(1,0),(1,1) 生成矩阵 G=01010101013.7 对下列每一个集合S，列出扩张码 : （1）S=0101，1010，1100 （2）S=1000，0100，0010，0001 （3）S=11000，01111，11110，01010 解: (1) 0101+1010=1111 ， 0101+1100=1001 1010+1100=0110 ， 0101+1010+1100=0011 再补上 0000 及原先 3 个公共组成第二，三问步骤省略 为1111，1001，0110，0011，0000，0101，1010，1100 (2) 为1100，1010，1001，0110，0101，0011，1110，1011，0111，1101，1111，0000，1000，0100，0010，0001 (3) 为10111，00110，10010，10001，00101，10100，01001，11000，01111，11110，01010，00000，11011，01100，11101 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 48 页 - - - - - - - - - 3.8 考虑（ 23，12，7）二元码。证明若它被用在一个比特错误概率为p=0.01的二元对称信道（ BSC ）中，字错误概率将约为0.00008 解：由题可得其转移概率p=0.01，在(23.12.7)二元码中其可以纠出2t+1=7 t=3位错误即在码元中出现 4 个错才会使得其出现误码率，出现3 个以上错误的概率为00008. 01)1(203323212223221123230023234232323423qpCqpCqpCqpCpCppCnnnnnnn则出现的误字率为0.00008 所以得证。3.9 假设 C是一个二元码， 它的奇偶校验矩阵为H 。证明由 C 通过添加整体奇偶校验比特得到的扩展码1C的奇偶校验矩阵为1|0|0|0111|1HH. 证明：根据题意，扩展码1C为: 1|0|0|0111| 0CC, 又C得奇偶校验矩阵为 H ，0TCH。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 48 页 - - - - - - - - - 1|1|1|1000|1TTHH，11| 0|10| 0|10|0| 0|100000111| 0000|1TTTCHC HCH即扩展码1C的奇偶校验矩阵为1H。证毕。3.11 设 C是长度为 n, 最小距离为 7 的二元完备码。证明n=7或 n=23。证明：由完备码的定义可知，一个完备码必须满足下列条件：02tn kiniC (1) 由题意可知：*21dt，其中*7d即有：3t当 n=7时，由（ 1）式可得，371702iiC右式展开得：3012377777017213564iiCCCCC左式同理，可证得 n=23时，同样满足（ 1）式。故可证明当 n=7 或 n=23时，C是二元完备码。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 25 页，共 48 页 - - - - - - - - - 3.12 用Hr来表示二元汉明码的码率，求limHkr 。解：根据二元汉明码的性质可知：mm(n,k)=(2-1,2-1-m)其中 m是任意正整数。则由码率的定义可知：Hkrnmm2 -1-m2 -1则有：limlim1Hkkrmm2 -1-m2 -1名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 26 页，共 48 页 - - - - - - - - - 第 4 章 循环码4.1 下面的哪个码是（ a）循环码，（b）与一个循环码等价？（1）2GF上的1001,0011,1100,0110,0000。（2）2GF上的11011,01101,10110,00000。（3）3GF上的11011,01101,10110,00000。（4）3GF上的2211,1122,0000。（5）长度为n的 q- 元重复码。解：由书中定义 4.1 可知，循环码需要满足两个条件，（1） 首先它必须是一个线性码，（2） 其 次 它 的 一 个 码 字 的 任 意 循 环 移 位 的 结 果 还 是 一 个 码 字 ， 即 若110,.,naaa为其中的一个码字，则201,.,nnaaa也是其中一个码字。下面一一证明：（1）首先证明1C是一个线性码：设543211,cccccC，则00001c，01102c，11003c，00114c，10015c，2210110ccc，3311100ccc，4410011ccc，5511001ccc，?101032cc，?010142cc，?111152cc，?111143cc，?010153cc，?101054cc显然1C不满足线性码的第一个条件，则它不是一个线性码，就不可能是一个循环码。（2）首先证明2C是一个线性码：设43212,ccccC，则000001c，101102c，011013c，110114c，22110110ccc，33101101ccc，44111011ccc，43211011ccc，34201101ccc，24310110ccc名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 27 页，共 48 页 - - - - - - - - - 2C满足线性码的第一个条件，显然第二个条件也满足。2C中的最小距离3d，最小重量3w，即3wd，2C也满足第三个条件，可知2C是一个线性码。下面证明2C是循环的，101102c，经过循环移位之后得到的码字是010112c，这个码字不是2C中的码字，即2C不满足循环码的第二个条件。综上可知，2C不是一个循环码，但是它与一个循环码等价。（3）首先证明3C是一个线性码：设43213,ccccC，则000001c，101102c，011013c，110114c，22110110ccc，33101101ccc，44111011ccc，?1121132cc，?2112142cc，?1211243cc显然3C不满足线性码的第一个条件，则它不是一个线性码，就不可能是一个循环码。（4）首先证明4C是一个线性码：设3214,cccC，则00001c，11222c，22113c，2211122ccc，3312211ccc，1320000ccc4C满足线性码的第一个条件，显然第二个条件也满足。4C中的最小距离4d，最小重量4w，即4wd，4C也满足第三个条件，可知4C是一个线性码。下面证明4C是循环的，11222c，经过循环移位之后得到的码字是21122c，这个码字不是4C中的码字，即4C不满足循环码的第二个条件。综上可知，4C不是一个循环码，但是它与一个循环码等价。（5）长度为n的 q- 元重复码，假设3n，2q，则111111111，可知其不为线性码，也定不为循环码。4.2 为下列定义的多项式环构造加法和乘法表名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 28 页，共 48 页 - - - - - - - - - 2211GFxGFxF（x）(1) 定义在（2）上的F（x）(2) 定义在（3）上的解： (1) 首先判断得环的多项式的最高次数=1，环中有四个元素，分别为 0,1,x,x+1. 所得加法表如下：+ 0 1 x X+1 0 0 1 x X+1 1 1 0 1+x x x x X+1 0 1 X+1 X+1 x 1 0 乘法表如下：. 0 1 x X+1 0 0 0 0 0 1 0