《信息论》讲义（第六章）6-2 循环码(Cyclic Code)循环码是线性分组码的最重要的一类码，它的结构完全建立在有限域多项式的基础上它具有两个基本特点：一是编码电路与译码电路非常简单，易于实现；二是其代数性质好编码译码分析方便，有一些好的译码方法6-2-1 循环码的描述[循环码定义]：一个(n,k)线性分组码C，如果码组中的一个码字的循环移位也是这个码组中的一个码字，则称C为循环码C(0)={cn-1,cn-2,……c1,c0} ∈CC(1)={cn-2,cn-3,……c0,cn-1} ∈C称为具有循环自闭性[循环码的多项式描述]：循环码可以用监督矩阵和生成矩阵描述，但更多地用域上多项式来描述，一个(n,k)循环的码字矢量C(0)用一个n-1次多项式描述，可以表示为：C(x)= cn-1xn-1+cn-2xn-2+……+c1x+c0这个多项式称为码字多项式码字矢量的循环移位可以用x乘上C(x)后的模xn-1(xn+1)来表示xC(x)= x(cn-1xn-1+cn-2xn-2+……+c1x+c0) = cn-1xn+cn-2xn-1+……+c1x2+c0 x = cn-2xn-1+……+c1x2+c0 x+ cn-1 (模xn+1)模xn+1相当于xn+1=0；xn=1[循环码举例]：(7,4)系统循环码的编码及码字多项式如下表：信息码字循环码字码字多项式g(x)的倍式倍式编码00000000 00000000000010001 011x3+x+11000100100010 110x4+x2+xx001000110011 101x4+x3+x2+1x+1001101000100 111x5+x2+x+1x2+1010101010101 100x5+x3+x2x2010001100110 001x5+x4+1x2+x+1011101110111 010x5+x4+x3+xx2+x011010001000 101x6+x2+1x3+x+1101110011001 110x6+x3+x2+xx3+x101010101010 011x6+x4+x+1x3+1100110111011 000x6+x4+x3x3100011001100 010x6+x5+xx3+x2+x111011011101 001x6+x5+x3+1x3+x2+x+1111111101110 100x6+x5+x4+x2x3+x2110011111111 111x6+x5+x4+x3+x2+x+1x3+x2+11101可以看出：每个码字的循环移位仍然属于这个码组，注意：并不是说这个码组是由一个码字的循环移位构成的，本例中是由四个码字的循环移位构成的。
[生成多项式的定义]：在一个(n,k)循环码中，有且仅有一个次数为n-k=r的码字多项式，记为：g(x)=xr+gr-1xr-1+……+g1x+1同时：每个码字多项式都是g(x)的倍式；每个次数小于等于n-1的g(x)的倍式必为一个码字多项式这时称g(x)的(n,k)码的生成多项式从上面的例子可见，g(x)=x3+x+1为(7,4)循环码的生成多项式[生成多项式的性质]：§ 循环码C中次数最低的非零码字多项式是唯一的，其次数为r=n-k§ 令g(x)=xr+gr-1xr-1+……+g1x+g0为一个(n,k)循环码C中最低次数码字多项式，则其常数项必为g0=1[定理1]：(n,k)循环码的生成多项式g(x)是xn+1的因式{证明}：已知g(x)为一个n-k次多项式，则xkg(x)为一个n次多项式，则必有：因为xkg(x)是g(x)的循环移位，它也是一个码字多项式，所以一定为g(x)的倍式，即有：g(k)(x)为g(x)的循环移位在模xn+1下的结果，因此有：g(k)(x)=q(x)g(x)，由上面的关系式可知：xkg(x)=(xn+1)+g(k)(x)xn+1=xkg(x)+q(x)g(x)=[xk+q(x)]g(x)因此，g(x)为xn+1的因式。
[定理2]：若g(x)是一个n-k次多项式，且为xn+1的因式，则g(x)生成一个(n,k)循环码这个定理说明：xn+1的次数为n-k的任何一个因式，均可以生成一个(n,k)循环码对于较大的n，xn+1可以有多个n-k次多项式，产生不同的(n,k)循环码，但可能有好有坏例如：多项式x7+1可以分解为：x7+1=(x3+x+1)(x3+x2+1)(x+1)可以看出有两种(7,4)循环码的生成矩阵 g(x)= (x3+x+1)和g(x)= (x3+x2+1)还可以产生一种(7,6)循环码，6-2-2 循环码的编码方法[系统循环码的编码方法]：已知循环码的生成矩阵可以按以下步骤产生系统循环码首先定义以下多项式：m(x)=mk-1xk-1+mk-2xk-2+……+m1x+m0 为信息码字多项式；c(x)=cn-1xn-1+cn-2xn-2+……+c1x+c0 为循环码字多项式；g(x)=xr-1+gr-2xr-2+……+g1x+1 为生成多项式；系统码的编码分为三步：§ 用xn-k乘上m(x);§ 用g(x)除以xn-km(x)，得到模g(x)的余式r(x)§ c(x)=xn-km(x)+r(x)为系统循环码的码字多项式。
[例题1]：(7,4)循环码的生成多项式为g(x)=x3+x+1求m=[1010]的循环码解：m(x)=x3+x, xn-k=x3;xn-km(x)=x3(x3+x)=x6+x4r(x)=x+1C(x)=xn-km(x)+r(x)=x6+x4+x+1[C]=[1010 011][例题2]：(7,3)循环码的生成多项式为g(x)=x4+x3+x2+1=(x+1)(x3+x+1)求：[m]=[010]的循环码字[C]解：m(x)=x; xn-km(x)=x4x=x5C(x)=x5+x2+x+1[C]=[010 0111][非系统循环码的编码方法]：已知循环码的生成矩阵，可以方便的求出非系统循环码，C(x)=m(x)g(x)例如：m=[1101] g(x)=x3+x+1C(x)=(x3+x2+1)(x3+x+1)=x6+x4+x3+x5+x3+x2+x3+x+1=x6+x5+x4+x3+x2+x+1[C]=[1111111]m=[0101]; c(x)=(x2+1)(x3+x+1)=x5+x3+x2+x3+x+1=x5+x2+x+1[C]=[0100111][循环码的生成矩阵]：循环码可以用域上多项式描述，也可以用生成矩阵描述。
已知g(x)为循环码C中的一个码字多项式，由循环码的循环特性可知，可以证明：在(n,k)循环码的码字多项式中，g(x),xg(x),……xk-1g(x)等k个码字多项式必是线性无关（相互独立的）的根据线性空间的特性，可知，它们是一个k维子空间的基底，即由它们的线性组合可以生成这个k维子空间的2k个码字再根据线性分组码生成矩阵的定义，它的行向量是由k个线性无关的码字构成的，可以得到(n,k)循环码的一个多项式矩阵为：[G(x)]=xk-1g(x)xk-2g(x)…g(x)相应的生成矩阵为[G]=gn-kgn-k-1…g1g000…00gn-kgn-k-1…g1g00…0…0……0gn-kgn-k-1…g1g0由这个基本关系式可以看出，当输入信息码字矢量为(mk-1,mk-2,……m0)时，相应的码字多项式为：C(x)=(mk-1,mk-2,……m0)G(x) =(mk-1xk-1+mk-2xk-2+……+m0)g(x) =m(x)g(x)利用这种方法产生的循环码为非系统循环码，因为，[G(x)]为非标准型生成矩阵，（非典型生成矩阵）这个非标准型生成矩阵可以通过矩阵的初等变换转换为标准型生成矩阵。
可以通过以下例子说明[例题]：已知(7,4)循环码的生成多项式为g(x)=x3+x+1，其非标准型生成矩阵为：[G(x)]=x3g(x)=x6+x4+x3=1011000x2g(x)x5+x3+x20101100xg(x)x4+x2+x0010110g(x)x3+x+10001011利用不同的矩阵变换可以得到不同的标准型生成矩阵这种变换包括：§ 列换位；§ 初等行变换；通过以上两种方法，可以得到标准型生成矩阵：[G]=1000111010010100101100001011只使用初等行变换可以得到标准生成矩阵：[G]=1000101010011100101100001011可知标准型生成矩阵是不唯一的6-2-3 校验子与循环码的译码原理设发送的码字多项式位C(x)，错误图样多项式位E(x)，则接收码字多项式为：R(x)=C(x)+E(x)译码器的工作过程为：§ 由接收码字多项式R(x)计算校验子多项式S(x);§ 根据校验子多项式S(x)计算错误图样多项式E(x);§ 利用R(x)-E(x)=C(x)计算译码器输出的估计值发送码字多项式为：C(x)=cn-1xn-1+cn-2xn-2+……c1x+c0接收码字多项式为；R(x)=rn-1xn-1+rn-2xn-2+……+r1x+r0校验子多项式为：E(x)=en-1xn-1+en-2xn-2+……e1x+e0由R(x)=C(x)+E(x)可知：ri=ci+eI i=0,1,…n-1这时定义校验子多项式为： [模g(x)]即：S(x)≡E(x)≡R(x) [模g(x)]也就是说，接收码字多项式除以g(x)的余式多项式为校验子多项式。
如果：S(x)=0，表示接收码字无错；如果：S(x)≠0,表示接收码字有错；(n,k)循环码的校验子多项式的一般表达式为：S(x)=sr-1xr-1+sr-2xr-2+……+s1x+s0即校验子多项式S(x)为一个r-1次多项式其校验子矢量为：[S]=[sr-1,sr-2,……s1,s0]它共有2r个状态，当2r≥n+1时，即可以纠一位错[例题]：(7,4)循环码的校验子及译码，已知：(7,4)循环码的生成矩阵为g(x)=x3+x+1考虑接收码字不错或只错一位时的校验子多项式发送码字多项式为：C(x)=cn-1xn-1+cn-2xn-2+……c1x+c0接收码字多项式为；R(x)=rn-1xn-1+rn-2xn-2+。