《编码理论》课件第7章

第7章循环码7.1循环码的多项式表述7.2循环码的矩阵表述7.3循环码的编码7.4循环码的译码7.5捕错译码及大数逻辑译码7.6

BCH码7.7

RS码及Goppa码 7.1循环码的多项式表述

7.1.1基本概念

将—个n维码字C＝cn－1cn－2...c1

c0的分量循环右移一位表示为RC(1)，则RC(1)＝c0cn－1

cn－2…c2

c1

若将C的分量循环右移i位表示为RC（i），则RC(i)＝ci－1ci－2...c1cocn－1...ci＋1ci

（7-1）如果将码字C循环左移1位表示SC（1），则SC（1）＝cn－2cn－3...c1

c0cn－1

同样如果将码字C循环左移i位后就得到：SC（i）＝cn－i－1cn－i－2…，cocn－1…cn－i＋1cn－i

（7-2）不难验证对任意i(0≤i≤n一1)由(7-1)式和(7-2)式定义的左、右循环移位满足：RC（n—i）＝SC（i）

可见左、右循环移位在(7-3)式的含义下是彼此等价的。今后在不引起混淆的情况下将它们统称为循环移位。

设C是一个(n，k)线性码，如果C中的任意一个码字经任意循环移位之后仍然是C中的一个码字，那么就称此码是—个循环码。

循环码的描述方式有多种多样，在不同情况下使用不同的描述方式将有助于问题的深入研究，现在介绍如何用多项式去描述循环码。

由于任意一个n维码字C＝cn－1cn－2...c1c0都可以用—个次数不超过n—1的多项式描述，即:C(x)＝cn—1xn－1＋cn—2xn－2十…十clx＋c0

(7-4)称C(x)为相应码字的多项式。显然C与C(x)是一一对应的，因此任何一个GF（2）(n,k)线性分组码都可以等价地看作一类由2k个次数不超过n一1的多项式组成的集合。

码字C循环i次所得的码多项式为：C（i）(x)＝cn－1－ixn－1＋cn－i－2xn－2＋...＋c0xi＋cn－1xi－1

＋...＋cn－i

(7-5)将式(7-46)乘以x，再除以xn＋1得：（7-6）式(7-6)表明，码字循环一次的码多项式C（1）(x)是原码多项式C(x)乘x除以xn＋1的余式。写作：

由此可以推知，C(x)的i次循环移位C（i）(x)是C(x)乘xi除以xn＋l的余式。即：C1(x)xC(x)mod(xn＋1)C（i）(x)xiC(x)mod(xn＋1)(7-7)循环码的码字的i次循环移位等效于将码多项式乘xi后再模xn＋1。式(7-7)揭示了(n，k)线性码中码字多项式与码字循环移位之间的关系,它对循环码的研究起着重要作用。

定理7-1在以多项式为模的剩余类全体所构成的n维线性空间中，其一个k维子空间是一个循环子空间（循环码）的充要条件为是一个理想。

由定理7-1可知，一个（n，k）循环码的码字多项式都是模运算下多项式剩余类环中的一个理想，而且一定是一个主理想子环。反之，多项式剩余类环的一个主理想子环也一定生成一个循环码。

[例7-1]GF(2)中的（7,3）循环码，可由任一个非零码字，比如0011101经过循环移位，得到其它6个非0码字；也可由相应的码多项式x4十x3＋x2＋l，乘以xi(i＝1，2，…，6)，再模x7＋1运算得到其它6个非0码多项式。这个移位过程和相应的多项式运算如表7-1所示。表7-1(7，3)循环码的循环移位7.1.2循环码的生成方法

定理7-2

设为次数小于n的多项式集合，本原多项式xn-1。中的一个码组C是循环码的充分必要条件是C满足下列条件：(1)(2)

证明：充分性（1）假设C是中的一个循环码。因为循环码是线性分组码的一个子集，故第一个条件满足。

(2)设

乘以x后对应于一个循环移位。但因为一个循环码字的循环移位还是一个合法码字，即x·a(x)∈C，x·(xa(x))∈C,依此类推，所以

也在C中，因每一个被加数也在C中。

必要性。假定（1）和（2）都满足。把r(x)看做一个常量，则C是线性的。在条件（2）中令r(x)=x，这表明每个循环移位都会产生一个码字,因此表明C是个循环码。(7－8)下面介绍一种循环码的生成方法,即用到目前为止建立起来的数学工具如何构造循环码。设为次数小于n的多项式集合，本原多项式f(x)=xn-1,生成一个循环码步骤

(1)在中取一个多项式;

(2)用中的所有多项式乘以后模

xn-1得到一个多项式集合;

(3)多项式集合对应一个分组长度为n的循环码码字的集合。

【例7－2】设GF(2)上的R3中的多项式f(x)=1+x2。一般地,R3中的一个多项式可以表示为r(x)=r0+r1x+r2x2，其中系数ri∈GF(2),i=1,2,3。因此，定义在GF(2)上的R3中的多项式有2×２×２=8个，它们分别为0、1、x、x2、1+x、1+x2、x+x2、1+x+x2。要生成一个循环码，用R3中的这8个元素去乘以f(x)，然后将结果模x3-1，得

故只有4个不同的码字多项式：｛01+x1+x2x+x2｝，它们对应的码字为｛000011101110｝。7.1.3多项式描述

1.生成多项式

根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在(n，k)循环码的2k个码字中，取前k—1位皆为0的码字g(x)(其次数r＝n—k)，再经k—1次循环移位，共得到k个码字：g(x)，xg(x)，…,xk－1g(x)。这k个码字显然是相互独立的，这就说明，(n，k)循环码可由它的一个(n—k)次码多项式g(x)来确定，所以说g(x)生成了(n，k)循环码，因此称g(x)为码的生成多项式，即：

g(x)＝gn－ｋxn－k＋gn－k－1xn－k－1十...十g1x＋go(7-9)2.生成多项式的性质

GF(2)中g(x)有如下的性质：

(1)在(n，k)循环系统码中存在一个(n－k)次码多项式；

因为在2k个信息组中，有一个信息组为，它的对应码多项式的次数为n一1一(k一1)＝n－k

(2)在(n，k)循环码中，n—k次码多项式是最低次码多项式,且gn－k＝1，g0＝1。

若g(x)不是最低次码多项式，那么设更低次的码多项式为g＇(x)，其次数为n—k—1。g＇(x)的前面k位为0，即k个信息位全为0，而监督位不为0，这对线性码来说是不可能的。因此g(x)是最低次的码多项式，且gn－k＝1，g0＝1，否则g(x)经n—1次左移循环后将得到低于n－k次的码多项式。

(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的多项式，必是一个码多项式。

由定理7-2可知结论是显然的。

(5)任意(n，k)循环码的生成多项式g(x)一定整除1＋xn。反过来若g(x)是一个n—k次多项式并且还整除(1＋xn)，那么g(x)一定是某个循环码的生成多项式。

因此，当求一个(n，k)循环码时，只要分解多项式xn＋1，从中取出(n—k)次因式作生成多项式即可。

[例7-3]求(7，3)循环码的生成多项式。

分解多项式x7＋1，取其4次因式作生成多项式:

x7十l＝(x＋1)(x3＋x2＋1)(x3＋x＋1)

可将一次和任一个三次因式的乘积作为生成多项式，因而可任取:

gl(x)＝(x＋1)(x3＋x2＋1)＝x4＋x2＋x＋1

或g2(x)＝(x＋1)(x3＋x＋1)＝x4＋x3＋x2＋1

3.监督多项式

如果设g(x)为(n，k)循环码的生成多项式，必为xn＋1的因式，则有:

xn＋1＝h(x)·g(x)

因为g(x)为n—k次多项式，以g(x)为生成多项式，则生成一个(n，k)循环码，以h(x)为生成多项式，则生成(n，n—k)循环码，这两个循环码互为对偶码。称h(x)为(n，k)循环码的校验多项式或监督多项式,且

h(x)＝hkxk＋hk－１xk－１＋…＋hlx＋ho

（7-10）

7.2循环码的矩阵表述

7.2.1生成矩阵

生成多项式可以生成k个相互独立的码字，这k个码字可作为码生成矩阵的k行，于是得到(n,k)循环码的生成矩阵G,即（7-12）

【例7－4】设（7，4）循环码的生成多项式g(x)＝x3＋x＋1，求其生成矩阵G。

解由式(7－12)得:由此生成矩阵G可以生成（7，4）循环码的码字。另利用多项式

C(x)=u(x)g(x)

也可求出对应码字,其中u(x)为信息多项式。【例7－4】设（7，4）循环码的生成多项式g(x)＝x3＋x＋1，求其生成矩阵G。

解由式(7－12)得:

由此生成矩阵G可以生成（7，4）循环码的码字。另利用多项式

C(x)=u(x)g(x)

也可求出对应码字,其中u(x)为信息多项式。7.2.2监督矩阵

循环码的校验多项式或监督多项式为

h(x)＝hkxk＋hk－１xk－１＋…＋h1x＋h0，则(n，k)循环码的监督矩阵为(7－13)式中：h*(x)为h(x)的反多项式。【例7－5】求GF(2)中(7，3)循环码的监督矩阵。

解因为x7＋1＝(x3＋x＋1)(x4＋x2＋x＋1)4次多项式为生成多项式:g(x)＝x4＋x2＋x＋1＝g4x4＋g3x3＋g2x2＋glx＋go

3次多项式则是监督多项式：h(x)＝x3＋x＋1＝h3x3＋h2x2＋hlx＋ho

由式(7-13)得(7，3)循环码的监督矩阵：7.2.3检错能力

循环码特别适合于检测错误，一则因它有很强的检错能力，二则因编码器和错误检测电路都很容易实现，而且还能检查出位数相当长的突发差错。下面简要讨论循环码的检错能力。

(1)能检出全部单个错码。设码组中第i位上有单个错码，则对应的错码多项式为xi，而任何多于一项的生成多项式，它的x0项为1，因此xi除以g(x)的余数必定不为0，即能检出全部单个错码。

(2)能检查全部离散的二位错

设码组中第i和第j位错码，且i<j<n，则错码多项式为：xj＋xi＝xi（1＋xj－i）。因为多于一项的g(x)必定不能除尽xi，所以，只要选取的g(x)是不能除尽(xj－i十1)，且其阶(n－k)>(j－i)，就能检查出全部二位错码。

(3)能检查出全部的奇数个错码。由于具有奇数项错码的多项式必不含有因子(x＋1)，所以只要选取的g(x)含有(x＋1)因子，错码多项式不能被g(x)整除，即能检出全部奇数个错码。

(4)能检测所有长度不超过(n－k)的突发错误

长度不大于b的突发错误的错码多项式可表示为：E（x）＝xi（eb－1xb－1＋eb－2xb－2＋...＋e1x＋1）＝xiE1(x)(7-14)其中E1(x)为不高于(b－1)项的多项式。如果g(x)不能除尽E(x)，则这种突发错误就可检测出来。由于已知g(x)不能有x作因子，而且多于一项的g(x)必定除不尽xi，因此，只有它能除尽E1(x)才能除尽E(x)。但是g(x)为(n－k)次多项式，而E1(x)的次数(b－1)只要不超过(n－k－1)次，即g(x)的次数比E1(x)的高，g(x)就一定除不尽E1(x)。因此，能检测长度不超过(n－k)的突发错误。(5)在突发长度b大于(n－k)的错误中，若b＝n－k＋1，则(n，k)循环码不能检测概率为2－(n－k－1)(或能检测的概率为[1－2－(n－k－1)])；若b>n－k＋1，则不能检测概率为2－(n－k)(或能检测的概率为[1—2－(n－k)])。

设错码多样式为E(x)＝xiE1(x)，其中式E1(x)的次数为(b—1)。

因为E1(x)中必有x0和xb－1项，所以还应有b－2项xj，其中0<j<b－1，这b－2项的系数为0或1，因此，共有2b－2种不同的多项式E1(x)。只有当E1(x)有g(x)的因子时，这种错码才不能被检测出来，即这时应有：E1(x)＝g(x)Q(x)因为g(x)为(n—k)次的，所以Q(x)必为b－1－(n－k)次。如b－1＝n－k(即b＝n－k＋1)，则Q(x)＝1。这时只有一个E1(x)错误图样是不可检测的，即E1(x)＝g(x)，所以它占不可检测的突发错误总数的1/2b－2＝2－（n－k－1），即可作为不能检测概率。

如果b－1>n－k，那么Q(x)应含有x0和xb－1－（n－k）项，其中有b－2－(n－k)项可具有任意的系数，0或1。所以，Q(x)有2b—2—(n－k)种不可检测的错码图样，它占的比例为2b-2-(n-k)/2b-2=2-(n-k)，即可作为不能检测概率。

以上可见循环码的检错能力是很高的。例如采用CRC-16或CRC-CCITT的循环码可以查出全部单错、双错、奇数位错，全部16位或16位以下突发错误，99．997％的17位突发错码以及99．998％的18位或更长的突发错码。 7.3循环码的编码

7.3.1编码原理

1.编码原理

由于生成多项式g(x)和校验多项式h(x)都可以唯一地确定循环码，因此编码方法既可基于g(x)又可基于h(x)。下面仅给出基于生成多项式的具体编码方案。设信息多项式:u(x)=uk－1xk－1＋uk－2

xk－2＋…＋uo

（7－16）一个非系统码形式的(n，k)循环码的码字多项式C(x)=u(x)g(x),所以非系统码的编码可以用一个乘法器实现。一个系统码形式的(n，k)循环码的码字多项式为C(x)=xn-ku(x)+r(x)=uk－1xn－1＋uk－2xn－2＋…＋uoxn-k+rn-k-1xn-k-1+…+r1x+r0

（7-17）式中：r(x)——监督元对应的多项式，即r(x)≡xn-ku(x)(modg(x))(7-18)一个系统码形式的(n，k)循环码的编码步骤为：

(1)用xn－k乘信息多项式u(x)；

(2)按式(7-18)求余式r(x);

(3)作码字c(x)=xn-ku(x)＋r(x)。

2.多项式乘法运算电路

设GF(p)域两个次数分别是k次、r次的二元多项式为a(x)和b(x),即a(x)=a0+a1x+…+akxk

(ai∈GF(p);i=0,1,2,…,k)(7-19)(7-20)两个多项式相乘得到

（7-21）式(7-21)中系数的乘法运算和加法运算都是模p运算。从式(7-21)看到，多项式c(x)的最高次项系数是a(x)、b(x)各自最高次项的乘积，c(x)的次高次项系数等于a(x)最高次项系数与b(x)次高次项系数之积加上b(x)最高次项系数与a(x)次高次项系数之积，…，以此类推，c(x)最低次的常数项等于a(x)常数项与b(x)常数项之积。由此想到，如果把a(x)，b(x)和c(x)的系数单独抽出来组成三个p进制序列A，B，C，那么C恰好是A和B的卷积，体现这种关系的卷积电路也就是所需要的乘法电路，乘法运算的电路实现如图7-1所示。图7－1乘法电路

【例7－6】已知GF(2)上的多项式a(x)=x3+x和b(x)=x3+x+1，求它们的乘积c(x)=a(x)b(x)及相应的乘法电路。

解分别将a(x)和b(x)的系数抽出，得到两个二进制序列A=a3a2a1a0=1010和B=b3b2b1b0=1011。将序列A由高到低依次输入。随着时钟脉冲的输入，接着的一步步运算(模2)如下：

第1拍：A序列右移一位，此拍的输出就是c(x)最高次项的系数c6，是上下对应位求积后相加,即c6=a3·b3=1⊙1=1。

第2拍：A序列再右移一位，输出c5=a3b2+a２b3=1⊙0⊙0⊙1=0。第3拍：A序列再右移一位,输出c4=a3b1+a2b2+a1b3=1⊙1⊙0⊙0⊙1⊙1=0。

依次类推，直到最后的第7拍，输出c0=a0b0=1⊙0=0。

7拍中的累计输出是C=［c6c5c4c3c2c1c0］=［1001110］，序列对应的多项式c(x)是：c(x)=x6+x3+x2+x。

根据上面的运算过程，可设计出乘法电路如图7－2所示。图7－2乘法电路

【例7－7】已知二元多项式a(x)=1+x+x4和b(x)=1+x2，设计其乘法电路。

解c(x)=a(x)b(x)=1+x+x2+x3+x4+x6其电路实现框图如图7－3所示。图7－3乘法电路实现框图

3.多项式除法运算电路

设GF(p)域两个次数分别是n次、r次的多项式a(x)和b(x)为:a(x)=a0+a1x+…+anxn（ai∈GF(p)；i=0,1,2,…,n）n≥r)(7-22)(7-23)两个多项式相除得到:(7－24)式中：q(x)——a(x)除以b(x)的商式；r(x)——a(x)除以b(x)的余式。图7－4多项式除法运算电路

【例7－8】已知二元域多项式 及 ，求a(x)除以b(x)的余式r(x)及实现电路。

解将a(x)除b(x)得商p(x)=x3+1，余数r(x)=x2。据此设计除法运算电路如图7－5所示。

这是一个线性反馈移位寄存器。每单位时间(拍)中，D3的内容在输出的同时反馈回移存器各位。初始时移存器D1D2D3=000，其工作过程为：

第1、2、3拍：顺序输入a6=1，a5=0，a4=1(高位先)，输出000，反馈输入也是000。第3拍结束时，移存器内容D1D2D3=101。第4拍：输入a3=0，移存器D1D2D3的输出分别是101。Ｄ3的输出就是除法电路的输出q3=1，也就是反馈电路的输入。反馈信号q3通过反馈线将q3·b=1(b0b1b2)=110加到输入及移存器D1D2输出端，

运算结果010+110=100就是第4拍结束时移存器D1D2D3的值。

同理得，第5拍输入a2=1，除法电路输出q2=D3=0，第5拍结束时移存器D1D2D3的值为110；第6拍输入a1=1，除法电路输出q1=0，第6拍结束时移存器D1D2D3的值为111；第7拍输入a0=1，除法电路输出q0=1，第7拍结束时移存器D1D2D3的值为001。

第8、9、10拍：中断反馈(反馈开关位置从S1变到S2，将移存器内容(r0r1r2)逐位输出(高位先)，每拍一位。从第4拍到第10拍的输出依次是q3q2q1q0r2r1r0，前4位是商，后3位是余数。

【例7－9】设二元多项式a(x)和b(x)分别为a(x)=x5+x4+x2+1和b(x)=x3+x+1，根据多项式相除的长除法运算可得：a(x)=(x2+x+1)b(x)+x2，其中，商多项式q(x)=x2+x+1，余式r(x)=x2。完成上述两个多项式相除的运算电路如图7－5所示。图中移位寄存器的工作过程如表7－2所示。图7－5除法运算电路表7－2例7－9移位寄存器的工作过程

【例7－10】设a(x)=x4+x+1，b(x)=x3+x2+1，设计完成两个多项式相除的运算电路。

解两个多项式相除，商为x+1，余数为x2，完成上述两个多项式相除的运算电路如图7－6所示。

表7－3给出了除法电路的运算过程。运算开始前所有的触发器清零。随着第一个时钟节拍的到来，运算开始，被除式a(x)的系数a4a3a2a1a0=10011按节拍依次输入，先输入a4，最后输入a0，移位寄存器内容也随输入而不断改变。运算结束时，输出的商为00011，即x+1，移位寄存器中的内容D3D2D1=100，即余式为x2。表7－3除法电路的运算过程

图7－6除法电路7.3.2编码实现电路

系统循环码的编码方法是：首先将信息元多项式u(x)乘以xn-k成为xn-ku(x),然后将xn-ku(x)除以生成多项式g(x)得到余式r(x)，该余式就是校验元多项式，从而可得码字多项式c(x)=xn-ku(x)+r(x)。

用电路实现编码时可以采用以g(x)为除式的除法电路。该电路是一个带反馈的根据生成多项式g(x)＝1＋g1x+…＋gn－k－1xn－k－1+xn－k作出的n-k级线性移位寄存器编码电路，如图7－7所示。图7－7

n－k级线性移位寄存器编码电路编码运算过程如下：

第1步：门打开后，k位信息数据u0，u1，…，uk－1移入线路中，同时送入通信信道。消息从线路的

前端移入（等价于用xn－k左乘u(x))。一旦k位消息全部移入线路，在寄存器中的n-k个数据就构成了余项，它们就是校验数据。

第2步：开关关上后，断开反馈连线。

第3步：移出校验元并把它们送入信道。这n-k个一致校验元b0，b1，…，bn－k－1与k个信息元一起构成一个完整的码字。

【例7－11】

(7，4)循环码的g(x)=x3+x2+1,试设计其编码电路。给出当输入u(x)=1+x3时的编码过程。

解图7－8所示为生成多项式的编码电路。该电路在除法电路的基础上，将输入信息元组u(x)从n-k个寄存器的高端送入，相当于u(x)乘以xn-k。移位脉冲cp在1～k个节拍内，S1、S2打向“1”，各信息元直接经S1输出，成为系统码的前k个码元；同时它们又依次进入除法电路，进行xn-ku(x)除以g(x)的运算。运算结束时留在移位寄存器中的存数就是余式r(x)的系数。然后，cp在(k+1)～n个节拍内，S1、S2打向“2”，使移位寄存器中的各校验元依次输出，形成了一个长为n的码字。图7－8

(7，4)循环码编码器电路表7－4

(7，4)循环码编码过程

7.4循环码的译码

7.4.1译码原理

对线性码进行译码时，根据接收码字多项式的伴随式和可纠的错误图样间的一一对应关系，可由伴随式得到错误图样。循环码是线性码的一个特殊子类，且由于循环码的循环特性，致使它的译码更加简单易行。循环码的译码包括以下三个步骤：计算接收多项式的伴随式，求伴随式对应的错误图样，用错误图样译码。（7-25）这是由接收码字相应分量直接求和计算伴随式的方法，对所有线性码都是适用的。

2．用k级移存器的伴随式计算电路

定理7－3二元线性系统码中，接收码字Ｒ的伴随式S等于对Ｒ的信息部分所计算的监督元(相当于对Ｒ的信息部分重新编码)与接收的监督元的矢量和。

证明设接收码字R＝［RI|RP］，RI是R的信息部分，它是长度为k的矢量，RP是Ｒ的监督元部分，是长为r＝n－k的矢量，监督矩阵为H＝［Q|Ir］，Q为r×k阶子阵，Ir为r×r阶单位子阵。由伴随式的定义：

Q是H中除单位子阵外的r×k阶子阵，所以RIQT是把RI作信息元重新编码计算的监督元。而Rp为接收的监督元。证毕。S＝RHT＝[RI︱RP][Q︱IR]T＝RIQT＋RPIR＝RIQT＋Rp

（7－26）图7－9用k级移存器实现的伴随式计算电路该电路的工作步骤如下：

(1)门1通，门2、3、4关，接收码字R的k位信息部分输入编码器。

(2)门1关，门2、3、4通，接收信息编码所得的监督元与接收监督元逐位模2加，得到伴随式。但这种伴随式计算方法只适于线性系统码。

3．用n－k级移存器的伴随式计算电路

设接收多项式为R(x)，它的信息部分表示为RI(x)，监督部分表示为Rp(x)，由定理7－3知：S(x)＝R＇(x)＋Rp(x)(7-27)式中：R′(x)是对RI(x)重新编码的监督元多项式。若码的生成多项式为g(x)，则S(x)≡RI(x)＋Rp(x)R(x)(modg(x))(7-28)式(7-28)表明，循环码接收多项式的伴随式是接收多项式R(x)除以g(x)的余式。设E(x)为R(x)的错误图样，那么：R(x)＝C(x)＋E(x)（2-29）但C(x)为g(x)的倍式，所以S(x)≡[C(x)十E(x)]≡

E(x)(modg(x))(7-30)式(7－30)也表明了伴随式是由错误图样决定的，与具体码字无关。应该指出，循环码伴随式的表示式(7－28)虽由系统码推出，但由于伴随式仅与错误图样有关，因而对非系统码也是适用的。图7-10n—k级移存器的伴随式计算电路

定理7－4设S(x)为接收码字R(x)的伴随式，则R(x)的循环移位xR(x)(modxn+1)的伴随式S（1）(x)等于伴随式S(x)的循环移位xS(x)(modg(x)),即S（1）(x)≡xS(x)(modg(x))（7－31）证明由伴随式计算式(7－28)知S(x)≡R(x)(modg(x))x（1）S(x)xR(x)(modg(x))对上式两边作同余运算得（7－32）令（7－33）即用R（1）(x)表示R(x)循环移位一次xR(x)(mod（xn＋1）)的码多项式。对式(7-33)进行模g(x)运算，则得到R(x)循环移位xR(x)的伴随式（7－34）考虑到式(7-32)，则有证毕7.4.3梅吉特译码

循环码的译码基本上按线性分组码的译码步骤进行，其循环位移特性使译码电路大为简化。通用的循环码译码器如图7－11所示。包括三个部分：

(1)伴随式计算电路，可根据实际情况选取不同的伴随式电路。

(2)错误图样检测器,是一个组合逻辑电路，其作用是将伴随式译为错误图样。它是这样设计的：当且仅当错误图样是一个可纠的错误图样，并且此错误图样包含最高阶位上的一个错误时，伴随式计算电路计算得到的伴随式才使检测电路输出为“1”。也就是说，如果错误图样检测器输出为“1”，则认为最高阶位上接收符号是错误的，应该予以纠正；如果检测器输出“0”，则认为最高阶位上的接收符号是正确的，不必纠正。对于码字中任何位置上的错误，通过码多项式和伴随式同时循环移位，当错误符号移到最高阶位上时，伴随式则使检测器输出为“1”，将其错误纠正。因而通过循环移位后，能使可纠错误图样中的全部错误都得到纠正。

(3)接收码多项式缓存器和模2加纠错电路。图7－11通用循环码译码器整个译码电路的工作过程如下：

(1)将接收码多项式移入伴随式计算电路，计算出伴随式,同时将接收码多项式移入缓存器。

(2)将伴随式写入错误图样检测器，并在检测器中循环移位(modg(x))，同时将接收码多项式移出缓存器，当检测器输出“1”时，表示缓存器此时刻的输出符号是错误的，并将错误纠正。同时检测器输出反馈到伴随式计算电路的输入端，去修改伴随式，从而消除该错误对伴随式所产生的影响。直到接收码多项式全部移出缓存器，该接收码多项式纠错完毕。若最后伴随式寄存器中为全“0”，则表示错误全部被纠正；否则，检出了不可纠的错误图样。

【例7－12】已知g(x)=x3+x+1,画出二进制(7，4，3)汉明循环码的梅吉特译码电路。

解汉明码纠错能力为t=1，可纠正的差错图样有7个：E(x)=1,x,x2,x3,x4,x5,x6（重量为1)。采用梅吉特译码器时，只要能纠正一个可纠正差错图样，比如E=［1000000］或多项式E(x)=x6，就可以通过该可纠正图样的循环纠正同类的其他差错图样。由于所有可纠正差错图样视为E=［1000000］循环移位而来，因此设计的译码逻辑电路只要能识别与E=［1000000］对应的伴随式101或s(x)=x2+1即可,相应的电路图如图7－12所示。图7-12循环码的梅吉特译码电路译码逻辑电路由3路与门构成，中间1路带“非”。只有当s2s1s0=101时，与门输出才为“1”。

假设差错图样是E=［0001000］,即E(x)=x3，在前7个时钟周期，接收码多项式分两路同时输入g(x)除法器和7级缓存器。第7拍结束时，除法器D3D2D1中包含的伴随式s2s1s0是011。从第8拍到第14拍，输入端恒为0，除法器在每一时钟周期右移作一次除法；7级缓存器则右移一位，与译码逻辑电路的输出模2加后即是译码结果。如果译码逻辑电路判断7级缓存器最高位有错，译码逻辑将输出“1”，在下一拍最高位输出时通过模2加对该位作纠正运算。例7－12的各节拍中，除法器保存的伴随式、译码逻辑值及输出信号如表7－5所示。表7－5梅吉特译码器的循环纠错

表7-5说明:与门输出由上拍s2s1s0决定,对应的差错图样r6r5r4r3r2r1r0中的最高位是缓存器下一输出位。

例7-12中的译码器称为无反馈的梅吉特译码器。事实上，还有一种反馈型的梅吉特译码器如图7-13所示，它能更充分地利用码的循环特性(以时间换电路复杂性)。与无反馈型相比，它有两处不同：

(1)n级缓存器能做模运算(循环移位)，使码字在缓存器中反复循环而不丢失；

(2)纠错信息同时反馈给缓存器里的码多项式和除法器的伴随式，使它们能同步地反映纠正后的与的变化情况。图7-13反馈型的梅吉特译码器这些特点使反馈型梅吉特译码器能够多次循环纠错，从而简化了差错图样识别电路。比如，对于(15，7，5)循环码，它应该能纠正所有的重量为1和2的差错图样，以及部分3重差错。如果用无反馈梅吉特译码器，由于是一次纠错(码字输入缓存器后逐位输出并加入纠错信号，纠错过程限在这一个n拍中完成)，译码逻辑必然比较复杂。如果采用反馈型，可以让纠错在多次循环中进行。例如，当出现一种可纠的3重差错图样后，码字暂不输出，而是令其在内部循环纠错，此时k1闭合而k2断开。如果在第一个循环周期纠正了其中一处差错，那么在第二个循环周期时就只剩下包含两个差错的图样了。再循环一次，也许就剩下一个差错的图样了。循环纠错完毕后，把k1断开而k2闭合，n级缓存器中经过纠错的码字开始输出。这种方法的译码电路只要设计得当，可比无反馈时简单得多。

【例7－13】已知(7，3)循环码，当码字传送出现一个错误时，设计译码器。

解若用一般译码器需要识别如0000001，0000010，0000100，0001000，0010000，0100000，1000000等7个不同的错误图样，但对循环码译码器来说，可以把这些错误图样归成一类，译码器只要识别其中的一个错误图样就可以了。若(7，3)循环码译码器按错误图样1000000设计，于是s(x)=e(x)modg(x)=x6mod(x4+x3+x2+1)=x3+x2+x，即s=1110，其译码器电路如图7－14所示。图7－14例7－13(7，3)循环码译码器电路表7-6(7，3)循环码译码过程(1)若在上述码字传送时，错误图样是E=［0001000］，即R=［0110010］，译码器工作过程见表7－7。从表7－7中可见，到第7拍结束时s不是全0，但也不是1110，说明接收码字有错，但错误图样不是［1000000］。从第8拍开始g(x)除法电路进行自发运算，到第10拍结束时得s=1110。然后与门呈开的状态并输出纠错信号M=1,对于R的对应位实施纠错,同时M=1信号使D1～D4清0。表7－7例7－13(7，3)循环码译码过程(2)将梅吉特译码器稍加改动，也可以用做缩短循环码的译码。缩短i个信息位的(n-i，k-i)缩短循环码是在(n，k)循环码中选前i个信息位为0的码字组成的，其伴随式的位数是一样的。从原理上来说，译码时，只要在前面添上i个0，就可以用(n，k)循环码译码器来实现。如考虑到时钟的配合，可以不添0而对(n，k)译码器做两处修改：缓存器长度减小i；除法电路改由第i节延时单元输入，相当于求xiR(x)modg(x)。

梅吉特译码器是通用循环码译码器。从原理上说，它可以用于任何循环码或缩短循环码的译码。但实际上，这种译码器的复杂程度随纠错能力t的增加而飞快增长。因此，当t>3时，或突发差错超过每码字一次时，一般不使用这种译码器。汉明码的t=1，所有差错图样可归入同一类，因此特别适合采用梅吉特译码器。

7.5捕错译码及大数逻辑译码

7.5.1捕错译码

捕错译码是梅吉特通用译码法的一种实用变形，译码器的组合逻辑电路比较简单，对纠正一个错误或两个错误的码用捕错译码法译码很有效，改进的捕错译码法(嵩忠雄译码法)可用来

纠正两个或三个随机错误的码。捕错译码法一般适用于短码或低码率的码的译码，否则将损失一部分纠错能力。然而，捕错译码用于纠突发错误的码的译码是很有效的。

循环码的捕错译码的基本思想是利用码的循环特性，把错误全部移到监督码元位置上，这时错误图样E(x)等于伴随式S(x)，因而在求得伴随式后，只需与监督位上的码元相加，就能实现纠错。假设(n，k)循环码是纠错能力为t的系统码，它的码多项式为

其中：cn－1,cn-2，…，cn-k为信息位；cn－k－1，…，c1，c0为监督位。

令接收码字为R(x)，错误图样为C(x)＝cn－1xn—1＋cn－2xn—2＋…＋c1x＋c0循环码的伴随式可表示为：(7-35)假定en－1，…，en－k全为0，即全部错误限制在n—k个监督位上，则E(x)是一个小于n—k次的多项式(低于g(x)的次数)，此时有：(7-36)由式(7-35)和式(7-36)得到E(x)＝S(x)(7-37)对于纠错能力为t的(n，k)循环码，要求t个错误限制在n-k个相邻位上，码的参数应满足什么条件，这个要求才能得到保证呢?t个错误限制在n-k个相邻位上，等效于要求R(x)中有一个相邻k位的无错区间。若n、k、t满足

n>t·k

(7-38)那么即使t个错误均匀分布，在R(x)中也一定存在相邻k位无错的区间。因而纠t个错误的(n，k)循环码若码的参数满足式(7-38)，通过循环移位就一定能把R(x)的t个错误移到n—k个监督位上。在循环移位过程中，可用下面的定理判断t个错误是否已全部集中到码的n—k个监督位上，。

定理7－5设(n，k)循环码的纠错能力为t，如果错误限制在n-k个监督位上，则伴随式的重量不大于t;如果在信息位上存在错误，则伴随式的重量必大于t。捕错译码电路的实现见有关文献。7.5.2改进的捕错译码

前面讨论的捕错译码要求接收码字中的错误集中在n－k个相邻位上，因此，它适用于纠正突发错误或一个和某些两个随机错误(条件是n>t·k)的码。纠正三个或三个以上的随机错误的码一般不满足n>t·k的条件。然而，改进后的捕错译码可以用来纠正这样的错误图样，即每个错误图样的大部分错误集中在n-k个相邻位上，而只有少数错误在此n-k位跨距之外。下面讨论由嵩忠雄提出的一种改进方案。设干扰产生的错误图样为E(x)＝en—1xn—1十en—2xn—2＋…＋e0

可分成两个部分；接收码字信息部分中的错误为：EI(x)＝en－1xn－1＋…＋en－kxn－k接收码字监督部分中的错误为Ep＝en－k－1xn－k－1＋…＋e0

接收码字的伴随式为(7-39)则有:(7-40)令代入式(7-40)得:Ep(x)＝S(x)＋SI(x)(7-41)式(7-41)表明，接收码字监督位上的错误图样等于接收码字的伴随式与信息位上错误的伴随式之和。如果我们对信息位上可能的错型一个一个地进行试验，并确定出某一个为实际错误图样，那么监督位上的错误图样则可由式(7-41)求出，从而求得接收码字R(x)的错误图样E(x)。由上述可知，改进捕错译码法的出发点是先确定接收码字信息部分中的错误图样。(7-42)(7-43)

若码的纠错能力为t，且错误图样重量为W[E(x)]≤t，在k个信息位上的错误图样的重量W[EI(x)]＝W[Xn－kQj(x)]＝W(Qj(x))，则在n—k个监督位上的错误图样Ep（i）

(x)的重量为W[(x)]＝W[S（i）(x)＋SIj(x)]≤t－W[Qj(x)]（7-44）所以，当式(7-44)对某个j成立时，就表示xn－k

Qj(x)是E（i）(x)在信息位上的错误图样。而接收码字的错误图样为:E(x)＝xn－i

E（i）(x)＝xn－i

[xn－k

Qj(x)＋S（i）(x)＋SIj(x)](7-45)将所求得的错误图样E(x)和R(x)模2加，可使R(x)中的错误得到纠正。从错误图样的特定结构出发，由循环码的通用译码法演变出了捕错译码法。而从码的结构出发，可导出大数逻辑译码法。这是一种很有效的译码方法，具有译码设备简单，速度快的优点，因而得到广泛的应用。7.5.3大数逻辑译码

1.正交一致监督和式

设hj(j＝n-k-1,n-k-2，…，0)是循环码的一致监督矩阵H的行变量，则H为H＝[hn－k－1hn－k－2…h0]T又设C为任一码字，R＝[rn－1…r0]为接收码字，其伴随式ST＝HRT的各分量为：(7-46)式(7－46)称为接收码字R的监督和式。

若R为一码字，则sj＝0;若R不是一个码字，则sj≠0。

若E＝[en－1

en－2…e0]为R的信道错误图样。由于R＝C＋E,HCT＝0T，所以：(7-47)因此，接收码字的监督和式，实际上是对信道错误图样进行监督，而与发送的具体码字无关。在式(7-47)中，若hj,i＝1，则说码元位ci被监督和式sj监督。并把sn－k－1,sn－k－2，…，s0称为监督和式组。

若在(n，k)循环码的监督和式组中，码元位ci(i＝n－1，n－2，…，0)被J个(J≤n－k)一致监督和式监督，而其它码元位不被一个以上的监督和式监督，则称此J个监督和式为对码元位ci正交的一致监督和式组。

以二元(7，3)循环码为例，其监督方程为:(7-48)由式(7-48)得新的监督方程组:(7-49)

由式(7-49)可见，码元c6被所有三个监督方程监督，而其它任一码元在三个监督方程中出现不多于1次(可以不出现)，因而称式(7-49)的监督方程正交于码元位c6。将式(7-49)改写成矩阵形式：令：则H0CT＝0T

称H0为正交一致监督矩阵。其特点是：与正交码元位对应的列为全“1”，其它任一列中“1”的个数不多于一个,称S0＝RHT0为正交伴随式。由于循环码的循环特性，任意码字的循环移位仍是一个码字，也满足正交监督矩阵H0。所以对最高阶码元位cn－1正交的码字C，经过一次循环移位后就变成了对次高阶码元位cn－2正交的码字C（1）。不难推知，连续的循环移位可以得到对码字的所有码元达成正交的监督和式。

例如，(7，3)循环码的三个正交监督和式为（7-50）

s00，s01，s02构成正交伴随式S0＝s00s01s02。S0经过一次循环移位S0（1）的正交监督和式为:（7-51）式(7-50)是正交于最高阶码元上的正交监督和式，而式(7-51)是S0经过一次循环移位S0（1）的三个正交于次高阶码元上的监督和式。

2.一步大数逻辑译码法

定理7－6若(n，k)循环码可以构成j个正交于最高阶位xn－1上的一致监督和式，则该码可以用来纠正t≤j/2错误的所有错误图样。

由此定理可直接得到：在可构成j个正交监督和式的(n，k)循环码中，如果在正交位置上含有错误，则正交伴随式S0的重量W［S0

］>j/2；如果在正交位置上没有错误，则W［S0］≤j/2。因此，译码器可用一个大数逻辑门来检测正交伴随式的重量，当W［S0

］>j/2时，正交位置上有错；当W［S0］≤j/2时，正交位置上无错。即把S0的各分量作为大数逻辑门的输入，当这些输入中多数为“1”时，正交位置上接收符号是错误的，大数逻辑门输出“1”，将错误纠正；当大数门的输入中只有一半或更少个“1”时，则正交位置上没有错误，大数门输出“0”。再利用码的循环位移特性，可纠正接收字中所含的全部错误(错误个数≤j／2)。这种译码方法称为一步大数逻辑译码法。

【例7－14】已知（7，3）循环码的三个正交监督和式为（7－52）试设计大数逻辑译码电路。

解在式(7－52)所示的方程组中，r6～r0是已知数，e6～e0是希望求解的未知数。

如果用解方程组的方法，则可以先用r6～r0计算e6～e0，这是由3个方程解7个未知数，可知答案不是惟一的。

但是，式(7－52)中除了最高位差错e6被全部3个方程包含外，其他任何位置的差错ei(i≠6)都仅被一个方程式所包含。正交一致监督和式A=s02s01s00的重量W［A］是：如果有单个差错发生在最高位码元e6上，必有W［A］=3；反之，如果单个差错发生在除最高位的其他任何位置，都有W［A］=1。可见，通过计算正交一致监督和式A的重量W［A］，不但能发觉是否有错，而且可以判断出单个差错是否发生在最高位。如果j>2，说明最高位存在差错(e6=1)；如果j<2，说明差错在其他位置而不在最高位上。这样，就可以根据j大于2还是小于2来决定应不应该给最高位加一个纠错信号。上面讨论的差错判决限于判断最高位是否有错，而不能判断其他位是否有错。好在循环码码字的循环、伴随式的循环及差错图样的循环是同步的，只要将码字循环一遍，差错图样也就会循环一遍，任何其他位置上的差错在一个循环周期里都有机会处于最高位。因此，在纠错能力范围内，只要保证最高位的差错能被纠正，就能保证其他位置上的差错被纠正。由于判决是根据j是否大于2作出的，所以称为“大数逻辑”或“门限”。图7－15所示为根据式(7－52)设计的大数逻辑译码器。大数门是一个判决电路，j>2时输出“1”，否则输出“0”。在开头的7拍中，接收码元送入7级移存器。从第8拍开始，接收码元逐拍输出，大数门也开始工作，对最高位r6的正确与否作出判决，并趁移存器输出r6之际加上一个判决(纠错)信号“1”或“0”。同时，转换开关由S1转向S2，接通反馈而切断输入，以实现码字循环。经又一个7拍后，全部码元译码输出完毕。图7－15利用接收码字R的大数逻辑译码

3.L步大数逻辑译码

一步大数逻辑译码虽然简单易行，但实际中一步大数逻辑可译码并不多，且纠错能力也不强。为了扩大应用范围，改善纠错能力，人们把正交于某一码元的概念推广到正交于某一码元集合，并通过L步大数逻辑判断逐次减少集合中码元的个数，最后完成对某一码元位的译码，这就是L步大数逻辑译码的思路。下面举例说明。

【例7－15】已知（7，4）汉明码的校验矩阵为

设s2、s1、s0分别表示H的第1行、第2行、第3行，试用L步大数逻辑译码。

解：由矩阵第1行、第2行、第3行的行的线性组合，可得一致监督和式：

注意到s00与s０１正交于r6+r3，如果r6和r3中只有一位出错，可用大数门求出。同样，s02与s03正交于r6+r4，如果r6和r4中只有一位出错，也可用大数门求出。将这两个大数门的值送入第二级大数门，只有当r6出错时，输出第二级大数门的重量才是2。这一过程用了二步大数逻辑译码：第一步判断集合r6、r3和r6、r4，是否有错，第二步才判断r6是否有错。具体的电路实现如图7－16所示。图7－16二步大数逻辑译码电路对于L>2的L步大数逻辑译码，其思路与例7－15相同，只是更复杂而已。一般说来，译码设备的复杂性随L指数而增加。因此实际中很少用到L>2。

比较梅吉特译码与大数逻辑译码，我们可以看到：

梅吉特译码基本上是一种查表法，并能提供最大似然的性能。在实际中，梅吉特译码器限于n-k与t都较小的码，可以获得的最大实际编码增益约2.5dB(误比特率105时)。此外，梅吉特译码的概念不能直接扩充至软判决，这是它的又一不足之处。

大数逻辑译码简单易行，但只能用于为数不多的大数逻辑可译码，其中有些码具有较大的最小码距，最大的编码增益为3.5dB。大数逻辑译码可直接扩展到使用软判决的门限译码。

7.6

BCH码

7.6.1多项式表述

因为g(x)是xn-1的一个因子，所以循环码的生成多项式可以写成如下形式：(7-53)其中,f1(x),f2(x),…,fq(x)是以g(x)为根的极小多项式，每一个极小多项式对应于g(x)在扩域上的一个根。设C(x)为GF(p)的一个码字多项式，E(x)为错误多项式。则接收到的多项式为(7-54)(7-55)对分组长度n，则有（7-56）因此，得到包含q个方程的方程组，它们只含有错误图样的分量。如果求解该方程组能得到ej，便可以精确地确定错误图样。能否解此方程组决定于g(x)的根的个数，即q的值。为了求解错误图样，必须小心选取这q个方程。如果要设计能纠t个错误的循环码，应选择是方程组对至多t个非零ej的情况可以求解。

定义伴随式Si=e(ri)(i=1,2,…,q)。希望选取r1,r2,…,rq使得由S1,S2,…,Sq可以求解t个错误。若α是个本原元，则能纠t个错误的ri的集合为｛α1,α2,α3,…,α2t｝。因此，有如下一种能确定纠t个错误的BCH码的生成多项式的简单方法。对一个本原分组长度n=pm-1，确定可纠t个错误的BCH码的生成多项式的步骤为：

(1)选取一个次数为m的素多项式并构造GF(pm)；

(2)求αi(i=1,2,…,q)的极小多项式fi(x)；

(3)可纠t个错误的码的生成多项式为（7-57）用这种方法设计的码至少能纠t个错误。但在很多情况下，这些码所纠的错误多于t个。因此，称d=2t+1(7-58)为码的设计距离，其最小距离为dmin≥2t+1。它的生成多项式次数等于n-k。

【例7－16】考虑GF(2)上的本原多项式p(z)=z4+z+1，构造扩域GF(24)。

解设α=z为本原元。GF(24)上以α的幂形式表示的元素及它们对应的极小多项式在表7－8中列出。表7－8

GF(24)上的元素和对应的极小多项式

【例7－17】利用表7－8确定纠t个错误的BCH码的生成多项式，即t=1，2，3，4，5，6，7且n=15。

解由式（7－57）可知，一个BCH码的生成多项式由lcm［f1(x),f2(x),…,f2t(x)］给出。利用表7－8来获得极小多项式f1(x)和f2(x)。于是纠单一错误的BCH码的生成多项式为因为degg(x)=n-k，可得n-k=4，从而给出k=11,于是得到纠单一错误的BCH(15，11)码的生成多项式。该码的设计距离为d=2t+1=3,可以计算出该码的实际最小距离dmin也是3。因此，在此情况下设计距离等于最小距离。

确定纠两个错误的BCH码的生成多项式，即t=2且n=15。该BCH码的生成多项式为因为degg(x)=n-k，可得n-k=8，从而给出k=7。于是得到纠两个错误的BCH(15，7)码的生成多项式。该码的设计距离为d=2t+1=5。可以计算该码的最小距离dmin也是5。因此，在此情况下设计距离等于最小距离。

确定纠三个错误的二元BCH码的生成多项式，该BCH码的生成多项式为表7－10码长达25-1的二元BCH码的生成多项式7.6.2矩阵表述

设BCH码的生成多项式g(x)的根为(β,β2,…,β2t)∈GF(2m)，则上述2t个元素也必然是任一码字多项式C(x)＝cn－1xn-1＋cn－2xn-2＋…＋c1x＋c0的根，即（7－59）其中i＝1，2，…，2t。可以将这些不同i值的方程组写成矩阵形式:＝０

(7－60）g(x)＝lcm（m1(x)，m2(x)，m3（x），m4（x），…，m2t(x)）＝lcm（m1(x)，m3（x），…，m2t－１(x)在(7-61)式中，可不包括下标为偶数的最小多项式。于是BCH码的H可简化成:（7－62）式(7－62)中，若