6-2 循环码(Cyclic Code)
循环码是线性分组码的最重要的一类码，它的结构完全建立在有限域多项式的基础上。它具有两个基本特点：一是编码电路与译码电路非常简单，易于实现；二是其代数性质好编码译码分析方便，有一些好的译码方法。 6-2-1 循环码的描述
[循环码定义]：
一个(n,k)线性分组码C ，如果码组中的一个码字的循环移位也是这个码组中的一个码字，则称C 为循环码。
C (0)={cn-1,c n-2,……c1,c 0} ∈C C (1)={cn-2,c n-3,……c0,c n-1} ∈C 称为具有循环自闭性。 [循环码的多项式描述]：
循环码可以用监督矩阵和生成矩阵描述，但更多地用域上多项式来描述，一个(n,k)循环的码字矢量C (0)用一个n-1次多项式描述，可以表示为：
C(x)= cn-1x n-1+cn-2x n-2+……+c1x+c0 这个多项式称为码字多项式。
码字矢量的循环移位可以用x 乘上C(x)后的模x n -1(xn +1)来表示。 xC(x)= x(cn-1x n-1+cn-2x n-2+……+c1x+c0) = cn-1x n +cn-2x n-1+……+c1x 2+c0 x
= cn-2x n-1+……+c1x 2+c0 x+ cn-1 (模x n +1)
模x n +1相当于x n +1=0；x n =1 [循环码举例]：
(7,4)系统循环码的编码及码字多项式如下表：
可以看出：每个码字的循环移位仍然属于这个码组，
注意：并不是说这个码组是由一个码字的循环移位构成的，本例中是由四个码字的循环移位构成的。
[生成多项式的定义]：
在一个(n,k)循环码中，有且仅有一个次数为n-k=r的码字多项式，记为：
g(x)=xr +gr-1x r-1+……+g1x+1
同时：每个码字多项式都是g(x)的倍式；每个次数小于等于n-1的g(x)的倍式必为一个码字多项式。这时称g(x)的(n,k)码的生成多项
式。
从上面的例子可见，g(x)=x3+x+1为(7,4)循环码的生成多项式。 [生成多项式的性质]：
循环码C 中次数最低的非零码字多项式是唯一的，其次数为r=n-k。
令g(x)=xr +gr-1x r-1+……+g1x+g0为一个(n,k)循环码C 中最低次数码字多项式，则其常数项必为g 0=1。 [定理1]：
(n,k)循环码的生成多项式g(x)是x n +1的因式。
{证明}：已知g(x)为一个n-k 次多项式，则x k g(x)为一个n 次多项式，则必有：
x k g (x ) g (k ) (x )
=1+n
x n +1x +1
因为x k g(x)是g(x)的循环移位，它也是一个码字多项式，所以一定为g(x)的倍式，即有：g (k)(x)为g(x)的循环移位在模x n +1下的结果，因此有：g (k)(x)=q(x)g(x)，由上面的关系式可知：
x k g(x)=(xn +1)+g(k)(x)
x n +1=xk g(x)+q(x)g(x)=[xk +q(x)]g(x) 因此，g(x)为x n +1的因式。 [定理2]：
若g(x)是一个n-k 次多项式，且为x n +1的因式，则g(x)生成一个(n,k)循环码。
这个定理说明：x n +1的次数为n-k 的任何一个因式，均可以生成
一个(n,k)循环码。对于较大的n ，x n +1可以有多个n-k 次多项式，产生不同的(n,k)循环码，但可能有好有坏。
例如：多项式x 7+1可以分解为： x 7+1=(x3+x+1)(x3+x2+1)(x+1)
可以看出有两种(7,4)循环码的生成矩阵 g(x)= (x3+x+1)和g(x)= (x3+x2+1)。
还可以产生一种(7,6)循环码， 6-2-2 循环码的编码方法
[系统循环码的编码方法]：
已知循环码的生成矩阵可以按以下步骤产生系统循环码。 首先定义以下多项式：
m(x)=mk-1x k-1+mk-2x k-2+……+m1x+m0 为信息码字多项式； c(x)=cn-1x n-1+cn-2x n-2+……+c1x+c0 为循环码字多项式； g(x)=xr-1+gr-2x r-2+……+g1x+1 为生成多项式； 系统码的编码分为三步： 用x n-k 乘上m(x);
用g(x)除以x n-k m(x)，得到模g(x)的余式r(x)
x n -k m (x ) r (x )
=q (x ) + g (x ) g (x )
c(x)=xn-k m(x)+r(x)为系统循环码的码字多项式。 [例题1]：
(7,4)循环码的生成多项式为g(x)=x3+x+1
求m=[1010]的循环码。 解：m(x)=x3+x, x n-k =x3; x n-k m(x)=x3(x3+x)=x6+x4
x n -k m (x ) x 6+x 4x +1
=3=x 3+1+3 g (x ) x +x +1x +x +1
r(x)=x+1
C(x)=xn-k m(x)+r(x)=x6+x4+x+1 [例题2]：
(7,3)循环码的生成多项式为g(x)=x4+x3+x2+1=(x+1)(x3+x+1) 求：[m]=[010]的循环码字[C] 解：m(x)=x; x n-k m(x)=x4x=x5
x 5x 2+x +1
=x +4
x 4+x 3+x 2+1x +x 3+x 2+1
C(x)=x5+x2+x+1 [非系统循环码的编码方法]：
已知循环码的生成矩阵，可以方便的求出非系统循环码， C(x)=m(x)g(x)
例如：m=[1101] g(x)=x3+x+1
C(x)=(x3+x2+1)(x3+x+1)=x6+x43532+x3+x+1=x6+x5+x4+x3+x 2+x+1 [C]=[1111111]
m=[0101]; c(x)=(x2+1)(x3+x+1)=x53235+x2+x+1
[C]=[0100111] [循环码的生成矩阵]：
循环码可以用域上多项式描述，也可以用生成矩阵描述。 已知g(x)为循环码C 中的一个码字多项式，由循环码的循环特性可知，可以证明：在(n,k)循环码的码字多项式中，g(x),xg(x),……xk-1g(x)等k 个码字多项式必是线性无关（相互独立的）的。根据线性空间的特性，可知，它们是一个k 维子空间的基底，即由它们的线性组合可以生成这个k 维子空间的2k 个码字。再根据线性分组码生成矩阵的定义，它的行向量是由k 个线性无关的码字构成的，可以得到(n,k)循环码的一个多项式矩阵为：
[G(x)]=
相应的生成矩阵为
g n-g n-k-… g 1 g 0 0 0 … 0
k 1
0 g n-k g n-k-… g 1 g 0 0 … 0
[G]= 1
… 0 … … 0 g n-k g n-k-… g 1 g 0
1
由这个基本关系式可以看出，当输入信息码字矢量为(mk-1,m k-2, ……m0) 时，相应的码字多项式为：
C(x)=(mk-1,m k-2, ……m0)G(x) =(mk-1x k-1+mk-2x k-2+……+m0)g(x) =m(x)g(x)
x k-1g(x) x k-2g(x) … g(x)
利用这种方法产生的循环码为非系统循环码，因为，[G(x)]为非标准型生成矩阵，（非典型生成矩阵）。
这个非标准型生成矩阵可以通过矩阵的初等变换转换为标准型生成矩阵。可以通过以下例子说明。
[例题]：已知(7,4)循环码的生成多项式为g(x)=x3+x+1，其非标准型生成矩阵为：
x 3g(xx 6+x4+x3 1 0
) 2
[G(x)]x g(xx 5+x3+x2 0 1
= =
= )
xg(x) x 4+x2+x 0 0
3
g(x) x +x+1 0 0
1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 利用不同的矩阵变换可以得到不同的标准型生成矩阵。 这种变换包括： 列换位； 初等行变换；
通过以上两种方法，可以得到标准型生成矩阵：
[G]=
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1
只使用初等行变换可以得到标准生成矩阵：
[G]=
可知标准型生成矩阵是不唯一的。 6-2-3 校验子与循环码的译码原理
设发送的码字多项式位C(x)，错误图样多项式位E(x)，则接收码
字多项式为：
R(x)=C(x)+E(x) 译码器的工作过程为：
由接收码字多项式R(x)计算校验子多项式S(x); 根据校验子多项式S(x)计算错误图样多项式E(x); 利用R(x)-E(x)=C(x)计算译码器输出的估计值。 发送码字多项式为：
C(x)=cn-1x n-1+cn-2x n-2+……c1x+c0 接收码字多项式为；
R(x)=rn-1x n-1+rn-2x n-2+……+r1x+r0 校验子多项式为：
E(x)=en-1x n-1+en-2x n-2+……e1x+e0 由R(x)=C(x)+E(x)可知： r i =ci +eI i=0,1,…n-1 这时定义校验子多项式为：
S (x ) =
R (x ) C (x ) +E (x ) C (x ) E (x ) E (x )
==+≡ [模g(x)] g (x ) g (x ) g (x ) g (x ) g (x )
即：S(x)≡E(x)≡R(x) [模g(x)]
也就是说，接收码字多项式除以g(x)的余式多项式为校验子多项式。
如果：S(x)=0，表示接收码字无错； 如果：S(x)≠0, 表示接收码字有错；
(n,k)循环码的校验子多项式的一般表达式为：
S(x)=sr-1x r-1+sr-2x r-2+……+s1x+s0
即校验子多项式S(x)为一个r-1次多项式。其校验子矢量为： [S]=[sr-1,s r-2,……s1,s 0]
它共有2r 个状态，当2r ≣n+1时，即可以纠一位错。 [例题]：(7,4)循环码的校验子及译码， 已知：(7,4)循环码的生成矩阵为g(x)=x3+x+1 考虑接收码字不错或只错一位时的校验子多项式。 发送码字多项式为：
C(x)=cn-1x n-1+cn-2x n-2+……c1x+c0 接收码字多项式为；
R(x)=rn-1x n-1+rn-2x n-2+……+r1x+r0 校验子多项式为：
E(x)=en-1x n-1+en-2x n-2+……e1x+e0
这个表给出了接收码字不出错或只错一位时校验子多项式和校验子矢量的结果。根据这个表可以进行译码。
例如：发送码字为：C={0010110}，接收码字为：，表明r 3错。
接收码字多项式为：R(x)=x4+x3+x2+x, g(x)=x3+x+1，校验子多项式为：
R (x ) x 4+x 3+x 2+x
S (x ) ==≡x +1 [模g(x)]
g (x ) x 3+x +1
S(x)=x+1 [s2,s1,s0]=[011] 查表可知r 3出错。
已知(7,4)循环码的最小汉明距离dmin=3，只能纠一位错，当接收码字出现两位错时将不能纠正。
例如：发送码字为：C={0010111}，接收码字为：，表明r 3和r 0错。
R(x)=x4+x3+x2+x+1
S(x)=x; [s2,s 1,s 0]=[010]，根据校验子表可知，译码器判为r 1错，这时产生译码错码。 6-2-4 循环码的编码电路
根据循环码的编码方法，可知编码电路应当是一个多项式的除法电路，它是码字多项式的循环一位后除以生成多项式。
[系统码编码器]：
为了构成系统码，可知C(x)=xn-k m(x)+r(x) r(x)=xn-k m(x)/g(x) [模g(x)] 以(7,4)汉明码为例：g(x)=x3+x+1
编码器电路如图所示：它由n-k 级移位寄存器构成。
这是一个由n-k=3级移位寄存器及加法器、或门和门控电路构成的。
移位寄存器的初始状态为全0，门1开，门2关。信息码元以
[m3,m 2,m 1,m 0]依次输入编码器。信息码元一方面通过或门输出，另一方面送入除法电路。在除法电路的右端输入m(x)相当于完
成了循环移位n-k=3位。
四次移位后，信息码元已输出，形成了系统循环码的前四位信
息位。同时寄存器中存放的就是余式多项式的系数，从右到左
分别是(c2,c 1,c 0) 。
门1关，门2开，经三次移位，这三个监督位从编码器输出。 门1开，门2关，进行第二个码字的编码。
m=[1001], C=[1001 110]的编码过程如下表：
(7,3)循环码的生成矩阵为：g(x)=x4+x3+x2+1
其编码电路为：
由于n-k=r=4所以编码器有四级移位寄存器。
[非系统循环码编码电路]：
非系统循环码的产生为：C(x)=m(x)g(x),可知其编码器为如下：
m(x)
例如m=[1110]，编出的循环码字为：C=[1100001]
C(x)=m(x)g(x)=(x3+x2+x)(x3+x+1)=x6+x5+1
6-3 循环码的译码
循环码的编码电路由n-k 级移位寄存器构成，比较简单，但是循环码的译码电路就相对比较复杂。因此，循环码的译码方法是研究编码理论和编码技术的重要内容。
线性分组码（不仅是循环码）的译码大体分为两类：一是利用码字的代数结构进行译码，称为代数译码方法。另一类不仅利用代数结构，而且还利用概率理论，称为概率译码。这里我们重点介绍代数译码方法，包括捕获（错）译码，大数逻辑译码。
6-3-1 梅吉特(Meggit)译码器
上面我们介绍了循环码的校验子（伴随式）译码的基本原理，已知：
S(x)=R(x)/g(x) [mod g(x)]
这里首先介绍一个有关校验子多项式的重要特性。
[定理]：
设S(x)是接收码字多项式R(x)的校验子多项式，则R(x)的循环移位xR(x)[mod x n +1]的校验子S 1(x)是S(x)在g(x)除法电路中无输入时右移一位的结果。
S 1(x)≡xS(x) [mod g(x)]
[证明]：由校验子多项式的定义可知，
S(x)≡R(x) [mod g(x)]，两边同时乘以x 可得；
xS(x)≡xR(x) [mod g(x)]
这时如果定义
S 1(x)≡xR(x) [mod g(x)]
显然有S 1(x)≡xS(x) [mod g(x)]
[定理的推广]：
这个定理的结果可以推广为，对于任意给定的j=1,2,…,n-1，必有x j R(x)的校验子多项式为：
S j (x)=xj R(x)/g(x)≡x j S(x) [mod g(x)]
同时有任意多项式a(x)乘R(x)所对应的校验子多项式
S a (x)=a(x)R(x)/g(x)≡a(x)S(x) [mod g(x)]
校验子多项式的这些性质，在循环码的译码中有重要作用。
[梅吉特译码原理]：
如果：C(x)为循环码C 中的一个码字多项式，则xC(x)[mod xn +1]也是这个码组中的一个码字。
如果：S(x)为R(x)=C(x)+E(x)的校验子多项式，则xS(x)也必然是xR(x)=xC(x)+xE(x)的校验子多项式。
这表明：如果E(x)是一个译码器可以纠正的错误图样（相当于译码标准阵中的陪集首），则xE(x)也是一个可以纠正的错误图样，x j E(x) (j=1,2,…,n-1) 也是可以纠正的错误图样。
这样就可以根据这种循环关系，对错误图样分类，将任一错误图样及其所有n-j 次的循环移位归为一类。
同一类的错误，可以使用同一个译码单元电路，可以简化译码器电路的复杂性。
例如：可以将“只错一位”的错误图样(100…0),(010…0),…,(00…01)归为一类，这样用一个错误图样(100…0)的校验子S(x)代表这一类错误图样的校验子。
这样可以大大减少译码器要识别的错误图样类别的个数：
一个(n,k)循环码，要纠正t 位错误，译码器要识别的错误图样总数为：
Ne =∑C n j
j =1t
例如(7,4)循环码可以纠正一位错，n=7，t=1，N e =C71=7。
而通过分类后，译码器需要识别的错误图样的类别数为：
-1N g =∑C n j -1
j =1t
例如(7,4)循环码的错误图样类别数为N g =1。可以看到通过分类识别，可以简化循环码译码器的复杂性。
[例题]：(7,4)循环码的生成矩阵为g(x)=x3+x+1，通过前面分析可知，只要接收码字矢量只错一位，译码器总可以正确译码。
在构造此译码器的错误图样识别电路时，只要识别一个错误图样例如，E 6=[1000000]就可以了。这个错误图样对应的校验子矢量为S=[101]，由此可以得到一种译码器结构如图：
这个译码器上面是一个g(x)除法电路，下面是一个7级移位寄存器作为缓存器，中间的反相器和一个与门组成了(101)校验子识别电路。译码过程如下：
开始译码时门打开，移位寄存器内容位全0。收到的码字多项
式位R(x)=r6x 6+…+r0 由高次到低次分别输入到7级缓存器和
除法电路，7次移位后，缓存器存入整个码字，除法电路
[S(x)=E(x)/g(x), E(x)=x6]得到校验子S 0=[s2,s 1,s 0]。这时门关上，
进行译码。
如果S 0(x)=x6=x2+1[mod g(x)]，这时[101]识别电路输出为1，
表明r 6为有错。
这时译码器继续移位，通过[101]识别电路可以将r 6位的错误纠
正。
在纠错的同时，[101]识别电路的输出又反馈到除法电路的输入
端，以消除错误码元对除法电路的下一个校验子计算的影响。校验子产生电路开始在无输入的情况下移位，相当以开始产生
x j S(x)。
本电路中，第7次移位后产生了校验子S 0，第8次移位时对r 6进行纠正，同时将[101]识别电路的输出的1输入到除法电路的输入端，结果使除法电路的寄存器状态为[000]，消除了e 6的影响。
下面我们看一下，利用这个电路能否纠正其它错误图样的接收码字。
如果E(x)=x5, 表明e 5=1或E=[0100000]，这时经过前7次移位
后得到的校验子多项式为S 0(x)=x5=x2+x+1[mod g(x)]，这时除
法电路的移位寄存器状态为[111]，[101]识别电路的输出为0，说明r 6正确，不必纠正。
第8次移位后，r5移位到缓存器的最右端。同时校验子除法电
路的结果根据定理可知：（通过电路分析也可以看出）
S 1(x)=xS0(x)=xE(x)=x6=x2+1 [mod g(x)] 产生[101]状态；
这时[101]识别电路输出1，对r 5进行纠正。
可以看到，利用循环码的循环特性，可以简化译码器的复杂性。 从上述译码过程中可以看到，(n,k)循环码的译码器译一个码字共需要2n 次移位，不能实现连续译码，为了实现连续译码，可以再加一套除法电路，
其工作过程如下：
译码前两个移位寄存器为全0状态，门1开，门2关，当k=4
次移位后，4级缓存器接收到码字的前4位信息位。
此时，门1关。再移位n-k=3次后，上面的除法电路得到校验
子S 0(x)，
这时门2开，将上面除法电路得到的校验子送入下面的除法电
路，随即门2关闭，且上面的除法电路清0。
门1再次打开，4级缓存器一边送出第一组信息，一边接收第
二个码字的信息位，与此同时，上面的除法电路计算第二个码字的校验子，下面的除法电路对第一组码字进行纠错。
以上是对系统码而设计的电路，如果是非系统码，k 级缓存器
应改为n 级，而且要在得到的码字中恢复信息位。根据m(x)=C(x)/g(x)，应再加一个除法电路。
上面介绍的系统循环码的一般译码器称为梅吉特译码器。
6-3-2 捕错译码
循环码的译码器的复杂性主要取决于由校验子确定错误图样的组合逻辑电路的复杂性，另外一种译码方法称为捕错译码，其特点是适应于纠突发错误码。
[工作原理]：
设C(x)是一个纠t 位错误的(n,k)系统循环码的码字多项式，而相应的接收码字多项式为：R(x)=C(x)+E(x)，译码器得到的校验子多项式为：
S(x)=R(x)/g(x)=E(x)/g(x)≡E(x) [mod g(x)]
≡E I (x)+EP (x), [mod g(x)]
其中：
E I (x)=en-1x n-1+en-2x n-1+…+en-k x n-k
E P (x)=en-k-1x n-k-1+…+e1x+e0
E I (x)为k 位信息位的错误图样，E P (x)是n-k=r位监督位的错误图样。
这时可以看到：
如果：错误图样多项式E(x)的次数=n-k-1=r-1，
即码字中的错误集中在n-k=r监督位上，
即e n-1=en-2=…=en-k =0；
则：E I (x)=0，E(x)=EP (x)。
又因为：生成多项式g(x)的次数位n-k=r，
所以：校验子多项式S(x)=E(x)/g(x)=EP (x), [mod g(x)]
得到的结论是：对于具有这样的错误图样的码字C(x)，经过循环移位后，可以使S(x)=E(x)，译码过程就可以变为：C(x)=R(x)-S(x)。(在GF(2)上，减法与加法一样)
要使一个码字的错误码元全部集中在码字的后n-k=r位上，只要求错误码元集中在任意连续n-k 位上即可。因为：码字多项式的循环移位和校验子多项式的循环移位有一一对应的关系。
[捕错译码的定义]：
若接收码字R(x)对应的校验子多项式为S 0(x)，经过i 次循环移位后，x i R(x)=Ri (x)对应的校验子多项式为S i (x)。一旦检测出S i (x)的重量W(Si (x))≢t ，就认为此时码字的错误码元已经全部集中在x i R(x)=Ri (x)的后n-k 位以内了。这时可以由R i (x)-Si (x)得到已经纠错的接收码字C i (x)=xi C(x)，但码字顺序不对，将其再进行n-i 次循环移位，即可得到:
C(x)=xn C(x)=xn-i x i C(x)
从而纠正了错误，这种译码方法称为捕错译码。
[捕错译码的适应条件]：
只有当所有小于等于t 个错误全部集中再连续n-k=r位以内时，
捕错译码才有效。
当码字的错误突发长度b 小于等于(n-k)/2时，捕错译码才有效。 例如：(7,4)码，d min =3, t=1, n=7, k=4, n-k=3 (n-k)/2=1.5 所以b=1
(15,7)码，d min =5, t=2, n-k=8, (n-k)/2=4 b=4,
如果一个(n,k)码可以纠正t 位错，使用捕错译码的必要条件是： k
[定理]：捕错译码的判别条件
纠正t 位错误的(n,k)二元循环码，捕错译码器已经把t 个错误集中在R i (x)的最低n-k 位以内的充要条件，是此时的校验子矢量的汉明重量：
W(Si (x))≢t
[证明]：
如果错误已经集中在最低n-k 位以内，则
S i (x)≡x i E(x)=Ei (x)=EP (x) [mod g(x)]
S i (x)=EP (x)
由于这个(n,k)码只能纠t 位错，所以，对于一个可纠正的错误图样，必有：
W(E(x))≢t
而E(x)的循环移位后，其矢量的汉明重量是不变的，则
W(Si (x))=W(Ei (x))≢t
这说明：只要能纠t 位错的码已经把错误码元集中到最低n-k 位上，公式W(Si (x))≢t 就一定成立。
反之；再证明：如果W(Si (x))≢t 满足，则错误码元就一定集中在最低n-k 位码元内了。利用反证法：
即当W(Si (x))≢t 满足时，错误码元没有集中到码字的最低n-k 位码元内，
则必有循环移位后的错误图样多项式E i (x)的次数大于等于g(x)的次数。 进
而
有
：
E i (x)=q(x)g(x)+Si (x),
相
应
有
：
C i (x)=Ei (x)+Si (x)=q(x)g(x)；
这样组成的C i (x)为g(x)的倍式，必然为一个码字多项式， 再由定理，线性分组码的最小码距等于非0码字的最小汉明重量，有：
W(Ei(x)+Si(x))=W(Ci(x))≣d=2t+1 (已知码字可纠t 位错) 由汉明三角不等式：对于一个(n,k)线性分组码C ，C 1,C 2,C 3为C 中的三个码字，并为C 3=C1+C2，这时有：d(C1,C 2) ≢d(C1,C 3)+d(C3,C 2) ，或表示为 W(C1+C2) ≢W(C1)+W(C2)
W(Ei (x))+W(Si (x))≣W(Ei (x)+Si (x))≣d=2t+1 由已知W(Ei (x))≢t ，所以得出W(Si (x))≣t+1>t； 这与立题假设W(Si (x))≢t ，矛盾，
这说明当W(Si (x))≢t 时，错误码元不可能不集中在码字的最低
n-k 位码元内。 定理证毕。
[例题]：已知二元(15,7)循环码，生成多项式g(x)=x8+x7+x6+x4+1，d min =5，其纠错能力为t=2，可以纠两位错。由t=2
译码过程如下：
译码前所有移位寄存器和缓存器都为全0状态，门2，门3开，门1，门4，门5关。n=15次移位后，接收码字的R(x)的15个码元全部进入15级缓存器，信息元在前7级，监督元在后8级，同时进入除法电路，得到校验子多项式S 0(x)。如果S 0(x)=0，说明无错，打开门5，输出接收码字。如果S 0(x)≠0，说明有错，进行以下各步。
此时门2关，门1开，如果W(S0(x))≢2，检测电路输出有效，
把门4打开，把门3关闭，此时除法电路移位寄存器中的内容就是接收码字的后8位的错误图样，只要接收码字只错2位或2位以下，后8位错误图样就等于全部错误图样。这时移位15次，除法电路的状态S 0(x)=EP (x)通过门4与接收码字的后8位逐次相加，完成纠错。然后门1关，门5开，再移位15次，输出接收码字。
如果W(S0(x))>2，则15级缓存器和除法电路都循环移位一次，再次检测，若仍大于2，则继续移位，当移位I 次后，检测到W(S0(x))≢2，则说明已经检测出错误图样已进入缓存器的后8位。这时门3关闭，门4打开，继续移位n-I 次，进行纠错。最后门1关，门2，门5开，再移位15次输出正确的接收码字。 从以上步骤中可以看出，译码器完成一个码字的译码，共需要3n 次移位。
这里介绍的是捕错译码器的基本原理，若要实现连续译码，还要进行一些改进，一方面力图使译码器电路简单化，另一方面提高译码速度，减少移位次数。 6-3-3 大数逻辑译码
循环码译码器的复杂性取决于码的代数结构，对于一类循环码来说，有一种比较简单的译码方法称为大数逻辑译码，1954年由Reed 提出。
[循环码的监督矩阵描述]：
前面我们介绍过，已知循环码的生成多项式g(x)，可以得到非系
统循环码的生成矩阵。
[G(x)]=
相应的生成矩阵为：
g n-g n-k … g 1 g 0 0 … 0 k -1
0 g n-k g n-k-… g 1 g 0 … 0
1
… … 0 … 0 g n-k g n-k-1 … g 1 g 0
x k-1g(x) x k-2g(x) … g(x)
[G]=
根据循环码的生成多项式一定为x n +1的因式，有 x n +1=g(x)h(x)=(gn-k x n-k +…+g1x+g0)(hk x k +…+h1x+h0) 根据这个关系可以看出： g n-k h k =1 g 0h 0=1
而其它乘积项的系数为0。即 g 0h 1+g1h 0=0 g 0h 2+g1h 1+g2h 0=0 …
g n-1h 0+gn-2h 1+…+gn-k h k-1=0
根据生成矩阵与监督矩阵的关系，可知
[H]=
h 0 h 1 0 h 0 … 0 0
… h 1 …
h k … 0
0 h k h 0
0 0 h 1
… 0 … 0 … … h k
[H]矩阵为n-k 行n 列。它完全由h(x)的系数决定的，h(x)称为循环码的校验多项式或称为监督多项式。生成矩阵与监督矩阵的关系
为：
[G][H]T =[0]
例如：(7,4)循环码的生成多项式g(x)=x3+x+1，而监督多项式为h(x)=x4+x2+x+1。相应的生成矩阵和监督矩阵分别为：
[G]=
[H]=
1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1
0 0 0 1
可以验证：[G][H]T =[0]，还可以看出，这个监督矩阵经过列变换可以变为系统码的监督矩阵，而且就是汉明码的一致监督矩阵。
如果将这个码的生成矩阵当作另一个码的监督矩阵，而将这个码的监督矩阵当作另一个码的生成矩阵，这另一个码就是这个码的对偶码。
例如：g(x)=x3+x2+1的(7,4)循环码，是g(x)=x4+x3+x2+1的(7,3)循环码的对偶码，
g(x)=x3+x+1的(7,4)循环码，是g(x)=x4+x2+x+1的(7,3)循环码的对偶码。
[系统循环码的生成矩阵与监督矩阵]：
由于循环码的生成矩阵的每一行都为一个码字，系统循环码的生成矩阵的k 个行向量分别为(10…0),(010…0),….(00…01) 信息码对应的循环码字。因此，已知一个(n,k)码的生成多项式，求出这些码字所
对应的监督码元作为行向量的后r 位，就可以得到生成矩阵的标准型。
用多项式表示的生成多项式的标准型为：
[G(x)]=
x n-1
x n-2 … x n-k
r 1(x) r 2(x) … r k (x)
其中r 1(x)、r 2(x)…rk (x)分别为码字多项式x n-1，x n-2…xn-k 除以g(x)的余式多项式。
生成矩阵标准型为：
[G]=
1 0 … 0 0 1 … 0 … 0 0 … 1
[r1] [r2] … [rk ]
[r1] [r2] [rk ]分别为r 1(x)、r 2(x)…rk (x)的向量形式。 例如：二元(7,4)循环码的生成矩阵的标准型。 由g(x)=x3+x+1
r 1(x)=xn-1/g(x)=x6/g(x)=x2+1 [mod g(x)] 对应矢量[r1]=[101]。
r 2(x)=xn-2/g(x)=x5/g(x)=x2+x+1 [mod g(x)] 对应矢量[r2]=[111]。
r 3(x)=xn-3/g(x)=x4/g(x)=x2+x [mod g(x)] 对应矢量[r3]=[110]。
r 4(x)=xn-4/g(x)=x3/g(x)=x+1 [mod g(x)] 对应矢量[r4]=[011]。
得到其生成矩阵的标准型为：
[G]=
1 0 0 0 1 0 1 0 1 0 0 1 1 1
0 0 1 0 1 1 0 0 0 0 1 0 1 1
看出[G]=[Ik ,Q]，由[G][H]T =[0]可得：系统循环码的监督矩阵为：
[H]=
1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1
到这里我们有两种办法得到系统线性分组码的生成矩阵标准型和监督矩阵；一种是上面介绍的已知g(x)的方法，另一种是已知非标准型矩阵通过初等变换的方法。 [H]矩阵通过列换位，可以变为标准型；
[G]矩阵通过列换位和初等行变换，可以变为标准型。 [大数逻辑译码的原理]：
首先通过一个例子说明大数逻辑译码的基本思想。已知(7,3)线性分组码的生成多项式为：g(x)=x4+x3+x2+1，得到其监督矩阵为：
1 [H]1 = 1
0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
设发送码字矢量为：C=(c6,c 5,c 4,c 3,c 2,c 1,c 0) ，错误图样矢量为：E=(e6,e 5,e 4,e 3,e 2,e 1,e 0) ，接收码字为R=C+E。相应的校验子为 [S]T =[H][E]T =
1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 e 6 e 5
… e 0
s 3 s 2 s 1 s 0
利用这个方程组的线性组合（变换），得到另一组校验方程： A 1=s3=e6+e4+e3 A 2=s1=e6+e5+e1
A 3=s2+s0=e6+e2+e0
这三个方程组的系数构成三个矢量，(1011000),(1100010),(1000101)是[H]矩阵的行向量的线性组合，
对于发送码字[C]，根据[H][C]T =[0]，可知：[A1][C]T =[A2][C]T =[A3][C]T =[0]，或
1 1 1 0 1 0 1 0 0
1 0 0 0 0 0 1 0 0 1 0 1
c 6 c 5 … c 1 c 0
=[H0][C]T =[0]
这样得到了一个新的校验方程： c 6+c4+c3=0 c 6+c5+c1=0 c 6+c2+c0=0
构造的这个监督方程组有这样一个特点：每个方程中都有c 6，而c 5,c 4,c 3,c 2,c 1,c 0则在各方程中只出现一次。有这种特点的监督方程称为正交于c 6的正交监督方程。其系数矩阵[H0]称为正交监督矩阵。
1 0 1 1 0 0 0
[H0]
1 1 0 0 0 1 0 =
1 0 0 0 1 0 1
[定义]：如果一个特定的码元(xn-i ) 出现在[H0]矩阵的每个行，而其它码元最多在其中一行中出现，则称[H0]为正交于码元(xn-i ) 的正交一致监督矩阵。
(7,3)循环码能够纠正一位错，同时检出两位错。如果利用这个正交监督矩阵对接收码字进行校验，可以看到：
如果只发生一位错，且r 6错，e 6=1，则A 1=A2=A3=1;
如果只错一位，但r 6没错，e 6==0，e i =1，则A 1,A 2,A 3, 中只有一个相关的A 等于1，其它两个等于0；
如果发生两位错，其中一位为r 6错，e 6=1，另一位为e 5=1，则A 1=1，A 2=1，A 3=0;
如果发生两位错，都不在正交位，e 5=e4=1，则A 1=1，A 2=0，A 3=1;
如果发生两位错，都不在正交位，e 4=e3=1, or e5=e1=1 or e2=e0=1, 则A 1=A2=A3=0; 可知：
如果发生一位错且错在正交位上，则三个A 中为1的个数大于2（=3）；
如果发生一位错且没错在正交位上，则三个A 中为1的个数小于2（=1）；
如果发生两位错，则三个A 中为1的个数等于2或等于0； 结论：
[定义]：利用正交监督矩阵进行译码，可以根据三个A 中取值为1的个数，对正交码元(r6) 码元纠错，同时，根据循环码的循环特性，纠正其它各位的错误。这种译码方法称为大数逻辑译码。对于以上例子中的译码过程，只要用一次大数逻辑判决就可以完成该位的译码，称为一步大数逻辑译码。
[大数逻辑译码器]：(门限译码器)
以(7,3)循环码为例，说明大数逻辑译码器的工作原理。译码器的
电路如下：
其工作过程如下：
由(7,3)循环码生成多项式g(x)=x4+x3+x2+1的除法电路，计算R(x)的校验子多项式S(x)。n=7次移位后得到校验子(s0,s 1,s 2,s 3) ，存在校验子移位寄存器中，此时，R(x)已全部进入7级缓存器中。
停止译码器输入，并开始对r n-1=r6进行检查，也就是检查A 1=s3，A 2=s1，A 3=s2+s0中1的个数。如果1的个数为3，大数门输出1。此时，缓存器移位一次，输出r 6，对它进行纠错，如果1的个数小于3，大数门无输出，r 6直接输出。
除法电路循环移位一次，对r 5进行检查，此时校验子寄存器中的内容是对r 5的计算结果。如果大数门输出1，则对r 5进行纠错，否则，r 5直接输出。
重复上述步骤，直至n=7次为止；
第n=7次移位完毕后，如果校验子除法电路的状态为全0，则说明R(x)中的错误是可以纠正的，否则说明是不可纠正的。若
是不可纠正的，译码器送出一个信号至用户，表示R(x)有误。然后重新清洗译码器的初始状态，准备接收第二各码字。
图中的虚线是把大数门输出的1反馈到除法电路的输入端，以
消除该错误码元对除法电路的影响。
[二步大数逻辑译码]：
例如：对于(7,4)循环码，g(x)=x3+x+1。它的一致监督矩阵为：
[H]
=
由[S]T =[H][E]T 可得：
s 2=e6+e4+e3+e2
s 1=e6+e5+e4+e1
s 0=e5+e4+e0
这时可以看出无法用一步大数逻辑译码实现，但可以用两步大数逻辑译码方法实现。可以定义：
A 11=s2=(e6+e4)+e3+e2
A 12=s1=(e6+e4)+e5+e1
A 21=s1=(e6+e5)+e4+e1
A 22=s2+s0=(e6+e5)+e2+e0
得到两组正交监督方程，再定义：
A 1=e6+e4
A 2=e6+e5
这样通过两次大数逻辑判决可以确定错误码元的位置。下面是(7,4)循环码二步大数逻辑门译码器原理图。
6-40 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1
6-41
6-2 循环码(Cyclic Code)
循环码是线性分组码的最重要的一类码，它的结构完全建立在有限域多项式的基础上。它具有两个基本特点：一是编码电路与译码电路非常简单，易于实现；二是其代数性质好编码译码分析方便，有一些好的译码方法。 6-2-1 循环码的描述
[循环码定义]：
一个(n,k)线性分组码C ，如果码组中的一个码字的循环移位也是这个码组中的一个码字，则称C 为循环码。
C (0)={cn-1,c n-2,……c1,c 0} ∈C C (1)={cn-2,c n-3,……c0,c n-1} ∈C 称为具有循环自闭性。 [循环码的多项式描述]：
循环码可以用监督矩阵和生成矩阵描述，但更多地用域上多项式来描述，一个(n,k)循环的码字矢量C (0)用一个n-1次多项式描述，可以表示为：
C(x)= cn-1x n-1+cn-2x n-2+……+c1x+c0 这个多项式称为码字多项式。
码字矢量的循环移位可以用x 乘上C(x)后的模x n -1(xn +1)来表示。 xC(x)= x(cn-1x n-1+cn-2x n-2+……+c1x+c0) = cn-1x n +cn-2x n-1+……+c1x 2+c0 x
= cn-2x n-1+……+c1x 2+c0 x+ cn-1 (模x n +1)
模x n +1相当于x n +1=0；x n =1 [循环码举例]：
(7,4)系统循环码的编码及码字多项式如下表：
可以看出：每个码字的循环移位仍然属于这个码组，
注意：并不是说这个码组是由一个码字的循环移位构成的，本例中是由四个码字的循环移位构成的。
[生成多项式的定义]：
在一个(n,k)循环码中，有且仅有一个次数为n-k=r的码字多项式，记为：
g(x)=xr +gr-1x r-1+……+g1x+1
同时：每个码字多项式都是g(x)的倍式；每个次数小于等于n-1的g(x)的倍式必为一个码字多项式。这时称g(x)的(n,k)码的生成多项
式。
从上面的例子可见，g(x)=x3+x+1为(7,4)循环码的生成多项式。 [生成多项式的性质]：
循环码C 中次数最低的非零码字多项式是唯一的，其次数为r=n-k。
令g(x)=xr +gr-1x r-1+……+g1x+g0为一个(n,k)循环码C 中最低次数码字多项式，则其常数项必为g 0=1。 [定理1]：
(n,k)循环码的生成多项式g(x)是x n +1的因式。
{证明}：已知g(x)为一个n-k 次多项式，则x k g(x)为一个n 次多项式，则必有：
x k g (x ) g (k ) (x )
=1+n
x n +1x +1
因为x k g(x)是g(x)的循环移位，它也是一个码字多项式，所以一定为g(x)的倍式，即有：g (k)(x)为g(x)的循环移位在模x n +1下的结果，因此有：g (k)(x)=q(x)g(x)，由上面的关系式可知：
x k g(x)=(xn +1)+g(k)(x)
x n +1=xk g(x)+q(x)g(x)=[xk +q(x)]g(x) 因此，g(x)为x n +1的因式。 [定理2]：
若g(x)是一个n-k 次多项式，且为x n +1的因式，则g(x)生成一个(n,k)循环码。
这个定理说明：x n +1的次数为n-k 的任何一个因式，均可以生成
一个(n,k)循环码。对于较大的n ，x n +1可以有多个n-k 次多项式，产生不同的(n,k)循环码，但可能有好有坏。
例如：多项式x 7+1可以分解为： x 7+1=(x3+x+1)(x3+x2+1)(x+1)
可以看出有两种(7,4)循环码的生成矩阵 g(x)= (x3+x+1)和g(x)= (x3+x2+1)。
还可以产生一种(7,6)循环码， 6-2-2 循环码的编码方法
[系统循环码的编码方法]：
已知循环码的生成矩阵可以按以下步骤产生系统循环码。 首先定义以下多项式：
m(x)=mk-1x k-1+mk-2x k-2+……+m1x+m0 为信息码字多项式； c(x)=cn-1x n-1+cn-2x n-2+……+c1x+c0 为循环码字多项式； g(x)=xr-1+gr-2x r-2+……+g1x+1 为生成多项式； 系统码的编码分为三步： 用x n-k 乘上m(x);
用g(x)除以x n-k m(x)，得到模g(x)的余式r(x)
x n -k m (x ) r (x )
=q (x ) + g (x ) g (x )
c(x)=xn-k m(x)+r(x)为系统循环码的码字多项式。 [例题1]：
(7,4)循环码的生成多项式为g(x)=x3+x+1
求m=[1010]的循环码。 解：m(x)=x3+x, x n-k =x3; x n-k m(x)=x3(x3+x)=x6+x4
x n -k m (x ) x 6+x 4x +1
=3=x 3+1+3 g (x ) x +x +1x +x +1
r(x)=x+1
C(x)=xn-k m(x)+r(x)=x6+x4+x+1 [例题2]：
(7,3)循环码的生成多项式为g(x)=x4+x3+x2+1=(x+1)(x3+x+1) 求：[m]=[010]的循环码字[C] 解：m(x)=x; x n-k m(x)=x4x=x5
x 5x 2+x +1
=x +4
x 4+x 3+x 2+1x +x 3+x 2+1
C(x)=x5+x2+x+1 [非系统循环码的编码方法]：
已知循环码的生成矩阵，可以方便的求出非系统循环码， C(x)=m(x)g(x)
例如：m=[1101] g(x)=x3+x+1
C(x)=(x3+x2+1)(x3+x+1)=x6+x43532+x3+x+1=x6+x5+x4+x3+x 2+x+1 [C]=[1111111]
m=[0101]; c(x)=(x2+1)(x3+x+1)=x53235+x2+x+1
[C]=[0100111] [循环码的生成矩阵]：
循环码可以用域上多项式描述，也可以用生成矩阵描述。 已知g(x)为循环码C 中的一个码字多项式，由循环码的循环特性可知，可以证明：在(n,k)循环码的码字多项式中，g(x),xg(x),……xk-1g(x)等k 个码字多项式必是线性无关（相互独立的）的。根据线性空间的特性，可知，它们是一个k 维子空间的基底，即由它们的线性组合可以生成这个k 维子空间的2k 个码字。再根据线性分组码生成矩阵的定义，它的行向量是由k 个线性无关的码字构成的，可以得到(n,k)循环码的一个多项式矩阵为：
[G(x)]=
相应的生成矩阵为
g n-g n-k-… g 1 g 0 0 0 … 0
k 1
0 g n-k g n-k-… g 1 g 0 0 … 0
[G]= 1
… 0 … … 0 g n-k g n-k-… g 1 g 0
1
由这个基本关系式可以看出，当输入信息码字矢量为(mk-1,m k-2, ……m0) 时，相应的码字多项式为：
C(x)=(mk-1,m k-2, ……m0)G(x) =(mk-1x k-1+mk-2x k-2+……+m0)g(x) =m(x)g(x)
x k-1g(x) x k-2g(x) … g(x)
利用这种方法产生的循环码为非系统循环码，因为，[G(x)]为非标准型生成矩阵，（非典型生成矩阵）。
这个非标准型生成矩阵可以通过矩阵的初等变换转换为标准型生成矩阵。可以通过以下例子说明。
[例题]：已知(7,4)循环码的生成多项式为g(x)=x3+x+1，其非标准型生成矩阵为：
x 3g(xx 6+x4+x3 1 0
) 2
[G(x)]x g(xx 5+x3+x2 0 1
= =
= )
xg(x) x 4+x2+x 0 0
3
g(x) x +x+1 0 0
1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 利用不同的矩阵变换可以得到不同的标准型生成矩阵。 这种变换包括： 列换位； 初等行变换；
通过以上两种方法，可以得到标准型生成矩阵：
[G]=
1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1
只使用初等行变换可以得到标准生成矩阵：
[G]=
可知标准型生成矩阵是不唯一的。 6-2-3 校验子与循环码的译码原理
设发送的码字多项式位C(x)，错误图样多项式位E(x)，则接收码
字多项式为：
R(x)=C(x)+E(x) 译码器的工作过程为：
由接收码字多项式R(x)计算校验子多项式S(x); 根据校验子多项式S(x)计算错误图样多项式E(x); 利用R(x)-E(x)=C(x)计算译码器输出的估计值。 发送码字多项式为：
C(x)=cn-1x n-1+cn-2x n-2+……c1x+c0 接收码字多项式为；
R(x)=rn-1x n-1+rn-2x n-2+……+r1x+r0 校验子多项式为：
E(x)=en-1x n-1+en-2x n-2+……e1x+e0 由R(x)=C(x)+E(x)可知： r i =ci +eI i=0,1,…n-1 这时定义校验子多项式为：
S (x ) =
R (x ) C (x ) +E (x ) C (x ) E (x ) E (x )
==+≡ [模g(x)] g (x ) g (x ) g (x ) g (x ) g (x )
即：S(x)≡E(x)≡R(x) [模g(x)]
也就是说，接收码字多项式除以g(x)的余式多项式为校验子多项式。
如果：S(x)=0，表示接收码字无错； 如果：S(x)≠0, 表示接收码字有错；
(n,k)循环码的校验子多项式的一般表达式为：
S(x)=sr-1x r-1+sr-2x r-2+……+s1x+s0
即校验子多项式S(x)为一个r-1次多项式。其校验子矢量为： [S]=[sr-1,s r-2,……s1,s 0]
它共有2r 个状态，当2r ≣n+1时，即可以纠一位错。 [例题]：(7,4)循环码的校验子及译码， 已知：(7,4)循环码的生成矩阵为g(x)=x3+x+1 考虑接收码字不错或只错一位时的校验子多项式。 发送码字多项式为：
C(x)=cn-1x n-1+cn-2x n-2+……c1x+c0 接收码字多项式为；
R(x)=rn-1x n-1+rn-2x n-2+……+r1x+r0 校验子多项式为：
E(x)=en-1x n-1+en-2x n-2+……e1x+e0
这个表给出了接收码字不出错或只错一位时校验子多项式和校验子矢量的结果。根据这个表可以进行译码。
例如：发送码字为：C={0010110}，接收码字为：，表明r 3错。
接收码字多项式为：R(x)=x4+x3+x2+x, g(x)=x3+x+1，校验子多项式为：
R (x ) x 4+x 3+x 2+x
S (x ) ==≡x +1 [模g(x)]
g (x ) x 3+x +1
S(x)=x+1 [s2,s1,s0]=[011] 查表可知r 3出错。
已知(7,4)循环码的最小汉明距离dmin=3，只能纠一位错，当接收码字出现两位错时将不能纠正。
例如：发送码字为：C={0010111}，接收码字为：，表明r 3和r 0错。
R(x)=x4+x3+x2+x+1
S(x)=x; [s2,s 1,s 0]=[010]，根据校验子表可知，译码器判为r 1错，这时产生译码错码。 6-2-4 循环码的编码电路
根据循环码的编码方法，可知编码电路应当是一个多项式的除法电路，它是码字多项式的循环一位后除以生成多项式。
[系统码编码器]：
为了构成系统码，可知C(x)=xn-k m(x)+r(x) r(x)=xn-k m(x)/g(x) [模g(x)] 以(7,4)汉明码为例：g(x)=x3+x+1
编码器电路如图所示：它由n-k 级移位寄存器构成。
这是一个由n-k=3级移位寄存器及加法器、或门和门控电路构成的。
移位寄存器的初始状态为全0，门1开，门2关。信息码元以
[m3,m 2,m 1,m 0]依次输入编码器。信息码元一方面通过或门输出，另一方面送入除法电路。在除法电路的右端输入m(x)相当于完
成了循环移位n-k=3位。
四次移位后，信息码元已输出，形成了系统循环码的前四位信
息位。同时寄存器中存放的就是余式多项式的系数，从右到左
分别是(c2,c 1,c 0) 。
门1关，门2开，经三次移位，这三个监督位从编码器输出。 门1开，门2关，进行第二个码字的编码。
m=[1001], C=[1001 110]的编码过程如下表：
(7,3)循环码的生成矩阵为：g(x)=x4+x3+x2+1
其编码电路为：
由于n-k=r=4所以编码器有四级移位寄存器。
[非系统循环码编码电路]：
非系统循环码的产生为：C(x)=m(x)g(x),可知其编码器为如下：
m(x)
例如m=[1110]，编出的循环码字为：C=[1100001]
C(x)=m(x)g(x)=(x3+x2+x)(x3+x+1)=x6+x5+1
6-3 循环码的译码
循环码的编码电路由n-k 级移位寄存器构成，比较简单，但是循环码的译码电路就相对比较复杂。因此，循环码的译码方法是研究编码理论和编码技术的重要内容。
线性分组码（不仅是循环码）的译码大体分为两类：一是利用码字的代数结构进行译码，称为代数译码方法。另一类不仅利用代数结构，而且还利用概率理论，称为概率译码。这里我们重点介绍代数译码方法，包括捕获（错）译码，大数逻辑译码。
6-3-1 梅吉特(Meggit)译码器
上面我们介绍了循环码的校验子（伴随式）译码的基本原理，已知：
S(x)=R(x)/g(x) [mod g(x)]
这里首先介绍一个有关校验子多项式的重要特性。
[定理]：
设S(x)是接收码字多项式R(x)的校验子多项式，则R(x)的循环移位xR(x)[mod x n +1]的校验子S 1(x)是S(x)在g(x)除法电路中无输入时右移一位的结果。
S 1(x)≡xS(x) [mod g(x)]
[证明]：由校验子多项式的定义可知，
S(x)≡R(x) [mod g(x)]，两边同时乘以x 可得；
xS(x)≡xR(x) [mod g(x)]
这时如果定义
S 1(x)≡xR(x) [mod g(x)]
显然有S 1(x)≡xS(x) [mod g(x)]
[定理的推广]：
这个定理的结果可以推广为，对于任意给定的j=1,2,…,n-1，必有x j R(x)的校验子多项式为：
S j (x)=xj R(x)/g(x)≡x j S(x) [mod g(x)]
同时有任意多项式a(x)乘R(x)所对应的校验子多项式
S a (x)=a(x)R(x)/g(x)≡a(x)S(x) [mod g(x)]
校验子多项式的这些性质，在循环码的译码中有重要作用。
[梅吉特译码原理]：
如果：C(x)为循环码C 中的一个码字多项式，则xC(x)[mod xn +1]也是这个码组中的一个码字。
如果：S(x)为R(x)=C(x)+E(x)的校验子多项式，则xS(x)也必然是xR(x)=xC(x)+xE(x)的校验子多项式。
这表明：如果E(x)是一个译码器可以纠正的错误图样（相当于译码标准阵中的陪集首），则xE(x)也是一个可以纠正的错误图样，x j E(x) (j=1,2,…,n-1) 也是可以纠正的错误图样。
这样就可以根据这种循环关系，对错误图样分类，将任一错误图样及其所有n-j 次的循环移位归为一类。
同一类的错误，可以使用同一个译码单元电路，可以简化译码器电路的复杂性。
例如：可以将“只错一位”的错误图样(100…0),(010…0),…,(00…01)归为一类，这样用一个错误图样(100…0)的校验子S(x)代表这一类错误图样的校验子。
这样可以大大减少译码器要识别的错误图样类别的个数：
一个(n,k)循环码，要纠正t 位错误，译码器要识别的错误图样总数为：
Ne =∑C n j
j =1t
例如(7,4)循环码可以纠正一位错，n=7，t=1，N e =C71=7。
而通过分类后，译码器需要识别的错误图样的类别数为：
-1N g =∑C n j -1
j =1t
例如(7,4)循环码的错误图样类别数为N g =1。可以看到通过分类识别，可以简化循环码译码器的复杂性。
[例题]：(7,4)循环码的生成矩阵为g(x)=x3+x+1，通过前面分析可知，只要接收码字矢量只错一位，译码器总可以正确译码。
在构造此译码器的错误图样识别电路时，只要识别一个错误图样例如，E 6=[1000000]就可以了。这个错误图样对应的校验子矢量为S=[101]，由此可以得到一种译码器结构如图：
这个译码器上面是一个g(x)除法电路，下面是一个7级移位寄存器作为缓存器，中间的反相器和一个与门组成了(101)校验子识别电路。译码过程如下：
开始译码时门打开，移位寄存器内容位全0。收到的码字多项
式位R(x)=r6x 6+…+r0 由高次到低次分别输入到7级缓存器和
除法电路，7次移位后，缓存器存入整个码字，除法电路
[S(x)=E(x)/g(x), E(x)=x6]得到校验子S 0=[s2,s 1,s 0]。这时门关上，
进行译码。
如果S 0(x)=x6=x2+1[mod g(x)]，这时[101]识别电路输出为1，
表明r 6为有错。
这时译码器继续移位，通过[101]识别电路可以将r 6位的错误纠
正。
在纠错的同时，[101]识别电路的输出又反馈到除法电路的输入
端，以消除错误码元对除法电路的下一个校验子计算的影响。校验子产生电路开始在无输入的情况下移位，相当以开始产生
x j S(x)。
本电路中，第7次移位后产生了校验子S 0，第8次移位时对r 6进行纠正，同时将[101]识别电路的输出的1输入到除法电路的输入端，结果使除法电路的寄存器状态为[000]，消除了e 6的影响。
下面我们看一下，利用这个电路能否纠正其它错误图样的接收码字。
如果E(x)=x5, 表明e 5=1或E=[0100000]，这时经过前7次移位
后得到的校验子多项式为S 0(x)=x5=x2+x+1[mod g(x)]，这时除
法电路的移位寄存器状态为[111]，[101]识别电路的输出为0，说明r 6正确，不必纠正。
第8次移位后，r5移位到缓存器的最右端。同时校验子除法电
路的结果根据定理可知：（通过电路分析也可以看出）
S 1(x)=xS0(x)=xE(x)=x6=x2+1 [mod g(x)] 产生[101]状态；
这时[101]识别电路输出1，对r 5进行纠正。
可以看到，利用循环码的循环特性，可以简化译码器的复杂性。 从上述译码过程中可以看到，(n,k)循环码的译码器译一个码字共需要2n 次移位，不能实现连续译码，为了实现连续译码，可以再加一套除法电路，
其工作过程如下：
译码前两个移位寄存器为全0状态，门1开，门2关，当k=4
次移位后，4级缓存器接收到码字的前4位信息位。
此时，门1关。再移位n-k=3次后，上面的除法电路得到校验
子S 0(x)，
这时门2开，将上面除法电路得到的校验子送入下面的除法电
路，随即门2关闭，且上面的除法电路清0。
门1再次打开，4级缓存器一边送出第一组信息，一边接收第
二个码字的信息位，与此同时，上面的除法电路计算第二个码字的校验子，下面的除法电路对第一组码字进行纠错。
以上是对系统码而设计的电路，如果是非系统码，k 级缓存器
应改为n 级，而且要在得到的码字中恢复信息位。根据m(x)=C(x)/g(x)，应再加一个除法电路。
上面介绍的系统循环码的一般译码器称为梅吉特译码器。
6-3-2 捕错译码
循环码的译码器的复杂性主要取决于由校验子确定错误图样的组合逻辑电路的复杂性，另外一种译码方法称为捕错译码，其特点是适应于纠突发错误码。
[工作原理]：
设C(x)是一个纠t 位错误的(n,k)系统循环码的码字多项式，而相应的接收码字多项式为：R(x)=C(x)+E(x)，译码器得到的校验子多项式为：
S(x)=R(x)/g(x)=E(x)/g(x)≡E(x) [mod g(x)]
≡E I (x)+EP (x), [mod g(x)]
其中：
E I (x)=en-1x n-1+en-2x n-1+…+en-k x n-k
E P (x)=en-k-1x n-k-1+…+e1x+e0
E I (x)为k 位信息位的错误图样，E P (x)是n-k=r位监督位的错误图样。
这时可以看到：
如果：错误图样多项式E(x)的次数=n-k-1=r-1，
即码字中的错误集中在n-k=r监督位上，
即e n-1=en-2=…=en-k =0；
则：E I (x)=0，E(x)=EP (x)。
又因为：生成多项式g(x)的次数位n-k=r，
所以：校验子多项式S(x)=E(x)/g(x)=EP (x), [mod g(x)]
得到的结论是：对于具有这样的错误图样的码字C(x)，经过循环移位后，可以使S(x)=E(x)，译码过程就可以变为：C(x)=R(x)-S(x)。(在GF(2)上，减法与加法一样)
要使一个码字的错误码元全部集中在码字的后n-k=r位上，只要求错误码元集中在任意连续n-k 位上即可。因为：码字多项式的循环移位和校验子多项式的循环移位有一一对应的关系。
[捕错译码的定义]：
若接收码字R(x)对应的校验子多项式为S 0(x)，经过i 次循环移位后，x i R(x)=Ri (x)对应的校验子多项式为S i (x)。一旦检测出S i (x)的重量W(Si (x))≢t ，就认为此时码字的错误码元已经全部集中在x i R(x)=Ri (x)的后n-k 位以内了。这时可以由R i (x)-Si (x)得到已经纠错的接收码字C i (x)=xi C(x)，但码字顺序不对，将其再进行n-i 次循环移位，即可得到:
C(x)=xn C(x)=xn-i x i C(x)
从而纠正了错误，这种译码方法称为捕错译码。
[捕错译码的适应条件]：
只有当所有小于等于t 个错误全部集中再连续n-k=r位以内时，
捕错译码才有效。
当码字的错误突发长度b 小于等于(n-k)/2时，捕错译码才有效。 例如：(7,4)码，d min =3, t=1, n=7, k=4, n-k=3 (n-k)/2=1.5 所以b=1
(15,7)码，d min =5, t=2, n-k=8, (n-k)/2=4 b=4,
如果一个(n,k)码可以纠正t 位错，使用捕错译码的必要条件是： k
[定理]：捕错译码的判别条件
纠正t 位错误的(n,k)二元循环码，捕错译码器已经把t 个错误集中在R i (x)的最低n-k 位以内的充要条件，是此时的校验子矢量的汉明重量：
W(Si (x))≢t
[证明]：
如果错误已经集中在最低n-k 位以内，则
S i (x)≡x i E(x)=Ei (x)=EP (x) [mod g(x)]
S i (x)=EP (x)
由于这个(n,k)码只能纠t 位错，所以，对于一个可纠正的错误图样，必有：
W(E(x))≢t
而E(x)的循环移位后，其矢量的汉明重量是不变的，则
W(Si (x))=W(Ei (x))≢t
这说明：只要能纠t 位错的码已经把错误码元集中到最低n-k 位上，公式W(Si (x))≢t 就一定成立。
反之；再证明：如果W(Si (x))≢t 满足，则错误码元就一定集中在最低n-k 位码元内了。利用反证法：
即当W(Si (x))≢t 满足时，错误码元没有集中到码字的最低n-k 位码元内，
则必有循环移位后的错误图样多项式E i (x)的次数大于等于g(x)的次数。 进
而
有
：
E i (x)=q(x)g(x)+Si (x),
相
应
有
：
C i (x)=Ei (x)+Si (x)=q(x)g(x)；
这样组成的C i (x)为g(x)的倍式，必然为一个码字多项式， 再由定理，线性分组码的最小码距等于非0码字的最小汉明重量，有：
W(Ei(x)+Si(x))=W(Ci(x))≣d=2t+1 (已知码字可纠t 位错) 由汉明三角不等式：对于一个(n,k)线性分组码C ，C 1,C 2,C 3为C 中的三个码字，并为C 3=C1+C2，这时有：d(C1,C 2) ≢d(C1,C 3)+d(C3,C 2) ，或表示为 W(C1+C2) ≢W(C1)+W(C2)
W(Ei (x))+W(Si (x))≣W(Ei (x)+Si (x))≣d=2t+1 由已知W(Ei (x))≢t ，所以得出W(Si (x))≣t+1>t； 这与立题假设W(Si (x))≢t ，矛盾，
这说明当W(Si (x))≢t 时，错误码元不可能不集中在码字的最低
n-k 位码元内。 定理证毕。
[例题]：已知二元(15,7)循环码，生成多项式g(x)=x8+x7+x6+x4+1，d min =5，其纠错能力为t=2，可以纠两位错。由t=2
译码过程如下：
译码前所有移位寄存器和缓存器都为全0状态，门2，门3开，门1，门4，门5关。n=15次移位后，接收码字的R(x)的15个码元全部进入15级缓存器，信息元在前7级，监督元在后8级，同时进入除法电路，得到校验子多项式S 0(x)。如果S 0(x)=0，说明无错，打开门5，输出接收码字。如果S 0(x)≠0，说明有错，进行以下各步。
此时门2关，门1开，如果W(S0(x))≢2，检测电路输出有效，
把门4打开，把门3关闭，此时除法电路移位寄存器中的内容就是接收码字的后8位的错误图样，只要接收码字只错2位或2位以下，后8位错误图样就等于全部错误图样。这时移位15次，除法电路的状态S 0(x)=EP (x)通过门4与接收码字的后8位逐次相加，完成纠错。然后门1关，门5开，再移位15次，输出接收码字。
如果W(S0(x))>2，则15级缓存器和除法电路都循环移位一次，再次检测，若仍大于2，则继续移位，当移位I 次后，检测到W(S0(x))≢2，则说明已经检测出错误图样已进入缓存器的后8位。这时门3关闭，门4打开，继续移位n-I 次，进行纠错。最后门1关，门2，门5开，再移位15次输出正确的接收码字。 从以上步骤中可以看出，译码器完成一个码字的译码，共需要3n 次移位。
这里介绍的是捕错译码器的基本原理，若要实现连续译码，还要进行一些改进，一方面力图使译码器电路简单化，另一方面提高译码速度，减少移位次数。 6-3-3 大数逻辑译码
循环码译码器的复杂性取决于码的代数结构，对于一类循环码来说，有一种比较简单的译码方法称为大数逻辑译码，1954年由Reed 提出。
[循环码的监督矩阵描述]：
前面我们介绍过，已知循环码的生成多项式g(x)，可以得到非系
统循环码的生成矩阵。
[G(x)]=
相应的生成矩阵为：
g n-g n-k … g 1 g 0 0 … 0 k -1
0 g n-k g n-k-… g 1 g 0 … 0
1
… … 0 … 0 g n-k g n-k-1 … g 1 g 0
x k-1g(x) x k-2g(x) … g(x)
[G]=
根据循环码的生成多项式一定为x n +1的因式，有 x n +1=g(x)h(x)=(gn-k x n-k +…+g1x+g0)(hk x k +…+h1x+h0) 根据这个关系可以看出： g n-k h k =1 g 0h 0=1
而其它乘积项的系数为0。即 g 0h 1+g1h 0=0 g 0h 2+g1h 1+g2h 0=0 …
g n-1h 0+gn-2h 1+…+gn-k h k-1=0
根据生成矩阵与监督矩阵的关系，可知
[H]=
h 0 h 1 0 h 0 … 0 0
… h 1 …
h k … 0
0 h k h 0
0 0 h 1
… 0 … 0 … … h k
[H]矩阵为n-k 行n 列。它完全由h(x)的系数决定的，h(x)称为循环码的校验多项式或称为监督多项式。生成矩阵与监督矩阵的关系
为：
[G][H]T =[0]
例如：(7,4)循环码的生成多项式g(x)=x3+x+1，而监督多项式为h(x)=x4+x2+x+1。相应的生成矩阵和监督矩阵分别为：
[G]=
[H]=
1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1
0 0 0 1
可以验证：[G][H]T =[0]，还可以看出，这个监督矩阵经过列变换可以变为系统码的监督矩阵，而且就是汉明码的一致监督矩阵。
如果将这个码的生成矩阵当作另一个码的监督矩阵，而将这个码的监督矩阵当作另一个码的生成矩阵，这另一个码就是这个码的对偶码。
例如：g(x)=x3+x2+1的(7,4)循环码，是g(x)=x4+x3+x2+1的(7,3)循环码的对偶码，
g(x)=x3+x+1的(7,4)循环码，是g(x)=x4+x2+x+1的(7,3)循环码的对偶码。
[系统循环码的生成矩阵与监督矩阵]：
由于循环码的生成矩阵的每一行都为一个码字，系统循环码的生成矩阵的k 个行向量分别为(10…0),(010…0),….(00…01) 信息码对应的循环码字。因此，已知一个(n,k)码的生成多项式，求出这些码字所
对应的监督码元作为行向量的后r 位，就可以得到生成矩阵的标准型。
用多项式表示的生成多项式的标准型为：
[G(x)]=
x n-1
x n-2 … x n-k
r 1(x) r 2(x) … r k (x)
其中r 1(x)、r 2(x)…rk (x)分别为码字多项式x n-1，x n-2…xn-k 除以g(x)的余式多项式。
生成矩阵标准型为：
[G]=
1 0 … 0 0 1 … 0 … 0 0 … 1
[r1] [r2] … [rk ]
[r1] [r2] [rk ]分别为r 1(x)、r 2(x)…rk (x)的向量形式。 例如：二元(7,4)循环码的生成矩阵的标准型。 由g(x)=x3+x+1
r 1(x)=xn-1/g(x)=x6/g(x)=x2+1 [mod g(x)] 对应矢量[r1]=[101]。
r 2(x)=xn-2/g(x)=x5/g(x)=x2+x+1 [mod g(x)] 对应矢量[r2]=[111]。
r 3(x)=xn-3/g(x)=x4/g(x)=x2+x [mod g(x)] 对应矢量[r3]=[110]。
r 4(x)=xn-4/g(x)=x3/g(x)=x+1 [mod g(x)] 对应矢量[r4]=[011]。
得到其生成矩阵的标准型为：
[G]=
1 0 0 0 1 0 1 0 1 0 0 1 1 1
0 0 1 0 1 1 0 0 0 0 1 0 1 1
看出[G]=[Ik ,Q]，由[G][H]T =[0]可得：系统循环码的监督矩阵为：
[H]=
1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 0 0 1
到这里我们有两种办法得到系统线性分组码的生成矩阵标准型和监督矩阵；一种是上面介绍的已知g(x)的方法，另一种是已知非标准型矩阵通过初等变换的方法。 [H]矩阵通过列换位，可以变为标准型；
[G]矩阵通过列换位和初等行变换，可以变为标准型。 [大数逻辑译码的原理]：
首先通过一个例子说明大数逻辑译码的基本思想。已知(7,3)线性分组码的生成多项式为：g(x)=x4+x3+x2+1，得到其监督矩阵为：
1 [H]1 = 1
0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1
设发送码字矢量为：C=(c6,c 5,c 4,c 3,c 2,c 1,c 0) ，错误图样矢量为：E=(e6,e 5,e 4,e 3,e 2,e 1,e 0) ，接收码字为R=C+E。相应的校验子为 [S]T =[H][E]T =
1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 e 6 e 5
… e 0
s 3 s 2 s 1 s 0
利用这个方程组的线性组合（变换），得到另一组校验方程： A 1=s3=e6+e4+e3 A 2=s1=e6+e5+e1
A 3=s2+s0=e6+e2+e0
这三个方程组的系数构成三个矢量，(1011000),(1100010),(1000101)是[H]矩阵的行向量的线性组合，
对于发送码字[C]，根据[H][C]T =[0]，可知：[A1][C]T =[A2][C]T =[A3][C]T =[0]，或
1 1 1 0 1 0 1 0 0
1 0 0 0 0 0 1 0 0 1 0 1
c 6 c 5 … c 1 c 0
=[H0][C]T =[0]
这样得到了一个新的校验方程： c 6+c4+c3=0 c 6+c5+c1=0 c 6+c2+c0=0
构造的这个监督方程组有这样一个特点：每个方程中都有c 6，而c 5,c 4,c 3,c 2,c 1,c 0则在各方程中只出现一次。有这种特点的监督方程称为正交于c 6的正交监督方程。其系数矩阵[H0]称为正交监督矩阵。
1 0 1 1 0 0 0
[H0]
1 1 0 0 0 1 0 =
1 0 0 0 1 0 1
[定义]：如果一个特定的码元(xn-i ) 出现在[H0]矩阵的每个行，而其它码元最多在其中一行中出现，则称[H0]为正交于码元(xn-i ) 的正交一致监督矩阵。
(7,3)循环码能够纠正一位错，同时检出两位错。如果利用这个正交监督矩阵对接收码字进行校验，可以看到：
如果只发生一位错，且r 6错，e 6=1，则A 1=A2=A3=1;
如果只错一位，但r 6没错，e 6==0，e i =1，则A 1,A 2,A 3, 中只有一个相关的A 等于1，其它两个等于0；
如果发生两位错，其中一位为r 6错，e 6=1，另一位为e 5=1，则A 1=1，A 2=1，A 3=0;
如果发生两位错，都不在正交位，e 5=e4=1，则A 1=1，A 2=0，A 3=1;
如果发生两位错，都不在正交位，e 4=e3=1, or e5=e1=1 or e2=e0=1, 则A 1=A2=A3=0; 可知：
如果发生一位错且错在正交位上，则三个A 中为1的个数大于2（=3）；
如果发生一位错且没错在正交位上，则三个A 中为1的个数小于2（=1）；
如果发生两位错，则三个A 中为1的个数等于2或等于0； 结论：
[定义]：利用正交监督矩阵进行译码，可以根据三个A 中取值为1的个数，对正交码元(r6) 码元纠错，同时，根据循环码的循环特性，纠正其它各位的错误。这种译码方法称为大数逻辑译码。对于以上例子中的译码过程，只要用一次大数逻辑判决就可以完成该位的译码，称为一步大数逻辑译码。
[大数逻辑译码器]：(门限译码器)
以(7,3)循环码为例，说明大数逻辑译码器的工作原理。译码器的
电路如下：
其工作过程如下：
由(7,3)循环码生成多项式g(x)=x4+x3+x2+1的除法电路，计算R(x)的校验子多项式S(x)。n=7次移位后得到校验子(s0,s 1,s 2,s 3) ，存在校验子移位寄存器中，此时，R(x)已全部进入7级缓存器中。
停止译码器输入，并开始对r n-1=r6进行检查，也就是检查A 1=s3，A 2=s1，A 3=s2+s0中1的个数。如果1的个数为3，大数门输出1。此时，缓存器移位一次，输出r 6，对它进行纠错，如果1的个数小于3，大数门无输出，r 6直接输出。
除法电路循环移位一次，对r 5进行检查，此时校验子寄存器中的内容是对r 5的计算结果。如果大数门输出1，则对r 5进行纠错，否则，r 5直接输出。
重复上述步骤，直至n=7次为止；
第n=7次移位完毕后，如果校验子除法电路的状态为全0，则说明R(x)中的错误是可以纠正的，否则说明是不可纠正的。若
是不可纠正的，译码器送出一个信号至用户，表示R(x)有误。然后重新清洗译码器的初始状态，准备接收第二各码字。
图中的虚线是把大数门输出的1反馈到除法电路的输入端，以
消除该错误码元对除法电路的影响。
[二步大数逻辑译码]：
例如：对于(7,4)循环码，g(x)=x3+x+1。它的一致监督矩阵为：
[H]
=
由[S]T =[H][E]T 可得：
s 2=e6+e4+e3+e2
s 1=e6+e5+e4+e1
s 0=e5+e4+e0
这时可以看出无法用一步大数逻辑译码实现，但可以用两步大数逻辑译码方法实现。可以定义：
A 11=s2=(e6+e4)+e3+e2
A 12=s1=(e6+e4)+e5+e1
A 21=s1=(e6+e5)+e4+e1
A 22=s2+s0=(e6+e5)+e2+e0
得到两组正交监督方程，再定义：
A 1=e6+e4
A 2=e6+e5
这样通过两次大数逻辑判决可以确定错误码元的位置。下面是(7,4)循环码二步大数逻辑门译码器原理图。
6-40 1 0 1 1 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1
6-41