

循环码



循环码

目录导航

定义

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

一个( , )线性分组码，若它的任一码字的每一循环移位寄存器都是的一个码字，则称是一个循环码，如表1所示。

表1(7,4)循环码

信息组

码字　　

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

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

编码种类

十六进制数

自然二进制码

循环二进制码

十六进制数

自然二进制码

循环二进制码

0000

1000

1100

0001

1001

1101

0010

0011

1010

1111

0011

0010

1011

1110

0100

0110

1100

1010

0101

0111

1101

1011

0110

0101

1110

1001

0111

0100

1111

1000

循环码的基本特征

为了探讨循环码的特征，把码字 =( … )用如下的码多项式 ( )来表示。

（1）特性一

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

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

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

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

（2）特性二

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

+1= ( ) ( )

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

（3）特性三

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

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

循环码的编码

（1）编码方法

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

表2 +1中的部分 ( )

循环码

码距

生成多项式 ( )

校验多项式 ( )

(7,6)

( + +1)( + +1)

(7,4)

+ +1

( + +1)( +1)

(7,3)

( +1)( + +1)

+ +1

(7,1)

( + +1)( + +1)

① 用生成多项式编码

a．选择一个能除尽 +1的－ = 次生成多项式 ( )。

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

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

② 用生成矩阵编码

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

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

b．用 ( )除 ( =0，1，…，－1)，得：

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

③ 用余式确定校验位

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

b.用 ( )除 ( )得到余式 ( )。

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

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

（2）除法电路编码器

以 ( )= + +1生成(7,4)循环码的编码器为例，如图3所示。

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

图3 (7,4)循环码编码器

表4 (7,4)编码器工作过程

输入

移位寄存器　　D D D

输出

1 1 0

1 0 1

1 0 0

0 1 0

0 0 1

0 0 0

循环码的译码

令 ( )是接收多项式 ( )= +…+ + 的伴随式，利用生成多项式 ( )除 ( )所得的余式 ( )，就是 ( )循环移位一次 ( )的伴随式。

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

图5 伴随式运算电路

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

表6 错误图样和伴随式

移存器状态　　D D D

错误图样　　

伴随式　　

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

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

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

图7 (7,4)循环码译码器

缩短循环码

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

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

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

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

表8 常用CRC码

CRC码

生成多项式

CRC－12

+ + + + +1

CRC－16

+ + +1

CRC－CCITT

+ + +1

BCH码

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

定义：对于任意正整数 ( ≥3)和 ( <2 =一定存在一个具有下列参数的二进制BCH码：

码长 =2 －1

校验位数目－

最小距离 ≥2 +1

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

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

表9 本原BCH码生成多项式

( )

7 4 1

( )=13

1 3

( )(15)=177

15 11 1

( )=23

7 2

( )(37)=721

5 3