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

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

2、是一個碼字 那么 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）關于循環(huán)碼強調兩點：1、本書討論的循環(huán)碼首先是一個線性分組碼。2、循環(huán)碼具有循環(huán)移位特性。例6-1：判斷下面三組碼字的特點。000110011101000100011111000100010001C1=C2=C3=C1是線性循環(huán)碼，C2是非循環(huán)的線性分組碼，C3是非線性的循環(huán)碼。碼多項式與碼多項式與n重碼相對應的重碼相對應的n-1次多項式次多項

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

4、5673567 我們就稱x7+x6+x5x3 和x6+x5x31 關于x7+1同余，并記為 x7+x6+x5x3x6+x5x31 mod(x7+1) 實際上，將(n,k)循環(huán)碼的一個碼字C=cn-1, cn-2, c1, c0 所對應的碼多項式循環(huán)左移一位，即相當于對碼多項式乘以x并除以xn+1后所得的余式，剛好是將碼字C循環(huán)移位一次后所得碼字(cn-2, cn-3, c0,cn-1)的碼多項式，即下面關系式成立： 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)碼的每個碼字必處在以xn+1為模運算的剩余類的某一類中。 生成多項式在生成多項式在(n,k)循環(huán)碼的循環(huán)碼的2k個個碼字中，取一個前碼字中，取一個前k-1位皆為位皆為0的碼的碼字，此碼字對應有一個次數(shù)最低，字，此碼字對應有一個次數(shù)最低，且為且為n-k=r的多項式的多項式g(x)，其它碼字，其它碼字所對應的碼多項式都是所對應的碼多項式都是g(x)的倍式，的倍式，則稱則稱g(x)生成該碼，并且稱生成該碼，并且稱g(x)為該為該碼的生成多項式。碼的生成多項式?？梢娚啥囗検骄哂幸韵绿卣鳎篻(x)= xr+ gr-1xr-1 + + g2x2+ g1x+

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

7、ld）。域中）。域中 的元素相加的元素相加a+b和相乘和相乘ab滿足下列關系：滿足下列關系：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 有負元存在且 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 當域中元素為有限數(shù)p時，稱為有限域或p元域，有限域理論是由數(shù)學家伽羅華Galols所創(chuàng)立的，因此又稱為伽羅華域，并記為GF(p)。 普通代數(shù)中全體有理數(shù)的集合叫有理域，全體實數(shù)的集合叫實數(shù)域。全體復數(shù)的集合叫復數(shù)域。它們都是無限域。 經(jīng)常用到的有限域是二元域GF(2)，它有兩個元素“0和“1”，其加法和乘法分別為：加法乘法0+000*000+110*101+011*001+101*11系數(shù)在GF(2)中的多項式叫做二元域上的多項式。二元域上多項式的加減乘除等運算在原理上和普通代數(shù)多項式的運算相同。例如：對碼字多項式C(x)=cn-1xn-1+ cn-2xn-2+ c1x+ c0有xi+ x

9、i0, ci+ ci0, ci2=ci . cici并且減法就是加法。加法符號為“”或簡記為“+”。證：因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ù)的第二項乘積為0，將第三項類似地逐步展開，就可以得出C2(x) cn-1x2(n-1)+ cn-2x2(n-2) + c1x 2 + c0=C(x2)例6-2試證明對上述二元域上碼多項式C(x),有C2(x) C(x2) 定理：設d(x)

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

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

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

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

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

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

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

17、g(x)生成的(n,k)循環(huán)碼的一個碼字的充分必要條件是 C(x) 0 modg(x) 對長為 k 位的任意消息組 M=(mk-1, m1,m0)，其對應的消息多項式為 M(x)=mk-1xk-1+ m1x+m0 可乘以 g(x)而構成 n-1 次的碼多項式 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乘消息多項式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)碼的碼多項式。如果令如果令M(X)為單項式為單項式xk-ii=0,1,2k-1則則Ci(x)=x + r (x)n-ii可以容易看到碼多項式可以容易看到碼多項式Ci(x)對應的碼字或向量），對應的碼字或向量），i=0,1,2k-1是線性無關的，所以這是線性無關的，所以這K個碼多項式組成個碼多項式組成了循環(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)碼的碼多項式。 解：由于n=7時 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由此得出對應于消息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故此多項式為C(x)=x4(x2+1)+x+1= x6+x4+x+1由此得出對應的編成碼字為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)督多項式，次數(shù)為k。例如，由x7+1就可以構成如表6-3所示不同k值的循環(huán)碼。由x7+1的因式構成(7,3)循環(huán)碼 表6-3(n,k)碼 碼距d 生成多項式g(x) 監(jiān)督多項式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)的問題。在實際編碼技術中，這個相除是用除法電路來實現(xiàn)的。 一、多項式除法電路 我們先來分析一下例6-3中除法運算112112342223446xxxxxxxxxxxx 為了完成這個計算步驟，可以根據(jù)除式的次數(shù)r(此處r4)，設置r級移位寄存器(圖6-1)，并在移位寄存器的某些位置(這些位置由除式中系數(shù)不為零的項來決定)上，加上按模二相加的反饋連結線。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可以看出除法電路的特點：1、除法電路中移位寄存器的級數(shù)等于除法的次數(shù)；2、除式的非零系數(shù)對應著移位寄存器的反饋抽頭；3、為了求余式，總的移位次數(shù)等于倍除式次數(shù)加1。二、自動乘xr的除法電路 從表6-4中可以看出，在第一次到第四次移位過程中，除法電路中只是接收輸入的x6、 x5、 x4、 x3的系數(shù)，只在第五次移位時才真正開始運算。為了節(jié)省時間，可以將圖6-1改為圖6-2的形式，此時被除數(shù)M(x)不是從D0的輸入端輸入，而是從D2的輸出端輸入。因此，它相當于被除數(shù)M(x)自動乘x4以后

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

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

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

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

28、D0 、D1 、D2中的初始狀態(tài)進行移位來決定電路的狀態(tài)。顯然，對于全零的初始狀態(tài)000，無論移多少次后，移存器的狀態(tài)始終為0?，F(xiàn)設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ā)運算電路D2 可以看出，經(jīng)過7次循環(huán)移位后，返回到原來初始狀態(tài)(圖6-5)。一般說來，用一個m次本原多項式g(x)作成的除法電路，在初始狀態(tài)不全為0和無輸入的條件下，將輸出一個周期的2m-1的最長二進制循環(huán)序列。稱為m序列，其電路稱為m序列產(chǎn)生器。 從表6-7還可以看出，移寄存器的每一個狀態(tài)，與單個錯誤圖樣被E

29、(x) g(x)除后所得的余式即伴隨式S(x)之間，有著一一對應的關系。且每移位一次，相當于錯誤圖樣的次數(shù)升高一次。例如，001相當于E(x) x2 的伴隨式，而110相當于E(x) x2 x+1(mod g(x)的伴隨式。 因此，若用Si 代表 xi被g(x)除后所得的余式，則j次移位后的伴隨式Si+j 是xi+j被g(x)除后所得的余式，它對應于Si 的狀態(tài)在自發(fā)運算電路中循環(huán)移位j次后所得的狀態(tài)，即 Si+j (x) = xjSi (x) mod g(x) 特別值得提出的是，對應于在第i位發(fā)生錯誤時，E(x)=xi,其伴隨式為Si(x),當 Si(x)在自發(fā)運算電路中運算移位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)，這個特點將要在下面的譯碼電路中用到。二、糾正一位錯誤的(7,4)碼譯碼電路譯碼電路由I，II,III部分構成(圖6-6)。D0D1圖6-6糾正一位錯誤的(7,4)碼譯碼電路D2控制門IR(X)D0D1D2與門E(X)C(X)R(X)反相7級移位寄存器IIIII 第一部分為g(x)=x3+x+1除法電路計算伴隨式S(x)部分，接收到的R(x)一方面送入除法電路，一方面進入第III部分的7級移位寄存器。當R(x)全部移入

31、7級移位寄存器時，除法電路經(jīng)7次運算后得到S(x)。若S(x)為零，則D0 、D1 、 D2 的狀態(tài)為000，說明接收到的碼多項式R(x)沒有錯誤，否則有錯。有錯時需通過第II部分自發(fā)運算電路找到發(fā)生錯誤的碼位，以模二方式加上一個“1以糾正該位錯誤。 要注意到接收碼R(x)和發(fā)送碼C(x)都是高次位先行，伴隨式Si相應于錯誤圖樣 xi，如從先行的高次位來計算該位的位置次序，則認為是第7-i位有錯。 利用控制門將Si送入第II部分自發(fā)運算電路。與此同時，第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構成或非門的全0輸入，使其開通，輸出一個“1”。此時7級移位寄存器正好移了7-i次，剛好移至第i位，把待糾錯的那一位送到輸出端，和或非門的輸出“1模二相加，使該碼元變反，從而完成了糾錯。 例如，當Si = S2 ,相當于x2有錯，從高次算起則是第7-25位有錯。 D0D1D2的狀態(tài)為001，經(jīng)過自發(fā)運算電路移位運算5次后變?yōu)?00，這時與門開通，輸出一個“1”，和7級移存器的第5位(即x2位)碼元進行模二相加，從而糾正該位錯誤。第七節(jié)BCH碼 以發(fā)現(xiàn)著命名的BCH(Bose-Chaudhurl-Hocqueng

33、hem)碼，是自1959年發(fā)展起來的一種能糾正多位錯誤的循環(huán)碼。由于碼的生成多項式與碼的最小距離有關，容易根據(jù)糾錯能力要求來直接確定碼的構造，因此，它是一類應用廣泛的差錯控制碼。一、最小多項式 令是GF(2m)中的一個元素，某個形成循環(huán)周期并對的所有根均滿足m()=0的最低多項式m(x),稱為的最小多項式。 這個最小多項式是既約的。而且根據(jù)(6-3)可知，當為m(x)的根時， 2, 4，8，也比是m(x)的根。 以GF(24)為例，當有根a時,則a,a2,a22=a4, a23=a8,均為根(a24=a16 =a不是新根)。因此，包括全部根的最小多項式為 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當a3 時，則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 時，則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的一個既約因式。二、碼的主要特征 對于任何正整數(shù)m和t(m=3,t2m-1)，存在著能糾正t個以內錯誤的BCH碼，其參數(shù)為： 碼長：n= 2m-1 (6-25) 監(jiān)督元位數(shù)：n-k=2t+1 (6-27) 其生成多項式g(x)為GF(2m)上最小多項式m1(x), m2(x), ,m2t(x)的最小公倍式，即 g(x)=LCMm1(x), m2(x), ,m2t

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

37、就來證明，生成多項式g(x)按(6-28)的形式選取，其監(jiān)督矩陣H中任取d-1列所構成的行列式的值不等于0，從而滿足d-1列線性無關的要求。 實際上，由于d=2t+1,(6-28)又可以表示為 g(x)=LCMm1(x), m2(x), ,md(x) (6-30) 式中包括了由1至d-1的最小多項式，因此a1, a2, ad-1均為g(x)的根，從而也比為任一碼多項式的根。設任一碼多項式為 C(x)= cn-1 xn-1+ c2 x2+ c1 x+ c0 將根a1,a2, ad-1依次代入后，將構成下列聯(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或寫為HXT=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列，它們的行列式之值也不會為0。設選取第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列線性無關，從而保證碼字中有最小的重量d，也就是最小碼距為d，故得所證。0)(112jiijidIJiIIII例6-4求長度n=15的BCH碼的生成多項式，它們能分別糾正1個，2個，3個錯誤。解：糾正1個錯誤，此時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個錯誤，此時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個錯誤，此時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碼就是糾正一位錯誤的漢明碼。一般而言，對任何m=3.長度為n=2m-1的漢明碼，就是糾正單個錯誤的，長度為n=2m-1的BCH碼。碼長n=2m-1(m=3,4,5,6)的漢明碼的生成多項式列在表6-8中。由表中可以看出，漢明碼的生成多項式都是m次本原多項式，因此屬于本原BCH碼。三、戈雷碼 前面討論的生成多項式g(x)包含本原元

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