循環(huán)碼與BCH碼.ppt

《循環(huán)碼與BCH碼.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

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

2、Cn-1=[c0,cn-1,…,c2,c1]都是碼字例如，第五章中表5-2中所列的(7,3)碼，就是具有這種循環(huán)特性的循環(huán)碼。（P176）關于循環(huán)碼強調(diào)兩點：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次多項式C(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0[6-1]稱為碼多項式。例如：碼字C=[001011

3、1]所對應的碼多項式為C(x)=x4+x2+x+1假如已知碼多項式C(x)=x7+x3+x+1，則可求出對應的碼字C=10001011實際上，將(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+cn

4、x+cn-1mod(xn+1)(n,k)循環(huán)碼的每個碼字必處在以xn+1為模運算的剩余類的某一類中。生成多項式在(n,k)循環(huán)碼的2k個碼字中，取一個前k-1位皆為0的碼字，此碼字對應有一個次數(shù)最低，且為n-k=r的多項式g(x)，其它碼字所對應的碼多項式都是g(x)的倍式，則稱g(x)生成該碼，并且稱g(x)為該碼的生成多項式?？梢娚啥囗検骄哂幸韵绿卣鳎篻(x)=xr+gr-1xr-1+…+g2x2+g1x+g0g0≠0r=n-k如果g(x)為(n,k)循環(huán)碼的最低次多項式，即生成多項式時，xg(x),x2g(x),…,xk-1g(x)都是碼字，這k個碼字是獨

5、立的，故可作為碼的一組生成基底，使每個碼多項式都是這一組基底的線性組合。例如P176例5-1由此看來，找到合適的g(x)是構(gòu)造循環(huán)碼的關鍵。在這方面需要用到有限域的知識。第二節(jié)　有限域中的運算規(guī)則運算自封：一個集合中的元素經(jīng)過某種運算（例如加減乘除）后仍為集合中的元素時，稱為運算自封。域：運算自封元素的集合叫做域F（Field）。域中的元素相加a+b和相乘ab滿足下列關系：D：滿足分配律a(b+c)=ab+ac,(a+b)c=ac+bc當域中元素為有限數(shù)p時，稱為有限域或p元域，有限域理論是由數(shù)學家伽羅華（Galols）所創(chuàng)立的，因此又稱為伽羅華域，并記為GF(p

6、)。普通代數(shù)中全體有理數(shù)的集合叫有理域，全體實數(shù)的集合叫實數(shù)域。全體復數(shù)的集合叫復數(shù)域。它們都是無限域。經(jīng)常用到的有限域是二元域GF(2)，它有兩個元素“0”和“1”，其加法和乘法分別為：加法　　　　　　乘法0+0＝0　　　　　0*0＝00+1＝1　　　　　0*1＝01+0＝1　　　　　1*0＝01+1＝0　　　　　1*1＝1系數(shù)在GF(2)中的多項式叫做二元域上的多項式。二元域上多項式的加減乘除等運算在原理上和普通代數(shù)多項式的運算相同。例如：對碼字多項式C(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0有xi+xi＝0,ci+ci＝0,ci2=ci.

7、ci＝ci并且減法就是加法。加法符號為“　　”或簡記為“+”。證：因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-12＝cn-1，上式包括2作系數(shù)的第二項乘積為0，將第三項類似地逐步展開，就可以得出C2(x)＝cn-1x2(n-1)+cn-2x2(n-2)+…+c1x2+c0=C(x2)例6-2　試證明對上述二元域上碼多項式C(x),有C2(x)＝C(x2)定理：設d(x)和g(x)是二元域上的兩個多項式。

8、則有唯一的