ECC BCH 編碼 原理PPT_第1頁
ECC BCH 編碼 原理PPT_第2頁
ECC BCH 編碼 原理PPT_第3頁
ECC BCH 編碼 原理PPT_第4頁
ECC BCH 編碼 原理PPT_第5頁
已閱讀5頁,還剩41頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

1、2020/7/14,1,3.1 引言,BCH碼是一類最重要的循環(huán)碼,能糾正多個隨機錯誤,它是1959年由Bose、Chaudhuri及Hocquenghem各自獨立發(fā)現(xiàn)的二元線性循環(huán)碼,人們用他們的名字字頭命名為BCH碼。 在前面的討論中,我們所做的只是構(gòu)造一個碼,然后計算它的最小距離,從而估計出它的糾錯能力,而在BCH碼中,我們將采用另外一種方法:先說明我們希望它能糾錯的個數(shù),然后構(gòu)造這種碼。,2020/7/14,2,3.2 BCH碼簡述,若循環(huán)碼的生成多項式具有如下形式: g(x)=LCMm1(x),m3(x),m2t-1(x) 其中LCM表示最小公倍式,t為糾錯個數(shù),mi(x)為素多項式

2、,則由此生成的循環(huán)碼稱為BCH碼,其最小碼距 (d0稱為設(shè)計碼距),它能糾正t個隨機獨立差錯。 BCH碼的碼長n=2m-1或是n=2m-1的因子,本原BCH碼,非本原BCH碼,2020/7/14,3,舉例說明,例3.1: BCH(15,5)碼,可糾正3個隨機獨立差錯,即t=3 n=15=2m-1, so m=4 查不可約多項式表可得 m1(x)=(23)8=010011=x4+x+1 m3(x)=(37)8=011111=x4+x3+x2+x+1 m5(x)=(07)8=000111=x2+x+1 這樣 g(x)=LCMm1(x),m3(x),m5(x) =(x4+x+1)(x4+x3+x2+

3、x+1)(x2+x+1) = x10+x8+x5+x4+x2+x+1,2020/7/14,4,例3.2: BCH(31,16)碼,可糾正3個隨機獨立差錯,即t=3 n=31=2m-1, so m=5 查不可約多項式表可得 m1(x)=(45)8=100101=x5+x2+1 m3(x)=(75)8=111101=x5+x4+x3+x2+1 m5(x)=(67)8=110111=x5+x4+x2+x+1 這樣 g(x)=LCMm1(x),m3(x),m5(x) = x15+x11+x10+x9+x8+x7+x5 +x3+x2+x+1,2020/7/14,5,部分不可約多項式表,2020/7/14

4、,6,n 31的本原BCH碼,2020/7/14,7,部分非本原BCH碼,2020/7/14,8,3.3 有限域,一個元素個數(shù)有限的域稱為有限域,或者伽羅華域(Galois field); 有限域中元素的個數(shù)為一個素數(shù),記為GF(p),其中p為素數(shù); 一個大于1的整數(shù),如果它的正因數(shù)只有1和它本身,就叫做素數(shù),否則就叫做合數(shù)。 有限域中運算滿足 交換律:a+b=b+a, ab=b a 結(jié)合律:(a+b)+c=a+(b+c),a(bc)=(ab) c 和分配律:a (b+c)=a b+a c,2020/7/14,9,可以將GF(p)延伸為一個含有pm個元素的域,稱為GF(p)的擴展域,表示為GF

5、(pm),m是一個非零正整數(shù)。注意:GF(p)是GF(pm)的子集。 二進制域GF(2)是擴展域GF(2m)的一個子域,類似于實數(shù)域是復(fù)數(shù)域的一個子域一樣。除了數(shù)字0和1之外,在擴展域中還有特殊的元素,用一個新的符號a表示。GF(2m)中任何非0元素都可由a的冪次表示。,2020/7/14,10,有限元素的集合GF(2m),只能含有2m個元素,并且對乘法封閉,其約束條件為: 根據(jù)這個多項式限制條件,任何冪次等于或超過2m-1的域元素都可降階為下述冪次小于2m-1的元素: 這樣,GF(2m)的元素可表示為:,2020/7/14,11,擴展域GF(2m)中的加法,在GF(2m)中,將每個非0元素用

6、多項式ai(x)表示,其系數(shù)至少有一個不為0。對于i=0,1, 2,2m-2,有: ai = ai(x) = ai,0+ai,1x+ai,2x2+ai,m-1xm-1 考慮m=3,有限域表示為GF(23),下表為上式描述的基本元素x0,x1,x2映射為7個元素ai和一個0元素。表中的各行是二進制數(shù)字序列,代表上式中的系數(shù)ai,0、ai,1、ai,2的取值。,2020/7/14,12,多項式為f(x)=1+x+x3的GF(8)的元素與基本元素之間的映射,2020/7/14,13,有限域中兩個元素的加法定義為兩個多項式中同冪次項系數(shù)進行模2加,即 ai+aj=(ai,0+aj,0)+ (ai,1+

7、aj,1)x+ +(ai,m-1+aj,m-1)xm-1 有限域的本原多項式:因為這些函數(shù)用來定義有限域GF(2m)。 一個多項式是本原多項式的充要條件:一個m階的不可約多項式f(x),如果f(x)整除xn+1的最小正整數(shù)n滿足n=2m-1,則該多項式是本原的。,2020/7/14,14,例3.3 本原多項式的辨別 (1) p1(x)=1+x+x4 (2) p2(x)=1+x+x2+x3+x4 分析: (1)通過驗證這個冪次為m=4的多項式是否能夠整除 ,但不能整除1n15范圍內(nèi)的xn+1,就可以確定它是否為本原多項式。經(jīng)反復(fù)計算,p1(x)是本原多項式,p2(x)不是,因為它能整除x5+1。

8、,2020/7/14,15,部分本原多項式,2020/7/14,16,考慮一個本原多項式定義的有限域的例子,選擇p(x)=1+x+x3,多項式的冪次為m=3,所以由p(x)所定義的域中包含了2m=23=8個元素。求解p(x)的根就是指找到x使p(x)=0。我們所熟悉的二進制數(shù)0和1不能滿足,因為p(1)=1,p(0)=1 (運用模2運算)。由基本代數(shù)學(xué)理論我們知道,對于冪次為m的多項式必然有m個根。對于這個例子,p(x)=0有3個根,由于這3個根不可能位于與p(x)系數(shù)相同的有限域中,而是位于擴展域GF(23)中。用擴展域的元素a來定義多項式p(x)的根,可寫成如下形式:p(a)=0,2020

9、/7/14,17,即 1+a+a3=0 a3=1+a 這意味著a3可以表示為更低階a項的加權(quán)和。 類似地有: a4=a*a3=a*(1+a)=a+a2 a5=a*a4=a*(a+a2)=a2+a3=1+a+a2 a6=a*a5=a*(1+a+a2)=a+a2+a3=1+a2 a7=a*a6=a*(1+a2)=a+a3=1=a0 所以,有限域GF(23)的8個元素為 0,a0,a1,a2,a3,a4,a5,a6,2020/7/14,18,這8個元素中哪些是p(x)=0的3個根呢?我們可通過枚舉找到! p(a0)=1, a0不是 p(a1)=1+a+a3=0, a1是 p(a2)=1+a2+a6=

10、1+a0=0, a2是 p(a3)=1+a3+a9=1+a3+a2=1+a5=a4, a3不是 p(a4)=1+a4+a12=1+a4+a5=1+a0=0, a4是 同理可計算p(a5)、p(a6)都不等于0,所以p(x)=1+x+x3的3個根是a, a2, a4,2020/7/14,19,p(x)=1+x+x3, GF(8)加法運算表,2020/7/14,20,p(x)=1+x+x3, GF(8)乘法運算表,2020/7/14,21,如果GF(p)上的所有元素(除0外)都可表示為某元素a的冪,則a稱為GF(p)上的本原元。 例3.4 考慮GF(5),因為p=5是個素數(shù),模算數(shù)可以進行。考慮該

11、域上的元素2, 20=1(mod 5)=1, 21=2(mod 5)=2 22=4(mod 5)=4, 23=8(mod 5)=3 因此,所有GF(5)上的非零元素,即1,2,3,4都可以表示成2的冪,故2是GF(5)上的本原元;大家可以驗證,3也是GF(5)上的本原元。,2020/7/14,22,GF(pm)中,在模p(x)運算下的擴域上,x所表示的元素是本原元。 例如: 用本原多項式p(x)=1+x+x3 來構(gòu)造GF(8),設(shè)GF(8)上的本原元為a, 通過將a的冪模p(a)得到GF(8)上的所有元素。,2020/7/14,23,定理:設(shè)b1,b2,bp-1為GF(p)上的非零域元素,則x

12、p-1+1=(x+b1)(x+b2)(x+bp-1) 從循環(huán)碼知識我們知道,為了找到分組長度為n的循環(huán)碼的生成多項式,首先分解xn+1,因此xn+1可以表示為多個因子的乘積,即 xn+1=f1(x)f2(x)fw(x) 在擴展域GF(pm)中,n=pm-1,2020/7/14,24,例3.5 考慮GF(2)和它的擴展域GF(8)。這里p=2,m=3,對x7+1進行分解 x7+1=(x+1)(x3+x+1)(x3+x2+1) 同時我們知道,GF(8)中的非零元素為1, a , a+1, a2, a2+1, a2+a, a2+a+1,因此我們可以寫為 x7+1=(x+1)(x+a)(x+a+1)(

13、x+a2) (x+a2+1)(x+a2+a)(x+a2+a+1) =(x+1)(x+a)(x+a2)(x+a2+a) (x+a+1)(x+a2+1)(x+a2+a+1) 而在GF(8)上,有 x3+x+1= (x+a)(x+a2)(x+a2+a) x3+x2+1=(x+a+1)(x+a2+1)(x+a2+a+1),2020/7/14,25,2020/7/14,26,3.4 BCH碼的編碼,對一個分組長度n=pm-1、確定可糾t個錯誤的BCH碼的生成多項式的步驟: 1. 選取一個次數(shù)為m的素多項式并構(gòu)造GF(pm) 2. 求ai,i=0,1,2,n-2的極小多項式fi(x) 3. 可糾t個錯誤的

14、碼的生成多項式為 g(x)=LCMf1(x),f2(x),f2t(x) 用這種方法設(shè)計的碼至少能糾t個錯誤,在很多情況下,這些碼能糾多于t個錯誤!因此d=2t+1稱為碼的設(shè)計距離,其最小距離d* 2t+1。注意:一旦確定了n和t,我們便可以確定BCH碼的生成多項式。,2020/7/14,27,例3.6 考慮GF(2)上的本原多項式p(a)=a4+a+1,我們將以此來構(gòu)造GF(16),設(shè)a為本原元。GF(16)上以a的冪表示形式的元素及它們對應(yīng)的極小多項式為:,2020/7/14,28,我們希望確定糾單錯的BCH碼的生成多項式,即t=1且n=15。由前面公式可知,一個BCH碼的生成多項式由LCM

15、f1(x),f2(x),f2t(x)給出,利用前面的表我們可獲得極小多項式f1(x)和f2(x),于是有: g(x)=LCMf1(x),f2(x) =LCM(x4+x+1), (x4+x+1) =x4+x+1 因為deg g(x)=n-k,可得n-k=4,所以k=11,于是我們得到糾單一錯誤的BCH(15,11)碼的生成多項式。該碼的設(shè)計距離為d=2t+1=3,可以計算該碼的實際最小距離d*也是3。,2020/7/14,29,如果希望糾2個錯誤,且n=15。則其生成多項式為 g(x)=LCMf1(x),f2(x),f3(x),f4(x) =LCM(x4+x+1),(x4+x+1), (x4+x

16、3+x2+x+1),(x4+x+1) = (x4+x+1)(x4+x3+x2+x+1) = x8+x7+x6+x4+1 因為deg g(x)=n-k=8,所以k=7,于是我們得到糾2個錯誤的BCH(15,7)碼的生成多項式。該碼的設(shè)計距離為d=2t+1=5,可以計算該碼的實際最小距離d*也是5。,2020/7/14,30,如果希望糾3個錯誤,且n=15。則其生成多項式為 g(x)=LCMf1(x),f2(x),f3(x),f4(x),f5(x),f6(x) = (x4+x+1)(x4+x3+x2+x+1)(x2+x+1) = x10+x8+x5+x4+x2+x+1 因為deg g(x)=n-k

17、=10,所以k=5,于是我們得到糾3個錯誤的BCH(15,5)碼的生成多項式。該碼的設(shè)計距離為d=2t+1=7,可以計算該碼的實際最小距離d*也是7。,2020/7/14,31,如果希望糾4個錯誤,且n=15。則其生成多項式為 g(x)=LCMf1(x),f2(x),f3(x),f4(x), f5(x),f6(x),f7(x),f8(x) = (x4+x+1)(x4+x3+x2+x+1) (x2+x+1)(x4+x3+1) = x14+x13+x12+x11+x10+x9+x8+x7 +x6+x5+x4+x3+x2+x+1 因為deg g(x)=n-k=14,所以k=1。(簡單的重復(fù)碼)。于是

18、我們得到糾4個錯誤的BCH(15,1)碼的生成多項式。該碼的設(shè)計距離為d=2t+1=9,可以計算該碼的實際最小距離d*是15。在此情況下,設(shè)計距離不等于實際最小距離,碼設(shè)計得太過度了,該碼實際可糾(d*-1)/2=7個隨機錯誤!,2020/7/14,32,3.5 BCH碼的譯碼,根據(jù)生成多項式,可以構(gòu)造出快速的硬件編碼器,而對于BCH碼的譯碼,由于它是循環(huán)碼的一個子類,任何對循環(huán)碼的標(biāo)準(zhǔn)譯碼過程都適用于BCH碼。下面我們主要討論專門針對BCH碼的更高效的算法: Gorenstein-zierler譯碼算法 設(shè)c(x)為發(fā)送碼字多項式,e(x)為錯誤多項式,則接收到的多項式為r(x)=c(x)+

19、e(x) 設(shè)y1,y2,yw為g(x)在GF(pm)上的根,即g(yi)=0,i=1,2,w。因為對某個信息多項式a(x),有c(x)=a(x)g(x),所以c(yi)=0 r(yi)=c(yi)+e(yi)=e(yi), i=1,2,w,2020/7/14,33,假設(shè)BCH碼是根據(jù)一個域元素a來構(gòu)造的,考慮錯誤多項式 e(x)=en-1xn-1+en-2xn-2+e1x+e0 其中最多有t個系數(shù)為非零(可糾t個錯誤),假設(shè)實際發(fā)生了v個錯誤,其中0vt。設(shè)錯誤發(fā)生在位置i1,i2,iv,則錯誤多項式可寫為 其中 為第k個錯誤的大小,對二元碼,,2020/7/14,34,對糾錯問題,我們必須知

20、道兩件事: (1)錯誤在哪里發(fā)生了,即錯誤的位置 (2)錯誤程度 因此,未知量為i1,i2,iv和 , , ,它們分別表明錯誤發(fā)生的位置和程度。 伴隨式可通過對接收到的關(guān)于a的多項式計算得到: 定義錯誤程度 和錯誤位置 , k=1,2,v。其中ik為第k個錯誤的位置,Xk是與這個位置相關(guān)的域元素。,2020/7/14,35,現(xiàn)在伴隨多項式可寫為 S1=Y1X1+Y2X2+YvXv 對j=1,2,2t, 我們定義伴隨式 Sj=r(aj)=c(aj)+e(aj)=e(aj) 于是我們可得到2t個聯(lián)立方程組,它有v個錯誤位置未知量X1,X2,Xv和v個錯誤程度未知量Y1,Y2,Yv:,2020/7/

21、14,36,定義錯誤定位多項式 U(x)=Uvxv+Uv-1xv-1+U1x+1 這個多項式的根是錯誤位置的逆 ,k=1,2,v,即 U(x)=(1-xX1)(1-xX2)(1-xXv) 所以,如果我們知道錯誤定位多項式U(x)的系數(shù),便可以求得錯誤位置X1,X2,Xv。經(jīng)過一系列代數(shù)變換,我們可得如下矩陣:,錯誤定位多項式的系數(shù)可通過對伴隨式矩陣M求逆得到!,2020/7/14,37,BCH碼的譯碼步驟,作為測試值,令v=t,計算伴隨矩陣M的行列式。如果行列式的值為零,令v=t-1,再一次計算M的行列式。重復(fù)這個過程直到找到一個v值,使伴隨矩陣的行列式不為0,該v值就是實際產(chǎn)生錯誤的數(shù)目。

22、求M的逆,并計算錯誤定位多項式U(x)的系數(shù); 求解U(x)=0的零點,從中可計算錯誤位置X1,X2,Xv。如果是二元碼,就到此為止(因為錯誤程度為1); 如果不是二元碼,回到方程組 解這些方程組就得到錯誤程度,2020/7/14,38,例3.7 考慮糾3個錯誤的BCH(15,5)碼,它的生成多項式為g(x)=x10+x8+x5+x4+x2+x+1 設(shè)傳輸?shù)氖侨?碼字,接收到的多項式為r(x)=x5+x3,故有兩個錯誤分別在第4個位置和第6個位置,錯誤多項式為e(x)=x5+x3。但譯碼器并不知道這些,它連實際發(fā)生了幾個錯誤都不知道! 解:利用Gorenstein-aierler譯碼算法,首先

23、用GF(16)上的算術(shù)計算出伴隨式 S1=a5+a3=a11, S2=a10+a6=a7 S3=a15+a9=a7, S4=a20+a12=a14 S5=a25+a15=a5, S6=a30+a18=a14 因為這是個糾3個錯的碼,首先令v=t=3,2020/7/14,39,Det(M)=0, 這表明發(fā)生的錯誤數(shù)少于3個。 下面令v=2 Det(M) 0, 這表明實際發(fā)生了2個錯誤。 下面計算M-1,2020/7/14,40,求解U1和U2可得U2=a8及U1=a11, 從而 U(x)=a8x2+a11x+1=(1+xa5)(1+xa3) 因此恢復(fù)出來的錯誤位置為a5和a3。因為該碼是二元碼,

24、錯誤程度為1,故e(x)=x5+x3。 #,2020/7/14,41,3.6 戈雷(Golay)碼,在第9頁中,我們曾給出一些部分非本原BCH碼的列表,Golay碼就是(23,12)碼。由表可查出,其生成多項式 (5343)8=101 011 100 011 即 g1(x)=x11+x9+x7+x6+x5+x+1 或g2(x)=x11+x10+x6+x5+x4+x2+1 它們都是x23+1的因式,即 x23+1=(x+1)g1(x)g2(x) 其最小碼距為7,可糾正不大于3個的隨機錯誤。 Golay碼是一個完備碼。,如果r 位監(jiān)督位所組成的校正子與誤碼圖樣一一對應(yīng),這種碼組稱為完備碼.,2020/7/14,42,定理:一個有M個碼字,最小距離為2t+1的q-元(n,k)碼,滿足 其中qn這個界稱為漢明界,一個能到達漢明界的碼稱為完備碼,即上式取等號。 容易證明:,2020/7/14,43,3.7 Reed-Solomon (RS)碼,1960年MIT Lincoln實驗室的S. Reed和G. Solomon在Journal of the Society for Industrial and Applied Mathematics上發(fā)表的一篇論文: Polynomial Codes over Cert

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論