信息论与编码：循环码

第八章循环码2内容提要循环码是线性分组码中一个重要的子类。本章将介绍循环码的基本概念以及循环码的多项式描述方法；循环码的基本定理及其矩阵描述

；简单的循环码的编译码方法及其实现电路。3§8.1循环码的概念一．定义

设一个（n，k）线性分组码C，如果它的任一码字的每一次循环移位都还是C的一个码字，则称C是循环码。由于循环码是线性分组码，所有这些具有循环关系的码字的全体构成了n维矢量空间中具有循环特性的k维子空间。4【例】（7，3）线性分组码由：得由两组码字循环构成的循环码。

5二．循环码的数学描述1．循环码的特点：（1）它是线性分组码，其数学模型应具有线性特性；（2）具有循环特性。

故循环码的数学模型必须能兼具线性和循环特性→多项式描述。2．线性分组码的多项式描述字：

字多项式

码字：

码字多项式

对于线性分组码C，可以表示成码字多项式构成的集合：

63．循环特性的表示以前面的（7，3）循环码为例：（任取一码字）移一位移两位移三位?此时：7>n-1=6，超出了n=7的矢量空间。

要求：

则：，即7下面用去除，得余对于上面第三次移位结果，可重新表示如下：

结论：如果将一个循环码的某一非零码字用码多项式表示出来，那么其他的非零码字多项式就可以用这个码字多项式（或码字多项式的和）乘上x的一个幂，再求（xn+1）的余得到。说明：一个码字的移位最多能得到n个码字，因此“循环码字的循环仍是码字”并不意味着循环码集可以从一个码字循环而得，还应包含码字的一些线性组合。8§8.2循环码的基本定理及其矩阵描述

一．循环码的生成多项式1．定义：若g(x)是一个(n-k)次多项式，且是(xn-1)的因式，则由g(x)可以生成一个（n，k）循环码，g(x)称为该循环码的生成多项式。两个结论：（1）GF(2)上的（n，k）循环码中，存在着一个次数为(n-k)的首一码多项式g(x)（首一：多项式最高幂次项系数

gn-k=1

）（gn-k=1）

使得所有码多项式都是g(x)的倍式，即：

且所有小于n次的g(x)的倍式都是码多项式。故循环码完全由它的生成多项式确定。9（2）（n，k）循环码的生成多项式g(x)一定是(xn+1)的因子，即

或写成相反，如果g(x)是xn-1的n-k次因子，则g(x)一定是（n，k）循环码的生成多项式。生成多项式不唯一。2．（n，k）循环码的构造（1）对(xn-1)做因式分解，找出(n–k)次因式；（2）以该(n–k)次因式为生成多项式g(x)与不高于k–1次信息多项式u(x)相乘，即得到对应消息序列的码多项式。10【例】一个长度n=7的循环码的构造方法。（1）对x7-1作因式分解

故x7-1有如下因式：

一次因式：

三次因式：

四次因式：

六次因式：

（一个）

（两个）

（一个）

（两个）

11n–k=1，k=6，生成一种（7，6）循环码；n–k=3，k=4，生成两种（7，4）循环码；n–k=4，k=3，生成两种（7，3）循环码；n–k=6，k=1，生成一种（7，1）循环码；例：要得到一（7，4）循环码，可选n–k=3次多项式1+x2+x3或1+x+x3

为生成多项式：

以g（x）=1+x2+x3为例，（信息位长度为4）

设信息多项式为：

则：循环码编码后的码多项式为：

（2）若以n-k次因式作为生成多项式，可供选择的有12例：

对于上述（7，4）循环码，有4个信息位，对应有16个信息序列，利用16个信息序列多项式与生成多项式的乘法运算，可得全部（7，4）循环码得16个码字，如表：信息位码字信息位码字信息位码字信息位码字00010010010010000111111010110001011001011001011001011000011000111000101000101001101101100111110010101101000111010111010111010011010011010011010011110011100000000000011011111111循环组1循环组2循环组3循环组4任何码字的循环移位仍是码字，并非由一个码字循环移位可以得到所有码字，上述（7，4）码的码集由4组码字循环构成。结论：当一个循环码给定其生成多项式g（x）后，根据生成多项式就可以进行编码（但编出的码不一定为系统码）13二．循环码的生成矩阵（n，k）循环码是n维线性空间一个具有循环特性的k维的子空间，故（n，k）循环码的生成矩阵可用码空间中任一组k个线性无关的码字构成，即k个线性无关的码字构成（n，k）循环码的基底，基底不唯一。如何得到k个线性无关的码字？

方法：当循环码的生成多项式g（x）给定后，可以取g（x）本身加上移位k–1次所得到的k–1码字作为k个基底，即：

→构成基底

若：

则：

14各多项式对应的矢量分别为：

这k个矢量是线性无关的，且由g（x）循环移位得到，故都是码字，由它们构成一个k×n的矩阵，它们就是循环码的生成矩阵。

15【例】（7，4）循环码：

当一个循环码的生成矩阵确定后，其编码规则为：

如：16（次数）

设：

则：三．循环码的系统码由上述方法作出的生成矩阵所编出的码不是系统形式，如何得到系统形式的循环码？1．系统循环码的编码：设

用xn–k

和u（x）相乘，再除以g(x)17a(x)g(x)是g(x)的一个倍式，则它是一个码多项式，对应的码矢量为：码矢量为系统形式的码字，信息位在尾部。※系统码的编码步骤：(1)将k个消息位按升幂排列的次序写成消息多项式u（x）

；

(2)用xn–k

乘以u（x）得到一个次数的多项式；

(3)用生成多项式g（x）除xn–k

u（x）得余b（x）（一致校验元）；

(4)联合b(x)和xn–k

u(x)得到系统码多项式v(x)=b(x)+xn–k

u(x)；

(5)将码多项式转换为码字。18【例】（7，4）循环码：

求

的系统码字。

，

【解】

，n＝7，k＝4

（1）

（2）（3）（4）192．系统码的生成矩阵（1）由生成矩阵做初等行变换，将其变为形式，即为系统形式的生成矩阵（单位阵在后，信息位在尾部）。

，求系统形式的生成矩阵。

【例】（7，4）循环码：

（2）分别求g（x）除的余式（记为），由余式对应的矢量作行矢量构成的k×n-k的分块矩阵P联合k×k的单位阵I就构成系统形式的生成矩阵：20，求系统形式的生成矩阵。

【例】（7，4）循环码：

21四．循环码的校验矩阵一般情况下，多项式xn-1可因式分解为xn-1=g(x)·h(x)

g(x)—（n，k）循环码的生成多项式，

h(x)—（n，k）循环码的一致校验多项式，在因式分解中，g(x)和h(x)处于同等地位，既可以用g(x)去生成一个循环码，也可以用h(x)去生成一个循环码。设由g(x)生成的码为C，在由h(x)生成的码就是C的对偶码C⊥。

循环码C的对偶码C⊥的基底由

构成。

22设

则：将上述矢量按逆序排列作为一个（n-k）×n矩阵的行矢量，则该矩阵就是码C的校验矩阵。23【例】（7，4）循环码：

则：C⊥的基底（n-k-1=2）

24※系统形式的校验矩阵

（1）对非系统形式的校验矩阵作初等行变换，变成[In-k，PT]的形式；（2）分别求h（x）除的余式（记为），由余式对应的逆矢量可得到系统形式的校验矩阵：（3）

25【例】（7，4）循环码：

（1）（2）k=4，n–k–1=2

（3）26§8.3循环码的编码

循环码是线性分组码的一个子类，因此循环码可以按一般线性分组码利用常用的组合逻辑电路来实现编码。但对于线性分组码，当其信息位分组长度较长，编码位数较多时，其编码电路非常复杂。由于循环码具有循环特性，其编码器通常用简单的具有反馈连接的移位寄存器就可以实现，大大简化了编码器的复杂度。利用具有反馈连接的移位寄存器实现的循环码编码电路，实际上是多项式运算电路。首先研究多项式运算电路。27一．G(F2)上的多项式除法电路

设（被除式）（除式）q(x)→商，r(x)→余除法电路：28（1）除法电路的结构由除式b（x）决定；（2）组成：由r个存储单元组成r级移位寄存器（D0～Dr-1）

bi：常乘器，（bi=1，输出＝输入；bi=0，输出＝0）当bi=1，对应支路连通（直通）；当bi=0，对应支路断开，对应的模2加法器可去掉。

故：电路有r个移位寄存器，最多r+1个常乘器，最多r个模2加法器。说明：29（3）工作原理简述：①电路清零，被除式系数按高次到低次依次进入电路（ak首先进入），r次移位后，移存器自右至左内容为：（a

k，a

k-1，...，ak-r+1）②第r+1次移位后，输出商的最高次位的系数（a

k

b

r

或ak

b

r-1），并反馈到前面作模2加运算后存入各级寄存器中，以后每次移位输出商的对应次位的系数并反馈回去。③依次类推，经过k+1次移位后，完成整个除法运算，最后输出商常数项系数，此时移存器中的内容就是余式r（x）各次项对应的系数（高位寄存器对应高次项系数）。30【例】工作过程:(r=3)节拍输入D0D1D2输出清零010000111000201100r次300110r＋1次411111（x）k＋1次5-0011（x0）31二．循环码编码器1．基于生成多项式g（x）的编码器（n－k级编码器）编码器电路的结构由生成多项式决定，生成多项式g（x）的最高次数为n-k，故编码器有n-k级移存器，故称n-k级编码器。对于循环码的系统编码，首先要得到u(x)xn-k除以g(x)的余式p(x)，再组合成系统码，即：对于除法电路：一方面我们可以得到商，还可以得到余式。对于系统码编码我们可以先输出信息位，再输出余式（校验位）就可以得到系统码，另外由于被除式为u(x)x

n-k，u(x)应从n-k级移存器的最前端输入。32编码过程：（1）门打开，k接“1”，消息数据uk-1,...

u0移入电路，并同时送入信道，一旦k个消息全部移入电路，移存器中的n-k个数据就构成了余式的系数；（2）门关，断开反馈连接，k接“2”；（3）移出移存器中的数据(校验元)，并送入信道，与k个信息位组成码字。33【例】（7，4）循环码，

若：34编码过程：（k＝4）节拍输入D0D1D2输出门开，k→1010001111012010113110004－1001门关，k→25－01006－00107－0001352．基于校验多项式h（x）的编码器（k级编码器）编码器电路的结构由校验多项式决定，生成多项式h(x)的最高次数为k，故编码器有k级移存器，故称

k级编码器。编码器电路编码过程（1）门1打开，门2关闭，k位消息数据u0，u1，...，uk-1移入电路，并同时送入信道；（2）k位消息全部移入，门1关，门2开；（3）以后的每次移位产生一个校验元并送入信道，直到n－k个校验元全部产生并送入信道为止。然后门2关，门1开，准备下一组消息编码；36【例】（7，4）循环码，

k＝4级编码器编码过程

输入节拍D0D1D2D3输出门1开，门2关100000111000102010001310101－411011门1关，门2开－501100－600110－700010373．两种编码器的比较（1）基于g（x）的编码器为n－k级编码器，需要n－k级移存器；基于h（x）的编码器为k级编码器，需要k级移存器。（2）当n－k<k时，采用n－k级编码器需要资源少；当n－k>k时，采用k级编码器需要资源少。

38§8.4循环码译码

一．译码步骤：和线性分组码一样，循环码译码步骤分三步：（1）计算接收多项式r(x)的伴随多项式s(x)；（2）根据s

(x)找出相应错误图样多项式e(x)；（3）将e

(x)和r(x)模2加，得到译码输出v

(x)

。二．伴随式计算及错误检测1．伴随式及计算设接收多项式为r(x)，码多项式为v(x)，错误图样多项式为e(x)，则用生成多项式g（x）除r（x），得

（求余运算）

39【定理】设g(x)是(n，k)系统循环码的生成多项式，接收字多项式为r(x)，对应错误图样为e(x),则

且它们的系数就是该接收字的伴随式。即

可见，循环码的伴随式计算电路就是一个接收多项式r(x)除以生成多项式g（x）的除法电路。电路初始状态为0，当r(x)全部移入后，移存器中的内容为伴随式多项式s(x)。

402．伴随式计算电路的性质由于码的循环结构，伴随式有个重要的性质，用定理描述。

【定理】设s(x)是r(x)的伴随式，则r(x)的循环移位x·r(x)的伴随式s(1)(x)是s(x)在伴随式计算电路中无输入时右移一位的结果，即：【推论】用生成多项式g(x)除x

is(x)所得余式s(i)(x)是r(x)经i次移位后r(i)(x)的伴随式。说明：把含有s(x)的伴随式移存器的输入门断开，移位一次就得到r(1)(x)的伴随式s(1)(x)

，移位i次，就得到r(i)(x)的伴随式s(i)(x)

。41【例】（7，4）循环码，计算对应的伴随式。伴随式计算电路计算过程：（开始时，移存器清零）节拍输入S0S1S2节拍输入S0S1S210000601112110070101s311108—100s(1)400119—010s(2)5101142由

计算电路性质的意义：对于在同一循环组中的接收字，只需计算一个接收字的伴随式，即可以通过移位来计算其他接收字的伴随式。43普通(n,k)线性分组码的译码电路框图44三．循环码一般译码器1．组成：（三部分）（梅吉特：Meggit通用译码器）（1）一个n位的缓冲寄存器（2）组合逻辑电路（3）一个r位的伴随式计算电路

2．错误纠正过程

（1）开始译码时，门开，移存器和伴随式计算电路清零，接收字r（x）一方面送入n级缓存，一方面送入伴随式计算电路，形成伴随式。当n位数据接收完后，门关，禁止输入。45（2）将伴随式输入错误图样检测电路，找出对应的错误图样。

方法：当且仅当缓存器中最高位出错时，组合逻辑电路输出才为“1”，即，若检测电路输出为“1”，说明缓存中最高位的数据是错误的，需要纠正。这时输出的“1”同时反馈到伴随式计算电路，对伴随式进行修正，消除该错误对伴随式的影响（修正后为高位无错对应的伴随式）。（3）如高位无错误，组合电路输出“0”，高位无需纠正，然后，伴随式计算电路和缓存各移位一次，这是高位输出。同时，接收字第二位移到缓存最高位，而伴随式计算电路得到此高位伴随式，用来检测接收字的次高位，即缓存最右一位是否有错。如有错，组合电路输出“1”与缓存输出相加，完成第二个码元的纠错，如无错，则重复上述过程，一直译完一个码字为止。46【例】（7，4）循环码，dmin(C)=3，可以纠正一个错误。

所有单重错误的错误图样：

错误图样伴随式对应H的列（0000001）e6(x)=x61+x21017（0000010）e5(x)=x51+x+x21116（0000100）e4(x)=x4x+x20115（0001000）e3(x)=x31+x1104（0010000）e2(x)=x2x20013（0100000）e1(x)=xx0102（1000000）e0(x)=11100147由上表可知：最高位x6出错的伴随式为1+x2，因此，识别最高位