循环码(7,3)码

《信息论与编码》课程设计报告-1-成都理工大学工程技术学院《信息论与编码》课程设计报告《信息论与编码》课程设计报告《信息论与编码》课程设计报告《信息论与编码》课程设计报告——循环码（7，3）码2007级信息工程指导教师：梁维海作者：钟玉东（1班）吴镇宏（2班）袁艳凤（1班）贾辉（2班）2009年6月18日《信息论与编码》课程设计报告-2-循环码（7，3）码（生成多项式）1)(234+++=xxxxg摘要：本报告详细给出了循环码的定义以及由生成多项式求解生成矩阵和系统生成矩阵的过程，并在Matlab环境下写出了循环码的编码器和解码器代码，实现了编码和译码功能。分析和讨论了此码发现错误、纠正错误的能力，并讨论了其与线性分组码、Hamming码等信道编码的区别与联系。关键字：循环码编码译码检错纠错Matlab信道编码：信道编码又称差错控制编码或纠错编码，它是提高信息传输可靠性的有效方法之一。一类一类信道编码是对传输信号的码型进行变换，使之更适合于信道特性或满足接收端对恢复信号的要求，从而减少信息的损失；另一类信道编码是在信息序列中人为的增加冗余位，使之具有相关特性，在接收端利用相关性进行检错或纠错，从而达到可靠通信的目的。1.1、循环码循环码是线性分组码中一个重要的分支。它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠随机错误，也能纠突发错误。循环码是目前研究得最成熟的一类码，并且有严密的代数理论基础，故有许多特殊的代数性质，这些性质有助于按所要求的纠错能《信息论与编码》课程设计报告-3-力系统地构造这类码，且易于实现，所以循环码受到人们的高度重视，在FEC系统中得到了广泛应用。1.1.1、循环码定义定义：一个线性分组码，若具有下列特性，则称为循环码。设码字（1.1.1）)(0121cccccnn⋅⋅⋅=−−若将码元左移一位，得（1.1.2）())(10121−−⋅⋅⋅=nnccccc也是一个码字。()1c由于（）线性分组码是维线性空间中的一个维子空kn,nnVk间，因此循环码是维线性空间中的一个维循环子空间。()kn,nnVk注意：循环码并非由一个码字的全部循环移位构成。1.1.2、循环码的特点循环码有两个数学特征：（1）线性分组码的封闭型；（2）循环性，即任一许用码组经过循环移位后所得到的码组仍为该许用码组集合中的一个码组。即若为一循环码组，则()0121aaaann⋅⋅⋅−−、、……还()1032−−−⋅⋅⋅nnnaaaa()2143−−−−⋅⋅⋅nnnnaaaa是许用码组。也就是说，不论是左移还是右移，也不论移多少位，仍《信息论与编码》课程设计报告-4-然是许用的循环码组。表1.1-1列出了某（7，3）循环码的全部码组。码组信息位监督位码组信息位监督位编号编号10000000510011102001110161010011301001117110100140111010811101006a5a4a3a2a1a0a6a5a4a3a2a1a0a表1.1-1（7，3）循环码组以3号码组（0100111）为例，左移循环一位变成5号码组（1001110），依次左移一位构成的状态图如图1.1-2所示。11101000100111011101000111011001110101001111010013号5号2号4号8号7号6号图1.1-1（7，3）循环码中的循环圈可见除全零码组外，不论循环右移或左移，移多少位，其结果均在该循环码组的集合中（全零码组自己构成独立的循环圈）。《信息论与编码》课程设计报告-5-1.1.3、码多项式为了用代数理论研究循环码，可将码组用多项式表示，循环码组中各码元分别为多项式的系数。长度为的码组n用码多项式表示则为()0121aaaaAnn⋅⋅⋅=−−（1.1.3）012211)(axaxaxaxAnnnn+⋅⋅⋅++=−−−−式中，的幂次是码元位置的标记。x若把一个码组左移位后的码组记为i，其码多项式为),,,,(121)(ininininiaaaaA−+−−−−−⋅⋅⋅=（1.1.4）ininninniniaxaxaxaxA−+−−−−−−−++⋅⋅⋅++=12211)()(可以根据按模运算得到，即)()(xAi)(xAxi1+nx（1.1.5）)1mod()()()(+≡niixxAxxA或（1.1.6）)()1)(()()(xAxxQxAxini++=式中，为除以的商式，而等于)(xQ)(xAxi1+nx)()(xAi)(xAAi⋅被除得之余式。1+nx以码组1011100为例，若将此码左移两位，则由式（1.1.6）可得)()1)(()()2(723462xAxxQxxxxx++=+++《信息论与编码》课程设计报告-6-易有其余式为，对应的码组为1110010，它与xxxxxAi+++=456)()(直接对码组进行循环左移的结果相同。码多项式之间可以进行代数运算，在二元码中遵循模2运算的规则。根据线性码的封闭性，任意两码字经模运算后仍为本码组中的码字。1.1.4、生成多项式（n,k）循环码码组集合中（全“0”码除外）幂次最低的多项式（n-k）阶称为生成多项式。它是能整除且常数项为1的)(xg1+nx多项式，具有唯一性。集合中其他码多项式，都是按模（）运1+nx算下的倍式，即可以由多项式产生循环码的全部码组。)(xg)(xg假设信息码多项式为，则对应的循环码多项式为)(xm（1.1.7）)()()(xgxmxA=式中，为次数不大于的多项式，共有个（）循环)(xm1−kk2kn,码组。考查表1.1-1，其中阶的多项式只有编号为2的码组4=−kn（0011101），所以表中所示（7，3）循环码组的生成多项式，并且该码组集合中的任何码多项式1)(234+++=xxxxg)(xA都可由信息位乘以生成多项式得到《信息论与编码》课程设计报告-7-（1.1.8）)1mod()()()(0121+++⋅⋅⋅++=−−nkkxxgmmmmxA式中，为信息码元。)(0121mmmmkk⋅⋅⋅−−对于（7，k）循环码，的因式分解为17+x（1.1.9）)1)(1)(1(12337+++++=+xxxxxx由该式可以构成表1.1-2所示几种（7，k）循环码。表1.1-2（7，3）循环码的生成多项式从表1.1-2中可以看出，即使n,k均已确定，也可能由多种生成多项式供选择，选用的多项式不同，产生出的循环码组也不同。1.1.5、生成矩阵根据各码组集合中生成多项式的唯一性，可以构造生成矩阵G。由于g（x）的次数为，则都是码多项式，kn−)(,),(),(1xgxxxgxgk−⋅⋅⋅(7,k)g(x)(7,1)(7,3)(7,4)(7,6))1)(1(323++++xxxx)1)(1()1)(1(323++++++xxxxxx或11323++++xxxx或1+x《信息论与编码》课程设计报告-8-而且线性无关，因此以这k各多项式对应的码组作为k行就能构成该循环码的生成矩阵，因此循环码的生成矩阵多项式可以写成（1.1.10）⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=−)()()()(1xgxgxxgxxGk⋮以生成多项式构造，相应的矩阵1)(234+++=xxxxg)(xG形式为（1.1.11）⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡+++++++++=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=1)()()()(23434524562xxxxxxxxxxxxgxgxxgxxG则G为g(x)升幂排列时的G为（1.1.12）⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=101110001011100010111G对式（1.1.12）作线性变换，整理成典型形式的生成矩阵（1.1.13）⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=101110011100100111001G若信息码元与式（1.1.13）相乘，得到的就是系统循环码。1.1.6、监督多项式与监督矩阵如前所述，在（n，k）循环码中，由于g(x)能除尽,因此1+nx可分解成g(x)和其他因式的乘积，记为《信息论与编码》课程设计报告-9-)()(1xhxgxn=+即可写成（1.1.14）)(1)(xgxxhn+=由于g(x)是常数项为1的r次多项式，所以h(x)必为k次多项式。称h(x)为监督多项式或一致校验多项式，与式（1.1.10）给出的G(x)相对应，监督矩阵多项式可表示为（1.1.15）⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=−)()()()(***1xhxxhxhxxHr⋮式中，式h(x)的逆多项式。)(*xh由式（1.1.14）可知，前述生成多项式的g(x)的一致校验多项式为，所以其一致校验矩阵（监督矩阵）为1)(23++=xxxh（1.1.16）⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=1011000010110000101100001011)(XH1.1.7、系统循环码循环码也可以构成为系统循环码。为方便系统码的构造，将消息多项式和码式都记为高位在前，即的消息多),,,,(0121mmmmmkk⋅⋅⋅=−−项式为m(x)，1110)(−−+++=kkxmxmmxm⋯《信息论与编码》课程设计报告-10-又设码式的高幂次部分等于m(x)，即)()()(111110xpxmxxcxcxcxccxcknnnknknknkn+⋅=++++++=−−−+−+−−−⋯⋯knrxp−=∂)(�其中p(x)称为校验位多项式，由于码式是生成式的倍式，所以))((mod0)()()()(xgxgxaxmxxpkn==+−))()(mod()(xgxmxxpr⋅−=因此循环码的系统码码式为（1.1.17）))]((mod)([)()(xgxmxxmxxcrr−=将循环码的系统码构造步骤总结为（1）多项式乘))(()(xmxxmxrr=（2）多项式求模（余式）)())())(mod((xpxgxmxr=（3）多项式减)()())((xcxpxmxr=−如果令为单项式，)(xm1+rx1,,1,0−=ki⋯rxpxpxgxaxiir∂+=+)(),()()(1�iriixxpxc++=)()(那么容易看到，对应的向量，是线性无关的，)(xciic1,,1,0−=ki⋯从而得到循环码系统码的生成矩阵为sG（1.1.18）⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=−−−−−−1000100011,11,10,11,111101,00100rkkkrrspppppppppG⋯⋯⋯⋯⋯⋯⋯故由式（1.1.18）可以求得前述（7，3）循环码系统码的生成矩阵为《信息论与编码》课程设计报告-11-⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=101110011100100111001sG1.1.8、循环码的编码1.利用生成多项式g(x)实现编码：如上所述，但循环码的生成多项式g(x)确定时，码就完全确定了。现在讨论生成多项式g(x)给定以后，如何实现循环码的编码问题。若已知g(x)=gn-kxn-k+gn-k-1xn-k-1+...g1x+g0并设信息元多项式m(x)=mk-1xk-1+mk-2xk-2+...m1x+m0要编码成系统循环码形式，即码字的最左边k位是信息元，其余n-k位是校验元，则要用xn-k乘以m(x)，再加上校验元多项式r(x),这样得到的码字多项式c(x)为c(x)=xn-km(x)+r(x)=mk-1xn-1+mk-2xn-2+...m0xn-k+rn-k-1xn-k-1+...r1x+r0其中r(x)=rn-k-1xn-k-1+...r1x+r0c(x)一定是g(x)的倍式，即有c(x)=xn-km(x)+r(x)=q(x)g(x)c(x)=xn-km(x)+r(x)=0.modg(x)注意到g(x)为n-k次多项式，而r(x)最多为n-k-1次多项式，必有r(x)=xn-km(x),modg(x)（1.1.19）即r(x)必是xn-km(x)除以g(x)的余式。式(1.1.19)指出了系统循环码的编码方法：首先将信息元多项式《信息论与编码》课程设计报告-12-m(x)乘以xn-k成为xn-km(x)，然后将xn-km(x)除以生成多项式g(x)得到余式r(x)，该余式就是校验元多项式，从而得到码字多项式c(x)=