[科普中国]-循环码

循环码是线性码的一个重要的子类，它有以下两大特点：第一，码的结构可以用代数方法来构造和分析，并且可以找到各种实用的译码方法；第二，由于其循环特性，编码运算和伴随式计算，可用反馈移位寄存器来实现，硬件实现简单。1

定义循环码：无权码，每位代码无固定权值，任何相邻的两个码组中，仅有一位代码不同。

一个(n,k)线性分组码C，若它的任一码字的每一循环移位寄存器都是C的一个码字，则称C是一个循环码。

信息组表1(7,4)循环码

信息组

m3 m2 m1 m0

码字
C6 C5 C4 C3 C2 C1 C0

0 0 0 0

0 0 0 0 0 0 0

0 0 0 1

0 0 0 1 1 0 1

0 0 1 0

0 0 1 0 1 1 1

0 0 1 1

0 0 1 1 0 1 0

0 1 0 0

0 1 0 0 0 1 1

0 1 0 1

0 1 0 1 1 1 0

0 1 1 0

0 1 1 0 1 0 0

0 1 1 1

0 1 1 1 0 0 1

1 0 0 0

1 0 0 0 1 1 0

1 0 0 1

1 0 0 1 0 1 1

1 0 1 0

1 0 1 0 0 0 1

1 0 1 1

1 0 1 1 1 0 0

1 1 0 0

1 1 0 0 1 0 1

1 1 0 1

1 1 0 1 0 0 0

1 1 1 0

1 1 1 0 0 1 0

1 1 1 1

1 1 1 1 1 1 1

给出(7,4)循环码，由于循环码是线性分组码的一种，所以它也具有封闭性，任意两个码字相加之和必是另一码字。所以它的最小码距也就是非零码字的最小码重。在表1给出的(7,4)循环码中，dmin=3。而且根据定义，任一码字的每一循环移位的结果都是(7,4)循环码的一个码字。但某一码字的循环移位，并不能生成所有的码字。对于一个循环码来说，可以同时存在多个循环圈。

编码种类十六进制数

自然二进制码

循环二进制码

十六进制数

自然二进制码

循环二进制码

0

0000

0000

8

1000

1100

1

0001

0001

9

1001

1101

2

0010

0011

A

1010

1111

3

0011

0010

B

1011

1110

4

0100

0110

C

1100

1010

5

0101

0111

D

1101

1011

6

0110

0101

E

1110

1001

7

0111

0100

F

1111

1000

特征为了探讨循环码的特征，把码字C=(Cn－1 Cn－2…C1C0)用如下的码多项式C(x)来表示。

（1）特性一

在一个(n,k)循环码中，存在惟一的一个n－k次码多项式：

每一个码多项式C(x)都是g(x)的一个倍式，反之每个为g(x)倍式，且次数小于等于n－1的多项式必是一个码多项式。

由此可见，(n,k)循环码中的每一个码多项式C(x)均可由下式表示：

如果m(x)的系数(mk－1…m1m0)就是表示待编码的k位信息位，则C(x)就是对应于此信息组m(x)的码多项式。因此(n,k)循环码完全可由g(x)确定。g(x)也称为循环码(n,k)的生成多项式。g(x)的次数n－k等于码中一致校验位的位数。

（2）特性二

(n,k)循环码的生成多项式是xn+1的因子，即：

xn+1=g(x)h(x)

其中h(x)称为码的一致校验多项式，循环码的H矩阵也可以通过h(x)来生成。

（3）特性三

若g(x)是一个n－k次多项式，并且是xn+1的因子，则g(x)一定能生成一个(n,k)循环码。

表2.5给出了多项式x7+1中所含有的部分生成多项式和相应的循环码。

循环码的编码

（1）编码方法

根据上述的三个循环码特征，可以有三种(n,k)循环码的编码方法。

表2x7+1中的部分g (x)

循环码

码距

生成多项式g(x)

校验多项式h(x)

(7,6)

2

x+1

(x 3+x+1)(x 3+x 2+1)

(7,4)

3

x 3+x+1

(x 3+x 2+1)(x+1)

(7,3)

4

(x+1)(x 3+x+1)

x 3+x 2+1

(7,1)

7

(x 3+x 2+1)(x 3+x+1)

x+1

① 用生成多项式编码

a．选择一个能除尽xn+1的n－k=r次生成多项式g(x)。

b．由g(x)生成各码多项式。

c．找出与码多项式相对应的循环码字。

② 用生成矩阵编码

有两种求生成矩阵的方法：

a．因为g(x)是最低次数的码多项式。且xg(x)，x2g(x)，…，xk－1g(x)皆为码多项式。用它们构成G，再用行变换把G变换为典型生成矩阵，然后用其编码。

b．用g(x)除xn－k+i (i=0，1，…，k－1)，得：

于是是g(x)的倍式，且次数小于等于n－1，所以为码多项式。用此方法可得到k个码多项式，可以直接构成典型生成矩阵，用以编码。

③ 用余式确定校验位

a.用乘信息多项式m(x)。

b.用g(x)除m(x)得到余式r(x)。

c.生成码多项式m(x)+r(x)。

第一种方法可用乘法电路来完成，第二种方法用生成矩阵G编码是一般线性分组编码的通用方法，利用这一种方法编循环码，体现不出循环码的优点，第三种方法可用除法电路来完成，应用比较广泛。

（2）除法电路编码器

以g(x)=x3+x+1生成(7,4)循环码的编码器为例。

编码器主要由一除法电路构成。除法电路由移位寄存器和模2加法器组成。移位寄存器的个数与g(x)的次数相等。因为g(x)=x3+x+1，所以移位寄存器有三个。g(x)多项式中的系数是1还是0表示该移位寄存器的输入端反馈线的有无。图中x的一次项的系数为1，所以D1的输入端有反馈线及模2加法器。信息输入时，门打开，K1接通，信息送入除法器的同时，向外输出；信息位送完，门关闭，K2接通。除法电路中D2D1D0的内容，即所得余式，也就是校验位紧随信息位输出，完成一个码字的编码过程。这里设信息码元为1101，编码结果为1101001。2

工作过程输入m

移位寄存器
D0 D1 D2

输出

1

1 1 0

1

1

1 0 1

1

0

1 0 0

0

1

1 0 0

1

0

0 1 0

0

0

0 0 1

0

0

0 0 0

1

译码令S(x)是接收多项式R(x)=rn－1xn－1+…+r1x+r0的伴随式，利用生成多项式g(x)除xS(x)所得的余式S(1)(x)，就是R(x)循环移位一次R(1)(x)的伴随式。

因此，可用伴随式运算电路依次求出对应于各码位的伴随式。以g(x)=x3+x+1的(7,4)循环码为例，其伴随式运算电路由图2.19给出。

图5 伴随式运算电路

表6是错误图样和相应的伴随式。

表6 错误图样和伴随式

移存器状态
D0 D1 D2

错误图样
e0e1e2e3e4e5e6

伴随式
S0 S1 S2

1 0 0

1 0 0 0 0 0 0

1 0 0

0 1 0

0 1 0 0 0 0 0

0 1 0

0 0 1

0 0 1 0 0 0 0

0 0 1

1 1 0

0 0 0 1 0 0 0

1 1 0

0 1 1

0 0 0 0 1 0 0

0 1 1

1 1 1

0 0 0 0 0 1 0

1 1 1

1 0 1

0 0 0 0 0 0 1

1 0 1

可以看出如果我们在伴随式运算电路中赋予一个与e0出错项对应的伴随式S=001，随着伴随式电路的运算，移存器中的内容就会是依次是e1,e2,…,e6的伴随式。

定理表明如果e(x)的伴随式是S(x)，则xe(x)的伴随式t(x)=S（1）(x)。它相当于S(x)在伴随式运算电路里的循环移一位。当差错码元移到最高位时，就和最高位出错的伴随式相同，这就大大简化了译码器的结构。g(x)=x3+x+1的(7,4)循环码的译码电路由图7给出。

译码器缩短循环码

循环码的生成多项式g(x)应该是xn+1的一个(n－k) 次因子，但有时在给定码长n时，xn+1的因子不能满足设计者的需要，为了增加选择机会，往往采用缩短循环码。

在(n,k)循环码的2k个码字中选择前i位信息位为0的码字，共有2k－i个，组成一个新的码字集。这样就构成了一个(n－i,k－i)缩短循环码。

在缩短循环码中，校验码原位数不变，缩短的仅仅是信息位，因此(n－i,k－i)缩短循环码的纠检错的能力不低于(n,k)码的纠检错能力。但码字间已失去了循环特征。

在数据通信中广泛采用的循环冗余检验码(CRC，Cyclic Redundancy Checks)，是一种循环码，常利用缩短循环码，如CRC－12、CRC－16、CRC－CCITT码，表8给出了它们的生成多项式。

常用CRC码CRC码

生成多项式

CRC－12

x12+x11+x3+x2+x+1

CRC－16

x16+x15+x2+1

CRC－CCITT

x16+x12+x5+1

BCH码

BCH码是循环码的一个重要的子类，它是一种能纠正多个随机错误的应用最为广泛和有效的差错控制码。

定义：对于任意正整数m(m≥3)和t(t