通信原理习题文档资料.ppt

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

解法：解法：1、对于、对于(n,k)汉明码，根据汉明码的定义，可得：汉明码，根据汉明码的定义，可得：n=2r-1,其中其中r=n-k，为汉明码的监督位的数目所，为汉明码的监督位的数目所以以k=n-r=2r-1-r根据编码效率的公式根据编码效率的公式 求求编码效率编码效率2、汉明码最大的特点是可以纠正、汉明码最大的特点是可以纠正1位错误3主要题型及解法主要题型及解法三、给出非典型的生成矩阵三、给出非典型的生成矩阵G G或监督或监督( (校验校验) )矩矩阵阵H H，，(1)(1)要求其对应的要求其对应的H H或或G G；；(2)(2)求其所有系统码字；求其所有系统码字；(3)(3)判断其检错、纠错能力判断其检错、纠错能力解法解法: (1): (1)先将先将G G或或H H进行初等行进行初等行( (列列) )变换化成变换化成典型阵的形式，再根据典型阵的形式，再根据G G和和H H的转换关系直的转换关系直接写出对应的接写出对应的H H或或G G4主要题型及解法主要题型及解法(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加法和乘法的规律，巧妙地计算以加法和乘法的规律，巧妙地计算以避免出错避免出错3) (3) 根据线性分组码的最小码距等于其非零根据线性分组码的最小码距等于其非零码元的最小码重即可求的最小码距码元的最小码重即可求的最小码距d0d0，求，求出出d0d0即可判断其检错、纠错能力即可判断其检错、纠错能力5主要题型及解法主要题型及解法四、给出四、给出(n,k)(n,k)线性分组码的监督关系方程组线性分组码的监督关系方程组求其求其H H和和G G；判断某个码是否该分组码的码；判断某个码是否该分组码的码字解法：首先根据监督方程写出对应的监督矩解法：首先根据监督方程写出对应的监督矩阵阵H,H,然后将其化成标准形式，即可求出对然后将其化成标准形式，即可求出对应的应的G G；然后计算伴随式；然后计算伴随式S=BHS=BHT T，若，若S=0S=0，则，则B B是该是该(n,k)(n,k)码的码字，否则码的码字，否则B B不是该不是该(n,k)(n,k)码码的码字。

的码字6主要题型及解法主要题型及解法五、关于循环码的题目：五、关于循环码的题目：1 1、给出、给出(n,k)(n,k)循环码的生成多项式循环码的生成多项式g(x),g(x),求求其对应的生成矩阵其对应的生成矩阵G G和监督矩阵和监督矩阵H;H; 解法：根据解法：根据7五、关于循环码的题目五、关于循环码的题目可求出可求出G(x)G(x)，将其变化成典型矩阵，将其变化成典型矩阵G G，根据，根据G G可求出可求出H H2 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),即得即得A A8五、关于循环码的题目五、关于循环码的题目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)，则必定有，则必定有B(x)B(x)能被能被g(x)g(x)整除！整除！ 故判断方法如下：用长除法计算故判断方法如下：用长除法计算B(x)/g(x)B(x)/g(x)，若，若能整除则判断传输没有出错否则肯定出错能整除则判断传输没有出错否则肯定出错9第第1111章习题选讲章习题选讲例例1 1：已知某线性分组码的：已知某线性分组码的8 8个码字为个码字为:000000:000000、、001110001110、、010101010101、、011011011011、、100011100011、、101101101101、、110110110110、、111000111000，求该，求该码的最小码距，并判断其纠检错能力码的最小码距，并判断其纠检错能力。

解：由于线性分组码的封闭性和码距的定义解：由于线性分组码的封闭性和码距的定义可得知：线性分组码的最小码距等于非全可得知：线性分组码的最小码距等于非全零码的最小码重故有：零码的最小码重故有：10例例1 1故由观察法即可得出故由观察法即可得出由纠错编码定理可得其检纠错能力如下：由纠错编码定理可得其检纠错能力如下：(1)(1)能发现能发现2 2个错误码元个错误码元(2)(2)能纠正能纠正1 1个错误码元个错误码元11例例2. 2. 一个码长为一个码长为1515的汉明码，其监督码元的汉明码，其监督码元有多少位？编码效率是多少？用其作纠错有多少位？编码效率是多少？用其作纠错码能够纠正几位错误码能够纠正几位错误? ?解：由汉明码的定义有：解：由汉明码的定义有：n=2n=2r r-1=15,-1=15,故有故有r=4,r=4,所以编码效率所以编码效率 汉明码能纠正汉明码能纠正1 1位错误 12例例3. 3. 已知已知(7,3)(7,3)线性分组码的生成矩阵为线性分组码的生成矩阵为求其监督矩阵，写出该求其监督矩阵，写出该(7,3)(7,3)码的系统码，并码的系统码，并判断其纠检错能力。

判断其纠检错能力13解：先用初等行变换将生成矩阵化成典型解：先用初等行变换将生成矩阵化成典型阵，如下所示：阵，如下所示：1415K=3,K=3,所以共有所以共有2 23 3=8=8个系统码字，再根据个系统码字，再根据A=MGA=MG，即可分别求出各个码字即可分别求出各个码字举例如下：举例如下：16其它码字分别为：其它码字分别为：故由线性分组码的性质可得其最小码距故由线性分组码的性质可得其最小码距d0d0为为4 4，由检纠错编码定，由检纠错编码定理可得：能发现理可得：能发现3 3位错误；能纠正位错误；能纠正1 1位错误；能发现位错误；能发现2 2位错误的位错误的同时纠正同时纠正1 1位错误17例例4. 4. 已知某已知某(7,4)(7,4)循环码的生成多项式循环码的生成多项式 g(x)=x g(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,判断其是否是该分组码的码字。

判断其是否是该分组码的码字18解解: (1)19(2)(2)方法一：利用方法一：利用A=MGA=MG求解，其中求解，其中M M共有共有1616种不同的组合，种不同的组合，求解除所有码字后，即可用观察法得出循求解除所有码字后，即可用观察法得出循环码的最小码距为环码的最小码距为3 3方法二：利用方法二：利用 求出求出A(x)A(x)，即可求出，即可求出A(x)A(x)对应的码字对应的码字A A20(3)方法一：直接利用第方法一：直接利用第(2)小题的结果即可小题的结果即可 方法二：方法二：21方法三：方法三：22(4)(4)因为循环码首先是一种线性分组码，所因为循环码首先是一种线性分组码，所以如果已知以如果已知H H，则可以根据，则可以根据S ST T或或S S是否为是否为0 0来判断，若为来判断，若为0 0则判定则判定B B是该分组码的码是该分组码的码字。