第3章分组码现代编码技术曾凡鑫

第3章分组码3.1纠、检错编码的根本概念3.2线性分组码3.3循环码3.4BCH码习题 3.1纠、检错编码的根本概念

为了降低错误概率pe及使接收端具备检错、纠错能力，我们这样来对待传消息进行编码。选码C1={00000，11111}，作映射：

即消息中的每一符号比特按其重复的5比特码字来表示，并由发送端传送。接收端按选大原那么进行译码，在接收的5比特矢量中，哪个符号多就译为哪个。例如接收为10110，那么译为11111。消息的编码、译码关系见表3.1。表3.1消息的编码、译码关系定义 ，x=(x1，x2，…，xn)，y=(y1，y2，…，yn)，称

dist(x，y)=|{i|xi≠yi，i=1，2，…，n}|(3.1.1)

为码字x与y的汉明距离。

码字间的汉明距离满足以下三角不等式：

dist(x，y)≤dist(x，z)+dist(z，y)

(3.1.2)

在一个码中，任意两个不同码字间汉明距离的最小者称为这个码的最小汉明距离。

定义设有码C，称

(3.1.3)

为码C的最小汉明距离。

在一个码中，码字中非零码元的数目也是一个重要的参数，这个参数通常称为码字的汉明重量。

定义设有码C， ，称

wt(x)=|{i|xi≠0，i=1，2，…，n}| (3.1.4)

为码字x的汉明重量。

定义设有码C，0=(0，…，0)，称

wt(C)=min{wt(x)|x∈C，x≠0} (3.1.5)

为码C的最小汉明重量。

例设有码C2=(a1，a2，a3，a4，a5，a6，a7，a8)，式中

a1=(0000000)

a2=(0011101)

a3=(0100111)

a4=(0111010)

a5=(1001110)

a6=(1010011)

a7=(1101001)a8=(1110100)

求dist(a2，a4)，dist(a3，a7)，wt(a8)，dist(C2)，wt(C2)。

解dist(a2，a4)=4，dist(a3，a7)=4，wt(a8)=4，

dist(C2)=4，wt(C2)=4定义设有码C，如果 ，有x+y∈C，那么称码C是线性码。

所有的这样2k个码字构成的集合称为分组码。须注意一点，n－k个校验元可以放在码字中的任何位置，如果码字前k位固定为信息码，那么这种分组码称为系统分组码，如图3.1所示。图3.1系统(n，k)分组码码字结构定义将k位信息码通过一定的规那么添加n－k个校验元而形成长为n的码字，如果所有这样的码字组成一个线性码，那么称为(n，k)线性分组码。

定义称(n，k)线性分组码的 为码率。例构造奇偶校验码。对X={0，1}的k维扩展信源Xk添加一位校验位形成一个长为k+1的码字，即

且满足关系：

x1+x2+…+xk+xk+1=0(偶校验) (3.1.6)

即信息码(x1x2…xk)中如有偶数个1，那么xk+1=0，如有奇数个1，那么xk+1=1。

或

x1+x2+…+xk+xk+1=1(奇校验) (3.1.7)

即信息码(x1x2…xk)中如有偶数个1，那么xk+1=1，否那么xk+1=0。解仅讨论偶校验，所得结论适合于奇校验。设发送码字(x1x2…xkxk+1)，接收矢量为(y1y2…ykyk+1)，如果无错，那么接收矢量应满足式(3.1.6)；如果产生奇数个错误，那么y1+y2+…+yk+yk+1=1，因为一个码元x发生错误意味着这个码元变为x+1，为讨论方便，不防设y1，y2，…，y2r+1发生错误，于是

y1+y2+…+yk+yk+1=(1+x1)+(1+x2)+…+(1+x2r+1)+x2r+2+…+xk+xk+1

=(2r+1)+(x1+x2+…+xk+xk+1)

=2r+1=1(mod2)

说明不满足式(3.1.6)，从而发现错误，但无法判别哪些码元、多少码元出错，所以无纠错能力。如果是偶数个错误，那么有

y1+y2+…+yk+yk+1=2r+(x1+x2+…+xk+xk+1)=2r=0(mod2)

说明满足式(3.1.6)，因而无法检出错误。

综合起来，奇偶校验码能检奇数个错误，不能检偶数个错误，无纠错能力，码率为 。定理在一个线性分组码中，码的最小汉明距离等于码的最小汉明重量。

证明设C是线性分组码，那么0∈C，再设x∈C，满足wt(x)=wt(C)，即有

dist(C)≤dist(x，0)=wt(x)=wt(C)

另一方面，设x，y∈C且dist(x，y)=dist(C)，因为

，且wt(z)=dist(x，y)，所以

wt(C)≤wt(z)=dist(x，y)=dist(C)

故

dist(C)=wt(C)定理对一个二元(n，k)线性分组码C，有

(1)能纠正t个错误的充要条件是dist(C)=2t+1；

(2)能检测s个错误的充要条件是dist(C)=s+1；

(3)能纠正t个错误，并能发现s(s>t)个错误的充要条件是dist(C)=t+s+1。

证明只证结论(1)，其余省略。设发送码字为x，接收矢量为y，z是C中不等于x的任意码字。

①必要性。假设x传送后发生了r(≤t)个错误，那么有

dist(x，y)=r≤t

由汉明距离的三角不等式(3.1.2)，有

dist(z，y)≥dist(x，z)－dist(x，y)

≥dist(C)－dist(x，y)=2t+1－r≥t+1(3.1.8)式(3.1.8)说明接收矢量y最像码C中的x，按选大原那么，接收端能正确译出码x，即纠正了矢量y中的r个错误。

②充分性。使用反证法。假设dist(C)<2t+1，那么必定存在两个不同的码字x=(x1，x2，…，xn)和z=(z1，z2，…，zn)满足dist(x，z)<2t+1。由码字间距离的定义，x与z间至多有2t个码元对应不同，分两种情况来讨论。

情况1：设x与z间有2r′(<2t+1)个码元对应不同。不妨设 ，j=1，2，…，2r′。取矢量y=(y1，y2，…，yn)，式中：

于是，由r′≤t得到

dist(x，y)=r′≤t

且dist(z，y)=r′≤t(3.1.9)情况2：设x与z间有2r′+1(<2t+1)个码元对应不同。不妨设 ，j=1，2，…，2r′+1。取矢量y=(y1，y2，…，yn)，式中：

于是，由r′≤t－1得到

dist(x，y)=r′+1≤t

且dist(z，y)=r′≤t－1(3.1.10) 3.2线性分组码

线性分组码的编码方法

1.(n，k)线性分组码的校验矩阵H

构造线性分组码的关键在于校验元的选取规那么，虽然有相同的信息码和相同的校验元数目，但不同校验元的选取规那么所产生的线性分组码的纠、检错能力是不同的。为了说明问题，我们来考虑在信源X={0，1}的三维扩展信源X3上编一组(7，3)线性分组码，校验元按满足以下约束方程来选取，即

式中，(c6，c5，c4，c3，c2，c1，c0)为(7，3)线性分组码的任意一个码字，(c6，c5，c4)为信息码。(3.2.1)为了便于讨论，将式(3.2.1)写成矩阵形式：

简记为

HcT=0T (3.2.3)(3.2.2)式中：

c=(c6，c5，c4，c3，c2，c1，c0)

0=(0，0，0，0)

式(3.2.3)是重要的，一个长度为7的矢量是(7，3)线性分组码的码字的充要条件是满足式(3.2.3)。因此，式(3.2.3)和矩阵H是进行编码的关键。(3.2.4)一般地，(n，k)线性分组码是通过下面的方程来获得校验元的，即

将其写成矩阵形式，有

HcT=0T (3.2.6)(3.2.5)式中：(3.2.7)

定义称式(3.2.5)为校验方程，称矩阵H为校验矩阵。

由线性代数的知识我们知道，经过行初等变换校验矩阵H可以转化为如下形式：

式中，In－k是n－k阶单位矩阵。(3.2.8)

2.(n，k)线性分组码的生成矩阵G

从线性空间的角度来看，一个(n，k)线性分组码C是n维线性空间Vn的一个k维子空间。我们知道线性空间中每一个矢量都可以通过一组基来线性表示。设码C中的一组基为

a1=(g11，g12，…，g1n)

a2=(g21，g22，…，g2n)

…

ak=(gk1，gk2，…，gkn)

那么，码C中任意一个码字c可以表示为(3.2.9)

定义称矩阵

为(n，k)线性分组码的生成矩阵。

显然，G的秩为k。于是，任意(n，k)线性分组码C中码字可以简记为

c=mG (3.2.10)经过矩阵的行初等变换，生成矩阵G一定能等价于

即生成矩阵的分块矩阵为

G=［Ik，Q］ (3.2.12)(3.2.11)式中：Ik是k阶单位矩阵，

这样，(n，k)线性分组码C中的任意码字可以表示成

这样的(n，k)线性分组码C刚好是系统码。(3.2.13)读者不难验证，例的(7，3)线性分组码C2的生成矩阵G为

式中：(3.2.14)

3.生成矩阵G与校验矩阵H间的关系

同一个(n，k)线性分组码C既可以用校验矩阵来表示，又可以用生成矩阵来表示，这说明两者间一定存在某种关系。

1)HGT=0

将式(3.2.10)代入式(3.2.6)，有

HGTmT=0T (3.2.15)

式(3.2.15)对Xk中全部字符m都成立，所以一定有(3.2.16)简记式(3.2.16)中0(n－k)×k表示阶为(n－k)×k的零矩阵，为简便，在意义明确时略去下标。

以线性空间的观点，式(3.2.16)说明校验矩阵H的全部行向量与生成矩阵G的全部行向量是彼此正交的。

又因(n，k)线性分组码C是线性空间Vn的k维线性子空间，所以存在一个与C正交的线性子空间(记为C⊥)，使

(3.2.17)

式中，“〞表示直和。式(3.2.17)的图示说明见图3.2。

根据线性空间的维数公式，有

dim(C⊥)=dim(Vn)－dim(C)=n－k (3.2.18)图3.2n维线性空间的直和分解2)系统线性分组码的H和G

一般地，根据式(3.2.8)和式(3.2.12)，一个系统(n，k)线性分组码的校验矩阵和生成矩阵可以分别表示为

G=［Ik，Q］，H=［P，In－k］ (3.2.19)

将式(3.2.19)代入式(3.2.16)，得到

于是，得到

P=QT (3.2.20)4.系统(n，k)线性分组码的编码实现电路

例实现系统(7，3)线性分组码。

解根据式(3.2.14)，系统(7，3)线性分组码的码字有如下形式：校验元用信息码来表示，有

系统(7，3)线性分组码的编码实现电路如图3.3所示。(3.2.21)图3.3系统(7，3)线性分组码的编码电路5.(n，k)线性分组码的最小汉明距离

定理一个(n，k)线性分组码的最小汉明距离为d+1的充要条件是它的校验矩阵的任意d列线性无关，并存在d+1列线性相关。

例构造一个单纠错线性分组码。

解考虑n维线性空间：

一共有2n个不同矢量。因为a，b∈Vn，a与b是线性无关的，否那么a+b=0，所以a=b与Vn中任意两个矢量不相同矛盾。又因为Vn是线性空间，所以任意两个矢量之和仍是Vn中的矢量，即a，b∈Vn存在一个g∈Vn使g=a+b，说明Vn中任意三个矢量是线性相关的。因此，我们可以构造一个校验矩阵：

即H的列由Vn中全体不为零的矢量的转置构成。(3.2.22)线性分组码的译码方法

译码是编码的逆过程，通信系统通过译码来完成对信道上传送的码字检错和纠错。线性分组码的译码有伴随式译码和标准阵列译码两种根本译码方法。

1.伴随式译码

设发送码字c=(cn－1，cn－2，…，c1，c0)，接收矢量y=(rn－1，rn－2，…，r1，r0)，根据式(3.2.6)，如果HyT=0，那么接收矢量y是一个正确接收的码字；如果HyT≠0，那么接收矢量y产生了错误，需要进行纠错。因此，HyT的结果是译码的关键。(3.2.22)定义称S=yHT或者ST=HyT为接收矢量y的伴随式，亦称校验子。

对一个接收矢量y，与发送码字相比，要么出错，要么正确，因此，接收矢量y可以表示为

y=(cn－1+en－1，cn－2+en－2，…，c1+e1，c0+e0)

式中：如果y中ri无错，那么ei=0；如果ri有错，那么ei=1。

用矢量e=(en－1，en－2，…，e1，e0)表示接收矢量y的出错情况，称矢量e为错误图样。显然，如果e=0，那么接收矢量y是正确码字。

伴随式与错误图样存在关系：

ST=H(c+e)T=HcT+HeT=HeT (3.2.23)将校验矩阵H用列向量来表示，即H=［h1，h2，…，hn］，并代入式(3.2.23)，有

ST=en－1h1+en－2h2+…+e1hn－1+e0hn

(3.2.24)

如果产生t位错误，且在接收矢量的出错位为i1，i2，

…，it，那么错误图样

，式中， ，其余为0。式(3.2.24)可简化为

(3.2.25)总结上面的分析，我们得到如下结论：

(1)校验子由错误图样决定，与发送的码字无关。

(2)伴随式是否为零是判断接收矢量是否出错的标准。如伴随式S=0，那么无错；否那么，有错。

(3)错误图样不同，产生的伴随式也就不同，伴随式恰好就是与出错码元所对应的校验矩阵的列之和。

例考虑例中的(7，3)线性分组码C2，发送码字a5=(1001110)，分别就下述接收矢量进行译码。

(1)接收矢量y=(1011110)，即发生一个错误；

(2)接收矢量y=(1000100)，即发生两个错误；

(3)接收矢量y=(0101111)，即发生三个错误。

解(7，3)线性分组码C2的校验矩阵为式(3.2.4)。

(1)计算伴随式，得(2)计算校验子，得(3)计算校验子，得

2.标准阵列译码

伴随式译码对能纠正一个错误的(n，k)线性分组码是简单可行的，但随着码的纠错能力增强，确定错误图样的复杂度变得越来越高，必须寻找另一种译码方法来代替伴随式译码。这种译码方法就是标准阵列译码。那么，怎样来完成互不相交的2k个子集的分配呢？第一步，将(n，k)线性分组码

中的2k个码字排成2k列，将码字0放于第一列，形成第一行；第二步，在不包含有码字的具有2n－2k个矢量的集合Vn－C中挑选一个重量最轻的矢量v2，让v2与第一行中的每一个码字相加，并将结果放于对应码字的下面，形成第二行(见表3.2)，记第二行的全部矢量为B1；第三步，在2n－2k+1个矢量的集合Vn－C－B1中挑选一个重量最轻的矢量v3，让v3与第一行的码字相加，其结果放于对应码字下面，形成第三行，记第三行的全部矢量为B2；如此继续下去，直到用完Vn－C中的矢量。每一行都称为陪集，第一列称为陪集首。表3.2(n，k)线性分组码的标准阵列标准阵列的有效性可以通过下述定理来保证。

定理

n维线性空间Vn中任意一矢量必定出现于标准阵列中，并且仅出现一次，同一陪集中无相同的矢量。

例设(6，3)线性分组码的校验矩阵为

完成标准阵列。

解首先，求出(6，3)线性分组码的全部码字，生成矩阵为

(6，3)线性分组码的码字与信息码间的关系为

将［m2，m1，m0］取遍空间

{0，1}3={000，001，010，011，100，101，110，111}得到(6，3)线性分组码C的码字为

000000001110010101011011

100011101101110110111000

其次，构造标准阵。

V6－C中共有56个矢量，选最小重量矢量v2=(100000)，并与C中每一个码字相加，得到陪集B1。V6－C－B1共有48个矢量，选最小重量矢量v3=(010000)，得到陪集B2。如此继续下去，构成标准阵列，见表3.3。表3.3例的标准阵列根据表3.2，n维线性空间Vn中任意一矢量都可以表示为(n，k)线性分组码中的某个码字与一个陪集首之和。用数学语言表示，即 ，存在(n，k)线性分组码中的码字ci和陪集首vi满足：

y=ci+vi (3.2.26)

计算矢量y的伴随式，有

由式(3.2.27)，我们可得如下结论。(3.2.27)定理在标准阵列中，同一陪集的所有矢量的伴随式相同，不同陪集的伴随式不同，每一个伴随式取决于陪集首。

定理说明标准阵列中伴随式与陪集首间有一个一一对应的关系，因此，把存储标准阵列改为存储伴随式及对应的陪集首，存储量将大幅度降低。译码时，首先求接收矢量y的伴随式，并找到所对应的陪集首v，然后译码为y+v。这种译码方法与查找标准阵列表译码方法等价。例的(6，3)线性分组码及校验矩阵H同例，求(6，3)线性分组码的伴随式与陪集首的对应表，并译出接收矢量(100101)对应的码字。

解根据表3.3，全部陪集首实质上就是子集D1，陪集首(000000)的伴随式S1=(000)，陪集首(100000)的伴随式S2=(011)，…，见表3.4。表3.4例的伴随式与陪集首对应表当接收矢量为(100101)时，对应的伴随式为

查表3.4，对应的陪集首v=(001000)，故译出发送的码字为

(100101)＋(001000)＝(101101)读者不难发现，例的译码结果与直接查表3.3的结果是相同的，但存储量由表3.3的64个矢量下降为16个矢量。一般地，需要存储的陪集首为2n－k个n维矢量，需要存储的伴随式为2n－k个n－k维矢量。而标准阵列需要储存2n个n维矢量，节约的存储量是非常可观的。(n，k)线性分组码的译码过程如图3.4所示。图3.4译码过程 3.3循环码

循环码的编码方法

1.循环码的定义及多项式描述

在介绍循环码的定义之前，我们先来定义一个矢量变换算子，即左移循环算子。

定义设矢量c=(cn－1，cn－2，…，c1，c0)∈Vn，变换L将矢量c变为Vn中另一个矢量Lc，且满足关系：

Lc=(cn－2，cn－3，…，c1，c0，cn－1)(3.3.1)

那么，称变换L为左移循环算子。结合左移循环算子和例中的(7，3)线性分组码C2，读者不难发现，C2中的码字有下述特点：

一般地，Lic=L(L(…(L(c)…)))，L0c=c。例如，L2a4=L(L(a4))=L(a8)=a7。简单地说，C2中的码字在左移循环算子变换下仍是C2中的码字，本节要讨论的就是具有这种特性的线性分组码，称为循环码。定义一个线性分组码C，如果 ，有Lc∈C，那么称线性分组码C为循环码。

为了研究循环码的特性，我们引入称为码字多项式的多项式来描述一个码字，这个多项式与码字间建立了一一对应的关系，即

例求例中的(7，3)线性分组码C2的全部码字多项式。

解C2的全部码字多项式见表3.5。表3.5(7，3)线性分组码C2的全部码字多项式

2.循环码的生成多项式与生成矩阵

定义如果一个循环码的所有码字多项式都是一个次数最低的多项式g(x)的倍数，那么称g(x)为这个循环码的生成多项式。

定理每个(n，k)循环码中，生成多项式g(x)一定存在并且唯一，生成多项式g(x)的次数deg(g(x))=n－k并且具有以下形式：

g(x)=gn－kxn－k+gn－k－1xn－k－1+…+g1x+g0(3.3.2)

每个次数不超过n－1且是g(x)的倍数的多项式是这个循环码的码字多项式。

既然生成多项式存在，那么如何来寻找呢？定理每一个(n，k)循环码的生成多项式g(x)一定整除xn－1，即g(x)|xn－1。反过来，如果多项式g(x)次数deg(g(x))=n－k，并且g(x)|xn－1，那么多项式g(x)一定能生成一个(n，k)循环码。

有了生成多项式g(x)，每一个(n，k)循环码可以由生成多项式来简单表出，其全部码字多项式为

0，g(x)，xg(x)，x2g(x)，…，xn－2g(x)，xn－1g(x)

(3.3.3)

生成多项式用式(3.3.2)表示,因为g(x),xg(x),x2g(x),…，xk－2g(x)，xk－1g(x)为循环码的一组基，所以(n，k)循环码的生成矩阵可以表示为(3.3.4)

例求(7，3)循环码的生成多项式及生成矩阵。

解根据定理，首先将x7－1进行因式分解：

x7－1=(x+1)(x3+x2+1)(x3+x+1)

满足本例要求的答案有两个：

(1)生成多项式取

g1(x)=(x+1)(x3+x2+1)=x4+x2+x+1

生成矩阵为(2)生成多项式取

g2(x)=(x+1)(x3+x+1)=x4+x3+x2+1

生成矩阵为

3.循环码的校验多项式与校验矩阵

设g(x)是(n，k)循环码的生成多项式，由定理知，存在一个次数为k的多项式h(x)使

xn－1=h(x)g(x) (3.3.5)

定义称满足式(3.3.5)的k次多项式h(x)为(n，k)循环码的校验多项式。

设校验多项式为

h(x)=hkxk+hk－1xk－1+…+h1x+h0 (3.3.6)

将式(3.3.2)和式(3.3.6)代入式(3.3.5)，在模xn－1下，g(x)h(x)=0，从而得到方程组

式中，i=1，2，…，n－1。(3.3.7)将式(3.3.7)写成矩阵形式，有

GHT=0 (3.3.8)

称矩阵H为(n，k)循环码的校验矩阵。

式(3.3.8)中，(3.3.9)

例求例中生成矩阵g2(x)对应的校验多项式及校验矩阵。

解校验多项式为

校验矩阵为

4.系统循环码的编码实现

1)信息元多项式与校验元多项式的关系

由信息码构成的多项式称为信息元多项式，由校验元构成的多项式称为校验元多项式。设一个(n，k)循环码的生成多项式为g(x)，信息码(mk－1，mk－2，…，m1，m0)，我们来确定循环码的码字校验元。因为考虑系统循环码，所以码字结构为

c=(mk－1，mk－2，…，m1，m0，cn－k－1，cn－k－2，…，c1，c0)信息元多项式和校验元多项式分别为

m(x)=mk－1xk－1+mk－2xk－2+…+m1x+m0

r(x)=cn－k－1xn－k－1+cn－k－2xn－k－2+…+c1x+c0

于是，码字c的码字多项式为

c(x)=mk－1xn－1+mk－2xn－2+…+m1xn－k－1+m0xn－k

+cn－k－1xn－k－1+…+c1x+c0=xn－km(x)+r(x)

(3.3.10)

根据生成多项式的定义，c(x)是生成多项式g(x)的倍数，即存在一个多项式q(x)满足：

xn－km(x)+r(x)=q(x)g(x) (3.3.11)2)基于生成多项式的循环码的编码实现

除法电路由移位存放器、模2加法器和逻辑门组成，除法电路结构取决于生成多项式g(x)，一般结构如图3.5所示。其中，当gi=1时，门gi合上，否那么断开。图3.5根据生成多项式g(x)构成的循环码的编码电路

例用除法电路实现系统(7，4)循环码的码字(1010001)编码，生成多项式g(x)=x3+x2+1。

解(1)本例生成多项式g(x)产生的除法电路如图3.6所示。图3.6基于生成多项式的(7，4)循环码的编码电路(2)工作原理如下：

①输入m′=(1010000)。本例中信息码为(1010)，在其后添加了7－4=3个0形成长度为7的输入矢量。添加0的作用相当于m(x)乘以xn－k，即产生xn－km(x)。

②门1和门2开，门3接于A，移位存放器清零。

③门1和门2合上，门3接于B，输入信息码(1010)，同时信息码由门3输出，形成码字的前4位码元。各移位存放器的内容变化见表3.6。

④信息码输入完毕后，门3接于C，输出校验元，各移位存放器的内容变化见表3.6。

⑤当输入m′全部输完时，门1和门2开，门3接于A，移位存放器清零，准备下一组码字的编码。表3.6图3.6编码电路编码过程3)基于校验多项式的循环码编码电路

由图3.5知，生成多项式g(x)构成的除法电路的移位存放器的数量取决于g(x)的次数，次数越大，用的移位存放器数目越多，电路越复杂。由式(3.3.5)知，deg(h(x))+deg(g(x))=n。如果deg(g(x))>deg(h(x))，那么用校验多项式来进行编码的电路会简单一些。根据式(3.3.9)和式(3.2.6)，有

式中，(cn－1，cn－2，…，cn－k)=(mk－1，mk－2，…，m0)。(3.3.12)简化后得到(3.3.13)式(3.3.13)写成方程组形式，校验元与信息元的关系为(3.3.14)从式(3.3.14)看出，校验元cn－k－1取决于信息码(mk－1，mk－2，…，m1，m0)与校验多项式的系数(h0，h1，…，hk－1)的内积，cn－k－2取决于(mk－2，mk－3，…，m1，m0，cn－k－1)与(h0，h1，…，hk－1)的内积，以此类推，c0取决于(ck，ck－1，…，c1)与(h0，h1，…，hk－1)的内积，这说明可以从校验元cn－k－1开始，以cn－k－1，cn－k－2，…，c1，c0的顺序来递推校验元。完成这一递推过程的一般电路见图3.7。图3.7根据校验多项式h(x)构成的循环码编码电路

例用校验多项式h(x)=x4+x3+x2+1来产生系统(7，4)循环码的码字(1001011)。

解(1)本例产生码字的电路如图3.8所示。图3.8基于校验多项式的(7，4)循环码编码电路(2)工作原理如下：

①门1和门2开，移位存放器清零。

②门1关，门2开，输入信息码(1001)，输出端获得码字前4位码元(m3m2m1m0)。各移位存放器内容见表3.7。表3.7图3.8编码电路的编码过程③信息码输入完毕后，门1开，门2关，在时钟脉冲未到来前，移位存放器D和D4的输入端信号为

h0m3+h1m2+h2m1+h3m0=1×1+0×0+1×0+1×1=0

即校验元c2=0，当时钟脉冲到来时，c2进入D4和D，同时输出校验元c2=0；在时钟脉冲未到来前，移位存放器D和D4的输入端信号为

h0m2+h1m1+h2m0+h3c2=1×0+0×0+1×1+1×0=1

即c1=1，当时钟脉冲到来时，输出c1=1，并且进入D4。类推可得c0=1。

④门1和门2开，移位存放器清零，准备下一组码字的编码。循环码的译码方法

设(n，k)循环码发送的码字、接收矢量和错误图样及所对应的码字多项式、接收矢量多项式和错误图样多项式如下：

设y(x)除以g(x)的余式为s(x)，即存在一个q1(x)使

y(x)=q1(x)g(x)+s(x)

(3.3.15)由定理知，如s(x)=0，那么y(x)为正确码字；如s(x)≠0，那么y(x)产生了错误。因此，s(x)是否为零是判断接收矢量y(x)是否有错的关键，称s(x)为伴随式多项式。

又因为

y(x)=c(x)+e(x)，c(x)=q2(x)g(x)

所以有

s(x)=e(x)(modg(x)) (3.3.16)

式(3.3.16)表示伴随式多项式在模g(x)下与错误图样多项式相同，并且可以由一个除法电路来计算。

定理

s(x)是接收矢量y的多项式y(x)的伴随式，s(1)(x)是Ly的多项式Ly(x)的伴随式，那么

s(1)(x)=xs(x)

(modg(x)) (3.3.17)

证明由式(3.3.15)，有

s(x)=y(x)

(modg(x)) 于是可得

xs(x)=xy(x)

(modg(x)) (3.3.19)又因为

Ly(x)=xy(x)(mod(xn－1)) (3.3.20)

联合式(3.3.19)和式(3.3.20)，在模g(x)下Ly(x)的伴随式为

s(1)(x)=xs(x)(modg(x))

一般地，多项式循环移位后存在关系：

s(i)(x)=xis(x)(modg(x))(i=1，2，…，n－1)

(3.3.21)

定理说明接收矢量多项式在模xn－1下的循环移位与伴随式在模g(x)下的循环移位是一一对应的。有了以上的准备，现在可以讨论循环码的译码电路了。循环码的译码电路主要由三局部组成(见图3.9)：伴随式计算电路、错误图样计算电路以及接收矢量移位存放器和纠错电路。为便于理解，以纠正一个错误的循环码为例来说明。当且仅当错误是可纠正，并且出错位恰好位于错误图样的最高位时，错误图样计算电路输出信号“1〞，并由纠错电路纠错；相反，如果输出的信号是“0〞，那么认为最高位是正确的。对于错误不在最高位的情况，通过码组和伴随式同时循环移位，使错误移至最高位来纠错。图3.9循环码的译码电路例由生成多项式g(x)=x4+x3+x2+1产生(7，3)循环码发送码字c=(0111010)，接收矢量为y=(0110010)，完成译码。

解(1)译码电路见图3.10。移位存放器D6~D0储存接收矢量y；移位存放器T3~T0计算伴随式；非门和与门检测错误图样。当T3~T0输出(1110)时，与门输出“1〞，因为接收矢量y的多项式y(x)=x5+x4+x，所以接收矢量y对应的伴随式多项式s(x)=y(x)(modg(x))=x3，其中伴随式是(1000)，只有当接收矢量为(1111010)时，即错误图样为(1000000)，对应的伴随式

多项式为x3+x2+x，其伴随式才是(1110)。既然图3.9中伴随式检测电路不是针对接收矢量y=(0110010)而设计的，为什么本电路仍然能完成纠错呢？其原因在于(7，3)循环码的全部错误图样与伴随式有一一对应的循环移位，即使以(1110)来设计伴随式检测电路，经过4次循环移位也能找到伴随式(1000)，见表3.8。表3.8告诉我们，以任意伴随式设计伴随式检测电路，经过循环后伴随式计算电路一定能找到所对应的伴随式，并由伴随式检测电路输出纠错信号，纠正错误。图3.10例的译码电路表3.8例的全部错误图样与伴随式的循环移位(2)电路工作原理如下：

①门1和门2开，各移位存放器清零。

②门1关，门2开。接收矢量y=(0110010)送入移位存放器D6~D0和T3~T0，每送一个码元，伴随式计算电路计算一次伴随式，各移位存放器的状态见表3.9。当接收矢量全部输入后，由于伴随式非(0000)，故认为有错，但伴随式也不为(1110)，故需要继续查错。③门1开，门2关。一方面移位存放器D6~D0的内容移入输出端，另一方面伴随式计算电路在无输入自循环。由表3.9可以看出，当第10个时钟结束后，伴随式输出为(1110)，第11个脉冲到来时，与门输出“1〞，D6输出“0〞，输出端被输入“1+0=1〞，刚好纠正接收矢量产生的错误，同时，伴随式存放器被全部清零。D6~D0的内容继续移入输入端，到全部矢量移完为止。

④门1和门2开，各移位存放器清零，准备译出下一接收矢量。表3.9图3.10译码电路的工作过程 3.4BCH码

BCH码的定义及最小汉明距离

定义设m是一正整数，m0是任意整数，GF(q)表示有q个元素的有限域，其中q是一个素数或素数的幂，GF(qm)是GF(q)的扩域，a∈GF(qm)，如果一个循环码由GF(q)上的多项式g(x)生成，并且g(x)的根包含下面d-1个根：

a，a

2，a

3，…，a

d－1 (3.4.1)

那么，称这个由g(x)生成的循环码为设计距离为d的q元BCH码。如果定义中g(x)有一个根是GF(qm)中的本原元，那么g(x)生成的BCH码码长必定为n=qm－1，称这种BCH码为本原BCH码，否那么称为非本原BCH码。非本原BCH码是存在的，其码长是qm－1的因子，本书不讨论这种情况。

BCH码的优势之一在于，如果确定了BCH码的生成多项式g(x)的连续根，那么由g(x)生成的BCH码的实际最小汉明距离不小于设计距离。

定理BCH码的最小汉明距离至少为d。

证明因为BCH码为一循环码，所以任意码字多项式c(x)必定是生成多项式g(x)的倍数，即存在多项式q(x)满足c(x)=q(x)g(x)。设码字多项式c(x)为

c(x)=cn－1xn－1+cn－2xn－2+…+c1x+c0 (3.4.2)

将生成多项式g(x)的连续d－1个根式(3.4.1)代入式(3.4.2)，得到方程组(3.4.3)写成矩阵形式，有

HcT=0T (3.4.4)

式中： c=(cn－1，cn－2，…，c1，c0)(3.4.5)由式(3.4.4)知，式(3.4.5)的矩阵H是g(x)生成的BCH码的校验矩阵。根据定理，只需证明H中任意d－1列线性无关，那么这个BCH码的最小距离至少为d。

用反证法。假设H中i1，i2，…，id－1列线性相关，即存在不全为零的l1，l2，…，ld－1使(3.4.6)设BCH码的生成多项式g(x)为

g(x)=gn－kxn－k+gn－k－1xn－k－1+…+g1x+g0

同样，由于g(x)，xg(x)，x2g(x)，…，xk－1g(x)为BCH码的一组基，因此BCH码的生成矩阵为(3.4.7)BCH码的编码方法

1.二元BCH码

二元信号在工程上最容易实现，因而二元BCH码在工程上应用最广泛。对给定的正整数m和d(d=2t+1，t<2m－1)，二元BCH码的码长、校验位数和最小汉明距离是什么呢？

定理给定正整数m和t，存在一个(n，k)二元BCH码，其生成多项式以a，a

3，a

5，…，a

2t－1为根，其码长n=2m－1或n|2m－1，能纠正t个错误，并且n－k≤mt。

在GF(2m)中，a

i与a

2i有相同的最小多项式，因此，定理中生成多项式g(x)的根去掉了a的偶次幂。

例分别找出能纠正1、2、3和4个错误的长度n=15的二元本原BCH码的生成多项式。

解由有限域知识，GF(2)的多项式x15+1可以分解为

式中：其根为a3，a6，a9，a12；其根为a，a2，a4，a8；其根为a0；其根为a5，a10；其根为a7，a14，a15，a11。(1)纠正1个错误的BCH码生成多项式：

t=1，应选d－1=2个连续根，取a，a

2。又因为ma(x)=ma2(x)，所以生成多项式为

g(x)=ma(x)=x4+x+1

(2)纠正2个错误的BCH码生成多项式：

t=2，应选d－1=4个连续根，取a，a2，a

3，a

4，去掉a的偶次幂，所以生成多项式为

(3)纠正3个错误的BCH码生成多项式：

t=3，应选d－1=6个连续根，取a，a

2，a

3，a4，a5，a

6，去掉a的偶次幂，所以生成多项式为(4)纠正4个错误的BCH码生成多项式：

t=4，应选d－1=8个连续根，取a，a

2，a

3，a

4，a

5，a

6，a

7，a

8，去掉a的偶次幂，所以生成多项式为寻找BCH码的生成多项式是一件非常繁琐的工作，前人已将许多二元本原BCH码的生成多项式制成了表格，需要时直接查表就可以获得。码长n≤127的二元本原BCH码的生成多项式见表3.10，表中最小距离为实际距离。为节省篇幅，表3.10中的生成多项式采用八进制简记的方法表示，其与二进制的对应关系见表3.11。表3.10码长n≤127的二元本原BCH码的生成多项式表3.11八进制与二进制的对应关系

2.RS码

定义设q>2，称GF(q)上码长n=q－1的本原BCH码为RS码。

最小汉明距离至少为d的RS码的生成多项式为

g(x)=(x－a)(x－a

2)…(x－a

d－1)

例设q=23，a∈GF(q)且是一本原元，a是多项式x3+x+1的根，求最小汉明距离至少为5的RS码的生成矩阵和校验矩阵。

解因为要求RS码的最小汉明距离至少为5，所以应选a，a

2，a3，a4为生成多项式的根，即

g(x)=(x－a)(x－a2)(x－a3)(x－a4)

=x4+a3x3+x2+ax+a3

根据式(3.4.7)，RS码的校验矩阵为根据式(3.4.5)，RS码的校验矩阵为BCH码的译码方法

1.一般译码方法

设发送端发送码字多项式为

c(x)=cn－1xn－1+cn－2xn－2+…+c1x+c0

接收端接收的矢量多项式为

y(x)=rn－1xn－1+rn－2xn－2+…+r1x+r0

产生的错误图样多项式为

e(x)=en－1xn－1+en－2xn－2+…+e1x+e0假定共产生了v个错误，即错误的图样在x的l1,l2，…，lv次幂处不为零。

式(3.4.8)说明接收矢量y的 出错，如果接收端能确定出错位置及错误值，用y(x)－e(x)不难将错误纠正。为方便，常称 为错误位置。为了确定错误位置及错误值，需要计算伴随式和错位多项式。(3.4.8)1)BCH码的伴随式

BCH码的伴随式仍然是校验矩阵与接收矢量的乘积，设d=2t+1，由式(3.2.23)有

令 ，那么式(3.4.9)可简化为(3.4.9)(3.4.10)将式(3.4.10)写成方程组形式，有(3.4.11)2)BCH码的错误位置多项式

定义设BCH码可以纠正t个错误，称多项式

为错误位置多项式。式中，Xi与σi(i=1，2，…，t)间满足：(3.4.12)(3.4.13)很明显，错误位置多项式的根刚好是错误位置数Xi(i=1，2，…，t)的倒数，即 ，更清楚地，有

将式(3.4.14)两边同时乘以 ，得(3.4.15)(3.4.14)将式(3.4.15)两边再同时乘以 (i=1，2，…，t)，得

当i取遍1，2，…，t时，式(3.4.16)有t个方程，将这t个方程加在一起，得到(3.4.17)(3.4.16)将式(3.4.10)代入式(3.4.17)，有

将式(3.4.18)写成方程组形式，即(3.4.18)(3.4.19)将伴随式Si(i=1，2，…，2t)视为数，σi(i=1，2，…，2t)视为未知数，式(3.4.19)是含有t个未知数t个方程的线性方程组，这个方程组有唯一一组解的充要条件是系数矩阵应当是满秩的。为方便，将式(3.4.19)写成矩阵形式，即(3.4.20)下述定理保证方程组(3.4.20)有唯一一组解。

定理如果Sj(j=1，2，…，t)是由t个不同的非零数对(Yi，Xi)组成的，那么矩阵

是满秩矩阵，否那么为非满秩矩阵。(3.4.21)根据求解线性方程组的克莱姆法那么，下面三种简单情况能直接求出方程组的解。

第一种情况：产生1个错误。

由式(3.4.20)，得

S1σ1=－S2

所以，错误位置多项式为

σ(x)=1－(S2/S1)x

第二种情况：产生2个错误。

由式(3.4.20)，得到线性方程为于是，有解

所以，错误位置多项式为

σ(x)=1+σ1x+σ2x2(3.4.22)第三种情况：产生3个错误。

根据式(3.4.20)，得到线性方程为

于是，有解，，

所以，错误位置多项式为

σ(x)=1+σ1x+σ2x2+σ3x3

获得错误位置多项式后可以用试探法寻找错误位置多项式的根。遗憾的是，随着错误数的增加，直接求解线性方程组(3.4.20)变得越来越困难。例设a是不可约多项式x4+x+1的根，GF(24)由多项式x4+x+1生成，查表3.10得以a，a3，a5为根生成能纠正3个错误长度为n=15的(15，5)二元BCH码的生成多项式g(x)=2467，即g(x)=x10+x8+x5+x4+x2+x+1。假设接收矢量多项式为y(x)=x14+x8，那么接收的矢量正确吗？如有错，请纠正。

解(1)求解本例需要用x4+x+1所产生的有限域的元素，为方便，将有限域的元素表列于表3.12。表3.12由x4+x+1产生的有限域GF(24)(2)计算接收矢量的伴随式。由表3.12，得(3)找满秩矩阵。因为

所以(4)找错误位置多项式。根据式(3.4.22)，有

所以，错误位置多项式为

σ(x)=1+α6x+α7x2(5)找错误位置。因为

σ(α)=1+α6α+α7α2=1+α7+α9=0

σ(α7)=1+α6α7+α7α14=1+α13+α6=0

所以，错误位置多项式有根

于是，找到错误位置，即由式(3.4.8)，得错误图样多项式为

e(x)=x14+x8

(6)纠正错误：发送的码字为

c(x)=y(x)－e(x)=0

即发送的码字是c=(0，0，…，0)(15个0)。2.二元BCH码的译码方法

二元BCH码的错误位置多项式的迭代算法如下。

假设已经迭代出第n步的错误位置多项式：

第n+1步迭代如下：

(1)如果dn=0，那么σ(n+1)(x)=σ(n)(x)，ln+1=ln。

(2)如果dn≠0，那么在第－1/2，0，1，…，n－1次迭代中找出一次迭代m，满足2m－lm最大且dm≠0，然后更新以下公式：

继续迭代n+2步，直到迭代出σ(t)(x)为止。σ(t)(x)就是所求的错误位置多项式σ(x)。如果deg(σ(x))>t，那么表示发生了t个以上的错误，无法纠正；否那么，纠正错误。

迭代算法初始值。

每次迭代需要前两步迭代后的结果，为方便，选迭代次数以－1/2开始，即

n=－1/2，σ－1/2(x)=1，d－1/2=1，l－1/2=0，2n－l－1/2=－1

n=0，σ0(x)=1