又称不可约多项式它不能分解为次数更低的多项式的乘`隥课件

《又称不可约多项式它不能分解为次数更低的多项式的乘`隥课件》由会员分享，可在线阅读，更多相关《又称不可约多项式它不能分解为次数更低的多项式的乘`隥课件（72页珍藏版）》请在装配图网上搜索。

1、第六章循环码与第六章循环码与BCH码码第一节基本定义循环码是线性分组码中应用最广泛的一类码。它有两个重要的特点：1、码的结构可以用代数方法来表示、分析和构造。2、利用循环特性，可以用循环反馈移位寄存器来构造较为简单方便的编码器和译码器。循环码循环码：设C是码长为n，信息位为k,监督位为r的(n,k)线性分组码的任意一个码字，如果C的每一次循环移位也是码字，则把具有这种循环移位特点的码称为循环码循环码(Cyclic Codes)。即如果 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-

2、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

3、假如已知码多项式C(x)=x7+x3+x+1，则可求出对应的码字C=10001011 首首一一多多项项式式 首项系数为 1 的多项式。如 f(x)=x7+1。我们把多项式 f(x)的最高次数记为 0f(x)。此处0f(x)7。多多项项式式同同余余 它和数的同余类似。例如，用 x7+1 除x7+x6+x5x3 所得余式，和用x7+1 除 x6+x5x31 所得余数式相同，即：1xxxx11xxxxx7135673567 我们就称x7+x6+x5x3 和x6+x5x31 关于x7+1同余，并记为 x7+x6+x5x3x6+x5x31 mod(x7+1)实际上，将(n,k)循环码的一个码字C=cn-

4、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-1 mod(xn+1)(n,k)循环码的每个码字必处在以xn+1为模运算的剩余类的某一类中。生成多项式生成多项式在(n,k)循环码的2k个码字中，取一个前k-1位皆为0的码字，此码字对应有一个次数最低，且为n-k=r的多项

5、式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)是构造循环码的关键。在这方面需要用到有限域的知识。第二节有限域中的运算规则 运算自封运算自封：一个集合中的元素经过某种运算（例如

6、加减乘除）后仍为集合中的元素时，称为运算自封。域域：运算自封元素的集合叫做域F（Field）。域中 的元素相加a+b和相乘ab满足下列关系：A0:对 a,bF,a+b=c 存在且 唯一，cF A1:(a+b)+c=a+(b+c)A2:b+a=a+b A3:域中有 0 元，且对任意 a 有 a+0=0aa A4:对任意 a 有负元存在且 a+(-a)=(-a)a0 M0:对 a,bF,a+b=c 存在且 唯一，cF M1:(ab)c=a(bc)M2:ba=ab M3:域中有 1 元，且对任意 a 有 a1=1aa M4:对任意 a0 有异元 a-1且 a a-1=a-1a1 D：满足分配律a(b

7、+c)=ab+ac,(a+b)c=ac+bc 当域中元素为有限数p时，称为有限域或p元域，有限域理论是由数学家伽罗华（Galols）所创立的，因此又称为伽罗华域，并记为GF(p)。普通代数中全体有理数的集合叫有理域，全体实数的集合叫实数域。全体复数的集合叫复数域。它们都是无限域。经常用到的有限域是二元域GF(2)，它有两个元素“0”和“1”，其加法和乘法分别为：加法乘法0+000*000+110*101+011*001+101*11系数在GF(2)中的多项式叫做二元域上的多项式。二元域上多项式的加减乘除等运算在原理上和普通代数多项式的运算相同。例如：对码字多项式C(x)=cn-1xn-1+cn

8、-2xn-2+c1x+c0有xi+xi0,ci+ci0,ci2=ci.cici并且减法就是加法。加法符号为“”或简记为“+”。证：因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-1 2 cn-1，上式包括2作系数的第二项乘积为0，将第三项类似地逐步展开，就可以得出C2(x)cn-1x2(n-1)+cn-2x2(n-2)+c1x 2+c0=C(x2)例6-2试证明对上述二元域上码多项式C(x),有C2(x)C(x2)定理：设d(x)和g(x)是二元域上

9、的两个多项式。则有唯一的一对二元域上的多项式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个剩余类0 x211+x2x x+x21+x 1+x+x2 既约多项式既约多项式 又称不可约多项式，它不能分解为次数更低的多项式的乘积，例如x2+x+1和x4+x+1为不可约多项式，而x2+1不是既约多项式。因为(x+1)2=x2

10、+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+a20，可得a2 1+a=(01)+(10)=11这样就得到一个具有两位数字的扩域GF(4)，它包含0、1、a、a2四个元。第三节循环码多项式的基本特性循环码多项式(6-1)具有如下一些特性：(一

11、)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)(111021021121121nnnnnnnnnnxxCcxcxcxcxcxcxcxcxcxcxxxxCnnnn（当 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)倍式的小

12、于等于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

13、)，即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+gr-1xr-1+g2x2+g1x+1则g(x)和g(x)的线性组合g(x)g(x)必定也是码多项式，且由于首项相消，其次数小于g(x)的次数,与g(x)是码多项式中次数最低的矛盾。所以g(x)g(x)，g(x)是唯一的。

14、(三)(n,k)循环码的生成多项式g(x)是xn+1的因式，反之，若g(x)是xn+1的一个n-k次因式，则g(x)生成(n,k)循环码。证：因g(x)为n-k次，则xk g(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,

15、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)0 modg(x)对长为 k 位的任意消息组 M=(mk-1,m1,m0)，其对应的消息多项式为 M(x)=mk-1xk-1+m1x+m0 可乘以 g(x)而构成 n-1 次的码多项式 C(x)=M(x)g(x

16、)=(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)为单项式为单项

17、式xk-ii=0,1,2k-1则则Ci(x)=x +r(x)n-ii可以容易看到码多项式可以容易看到码多项式Ci(x)对应的码字（或向量），对应的码字（或向量），i=0,1,2k-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)式中rn-i(x)为xn-i除以g(x)后所得的余式。是g(x)的倍式，因而是由g(x)生成(n,k)循环码的码多项式。解：由于n=7时 x7+1=(x+

18、1)(x3+x+1)(x3+x2+1)6-14如选用g(x)=x3+x+1，并考虑到M=1101-M(x)=x3+x2+1即此处余式r(x)=1，由6-13得出C(x)=x3(x3+x2+1)+1=x6+x5+x3+1由此得出对应于消息1101的码字为1101001。1111)1()()(3233233xxxxxxxxxxxgxMxkn例6-2将消息M=1101编成(7,4)循环汉明码解：从6-14中取次数为n-k=4的g(x)，即取 g(x)=(x+1)(x3+x+1)=x4+x3+x2+1因M=101-M(x)=x2+1故此多项式为C(x)=x4(x2+1)+x+1=x6+x4+x+1由此

19、得出对应的编成码字为1010011。1111)1()()(234223424xxxxxxxxxxxxgxMxkn例6-3将消息M=101编成(n,k)=(7,3)循环码由上面例子可以看出，从xn+1中取不同的n-k次因式作g(x),就得出不同(n,k)循环码。一般可写为xn+1=h(x)g(x)或)1mod(0)()(nxxgxh其中h(x)称为监督多项式，次数为k。例如，由x7+1就可以构成如表6-3所示不同k值的循环码。由x7+1的因式构成(7,3)循环码 表6-3(n,k)码 码距d 生成多项式g(x)监督多项式h(x)(7,6)2 x+1 (x3+x+1)(x3+x2+1)(7,4)3

20、 x3+x+1 (x+1)(x3+x2+1)3 x3+x2+1 (x+1)(x3+x+1)(7,3)4 (x+1)(x3+x+1)x3+x2+1 4 (x+1)(x3+x2+1)x3+x+1(7,1)7 (x3+x+1)(x3+x2+1)x+1第五节循环码的编码电路 上一节已介绍，(n,k)循环码的编码，可以化为用g(x)去除 xn-kM(x)求余式r(x)的问题。在实际编码技术中，这个相除是用除法电路来实现的。一、多项式除法电路 我们先来分析一下例6-3中除法运算112112342223446xxxxxxxxxxxx 为了完成这个计算步骤，可以根据除式的次数r(此处r4)，设置r级移位寄存器

21、(图6-1)，并在移位寄存器的某些位置(这些位置由除式中系数不为零的项来决定)上，加上按模二相加的反馈连结线。D0D1输 出输 入图6-1除式为x4+x3+x2+1的除法电路D2D3 表6-4中列出图6-1除法电路在各次移位后的状态。在移位脉冲7后，寄存器D0与D1中的存数均为1，表明余式为1+x。除法电路中的状态表除法电路中的状态表6-4由图6-1和表6-4可以看出除法电路的特点：1、除法电路中移位寄存器的级数等于除法的次数；2、除式的非零系数对应着移位寄存器的反馈抽头；3、为了求余式，总的移位次数等于倍除式次数加1。二、自动乘xr的除法电路 从表6-4中可以看出，在第一次到第四次移位过程中

22、，除法电路中只是接收输入的x6、x5、x4、x3的系数，只在第五次移位时才真正开始运算。为了节省时间，可以将图6-1改为图6-2的形式，此时被除数M(x)不是从D0的输入端输入，而是从D2的输出端输入。因此，它相当于被除数M(x)自动乘x4以后再送入除法电路。D0D1输出图6-2自动乘xr的除法电路D2D3输入x4M(x)这种电路的运算结果表示在表6-5中，由表中可以看出，只要经过三次移位，就完成了除法运算，D0、D1、D2、D3 中的存数1100，就是余式中x0、x1、x2、x3的各次系数。三、编码电路 前面已经谈到，(n,k)循环码的编码方法，是从xn+1的因式中找到一个(n-k)次的生成

23、多项式g(x)，然后将与输入消息相对应的消息多项式M(x)乘xn-k，被g(x)除之，得出余式r(x),并将其附在xn-k M(x)之后，就构成码多项式C(x)。所有它的编码器就是一个将M(x)自动乘以xn-k的g(x)除法电路，加上几个控制门而成。下面以g(x)x3+x+1的(7,4)循环汉明码的编码电路为例加以说明。设输入消息M=1100，则M(x)x3+x2，于是xn-k M(x)x3(x3+x2)=x6+x5，它被g(x)除后，余式为r(x)=x，即监督位为010，相应的码多项式为C(x)=x6+x5+x，从而编成的码字为1100010。其编码电路如图6-3所示。D0D1输出图6-3g

24、(x)x3+x+1的(7,4)循环汉明码编码器D2门1输入x3M(x)门2运算过程表示在表6-6中。其中虚线方框中010表示余式x.首先门1断开，门2接通，用自动乘xn-k=x3的方式输入M(x)。当移位4次后，4个信息元已全部送入除法电路和信道。除法电路已完成除法运算，得到r=n-k=3个余数项010，存储在D0、D1、D2,中。这时门1接通，门2断开，把移位寄存器中的三个存数作为监督元附在四个信息元后送入信道，从而完成整个码字的编码过程。因此，编出的是系统码。第六节 循环码的译码电路设发送码多项式为C(x)=cn-1xn-1+cn-2xn-2+c1x+c0 接收码多项式为R(x)=rn-1

25、xn-1+rn-2xn-2+r1x+r0由于信道干扰的影响，发送码与接收码间有差别，构成错误图样码多项式E(x)=R(x)-C(x)=en-1xn-1+en-2xn-2+e1x+c0 由于正确的码多项式C(x)总是能被生成多项式所整除，用生成多项式g(x)除接收码多项式R(x)所得的余式(称位伴随式S(x),与用g(x)除E(x)所得的余式是相同的，即)(mod)()(xgxSxE通常，如果用g(x)去除接收码多项式R(x)，得到的伴随式S(x)0,与说明R(x)0，R(x)C(x)，没有错误。如果所得的余式是相同的，即S(x)0,则E(x)0,说明有错误。一、自发运算电路 在译码电路中，要用

26、到自发运算电路的概念。下面用熟悉的x7+1的一个本原多项因式g(x)=x3+x+1为例子来说明。图6-4为此多项式的除法电路。它没有输入电路，完全按D0、D1、D2中的初始状态进行移位来决定电路的状态。显然，对于全零的初始状态000，无论移多少次后，移存器的状态始终为0。现设D0 D1 D2的初始状态为100，移位；一次变为010。再移位一次变为001，连续移位的状态变化如表6-7所示。D0D1图6-4g(x)x3+x+1的自发运算电路D2 可以看出，经过7次循环移位后，返回到原来初始状态(图6-5)。一般说来，用一个m次本原多项式g(x)作成的除法电路，在初始状态不全为0和无输入的条件下，将

27、输出一个周期的2m-1的最长二进制循环序列。称为m序列，其电路称为m序列产生器。从表6-7还可以看出，移寄存器的每一个状态，与单个错误图样被E(x)g(x)除后所得的余式即伴随式S(x)之间，有着一一对应的关系。且每移位一次，相当于错误图样的次数升高一次。例如，001相当于E(x)x2 的伴随式，而110相当于E(x)x2 x+1(mod g(x)的伴随式。因此，若用Si 代表 xi被g(x)除后所得的余式，则j次移位后的伴随式Si+j 是xi+j被g(x)除后所得的余式，它对应于Si 的状态在自发运算电路中循环移位j次后所得的状态，即 Si+j(x)=xjSi(x)mod g(x)特别值得提

28、出的是，对应于在第i位发生错误时，E(x)=xi,其伴随式为Si(x),当 Si(x)在自发运算电路中运算移位7-i次后，伴随式变为x7-iSi(x)=Si-7-i(x)=S7(x)=S0(x)这就是说，对于任何i状态，经过7-i次移位后，总能使移存器的状态变为开始的100状态，这个特点将要在下面的译码电路中用到。二、纠正一位错误的(7,4)码译码电路译码电路由I，II,III部分构成(图6-6)。D0D1图6-6纠正一位错误的(7,4)码译码电路D2控制门IR(X)D0D1D2与门E(X)C(X)R(X)反相7级移位寄存器IIIII 第一部分为g(x)=x3+x+1除法电路计算伴随式S(x)

29、部分，接收到的R(x)一方面送入除法电路，一方面进入第III部分的7级移位寄存器。当R(x)全部移入7级移位寄存器时，除法电路经7次运算后得到S(x)。若S(x)为零，则D0、D1 、D2 的状态为000，说明接收到的码多项式R(x)没有错误，否则有错。有错时需通过第II部分自发运算电路找到发生错误的码位，以模二方式加上一个“1”以纠正该位错误。要注意到接收码R(x)和发送码C(x)都是高次位先行，伴随式Si相应于错误图样 xi，如从先行的高次位来计算该位的位置次序，则认为是第7-i位有错。利用控制门将Si送入第II部分自发运算电路。与此同时，第I部分除法电路继续接收R(x)的下一组码元。第I

30、II部分7级移位寄存器一方面送出前一组码元，一方面接收另一组R(x)码元。Si在自发电路中经过7-i次后变为S0100。D0中的“1”经过反相变成“0”后，与D1、D2中的“0”构成或非门的全0输入，使其开通，输出一个“1”。此时7级移位寄存器正好移了7-i次，刚好移至第i位，把待纠错的那一位送到输出端，和或非门的输出“1”模二相加，使该码元变反，从而完成了纠错。例如，当Si=S2,相当于x2有错，从高次算起则是第7-25位有错。D0D1D2的状态为001，经过自发运算电路移位运算5次后变为100，这时与门开通，输出一个“1”，和7级移存器的第5位(即x2位)码元进行模二相加，从而纠正该位错误

31、。第七节BCH码 以发现着命名的BCH(Bose-Chaudhurl-Hocquenghem)码，是自1959年发展起来的一种能纠正多位错误的循环码。由于码的生成多项式与码的最小距离有关，容易根据纠错能力要求来直接确定码的构造，因此，它是一类应用广泛的差错控制码。一、最小多项式 令是GF(2m)中的一个元素，某个形成循环周期并对的所有根均满足m()=0的最低多项式m(x),称为的最小多项式。这个最小多项式是既约的。而且根据(6-3)可知，当为m(x)的根时，2,4，8，也比是m(x)的根。以GF(24)为例，当有根a时,则a,a2,a22=a4,a23=a8,均为根(a24=a16=a不是新根

32、)。因此，包括全部根的最小多项式为 mi(x)=(x+a)(x+a2)(x+a4)(x+a8)=x4+x3(a+a2+a4+a8)+x2(a3+a5+a9+a6+a10+a12)+x(a14+a13+a11+a7)+a15利用GF(24)域中a4+a+1=0所生成的元素表(表6-1)，可以将上式简化为mi(x)=x4+x+1当a3 时，则2 a6，22 a12，23 a24 a9，均为根(24 a48 a3 不是新根)。因此，类似地得到m3(x)=(x+a3)(x+a5)(x+a9)(x+a12)=x4+x3+x2+x+1同理a5 时，则2 a10 也为根(4 a24 a5 不是新根)。因此m

33、5(x)=(x+a5)(x+a10)=x2+x+1由于x16+1(x+1)(x2+x+1)(x4+x+1)(x4+x3+1)(x4+x3+x2+x+1)所以m1(x)，m3(x)，m5(x)都是x15+1 x24-1+1的一个既约因式。二、码的主要特征 对于任何正整数m和t(m=3,t2m-1)，存在着能纠正t个以内错误的BCH码，其参数为：码长：n=2m-1 (6-25)监督元位数：n-k=2t+1 (6-27)其生成多项式g(x)为GF(2m)上最小多项式m1(x),m2(x),m2t(x)的最小公倍式，即 g(x)=LCMm1(x),m2(x),m2t(x)(6-28)或者，考虑到m2(

34、x)的根包括在m1(x)内,m6(x)的根包括在m2(x)内，也就是一般来说，a2i的最小多项式m2i(x)和ai的最小多项式mi(x)相同，偶数下标项可一律取消，于是(6-28)可进一步简化为 g(x)=LCMm1(x),m3(x),m2t-1(x)(6-29)为了证明(6-28)或(6-29)所选取的生成多项式g(x)能够生成最小码距d满足(6-27)的BCH码，参照第五章第五节介绍码的监督矩阵时，曾经谈到一个最小码距为d的码，在其监督矩阵H中，任意少于等于d-1列必须是线性无关，也就是H中任意少于等于d-1列相加的和均不应该等于零。下面就来证明，生成多项式g(x)按(6-28)的形式选取

35、，其监督矩阵H中任取d-1列所构成的行列式的值不等于0，从而满足d-1列线性无关的要求。实际上，由于d=2t+1,(6-28)又可以表示为 g(x)=LCMm1(x),m2(x),md(x)(6-30)式中包括了由1至d-1的最小多项式，因此a1,a2,ad-1均为g(x)的根，从而也比为任一码多项式的根。设任一码多项式为 C(x)=cn-1 xn-1+c2 x2+c1 x+c0 将根a1,a2,ad-1依次代入后，将构成下列联立方程组 cn-1 an-1+c2 a2+c1 a+c00 cn-1(a2)n-1+c2(a2)2+c1 a2+c00 cn-1(ad-1)n-1+c2(ad-1)2+

36、c1 ad-1+c00或写为HXT=OT的形式 cn-1 an-1 a2 a1 0 (a2)n-1(a2)2a21 c2 =0 c1 (ad-1)n-1(ad-1)2 ad-1 1 c0 0即监督矩阵为 an-1 a2 a1H=(a2)n-1(a2)2a21 (ad-1)n-1(ad-1)2 ad-1 1H中共有n列，现在证明，任取其中d-1列，它们的行列式之值也不会为0。设选取第i1,i2,id-1列，令1 ai1,2 ai2,i-1 aii-1,则有 1 2 d-1 H i1i2id-1=12 22 d-12 1d-1 2d-1 d-1d-1 1 1 1=12i-1 1 2 i-1 .1d

37、-2 2d-2 d-1d-2=12i-1Hv而 1 1 1Hv=1 2 i-1 .1d-2 2d-2 d-1d-2 为熟知的范德蒙德矩阵(Vandermonde Matrix)。它的行列式值已知为 因此，H中任取的d-1列线性无关，从而保证码字中有最小的重量d，也就是最小码距为d，故得所证。0)(112jiijidIJiIIII例6-4求长度n=15的BCH码的生成多项式，它们能分别纠正1个，2个，3个错误。解：纠正1个错误，此时t=1,由(6-21)知g(x)=LCMm1(x)=mi(x)=x4+x+1(10011)此处d=3,d0 g(x)=4=n-k,故k=15-4=11,即为(n,k,

38、d)=(15,11,3)码纠正2个错误，此时t=2,由(6-22)知g(x)=LCMm1(x),m3(x)=(x4+x+1)(x4+x3+x2+x+1)=(x8+x7+x6+x4+1)(111010001)此处d=5,d0 g(x)=4=n-k,故k=15-8=7,即为(n,k,d)=(15,7,5)码纠正3个错误，此时t=3,由(6-23)知g(x)=LCMm1(x),m2(x),m3(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)=(x10+x8+x5+x4+x2+x+1)(10100110111)此处d=7,d0 g(x)=10=n-k,故k=15-10=5,即为(n

39、,k,d)=(15,5,7)码从本例中看出，(15,11,3)BCH码就是纠正一位错误的汉明码。一般而言，对任何m=3.长度为n=2m-1的汉明码，就是纠正单个错误的，长度为n=2m-1的BCH码。码长n=2m-1(m=3,4,5,6)的汉明码的生成多项式列在表6-8中。由表中可以看出，汉明码的生成多项式都是m次本原多项式，因此属于本原BCH码。三、戈雷码 前面讨论的生成多项式g(x)包含本原元a的根的BCH码，称为本原BCH码。还有一种非本原BCH码，它的生成多项式g(x)不含有本原元的根，它的码长n也不等于2m-1，而是2m-1的一个因子。著名的戈雷码(Golay Code)，是一个二元域

40、内唯一已知的能纠正多位错误的完备码，它的码参数为(n,k,d)=(23,12,7),生成多项式为 g1(x)=x11+x10+x6+x5+x4+x2+1 或g2(x)=x11+x9+x7+x6+x5+x+1 g1(x)和g2(x)都是x23+1的因式，且非本原多项式。x23+1(x+1)g1(x)g2(x)它的码长(n=23)不等于2m-1 223-12047，而是2047的一个因子，即23*892047，因此，它属于非本原BCH码。显然，戈雷码的11个监督元被最充分地用来监督码字中三个以内的所有错误状态，即：211C(23,0)+C(23,1)+C(23,2)+C(23,3)因而它是一种性能

41、很好的完备码，在理论研究和实际应用中均有重要的价值。四、BCH码的译码方法 汉明码是能够纠正一位错误的循环码，BCH码则是能够纠正多位错误的循环码。码字的编码和译码关系，也象微分鳄积分，付里叶变换和付里叶反变换一样，是方向相异的正反运算，而且往往都是正向运算容易，反向运算较难。从前面的叙述中可以看出，BCH码的编码过程，就是根据码长和纠错位数的要求选择合适的生成多项式，再用循环码的编码方法进行。然而，BCH码的译码远比编码复杂，一直是编码理论研究中人们关注的重要课题。1960年Perterson奠定了二进制BCH码译码的理论基础。1966年Berlekamp提出了迭代译码算法，节省了计算量和加

42、快了译码速度。以后还有作者提出了欧几里德连分式等译码方法。译码的复杂性随之纠错位数的增加而增加，为了清楚起见，下面仅以纠正两位错误的例子来说明译码的主要原则和步骤。设能纠正t=2位错误的发送码字为 C(x)=cn-1 xn-1+c2 x2+c1 x+c0 接收到的码字为 R(x)=rn-1 xn-1+r2 x2+r1 x+r0 错误图样为 E(x)=en-1 xn-1+e2 x2+e1 x+e0 因为该码能纠正t=2位错误，故g(x)按(6-28)应为 g(x)=LCMm1(x),m2(x),m3(x),m4(x)也就是说，a,a2,a3,a4为C(x)的根，故监督矩阵可写为 an-1 a2

43、a 1H=(a2)n-1(a2)2a2 1 (a3)n-1(a3)2a31 (a4)n-1 (a4)2 a4 1 当我们用监督矩阵来检查接收码的码字R(x)时，可以得出伴随式 S1 ST=HRT=H(C+E)T=HET=S2 S3 S4 当码字在两位上发生错误(码位用x1,x2来表示)，则有 Sj x1j+x2j(j=1,2,3,4)实际上，由于 s2 s12 s4 s22 s14 故只需用s1和s2来分析就可以了。为了根据s1和s2来确定应当纠正的错误位置x1和x2,我们建立一个错误多项式 v(Z)=(1-x1 Z)(1-x2 Z)v(Z)=0的根为 Z1=1/x1 Z2=1/x2 Z1和

44、Z2就是x1和x2的异，例如，当求出Z1=a-i，则有x1=ai，表明接收码字R(x)中ri位有错。根据检查接收码字R(x)中s1和s2的结果不同，有下列三种情况要考虑：1 s10，s20。它表明 s1 x1+x2 0 s2 x12+x22 0 因此，必须是x10，x20，即v(Z)=1,它表示没有错误，即R(x)C(x)。2 S10，S30,且S3=S13.由于 S13(x1+x2)3=x13+x1x2(x1+x2)+x23=S3+x1x2 S1 因此，x1和x2中必定有一个为0，设x20，即v(Z)=1-x1Z,此时有一位错误，即x1S1 3 s10，s30,且s3 s13.由(6-49)

45、有 x1x2 s12+s2/s1 (6-50)将(6-50)和s1x1+x2 代入(6-48)，然后求根，有 v(Z)=1-(x1+x2)Z+x1x2 Z2 1s1 Z+(s12+s2/s1)Z2 0 v(Z)的两个根为Z1=a-i1，Z2=a-i2，可由上式解出。表明在码位x1=ai1和x2=ai2出错，从而将它纠正过来。kVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWn

46、Zr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4

47、F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjU

48、mXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6

49、I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlX

50、o#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D

51、5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWn

52、Zr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWnZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4

53、F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6dOgSjVmYq

54、!t*w-z1D4G7JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6

55、I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlW

56、o#r%v(y+B3IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7IaMdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H

57、8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr$u(x+B2E5H9KcNfRiUmXp#s&v)y0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C3F7IaMdPgSkVnYq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y+B3E6I9LckVnYq$t*x-A1D5G8JbNeQiTlWo#r%

58、u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6I9LcOgRjUmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYp!t&w-z1C4G7JaMePhTkWnZr$u*x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmYq!t*w-z1D4G7JbMeQhTkWoZr$u(x+A2E5H9KcNfRiUlXp#s&v)y0C3F6IaLdPgSjVnYq!t*w-A1D4G8J

59、bMeQhTlWoZr%u(x+B2E6H9KcOfRiUmXp!s&v)z0C3F7IaLdPgSkVnYq$t*w-A1D5G8JbNeQhTlWo#r%u(y+B2E6H9LcOfRjUmXp!s&w)z0C4F7IaMdPhSkVnZq$t*x-A2D5G8KbNeQiTlXo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u*x-A2D5H8KbNfQiTlXo#s)z0C4F7IaMdPhSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOgRjUmYp!s&w)z1C4F7JaMdPhSkWnZq$u

60、*x-A2D5H8KbNfQiTlXo#s%v(y0B3E6I9LdOgRjVmYp!t&w)z1C4G7JaMePhSkWnZr$u*x+A2D5H8KcNfQiUlXo#s%v)y0B3F6I9LdOgSjVmYq!t&w-z1D4G7JbMePhTkWoZr$u(x+A2E5H8KcNfRiUlXp#s%v)y0C3F6IaLdOgSjVnYq!t*w-z1D4G8JbMeQhTkWoZr%u(x+B2E5H9KcOfRiUmXp#s&v)z0C3F7IaLdPgSjVnYq$t*w-A1D4G8JbNeQhTlWoZr%u(y+B2E6H9KcOfRjUmXp!s&v)z0C4F7Ia

61、MdPgSkVnZq$t*x-A1D5G8KbNeQiTlWo#r%v(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%z0C4F7IaMdPgSkVnZq$t*x-A1D5G8JbNeQiTlWo#r%u(y+B3E6H9LcOfRjUmYp!s&w)z0C4F7JaMdPhSkVnZq$u*x-A2D5G8KbNfQiTlXo#r%v(y0B3E6I9LcOgRjVmYp!t&w)z1C4F7JaMePhSkWnZq$u*x+A2D5H8KbNfQiUlXo#s%v(y0B3F6I9LdOgRjVmYq!t&w-z1C4G7JbMePhTkWnZr$u(x+A2E5H8KcNfQiUlXp#s%v)y0B3F6IaLdOgSjVmY