第五章循环码

第5章循环码5.1循环码与理想5.2由生成多项式的根定义循环码5.3幂等多项式和最小循环码

5.4缩短循环码与准循环码

5.5平方剩余码5.6多项式及域元素运算电路5.7循环码的编码电路习题5.1循环码与理想

一、基本概念［7，4］汉明码CH的H矩阵为

由第二章可知，交换H矩阵各列，并不会影响码的纠错能力。把上述H矩阵的列进行交换后变为

由此矩阵可明显看出，第二行是第一行循环右移一位得到，第三行是第二行循环右移一位。由此矩阵编出的16个码字为：1000110，0100011，1010001，1101000，0110100，0011010，0001101；1001011，1100101，1110010，0111001，1011100，0101110，0010111；1111111；0000000。

由这些码字看出，若C1∈CH，则它的右(左)移循环移位所得到的n重也是一个码字，具有这种特性的［n，k］分组码称为循环码。由于［n，k］线性分组码是n维线性空间Vn中的一个k维子空间，因此［n，k］循环码是n维线性空间中的一个k维循环子空间。

定义5.1.1

一个n重子空间Vn，k∈Vn，若对任何一个V=(a

n-1，a

n-2，…，a0)∈Vn，k，恒有v1=(a

n-2，a

n-3，…，a0，a

n-1)∈Vn，k，则称Vn，k为循环子空间或循环码。

二、码的多项式描述从第二章可知，GF(p)上的所有n重构成一个线性空间Vn，其中每个矢量是分量取自GF(p)上n重，若将每个n重和系数取自GF(p)上的多项式相对应：n

重：

(a

n-1，a

n-2，…，a1，a0)ai∈GF(p)多项式：(a

n-1

x

n-1+a

n-2

x

n-2+…+a1x+a0)=f(x)

则它们之间建立了一一对应关系。在第四章中已指出，所有次数小于n次的多项式一定在模n次多项式F(x)∈Fp［x］的不同剩余类中，即f(x)∈{a

n-1

x

n-1+a

n-2

x

n-2+…+a1x+a0}(modF(x))

因此，Vn中每一个n重都与GF(p)上的次数低于n次的一个多项式相对应，并必在模F(x)的某一剩余类中。第四章中（p107）已证明，在模F(x)运算下，模F(x)的剩余类构成一多项式剩余类环Fp［x］／F(x)，若在该环中再定义一个数乘，即

ca(x)={ca

n-1

x

n-1+ca

n-2

x

n-2+…+ca0}c∈GF(p)

则可以证明模F(x)的剩余类构成一个n维线性空间，称为剩余类线性结合代数。(线形空间有数乘的要求)

定理5.1.1以多项式xn-1为模的剩余类线性结合代数中，其一个子空间Vn，k是一个循环子空间(循环码)的充要条件是：Vn，k是一个理想。

定义5.1.2

生成多项式g(x)是模xn-1剩余类代数中，一个理想的次数最低的非零首一多项式，它是理想或循环码的生成元。定理5.1.2GF(q)(q为素数或素数的幂)上的［n，k］循环码中，存在有唯一的n-k次首一多项式

g(x)=x

n-k+g

n-k-1x

n-k-1+…+g1x+g0，每一码多项式C(x)都是g(x)的倍式，且每一个≤(n-1)次的g(x)倍式一定是码多项式。

定理5.1.3

GF(q)上［n，k］循环码的生成多项式g(x)一定是xn-1的因式：xn-1=g(x)h(x)。反之，若g(x)为n-k次，且g(x)｜(xn-1)，则该g(x)一定生成一个［n，k］循环码。

例5.1在GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1)，求［7，4］循环码。找一个能除尽x7-1的n-k=3次首一多项式g(x)，可在x3+x+1与x3+x2+1中任选一个，现在选g(x)=x3+x2+1，则{xg(x)}：xg(x)=x4+x3+x{x2g(x)}：x2g(x)=x5+x4+x2{x3g(x)}：x3g(x)=x6+x5+x3

它们相应的n重为：(0001101)，(0011010)，(0110100)，(1101000)，把它们作为生成矩阵的行，就得到了［７，4］码的生成矩阵。

三、循环码的生成矩阵、校验矩阵由前知，xn-1=g(x)h(x)。若g(x)为n-k次，则h(x)为k次多项式。以g(x)作为生成多项式所组成的［n，k］循环码中g(x)，xg(x)，…，xk-1

g(x)等k个码多项式必是线性无关的，设可以由这些码多项式所对应的码字，构成循环码的生成矩阵G，则

g(x)=g

n-kx

n-k+g

n-k-1

x

n-k-1+…+g1x+g0xg(x)=g

n-kx

n-k+1+g

n-k-1

x

n-k+…+g1x2+g0x…xk-1g(x)=g

n-kx

n-1+g

n-k-1

x

n-2+…+g0xk-1所以xn-1=g(x)h(x)=(g

n-kx

n-k+…+g1x+g0)(hkxk+…+h1x+h0)线性分组码的任一码字都是其它码字的线性组合，因此只需找一个基底作为其它码字的生成基底

由此可知等式右边的x

n-1，x

n-2，…，x的系数均为0，即

g0h0=-1g0h1+g1h0=0…g0h1+g1h

i-1+…+g

n-khi-(n-k)=0…g0h

n-1+g1h

n-2+…+g

n-khk-1=0g

n-khk=1(5.1.2)

上式可简写成

g0hi+g1h

i-1+…+g

n-kh

i-(n-k)=0i=1，2，…，n-1g0h0+g

n-khk=0因此［n，k］循环码的一致校验矩阵(5.1.3)

容易验证

G·HT=0

(5.1.4)

所以，我们称h(x)=(xn-1)／g(x)为码的校验多项式，由式(5.1.3)可以看出，H矩阵的行完全由h(x)的系数决定。如例5.1中［7，4］码的校验多项式相应的H矩阵为

定理5.1.4令C1和C2分别由g1(x)和g2(x)生成的两个不同的循环码，则当且仅当g2(x)｜g1(x)时，C1C2。

证明若g2(x)｜g1(x)，则g1(x)=a(x)g2(x)，也就是由g1(x)的所有倍式生成的循环码C1必在由g2(x)生成的码C2中，所以C2C1。反之，若C2C1，则C1的每一个码字不但是g1(x)的倍式，也必是g2(x)的倍式，

g2(x)｜g1(x)m1(x)。若g2(x)｜m1(x)，则m1(x)是C2码的一个码字，因而C1码的每一码字g1(x)m1(x)必包含有C2码的码字，C1C2，这与C1C2的假设相矛盾，所以g2(x)m1(x)，可知g2(x)｜g1(x)。该定理给出了C1是C2码子码的充要条件。

四、系统码的构成用式(5.1.1)矩阵生成的循环码，并不是系统码。系统码的G矩阵为

G=［Ikp］

左边是k×k阶单位方阵。这相当于码字多项式的第n-1次至n-k次的系数是信息位，而其余的为校验位，这相当于

C(x)=m(x)x

n-k+r(x)≡0(modg(x))(5.1.5)

式中

m(x)=mk-1xk-1+mk-2

xk-2+…+m1x+m0

是信息多项式，(mk-1，…，m1，m0)是信息位，而

r(x)=r

n-k-1

x

n-k-1+r

n-k-2

x

n-k-2+…+r1x+r0

是校验位多项式，相应的系数是码元的校验位。由上式可得-r(x)=C(x)+m(x)x

n-k≡m(x)x

n-k(modg(x))

(5.1.6)

所以要构造用g(x)生成的系统码，首先必须将信息组乘以x

n-k变成x

n-km(x)；然后，用g(x)除，得到余式r(x)；再将其各项系数取加法逆元，就得到了所要求的校验位。因此，循环码系统码的编码问题就是以g(x)为模的除法问题。

由G=［Ikp］可知，信息组的基底矢量是：(100…0)，(010…0)，…，(00…01)，相应的信息多项式分别为：m1(x)=xk-1，m2(x)=xk-2，…，mk(x)=1。与这些信息多项式相应的校验多项式分别为：

r1(x)≡x

n-kxk-1(modg(x))，r2(x)≡x

n-kxk-2(modg(x))，

…，rk(x)≡x

n-k(modg(x))。

一般写成

ri≡x

n-kxk-i≡x

n-i(modg(x))i=1，2，…，k

与此相应的码多项式为

g(x)qi(x)=Ci(x)=x

n-i

-ri(x)i=1，2，…，k共k个，它们的系数就组成了系统码G矩阵的行。

(5.1.7)(5.1.8)

(5.1.9)

例5.2二进制［7，4］码的g(x)=x3+x2+1，求系统码的G和H矩阵。

r1(x)≡x6≡x2+x(modg(x))r2(x)≡x5≡x+1(modg(x))r3(x)≡x4≡x2+x+1(modg(x))r4(x)≡x3≡x2+1(modg(x))

在GF(2)上，元素的逆元就是它自己，所以1000110010001100101110001101G==［Ikp］101110011100100111001H==［-pTIn-k］§5.2由生成多项式的根定义循环码

循环码是模xn-1剩余代数中的一个以g(x)作生成元的理想，每一个码多项式都是g(x)的倍式。因此g(x)的根亦必是所有码字多项式的根，基于这点，我们可以从根来定义循环码。设码的生成多项式g(x)=xr+g

r-1

x

r-1+…+g1(x)+g0

gi∈GF(q)

它必在某一个GF(q)的扩域上完全分解，即它的全部根必在此扩域上。关于g(x)的根有两种情况：一是g(x)无重根，一是有重根。由于有重根情况下用g(x)生成码，比无重根时生成的码除个别码外通常要差［参考书7］，故下面我们仅讨论g(x)无重根的情况。为此，首先要找出g(x)无重根的条件。g(x)｜(xn-1)，或g(x)h(x)=xn-1。若g(x)有ri个重根，则xn-1也必含有ri个重根。因此要保证g(x)无重根，首先必须要求xn-1无重根。

定理5.2.1

在GF(q)上多项式xn-1无重根的充要条件是(n，q)=1。

例5.3求GF(24)上以α，α2，α4为根的循环码。设α∈GF(24)是本原域元素，则它的最小多项式就是本原多项式m1(x)=x4+x+1，α，α2，α4，α8是它的共轭根系。因此以α，α2，α4，α8为根的循环码的生成多项式g(x)=x4+x+1，码长n就是α的级数，等于24-1=15，故得到一个［15，11］码，这是一个循环汉明码。

设［15，11］码的码多项式C(x)

C(x)=c

14x

14+c13x13+…+c0，ci∈GF(2)，i=0，1，2，…，14则

C(α)=c14α14+c

13α13+…+c1α+c0=0C(α2)=c

14(α2)14+c13(α2)13+…+c1α2+c0=0C(α4)=c

14(α4)14+c

13(α4)13+…+c1α4+c0=0C(α8)=c

14(α8)14+c

13(α8)13+…+c1α8+c0=0或

(5.2.5)得到H的另一种表示方式：g（x）的根的表示

定理5.2.1若H矩阵的元素均在GF(qm)中，且第j行元素等于第i行相应元素的q次幂；则在GF(q)中，由第j行元素所组成的m行，与第i行元素所组成的m行之间，每行均线性相关。

证明设H的第i行元素为α0，α1，α2，…，αn-1,第j行元素为αq·0，αq·1，αq·2，…，αq(n-1)。令x是GF(qm)中的任一元素，α是本原域元素，则x与xq可用域的自然基表示成

x=a0+a1α+a2α2+…+a

m-1α(m-1)

ai∈GF(q)

(5.2.6)xq=b0+b1α+b2α2+…+b

m-1α(m-1)

bi∈GF(q)(5.2.7)由式(5.2.6)，并根据推论4.5.3可得

xq=(a0+a1α+a2α2+…+a

m-1α(m-1))q=aq0+aq1αq+aq2α2q+…+aq

m-1αq(m-1)=a0+a1αq+a2α2q+…+a

m-1αq(m-1)

(5.2.8)定义

αiq=c

i0+c

i1α+…+c

i,m-1αm-1

c

ij∈GF(q)，i=0，1，…，m-1比较式(5.2.7)与式(5.2.8)并利用上式可知，xq的系数(b0，b1，…，b

m-1)完全可由x的系数(a0，a1，…，a

m-1)的线性组合得到。

α2，α4，α8与α有完全相同的最小多项式m1(x)，因而它们有完全相同的零空间。而该定理也说明了这一点。所以在式(5.2.5)的H矩阵中，仅只考虑α14，α13，…，α，1这一行的GF(2)上的四重表示即可。因而［15，11］循环汉明码的H为

式中，α14，α13，…，α和1的四重表示见表4-2(下同)。

一般情况下，由于共轭根系有相同的最小多项式，因此由定理5.2.1及式(5.2.2)的H矩阵在GF(2m)域中可以简化为

例5.4求以GF(24)中的1，α，α2，α4元素为根的二进制循环码。1=α0的最小多项式是1+x，所以

g(x)=(1+x)(x4+x+1)=x5+x4+x2+1n=LCM(1，15)=15

得到一个［15，10］码，该码的H矩阵是显然，这是一个增余删信汉明循环码。

一般情况下，GF(2)上的循环汉明码是一个［2m-1，2m-1-m］码，它的校验矩阵

(5.2.10)αi∈GF(2m)

而增余删信汉明循环码是［2m-1，2m-2-m］码，它的校验矩阵

(5.2.11)§5.3幂等多项式和最小循环码§5.4缩短循环码与准循环码§5.6多项式及域元素运算电路

一、多项式相加电路已知GF(q)上的两多项式

A(x)=a

n-1

x

n-1+a

n-2

x

n-2+…+a1x+a0

ai∈GF(q)

B(x)=b

n-1

x

n-1+b

n-2

x

n-2+…+b1x+b0

bi∈GF(q)由第四章所定义的多项式相加

C(x)=A(x)+B(x)=(a

n-1+b

n-1)x

n-1+…+(a1+b1)x+(a0+b0)=c

n-1

x

n-1+c

n-2

x

n-2+…+c1x+c0

ci∈GF(q)，ci=ai+bi，i=0，1，2，…，n-1

要完成上述多项式相加，可用图5-1所示的电路完成。图5-1多项式A(x)+B(x)并行运算电路图5-1及以后各图中符号的意义如下：：

代表一个寄存GF(q)上元素的单元，可用触发器、磁芯或其它存贮单元组成；：代表模q相加器，无进位运算；：代表两个输入端与门；：代表乘a的模q常数乘法器，无进位运算；：代表两个输入端的或门。两个多项式相加之结果C(x)的系数存贮在A(x)寄存器中。图5-2为串行相加电路，相加结果送入A(x)系数寄存器中。图5-2多项式A(x)+B(x)串行运算电路若为A(x)-B(x)，则只要把B(x)系数以GF(q)中的加法逆元代替得到-B(x)，再作-B(x)+A(x)运算即可。在二进制情况下“-”与“+”运算相同，因此相加电路与相减电路一样。

二、多项式相乘电路设两多项式为：

A(x)=akxk+ak-1

xk-1+…+a1x+a0

ai∈GF(q)B(x)=brxr+b

r-1

x

r-1+…+b1x+b0

bi∈GF(q)已知两多项式相乘为

C(x)=A(x)B(x)=akbrxk+r+(akb

r-1+ak-1br)xk+r-1

+(akb

r-2+ak-1b

r-1+ak-2br)xk+r-2+…

+(akb

r-i+ak-1b

r-(i-1)+…+ak-ibr)xk+r-i+…

+(a1b0+a0b1)x+a0b0可用图5-3所示的电路完成上述运算过程。该电路由r个存贮单元组成的r级移位寄存器，至多r个模q相加器和至多(r+1)个模q常乘器所组成。图5-3乘B(x)运算电路工作开始时，r级移位存贮器中的存数全清洗为0，且规定被乘多项式A(x)的高次项系数ak首先送入电路，电路的工作过程如下：(1)当A(x)的最高次系数ak首先送入时，乘积C(x)的最高次项xk+r的系数akbr就出现在输出端，同时ak存入移存器的第一级(最左一级)。(2)A(x)的第二个系数ak-1送入电路时,ak由第一级输出送入第二级,同时与b

r-1相乘和ak-1

br相加后送到输出端,这就是C(x)的xk+r-1项系数akb

r-1+ak-1

br。此时，移存器内的存贮数据为ak-1，ak，0，0，…，0(自左至右)。(3)上述过程重复进行，直至k次移位后，A(x)的系数全部送入移存器。k+r+1次移位后，移存器输出C(x)的常数项a0+b0，移存器中的内容全部恢复到全为0初态，乘法完成。由上面乘法过程可以看出,这种乘法电路完成一次乘法运算,共需移位A(x)+B(x)+1次。

图5-4另一种乘B(x)电路例5.11A(x)=x3+x2+1，B(x)=x2+1，它们都是GF(2)上的多项式，求C(x)=A(x)B(x)之电路。A(x)乘B(x)的电路如图5-5所示。因为进行模2运算，故常乘器或者乘0或者乘1。若乘0，常乘器是一开路线；若乘1，则是一闭合线。该电路的运算工作过程如表5-3所示。由表看到，6次移位后，移存器输出了A(x)=(x3+x2+1)(x2+1)=x5+x4+x3+1的全部系数：111001，移存器内容全部恢复到全为0初态。图5-5乘B(x)=x2+1的电路表5-3

x3+x2+1乘x2+1过程表

三、多项式除法电路

GF(q)上的两多项式

A(x)=akxk+ak-1

xk-1+…+a1x+a0B(x)=brxr+b

r-1

x

r-1+…+b1x+b0

k≥r

由欧几里德除法可知：

A(x)=q(x)B(x)+r(x)0≤r(x)＜B(x)或r(x)=0

今后均假设k≥r，否则q(x)=0，r(x)=A(x)。多项式A(x)被B(x)除的电路如图5-6所示，它由r级移存器、至多r个GF(q)加法器和至多r+1个常乘器组成。图5-6除B(x)=brxr+…+b1x+b0电路为了理解除法电路的工作过程，下面我们列出B(x)除A(x)的竖式运算式子：brxr+b

r-1

x

r-1+…+b1x+b0(除式)b-1rakxk-r+b-1r(ak-1-b-1rbr-1ak)xk-r-1+…(商式)akxk+ak-1xk-1+…+a1x+a0(被除式)-(akxk+b-1rbr-1akxk-1+…+b0b-1rakxk-r)(ak-1-b-1rbr-1ak)xk-1+…+(ak-r-b0b-1rak)xk-r+…(A)-((ak-1-b-1rbr-1ak)xk-1+…)……(余式)由上面式子，我们讨论图5-6除法电路的工作过程。(1)开始运算时r级移存器中的存数全部清为0。第一个移位节拍后，被除多项式A(x)的最高次项xk的系数ak首先进入电路的最左一级。r次移位后ak进入到移存器的最右一级中，此时自左至右移存器中的内容为ak-r+1，ak-r+2，…，ak-1，ak。(2)第r+1次移位后，ak输出与b-1r相乘得到akb-1r，这就是商式q(x)的第一项xk-r的系数。akb-1r同时反馈到后面各级寄存器中(所以称这种除法电路为线性反馈移存器)减去akb-1rB(x)，所以，此时移存器中自左至右的内容为(ak-r-b0b-1rak),(ak-r+1-b1b-1rak)，…，(ak-1-br-1

b-1rak)，这相应于竖式运算中的第A项所示的结果。(3)依次类推，经k+1次移位后，完成了整个除法运算过程。它的输出为商式q(x)，而移存器中的内容就是余式r(x)的系数。例5.12设除式B(x)=x3+x+1，被除式A(x)=x4+x3+1都是GF(2)上的多项式，求B(x)除A(x)的电路。除B(x)的除法电路如图5-7所示，它由3级移存器和2个模2相加器组成。因为在GF(2)中，1的逆元仍为1，相加和相减相同，所以b-1r与-bi常乘器均为一条闭合线。图5-7除B(x)=x3+x+1电路完成上述两个多项式相除的长除法运算式如下：

x+1(商式)

x3+x+1x4+x3+1(被除式)(除式)x4

+x2+x

x3+x2+x+1

x3+x+1

x2(除式)这里

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

商为x+1，余式为x2。表5-4中列出了电路的工作过程。显然，r+1=4次移位后得到商的第一个系数，k+1=5次移位后，就完成了整个除法运算，并在D1、D2、D3组成的移存器中保留了余式001，即x2。表5-4

B(x)除x4+x3+1的运算过程表四、多项式相乘相除电路

GF(q)上的多项式A(x)、H(x)、G(x)分别为：A(x)=akxk+ak-1xk-1+…+a1x+a0H(x)=hrxr+h

r-1

x

r-1+…+h1x+h0G(x)=grxr+g

r-1

x

r-1+…+g1x+g0

若A(x)与H(x)相乘后再用G(x)除，则

A(x)H(x)=q(x)G(x)+r(x)0≤r(x)＜G(x)，或r(x)=0

该运算可用图5-8所示的电路实现，它由r级移存器、至多有2(r+1)个GF(q)的常乘器和r+1个GF(q)的相加器组成。显然，该电路就是图5-4与图5-6所示的两种电路的结合。如果H(x)与G(x)次数不等，则只要按G(x)与H(x)中最高次数设计移存器级数即可。图5-8乘H(x)除G(x)电路例5.13设GF(2)上的3个多项式为：

A(x)=x4+x+1，H(x)=x2+1，G(x)=x3+x+1

则

A(x)H(x)=(x4+x+1)(x2+1)=x6+x4+x3+x2+x+1=x3(x3+x+1)+(x2+x+1)=q(x)G(x)+r(x)

可用图5-9的电路实现，该电路的工作过程如表5-5所示，移位A(x)+1=5次后，即得到了商式x3和余式x2+x+1。图5-9乘(x2+1)除(x3+x+1)电路若GF(2)上的多项式

A(x)=x4+x+1，H(x)=x3+x+1，G(x)=x2+1

则

A(x)H(x)=(x4+x+1)(x3+x+1)=x7+x5+x3+x2+1=(x5+x+1)(x2+1)+x=q(x)G(x)+r(x)

该运算可用图5-10所示的电路实现，它的工作过程如表5-5所示。显然，移位A(x)+H(x)+1-G(x)=6次后，电路即可完成运算，它的输出是商

q(x)=(x5+x+1)，在移存器中保留了余式x。图5-10乘(x3+x+1)除(x2+1)电路表5-5图5-9和图5-10电路运算过程表五、多项式代数和Galois域计算电路1.计算以g(x)为模的多项式剩余类要确定GF(q)上的多项式

f(x)=fkxk+fk-1xk-1+…+f1x+f0

在模g(x)中属于哪一剩余类，这相当于用g(x)除f(x)求余式

f(x)=q(x)g(x)+r(x)0≤r(x)＜g(x)或r(x)=0

所以，f(x)∈{r(x)}或f(x)∈{0}。因此，计算f(x)在模g(x)的哪一剩余类中的电路，就是一个g(x)除法电路。2.求GF(q)扩域GF(qm)上的元素及其相乘电路由第四章知，如果有一个GF(q)上的m次本原多项式p(x)，则以它的根α的所有幂次，就得到了GF(qm)上的所有qm-1个非0元素；1，α，α2，…，αqm-2，这qm-1个元素构成一个循环乘法群。要得到这些元素，可以用p(x)除法电路自发运算(无输入运算)qm-1次得到，且电路的初始状态为α或其共轭根系元素的GF(q)上的m重。例5.14求GF(24)上的所有15个非0元素。用GF(2)上的四次本原多项式p(x)=x4+x+1作除法电路，进行自发运算即可得15个非0元素，如图5-11所示。图5-11求GF(24)元素电路开始计算时电路的初始状态置α=(10000)，每移位一次就在四级移存器中得到α2，α3，α4，…，α15，α，α2…。相应地，输出序列就是α，α2，α3，…，是一个周期为15的二进制序列。该电路的运算过程如表5-6所示。表5-6图5-11

电路运算表由此看出，移位寄存器每右移一次相当于乘α(左移一次相当于乘α-1)，15次移位后电路回到初始状态，它的输出序列显然也以15个码元为周期。由于用4级线性移存器所能产生的最长序列的长度为24-1=15，所以，这种用GF(2)上的m次本原多项式组成的除法电路(无输入情况)，称为最长序列线性移存器电路，所产生的序列称为m序列，它的周期是2m-1。3.计算R(xj)电路循环码的译码电路中经常要计算R(x)=r

n-1

x

n-1+r

n-2

x

n-2+…+r1x+r0的R(α)或R(αj)的值，式中，α是g(x)的根，g(α)=0。因为

R(x)=q(x)g(x)+r(x)0≤r(x)＜g(x)或r(x)=0

所以

R(α)=q(α)g(α)+r(α)=r(α)因此，把R(x)的系数(r

n-1，r

n-2，…，r1，r0)送入g(x)的除法电路中，最后在移存器中得到的余式就是R(α)。计算R(αj)比较麻烦。因为，在GF(qm)上，每个元素αj(j=0，1，…，qm-2)用自然基表示时，都可表示成次数小于m次的α多项式，α∈GF(qm)是本原域元素，它是m次本原多项式的根。因此要计算R(αj)，首先必须把αj表示成次数小于m的α多项式表示。现举例说明。例5.15计算GF(24)上的R(α5)，α是g(x)=x4+x+1的根，g(α)=α4+α+1=0。由于：1·α5=α2+α

α·α5=α6=α3+α2

α2·α5=α7=α3+α+1α3·α5=α8=α2+1现在要求计算R(α5)，也就是

R(α5)=q(α5)g(α5)+r(α5)因为要求在g(x)除法电路中，每右移一次相当于乘α5，为此必须先介绍乘α5电路。设原移存器的初始值为a0+a1α+a2α2+a3α3，乘以α5则变成

α5(a0+a1α+a2α2+a3α3)=a3α8+a2α7+a1α6+a0α5=a3(α2+1)+a2(α3+α+1)+a1(α3+α2)+a0(α2+α)=(a1+a2)α3+(a0+a1+a3)α2+(a0+a2)α+(a2+a3)所以，新的a0是原a2+a3，新的a1是原a0+a2，新的a2是原a0+a1+a3，新的a3是原a1+a2等。因此，在GF(24)上乘α5的电路如图5-12所示。送入R(x)，15次移位后就在该电路中的存贮器内得到R(α5)。图5-12GF(24)域上乘α5§5.7循环码的编码电路

一、n-k级编码器n-k级编码器有两种：一是g(x)的乘法电路，另一是g(x)的除法电路。前者所编出的码是非系统码，后者是系统码。

1.g(x)乘法电路编码器由§5.1可知，［n，k］循环码的编码就是将k位长的信息组m(x)=mk-1xk-1+mk-2xk-2+…+m1x+m0，编成长为n的码字C(x)。由循环码理论可知，C(x)=m(x)g(x)，g(x)=n-k。因此可用g(x)乘法电路实现非系统码编码。

例5.16求GF(2)上［7，4］循环汉明码编码器。该码的生成多项式g(x)=x3+x+1，由此可得图5-13的n-k=3级乘法编码器。设送入的信息组为1001，则编出的码组是1010011，相应的码多项式

C(x)=(x3+1)(x3+x+1)=x6+x4+x+1图5-13［7，4］循环汉明码三级乘法编码器

2.g(x)除法电路编码器由式(5.1.6)和式(5.1.5)知，要得到系统码必须首先将信息组m(x)乘以x

n-k，变成

x

n-km(x)，然后再用g(x)除，求得相应的余式r(x)，把其系数取“-”号就得到了相应的校验位，加上原来的信息组就组成了码字C。即

m(x)x

n-k=q(x)g(x)+r(x)0≤r(x)＜g(x)C(x)=m(x)x

n-k-r(x)所以，［n，k］系统码编码电路就是乘x

n-k除g(x)的电路。［7，4］循环汉明码系统码编码电路如图5-14所示。这种电路的工作过程如下：图5-14［7，4］循环汉明码系统码编码电路

(1)3级移存器的初始状态全清为0，门1开、门2关，然后进行移位，送入信息组m(x)的系数，高次位系数首先进入电路，它一方面经或门输出,一方面自动乘以x

n-k=x3次后进入g(x)除法电路，从而完成了

x

n-km(x)=x3m(x)的作用。(2)4次移位后m(x)全部送入电路，完成了除法作用，此时在移存器内保留了余式r(x)的系数，在二进制情况下就是校验元。

(3)此时门1关、门2开，再经过3次移位后，把移存器的校验元全部输出，与原先的4位信息元组成了一个长为7的码字C(x)。(4)门1开、门2关，送入第二组信息组重复上述过程。表5-7列出了图5-14的编码工作过程。输入的信息组为1001，7次移位后输出端得到已编好的码组1001110。表5-7图5-14电路的编码过程

二、k级编码器

［n，k］循环码系统码的编码器，也可根据校验多项式h(x)=hkxk+hk-1

xk-1+…+h1x+h0构造。设系统码的码多项式为

C(x)=c

n-1

x

n-1+c

n-2

x

n-2+…+c

n-kx

n-k

+c

n-k-1x

n-k-1+…+c1x+c0它的前k位系数：c

n-1，c

n-2，…，c

n-k