通信原理习题-文档资料

1、1循环码的典型监督矩阵循环码的典型监督矩阵对于系统循环码而言，其监督矩阵必然是典型形式。即对于系统循环码而言，其监督矩阵必然是典型形式。即若已知典型生成矩阵若已知典型生成矩阵则典型监督矩阵则典型监督矩阵【注】【注】 可以通过矩阵的初等变换，把非典型形式的生成矩阵可以通过矩阵的初等变换，把非典型形式的生成矩阵和监督矩阵，变换成典型形式。变换时注意是和监督矩阵，变换成典型形式。变换时注意是模模2 2运算运算。2主要题型及解法主要题型及解法一、已经给出线性分组码的各个码字，要求一、已经给出线性分组码的各个码字，要求求出最小码距，并判断其检错、纠错能力。求出最小码距，并判断其检错、纠错能力。解法：根据

2、线性分组码的重要性质：线性分解法：根据线性分组码的重要性质：线性分组码的最小码距等于非零码的最小码重即组码的最小码距等于非零码的最小码重即可求出。而码重就是指码字中可求出。而码重就是指码字中1 1的个数。根的个数。根据据P331332的检纠错编码定理求解分组码的检纠错编码定理求解分组码的检错、纠错能力。的检错、纠错能力。3主要题型及解法主要题型及解法二、关于汉明码的题目。二、关于汉明码的题目。解法：解法：1、对于、对于(n,k)汉明码，根据汉明码的定义，可得：汉明码，根据汉明码的定义，可得：n=2r-1,其中其中r=n-k，为汉明码的监督位的数目。所，为汉明码的监督位的数目。所以以k=n-r=

3、2r-1-r。根据编码效率的公式。根据编码效率的公式 求求编码效率。编码效率。2、汉明码最大的特点是可以纠正、汉明码最大的特点是可以纠正1位错误。位错误。kn4主要题型及解法主要题型及解法三、给出非典型的生成矩阵三、给出非典型的生成矩阵G G或监督或监督( (校验校验) )矩矩阵阵H H，(1)(1)要求其对应的要求其对应的H H或或G G；(2)(2)求其所有系统码字；求其所有系统码字；(3)(3)判断其检错、纠错能力。判断其检错、纠错能力。解法解法: (1): (1)先将先将G G或或H H进行初等行进行初等行( (列列) )变换化成变换化成典型阵的形式，再根据典型阵的形式，再根据G G和

4、和H H的转换关系直的转换关系直接写出对应的接写出对应的H H或或G G。5主要题型及解法主要题型及解法(2) (2) 对于所有的线性分组码，都可以用对于所有的线性分组码，都可以用A=MGA=MG来求码字，码字的个数由来求码字，码字的个数由k k确定，个数为确定，个数为2 2k k。假定假定k=3,k=3,则则M=000M=000，001001，010010，011011，100100，101101，110110，111111，共，共8 8个，则用每个个，则用每个M M乘以乘以G G即可得到所有码字。即可得到所有码字。（注意模（注意模2 2加法和乘法的规律，巧妙地计算以加法和乘法的规律，巧妙地

5、计算以避免出错。）避免出错。）(3) (3) 根据线性分组码的最小码距等于其非零根据线性分组码的最小码距等于其非零码元的最小码重即可求的最小码距码元的最小码重即可求的最小码距d0d0，求，求出出d0d0即可判断其检错、纠错能力。即可判断其检错、纠错能力。6主要题型及解法主要题型及解法四、给出四、给出(n,k)(n,k)线性分组码的监督关系方程组线性分组码的监督关系方程组求其求其H H和和G G；判断某个码是否该分组码的码；判断某个码是否该分组码的码字。字。解法：首先根据监督方程写出对应的监督矩解法：首先根据监督方程写出对应的监督矩阵阵H,H,然后将其化成标准形式，即可求出对然后将其化成标准形式

6、，即可求出对应的应的G G；然后计算伴随式；然后计算伴随式S=BHS=BHT T，若，若S=0S=0，则，则B B是该是该(n,k)(n,k)码的码字，否则码的码字，否则B B不是该不是该(n,k)(n,k)码码的码字。的码字。7主要题型及解法主要题型及解法五、关于循环码的题目：五、关于循环码的题目：1 1、给出、给出(n,k)(n,k)循环码的生成多项式循环码的生成多项式g(x),g(x),求求其对应的生成矩阵其对应的生成矩阵G G和监督矩阵和监督矩阵H;H; 解法：根据解法：根据12()().().()()kkxgxxgxGxx gxgx8五、关于循环码的题目五、关于循环码的题目可求出可求

7、出G(x)G(x)，将其变化成典型矩阵，将其变化成典型矩阵G G，根据，根据G G可求出可求出H H。2 2、求某个信息码元组、求某个信息码元组M M对应的码字。对应的码字。解法解法1 1：因为循环码首先是线性分组码，故可根据：因为循环码首先是线性分组码，故可根据A=MGA=MG求其码字。求其码字。解法解法2 2：利用循环码的性质求解。：利用循环码的性质求解。根据根据M M即可写出即可写出M(x)M(x)，则用，则用x xn-kn-kM(x)/g(x)M(x)/g(x)即可得到即可得到r(x),r(x),则则A(x)= xA(x)= xn-kn-kM(x)+ r(x),M(x)+ r(x),即

8、得即得A A。9五、关于循环码的题目五、关于循环码的题目3 3、给出、给出(n,k)(n,k)循环码的生成多项式循环码的生成多项式g(x),g(x),再给出接再给出接受码组受码组B(x),B(x),要求判断码组在传输中是否出错。要求判断码组在传输中是否出错。解法：利用循环码解法：利用循环码g(x)g(x)的重要性质求解：的重要性质求解：g(x)g(x)为为r=n-kr=n-k次码多项式，其次数最低，且所有其它码多次码多项式，其次数最低，且所有其它码多项式项式A(x)A(x)都能被都能被g(x)g(x)整除。假定传输正确，则有整除。假定传输正确，则有B(x)=A(x)B(x)=A(x)，则必定有

9、，则必定有B(x)B(x)能被能被g(x)g(x)整除！整除！ 故判断方法如下：用长除法计算故判断方法如下：用长除法计算B(x)/g(x)B(x)/g(x)，若，若能整除则判断传输没有出错。否则肯定出错。能整除则判断传输没有出错。否则肯定出错。10第第1111章习题选讲章习题选讲例例1 1：已知某线性分组码的：已知某线性分组码的8 8个码字个码字为为:000000:000000、001110001110、010101010101、011011011011、100011100011、101101101101、110110110110、111000111000，求该，求该码的最小码距，并判断其纠检

10、错能力。码的最小码距，并判断其纠检错能力。解：由于线性分组码的封闭性和码距的定义解：由于线性分组码的封闭性和码距的定义可得知：线性分组码的最小码距等于非全可得知：线性分组码的最小码距等于非全零码的最小码重。故有：零码的最小码重。故有：11例例1 1故由观察法即可得出故由观察法即可得出由纠错编码定理可得其检纠错能力如下：由纠错编码定理可得其检纠错能力如下：(1)(1)能发现能发现2 2个错误码元个错误码元(2)(2)能纠正能纠正1 1个错误码元个错误码元0min( ,)min( ),0ijli jdd A AW A l0min(),03ldW Al0001211()dedtdteet 12例例2

11、. 2. 一个码长为一个码长为1515的汉明码，其监督码元的汉明码，其监督码元有多少位？编码效率是多少？用其作纠错有多少位？编码效率是多少？用其作纠错码能够纠正几位错误码能够纠正几位错误? ?解：由汉明码的定义有：解：由汉明码的定义有：n=2n=2r r-1=15,-1=15,故有故有r=4,r=4,所以编码效率所以编码效率 汉明码能纠正汉明码能纠正1 1位错误。位错误。 1541173.3%1515knrnn13例例3. 3. 已知已知(7,3)(7,3)线性分组码的生成矩阵为线性分组码的生成矩阵为求其监督矩阵，写出该求其监督矩阵，写出该(7,3)(7,3)码的系统码，并码的系统码，并判断其

12、纠检错能力。判断其纠检错能力。1 0 1 0 0 1 11 1 0 1 0 0 10 0 1 1 1 0 1G14解：先用初等行变换将生成矩阵化成典型解：先用初等行变换将生成矩阵化成典型阵，如下所示：阵，如下所示：3 7101001111010010011101100111011010010011101100111001001110011101kkrknGI Q151011000111010011000100110001Tr krr nHQI16K=3,K=3,所以共有所以共有2 23 3=8=8个系统码字，再根据个系统码字，再根据A=MGA=MG，即可分别求出各个码字。，即可分别求出各个码字

13、。举例如下：举例如下： 1 0 0 1 1 1 0101,101 0 1 0 0 1 1 10 0 1 1 1 0 11010011Mthen A=M G=17其它码字分别为：其它码字分别为：故由线性分组码的性质可得其最小码距故由线性分组码的性质可得其最小码距d0d0为为4 4，由检纠错编码定，由检纠错编码定理可得：能发现理可得：能发现3 3位错误；能纠正位错误；能纠正1 1位错误；能发现位错误；能发现2 2位错误的位错误的同时纠正同时纠正1 1位错误。位错误。0000000 0011101 0100111 01110101001110 1101001111010018例例4. 4. 已知某已

14、知某(7,4)(7,4)循环码的生成多项式循环码的生成多项式 g(x)=xg(x)=x3 3+x+1,+x+1,试求：试求：(1)(1)监督矩阵监督矩阵H H和生成矩阵和生成矩阵G;G;(2)(2)写出该循环码的所有码字，并求其最小码写出该循环码的所有码字，并求其最小码 距；距；(3)(3)求求M=1010M=1010时对应的码字；时对应的码字；(4)(4)若若B=1001101,B=1001101,判断其是否是该分组码的码字。判断其是否是该分组码的码字。19解解: (1)364325324231 0 1 1 0 0 0( )0 1 0 1 1 0 0( )( )0 0 1 0 1 1 0(

15、)0 0 0 1 0 1 1( )11 0 0 0 1 0 11 0 0 0 1 0 10 1 0 1 1 0 00 1 0 0 1 1 10 0 1 0 1 1 00 0 1 0 1 1 00 0 0 1 0 1 10 0 0 1 0 1 1xg xxxxxg xxxxGxxg xxxxg xxxG 1 1 1 0 1 0 00 1 1 1 0 1 01 1 0 1 0 0 1kk rk nTr k rr nIQHQ I 20(2)(2)方法一：利用方法一：利用A=MGA=MG求解，其中求解，其中M M共有共有1616种不同的组合，种不同的组合，求解除所有码字后，即可用观察法得出循求解除所有

16、码字后，即可用观察法得出循环码的最小码距为环码的最小码距为3 3。方法二：利用方法二：利用 求出求出A(x)A(x)，即可求出，即可求出A(x)A(x)对应的码字对应的码字A A 0000 0001 0010 . 1110 1111M ( )( )( )n kA xM x xr x21(3)方法一：直接利用第方法一：直接利用第(2)小题的结果即可。小题的结果即可。 方法二：方法二：1 0 0 0 1 0 10 1 0 0 1 1 110101 0 1 0 0 1 10 0 1 0 1 1 00 0 0 1 0 1 1A M G22方法三：方法三：3336464333641010( )( )()( )11( )11( )1( )( )( )11 0 1 0 0 1 1