第五章循環(huán)碼

第5章循環(huán)碼5.1循環(huán)碼與理想5.2由生成多項(xiàng)式的根定義循環(huán)碼5.3冪等多項(xiàng)式和最小循環(huán)碼

5.4縮短循環(huán)碼與準(zhǔn)循環(huán)碼

5.5平方剩余碼5.6多項(xiàng)式及域元素運(yùn)算電路5.7循環(huán)碼的編碼電路習(xí)題5.1循環(huán)碼與理想

一、基本概念［7，4］漢明碼CH的H矩陣為

由第二章可知，交換H矩陣各列，并不會(huì)影響碼的糾錯(cuò)能力。把上述H矩陣的列進(jìn)行交換后變?yōu)?/p>

由此矩陣可明顯看出，第二行是第一行循環(huán)右移一位得到，第三行是第二行循環(huán)右移一位。由此矩陣編出的16個(gè)碼字為：1000110，0100011，1010001，1101000，0110100，0011010，0001101；1001011，1100101，1110010，0111001，1011100，0101110，0010111；1111111；0000000。

由這些碼字看出，若C1∈CH，則它的右(左)移循環(huán)移位所得到的n重也是一個(gè)碼字，具有這種特性的［n，k］分組碼稱為循環(huán)碼。由于［n，k］線性分組碼是n維線性空間Vn中的一個(gè)k維子空間，因此［n，k］循環(huán)碼是n維線性空間中的一個(gè)k維循環(huán)子空間。

定義5.1.1

一個(gè)n重子空間Vn，k∈Vn，若對(duì)任何一個(gè)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為循環(huán)子空間或循環(huán)碼。

二、碼的多項(xiàng)式描述從第二章可知，GF(p)上的所有n重構(gòu)成一個(gè)線性空間Vn，其中每個(gè)矢量是分量取自GF(p)上n重，若將每個(gè)n重和系數(shù)取自GF(p)上的多項(xiàng)式相對(duì)應(yīng)：n

重：

(a

n-1，a

n-2，…，a1，a0)ai∈GF(p)多項(xiàng)式：(a

n-1

x

n-1+a

n-2

x

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

則它們之間建立了一一對(duì)應(yīng)關(guān)系。在第四章中已指出，所有次數(shù)小于n次的多項(xiàng)式一定在模n次多項(xiàng)式F(x)∈Fp［x］的不同剩余類中，即f(x)∈{a

n-1

x

n-1+a

n-2

x

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

因此，Vn中每一個(gè)n重都與GF(p)上的次數(shù)低于n次的一個(gè)多項(xiàng)式相對(duì)應(yīng)，并必在模F(x)的某一剩余類中。第四章中（p107）已證明，在模F(x)運(yùn)算下，模F(x)的剩余類構(gòu)成一多項(xiàng)式剩余類環(huán)Fp［x］／F(x)，若在該環(huán)中再定義一個(gè)數(shù)乘，即

ca(x)={ca

n-1

x

n-1+ca

n-2

x

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

則可以證明模F(x)的剩余類構(gòu)成一個(gè)n維線性空間，稱為剩余類線性結(jié)合代數(shù)。(線形空間有數(shù)乘的要求)

定理5.1.1以多項(xiàng)式xn-1為模的剩余類線性結(jié)合代數(shù)中，其一個(gè)子空間Vn，k是一個(gè)循環(huán)子空間(循環(huán)碼)的充要條件是：Vn，k是一個(gè)理想。

定義5.1.2

生成多項(xiàng)式g(x)是模xn-1剩余類代數(shù)中，一個(gè)理想的次數(shù)最低的非零首一多項(xiàng)式，它是理想或循環(huán)碼的生成元。定理5.1.2GF(q)(q為素?cái)?shù)或素?cái)?shù)的冪)上的［n，k］循環(huán)碼中，存在有唯一的n-k次首一多項(xiàng)式

g(x)=x

n-k+g

n-k-1x

n-k-1+…+g1x+g0，每一碼多項(xiàng)式C(x)都是g(x)的倍式，且每一個(gè)≤(n-1)次的g(x)倍式一定是碼多項(xiàng)式。

定理5.1.3

GF(q)上［n，k］循環(huán)碼的生成多項(xiàng)式g(x)一定是xn-1的因式：xn-1=g(x)h(x)。反之，若g(x)為n-k次，且g(x)｜(xn-1)，則該g(x)一定生成一個(gè)［n，k］循環(huán)碼。

例5.1在GF(2)上，x7-1=(x+1)(x3+x+1)(x3+x2+1)，求［7，4］循環(huán)碼。找一個(gè)能除盡x7-1的n-k=3次首一多項(xiàng)式g(x)，可在x3+x+1與x3+x2+1中任選一個(gè)，現(xiàn)在選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

它們相應(yīng)的n重為：(0001101)，(0011010)，(0110100)，(1101000)，把它們作為生成矩陣的行，就得到了［７，4］碼的生成矩陣。

三、循環(huán)碼的生成矩陣、校驗(yàn)矩陣由前知，xn-1=g(x)h(x)。若g(x)為n-k次，則h(x)為k次多項(xiàng)式。以g(x)作為生成多項(xiàng)式所組成的［n，k］循環(huán)碼中g(shù)(x)，xg(x)，…，xk-1

g(x)等k個(gè)碼多項(xiàng)式必是線性無(wú)關(guān)的，設(shè)可以由這些碼多項(xiàng)式所對(duì)應(yīng)的碼字，構(gòu)成循環(huán)碼的生成矩陣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)線性分組碼的任一碼字都是其它碼字的線性組合，因此只需找一個(gè)基底作為其它碼字的生成基底

由此可知等式右邊的x

n-1，x

n-2，…，x的系數(shù)均為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)

上式可簡(jiǎn)寫成

g0hi+g1h

i-1+…+g

n-kh

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

n-khk=0因此［n，k］循環(huán)碼的一致校驗(yàn)矩陣(5.1.3)

容易驗(yàn)證

G·HT=0

(5.1.4)

所以，我們稱h(x)=(xn-1)／g(x)為碼的校驗(yàn)多項(xiàng)式，由式(5.1.3)可以看出，H矩陣的行完全由h(x)的系數(shù)決定。如例5.1中［7，4］碼的校驗(yàn)多項(xiàng)式相應(yīng)的H矩陣為

定理5.1.4令C1和C2分別由g1(x)和g2(x)生成的兩個(gè)不同的循環(huán)碼，則當(dāng)且僅當(dāng)g2(x)｜g1(x)時(shí)，C1C2。

證明若g2(x)｜g1(x)，則g1(x)=a(x)g2(x)，也就是由g1(x)的所有倍式生成的循環(huán)碼C1必在由g2(x)生成的碼C2中，所以C2C1。反之，若C2C1，則C1的每一個(gè)碼字不但是g1(x)的倍式，也必是g2(x)的倍式，

g2(x)｜g1(x)m1(x)。若g2(x)｜m1(x)，則m1(x)是C2碼的一個(gè)碼字，因而C1碼的每一碼字g1(x)m1(x)必包含有C2碼的碼字，C1C2，這與C1C2的假設(shè)相矛盾，所以g2(x)m1(x)，可知g2(x)｜g1(x)。該定理給出了C1是C2碼子碼的充要條件。

四、系統(tǒng)碼的構(gòu)成用式(5.1.1)矩陣生成的循環(huán)碼，并不是系統(tǒng)碼。系統(tǒng)碼的G矩陣為

G=［Ikp］

左邊是k×k階單位方陣。這相當(dāng)于碼字多項(xiàng)式的第n-1次至n-k次的系數(shù)是信息位，而其余的為校驗(yàn)位，這相當(dāng)于

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

是信息多項(xiàng)式，(mk-1，…，m1，m0)是信息位，而

r(x)=r

n-k-1

x

n-k-1+r

n-k-2

x

n-k-2+…+r1x+r0

是校驗(yàn)位多項(xiàng)式，相應(yīng)的系數(shù)是碼元的校驗(yàn)位。由上式可得-r(x)=C(x)+m(x)x

n-k≡m(x)x

n-k(modg(x))

(5.1.6)

所以要構(gòu)造用g(x)生成的系統(tǒng)碼，首先必須將信息組乘以x

n-k變成x

n-km(x)；然后，用g(x)除，得到余式r(x)；再將其各項(xiàng)系數(shù)取加法逆元，就得到了所要求的校驗(yàn)位。因此，循環(huán)碼系統(tǒng)碼的編碼問(wèn)題就是以g(x)為模的除法問(wèn)題。

由G=［Ikp］可知，信息組的基底矢量是：(100…0)，(010…0)，…，(00…01)，相應(yīng)的信息多項(xiàng)式分別為：m1(x)=xk-1，m2(x)=xk-2，…，mk(x)=1。與這些信息多項(xiàng)式相應(yīng)的校驗(yàn)多項(xiàng)式分別為：

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

與此相應(yīng)的碼多項(xiàng)式為

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

n-i

-ri(x)i=1，2，…，k共k個(gè)，它們的系數(shù)就組成了系統(tǒng)碼G矩陣的行。

(5.1.7)(5.1.8)

(5.1.9)

例5.2二進(jìn)制［7，4］碼的g(x)=x3+x2+1，求系統(tǒng)碼的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由生成多項(xiàng)式的根定義循環(huán)碼

循環(huán)碼是模xn-1剩余代數(shù)中的一個(gè)以g(x)作生成元的理想，每一個(gè)碼多項(xiàng)式都是g(x)的倍式。因此g(x)的根亦必是所有碼字多項(xiàng)式的根，基于這點(diǎn)，我們可以從根來(lái)定義循環(huán)碼。設(shè)碼的生成多項(xiàng)式g(x)=xr+g

r-1

x

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

gi∈GF(q)

它必在某一個(gè)GF(q)的擴(kuò)域上完全分解，即它的全部根必在此擴(kuò)域上。關(guān)于g(x)的根有兩種情況：一是g(x)無(wú)重根，一是有重根。由于有重根情況下用g(x)生成碼，比無(wú)重根時(shí)生成的碼除個(gè)別碼外通常要差［參考書(shū)7］，故下面我們僅討論g(x)無(wú)重根的情況。為此，首先要找出g(x)無(wú)重根的條件。g(x)｜(xn-1)，或g(x)h(x)=xn-1。若g(x)有ri個(gè)重根，則xn-1也必含有ri個(gè)重根。因此要保證g(x)無(wú)重根，首先必須要求xn-1無(wú)重根。

定理5.2.1

在GF(q)上多項(xiàng)式xn-1無(wú)重根的充要條件是(n，q)=1。

例5.3求GF(24)上以α，α2，α4為根的循環(huán)碼。設(shè)α∈GF(24)是本原域元素，則它的最小多項(xiàng)式就是本原多項(xiàng)式m1(x)=x4+x+1，α，α2，α4，α8是它的共軛根系。因此以α，α2，α4，α8為根的循環(huán)碼的生成多項(xiàng)式g(x)=x4+x+1，碼長(zhǎng)n就是α的級(jí)數(shù)，等于24-1=15，故得到一個(gè)［15，11］碼，這是一個(gè)循環(huán)漢明碼。

設(shè)［15，11］碼的碼多項(xiàng)式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行相應(yīng)元素的q次冪；則在GF(q)中，由第j行元素所組成的m行，與第i行元素所組成的m行之間，每行均線性相關(guān)。

證明設(shè)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)，并根據(jù)推論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的系數(shù)(b0，b1，…，b

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

m-1)的線性組合得到。

α2，α4，α8與α有完全相同的最小多項(xiàng)式m1(x)，因而它們有完全相同的零空間。而該定理也說(shuō)明了這一點(diǎn)。所以在式(5.2.5)的H矩陣中，僅只考慮α14，α13，…，α，1這一行的GF(2)上的四重表示即可。因而［15，11］循環(huán)漢明碼的H為

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

一般情況下，由于共軛根系有相同的最小多項(xiàng)式，因此由定理5.2.1及式(5.2.2)的H矩陣在GF(2m)域中可以簡(jiǎn)化為

例5.4求以GF(24)中的1，α，α2，α4元素為根的二進(jìn)制循環(huán)碼。1=α0的最小多項(xiàng)式是1+x，所以

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

得到一個(gè)［15，10］碼，該碼的H矩陣是顯然，這是一個(gè)增余刪信漢明循環(huán)碼。

一般情況下，GF(2)上的循環(huán)漢明碼是一個(gè)［2m-1，2m-1-m］碼，它的校驗(yàn)矩陣

(5.2.10)αi∈GF(2m)

而增余刪信漢明循環(huán)碼是［2m-1，2m-2-m］碼，它的校驗(yàn)矩陣

(5.2.11)§5.3冪等多項(xiàng)式和最小循環(huán)碼§5.4縮短循環(huán)碼與準(zhǔn)循環(huán)碼§5.6多項(xiàng)式及域元素運(yùn)算電路

一、多項(xiàng)式相加電路已知GF(q)上的兩多項(xiàng)式

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)由第四章所定義的多項(xiàng)式相加

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

要完成上述多項(xiàng)式相加，可用圖5-1所示的電路完成。圖5-1多項(xiàng)式A(x)+B(x)并行運(yùn)算電路圖5-1及以后各圖中符號(hào)的意義如下：：

代表一個(gè)寄存GF(q)上元素的單元，可用觸發(fā)器、磁芯或其它存貯單元組成；：代表模q相加器，無(wú)進(jìn)位運(yùn)算；：代表兩個(gè)輸入端與門；：代表乘a的模q常數(shù)乘法器，無(wú)進(jìn)位運(yùn)算；：代表兩個(gè)輸入端的或門。兩個(gè)多項(xiàng)式相加之結(jié)果C(x)的系數(shù)存貯在A(x)寄存器中。圖5-2為串行相加電路，相加結(jié)果送入A(x)系數(shù)寄存器中。圖5-2多項(xiàng)式A(x)+B(x)串行運(yùn)算電路若為A(x)-B(x)，則只要把B(x)系數(shù)以GF(q)中的加法逆元代替得到-B(x)，再作-B(x)+A(x)運(yùn)算即可。在二進(jìn)制情況下“-”與“+”運(yùn)算相同，因此相加電路與相減電路一樣。

二、多項(xiàng)式相乘電路設(shè)兩多項(xiàng)式為：

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)已知兩多項(xiàng)式相乘為

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所示的電路完成上述運(yùn)算過(guò)程。該電路由r個(gè)存貯單元組成的r級(jí)移位寄存器，至多r個(gè)模q相加器和至多(r+1)個(gè)模q常乘器所組成。圖5-3乘B(x)運(yùn)算電路工作開(kāi)始時(shí)，r級(jí)移位存貯器中的存數(shù)全清洗為0，且規(guī)定被乘多項(xiàng)式A(x)的高次項(xiàng)系數(shù)ak首先送入電路，電路的工作過(guò)程如下：(1)當(dāng)A(x)的最高次系數(shù)ak首先送入時(shí)，乘積C(x)的最高次項(xiàng)xk+r的系數(shù)akbr就出現(xiàn)在輸出端，同時(shí)ak存入移存器的第一級(jí)(最左一級(jí))。(2)A(x)的第二個(gè)系數(shù)ak-1送入電路時(shí),ak由第一級(jí)輸出送入第二級(jí),同時(shí)與b

r-1相乘和ak-1

br相加后送到輸出端,這就是C(x)的xk+r-1項(xiàng)系數(shù)akb

r-1+ak-1

br。此時(shí)，移存器內(nèi)的存貯數(shù)據(jù)為ak-1，ak，0，0，…，0(自左至右)。(3)上述過(guò)程重復(fù)進(jìn)行，直至k次移位后，A(x)的系數(shù)全部送入移存器。k+r+1次移位后，移存器輸出C(x)的常數(shù)項(xiàng)a0+b0，移存器中的內(nèi)容全部恢復(fù)到全為0初態(tài)，乘法完成。由上面乘法過(guò)程可以看出,這種乘法電路完成一次乘法運(yùn)算,共需移位A(x)+B(x)+1次。

圖5-4另一種乘B(x)電路例5.11A(x)=x3+x2+1，B(x)=x2+1，它們都是GF(2)上的多項(xiàng)式，求C(x)=A(x)B(x)之電路。A(x)乘B(x)的電路如圖5-5所示。因?yàn)檫M(jìn)行模2運(yùn)算，故常乘器或者乘0或者乘1。若乘0，常乘器是一開(kāi)路線；若乘1，則是一閉合線。該電路的運(yùn)算工作過(guò)程如表5-3所示。由表看到，6次移位后，移存器輸出了A(x)=(x3+x2+1)(x2+1)=x5+x4+x3+1的全部系數(shù)：111001，移存器內(nèi)容全部恢復(fù)到全為0初態(tài)。圖5-5乘B(x)=x2+1的電路表5-3

x3+x2+1乘x2+1過(guò)程表

三、多項(xiàng)式除法電路

GF(q)上的兩多項(xiàng)式

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

今后均假設(shè)k≥r，否則q(x)=0，r(x)=A(x)。多項(xiàng)式A(x)被B(x)除的電路如圖5-6所示，它由r級(jí)移存器、至多r個(gè)GF(q)加法器和至多r+1個(gè)常乘器組成。圖5-6除B(x)=brxr+…+b1x+b0電路為了理解除法電路的工作過(guò)程，下面我們列出B(x)除A(x)的豎式運(yùn)算式子：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除法電路的工作過(guò)程。(1)開(kāi)始運(yùn)算時(shí)r級(jí)移存器中的存數(shù)全部清為0。第一個(gè)移位節(jié)拍后，被除多項(xiàng)式A(x)的最高次項(xiàng)xk的系數(shù)ak首先進(jìn)入電路的最左一級(jí)。r次移位后ak進(jìn)入到移存器的最右一級(jí)中，此時(shí)自左至右移存器中的內(nèi)容為ak-r+1，ak-r+2，…，ak-1，ak。(2)第r+1次移位后，ak輸出與b-1r相乘得到akb-1r，這就是商式q(x)的第一項(xiàng)xk-r的系數(shù)。akb-1r同時(shí)反饋到后面各級(jí)寄存器中(所以稱這種除法電路為線性反饋移存器)減去akb-1rB(x)，所以，此時(shí)移存器中自左至右的內(nèi)容為(ak-r-b0b-1rak),(ak-r+1-b1b-1rak)，…，(ak-1-br-1

b-1rak)，這相應(yīng)于豎式運(yùn)算中的第A項(xiàng)所示的結(jié)果。(3)依次類推，經(jīng)k+1次移位后，完成了整個(gè)除法運(yùn)算過(guò)程。它的輸出為商式q(x)，而移存器中的內(nèi)容就是余式r(x)的系數(shù)。例5.12設(shè)除式B(x)=x3+x+1，被除式A(x)=x4+x3+1都是GF(2)上的多項(xiàng)式，求B(x)除A(x)的電路。除B(x)的除法電路如圖5-7所示，它由3級(jí)移存器和2個(gè)模2相加器組成。因?yàn)樵贕F(2)中，1的逆元仍為1，相加和相減相同，所以b-1r與-bi常乘器均為一條閉合線。圖5-7除B(x)=x3+x+1電路完成上述兩個(gè)多項(xiàng)式相除的長(zhǎng)除法運(yùn)算式如下：

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中列出了電路的工作過(guò)程。顯然，r+1=4次移位后得到商的第一個(gè)系數(shù)，k+1=5次移位后，就完成了整個(gè)除法運(yùn)算，并在D1、D2、D3組成的移存器中保留了余式001，即x2。表5-4

B(x)除x4+x3+1的運(yùn)算過(guò)程表四、多項(xiàng)式相乘相除電路

GF(q)上的多項(xiàng)式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

該運(yùn)算可用圖5-8所示的電路實(shí)現(xiàn)，它由r級(jí)移存器、至多有2(r+1)個(gè)GF(q)的常乘器和r+1個(gè)GF(q)的相加器組成。顯然，該電路就是圖5-4與圖5-6所示的兩種電路的結(jié)合。如果H(x)與G(x)次數(shù)不等，則只要按G(x)與H(x)中最高次數(shù)設(shè)計(jì)移存器級(jí)數(shù)即可。圖5-8乘H(x)除G(x)電路例5.13設(shè)GF(2)上的3個(gè)多項(xiàng)式為：

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的電路實(shí)現(xiàn)，該電路的工作過(guò)程如表5-5所示，移位A(x)+1=5次后，即得到了商式x3和余式x2+x+1。圖5-9乘(x2+1)除(x3+x+1)電路若GF(2)上的多項(xiàng)式

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)

該運(yùn)算可用圖5-10所示的電路實(shí)現(xiàn)，它的工作過(guò)程如表5-5所示。顯然，移位A(x)+H(x)+1-G(x)=6次后，電路即可完成運(yùn)算，它的輸出是商

q(x)=(x5+x+1)，在移存器中保留了余式x。圖5-10乘(x3+x+1)除(x2+1)電路表5-5圖5-9和圖5-10電路運(yùn)算過(guò)程表五、多項(xiàng)式代數(shù)和Galois域計(jì)算電路1.計(jì)算以g(x)為模的多項(xiàng)式剩余類要確定GF(q)上的多項(xiàng)式

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

在模g(x)中屬于哪一剩余類，這相當(dāng)于用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}。因此，計(jì)算f(x)在模g(x)的哪一剩余類中的電路，就是一個(gè)g(x)除法電路。2.求GF(q)擴(kuò)域GF(qm)上的元素及其相乘電路由第四章知，如果有一個(gè)GF(q)上的m次本原多項(xiàng)式p(x)，則以它的根α的所有冪次，就得到了GF(qm)上的所有qm-1個(gè)非0元素；1，α，α2，…，αqm-2，這qm-1個(gè)元素構(gòu)成一個(gè)循環(huán)乘法群。要得到這些元素，可以用p(x)除法電路自發(fā)運(yùn)算(無(wú)輸入運(yùn)算)qm-1次得到，且電路的初始狀態(tài)為α或其共軛根系元素的GF(q)上的m重。例5.14求GF(24)上的所有15個(gè)非0元素。用GF(2)上的四次本原多項(xiàng)式p(x)=x4+x+1作除法電路，進(jìn)行自發(fā)運(yùn)算即可得15個(gè)非0元素，如圖5-11所示。圖5-11求GF(24)元素電路開(kāi)始計(jì)算時(shí)電路的初始狀態(tài)置α=(10000)，每移位一次就在四級(jí)移存器中得到α2，α3，α4，…，α15，α，α2…。相應(yīng)地，輸出序列就是α，α2，α3，…，是一個(gè)周期為15的二進(jìn)制序列。該電路的運(yùn)算過(guò)程如表5-6所示。表5-6圖5-11

電路運(yùn)算表由此看出，移位寄存器每右移一次相當(dāng)于乘α(左移一次相當(dāng)于乘α-1)，15次移位后電路回到初始狀態(tài)，它的輸出序列顯然也以15個(gè)碼元為周期。由于用4級(jí)線性移存器所能產(chǎn)生的最長(zhǎng)序列的長(zhǎng)度為24-1=15，所以，這種用GF(2)上的m次本原多項(xiàng)式組成的除法電路(無(wú)輸入情況)，稱為最長(zhǎng)序列線性移存器電路，所產(chǎn)生的序列稱為m序列，它的周期是2m-1。3.計(jì)算R(xj)電路循環(huán)碼的譯碼電路中經(jīng)常要計(jì)算R(x)=r

n-1

x

n-1+r

n-2

x

n-2+…+r1x+r0的R(α)或R(αj)的值，式中，α是g(x)的根，g(α)=0。因?yàn)?/p>

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

所以

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

n-1，r

n-2，…，r1，r0)送入g(x)的除法電路中，最后在移存器中得到的余式就是R(α)。計(jì)算R(αj)比較麻煩。因?yàn)?，在GF(qm)上，每個(gè)元素αj(j=0，1，…，qm-2)用自然基表示時(shí)，都可表示成次數(shù)小于m次的α多項(xiàng)式，α∈GF(qm)是本原域元素，它是m次本原多項(xiàng)式的根。因此要計(jì)算R(αj)，首先必須把αj表示成次數(shù)小于m的α多項(xiàng)式表示?，F(xiàn)舉例說(shuō)明。例5.15計(jì)算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現(xiàn)在要求計(jì)算R(α5)，也就是

R(α5)=q(α5)g(α5)+r(α5)因?yàn)橐笤趃(x)除法電路中，每右移一次相當(dāng)于乘α5，為此必須先介紹乘α5電路。設(shè)原移存器的初始值為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次移位后就在該電路中的存貯器內(nèi)得到R(α5)。圖5-12GF(24)域上乘α5§5.7循環(huán)碼的編碼電路

一、n-k級(jí)編碼器n-k級(jí)編碼器有兩種：一是g(x)的乘法電路，另一是g(x)的除法電路。前者所編出的碼是非系統(tǒng)碼，后者是系統(tǒng)碼。

1.g(x)乘法電路編碼器由§5.1可知，［n，k］循環(huán)碼的編碼就是將k位長(zhǎng)的信息組m(x)=mk-1xk-1+mk-2xk-2+…+m1x+m0，編成長(zhǎng)為n的碼字C(x)。由循環(huán)碼理論可知，C(x)=m(x)g(x)，g(x)=n-k。因此可用g(x)乘法電路實(shí)現(xiàn)非系統(tǒng)碼編碼。

例5.16求GF(2)上［7，4］循環(huán)漢明碼編碼器。該碼的生成多項(xiàng)式g(x)=x3+x+1，由此可得圖5-13的n-k=3級(jí)乘法編碼器。設(shè)送入的信息組為1001，則編出的碼組是1010011，相應(yīng)的碼多項(xiàng)式

C(x)=(x3+1)(x3+x+1)=x6+x4+x+1圖5-13［7，4］循環(huán)漢明碼三級(jí)乘法編碼器

2.g(x)除法電路編碼器由式(5.1.6)和式(5.1.5)知，要得到系統(tǒng)碼必須首先將信息組m(x)乘以x

n-k，變成

x

n-km(x)，然后再用g(x)除，求得相應(yīng)的余式r(x)，把其系數(shù)取“-”號(hào)就得到了相應(yīng)的校驗(yàn)位，加上原來(lái)的信息組就組成了碼字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］系統(tǒng)碼編碼電路就是乘x

n-k除g(x)的電路。［7，4］循環(huán)漢明碼系統(tǒng)碼編碼電路如圖5-14所示。這種電路的工作過(guò)程如下：圖5-14［7，4］循環(huán)漢明碼系統(tǒng)碼編碼電路

(1)3級(jí)移存器的初始狀態(tài)全清為0，門1開(kāi)、門2關(guān)，然后進(jìn)行移位，送入信息組m(x)的系數(shù)，高次位系數(shù)首先進(jìn)入電路，它一方面經(jīng)或門輸出,一方面自動(dòng)乘以x

n-k=x3次后進(jìn)入g(x)除法電路，從而完成了

x

n-km(x)=x3m(x)的作用。(2)4次移位后m(x)全部送入電路，完成了除法作用，此時(shí)在移存器內(nèi)保留了余式r(x)的系數(shù)，在二進(jìn)制情況下就是校驗(yàn)元。

(3)此時(shí)門1關(guān)、門2開(kāi)，再經(jīng)過(guò)3次移位后，把移存器的校驗(yàn)元全部輸出，與原先的4位信息元組成了一個(gè)長(zhǎng)為7的碼字C(x)。(4)門1開(kāi)、門2關(guān)，送入第二組信息組重復(fù)上述過(guò)程。表5-7列出了圖5-14的編碼工作過(guò)程。輸入的信息組為1001，7次移位后輸出端得到已編好的碼組1001110。表5-7圖5-14電路的編碼過(guò)程

二、k級(jí)編碼器

［n，k］循環(huán)碼系統(tǒng)碼的編碼器，也可根據(jù)校驗(yàn)多項(xiàng)式h(x)=hkxk+hk-1

xk-1+…+h1x+h0構(gòu)造。設(shè)系統(tǒng)碼的碼多項(xiàng)式為

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位系數(shù)：c

n-1，c

n-2，…，c

n-k