循环码与BCH码

第六章循环码与BCH码第一节基本定义•循环码是线性分组码中应用最广泛的一类码。它有两个重要的特点：1、码的结构可以用代数方法来表示、分析和构造。2、利用循环特性，可以用循环反馈移位寄存器来构造较为简单方便的编码器和译码器。循环码：设C是码长为n，信息位为k,监督位为r的(n,k)线性分组码的任意一个码字，如果C的每一次循环移位也是码字，则把具有这种循环移位特点的码称为循环码(CyclicCodes)。即如果C=[cn-1,cn-2,…,c1,c0]是一个码字则C1=[cn-2,cn-3,…,c0,cn-1]C2=[cn-3,cn-4,…,cn-1,cn-2]……Cn-1=[c0,cn-1,…,c2,c1]都是码字例如，第五章中表5-2中所列的(7,3)码，就是具有这种循环特性的循环码。（P176）关于循环码强调两点：1、本书讨论的循环码首先是一个线性分组码。2、循环码具有循环移位特性。例6-1：判断下面三组码字的特点。000110011101000100011111000100010001C1=C2=C3=C1是线性循环码，C2是非循环的线性分组码，C3是非线性的循环码。码多项式与n重码相对应的n-1次多项式C(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0[6-1]称为码多项式。例如：码字C=[0010111]所对应的码多项式为C(x)=x4+x2+x+1假如已知码多项式C(x)=x7+x3+x+1，则可求出对应的码字C=10001011首一多项式首项系数为1的多项式。如f(x)=x7+1。我们把多项式f(x)的最高次数记为0f(x)。此处0f(x)＝7。多项式同余它和数的同余类似。例如，用x7+1除x7+x6+x5＋x3所得余式，和用x7+1除x6+x5＋x3＋1所得余数式相同，即：1xxxx11xxxxx7135673567我们就称x7+x6+x5＋x3和x6+x5＋x3＋1关于x7+1同余，并记为x7+x6+x5＋x3x6+x5＋x3＋1mod(x7+1)•实际上，将(n,k)循环码的一个码字C=[cn-1,cn-2,…,c1,c0]所对应的码多项式循环左移一位，即相当于对码多项式乘以x并除以xn+1后所得的余式，刚好是将码字C循环移位一次后所得码字(cn-2,cn-3,…,c0,cn-1)的码多项式，即下面关系式成立：x(cn-1xn-1+cn-2xn-2+…+c1x+c0)=cn-1xn+cn-2xn-1+…+c1x2+cnx≡cn-2xn-1+cn-3xn-2+…+c1x2+cnx+cn-1mod(xn+1)•(n,k)循环码的每个码字必处在以xn+1为模运算的剩余类的某一类中。•生成多项式在(n,k)循环码的2k个码字中，取一个前k-1位皆为0的码字，此码字对应有一个次数最低，且为n-k=r的多项式g(x)，其它码字所对应的码多项式都是g(x)的倍式，则称g(x)生成该码，并且称g(x)为该码的生成多项式。可见生成多项式具有以下特征：g(x)=xr+gr-1xr-1+…+g2x2+g1x+g0g0≠0r=n-k•如果g(x)为(n,k)循环码的最低次多项式，即生成多项式时，xg(x),x2g(x),…,xk-1g(x)都是码字，这k个码字是独立的，故可作为码的一组生成基底，使每个码多项式都是这一组基底的线性组合。例如P176例5-1由此看来，找到合适的g(x)是构造循环码的关键。在这方面需要用到有限域的知识。第二节有限域中的运算规则•运算自封：一个集合中的元素经过某种运算（例如加减乘除）后仍为集合中的元素时，称为运算自封。•域：运算自封元素的集合叫做域F（Field）。域中的元素相加a+b和相乘ab满足下列关系：A0:对a,bF,a+b=c存在且唯一，cFA1:(a+b)+c=a+(b+c)A2:b+a=a+bA3:域中有0元，且对任意a有a+0=0＋a＝aA4:对任意a有负元存在且a+(-a)=(-a)＋a＝0M0:对a,bF,a+b=c存在且唯一，cFM1:(ab)c=a(bc)M2:ba=abM3:域中有1元，且对任意a有a1=1a＝aM4:对任意a0有异元a-1且aa-1=a-1a＝1D：满足分配律a(b+c)=ab+ac,(a+b)c=ac+bc•当域中元素为有限数p时，称为有限域或p元域，有限域理论是由数学家伽罗华（Galols）所创立的，因此又称为伽罗华域，并记为GF(p)。•普通代数中全体有理数的集合叫有理域，全体实数的集合叫实数域。全体复数的集合叫复数域。它们都是无限域。•经常用到的有限域是二元域GF(2)，它有两个元素“0”和“1”，其加法和乘法分别为：加法乘法0+0＝00*0＝00+1＝10*1＝01+0＝11*0＝01+1＝01*1＝1系数在GF(2)中的多项式叫做二元域上的多项式。二元域上多项式的加减乘除等运算在原理上和普通代数多项式的运算相同。例如：对码字多项式C(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0有xi+xi＝0,ci+ci＝0,ci2=ci.ci＝ci并且减法就是加法。加法符号为“”或简记为“+”。证：因C2(x)＝(cn-1xn-1+cn-2xn-2+…+c1x+c0)2=(cn-1xn-1)2+2cn-1xn-1(cn-2xn-2+…+c1x+c0)+(cn-2xn-2+…+c1x+c0)2考虑到cn-12＝cn-1，上式包括2作系数的第二项乘积为0，将第三项类似地逐步展开，就可以得出C2(x)＝cn-1x2(n-1)+cn-2x2(n-2)+…+c1x2+c0=C(x2)例6-2试证明对上述二元域上码多项式C(x),有C2(x)＝C(x2)•定理：设d(x)和g(x)是二元域上的两个多项式。则有唯一的一对二元域上的多项式q(x)和r(x)。具有下面的性质：d(x)=q(x)g(x)+r(x)其中r(x)的次数小于g(x)的次数，叫余式。这个定理也称欧几里德(Euclid)除法定理。利用这种余式的唯一性质，按某个次数为m的多项式g(x)的求余运算，可以把所有多项式分为2m个剩余类。例如，m=3的三次多项式g(x)=1+x+x3有2m=23=8个剩余类0x211+x2xx+x21+x1+x+x2•既约多项式又称不可约多项式，它不能分解为次数更低的多项式的乘积，例如x2+x+1和x4+x+1为不可约多项式，而x2+1不是既约多项式。因为(x+1)2=x2+x+x+1=x2+1•和普通代数一样，对于多项式f(x),如果f(a)=0,则称a为多项式的根，例如(x+1)2的根为1。显然，既约多项式的根不能在二元域内，但是可以像实数根扩展到复数根那样，将既约多项式的根在二元域的扩充域中表示出来。以二次既约多项式1+x+x2为例，可以把二元域中的元“0”和“1”扩充一位，表示成0＝(00),1=(01)。如果a是1+x+x2的根，则可令a=(10).。再由1+a+a2＝0，可得a2＝1+a=(01)+(10)=11•这样就得到一个具有两位数字的扩域GF(4)，它包含0、1、a、a2四个元。第三节循环码多项式的基本特性循环码多项式(6-1)具有如下一些特性：(一)C(x)经过i次循环所得码多项式Ci(x),是用xn+1除xiC(x)后所得的余式，即xiC(x)＝q(x)(xn+1)+Ci(x)证：令i=1,由(6-1)式显然有1)(1)...)1(1)...(1)(111021021121121nnnnnnnnnnxxCcxcxcxcxcxcxcxcxcxcxxxxCnnnn（当i大于1时，可类似推导）xiC(x)的次数等于或小于n-1时，则可以较简单地直接写出Ci(x)＝xiC(x)(二)在一个(n,k)循环码中，有唯一的一个n-k次多项式g(x)=xn-k+gn-k-1xn-k-1+…+g2x2+g1x+1，每个为g(x)倍式的小于等于n-1次的多项式一定是码多项式。反之，每一个码多项式C(x)是g(x)的倍式。证：令r=n-k，由于g(x)=xr+gr-1xr-1+…+g2x2+g1x+1是(n,k)循环码中次数最低的一个非零首－多项式。由于码的循环特性，xg(x),x2g(x),…,xn-1-rg(x)也必为码多项式，从而它们的线性组合(mn-1-rxn-1-r+…+m2x2+m1x+m0)g(x)=M(x)g(x)也必在循环码中，故每一个次数等于或小于n-1次的g(x)的倍式是码多项式。反之，任意一个码字的码多项式Ci(x)，必定是最低的非零首－多项式g(x)的倍式。因为不然的话，将Ci(x)用g(x)除之，将会出现余式b(x)，即Ci(x)＝a(x)g(x)+b(x)，由此，b(x)=Ci(x)+a(x)g(x)为码多项式Ci(x)和g(x)的线性组合，必定也是一个码多项式。且其次数因其为余式低于g(x)。这和原来假设g(x)是码多项式集合中次数最低的相矛盾，故b(x)=0,即Ci(x)是g(x)的倍式：Ci(x)＝a(x)g(x)设g(x)不是唯一的，即还有一个同次数的非零首－多项式g’(x)=xr+g’r-1xr-1+…+g’2x2+g’1x+1则g’(x)和g(x)的线性组合g(x)－g’(x)必定也是码多项式，且由于首项相消，其次数小于g(x)的次数,与g(x)是码多项式中次数最低的矛盾。所以g(x)＝g’(x)，g(x)是唯一的。(三)(n,k)循环码的生成多项式g(x)是xn+1的因式，反之，若g(x)是xn+1的一个n-k次因式，则g(x)生成(n,k)循环码。证：因g(x)为n-k次，则xkg(x)为n次多项式，用xn+1除之，由6-5式可得：xkg(x)＝xn+1+Ck(x)其中Ck(x)为码多项式，总可以写为g(x)的倍式形式，即Ck(x)＝m(x)g(x)由此可以得出xn+1＝(xk+m(x))g(x)即g(x)是xn+1的一个因式。反之，当g(x)为n-k次，则它的倍式的线性组合(m0+m1x+m2x2+…mk-1xk-1)g(x)也是码多项式，系数m0、m1、m2、mk-1共有2k种不同组合，正好构成(n,k)码中k个信息元所形成的2k个码多项式。•概括地说，要生成一个(n,k)循环码，就是要找到一个能除尽xn+1的r=n-k次首－生成多项式g(x),由g(x)来生成各个码多项式后，找出与码多项式相对应的循环码字。第四节循环码的编码方法由上节已经知道，低于n次的多项式C(x)是一个由除尽xn+1的r=n-k次首－多项式g(x)生成的(n,k)循环码的一个码字的充分必要条件是C(x)0modg(x)对长为k位的任意消息组M=(mk-1,…,m1,m0)，其对应的消息多项式为M(x)=mk-1xk-1+…+m1x+m0可乘以g(x)而构成n-1次的码多项式C(x)=M(x)g(x)=(mk-1xk-1+…+m1x+m0)g(x)或xk-1g(x)…C(x)=[mk-1,…,m1,m0]·xg(x)=MG(x)g(x)式中G(x)为循环码的生成矩阵，其k行分别由g(x)循环移位而成。但是这样编成的循环码不是系统码。如要编成前k位是信息元，后r=n-k位是监督元的n位系统码，可以先用xn-k乘消息多项式M(x)，再用g(x)去除，即)()()()()(xgxrxqxgxMxkn其中q(x)是商式，r(x)是次数小于n-k的余式。于是C(x)=xn-kM(x)+r(x)=g(x)q(x)是g(x)的倍式，因而是由g(x)生成(n,k)循环码的码多项式。如果令M(X)为单项式xk-ii=0,1,2…k-1则Ci(x)=x+r(x)n-ii可以容易看到码多项式Ci(x)对应的码字（或向量），i=0,1,2…k-1是线性无关的，所以这K个码多项式组成了循环码的系统生成矩阵。系统循环码的生成矩阵为：xn-1+rn-1(x)xn-2+rn-2(x)C(x)=………xn-k+1+rn-k+1(x)xn-k+rn-k(x)式中r