第六章循環(huán)碼和BCH碼ppt課件

1、第六章循環(huán)碼與第六章循環(huán)碼與BCH碼碼第一節(jié)基本定義循環(huán)碼是線性分組碼中應(yīng)用最廣泛的一類碼。它有兩個(gè)重要的特點(diǎn)：1、碼的結(jié)構(gòu)可以用代數(shù)方法來表示、分析和構(gòu)造。2、利用循環(huán)特性，可以用循環(huán)反饋移位寄存器來構(gòu)造較為簡單方便的編碼器和譯碼器。循環(huán)碼：設(shè)循環(huán)碼：設(shè)C是碼長為是碼長為n，信息位為，信息位為k,監(jiān)督位監(jiān)督位為為r的的(n,k)線性分組碼的任意一個(gè)碼字，假設(shè)線性分組碼的任意一個(gè)碼字，假設(shè)C的每一次循環(huán)移位也是碼字，則把具有這種的每一次循環(huán)移位也是碼字，則把具有這種循環(huán)移位特點(diǎn)的碼稱為循環(huán)碼循環(huán)移位特點(diǎn)的碼稱為循環(huán)碼(Cyclic Codes)。即如果 C=cn-1, cn-2, c1, c0

2、是一個(gè)碼字 那么 C1=cn-2, cn-3, c0, cn-1 C2=cn-3, cn-4, cn-1, cn-2 Cn-1=c0, cn-1, c2, c1都是碼字例如，第五章中表5-2中所列的(7,3)碼，就是具有這種循環(huán)特性的循環(huán)碼。（P176）關(guān)于循環(huán)碼強(qiáng)調(diào)兩點(diǎn)：1、本書討論的循環(huán)碼首先是一個(gè)線性分組碼。2、循環(huán)碼具有循環(huán)移位特性。例6-1：判斷下面三組碼字的特點(diǎn)。000110011101000100011111000100010001C1=C2=C3=C1是線性循環(huán)碼，C2是非循環(huán)的線性分組碼，C3是非線性的循環(huán)碼。碼多項(xiàng)式與碼多項(xiàng)式與n重碼相對應(yīng)的重碼相對應(yīng)的n-1次多項(xiàng)式次多項(xiàng)

3、式C(x)=cn-1xn-1+ cn-2xn-2+ c1x+ c0 6-1稱為碼多項(xiàng)式。稱為碼多項(xiàng)式。例如：碼字C=0010111所對應(yīng)的碼多項(xiàng)式為C(x)=x4+ x2+ x+1 假如已知碼多項(xiàng)式C(x)=x7+ x3+ x+1，則可求出對應(yīng)的碼字C=10001011 首首一一多多項(xiàng)項(xiàng)式式 首項(xiàng)系數(shù)為 1 的多項(xiàng)式。 如 f(x)= x7+1。我們把多項(xiàng)式 f(x)的最高次數(shù)記為 0f(x)。 此處0f(x)7。 多多項(xiàng)項(xiàng)式式同同余余 它和數(shù)的同余類似。例如，用 x7+1 除x7+x6+x5x3 所得余式，和用x7+1 除 x6+x5x31 所得余數(shù)式相同，即：1xxxx11xxxxx713

4、5673567 我們就稱x7+x6+x5x3 和x6+x5x31 關(guān)于x7+1同余，并記為 x7+x6+x5x3x6+x5x31 mod(x7+1) 實(shí)際上，將(n,k)循環(huán)碼的一個(gè)碼字C=cn-1, cn-2, c1, c0 所對應(yīng)的碼多項(xiàng)式循環(huán)左移一位，即相當(dāng)于對碼多項(xiàng)式乘以x并除以xn+1后所得的余式，剛好是將碼字C循環(huán)移位一次后所得碼字(cn-2, cn-3, c0,cn-1)的碼多項(xiàng)式，即下面關(guān)系式成立： x(cn-1xn-1+ cn-2xn-2+ c1x+ c0) = cn-1xn+ cn-2xn-1+ c1x2+ cnx cn-2xn-1+ cn-3xn-2+ c1x2+ cnx

5、+ cn-1 mod(xn+1) (n,k)循環(huán)碼的每個(gè)碼字必處在以xn+1為模運(yùn)算的剩余類的某一類中。 生成多項(xiàng)式在生成多項(xiàng)式在(n,k)循環(huán)碼的循環(huán)碼的2k個(gè)個(gè)碼字中，取一個(gè)前碼字中，取一個(gè)前k-1位皆為位皆為0的碼的碼字，此碼字對應(yīng)有一個(gè)次數(shù)最低，字，此碼字對應(yīng)有一個(gè)次數(shù)最低，且為且為n-k=r的多項(xiàng)式的多項(xiàng)式g(x)，其它碼字，其它碼字所對應(yīng)的碼多項(xiàng)式都是所對應(yīng)的碼多項(xiàng)式都是g(x)的倍式，的倍式，則稱則稱g(x)生成該碼，并且稱生成該碼，并且稱g(x)為該為該碼的生成多項(xiàng)式。碼的生成多項(xiàng)式?？梢娚啥囗?xiàng)式具有以下特征：g(x)= xr+ gr-1xr-1 + + g2x2+ g1x+

6、 g0g0 0r=n-k 如果g(x)為(n,k)循環(huán)碼的最低次多項(xiàng)式，即 生成多項(xiàng)式時(shí)，xg(x), x2g(x), xk-1g(x)都是 碼字，這k個(gè)碼字是獨(dú)立的，故可作為碼的一 組生成基底，使每個(gè)碼多項(xiàng)式都是這一組基 底的線性組合。例如P176例5-1由此看來，找到合適的g(x)是構(gòu)造循環(huán)碼的關(guān)鍵。在這方面需要用到有限域的知識(shí)。第二節(jié)有限域中的運(yùn)算規(guī)則 運(yùn)算自封：一個(gè)集合中的元素經(jīng)過某種運(yùn)算例運(yùn)算自封：一個(gè)集合中的元素經(jīng)過某種運(yùn)算例如加減乘除后仍為集合中的元素時(shí)，稱為運(yùn)算如加減乘除后仍為集合中的元素時(shí)，稱為運(yùn)算自封。自封。 域：運(yùn)算自封元素的集合叫做域域：運(yùn)算自封元素的集合叫做域FFie

7、ld）。域中）。域中 的元素相加的元素相加a+b和相乘和相乘ab滿足下列關(guān)系：滿足下列關(guān)系：A0:對 a,bF,a+b=c 存在且 唯一，cF A1:(a+b)+c=a+(b+c) A2:b+a=a+b A3:域中有 0 元，且對任意 a 有 a+0=0aa A4:對任意 a 有負(fù)元存在且 a+(-a)=(-a)a0 M0:對 a,bF,a+b=c 存在且 唯一，cF M1:(ab)c=a(bc) M2:ba=ab M3:域中有 1 元，且對任意 a 有 a1=1aa M4:對任意 a0 有異元 a-1且 a a-1= a-1a1 D：滿足分配律a(b+c)=ab+ac,(a+b)c=ac+b

8、c 當(dāng)域中元素為有限數(shù)p時(shí)，稱為有限域或p元域，有限域理論是由數(shù)學(xué)家伽羅華Galols所創(chuàng)立的，因此又稱為伽羅華域，并記為GF(p)。 普通代數(shù)中全體有理數(shù)的集合叫有理域，全體實(shí)數(shù)的集合叫實(shí)數(shù)域。全體復(fù)數(shù)的集合叫復(fù)數(shù)域。它們都是無限域。 經(jīng)常用到的有限域是二元域GF(2)，它有兩個(gè)元素“0和“1”，其加法和乘法分別為：加法乘法0+000*000+110*101+011*001+101*11系數(shù)在GF(2)中的多項(xiàng)式叫做二元域上的多項(xiàng)式。二元域上多項(xiàng)式的加減乘除等運(yùn)算在原理上和普通代數(shù)多項(xiàng)式的運(yùn)算相同。例如：對碼字多項(xiàng)式C(x)=cn-1xn-1+ cn-2xn-2+ c1x+ c0有xi+ x

9、i0, ci+ ci0, ci2=ci . cici并且減法就是加法。加法符號(hào)為“”或簡記為“+”。證：因C2(x) (cn-1xn-1+ cn-2xn-2+ c1x+ c0) 2=(cn-1xn-1) 2+ 2cn-1xn-1( cn-2xn-2+ c1x+ c0) + (cn-2xn-2+ c1x+ c0) 2考慮到cn-1 2 cn-1，上式包括2作系數(shù)的第二項(xiàng)乘積為0，將第三項(xiàng)類似地逐步展開，就可以得出C2(x) cn-1x2(n-1)+ cn-2x2(n-2) + c1x 2 + c0=C(x2)例6-2試證明對上述二元域上碼多項(xiàng)式C(x),有C2(x) C(x2) 定理：設(shè)d(x)

10、和g(x)是二元域上的兩個(gè)多項(xiàng)式。則有唯一的一對二元域上的多項(xiàng)式q(x)和r(x)。具有下面的性質(zhì)： d(x)=q(x)g(x)+r(x) 其中r(x)的次數(shù)小于g(x)的次數(shù)，叫余式。 這個(gè)定理也稱歐幾里德(Euclid)除法定理。利用這種余式的唯一性質(zhì)，按某個(gè)次數(shù)為m的多項(xiàng)式g(x)的求余運(yùn)算，可以把所有多項(xiàng)式分為2m個(gè)剩余類。例如，m=3的三次多項(xiàng)式g(x)=1+x+x3有2m=23=8個(gè)剩余類0 x211+ x2x x+x21+x 1+x+x2 既約多項(xiàng)式既約多項(xiàng)式 又稱不可約多項(xiàng)式，它不能分又稱不可約多項(xiàng)式，它不能分解為次數(shù)更低的多項(xiàng)式的乘積，例如解為次數(shù)更低的多項(xiàng)式的乘積，例如x2

11、 +x + 1和和x4 +x +1為不可約多項(xiàng)式，而為不可約多項(xiàng)式，而x2+1不不是既約多項(xiàng)式。由于是既約多項(xiàng)式。由于(x+1)2= x2 +x+x + 1= x2 +1和普通代數(shù)一樣，對于多項(xiàng)式f(x),如果f(a)=0,則稱a為多項(xiàng)式的根，例如(x+1)2的根為1。顯然，既約多項(xiàng)式的根不能在二元域內(nèi)，但是可以像實(shí)數(shù)根擴(kuò)展到復(fù)數(shù)根那樣，將既約多項(xiàng)式的根在二元域的擴(kuò)充域中表示出來。以二次既約多項(xiàng)式1+x+x2為例，可以把二元域中的元“0和“1擴(kuò)充一位，表示成0(00),1=(01)。如果a是1+x+x2的根，則可令a=(10).。再由1+a+a20，可得a2 1+a=(01)+(10)=11這

12、樣就得到一個(gè)具有兩位數(shù)字的擴(kuò)域GF(4)，它包含0、1、a、 a2四個(gè)元。第三節(jié)循環(huán)碼多項(xiàng)式的基本特性循環(huán)碼多項(xiàng)式(6-1)具有如下一些特性： (一)C(x)經(jīng)過 i 次循環(huán)所得碼多項(xiàng)式 Ci(x),是用 xn+1 除 xiC(x)后所得的余式，即 xiC(x)q(x) (xn+1)+ Ci(x) 證：令 i=1,由(6-1)式顯然有 1)(1).)1(1).(1)(111021021121121nnnnnnnnnnxxCcxcxcxcxcxcxcxcxcxcxxxxCnnnn （當(dāng) i 大于 1 時(shí)，可類似推導(dǎo)） xiC(x)的次數(shù)等于或小于 n-1 時(shí)，則可以較簡單地直接寫出 Ci(x)x

13、iC(x) (二)在一個(gè)(n,k)循環(huán)碼中，有唯一的一個(gè)n-k次多項(xiàng)式g(x)= xn-k+ gn-k-1xn-k-1 + + g2x2+ g1x+ 1，每個(gè)為g(x)倍式的小于等于n-1次的多項(xiàng)式一定是碼多項(xiàng)式。反之，每一個(gè)碼多項(xiàng)式C(x)是g(x)的倍式。證：令r=n-k，由于g(x)= xr+ gr-1xr-1 + + g2x2+ g1x+ 1是(n,k)循環(huán)碼中次數(shù)最低的一個(gè)非零首多項(xiàng)式。由于碼的循環(huán)特性，xg(x), x2g(x), xn-1-rg(x)也必為碼多項(xiàng)式，從而它們的線性組合 (mn-1-rxn-1-r + + m2x2+ m1x+ m0 )g(x)=M(x) g(x)也

14、必在循環(huán)碼中，故每一個(gè)次數(shù)等于或小于n-1次的g(x)的倍式是碼多項(xiàng)式。反之，任意一個(gè)碼字的碼多項(xiàng)式Ci(x)，必定是最低的非零首多項(xiàng)式g(x)的倍式。因?yàn)椴蝗坏脑?，將Ci(x)用g(x)除之，將會(huì)出現(xiàn)余式b(x)，即Ci(x)a(x)g(x)+b(x)，由此，b(x)= Ci(x)+ a(x)g(x)為碼多項(xiàng)式Ci(x)和g(x)的線性組合，必定也是一個(gè)碼多項(xiàng)式。且其次數(shù)因其為余式低于g(x)。這和原來假設(shè)g(x)是碼多項(xiàng)式集合中次數(shù)最低的相矛盾，故b(x)=0,即Ci(x)是g(x)的倍式： Ci(x)a(x)g(x)設(shè)g(x)不是唯一的，即還有一個(gè)同次數(shù)的非零首多項(xiàng)式g(x)= xr+

15、gr-1xr-1 + + g2x2+ g1x+ 1則g(x)和g(x)的線性組合g(x) g(x)必定也是碼多項(xiàng)式，且由于首項(xiàng)相消，其次數(shù)小于g(x)的次數(shù),與g(x)是碼多項(xiàng)式中次數(shù)最低的矛盾。所以g(x) g(x)， g(x)是唯一的。(三)(n,k)循環(huán)碼的生成多項(xiàng)式g(x)是xn+1的因式，反之， 若g(x)是xn+1的一個(gè)n-k次因式，則g(x)生成(n,k)循環(huán)碼。證：因g(x)為n-k次，則xk g(x)為n次多項(xiàng)式，用xn+1除之， 由6-5式可得： xkg(x)xn+1+Ck(x)其中Ck(x)為碼多項(xiàng)式，總可以寫為g(x)的倍式形式， 即Ck(x)m(x)g(x)由此可以得

16、出xn+1 (xk+m(x)g(x)即g(x)是xn+1的一個(gè)因式。反之，當(dāng)g(x)為n-k次，則它的倍式的線性組合(m0 + m1x + m2x2 + mk-1xk-1) g(x)也是碼多項(xiàng)式， 系數(shù)m0 、 m1、 m2、 mk-1 共有2k種不同組合，正好 構(gòu)成(n,k)碼中k個(gè)信息元所形成的2k個(gè)碼多項(xiàng)式。 概括地說，要生成一個(gè)(n,k)循環(huán)碼，就是要找到一個(gè)能除盡xn+1的r=n-k次首生成多項(xiàng)式g(x),由g(x)來生成各個(gè)碼多項(xiàng)式后，找出與碼多項(xiàng)式相對應(yīng)的循環(huán)碼字。第四節(jié)循環(huán)碼的編碼方法由上節(jié)已經(jīng)知道，低于 n 次的多項(xiàng)式 C(x)是一個(gè)由除盡 xn+1的 r=n-k次首多項(xiàng)式

17、g(x)生成的(n,k)循環(huán)碼的一個(gè)碼字的充分必要條件是 C(x) 0 modg(x) 對長為 k 位的任意消息組 M=(mk-1, m1,m0)，其對應(yīng)的消息多項(xiàng)式為 M(x)=mk-1xk-1+ m1x+m0 可乘以 g(x)而構(gòu)成 n-1 次的碼多項(xiàng)式 C(x)=M(x)g(x)=(mk-1xk-1+ m1x+ m0 )g(x) 或 xk-1g(x) C(x)=mk-1, m1,m0 xg(x) = MG(x) g(x)式中G(x)為循環(huán)碼的生成矩陣，其k行分別由g(x)循環(huán)移位而成。但是這樣編成的循環(huán)碼不是系統(tǒng)碼。如要編成前k位是信息元，后r=n-k位是監(jiān)督元的n位系統(tǒng)碼，可以先用xn

18、-k乘消息多項(xiàng)式M(x)，再用g(x)去除，即)()()()()(xgxrxqxgxMxkn其中q(x)是商式，r(x)是次數(shù)小于n-k的余式。于是C(x)=xn-kM(x)+r(x)=g(x)q(x)是g(x)的倍式，因而是由g(x)生成(n,k)循環(huán)碼的碼多項(xiàng)式。如果令如果令M(X)為單項(xiàng)式為單項(xiàng)式xk-ii=0,1,2k-1則則Ci(x)=x + r (x)n-ii可以容易看到碼多項(xiàng)式可以容易看到碼多項(xiàng)式Ci(x)對應(yīng)的碼字或向量），對應(yīng)的碼字或向量），i=0,1,2k-1是線性無關(guān)的，所以這是線性無關(guān)的，所以這K個(gè)碼多項(xiàng)式組成個(gè)碼多項(xiàng)式組成了循環(huán)碼的系統(tǒng)生成矩陣。了循環(huán)碼的系統(tǒng)生成矩陣

19、。系統(tǒng)循環(huán)碼的生成矩陣為： xn-1 + rn-1(x) xn-2 + rn-2(x)C(x)= xn-k+1 + rn-k+1(x) xn-k + rn-k(x)式中rn-i(x)為xn-i除以g(x)后所得的余式。是g(x)的倍式，因而是由g(x)生成(n,k)循環(huán)碼的碼多項(xiàng)式。 解：由于n=7時(shí) x7+1=(x+1)(x3+x+1)(x3+x2+1) 6-14如選用g(x)= x3+x+1，并考慮到M=1101-M(x)= x3+x2+1即此處余式r(x)=1，由6-13得出C(x)=x3(x3+x2+1)+1= x6+x5+x3+1由此得出對應(yīng)于消息1101的碼字為1101001。11

20、11)1()()(3233233xxxxxxxxxxxgxMxkn例6-2將消息M=1101編成(7,4)循環(huán)漢明碼解：從6-14中取次數(shù)為n-k=4的g(x)，即取 g(x)=(x+1)(x3+x+1)=x4+x3+x2+1因M=101-M(x)= x2+1故此多項(xiàng)式為C(x)=x4(x2+1)+x+1= x6+x4+x+1由此得出對應(yīng)的編成碼字為1010011。1111)1()()(234223424xxxxxxxxxxxxgxMxkn例6-3將消息M=101編成(n,k)=(7,3)循環(huán)碼由上面例子可以看出，從xn+1中取不同的n-k次因式作g(x),就得出不同(n,k)循環(huán)碼。一般可寫

21、為xn+1 =h(x)g(x) 或)1mod(0)()(nxxgxh其中h(x)稱為監(jiān)督多項(xiàng)式，次數(shù)為k。例如，由x7+1就可以構(gòu)成如表6-3所示不同k值的循環(huán)碼。由x7+1的因式構(gòu)成(7,3)循環(huán)碼 表6-3(n,k)碼 碼距d 生成多項(xiàng)式g(x) 監(jiān)督多項(xiàng)式h(x)(7,6) 2 x+1 (x3+x+1)(x3+x2+1)(7,4) 3 x3+ x+1 (x+1)(x3+x2+1) 3 x3+ x2 +1 (x+1)(x3+x+1)(7,3) 4 (x+1)(x3+x+1) x3+x2+1 4 (x+1)(x3+ x2 +1) x3+x+1(7,1) 7 (x3+x+1)(x3+x2+1)

22、 x+1第五節(jié)循環(huán)碼的編碼電路 上一節(jié)已介紹，(n,k)循環(huán)碼的編碼，可以化為用g(x)去除 xn-kM(x)求余式r(x)的問題。在實(shí)際編碼技術(shù)中，這個(gè)相除是用除法電路來實(shí)現(xiàn)的。 一、多項(xiàng)式除法電路 我們先來分析一下例6-3中除法運(yùn)算112112342223446xxxxxxxxxxxx 為了完成這個(gè)計(jì)算步驟，可以根據(jù)除式的次數(shù)r(此處r4)，設(shè)置r級移位寄存器(圖6-1)，并在移位寄存器的某些位置(這些位置由除式中系數(shù)不為零的項(xiàng)來決定)上，加上按模二相加的反饋連結(jié)線。D0D1輸 出輸 入圖6-1除式為x4+x3+x2+1的除法電路D2D3 表6-4中列出圖6-1除法電路在各次移位后的狀態(tài)。

23、在移位脈沖7后，寄存器D0與D1中的存數(shù)均為1，表明余式為1+x。 除法電路中的狀態(tài)表6-4由圖6-1和表6-4可以看出除法電路的特點(diǎn)：1、除法電路中移位寄存器的級數(shù)等于除法的次數(shù)；2、除式的非零系數(shù)對應(yīng)著移位寄存器的反饋抽頭；3、為了求余式，總的移位次數(shù)等于倍除式次數(shù)加1。二、自動(dòng)乘xr的除法電路 從表6-4中可以看出，在第一次到第四次移位過程中，除法電路中只是接收輸入的x6、 x5、 x4、 x3的系數(shù)，只在第五次移位時(shí)才真正開始運(yùn)算。為了節(jié)省時(shí)間，可以將圖6-1改為圖6-2的形式，此時(shí)被除數(shù)M(x)不是從D0的輸入端輸入，而是從D2的輸出端輸入。因此，它相當(dāng)于被除數(shù)M(x)自動(dòng)乘x4以后

24、再送入除法電路。D0D1輸出圖6-2自動(dòng)乘xr的除法電路D2D3輸入x4M (x)這種電路的運(yùn)算結(jié)果表示在表6-5中，由表中可以看出，只要經(jīng)過三次移位，就完成了除法運(yùn)算， D0、 D1、 D2、D3 中的存數(shù)1100，就是余式中x0、 x1、 x2、 x3的各次系數(shù)。三、編碼電路 前面已經(jīng)談到，(n,k)循環(huán)碼的編碼方法，是從xn+1的因式中找到一個(gè)(n-k)次的生成多項(xiàng)式g(x)，然后將與輸入消息相對應(yīng)的消息多項(xiàng)式M(x)乘xn-k，被g(x)除之，得出余式r(x),并將其附在xn-k M(x)之后，就構(gòu)成碼多項(xiàng)式C(x) 。所有它的編碼器就是一個(gè)將M(x)自動(dòng)乘以xn-k的g(x)除法電路

25、，加上幾個(gè)控制門而成。 下面以g(x)x3+x+1的(7,4)循環(huán)漢明碼的編碼電路為例加以說明。 設(shè)輸入消息M=1100，則M(x)x3+ x2 ，于是xn-k M(x) x3(x3+ x2 )= x6+ x5，它被g(x)除后，余式為r(x)=x，即監(jiān)督位為010，相應(yīng)的碼多項(xiàng)式為C(x) = x6+ x5+x，從而編成的碼字為1100010。其編碼電路如圖6-3所示。D0D1輸出圖6-3g(x)x3+x+1的(7,4)循環(huán)漢明碼編碼器D2門1輸入x3M (x)門2運(yùn)算過程表示在表6-6中。其中虛線方框中010表示余式x. 首先門1斷開，門2接通，用自動(dòng)乘xn-k=x3的方式輸入M(x)。當(dāng)

26、移位4次后，4個(gè)信息元已全部送入除法電路和信道。除法電路已完成除法運(yùn)算，得到r=n-k=3個(gè)余數(shù)項(xiàng)010，存儲(chǔ)在D0 、D1 、D2, 中。這時(shí)門1接通，門2斷開，把移位寄存器中的三個(gè)存數(shù)作為監(jiān)督元附在四個(gè)信息元后送入信道，從而完成整個(gè)碼字的編碼過程。因此，編出的是系統(tǒng)碼。第六節(jié) 循環(huán)碼的譯碼電路設(shè)發(fā)送碼多項(xiàng)式為C(x)=cn-1xn-1+ cn-2xn-2+ + c1x+ c0 接收碼多項(xiàng)式為R(x)=rn-1xn-1+ rn-2xn-2+ + r1x+ r0由于信道干擾的影響， 發(fā)送碼與接收碼間有差別，構(gòu)成錯(cuò)誤圖樣碼多項(xiàng)式E(x)= R(x) - C(x) =en-1xn-1+ en-2x

27、n-2+ + e1x+ c0 由于正確的碼多項(xiàng)式C(x)總是能被生成多項(xiàng)式所整除，用生成多項(xiàng)式g(x)除接收碼多項(xiàng)式R(x)所得的余式(稱位伴隨式S(x),與用g(x)除E(x)所得的余式是相同的，即)(mod)()(xgxSxE通常，如果用g(x)去除接收碼多項(xiàng)式R(x)，得到的伴隨式S(x)0,與說明R(x)0， R(x)C(x)，沒有錯(cuò)誤。如果所得的余式是相同的，即S(x)0, 則E(x)0,說明有錯(cuò)誤。一、自發(fā)運(yùn)算電路 在譯碼電路中，要用到自發(fā)運(yùn)算電路的概念。 下面用熟悉的x7+1的一個(gè)本原多項(xiàng)因式g(x)=x3+x+1為例子來說明。圖6-4為此多項(xiàng)式的除法電路。它沒有輸入電路，完全按

28、D0 、D1 、D2中的初始狀態(tài)進(jìn)行移位來決定電路的狀態(tài)。顯然，對于全零的初始狀態(tài)000，無論移多少次后，移存器的狀態(tài)始終為0?，F(xiàn)設(shè)D0 D1 D2的初始狀態(tài)為100，移位；一次變?yōu)?10。再移位一次變?yōu)?01，連續(xù)移位的狀態(tài)變化如表6-7所示。D0D1圖6-4g(x)x3+x+1的自發(fā)運(yùn)算電路D2 可以看出，經(jīng)過7次循環(huán)移位后，返回到原來初始狀態(tài)(圖6-5)。一般說來，用一個(gè)m次本原多項(xiàng)式g(x)作成的除法電路，在初始狀態(tài)不全為0和無輸入的條件下，將輸出一個(gè)周期的2m-1的最長二進(jìn)制循環(huán)序列。稱為m序列，其電路稱為m序列產(chǎn)生器。 從表6-7還可以看出，移寄存器的每一個(gè)狀態(tài)，與單個(gè)錯(cuò)誤圖樣被E

29、(x) g(x)除后所得的余式即伴隨式S(x)之間，有著一一對應(yīng)的關(guān)系。且每移位一次，相當(dāng)于錯(cuò)誤圖樣的次數(shù)升高一次。例如，001相當(dāng)于E(x) x2 的伴隨式，而110相當(dāng)于E(x) x2 x+1(mod g(x)的伴隨式。 因此，若用Si 代表 xi被g(x)除后所得的余式，則j次移位后的伴隨式Si+j 是xi+j被g(x)除后所得的余式，它對應(yīng)于Si 的狀態(tài)在自發(fā)運(yùn)算電路中循環(huán)移位j次后所得的狀態(tài)，即 Si+j (x) = xjSi (x) mod g(x) 特別值得提出的是，對應(yīng)于在第i位發(fā)生錯(cuò)誤時(shí)，E(x)=xi,其伴隨式為Si(x),當(dāng) Si(x)在自發(fā)運(yùn)算電路中運(yùn)算移位7-i次后，

30、伴隨式變?yōu)閤7-iSi (x) = Si-7-i (x) = S7 (x) = S0 (x) 這就是說，對于任何i狀態(tài)，經(jīng)過7-i次移位后，總能使移存器的狀態(tài)變?yōu)殚_始的100狀態(tài)，這個(gè)特點(diǎn)將要在下面的譯碼電路中用到。二、糾正一位錯(cuò)誤的(7,4)碼譯碼電路譯碼電路由I，II,III部分構(gòu)成(圖6-6)。D0D1圖6-6糾正一位錯(cuò)誤的(7,4)碼譯碼電路D2控制門IR(X)D0D1D2與門E(X)C(X)R(X)反相7級移位寄存器IIIII 第一部分為g(x)=x3+x+1除法電路計(jì)算伴隨式S(x)部分，接收到的R(x)一方面送入除法電路，一方面進(jìn)入第III部分的7級移位寄存器。當(dāng)R(x)全部移入

31、7級移位寄存器時(shí)，除法電路經(jīng)7次運(yùn)算后得到S(x)。若S(x)為零，則D0 、D1 、 D2 的狀態(tài)為000，說明接收到的碼多項(xiàng)式R(x)沒有錯(cuò)誤，否則有錯(cuò)。有錯(cuò)時(shí)需通過第II部分自發(fā)運(yùn)算電路找到發(fā)生錯(cuò)誤的碼位，以模二方式加上一個(gè)“1以糾正該位錯(cuò)誤。 要注意到接收碼R(x)和發(fā)送碼C(x)都是高次位先行，伴隨式Si相應(yīng)于錯(cuò)誤圖樣 xi，如從先行的高次位來計(jì)算該位的位置次序，則認(rèn)為是第7-i位有錯(cuò)。 利用控制門將Si送入第II部分自發(fā)運(yùn)算電路。與此同時(shí)，第I部分除法電路繼續(xù)接收R(x)的下一組碼元。第III部分7級移位寄存器一方面送出前一組碼元，一方面接收另一組R(x)碼元。 Si在自發(fā)電路中經(jīng)

32、過7-i次后變?yōu)镾0100。 D0中的“1經(jīng)過反相變成“0后，與D1、 D2中的“0構(gòu)成或非門的全0輸入，使其開通，輸出一個(gè)“1”。此時(shí)7級移位寄存器正好移了7-i次，剛好移至第i位，把待糾錯(cuò)的那一位送到輸出端，和或非門的輸出“1模二相加，使該碼元變反，從而完成了糾錯(cuò)。 例如，當(dāng)Si = S2 ,相當(dāng)于x2有錯(cuò)，從高次算起則是第7-25位有錯(cuò)。 D0D1D2的狀態(tài)為001，經(jīng)過自發(fā)運(yùn)算電路移位運(yùn)算5次后變?yōu)?00，這時(shí)與門開通，輸出一個(gè)“1”，和7級移存器的第5位(即x2位)碼元進(jìn)行模二相加，從而糾正該位錯(cuò)誤。第七節(jié)BCH碼 以發(fā)現(xiàn)著命名的BCH(Bose-Chaudhurl-Hocqueng

33、hem)碼，是自1959年發(fā)展起來的一種能糾正多位錯(cuò)誤的循環(huán)碼。由于碼的生成多項(xiàng)式與碼的最小距離有關(guān)，容易根據(jù)糾錯(cuò)能力要求來直接確定碼的構(gòu)造，因此，它是一類應(yīng)用廣泛的差錯(cuò)控制碼。一、最小多項(xiàng)式 令是GF(2m)中的一個(gè)元素，某個(gè)形成循環(huán)周期并對的所有根均滿足m()=0的最低多項(xiàng)式m(x),稱為的最小多項(xiàng)式。 這個(gè)最小多項(xiàng)式是既約的。而且根據(jù)(6-3)可知，當(dāng)為m(x)的根時(shí)， 2, 4，8，也比是m(x)的根。 以GF(24)為例，當(dāng)有根a時(shí),則a,a2,a22=a4, a23=a8,均為根(a24=a16 =a不是新根)。因此，包括全部根的最小多項(xiàng)式為 mi(x)=(x+a)(x+a2) (

34、x+a4) (x+a8) =x4+ x3 (a+a2 +a4 +a8)+ x2(a3 +a5+a9 +a6+a10 +a12) +x(a14 +a13+a11 +a7) +a15利用GF(24)域中a4+a +1=0所生成的元素表(表6-1)，可以將上式簡化為mi(x)= x4+x +1當(dāng)a3 時(shí)，則2 a6 ， 22 a12， 23 a24 a9 ，均為根(24 a48 a3 不是新根)。因此，類似地得到m3(x)=(x+a3) (x+a5) (x+a9) (x+a12)=x4+ x3 + x2 +x+1同理a5 時(shí)，則2 a10 也為根(4 a24 a5 不是新根)。因此m5(x)=(x+

35、a5) (x+a10) = x2 +x+1由于x16 +1(x+1)(x2 +x+1)(x4+x+1)(x4+ x3 +1)(x4+ x3 + x2 +x+1)所以m1(x)， m3(x)， m5(x)都是x15 +1 x24-1 +1的一個(gè)既約因式。二、碼的主要特征 對于任何正整數(shù)m和t(m=3,t2m-1)，存在著能糾正t個(gè)以內(nèi)錯(cuò)誤的BCH碼，其參數(shù)為： 碼長：n= 2m-1 (6-25) 監(jiān)督元位數(shù)：n-k=2t+1 (6-27) 其生成多項(xiàng)式g(x)為GF(2m)上最小多項(xiàng)式m1(x), m2(x), ,m2t(x)的最小公倍式，即 g(x)=LCMm1(x), m2(x), ,m2t

36、(x) (6-28) 或者，考慮到m2(x)的根包括在m1(x)內(nèi), m6(x)的根包括在m2(x)內(nèi)，也就是一般來說，a2i的最小多項(xiàng)式m2i(x)和ai的最小多項(xiàng)式mi(x)一樣，偶數(shù)下標(biāo)項(xiàng)可一律取消，于是(6-28)可進(jìn)一步簡化為 g(x)=LCMm1(x), m3(x), ,m2t-1(x) (6-29) 為了證明(6-28)或(6-29)所選取的生成多項(xiàng)式g(x)能夠生成最小碼距d滿足(6-27)的BCH碼，參照第五章第五節(jié)介紹碼的監(jiān)督矩陣時(shí)，曾經(jīng)談到一個(gè)最小碼距為d的碼，在其監(jiān)督矩陣H中，任意少于等于d-1列必須是線性無關(guān)，也就是H中任意少于等于d-1列相加的和均不應(yīng)該等于零。下面

37、就來證明，生成多項(xiàng)式g(x)按(6-28)的形式選取，其監(jiān)督矩陣H中任取d-1列所構(gòu)成的行列式的值不等于0，從而滿足d-1列線性無關(guān)的要求。 實(shí)際上，由于d=2t+1,(6-28)又可以表示為 g(x)=LCMm1(x), m2(x), ,md(x) (6-30) 式中包括了由1至d-1的最小多項(xiàng)式，因此a1, a2, ad-1均為g(x)的根，從而也比為任一碼多項(xiàng)式的根。設(shè)任一碼多項(xiàng)式為 C(x)= cn-1 xn-1+ c2 x2+ c1 x+ c0 將根a1,a2, ad-1依次代入后，將構(gòu)成下列聯(lián)立方程組 cn-1 an-1+ c2 a2+ c1 a+ c00 cn-1(a2)n-1+

38、 c2 (a2) 2+ c1 a2+ c00 cn-1(ad-1)n-1+ c2 (ad-1) 2+ c1 ad-1 + c00或?qū)憺镠XT=OT的形式 cn-1 an-1 a2 a1 0 (a2)n-1(a2) 2a21 c2 = 0 c1 (ad-1)n-1(ad-1) 2 ad-1 1 c0 0即監(jiān)督矩陣為 an-1 a2 a1H= (a2)n-1(a2) 2a21 (ad-1)n-1(ad-1) 2 ad-1 1H中共有n列，現(xiàn)在證明，任取其中d-1列，它們的行列式之值也不會(huì)為0。設(shè)選取第i1, i2, ,id-1列，令1 ai1, 2 ai2, i-1 aii-1, 則有 1 2 d

39、-1 H i1i2id-1 = 12 22 d-12 1d-1 2d-1 d-1d-1 1 1 1=12i-1 1 2 i-1 . 1d-2 2d-2 d-1d-2=12i-1Hv而 1 1 1Hv=1 2 i-1 . 1d-2 2d-2 d-1d-2 為熟知的范德蒙德矩陣(Vandermonde Matrix)。它的行列式值已知為 因此，H中任取的d-1列線性無關(guān)，從而保證碼字中有最小的重量d，也就是最小碼距為d，故得所證。0)(112jiijidIJiIIII例6-4求長度n=15的BCH碼的生成多項(xiàng)式，它們能分別糾正1個(gè)，2個(gè)，3個(gè)錯(cuò)誤。解：糾正1個(gè)錯(cuò)誤，此時(shí)t=1,由(6-21)知g(

40、x)=LCMm1(x)=mi(x)= x4+x +1(10011)此處d=3,d0 g(x)=4=n-k,故k=15-4=11,即為(n,k,d)=(15,11,3)碼糾正2個(gè)錯(cuò)誤，此時(shí)t=2,由(6-22)知g(x)=LCMm1(x), m3(x)= (x4+x +1) (x4+ x3 + x2 +x+1)=(x8+ x7 + x6 +x4+1)(111010001)此處d=5,d0 g(x)=4=n-k,故k=15-8=7,即為(n,k,d)=(15,7,5)碼糾正3個(gè)錯(cuò)誤，此時(shí)t=3,由(6-23)知g(x)=LCMm1(x), m2(x) , m3(x)= (x4+x +1) (x4+

41、 x3 + x2 +x+1) (x2+x +1) =(x10+ x8+ x5 + x4 +x2+x+1)(10100110111)此處d=7,d0 g(x)=10=n-k,故k=15-10=5,即為(n,k,d)=(15,5,7)碼從本例中看出，(15,11,3)BCH碼就是糾正一位錯(cuò)誤的漢明碼。一般而言，對任何m=3.長度為n=2m-1的漢明碼，就是糾正單個(gè)錯(cuò)誤的，長度為n=2m-1的BCH碼。碼長n=2m-1(m=3,4,5,6)的漢明碼的生成多項(xiàng)式列在表6-8中。由表中可以看出，漢明碼的生成多項(xiàng)式都是m次本原多項(xiàng)式，因此屬于本原BCH碼。三、戈雷碼 前面討論的生成多項(xiàng)式g(x)包含本原元

42、a的根的BCH碼，稱為本原BCH碼。還有一種非本原BCH碼，它的生成多項(xiàng)式g(x)不含有本原元的根，它的碼長n也不等于2m-1，而是2m-1的一個(gè)因子。 著名的戈雷碼(Golay Code)，是一個(gè)二元域內(nèi)唯一已知的能糾正多位錯(cuò)誤的完備碼，它的碼參數(shù)為(n,k,d)=(23,12,7),生成多項(xiàng)式為 g1(x) =x11+ x10+ x6+ x5 + x4 +x2+1 或g2(x) =x11+ x9+ x7+ x6 + x5 +x+1 g1(x)和g2(x) 都是x23+1的因式，且非本原多項(xiàng)式。 x23+1(x+1) g1(x)g2(x) 它的碼長(n=23)不等于2m-1 223-12047，而是2047的一個(gè)因子，即23*892047，因此，它屬于非本原BCH碼。 顯然，戈雷碼的11個(gè)監(jiān)督元被最充分地用來監(jiān)督碼字中三個(gè)以內(nèi)的所有錯(cuò)誤狀態(tài)，即： 211C(23,0)+C(23,1)+C(23,2)+C(23,3) 因而它是一種性能很好的完備碼，在理論研究和