第6章信道编码(4)

6.4循环码,6.4.1循环码基本概念6.4.2循环码的生成矩阵和监督矩阵6.4.3循环码的编码6.4.4循环码的译码6.4.5循环码的捕错译码和大数逻辑译码6.4.6BCH码和RS码6.4.7Goppa码,6.4.1循环码基本概念,循环码是线性分组码中最主要、最有用的一类，目前对它的研究和应用也最多。其最引人注目的特点:可以用反馈线性移位寄存器很容易地实现其编码和伴随式计算；由于循环码有许多固有的代数结构，从而可以找到各种简单实用的译码方法。,1957年Prange首先开始研究循环码，此后人们对循环码的研究在理论和实践方面都取得了很大进展。现在循环码已成为研究最深入、理论最成熟、应用最广泛的一类线性分组码。在循环码中BCH码是其中最主要的一大类。汉明码、RM码、Golay码、RS码等均可变换成或纳入循环码内，1970年发现的Goppa码类中有一子类也属于循环码。,将码字C(cn-1,cn-2,c1,c0)的分量循环右移一位就可得到：RC(1)(c0,cn1,cn2,c2,c1)若将C的分量循环右移i位就得到一个n维矢量：RC(i)(ci1,ci2,c1,c0,cn1,ci1,ci)如果将矢量C循环左移1位后就得到：SC(1)(cn2,cn3,c1,c0,cn1)将C循环左移i位后就得到：SC(i)(cni1,cni2,c0,cn1,cni1,cni)对任意i(0in-1),左右循环移位满足：RC(n-i)=SC(i)可见左、右循环移位是彼此等价的。今后在不引起混淆的情况下将它们统称为循环移位。,【例】下表给出的(7,3)分组码的所有8个码字在移位之下是封闭的，所以此码是一个循环码。实际上此例的结论普遍成立，即任意(2r-1，2r-r-1)汉明码都是循环码。,(,)分组码编码表,循环码可用多种方式进行描述，在不同情况下使用不同的描述方式将有助于问题的深入研究，现在介绍如何用多项式去描述循环码。由于任意一个n维矢量C(cn1,cn2,c1,c0)都可以用一个次数不超过n-1的多项式惟一确定,即C(x)cn-1xn1cn-2xn2+c1xc0当C是一个码字时就称C(x)为相应码字的多项式。显然C与C(x)是一一对应的。因此任何一个(n,k)线性分组码都可以等价地看作一类由2k个次数不超过n-1的多项式组成的集合。,码字C循环i次所得码字的码多项式为C(i)(x)=cn-1-ixn-1+cn-i-2xn-2+c0 xi+cn-1xi-1+cn-i将式两边乘以x，再除以xn1得：,码字循环一次的码多项式C(1)(x)是原码多项式C(x)乘x再除以xn+1所得的余式。写作：C(1)(x)xC(x)mod(xn+1)由此可以推知，C(x)的i次循环移位C(i)(x)是C(x)乘xi再除以xn1所得的余式。即：C(i)(x)xiC(x)mod(xn1),循环码的码字i次循环移位等效于将码多项式乘xi后再模xn+1。例(7,3)循环码可由任一码字(如0011101)经过循环移位，得到其他6个非0码字；也可由相应的码多项式x4+x3x21，乘以xi(i1,2,6)，再模x71得到其他6个非0码多项式。,(7,3)循环码的循环移位,根据循环码的循环特性，可由一个码字的循环移位得到其他非0码字。在(n,k)循环码的2k个码多项式中，取前k-1位皆为0的码多项式g(x)(次数rn-k)，再经k-1次循环移位，共得到k个码多项式：g(x),xg(x),xk1g(x),这k个码多项式显然是相互独立的，可作为码生成矩阵的k行，于是得到(n，k)循环码的生成矩阵G(x)为,6.4.2循环码的生成矩阵和监督矩阵,码的生成矩阵一旦确定，码就确定了。这就说明，(n,k)循环码可由它的一个(n-k)次码多项式g(x)来确定，所以说g(x)生成了(n,k)循环码，因此称g(x)为码的生成多项式，即：g(x)gnxnkgnk1xnk1+g1xg0如果码C具有生成多项式g(x)，那么此码一定是循环码。g(x)有如下的性质：(1)在(n,k)循环系统码中存在一个(n-k)次码多项式。因为在2k个消息组中，有一个消息组为0001，它的对应码多项式的次数为n-1-(k-1)n-k,(2)在(n,k)循环码中，n-k次码多项式是最低次码多项式。,若g(x)不是最低次码多项式，那么设更低次的码多项式为g(x)，其次数为n-k-1。g(x)的前面k位为0，即k个信息位全为0，而监督位不为0，这对线性码来说是不可能的。因此g(x)是最低次的码多项式，且gnk1，g01，否则g(x)经n-1次左移循环后将得到低于nk次的码多项式。,(3）在(n,k)循环码中，g(x)是惟一的n-k次多项式。如果存在另一个n-k次码多项式，设为g(x)，根据线性码的封闭性，则g(x)g(x)也必为一个码多项式。由于g(x)和g(x)的次数相同，它们的和式的n-k次项系数为0，那么g(x)g(x)是一个次数低于n-k次的码多项式，前面已证明g(x)的次数是最低的，因此g(x)不能存在，所以g(x)是惟一的n-k次码多项式。,(4)在(n,k)循环码中，每个码多项式C(x)都是g(x)的倍式，而每个为g(x)倍式且次数小于或等于n-1的多项式，必是一个码多项式。设M(mk1,mk2,m0)为任一信息组，G(x)为该(n,k)循环码的生成矩阵，则相应的码多项式为,(5)任意(n,k)循环码的生成多项式g(x)一定整除1+xn。反过来若g(x)是一个n-k次多项式并且还整除(1+xn)，那么g(x)一定是某个循环码的生成多项式。设信息组为M(mk1,mk2,m0)，则相应的码多项式为C(x)MG(x)(mk1xk1mk2xk2m0)g(x)式中C(x)的次数n-1，M(x)是2k个信息多项式的表示式，所以C(x)即为相应2k个码多项式的表示式。因此g(x)生成一个(n,k)线性码。又因为C(x)是n-k次多项式g(x)的倍式，所以g(x)生成一个(n，k)循环码。,【例】设（7,4）循环码的生成多项式g(x)x3x1，求其生成矩阵G及生成的码字。,即,此生成矩阵G生成的（7,4）循环码的码字如表所示。,（7,4）循环码的编码表,【例】求(7,3)循环码的生成多项式。分解多项式x71，取其4次因式作生成多项式：x7+1(x1)(x3x21)(x3x1)可将一次和任一个三次因式的乘积作为生成多项式，因而可任取：g1(x)(x1)(x3x21)x4x2x1或g2(x)(x1)(x3x1)x4x3x21,因为(n,k)线性码的生成矩阵G和监督矩阵H满足GHT0,循环码也是线性码,如果设g(x)为(n,k)循环码的生成多项式，必为xn1的因式，则有:xn1h(x)g(x)因为g(x)为n-k次多项式，以g(x)为生成多项式，则生成一个(n,k)循环码，以h(x)为生成多项式，则生成(n,n-k)循环码，这两个循环码互为对偶码。称h(x)为(n，k)循环码的校验多项式或监督多项式，且h(x)hkxkhkxkh1xh0,显然，(n,k)循环码也可由其监督多项式完全确定，且hk，h0，则(n,k)循环码的监督矩阵为,式中：h*(x)h(x)的反多项式。,下面以(7,3)码为例说明(n,k)循环码可由监督多项式或生成多项式完全确定。因为x71(x3x1)(x4x2x1)4次多项式为生成多项式:g(x)x4x2x1g4x4g3x3g2x2g1xg03次多项式则是监督多项式：h(x)x3x1h3x3h2x2h1xh0,由等式x71h(x)g(x)两端的同次项系数相等得：x3的系数g3h0g2h1g1h2+g0h30x4的系数g4h0g3h1g2h2g1h30x5的系数g4h1g3h2g2h30x6的系数g4h2g3h30,将方程组写成矩阵形式:,列阵的元素是生成多项式g(x)的系数，是一个码字，那么第一个矩阵则为(7,3)循环码的监督矩阵，即：,第1行是码的监督多项式h(x)的系数的反序排列，而第2,3,4行是第一行的移位，用h*(x)表示h(x)的反多项式，因此可用监督多项式的系数来构成监督矩阵，于是得到:,如：(7,4)码的校验多项式,相应的H矩阵为,定理设C是以g(x)为生成多项式的(n,k)循环码，那么C的对偶码是一个(n,n-k)循环码，这里h(x)(1xn)/g(x)。前面介绍的生成矩阵的循环码不是系统码。不过可以很容易地将其变为系统码。,此矩阵是行满秩矩阵而且还具有系统码生成矩阵的形式。与该生成矩阵所对应的系统循环码的校验矩阵为,循环码的检错能力：能检出全部单个错码。能检查全部离散的二位错。能检查出全部的奇数个错码。能检测所有长度不超过(n-k)的突发错误。在突发长度b大于(n-k)的错误中，若b=n-k+1，则(n-k)循环码不能检测概率为2-(n-k-1)(或能检测的概率为1-2-(n-k-1)；若bn-k+1,则不能检测概率为2-(n-k)(或能检测的概率为1-2-(n-k)。,循环码的检错能力很高。,比如：采用CRC-16或CRC-CCITT的循环码可查出全部单错、双错、奇数位错，全部16位或16位以下突发错误，99.997%的17位突发错误以及99.998%的18位或更长的突发错误。,循环码的主要优点之一：其编码过程很容易用移位寄存器来实现。由于生成多项式g(x)和监督多项式h(x)都可以惟一地确定循环码，因此编码方法既可基于g(x)又可基于h(x)。下面仅给出一种基于生成多项式的具体编码方案。一个系统码形式的(n，k)循环码的编码步骤如下：(1)用xn-k乘以信息多项式M(x)；(2)用g(x)除以xn-kM(x)得到余式b(x)；(3)作码字b(x)xn-kM(x)多项式。,6.4.3循环码的编码,系统码的G矩阵为G=Ikp左边是kk阶单位方阵。这相当于码字多项式的第n-1次至n-k次的系数是信息位，而其余的为校验位，这相当于C(x)=m(x)xn-k+r(x)0(modg(x)式中m(x)=mk-1xk-1+mk-2xk-2+m1x+m0是信息多项式，相应的系数是信息位。r(x)=rn-k-1xn-k-1+rn-k-2xn-k-2+r1x+r0是校验位多项式，相应的系数是码元的校验位。由上式可得r(x)=C(x)+m(x)xn-km(x)xn-k(modg(x),要构造用g(x)生成的系统码：首先必须将信息组乘以xn-k变成xn-km(x)；然后用g(x)除，得到余式r(x)；再将其各项系数取加法逆元，就得到了所要求的校验位。因此，循环码系统码的编码问题就是以g(x)为模的除法问题。,以上三步均可用一个除法电路完成。该电路是一个带反馈的根据g(x)=1+g1x+gn-k-1xn-k-1+xn-k作出的(n-k)级线性移位寄存器。,n-k移位寄存器编码电路,6.4.4循环码的译码,线性码的译码根据接收码字多项式的伴随式和可纠的错误图样间的一一对应关系，由伴随式得到错误图样。因为循环码是线性码的一个特殊子类，且由于循环码的循环特性，致使它的译码更加简单易行。循环码的译码包括三个步骤：计算接收多项式的伴随式;求伴随式对应的错误图样;用错误图样纠错。,1.接收码字伴随式计算1)计算伴随式S设H(hn-k-1,hn-k-2,h0)T，其中hi,in-k-1,n-k-2,0表示H的行矢量。设S(sn-k-1,s0)，根据伴随式定义STHRT，于是得到伴随式各分量的表示式：,这是由接收码字相应分量的直接求和来计算伴随式的方法，对所有线性码都是适用的。译码电路是n-k个多输入的奇偶校验器，每个奇偶校验器的输入端由H阵的相应行hi中的1决定。2)用k级移位寄存器的伴随式计算电路定理二元线性系统码中，接收码字的伴随式S等于对的信息部分所计算的监督码元(相当于对的信息部分重新编码)与接收的监督码元的和。,证明设接收码字R(RIRP)，RI是R的信息部分，它是长度为k的矢量，RP是的监督码元部分，是长为rn-k的矢量，监督矩阵为HQIr，Q为rk阶子阵，Ir为rr阶单位子阵。由伴随式的定义：SRHTRIRPQIRTRIQTRPIRRIQTRpQ是H中除单位子阵外的rk阶子阵，所以RIQT是把RI作信息元重新编码计算的监督元。而Rp为接收的监督元。,用k级移位寄存器的伴随式计算电路,根据定理可得到用k级移位寄存器实现的伴随式计算电路。,工作步骤：(1)门1通，门2,3,4关，接收码字R的k位信息部分输入编码器。(2)门1关，门2,3,4通，接收信息编码所得的监督码元与接收监督码元逐位模2和，得到伴随式。但这种方法只适于线性系统码。,3)用n-k级移位寄存器的伴随式计算电路设接收多项式为R(x)，它的信息部分为RI(x)，监督部分为Rp(x)，由定理知：S(x)R(x)Rp(x)式中：R(x)是对RI(x)重新编码的监督字多项式；若码的生成多项式为g(x)，则S(x)R(x)Rp(x)R(x)(modg(x)循环码接收多项式的伴随式是接收多项式R(x)除以g(x)的余式。,设E(x)为R(x)的错误图样，那么：R(x)C(x)E(x)但C(x)为g(x)的倍式，所以S(x)C(x)十E(x)E(x)(modg(x)该式表明：伴随式是由错误图样决定的，与具体码字无关。应该指出，前面循环码伴随式的表示式是由系统码推出的，但由于伴随式仅与错误图样有关，因而对非系统码也是适用的。,用n-k级移位寄存器计算循环码伴随式的电路：,这是一个n-k级除法求余电路，它与编码除法电路的区别是，由于被除式R(x)不含x的幂的因子，所以接收码字(被除式)应由第一级输入端加入。,由于循环码的循环位移特性，即C(x)乘以x的任一次幂xl，进行模xn1运算，其结果仍是一码多项式。与此相对应，伴随式S(x)也有循环性质。定理设S(x)为接收多项式R(x)的伴随式，则R(x)的循环移位xR(x)(mod(xn+1)的伴随式S(1)(x)等于伴随式S(x)的循环移位xS(x)(modg(x)，即S(1)(x)xS(x)(modg(x)证明由伴随式计算知S(x)R(x)(modg(x)对上式两边作同余运算得xS(x)xR(x)(modg(x)令R(1)(x)xR(x)(mod(xn1),即用R(1)(x)表示R(x)循环移位一次xR(x)(mod(xn1)的码多项式。对上式进行模g(x)运算，则得到R(x)循环移位xR(x)的伴随式S(1)(x)xR(x)(modg(x)即S(1)(x)xS(x)(modg(x)该定理说明：接收码字的循环移位(mod(xn1)运算下)与伴随式在模g(x)运算下(或在除以g(x)的伴随式计算电路中)的循环移位是一一对应的。,.循环码的通用译码法(梅吉特译码法)循环码的译码基本上按线性分组码的译码步骤进行，其循环位移特性使译码电路大为简化。通用的循环码译码器包括三个部分：(1)伴随式计算电路，可根据实际情况选取不同的伴随式计算电路。(2)错误图样检测器。它是一个组合逻辑电路，其作用是将伴随式译为错误图样。(3)接收码字缓存器和模2和纠错电路。,循环码通用译码器,(2)S写入错误图样检测器，并在检测器中循环移位，同时将接收码字移出缓冲寄存器，当检测器输出“1”时，表示缓冲寄存器此时输出符号是错误的，则将该错误纠正。同时，检测器输出反馈到S计算电路的输入端，以修改S，从而消除该错误对S所产生的影响。直到接收码字全部移出缓存器，该接收码字纠错完毕。若最后S寄存器中为全0，则表示错误全部被纠正，否则检出了不可纠的错误图样。,(1)将接收码字移入S计算电路，计算出S,同时将接收码字移入缓冲寄存器。,错误图样检测器的设计：当且仅当错误图样是一个可纠的错误图样，并且此错误图样包含最高阶位上的一个错误时，伴随式计算电路计算出的伴随式才使错误图样检测器的输出为“1”。也就是说，如果该错误图样检测器输出为“1，则认为最高阶位上的接收符号是错误的，应该予以纠正；如果检测器输出“0”，则认为最高阶位上的接收符号是正确的，不必纠正。对于码字中任何位置上的错误，通过码字和伴随式的同时循环移位，当错误符号移到最高阶位上时，伴随式使检测器输出为“1”，将其错误纠正。因而通过循环移位后，能使可纠错误图样中的全部错误都得到纠正。,1.循环码的捕错译码捕错译码是梅吉特通用译码法的一种实用变形，译码器的组合逻辑电路比较简单，对纠一个错误或两个错误的码用捕错译码法译码很有效。改进的捕错译码法(嵩忠雄译码法)可用来纠正两个或三个随机错误的码。捕错译码法一般适用于短码或低码率码的译码，否则将损失一部分纠错能力。然而，捕错译码对于突发错误码的译码也是很有效的。,6.4.5循环码的捕错译码和大数逻辑译码,循环码的捕错译码的基本思想：利用码的循环特性，把错误全部移到监督码元位置上，这时E(x)等于S(x)，因而在求得S(x)后，只需与监督位上的码元相加，就实现了纠错。假设(n,k)循环码是纠错能力为t的系统码。它的码多项式为C(x)cn-1xn-1+cn-2xn-2+c1x+c0其中：cn-1,cn-2,cn-k为信息位；cn-k-1,c1,c0为监督位。令接收多项式为R(x)，错误图样为E(x)en-1xn-1+en-2xn-2+en-kxn-k+en-k-1xn-k-1+e0其中en-1,en-k为信息位的错误值；en-k-1,e0为监督位的错误值。,因为循环码的伴随式可表示为S(x)E(x)(modg(x)假定en-1,en-k全为0，即全部错误限制在n-k个监督位上，则E(x)是一个小于n-k次的多项式(低于g(x)的次数)，此时有：E(x)E(x)(modg(x)即E(x)S(x)该式说明：当R(x)的错误限制在n-k个监督位上时，R(x)的错误图样E(x)等于它的伴随式。即，求得伴随式也就求得了错误图样E(x)。,如果错误并不限制在n-k个监督位上，但限制在n-k个相邻位上，比如在xn-i,xn-i+1,xn-1,x0,x1,xn-k-i-1位上。当R(x)循环移位i次，xn-i位上的错误已移到监督位的末位，错误已全部移到了n-k个监督位上，而R(x)的i次循环移位R(i)(x)的伴随式是S(x)在g(x)除法电路中的i次循环移位S(i)(x),此时R(i)(x)的错误图样等于S(i)(x)，也就找到了R(x)在xn-i,xn-i+1,xn-1,x0,x1,xn-k-i-1位上的错误图样。,t个错误限制在n-k个相邻位上，等效于要求R(x)中有一个相邻k位的无错区间。若n,k,t满足：ntk那么即使t个错误均匀分布，在R(x)中也一定存在相邻k位无错的区间。因此通过循环移位就一定能把R(x)的t个错误移到n-k个监督位上。在循环移位过程中，可用下面的定理判断t个错误是否已全部集中到码的n-k个监督位上。定理设(n,k)循环码的纠错能力为t，如果错误限制在n-k个监督位置上，则伴随式的重量不大于t，如果在信息位上存在错误，则伴随式的重量必大于t。,2.改进的捕错译码法捕错译码法要求接收码字中的错误集中在nk个相邻位上，因此，这种捕错译码法适用于纠突发错误或个和某些两个随机错误(条件是ntk)的码。纠三个或三个以上的随机错误的码一般不满足ntk的条件。然而，改进后的捕错译码法可以用来纠正这样的错误图样，即每个错误图样的大部分错误集中在n-k个相邻位上，而只有少数错误在此n-k位跨距之外。下面讨论由嵩忠雄提出的一种改进方案。,设干扰产生的错误图样为E(x)en-1xn-1+en-2xn-2e0可将其分成两个部分。接收码字信息部分中的错误为EI(x)en1xn1enkxnk接收码字监督部分中的错误为EPen-k-1xn-k-1+e0接收码字的伴随式为S(x)E(x)EI(x)EP(x)(modg(x)则有:EP(x)S(x)+EI(x)(modg(x)令SI(x)EI(x)(modg(x)代入上式得:EP(x)S(x)SI(x),由该式可知：接收码字监督位上的错误图样等于接收码字的伴随式与信息位上错误的伴随式之和。如果对信息位上可能的错型一个一个地进行试验，并确定出某一个为实际错误图样，那么可求出监督位上的错误图样，从而求得接收多项式R(x)的错误图样E(x)。改进捕错译码法的出发点是先确定接收码字信息部分中的错误图样。,这种改进的捕错译码法要求预先找出在k个信息位上的N个确定的错误图样，这N个确定的错误图样应该能包括：当接收码字经过循环移位把大部分错误移到监督位上后，在信息位上的少量错误的各种可能的错误图样。也就是要求找出一组次数小于等于-1的N个多项式，用集合Qj(x),j=1,2,N表示，对于任何可纠正的错误图样E(x)存在一个多项式Qj(x)，使得xn-kQj(x)与E(x)的信息位上错误图样EI(x)一致，或与循环移位后的E(i)(x)的信息位上错误图样E(i)I(x)一致。令SIj(x)xn-kQj(x)(modg(x),如果在k个信息位上的错误图样EI(x)xnkQj(x)或者经过循环移位后在k个信息位上的错误图样E(i)I(x)xn-kQj(x)，那么SIj(x)就是EI(x)或者E(i)I(x)的伴随式。Ep(x)=S(x)+SIj(x)E(i)p(x)=S(i)(x)+SIj(x)若码的纠错能力为t，且错误图样重量为WE(x)t，在k个信息位上的错误图样的重量WEI(x)=WXn-kQj(x)=W(Qj(x)则在n-k个监督位上的错误图样E(i)p(x)的重量为WE(i)p(x)=WS(i)(x)+SIj(x)t-WQj(x),该式表明：xn-kQj(x)是E(i)(x)在信息位上的错误图样。而接收码字的错误图样为E(x)=xn-iE(i)(x)=xn-ixn-kQj(x)+S(i)(x)+SIj(x)将所求得的错误图样E(x)和R(x)模2加，可使R(x)中的错误得到纠正。从错误图样的特定结构出发，由循环码的通用译码法演变出了捕错译码法。而从码的结构出发，可导出大数逻辑译码法。这是一种很有效的译码方法，具有译码设备简单，速度快的优点，因而应用相当广泛。,3.循环码的大数逻辑译码对纠t个错误的(n,k)循环码，梅吉特通用译码法是在错误图样包含有最高阶位xn1上一个错误时，组合逻辑电路输出“1”，从而将其纠正，再利用码的循环特性，可以纠正所有接收符号上的错误。这对纠正一个错误的循环码是比较容易实现的，如果用于纠多个错误的码，组合逻辑电路变得很复杂，而大数逻辑译码法就是利用码的特殊结构使译码电路简化的。下面就来讨论这种译码方法。,设H为(n,k)循环码的一致监督矩阵H=hn-k-1hn-k-2h0T其中:hj,jn-k-1，n-k-2，0是H的行矢量。又设C为任一码字，R=(rn-1,r0)为接收码字，其伴随式STHRT的各分量为,称为接收码字R的监督和式。若R为一个码字，则sj0;若R不是一个码字，则sj0。若E=(en-1,en-2,e0)为R的信道错误图样。由于R=C+E,HCT=0T，所以,接收矢量的监督和式，实际上是对信道错误图样进行监督，而与发送的具体码字无关。若hj,i=1，则说码元位ci被监督和式sj监督。把sn-k-1,sn-k-2,s0称为监督和式组。若在(n,k)循环码的监督和式组中，码元位ci,in-1,n-2,0被J个(Jnk)一致监督和式监督，而其他码元位不被一个以上的监督和式监督，则称此J个监督和式为对码元位ci正交的一致监督和式组。,以(7,3)循环码为例，其监督方程为,即：,码元c6被所有3个监督方程监督，而其他任一码元在3个监督方程中的出现不多于1次，称上式的监督方程正交于c6。,将式改写成矩阵形式：,令,则,称H0为正交一致监督矩阵。其特点是：与正交码元位对应的列全为“1”，其他任一列中“1”的个数不多于一个,称S0=RHT0为正交伴随式。,由于循环码的循环特性，任意码字的循环移位仍是一个码字，也满足正交监督矩阵H0。所以对最高阶码元位cn-1正交的码字C，经过一次循环移位后就变成了对次高阶码元位cn2正交的码字C(1)。不难推知，连续的循环移位可以得到对码字的所有码元达成正交的监督和式。,例如，(7,3)循环码的三个正交监督和式为,S00，S01，S02构成正交伴随式S0=（S02S01S00）。R经过一次循环移位R(1)的正交监督和式为,定理若(n,k)循环码可以构成J个正交于最高阶位xn-1上的一致监督和式A1,A2,AJ，则该码可以用来纠正tJ/2错误的所有错误图样。由此定理可直接得到：在可构成J个正交监督和式的(n,k)循环码中，如果在正交位置上含有错误时，正交伴随式S0的重量WS0J/2；如果在正交位置上没有错误，则WS0J/2。,译码器可用一个大数逻辑门来检测正交伴随式的重量，当WS0J/2时，正交位置上有错；当WS0J/2时，正交位置上无错。即把S0的各分量作为大数逻辑门的输入，当这些输入中多数为“1”时，正交位置上的接收符号是错误的，大数逻辑门输出“1”，将错误纠正；当大数门的输入中只有一半或更少个“1”时，则正交位置上没有错误，大数门输出“0”。再利用码的循环位移特性，可纠正接收字中所含的全部错误(错误个数J2)。这种译码方法称为一步大数逻辑译码法。,6.4.6BCH码和RS码1959年霍昆格姆(Hocgenghem)和1960年博斯(Bose)及查德胡里(Chaudhuri)分别提出的纠正多个随机错误的循环码，称为BCH码。这是一类纠错能力强，构造方便的好码。1960年彼得森(Pelerson)找到了二元BCH码的第一个有效算法，后经多人的推广和改进，于1967年由伯利坎普(Berlekamp)提出了BCH码译码的迭代算法，从而将BCH码由理论研究推向实际应用阶段，使它成为应用广泛而有效的一类线性码。下面先介绍BCH码的定义及其生成多项式，然后介绍应用广泛的ReedSolomon码(RS码)。,1.BCH码在已提出的许多纠正随机错误的分组码中，BCH码是迄今为止所发现的一类很好的码。它的纠错能力很强，且构造方便，对它的分析研究也很透彻。如何构造一个循环码以满足纠错能力为t的要求，这是编码理论中的一个重要课题。BCH码就是针对这一问题提出的。,汉明码是纠一位差错的完备码，它的每一位差错的S(x)都对应于H中的某一列。如果出现两位差错，其S(x)对应于相应的两列之和。这两列之和等于另外的某一列，故无法实现纠错。要增加纠错能力，必须增加码的多余性。BCH码就是在汉明码的基础上，增加H矩阵的行数来提高纠错能力的。下面分析BCH码的生成多项式g(x)。设BCH码的生成多项式g(x)的根为,2,2tGF(2m)则上述2t个元素也必然是任一码字多项式C(x)cn1xn-1cn2xn-2c1xc0的根，即：,cn1(i)n-1cn2(i)n-2c1ic00其中i1，2，2t。可以将这些不同i值的方程组写成矩阵形式:,g(x)m1(x)，m2(x)，m3(x)，m4(x)，m2t(x)m1(x)，m3(x)，m2t(x)在上式中，可不包括下标为偶数的最小多项式。,于是BCH码的H可简化成:,若t1，就得到汉明码的H矩阵。如果ak(1kn-1)是GF(2m)中的本原元，则得到本原BCH码，否称称为非本原BCH码。本原BCH码的码长n2m-1，而非本原BCH码的码长为2m-1的因子。对于本原BCH码，k一般取1，而an-1,an-2,a0这n个元素可用它们相应值的modf(a)余式排成列来表示，其中f(a)为m次本原多项式。,多元BCH码的监督矩阵为,多元BCH码的码元符号取自于多元域GF(q)，q为某一素数的幂，纠t个错误的多元BCH码的生成多项式是以GF(q)的扩域GF(qr)上2t个相邻元素为根的多项式：g(x)(x-a)(x-a2)(x-a2t)式中a，a2，a2t为GF(qr)中2t个相邻元素。由H或g(x)可确定q元本原BCH码。,2.二元BCH码码元符号取自于二元域GF(2)纠t个错误的二元BCH码的生成多项式是以GF(2)的扩域GF(2m)上2t个相邻元素为根的多项式。设a为GF(2m)的本原元，t为正整数，g(x)是GF(2m)中d-1个相邻元素:a，a2，a3，ad1,d2t1为根的最低次二元多项式，则以g(x)为生成多项式的循环码，称为二元本原BCH码。为了说明上面定义的意义，先给出下面的定理。,定理本原BCH码的最小距离dmind(d-1是g(x)相邻根的个数)。该定理表明，要构造一个码距为d的二元BCH码，则要求生成多项式g(x)以GF(2m)中相邻元素a，a2，ad1为根。然而GF(2m)中每个元素的最小多项式就是以该元素为根的最低多项式。那么生成多项式g(x)要以这些元素为根，则g(x)必以这些元素的最小多项式为因式。也就是说，g(x)应是a，a2，,ad1的最小多项式的最小公倍式。即：g(x)LCMm1(x),m2(