循环码（7，3）码（生成多项式1)(234+++=x x xx g ）摘要：本报告详细给出了循环码的定义以及由生成多项式求解生成矩阵和系统生成矩阵的过程，并在Matlab 环境下写出了循环码的编码器和解码器代码，实现了编码和译码功能。

分析和讨论了 此码发现错误、纠正错误的能力，并讨论了其与线性分组码、Hamming 码等信道编码的区别与联系。

关键字：循环码 编码 译码 检错 纠错 Matlab信道编码：信道编码又称差错控制编码或纠错编码，它是提高信息传输可靠性的有效方法之一。

一类一类信道编码是对传输信号的码型进行变换，使之更适合于信道特性或满足接收端对恢复信号的要求，从而减少信息的损失；另一类信道编码是在信息序列中人为的增加冗余位，使之具有相关特性，在接收端利用相关性进行检错或纠错，从而达到可靠通信的目的。

1.1、循环码循环码是线性分组码中一个重要的分支。

它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠随机错误，也能纠突发错误。

循环码是目前研究得最成熟的一类码，并且有严密的代数理论基础，故有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现，所以循环码受到人们的高度重视，在FEC 系统中得到了广泛应用。

1.1.1、循环码定义定义：一个线性分组码，若具有下列特性，则称为循环码。

设码字 )(0121c c c c c n n ⋅⋅⋅=-- （1.1.1） 若将码元左移一位，得())(10121--⋅⋅⋅=n n c c c c c （1.1.2）()1c也是一个码字。

由于（k n ,）线性分组码是n 维线性空间n V 中的一个k 维子空间，因此()k n ,循环码是n 维线性空间n V 中的一个k 维循环子空间。

注意：循环码并非由一个码字的全部循环移位构成。

1.1.2、循环码的特点循环码有两个数学特征： （1）线性分组码的封闭型；（2）循环性，即任一许用码组经过循环移位后所得到的码组仍为该许用码组集合中的一个码组。

即若()0121a a a a n n ⋅⋅⋅--为一循环码组，则()1032---⋅⋅⋅n n n a a a a 、()2143----⋅⋅⋅n n n n a a a a 、……还是许用码组。

也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。

表1.1-1列出了某（7，3）循环码的全部码组。

码组 信息位监督位码组信息位监督位编号 编号10000000510011102001110161010011301001117110100141111811116a 5a 4a 3a 2a 1a 0a 6a 5a 4a 3a 2a 1a 0a表1.1-1（7，3）循环码组 以3号码组（0100111）为例，左移循环一位变成5号码组（1001110），依次左移一位构成的状态图如图1.1-2所示。

11101000100111011101000111011001110101001111010013号 5号2号4号8号 7号 6号图1.1-1（7，3）循环码中的循环圈可见除全零码组外，不论循环右移或左移，移多少位，其结果均在该循环码组的集合中（全零码组自己构成独立的循环圈）。

1.1.3、码多项式为了用代数理论研究循环码，可将码组用多项式表示，循环码组中各码元分别为多项式的系数。

长度为n的码组()0121a a a a A n n ⋅⋅⋅=--用码多项式表示则为012211)(a x a x a x a x A n n n n +⋅⋅⋅++=---- （1.1.3）式中，x 的幂次是码元位置的标记。

若把一个码组左移i位后的码组记为),,,,(121)(i n i n i n i n i a a a a A -+-----⋅⋅⋅=，其码多项式为i n i n n i n n i n i a x a x a x a x A -+-------++⋅⋅⋅++=12211)()( （1.1.4） )()(x A i 可以根据)(x A x i 按模1+n x 运算得到，即 )1mod()()()(+≡ni i x x A x x A （1.1.5）或)()1)(()()(x A x x Q x A x i n i ++= （1.1.6）式中，)(x Q 为)(x A x i 除以1+n x 的商式，而)()(x A i 等于)(x A A i⋅被1+n x 除得之余式。

以码组1011100为例，若将此码左移两位，则由式（1.1.6）可得 )()1)(()()2(723462x A x x Q x x x x x ++=+++易有其余式为x x x x x A i +++=456)()( ，对应的码组为1110010，它与直接对码组进行循环左移的结果相同。

码多项式之间可以进行代数运算，在二元码中遵循模2运算的规则。

根据线性码的封闭性，任意两码字经模运算后仍为本码组中的码字。

1.1.4、生成多项式（n,k ）循环码码组集合中（全“0”码除外）幂次最低的多项式（n-k ）阶称为生成多项式)(x g 。

它是能整除1+nx 且常数项为1的多项式，具有唯一性。

集合中其他码多项式，都是按模（1+nx ）运算下)(x g 的倍式，即可以由多项式)(x g 产生循环码的全部码组。

假设信息码多项式为)(x m ，则对应的循环码多项式为)()()(x g x m x A = （1.1.7） 式中，)(x m 为次数不大于1-k 的多项式，共有k2个（k n ,）循环码组。

考查表1.1-1，其中4=-k n 阶的多项式只有编号为2的码组（0011101），所以表中所示（7，3）循环码组的生成多项式1)(234+++=x x x x g ，并且该码组集合中的任何码多项式)(x A 都可由信息位乘以生成多项式得到)1mod()()()(0121+++⋅⋅⋅++=--nk k x x g m m m m x A （1.1.8）式中，)(0121m m m m k k ⋅⋅⋅--为信息码元。

对于（7，k ）循环码，17+x 的因式分解为)1)(1)(1(12337+++++=+x x x x x x （1.1.9） 由该式可以构成表1.1-2所示几种（7，k ）循环码。

表1.1-2 （7，3）循环码的生成多项式从表1.1-2中可以看出，即使n,k 均已确定，也可能由多种生成多项式供选择，选用的多项式不同，产生出的循环码组也不同。

1.1.5、生成矩阵根据各码组集合中生成多项式的唯一性，可以构造生成矩阵G 。

由于g （x ）的次数为k n -，则)(,),(),(1x g x x xg x g k -⋅⋅⋅都是码多项式，(7,k) g(x)(7,1) (7,3) (7,4) (7,6))1)(1(323++++x x x x )1)(1()1)(1(323++++++x x x x x x或11323++++x x x x 或1+x而且线性无关，因此以这k 各多项式对应的码组作为k 行就能构成该循环码的生成矩阵，因此循环码的生成矩阵多项式可以写成⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=-)()()()(1x g x g x x g x x G k （1.1.10） 以生成多项式1)(234+++=x x x x g 构造)(x G ，相应的矩阵形式为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡+++++++++=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=1)()()()(23434524562x x x x x x x x x x x x g x g x x g x x G （1.1.11）则G 为g(x)升幂排列时的G 为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=101110001011100010111G （1.1.12）对式（1.1.12）作线性变换，整理成典型形式的生成矩阵⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=101110011100100111001G （1.1.13）若信息码元与式（1.1.13）相乘，得到的就是系统循环码。

1.1.6、监督多项式与监督矩阵如前所述，在（n ，k ）循环码中，由于g(x)能除尽,因此1+nx 可分解成g(x)和其他因式的乘积，记为)()(1x h x g x n=+即可写成)(1)(x g x x h n +=（1.1.14） 由于g(x)是常数项为1的r 次多项式，所以h(x)必为k 次多项式。

称h(x)为监督多项式或一致校验多项式，与式（1.1.10）给出的G(x)相对应，监督矩阵多项式可表示为⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎣⎡=-)()()()(***1x h x xh x h x x H r （1.1.15） 式中，)(*x h 式h(x)的逆多项式。

由式（1.1.14）可知，前述生成多项式的g(x)的一致校验多项式为1)(23++=x x x h ，所以其一致校验矩阵（监督矩阵）为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=1011000010110000101100001011)(X H （1.1.16）1.1.7、系统循环码循环码也可以构成为系统循环码。

为方便系统码的构造，将消息多项式和码式都记为高位在前，即),,,,(0121m m m m m k k ⋅⋅⋅=--的消息多项式为m(x)，1110)(--+++=k k x m x m m x m又设码式的高幂次部分等于m(x)，即)()()(111110x p x m x x c x c x c x c c x c k n n n k n k n k n k n +⋅=++++++=---+-+--- k n r x p -=<∂)(其中p(x)称为校验位多项式，由于码式是生成式的倍式，所以))((mod 0)()()()(x g x g x a x m x x p kn ==+-))()(mod ()(x g x m x x p r⋅-= 因此循环码的系统码码式为 ))]((mod )([)()(x g x m x x m xx c rr-= （1.1.17）将循环码的系统码构造步骤总结为（1）多项式乘))(()(x m x x m x rr =（2）多项式求模（余式） )())())(mod ((x p x g x m x r=（3）多项式减)()())((x c x p x m x r =- 如果令)(x m 为单项式1+r x ，1,,1,0-=k ir x p x p x g x a xi i r <∂+=+)(),()()(1ir ii x x p x c ++=)()( 那么容易看到，)(x c i 对应的向量i c ，1,,1,0-=k i 是线性无关的，从而得到循环码系统码的生成矩阵s G 为⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=------1000100011,11,10,11,111101,00100r k k k r r s p p p p p p p p p G（1.1.18）故由式（1.1.18）可以求得前述（7，3）循环码系统码的生成矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=101110011100100111001s G1.1.8、循环码的编码1. 利用生成多项式g(x)实现编码：如上所述，但循环码的生成多项式g(x)确定时，码就完全确定了。