信息论第六章答案(共18页).doc

精选优质文档-倾情为你奉上6.1 奇校验码码字是c=(m0,m1,mk-1,p)，其中奇校验位p满足方程m0+m1+, +mk-1+p =1 (mod 2)证明奇校验码的检错能力与偶校验码的检错能力相同，但奇其校验码不是线性分组码。证：偶校验码的编码方程为m0+m1+, +mk-1+p =0 (mod 2)当差错图案e中有奇数个1时，通过偶校验方程可以检测出发生错误，因此检测概率：奇校验码的编码方程为m0+m1+, +mk-1+p =1 (mod 2)当差错图案e中有偶数个1时，通过偶校验方程可以检测出发生错误，因此检测概率：由线性分组码的性质可知，码组中必有一个全零码字。而奇校验码中没有全零码，如果有的话必是错码，所以奇校验码不是线性分组码。6.2 一个 (6, 2) 线性分组码的一致校验矩阵为（1） 求hi (i=1，2，3，4)使该码的最小码距dmin3。（2） 求该码的系统码生成矩阵Gs及其所有4个码字。解：（1）对H做行、列初等变换：后五列已是满足三列无关，四列相关，可使dmin=4。因此，dmin=3，必须包含第一列，而剩余5列取2列有10种组合： 1+2+3，1+2+4，1+2+5，1+2+6，1+3+4，1+3+5，1+3+6, 1+4+5, 1+4+6，1+5+6三列相关的4种：h值分别可以为0110T；1111T；1101T；1001T； dmin=4，因此，必须包含第一列，而剩余5列取3列有10种组合： 1+2+3+4，1+2+3+5，1+2+3+6，1+2+4+5，1+2+4+6，1+2+5+6，1+3+4+5, 1+3+4+6, 1+3+5+6，1+4+5+6四列相关的1种：（1+2+3+4，1+4+5+6）的h值一样0111T； dmin=5，必须包含第一列，剩余5列取4列有5种组合：1+2+3+4+5，1+2+3+4+6，1+2+3+5+6，1+2+4+5+6，1+3+4+5+6，五列相关的1种：1+2+3+5+6的h值 0000T，但是全零列不能校验任何位的差错，故不能构成校验矩阵。 dmin=6，必须包含第一列，剩余5列取5列有1种组合：1+2+3+4+5+6，没有6列相关的h(2) 将H行、列初等变换至：（此小题的答案有多种，视选取的hi不同而不同。）6.3 一个纠错码消息与码字的对应关系如下：（00）（00000），（01）（00111），（10）（11110），（11）（11001）（1）证明该码是线性分组码。（2）求该码的码长、编码效率和最小码距。（3）求该码的生成矩阵和一致校验矩阵。（4）构造该码BSC上的标准阵列。（5）若消息在转移概率p=10-3的BSC上等概率发送，求用标准阵列译码后的码字差错概率和消息比特差错概率。（6）若在转移概率p=10-3的BSC上消息0发送的概率为0.8，消息1发送的概率为0.2，求用标准阵列译码后的码字差错概率和消息比特差错概率。（7）若传送消息0出错的概率为10-4，传送消息1出错的概率为10-2，消息等概发送，求用标准阵列译码后的码字差错概率和消息比特差错概率。解：（1）该码组等长，由K=2，得n=2k=4；该码组中有全零码；消息（01）和（10）的和（11）对应得码字（11001）是（01）对应的码字（00111）与消息（10）对应的码字（11110）的和，满足线性关系；最小非零码重量等于最小码距为3；所以该码组是线性分组码。（2）码长n=5，效率=k/n=2/5=40%，最小码距为3，因为最小码重量为3。（3）由于G的每行是线性分组码的一个码字，所以，由（10）和（01）消息对应得码字构成生成矩阵的两行：本小题视选取得码字与G的初等变换结果不同而有不同的系统码生成矩阵和一致校验矩阵。但是码字的重量分布不变。（4）伴随式和错误图案的关系：伴随式有2n-k8种组合，差错图案中代表无差错的有1种，代表1个差错的图案有5种，代表两个差错的图案有种10。只需挑选其中对应最轻差错图案的两个。先将ej=(00000)、(10000)、(01000)、(00100)、(00010)、(00001)代入上面的关系式，得对应的Sj分别是(000)、(111)、(101)、(100)、(010)、(001)。剩下的伴随式中，(011)所对应的差错图案是2k个即(00011)、(10100)、(01101)、(11010),其中(00011)和(10100)并列重量最轻，任选其中一个如(00011)。同样可得伴随式(101)所对应的最轻差错图案之一是(00101)。其它三个差错图案为（10010）、（01011）、（11100）。标准阵列：SC0+eC1C2C30000000000111111101100111110000101110111001001110010000111110110100011000010000011110101110101000010001011110011011001000010011011111110000110001100100111011101010100101000101101111100另外两种2重量的差错图案和伴随式：0111010010011010100110110110010101010110001011（5）按（4）的标准阵列译码，记Ac是标准阵列中码字c对应的列，E是包括无错图案和全部可纠正差错图案的集合，那么码字差错概率为：记消息比特差错概率为Pb(e)，消息向量差错概率为PB(e)，注意到该码是非系统码以及消息向量长为2，则应有：（6）码字差错概率计算中消息比特差错概率：（7）码字差错概率计算中消息比特差错概率：码字差错概率和消息比特差错概率相等。6.6 一个通信系统消息比特速率为10kbit/s，信道为衰落信道，在衰落时间（最大为2ms）内可以认为完全发生数据比特传输错误。（1）求衰落导致的突发错误的突发比特长度。（2）若采用汉明码和交织编码方法纠正突发差错，求汉明码的码长和交织深度。（3）若用分组码交织来纠正突发差错并限定交织深度不大于256，求合适的码长和最小码距。（4）若用BCH码交织来纠正突发错误并限定交织深度不大于256，求合适的码长和BCH码生成多项式。解：（1）对于（n，k）分组码，消息长度为k的分组编码长度为n。消息比特率为10kbit/s的(n，k)编码后速率为10n/k bit/s。若在衰落时间（最大为2ms）内认为完全发生数据比特传输错误，则衰落导致差错的突发比特长度为b=2×10-3×10n/k×103=20n/k 比特（2）汉明码是一种d=3的完备码，其纠错能力是t=1比特。因此，交织深度不小于D才能纠正Dt个连续差错比特，Db/t=20n/k 比特。如果是（7，4）汉明码，则D20×7/4=35 比特。编码后速率为10×7/4=17.5Kbit/s。延时为2nD/（10n/k）=2kD/10=4n=28（ms）如果是（15，11）汉明码，则D20×15/1127.27 =28比特。编码后速率为13.63Kbit/s。延时为60（ms）如果是（31，26）汉明码，则D20×31/2623.85 =24比特。编码后速率为11.92Kbit/s。延时为124（ms）如果是（63，57）汉明码，则D20×63/5722.1 =23比特。编码后速率为11.05Kbit/s。延时为252（ms）如果是（127，120）汉明码，则D20×127/12021.17 =22比特。编码后速率为10.58Kbit/s。延时为508（ms）如果是（255，247）汉明码，则D20×255/24720.72 =21比特。编码后速率为10.32Kbit/s。延时为1020（ms）从延时最小的角度取（7，4）汉明码最好，存储容量nD=245bit最小。此时的编码后速率最高，交织深度最大，码率R=4/7最低。（3）由b=20n/k，bDt256×t256×(d-1)/2，及码限约束关系，如Singleton限dn-k+1设计。如果纠错数t=1，则d=3或4。由：如果k=3，可取6n57，因此（7，4）Hamming码的缩短码（6，3）、（7，3）Hamming等均可，这里nk+d+1的约束显然太宽，这是由Singleton限太宽松引起的，使用更紧的约束，如Hamming限、Plotkin限使n大于由s限确定的下限。如果还要求是好码，则n的上限由Varshamov-Gilbert限来控制。于是n需满足：（3） BCH码的dmin2t+1，n-kmt，n=2m-1假设纠一位插错，t=1，dmin3，由Singleton限dn-k+1设计，3m+1，m2。由。因此，t=1时，任何m2的BCH码均可。t2时，D256的分组交织码性能更好。m=3，4，5，6，7的BCH码生成多项式见表6.3.4（p.202），如：m=3, t=1, g(x)=x3+x+1m=4, t=1, g(x)=x4+x+1m=4, t=2, g(x)=x8+x7+x6+x4+1m=4, t=3, g(x)= x10+x8+x5+x4+x2+x+16.7 若循环码以g(x)=1+x为生成多项式，则（1）证明g(x)可以构成任意长度的循环码。（2）求该码的一致校验多项式。（3）证明该码等价为一个偶校验码。解：（1）g(x)是（n，k）循环码的生成多项式，当且仅当g(x)是xn-1的r=n-k次因式，这里r=1，所以n=k+1，如果信息位长k任意，则(k+1,k)码的升幂排列表示的码式：（2）由g(x)h(x)=xn-1= xk+1-1，在二进制运算中减一与加一运算一致。所以，（3）设信息多项式为降幂排列表示：所以与偶校验码等价。也可以用生成矩阵来证明（升幂或降幂排列表示均可）：G的最后一列为全“1”，说明校验位是所有信息位的模2和结果。所有码元和是零，即是偶校验。6.8 已知循环码生成多项式为g(x)=1+x+x4,（1）求该码的最小码长n，相应的一致校验多项式h(x)和最小码距d。（2）求该码的生成矩阵、一致校验矩阵、系统码生成矩阵。（3）画出该码的k级系统码电路图，给出编码电路的编码过程。（4）若消息为m(x)=x+x3+x4，分别由编码电路和代数计算求其相应的码式c(x)。（5）画出该码的伴随式计算电路图，给出伴随式计算电路的工作过程。（6）若错误图样为e(x)=x2+x9，分别由伴随式计算电路和代数计算求其相应的伴随式s(x)。（7）若消息长度大于n-4，由（2）小题给出的编码电路产生的输出v(x)是什么？v(x)仍可以用（5）小题给出的伴随式计算电路判断是否有传输差错么？解：（1）由和这是一个（15，11）循环汉明码，m=4, n=2m-1=15, k=2m-m-1, 最小码距d=3（2）另外，如果G是按降幂排列的，则H按升幂排列。由H矩阵的行初等变换，可得系统码形式的一致校验矩阵Hs。（第3行加到第4行，第2行加到第3行，第1行加到第2行）由Hs变换至Gs（3）k级系统码电路图如下：工作过程：时钟t门控信号G1/G2输入m(x)输出 C(x)T0T101/0m(x)X4 m(x)T11T140/10X4 m(x)modg(x)（4） 当m(x)=x+x3+x4，即11位比特（）时，C(x)= X4 m(x)+ X4 m(x) mod g(x)C(x)= x3+x5+x7+x8，即（0000）。由K级编码器获得码字的过程：Tm(x)D10D9D8D7D6D5D4D3D2D1D0C(x)G1/G2000 0 0 0 0 0 0 0 0 0 001/0100 0 0 0 0 0 0 0 0 0 001/0200 0 0 0 0 0 0 0 0 0 001/0300 0 0 0 0 0 0 0 0 0 001/0400 0 0 0 0 0 0 0 0 0 001/0500 0 0 0 0 0 0 0 0 0 001/0610 0 0 0 0 0 0 0 0 0 0 11/0711 0 0 0 0 0 0 0 0 0 011/0801 1 0 0 0 0 0 0 0 0 001/0910 1 1 0 0 0 0 0 0 0 011/01001 0 1 1 0 0 0 0 0 0 0 01/01100 1 0 1 1 0 0 0 0 0 0 10/11201 0 1 0 1 1 0 0 0 0 000/11300 1 0 1 0 1 1 0 0 0 000/11400 0 1 0 1 0 1 1 0 0 000/1上述获得的码式不是系统码形式。系统码形式的码式生成方法如下：由r级系统码编码器获得的码式为：由r级编码器获得码字的过程：Tm(x)D0D1D2D3C(x)G1/G2000 0 0 0 01/0100 0 0 001/0200 0 0 0 01/0300 0 0 0 01/0400 0 0 0 01/0500 0 0 001/0610 0 0 0 11/0711 1 0 011/0801 0 1 0 01/0910 1 0 1 11/01000 0 1 0 01/01100 0 0 1 10/11200 0 0 0 00/11300 0 0 0 00/11400 0 0 0 00/1（5）循环码伴随式的计算电路：循环码伴随式的计算过程Tr(x)D0D1D2D3000 0 0 0 0100 0 0 00200 0 0 0 0300 0 0 0 0400 0 0 0 0500 0 0 00610 0 0 0 0711 0 0 01801 1 0 0 0910 1 1 001001 0 1 1 11111 0 0 1 01200 0 0 0 01300 0 0 0 01400 0 0 00150 0 0 0 0（6），S=0111循环码伴随式计算e=0000过程Tr(x)D0D1D2D3000 0 0 0 0100 0 0 00200 0 0 0 0300 0 0 0 0400 0 0 0 0510 0 0 00601 0 0 0 1700 1 0 01800 0 1 01900 0 0 1 11001 1 0 0 01100 1 1 0 01210 0 1 1 01300 1 0 1 01401 1 1 01150 1 1 1 16.9 已知（8，5）线性分组码的生成矩阵为：（1） 证明该码为循环码。（2） 求该码的生成多项式g(x)、一致校验多项式h(x)和最小码距d。解：（1）由G的第五行构成的码多项式：由G的第四行构成的码多项式：由G的第三行构成的码多项式：由G的第二行构成的码多项式：由G的第一行构成的码多项式：从上述G构成的码字C(x)可知，它们是g(x)的被式，g(x)是唯一的，g(x)的零次项是1，g(x)的最高次幂r=n-k=8-5=3。因此，由g(x)的xi产生的被式是循环码。也可以从生成矩阵G的行初等变换，得到循环码形式的生成矩阵：（2）H中第一和第五列相关，所以最小码距为2。6.11 一通信系统信道为转移概率p=10-3的BSC。求下列各码的重量分布Ai，i=0,1,2,n和不可检差错概率。（1）（7，4）汉明码（2）（7，3）最大长度码（simplex码）（3）（8，4）扩展汉明码（4）（8，1）重复码（5）（8，7）偶校验码解：（1）（7，4）汉明码的信息位长4，有16种消息。其生成多项式g(x)=1+x+x3, C(x)=m(x)g(x)码多项式重量码多项式重量C0(x)=0w0=0C8(x)=x3·g(x)= x3+x4+x6w8=3C1(x)=1·g(x)= 1+x+x3w1=3C9(x)=(1+ x3)·g(x)= 1+x+x4+x6w9=4C2(x)=x·g(x)= x+x2+x4w2=3C10(x)=(x+ x3)·g(x)= x+x2+x3+x6w10=4C3(x)=(1+x)·g(x)= 1+x2+x3+x4w3=4C11(x)=(1+x+ x3)·g(x)= 1+x2+x6w11=3C4(x)=x2·g(x)= x2+x3+x5w4=3C12(x)=( x2+ x3)·g(x)= x2+x4+x5+x6W12=4C5(x)=(1+x2)·g(x)= 1+x+x2+x5w5=4C13(x)=(1+ x2+ x3)·g(x)=1+ x+x2+x3+x4+x5+x6W13=7C6(x)=(x+x2)·g(x)= x+x3+x4+x5w6=4C14(x)=(x+ x2+ x3)·g(x)= 1+x3+x5+x6W14=4C7(x)=(1+x+x2)·g(x)= 1+x4+x5w7=3C10(x)=(1+x+ x2+ x3)·g(x)= x+x5+x6w15=3（7，4）汉明码的重量分布1,0,0,7,7,0,0,1，dmin=3，不可检差错概率：另一种做法是用生成矩阵，生成16个码字，分别计算每个码字中1的数目。（2）（7，3）汉明码的信息位长3，有8种消息。其生成多项式g(x)=（1+x）(1+x2+x3)=1+x+x2+x4, C(x)=m(x)g(x)码多项式重量码多项式重量C0(x)=0w0=0C4(x)=x2·g(x)= x2+x3+x4+x6w4=4C1(x)=1·g(x)= 1+x+x2+x4w1=4C5(x)=(1+x2)·g(x)= 1+x+x3+x6w5=4C2(x)=x·g(x)= x+x2+x3+x5w2=4C6(x)=(x+x2)·g(x)= x+x4+x5+x6W6=4C3(x)=(1+x)·g(x)= 1+x3+x4+x5w3=4C7(x)=(1+x+x2)·g(x)= 1+x2+x5+x6w7=4（7，3）汉明码的重量分布1,0,0,0,7,0,0,0，dmin=4，不可检差错概率：另一种通过McWilliams恒等式计算（7，3）码的重量分布：dmin=4，不可检差错概率：(3) （8，4）扩展汉明码是在（7，4）汉明码的基础上加一位全校验位，即原来码字中1的个数为偶数，则添加校验位0；原来码字中1的个数为奇数，则添加校验位1。扩展后的码子满足偶校验规则。因此，原来（7，4）码的奇数重量码将加一，偶数重量码的重量不变。（8，4）扩展汉明码的重量分布1,0,0,0,14,0,0,0,1，dmin=4，不可检差错概率：（4）（8，1）重复码(),()，码重量分布1,0,0,0,0,0,0,0,1, dmin=8，不可检差错概率：（5）（8，7）偶校验码，有128种消息。作偶校验，即码字中1的个数为偶数，则添加校验位0；原来码字中1的个数为奇数，则添加校验位1。第一种方法是分析码子中信息位中“1”的个数与校验位中“1”的个数关系。7位信息全为零，第8比特为0，零重量码字数1个。7位信息中只有1个“1”，第8比特为1；7位信息中有2个“1”，第8比特为0，则2重量码字数：。7位信息中只有3个“1”，第8比特为1；7位信息中有4个“1”，第8比特为0，则4重量码字数：。7位信息中只有5个“1”，第8比特为1；7位信息中有6个“1”，第8比特为0，则6重量码字数：。7位信息全为“1”，第8比特为10，8零重量码字数1个。所以，（8，7）偶校验码的重量分布1，0，28，0，70，0，28，0，1第二种方法是将信息位从0至127分别计算第8位偶检验位，然后对每个码字计算重量。统计码重量分布。码字重量码字重量码字重量码字重量,00,12,12,02,12,02,02,14,12,02,02,14,02,14,14,04,12,02,02,14,02,14,14,04,02,14,14,04,14,04,04,16,12,02,02,14,02,14,14,04,02,14,14,04,14,04,04,16,02,14,14,04,14,04,04,16,14,14,04,16,04,16,16,06,12,02,02,14,02,14,14,04,02,14,14,04,14,04,04,16,02,14,14,04,14,04,04,16,14,04,04,16,04,16,16,06,02,14,14,04,14,04,04,16,14,04,04,16,04,16,16,06,14,04,04,16,04,16,16,06,04,16,16,06,16,06,06,18（8，7）偶校验码码重量分布1,0,28,0,70,0,28,0,1, dmin=2，不可检差错概率：第三种方法是采用McWILLIAMS恒等式。因为，（8，1）重复码是（8，7）偶校验码的对偶码。专心-专注-专业