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)循环码的一个码字。但某一码字的循环移位，并不能生成所有的码字。对于一个循环码来说，可以同时存在多个循环圈。

十六进制数

自然二进制码

循环二进制码

十六进制数

自然二进制码

循环二进制码

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。

输入m

移位寄存器

D0 D1 D2

输出

1

1 1 0

1

1

1 0 1

1

1 0 0

1

1 0 0

1

0 1 0

0 0 1

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)循环码为例.

表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－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<2m－1=一定存在一个具有下列参数的二进制BCH码：

码长n=2m－1

校验位数目n－k≤mt

最小距离dmin≥2t+1

BCH码可以分为两类，即本原BCH码和非本原BCH码。本原BCH码码长n=2m－1，它的生成多项式g(x)中含有最高次数为m的本原多项式，本原多项式是一个既约多项式，它能除尽xn+1的最小正整数n，满足n=2m－1。具有循环码特性，纠单个随机错误的汉明码，是可纠单个随机错误的本原BCH码。而非本原BCH码中的生成多项式g(x)中不含本原多项式，且码长n是2m－1的一个因子，著名的戈雷(Golay)码，就属于非本原BCH码。

给出了n≤31的本原BCH码的参数和生成多项式。

本原BCH码生成多项式

n k t

gt(x)

7 4 1

g1(x)=13

1 3

g1(x)(15)=177

15 11 1

g1(x)=23

7 2

g1(x)(37)=721

5 3

g2(x)(7)=2467

1 7

g3(x)(31)=77777

31 26 1

g1(x)=45

21 2

g1(x)(75)=3551

16 3

g2(x)(67)=10765 7

11 5

g3(x)(57)=54233 25

n k t

gt(x)

6 7

g5(x)(73)=31336 5047

1 15

g7(x)(51)=17777 77777 7

表中的每一位数字为八进制数，代表g(x)多项式中3个二进制系数。如n=31，k=26,t=1的BCH码的生成多项式g1(x)=45。45表示100101，所以，该BCH码的g(x)=x5+x2+1。有了生成多项式表就可很方便地构造所需的BCH码。

里德—所罗门(Read-Solomon)码

除了二进制码之外，还有非二进制码。如果P是一素数，q是p的任意次幂，存在着由伽罗华域GF(q)产生的码。这些码称为q进制码。q进制码的编码和译码都与二进制码相似。

对任意选择的正整数s和t，存在长度为n=qs－1的q进制BCH码。它能纠正t个错误，而只用2St个校验位。S=1时的q进制BCH码是q进制BCH码中的一类最重要的子码。这类子码称为里德——所罗门(Read-Solomon)码，简称R-S码。纠t位错误，系数为GF(q)中元素的R-S码具有下列参数：

码长：n=q－1

校验位数目：n－k=2t

最小距离：dmin=2t+1

R-S码对纠多重突发差错非常有效。

R-S码把L位(例如8位)的一个字节，作为一个编码符号。如果我们要设计一个纠t=5位错误的，由8位字节组成的R-S码，码长为q－1=255字节(这里，p=2,q=28)。那么根据R-S码的参数，校验位的数目为r=n－k=2t=10字节(80位)，其余k=n－r=245字节(1960位)是信息位。