纠错4章[baky]

《纠错4章[baky]》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、纠错编码（四）1循环码的定义:一个(n,k)线性分组码，若将其任意一个码字的码元向右或向左循环移一位，所得的或仍然是码字，则称该码为循环码。例4.1汉明循环码C的生成矩阵G和校验矩阵H(p76)依次令m=(0000)…(1111)代入方程C＝mG可得16个码字。经分析，将16个码字归结为4个循环环第一循环第二循环第三循环第四循环(1011000)(1110100)(0000000)(1111111)(0110001)(1101001)(1100010)(1010011)(1000101)(0100111)(000

2、1011)(1001110)(0010110)(0011101)(0101100)(0111010)2循环码的多项式描述GF(2)上n维矢量空间Vn中的任一矢量V=(vn-1,…,v1,v0)viGF(2)可与GF(2)域上多项式V(x)一一对应如下：V=(vn-1,…,v1,v0)V(x)=vn-1xn-1+…+v1x+v0多项式的各系数就是矢量各元素的值，x的幂次指示对应元素所在位置。码空间是矢量空间Vn的一个子空间，因此n重矢量不一定是码矢量，n次多项式不一定是码多项式。位于码空间的矢量叫码矢，对应的多

3、项式为码多项式。我们约定：以下所说的码字、码组、码矢和码多项式等术语具有相同的物理意义，只是描述角度和表达方式不同而已。3码矢C0=(cn-1,…,c1,c0)右循环一位C1=(cn-2,…,c1,c0,cn-1,)也是码矢。它们各自对应的码多项式是:C0(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0C1(x)=cn-2xn-1+cn-3xn-2+…+c0x+cn-1比较两者，可知C1(x)=xC0(x),mod(xn+1)(4-2)以此类推，循环码循环移2位、移3位、移n-1位后仍然应是码字,我们

4、于是得到下面一系列等式：C2(x)=xC1(x)=x2C0(x),mod(xn+1)C3(x)=xC2(x)=x3C0(x),mod(xn+1)::Cn-1(x)=xCn-2(x)=xn-1C0(x),mod(xn+1)4由码空间的封闭性，可知码多项式C0(x),…,Cn-1(x)的线性组合仍应是码多项式：C(x)=an-1xn-1C0(x)+an-2xn-2C0(x)+…+a1xC0(x)+a0C0(x)=(an-1xn-1+an-2xn-2+…+a1x+a0)C0(x)=A(x)C0(x)mod(xn+1)(

5、4-3)C0(x)是码多项式，A(x)是n-1次多项式,但不一定是码多项式。式(4-3)给出的结论是：码多项式与任意n-1次多项式作运算后，结果一定回落到码空间。码多项式构成一个理想子环5用近世代数来分析，GF(q)域上次数小于n的多项式在模q加法和模(xn-1)乘法运算下构成一个多项式剩余类环，该环是交换环，环上任一理想子环一定是主理想(P39)。定理4.1(n，k)循环码的码多项式是模(xn-1)乘运算下多项式交换环的一个主理想。反之，多项式交换环的一个主理想一定可以产生一个循环码。由于主理想的所有元素（码多

6、项式）都可以由一个元素的幂次组成，这个元素（码多项式）称为该主理想的生成元,或叫作该(n,k)循环码的生成多项式生成多项式不是唯一的，但总有一个是次数最低的6定理4.2在一个GF(2)域上的(n,k)循环码中，一定存在唯一的一个次数最低的(n-k)次首一码多项式g(x)=xn-k+gn-k-1xn-k-1+…+g1x+1使所有码多项式都是g(x)的倍式，且所有小于n次的g(x)的倍式都是码多项式。即C(x)＝m(x)g(x)及g(x)

7、C(x)“所有小于n次的g(x)的倍式都是码多项式”意味着m(x)g(x)一定

8、是码字，其中m(x)是GF(2)上小于k次的任意多项式，以致它与(n-k)次的g(x)相乘后所得倍式的次数一定小于n次。7定理4.3(n，k)循环码的生成多项式g(x)一定是(xn-1)的因式，即一定存在一个多项式h(x)，满足(xn-1)＝g(x)h(x)或g(x)

9、(xn-1)反之，如果g(x)是(xn-1)的（n-k）次因式，g(x)一定是某(n，k)循环码的生成多项式。8上述三定理告诉了我们构造(n，k)循环码的方法如下：①对xn-1(在二元域中等效于对xn+1)实行因式分解,找出其中的（n-k）次因式。

10、②以找出的（n-k）次因式为循环码生成多项式g(x)，与信息多项式m(x)相乘，即得码多项式：C(x)=m(x)g(x)。9例4.2分析码长n=7的所有可能二进制循环码解：将GF(2)上多项式(x7＋1)因式分解，或查表4.6m=3一行，得：(x7＋1)=(x＋1)(x3＋x＋1)(x3＋x2＋1)因此(x7＋1)因式的次数可以有以下四种1次(x＋1)3次(x3＋x＋1)