ECC BCH 編碼 原理PPT

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

2、，則由此生成的循環(huán)碼稱為BCH碼，其最小碼距 (d0稱為設(shè)計(jì)碼距)，它能糾正t個(gè)隨機(jī)獨(dú)立差錯(cuò)。 BCH碼的碼長n=2m-1或是n=2m-1的因子,本原BCH碼,非本原BCH碼,2020/7/14,3,舉例說明,例3.1: BCH(15,5)碼，可糾正3個(gè)隨機(jī)獨(dú)立差錯(cuò)，即t=3 n=15=2m-1, so m=4 查不可約多項(xiàng)式表可得 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個(gè)隨機(jī)獨(dú)立差錯(cuò)，即t=3 n=31=2m-1, so m=5 查不可約多項(xiàng)式表可得 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,部分不可約多項(xiàng)式表,2020/7/14

4、,6,n 31的本原BCH碼,2020/7/14,7,部分非本原BCH碼,2020/7/14,8,3.3 有限域,一個(gè)元素個(gè)數(shù)有限的域稱為有限域，或者伽羅華域(Galois field); 有限域中元素的個(gè)數(shù)為一個(gè)素?cái)?shù)，記為GF(p),其中p為素?cái)?shù)； 一個(gè)大于1的整數(shù)，如果它的正因數(shù)只有1和它本身，就叫做素?cái)?shù)，否則就叫做合數(shù)。 有限域中運(yùn)算滿足 交換律: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)延伸為一個(gè)含有pm個(gè)元素的域，稱為GF(p)的擴(kuò)展域，表示為GF

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

6、多項(xiàng)式ai(x)表示，其系數(shù)至少有一個(gè)不為0。對(duì)于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個(gè)元素ai和一個(gè)0元素。表中的各行是二進(jìn)制數(shù)字序列，代表上式中的系數(shù)ai,0、ai,1、ai,2的取值。,2020/7/14,12,多項(xiàng)式為f(x)=1+x+x3的GF(8)的元素與基本元素之間的映射,2020/7/14,13,有限域中兩個(gè)元素的加法定義為兩個(gè)多項(xiàng)式中同冪次項(xiàng)系數(shù)進(jìn)行模2加，即 ai+aj=(ai,0+aj,0)+ (ai,1+

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

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

9、/7/14,17,即 1+a+a3=0 a3=1+a 這意味著a3可以表示為更低階a項(xiàng)的加權(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個(gè)元素為 0,a0,a1,a2,a3,a4,a5,a6,2020/7/14,18,這8個(gè)元素中哪些是p(x)=0的3個(gè)根呢？我們可通過枚舉找到！ 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是 同理可計(jì)算p(a5)、p(a6)都不等于0，所以p(x)=1+x+x3的3個(gè)根是a, a2, a4,2020/7/14,19,p(x)=1+x+x3, GF(8)加法運(yùn)算表,2020/7/14,20,p(x)=1+x+x3, GF(8)乘法運(yùn)算表,2020/7/14,21,如果GF(p)上的所有元素(除0外)都可表示為某元素a的冪，則a稱為GF(p)上的本原元。 例3.4 考慮GF(5)，因?yàn)閜=5是個(gè)素?cái)?shù)，模算數(shù)可以進(jìn)行?？紤]該

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)上的本原元；大家可以驗(yàn)證，3也是GF(5)上的本原元。,2020/7/14,22,GF(pm)中，在模p(x)運(yùn)算下的擴(kuò)域上，x所表示的元素是本原元。 例如: 用本原多項(xiàng)式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)碼知識(shí)我們知道，為了找到分組長度為n的循環(huán)碼的生成多項(xiàng)式，首先分解xn+1,因此xn+1可以表示為多個(gè)因子的乘積，即 xn+1=f1(x)f2(x)fw(x) 在擴(kuò)展域GF(pm)中，n=pm-1,2020/7/14,24,例3.5 考慮GF(2)和它的擴(kuò)展域GF(8)。這里p=2,m=3,對(duì)x7+1進(jìn)行分解 x7+1=(x+1)(x3+x+1)(x3+x2+1) 同時(shí)我們知道，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碼的編碼,對(duì)一個(gè)分組長度n=pm-1、確定可糾t個(gè)錯(cuò)誤的BCH碼的生成多項(xiàng)式的步驟： 1. 選取一個(gè)次數(shù)為m的素多項(xiàng)式并構(gòu)造GF(pm) 2. 求ai,i=0,1,2,n-2的極小多項(xiàng)式fi(x) 3. 可糾t個(gè)錯(cuò)誤的

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

15、f1(x),f2(x),f2t(x)給出，利用前面的表我們可獲得極小多項(xiàng)式f1(x)和f2(x)，于是有： g(x)=LCMf1(x),f2(x) =LCM(x4+x+1), (x4+x+1) =x4+x+1 因?yàn)閐eg g(x)=n-k，可得n-k=4，所以k=11,于是我們得到糾單一錯(cuò)誤的BCH(15,11)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=3，可以計(jì)算該碼的實(shí)際最小距離d*也是3。,2020/7/14,29,如果希望糾2個(gè)錯(cuò)誤，且n=15。則其生成多項(xiàng)式為 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 因?yàn)閐eg g(x)=n-k=8，所以k=7,于是我們得到糾2個(gè)錯(cuò)誤的BCH(15,7)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=5，可以計(jì)算該碼的實(shí)際最小距離d*也是5。,2020/7/14,30,如果希望糾3個(gè)錯(cuò)誤，且n=15。則其生成多項(xiàng)式為 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 因?yàn)閐eg g(x)=n-k

17、=10，所以k=5,于是我們得到糾3個(gè)錯(cuò)誤的BCH(15,5)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=7，可以計(jì)算該碼的實(shí)際最小距離d*也是7。,2020/7/14,31,如果希望糾4個(gè)錯(cuò)誤，且n=15。則其生成多項(xiàng)式為 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 因?yàn)閐eg g(x)=n-k=14，所以k=1。(簡單的重復(fù)碼)。于是

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

19、e(x) 設(shè)y1,y2,yw為g(x)在GF(pm)上的根，即g(yi)=0,i=1,2,w。因?yàn)閷?duì)某個(gè)信息多項(xiàng)式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ù)一個(gè)域元素a來構(gòu)造的，考慮錯(cuò)誤多項(xiàng)式 e(x)=en-1xn-1+en-2xn-2+e1x+e0 其中最多有t個(gè)系數(shù)為非零(可糾t個(gè)錯(cuò)誤),假設(shè)實(shí)際發(fā)生了v個(gè)錯(cuò)誤，其中0vt。設(shè)錯(cuò)誤發(fā)生在位置i1,i2,iv,則錯(cuò)誤多項(xiàng)式可寫為 其中 為第k個(gè)錯(cuò)誤的大小，對(duì)二元碼，,2020/7/14,34,對(duì)糾錯(cuò)問題，我們必須知

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

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

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

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

24、錯(cuò)誤程度為1，故e(x)=x5+x3。 #,2020/7/14,41,3.6 戈雷(Golay)碼,在第9頁中，我們曾給出一些部分非本原BCH碼的列表，Golay碼就是(23,12)碼。由表可查出，其生成多項(xiàng)式 (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個(gè)的隨機(jī)錯(cuò)誤。 Golay碼是一個(gè)完備碼。,如果r 位監(jiān)督位所組成的校正子與誤碼圖樣一一對(duì)應(yīng)，這種碼組稱為完備碼.,2020/7/14,42,定理：一個(gè)有M個(gè)碼字，最小距離為2t+1的q-元(n,k)碼，滿足 其中qn這個(gè)界稱為漢明界，一個(gè)能到達(dá)漢明界的碼稱為完備碼，即上式取等號(hào)。 容易證明：,2020/7/14,43,3.7 Reed-Solomon (RS)碼,1960年MIT Lincoln實(shí)驗(yàn)室的S. Reed和G. Solomon在Journal of the Society for Industrial and Applied Mathematics上發(fā)表的一篇論文: Polynomial Codes over Cert