2022/12/101編碼理論

CodingTheory周武旸中國(guó)科學(xué)技術(shù)大學(xué)個(gè)人通信與擴(kuò)頻實(shí)驗(yàn)室2022/12/101編碼理論

CodingT2022/12/102第三章BCH碼3.1引言3.2BCH碼簡(jiǎn)述3.3有限域3.4BCH碼的編碼3.5BCH碼的譯碼3.6戈雷(Golay)碼3.7Reed-Solomon碼2022/12/102第三章BCH碼3.1引言2022/12/1033.1引言BCH碼是一類(lèi)最重要的循環(huán)碼，能糾正多個(gè)隨機(jī)錯(cuò)誤，它是1959年由Bose、Chaudhuri及Hocquenghem各自獨(dú)立發(fā)現(xiàn)的二元線性循環(huán)碼，人們用他們的名字字頭命名為BCH碼。在前面的討論中，我們所做的只是構(gòu)造一個(gè)碼，然后計(jì)算它的最小距離，從而估計(jì)出它的糾錯(cuò)能力，而在BCH碼中，我們將采用另外一種方法：先說(shuō)明我們希望它能糾錯(cuò)的個(gè)數(shù)，然后構(gòu)造這種碼。2022/12/1033.1引言BCH碼是一類(lèi)最重要的循環(huán)2022/12/1043.2BCH碼簡(jiǎn)述若循環(huán)碼的生成多項(xiàng)式具有如下形式：

g(x)=LCM[m1(x),m3(x),…,m2t-1(x)]其中LCM表示最小公倍式，t為糾錯(cuò)個(gè)數(shù)，mi(x)為素多項(xiàng)式，則由此生成的循環(huán)碼稱為BCH碼，其最小碼距(d0稱為設(shè)計(jì)碼距)，它能糾正t個(gè)隨機(jī)獨(dú)立差錯(cuò)。BCH碼的碼長(zhǎng)n=2m-1或是n=2m-1的因子本原BCH碼非本原BCH碼2022/12/1043.2BCH碼簡(jiǎn)述若循環(huán)碼的生成多項(xiàng)2022/12/105舉例說(shuō)明例3.1:BCH(15,5)碼，可糾正3個(gè)隨機(jī)獨(dú)立差錯(cuò)，即t=3n=15=2m-1,som=4查不可約多項(xiàng)式表可得m1(x)=(23)8=010011=x4+x+1m3(x)=(37)8=011111=x4+x3+x2+x+1m5(x)=(07)8=000111=x2+x+1這樣g(x)=LCM[m1(x),m3(x),m5(x)]=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)=x10+x8+x5+x4+x2+x+12022/12/105舉例說(shuō)明例3.1:BCH(15,5)2022/12/106例3.2:BCH(31,16)碼，可糾正3個(gè)隨機(jī)獨(dú)立差錯(cuò)，即t=3n=31=2m-1,som=5查不可約多項(xiàng)式表可得m1(x)=(45)8=100101=x5+x2+1m3(x)=(75)8=111101=x5+x4+x3+x2+1m5(x)=(67)8=110111=x5+x4+x2+x+1這樣g(x)=LCM[m1(x),m3(x),m5(x)]=x15+x11+x10+x9+x8+x7+x5+x3+x2+x+12022/12/106例3.2:BCH(31,16)碼，可2022/12/107部分不可約多項(xiàng)式表2階173階1134階1233375075階1453755672022/12/107部分不可約多項(xiàng)式表2階173階11342022/12/108n≤31的本原BCH碼nktg(x)74113151112315727211553246731261453121235513116310765731115542332531673133650472022/12/108n≤31的本原BCH碼nktg(x)2022/12/109部分非本原BCH碼nkdg(x)1795727211634321125166321671263572149643215231275343255541020412793100100127767007007336730432022/12/109部分非本原BCH碼nkdg(x)1792022/12/10103.3有限域一個(gè)元素個(gè)數(shù)有限的域稱為有限域，或者伽羅華域(Galoisfield);有限域中元素的個(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,a?b=b?a結(jié)合律:(a+b)+c=a+(b+c),a?(b?c)=(a?b)?c和分配律:a?(b+c)=a?b+a?c2022/12/10103.3有限域一個(gè)元素個(gè)數(shù)有限的域稱2022/12/1011可以將GF(p)延伸為一個(gè)含有pm個(gè)元素的域，稱為GF(p)的擴(kuò)展域，表示為GF(pm)，m是一個(gè)非零正整數(shù)。注意：GF(p)是GF(pm)的子集。二進(jìn)制域GF(2)是擴(kuò)展域GF(2m)的一個(gè)子域，類(lèi)似于實(shí)數(shù)域是復(fù)數(shù)域的一個(gè)子域一樣。除了數(shù)字0和1之外，在擴(kuò)展域中還有特殊的元素，用一個(gè)新的符號(hào)a表示。GF(2m)中任何非0元素都可由a的冪次表示。2022/12/1011可以將GF(p)延伸為一個(gè)含有pm個(gè)2022/12/1012有限元素的集合GF(2m)，只能含有2m個(gè)元素，并且對(duì)乘法封閉，其約束條件為：根據(jù)這個(gè)多項(xiàng)式限制條件，任何冪次等于或超過(guò)2m-1的域元素都可降階為下述冪次小于2m-1的元素：這樣，GF(2m)的元素可表示為：2022/12/1012有限元素的集合GF(2m)，只能含有2022/12/1013擴(kuò)展域GF(2m)中的加法在GF(2m)中，將每個(gè)非0元素用多項(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的取值。2022/12/1013擴(kuò)展域GF(2m)中的加法在GF(22022/12/1014域元素基本元素x0x1x20000a0100a1010a2001a3110a4011a5111a6101a7100多項(xiàng)式為f(x)=1+x+x3的GF(8)的元素與基本元素之間的映射2022/12/1014基本元素x0x1x20000a0102022/12/1015有限域中兩個(gè)元素的加法定義為兩個(gè)多項(xiàng)式中同冪次項(xiàng)系數(shù)進(jìn)行模2加，即

ai+aj=(ai,0+aj,0)+(ai,1+aj,1)x+…+(ai,m-1+aj,m-1)xm-1有限域的本原多項(xiàng)式：因?yàn)檫@些函數(shù)用來(lái)定義有限域GF(2m)。一個(gè)多項(xiàng)式是本原多項(xiàng)式的充要條件：一個(gè)m階的不可約多項(xiàng)式f(x)，如果f(x)整除xn+1的最小正整數(shù)n滿足n=2m-1，則該多項(xiàng)式是本原的。2022/12/1015有限域中兩個(gè)元素的加法定義為兩個(gè)多項(xiàng)2022/12/1016例3.3本原多項(xiàng)式的辨別

(1)p1(x)=1+x+x4(2)p2(x)=1+x+x2+x3+x4

分析:(1)通過(guò)驗(yàn)證這個(gè)冪次為m=4的多項(xiàng)式是否能夠整除,但不能整除1≤n<15范圍內(nèi)的xn+1，就可以確定它是否為本原多項(xiàng)式。經(jīng)反復(fù)計(jì)算，p1(x)是本原多項(xiàng)式，p2(x)不是，因?yàn)樗苷齲5+1。2022/12/1016例3.3本原多項(xiàng)式的辨別2022/12/1017部分本原多項(xiàng)式mm31+x+x3111+x2+x1141+x+x4121+x+x4+x6+x1251+x2+x5131+x+x3+x4+x1361+x+x6141+x+x6+x10+x1471+x3+x7151+x+x1581+x2+x3+x4+x8161+x+x3+x12+x1691+x4+x9171+x3+x17101+x3+x10181+x7+x182022/12/1017部分本原多項(xiàng)式mm31+x+x32022/12/1018考慮一個(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來(lái)定義多項(xiàng)式p(x)的根，可寫(xiě)成如下形式：p(a)=02022/12/1018考慮一個(gè)本原多項(xiàng)式定義的有限域的例子2022/12/1019

即1+a+a3=0a3=1+a

這意味著a3可以表示為更低階a項(xiàng)的加權(quán)和。類(lèi)似地有：a4=a*a3=a*(1+a)=a+a2a5=a*a4=a*(a+a2)=a2+a3=1+a+a2a6=a*a5=a*(1+a+a2)=a+a2+a3=1+a2a7=a*a6=a*(1+a2)=a+a3=1=a0所以，有限域GF(23)的8個(gè)元素為{0,a0,a1,a2,a3,a4,a5,a6}

2022/12/1019即1+a+a3=02022/12/1020這8個(gè)元素中哪些是p(x)=0的3個(gè)根呢？我們可通過(guò)枚舉找到！p(a0)=1,a0不是p(a1)=1+a+a3=0,a1是p(a2)=1+a2+a6=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,a42022/12/1020這8個(gè)元素中哪些是p(x)=0的3個(gè)2022/12/1021p(x)=1+x+x3,GF(8)加法運(yùn)算表+a0a1a2a3a4a5a6a00a3a6a1a5a4a2a1a30a4a0a2a6a5a2a6a40a5a1a3a0a3a1a0a50a6a2a4a4a5a2a1a60a0a3a5a4a6a3a2a00a1a6a2a5a0a4a3a102022/12/1021p(x)=1+x+x3,GF(8)2022/12/1022p(x)=1+x+x3,GF(8)乘法運(yùn)算表×a0a1a2a3a4a5a6a0a0a1a2a3a4a5a6a1a1a2a3a4a5a6a0a2a2a3a4a5a6a0a1a3a3a4a5a6a0a1a2a4a4a5a6a0a1a2a3a5a5a6a0a1a2a3a4a6a6a0a1a2a3a4a52022/12/1022p(x)=1+x+x3,GF(8)2022/12/1023如果GF(p)上的所有元素(除0外)都可表示為某元素a的冪，則a稱為GF(p)上的本原元。例3.4考慮GF(5)，因?yàn)閜=5是個(gè)素?cái)?shù)，模算數(shù)可以進(jìn)行。考慮該域上的元素2，

20=1(mod5)=1,21=2(mod5)=222=4(mod5)=4,23=8(mod5)=3

因此，所有GF(5)上的非零元素，即{1,2,3,4}都可以表示成2的冪，故2是GF(5)上的本原元；大家可以驗(yàn)證，3也是GF(5)上的本原元。2022/12/1023如果GF(p)上的所有元素(除0外)2022/12/1024GF(pm)中，在模p(x)運(yùn)算下的擴(kuò)域上，x所表示的元素是本原元。例如:用本原多項(xiàng)式p(x)=1+x+x3

來(lái)構(gòu)造GF(8)，設(shè)GF(8)上的本原元為a,通過(guò)將a的冪模p(a)得到GF(8)上的所有元素。a的冪GF(8)上的元素a01a1aa2a2a3a+1a4a2+aa5a2+a+1a6a2+12022/12/1024GF(pm)中，在模p(x)運(yùn)算下的2022/12/1025定理:設(shè)b1,b2,…,bp-1為GF(p)上的非零域元素，則xp-1+1=(x+b1)(x+b2)…(x+bp-1)從循環(huán)碼知識(shí)我們知道，為了找到分組長(zhǎng)度為n的循環(huán)碼的生成多項(xiàng)式，首先分解xn+1,因此xn+1可以表示為多個(gè)因子的乘積，即

xn+1=f1(x)f2(x)…fw(x)在擴(kuò)展域GF(pm)中，n=pm-12022/12/1025定理:設(shè)b1,b2,…,bp-1為G2022/12/1026例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,因此我們可以寫(xiě)為x7+1=(x+1)(x+a)(x+a+1)(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)2022/12/1026例3.5考慮GF(2)和它的擴(kuò)展域2022/12/1027極小多項(xiàng)式fi(x)對(duì)應(yīng)的根元素用a的冪表示x+11a0x3+x+1a,a2和a2+aa1,a2,a4x3+x2+1a+1,a2+1和a2+a+1a3,a6,a52022/12/1027極小多項(xiàng)式fi(x)對(duì)應(yīng)的根元素用a2022/12/10283.4BCH碼的編碼對(duì)一個(gè)分組長(zhǎng)度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ò)誤的碼的生成多項(xiàng)式為

g(x)=LCM[f1(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)式。2022/12/10283.4BCH碼的編碼對(duì)一個(gè)分組長(zhǎng)度2022/12/1029例3.6考慮GF(2)上的本原多項(xiàng)式p(a)=a4+a+1，我們將以此來(lái)構(gòu)造GF(16),設(shè)a為本原元。GF(16)上以a的冪表示形式的元素及它們對(duì)應(yīng)的極小多項(xiàng)式為：a的冪GF(16)的元素極小多項(xiàng)式a01x+1a1ax4+x+1a2a2x4+x+1a3a3x4+x3+x2+x+1a4a+1x4+x+1a5a2+ax2+x+1a6a3+a2x4+x3+x2+x+1a7a3+a+1x4+x3+1a8a2+1x4+x+1a9a3+ax4+x3+x2+x+1a10a2+a+1x2+x+1a11a3+a2+ax4+x3+1a12a3+a2+a+1x4+x3+x2+x+1a13a3+a2+1x4+x3+1a14a3+1x4+x3+12022/12/1029例3.6考慮GF(2)上的本原多項(xiàng)2022/12/1030我們希望確定糾單錯(cuò)的BCH碼的生成多項(xiàng)式，即t=1且n=15。由前面公式可知，一個(gè)BCH碼的生成多項(xiàng)式由LCM[f1(x),f2(x),…,f2t(x)]給出，利用前面的表我們可獲得極小多項(xiàng)式f1(x)和f2(x)，于是有：

g(x)=LCM[f1(x),f2(x)]=LCM[(x4+x+1),(x4+x+1)]=x4+x+1

因?yàn)閐egg(x)=n-k，可得n-k=4，所以k=11,于是我們得到糾單一錯(cuò)誤的BCH(15,11)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=3，可以計(jì)算該碼的實(shí)際最小距離d*也是3。

2022/12/1030我們希望確定糾單錯(cuò)的BCH碼的生成多2022/12/1031

如果希望糾2個(gè)錯(cuò)誤，且n=15。則其生成多項(xiàng)式為

g(x)=LCM[f1(x),f2(x),f3(x),f4(x)]=LCM[(x4+x+1),(x4+x+1),(x4+x3+x2+x+1),(x4+x+1)]=(x4+x+1)(x4+x3+x2+x+1)=x8+x7+x6+x4+1

因?yàn)閐egg(x)=n-k=8，所以k=7,于是我們得到糾2個(gè)錯(cuò)誤的BCH(15,7)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=5，可以計(jì)算該碼的實(shí)際最小距離d*也是5。2022/12/1031如果希望糾2個(gè)錯(cuò)誤，且n=152022/12/1032

如果希望糾3個(gè)錯(cuò)誤，且n=15。則其生成多項(xiàng)式為

g(x)=LCM[f1(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)閐egg(x)=n-k=10，所以k=5,于是我們得到糾3個(gè)錯(cuò)誤的BCH(15,5)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=7，可以計(jì)算該碼的實(shí)際最小距離d*也是7。2022/12/1032如果希望糾3個(gè)錯(cuò)誤，且n=152022/12/1033

如果希望糾4個(gè)錯(cuò)誤，且n=15。則其生成多項(xiàng)式為

g(x)=LCM[f1(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)閐egg(x)=n-k=14，所以k=1。(簡(jiǎn)單的重復(fù)碼)。于是我們得到糾4個(gè)錯(cuò)誤的BCH(15,1)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=9，可以計(jì)算該碼的實(shí)際最小距離d*是15。在此情況下，設(shè)計(jì)距離不等于實(shí)際最小距離，碼設(shè)計(jì)得太過(guò)度了，該碼實(shí)際可糾(d*-1)/2=7個(gè)隨機(jī)錯(cuò)誤！2022/12/1033如果希望糾4個(gè)錯(cuò)誤，且n=152022/12/10343.5BCH碼的譯碼根據(jù)生成多項(xiàng)式，可以構(gòu)造出快速的硬件編碼器，而對(duì)于BCH碼的譯碼，由于它是循環(huán)碼的一個(gè)子類(lèi)，任何對(duì)循環(huán)碼的標(biāo)準(zhǔn)譯碼過(guò)程都適用于BCH碼。下面我們主要討論專門(mén)針對(duì)BCH碼的更高效的算法:

Gorenstein-zierler譯碼算法設(shè)c(x)為發(fā)送碼字多項(xiàng)式，e(x)為錯(cuò)誤多項(xiàng)式，則接收到的多項(xiàng)式為r(x)=c(x)+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)=0r(yi)=c(yi)+e(yi)=e(yi),i=1,2,…,w2022/12/10343.5BCH碼的譯碼根據(jù)生成多項(xiàng)式2022/12/1035假設(shè)BCH碼是根據(jù)一個(gè)域元素a來(lái)構(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ò)誤，其中0≤v≤t。設(shè)錯(cuò)誤發(fā)生在位置i1,i2,…,iv,則錯(cuò)誤多項(xiàng)式可寫(xiě)為其中為第k個(gè)錯(cuò)誤的大小，對(duì)二元碼，2022/12/1035假設(shè)BCH碼是根據(jù)一個(gè)域元素a來(lái)構(gòu)造2022/12/1036對(duì)糾錯(cuò)問(wèn)題，我們必須知道兩件事：(1)錯(cuò)誤在哪里發(fā)生了，即錯(cuò)誤的位置(2)錯(cuò)誤程度因此，未知量為i1,i2,…,iv和,,…,,它們分別表明錯(cuò)誤發(fā)生的位置和程度。伴隨式可通過(guò)對(duì)接收到的關(guān)于a的多項(xiàng)式計(jì)算得到：定義錯(cuò)誤程度和錯(cuò)誤位置,k=1,2,…,v。其中ik為第k個(gè)錯(cuò)誤的位置，Xk是與這個(gè)位置相關(guān)的域元素。2022/12/1036對(duì)糾錯(cuò)問(wèn)題，我們必須知道兩件事：2022/12/1037現(xiàn)在伴隨多項(xiàng)式可寫(xiě)為

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:2022/12/1037現(xiàn)在伴隨多項(xiàng)式可寫(xiě)為2022/12/1038定義錯(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)過(guò)一系列代數(shù)變換，我們可得如下矩陣：錯(cuò)誤定位多項(xiàng)式的系數(shù)可通過(guò)對(duì)伴隨式矩陣M求逆得到！2022/12/1038定義錯(cuò)誤定位多項(xiàng)式錯(cuò)誤定位多項(xiàng)式的系2022/12/1039BCH碼的譯碼步驟作為測(cè)試值，令v=t，計(jì)算伴隨矩陣M的行列式。如果行列式的值為零，令v=t-1,再一次計(jì)算M的行列式。重復(fù)這個(gè)過(guò)程直到找到一個(gè)v值，使伴隨矩陣的行列式不為0，該v值就是實(shí)際產(chǎn)生錯(cuò)誤的數(shù)目。求M的逆，并計(jì)算錯(cuò)誤定位多項(xiàng)式U(x)的系數(shù)；求解U(x)=0的零點(diǎn)，從中可計(jì)算錯(cuò)誤位置X1,X2,…,Xv。如果是二元碼，就到此為止(因?yàn)殄e(cuò)誤程度為1);如果不是二元碼，回到方程組解這些方程組就得到錯(cuò)誤程度2022/12/1039BCH碼的譯碼步驟作為測(cè)試值，令v=2022/12/1040例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譯碼算法，首先用GF(16)上的算術(shù)計(jì)算出伴隨式

S1=a5+a3=a11,S2=a10+a6=a7S3=a15+a9=a7,S4=a20+a12=a14S5=a25+a15=a5,S6=a30+a18=a14

因?yàn)檫@是個(gè)糾3個(gè)錯(cuò)的碼，首先令v=t=32022/12/1040例3.7考慮糾3個(gè)錯(cuò)誤的BCH(12022/12/1041

Det(M)=0,這表明發(fā)生的錯(cuò)誤數(shù)少于3個(gè)。下面令v=2Det(M)≠0,這表明實(shí)際發(fā)生了2個(gè)錯(cuò)誤。下面計(jì)算M-12022/12/10412022/12/1042

求解U1和U2可得U2=a8及U1=a11,從而U(x)=a8x2+a11x+1=(1+xa5)(1+xa3)因此恢復(fù)出來(lái)的錯(cuò)誤位置為a5和a3。因?yàn)樵摯a是二元碼，錯(cuò)誤程度為1，故e(x)=x5+x3。

#2022/12/10422022/12/10433.6戈雷(Golay)碼在第9頁(yè)中，我們?cè)o出一些部分非本原BCH碼的列表，Golay碼就是(23,12)碼。由表可查出，其生成多項(xiàng)式(5343)8=101011100011即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)，這種碼組稱為完備碼.2022/12/10433.6戈雷(Golay)碼在第9頁(yè)2022/12/1044定理：一個(gè)有M個(gè)碼字，最小距離為2t+1的q-元(n,k)碼，滿足其中qn這個(gè)界稱為漢明界，一個(gè)能到達(dá)漢明界的碼稱為完備碼，即上式取等號(hào)。容易證明：2022/12/1044定理：一個(gè)有M個(gè)碼字，最小距離為2t2022/12/10453.7Reed-Solomon(RS)碼1960年MITLincoln實(shí)驗(yàn)室的S.Reed和G.Solomon在JournaloftheSocietyforIndustrialandAppliedMathematics上發(fā)表的一篇論文:PolynomialCodesoverCertainFiniteFields(某些有限域上的多項(xiàng)式碼)RS碼的編碼系統(tǒng)是建立在比特組基礎(chǔ)上的，即字節(jié)，而不是單個(gè)的0和1，因此它是非二進(jìn)制BCH碼，這使得它處理突發(fā)錯(cuò)誤特別好。

備注：在許多現(xiàn)實(shí)生活的信道中，錯(cuò)誤不是隨機(jī)的，而是突發(fā)的。例如，在一個(gè)移動(dòng)通信信道中，信號(hào)衰退導(dǎo)致突發(fā)錯(cuò)誤。當(dāng)錯(cuò)誤連續(xù)發(fā)生時(shí)，我們稱它們?yōu)橥话l(fā)錯(cuò)誤。2022/12/10453.7Reed-Solomon(2022/12/1046對(duì)于任意選取的正整數(shù)s，可構(gòu)造一個(gè)相應(yīng)碼長(zhǎng)為n=qs-1的q進(jìn)制BCH碼，其中碼元符號(hào)取自有限域GF(q)，而q為素?cái)?shù)的冪。當(dāng)s=1,q>2時(shí)所建立的碼長(zhǎng)為n=q-1的q進(jìn)制BCH碼，稱為RS碼。當(dāng)q=2m(m>1)，碼元符號(hào)取自域GF(2m)的二進(jìn)制RS碼可用來(lái)糾正突發(fā)錯(cuò)誤。輸入信息分為k*m比特一組，即每個(gè)符號(hào)有m比特，k個(gè)符號(hào)形成一組。2022/12/1046對(duì)于任意選取的正整數(shù)s，可構(gòu)造一個(gè)相2022/12/1047一個(gè)可糾t個(gè)符號(hào)錯(cuò)誤的RS碼，有如下參數(shù)碼長(zhǎng)：n=2m-1符號(hào)或m(2m-1)bit信息段：k符號(hào)或kmbit監(jiān)督段：n-k=2t符號(hào)或m(n-k)=2mtbit最小碼距：d=2t+1符號(hào)或md=m(2t+1)bit例3.8試構(gòu)造一個(gè)能糾3個(gè)錯(cuò)誤符號(hào)，碼長(zhǎng)n=15,m=4的RS碼。解：已知t=3,n=15,m=4,所以有碼距：d=2t+1=7個(gè)符號(hào)(28bit)監(jiān)督段：2t=6個(gè)符號(hào)(24bit)信息段：n-6=9個(gè)符號(hào)(36bit)碼長(zhǎng)：n=15個(gè)符號(hào)(60bit)因此該碼是(15,9)RS碼，也可看作是(60,36)二進(jìn)制碼；2022/12/1047一個(gè)可糾t個(gè)符號(hào)錯(cuò)誤的RS碼，有如下2022/12/1048最小距離為d的RS碼生成多項(xiàng)式應(yīng)具有如下形式：

g(x)=(x+a)(x+a2)…(x+ad-1)本例中，d=7g(x)=(x+a)(x+a2)…(x+a6)=x6+a10x5+a14x4+a4x3+a6x2+a9x+a6其中ai是GF(q)中的一個(gè)元素。RS碼生成多項(xiàng)式的次數(shù)總是2t！2022/12/1048最小距離為d的RS碼生成多項(xiàng)式應(yīng)具有2022/12/1049編碼理論

CodingTheory周武旸中國(guó)科學(xué)技術(shù)大學(xué)個(gè)人通信與擴(kuò)頻實(shí)驗(yàn)室2022/12/101編碼理論

CodingT2022/12/1050第三章BCH碼3.1引言3.2BCH碼簡(jiǎn)述3.3有限域3.4BCH碼的編碼3.5BCH碼的譯碼3.6戈雷(Golay)碼3.7Reed-Solomon碼2022/12/102第三章BCH碼3.1引言2022/12/10513.1引言BCH碼是一類(lèi)最重要的循環(huán)碼，能糾正多個(gè)隨機(jī)錯(cuò)誤，它是1959年由Bose、Chaudhuri及Hocquenghem各自獨(dú)立發(fā)現(xiàn)的二元線性循環(huán)碼，人們用他們的名字字頭命名為BCH碼。在前面的討論中，我們所做的只是構(gòu)造一個(gè)碼，然后計(jì)算它的最小距離，從而估計(jì)出它的糾錯(cuò)能力，而在BCH碼中，我們將采用另外一種方法：先說(shuō)明我們希望它能糾錯(cuò)的個(gè)數(shù)，然后構(gòu)造這種碼。2022/12/1033.1引言BCH碼是一類(lèi)最重要的循環(huán)2022/12/10523.2BCH碼簡(jiǎn)述若循環(huán)碼的生成多項(xiàng)式具有如下形式：

g(x)=LCM[m1(x),m3(x),…,m2t-1(x)]其中LCM表示最小公倍式，t為糾錯(cuò)個(gè)數(shù)，mi(x)為素多項(xiàng)式，則由此生成的循環(huán)碼稱為BCH碼，其最小碼距(d0稱為設(shè)計(jì)碼距)，它能糾正t個(gè)隨機(jī)獨(dú)立差錯(cuò)。BCH碼的碼長(zhǎng)n=2m-1或是n=2m-1的因子本原BCH碼非本原BCH碼2022/12/1043.2BCH碼簡(jiǎn)述若循環(huán)碼的生成多項(xiàng)2022/12/1053舉例說(shuō)明例3.1:BCH(15,5)碼，可糾正3個(gè)隨機(jī)獨(dú)立差錯(cuò)，即t=3n=15=2m-1,som=4查不可約多項(xiàng)式表可得m1(x)=(23)8=010011=x4+x+1m3(x)=(37)8=011111=x4+x3+x2+x+1m5(x)=(07)8=000111=x2+x+1這樣g(x)=LCM[m1(x),m3(x),m5(x)]=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)=x10+x8+x5+x4+x2+x+12022/12/105舉例說(shuō)明例3.1:BCH(15,5)2022/12/1054例3.2:BCH(31,16)碼，可糾正3個(gè)隨機(jī)獨(dú)立差錯(cuò)，即t=3n=31=2m-1,som=5查不可約多項(xiàng)式表可得m1(x)=(45)8=100101=x5+x2+1m3(x)=(75)8=111101=x5+x4+x3+x2+1m5(x)=(67)8=110111=x5+x4+x2+x+1這樣g(x)=LCM[m1(x),m3(x),m5(x)]=x15+x11+x10+x9+x8+x7+x5+x3+x2+x+12022/12/106例3.2:BCH(31,16)碼，可2022/12/1055部分不可約多項(xiàng)式表2階173階1134階1233375075階1453755672022/12/107部分不可約多項(xiàng)式表2階173階11342022/12/1056n≤31的本原BCH碼nktg(x)74113151112315727211553246731261453121235513116310765731115542332531673133650472022/12/108n≤31的本原BCH碼nktg(x)2022/12/1057部分非本原BCH碼nkdg(x)1795727211634321125166321671263572149643215231275343255541020412793100100127767007007336730432022/12/109部分非本原BCH碼nkdg(x)1792022/12/10583.3有限域一個(gè)元素個(gè)數(shù)有限的域稱為有限域，或者伽羅華域(Galoisfield);有限域中元素的個(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,a?b=b?a結(jié)合律:(a+b)+c=a+(b+c),a?(b?c)=(a?b)?c和分配律:a?(b+c)=a?b+a?c2022/12/10103.3有限域一個(gè)元素個(gè)數(shù)有限的域稱2022/12/1059可以將GF(p)延伸為一個(gè)含有pm個(gè)元素的域，稱為GF(p)的擴(kuò)展域，表示為GF(pm)，m是一個(gè)非零正整數(shù)。注意：GF(p)是GF(pm)的子集。二進(jìn)制域GF(2)是擴(kuò)展域GF(2m)的一個(gè)子域，類(lèi)似于實(shí)數(shù)域是復(fù)數(shù)域的一個(gè)子域一樣。除了數(shù)字0和1之外，在擴(kuò)展域中還有特殊的元素，用一個(gè)新的符號(hào)a表示。GF(2m)中任何非0元素都可由a的冪次表示。2022/12/1011可以將GF(p)延伸為一個(gè)含有pm個(gè)2022/12/1060有限元素的集合GF(2m)，只能含有2m個(gè)元素，并且對(duì)乘法封閉，其約束條件為：根據(jù)這個(gè)多項(xiàng)式限制條件，任何冪次等于或超過(guò)2m-1的域元素都可降階為下述冪次小于2m-1的元素：這樣，GF(2m)的元素可表示為：2022/12/1012有限元素的集合GF(2m)，只能含有2022/12/1061擴(kuò)展域GF(2m)中的加法在GF(2m)中，將每個(gè)非0元素用多項(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的取值。2022/12/1013擴(kuò)展域GF(2m)中的加法在GF(22022/12/1062域元素基本元素x0x1x20000a0100a1010a2001a3110a4011a5111a6101a7100多項(xiàng)式為f(x)=1+x+x3的GF(8)的元素與基本元素之間的映射2022/12/1014基本元素x0x1x20000a0102022/12/1063有限域中兩個(gè)元素的加法定義為兩個(gè)多項(xiàng)式中同冪次項(xiàng)系數(shù)進(jìn)行模2加，即

ai+aj=(ai,0+aj,0)+(ai,1+aj,1)x+…+(ai,m-1+aj,m-1)xm-1有限域的本原多項(xiàng)式：因?yàn)檫@些函數(shù)用來(lái)定義有限域GF(2m)。一個(gè)多項(xiàng)式是本原多項(xiàng)式的充要條件：一個(gè)m階的不可約多項(xiàng)式f(x)，如果f(x)整除xn+1的最小正整數(shù)n滿足n=2m-1，則該多項(xiàng)式是本原的。2022/12/1015有限域中兩個(gè)元素的加法定義為兩個(gè)多項(xiàng)2022/12/1064例3.3本原多項(xiàng)式的辨別

(1)p1(x)=1+x+x4(2)p2(x)=1+x+x2+x3+x4

分析:(1)通過(guò)驗(yàn)證這個(gè)冪次為m=4的多項(xiàng)式是否能夠整除,但不能整除1≤n<15范圍內(nèi)的xn+1，就可以確定它是否為本原多項(xiàng)式。經(jīng)反復(fù)計(jì)算，p1(x)是本原多項(xiàng)式，p2(x)不是，因?yàn)樗苷齲5+1。2022/12/1016例3.3本原多項(xiàng)式的辨別2022/12/1065部分本原多項(xiàng)式mm31+x+x3111+x2+x1141+x+x4121+x+x4+x6+x1251+x2+x5131+x+x3+x4+x1361+x+x6141+x+x6+x10+x1471+x3+x7151+x+x1581+x2+x3+x4+x8161+x+x3+x12+x1691+x4+x9171+x3+x17101+x3+x10181+x7+x182022/12/1017部分本原多項(xiàng)式mm31+x+x32022/12/1066考慮一個(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來(lái)定義多項(xiàng)式p(x)的根，可寫(xiě)成如下形式：p(a)=02022/12/1018考慮一個(gè)本原多項(xiàng)式定義的有限域的例子2022/12/1067

即1+a+a3=0a3=1+a

這意味著a3可以表示為更低階a項(xiàng)的加權(quán)和。類(lèi)似地有：a4=a*a3=a*(1+a)=a+a2a5=a*a4=a*(a+a2)=a2+a3=1+a+a2a6=a*a5=a*(1+a+a2)=a+a2+a3=1+a2a7=a*a6=a*(1+a2)=a+a3=1=a0所以，有限域GF(23)的8個(gè)元素為{0,a0,a1,a2,a3,a4,a5,a6}

2022/12/1019即1+a+a3=02022/12/1068這8個(gè)元素中哪些是p(x)=0的3個(gè)根呢？我們可通過(guò)枚舉找到！p(a0)=1,a0不是p(a1)=1+a+a3=0,a1是p(a2)=1+a2+a6=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,a42022/12/1020這8個(gè)元素中哪些是p(x)=0的3個(gè)2022/12/1069p(x)=1+x+x3,GF(8)加法運(yùn)算表+a0a1a2a3a4a5a6a00a3a6a1a5a4a2a1a30a4a0a2a6a5a2a6a40a5a1a3a0a3a1a0a50a6a2a4a4a5a2a1a60a0a3a5a4a6a3a2a00a1a6a2a5a0a4a3a102022/12/1021p(x)=1+x+x3,GF(8)2022/12/1070p(x)=1+x+x3,GF(8)乘法運(yùn)算表×a0a1a2a3a4a5a6a0a0a1a2a3a4a5a6a1a1a2a3a4a5a6a0a2a2a3a4a5a6a0a1a3a3a4a5a6a0a1a2a4a4a5a6a0a1a2a3a5a5a6a0a1a2a3a4a6a6a0a1a2a3a4a52022/12/1022p(x)=1+x+x3,GF(8)2022/12/1071如果GF(p)上的所有元素(除0外)都可表示為某元素a的冪，則a稱為GF(p)上的本原元。例3.4考慮GF(5)，因?yàn)閜=5是個(gè)素?cái)?shù)，模算數(shù)可以進(jìn)行。考慮該域上的元素2，

20=1(mod5)=1,21=2(mod5)=222=4(mod5)=4,23=8(mod5)=3

因此，所有GF(5)上的非零元素，即{1,2,3,4}都可以表示成2的冪，故2是GF(5)上的本原元；大家可以驗(yàn)證，3也是GF(5)上的本原元。2022/12/1023如果GF(p)上的所有元素(除0外)2022/12/1072GF(pm)中，在模p(x)運(yùn)算下的擴(kuò)域上，x所表示的元素是本原元。例如:用本原多項(xiàng)式p(x)=1+x+x3

來(lái)構(gòu)造GF(8)，設(shè)GF(8)上的本原元為a,通過(guò)將a的冪模p(a)得到GF(8)上的所有元素。a的冪GF(8)上的元素a01a1aa2a2a3a+1a4a2+aa5a2+a+1a6a2+12022/12/1024GF(pm)中，在模p(x)運(yùn)算下的2022/12/1073定理:設(shè)b1,b2,…,bp-1為GF(p)上的非零域元素，則xp-1+1=(x+b1)(x+b2)…(x+bp-1)從循環(huán)碼知識(shí)我們知道，為了找到分組長(zhǎng)度為n的循環(huán)碼的生成多項(xiàng)式，首先分解xn+1,因此xn+1可以表示為多個(gè)因子的乘積，即

xn+1=f1(x)f2(x)…fw(x)在擴(kuò)展域GF(pm)中，n=pm-12022/12/1025定理:設(shè)b1,b2,…,bp-1為G2022/12/1074例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,因此我們可以寫(xiě)為x7+1=(x+1)(x+a)(x+a+1)(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)2022/12/1026例3.5考慮GF(2)和它的擴(kuò)展域2022/12/1075極小多項(xiàng)式fi(x)對(duì)應(yīng)的根元素用a的冪表示x+11a0x3+x+1a,a2和a2+aa1,a2,a4x3+x2+1a+1,a2+1和a2+a+1a3,a6,a52022/12/1027極小多項(xiàng)式fi(x)對(duì)應(yīng)的根元素用a2022/12/10763.4BCH碼的編碼對(duì)一個(gè)分組長(zhǎng)度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ò)誤的碼的生成多項(xiàng)式為

g(x)=LCM[f1(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)式。2022/12/10283.4BCH碼的編碼對(duì)一個(gè)分組長(zhǎng)度2022/12/1077例3.6考慮GF(2)上的本原多項(xiàng)式p(a)=a4+a+1，我們將以此來(lái)構(gòu)造GF(16),設(shè)a為本原元。GF(16)上以a的冪表示形式的元素及它們對(duì)應(yīng)的極小多項(xiàng)式為：a的冪GF(16)的元素極小多項(xiàng)式a01x+1a1ax4+x+1a2a2x4+x+1a3a3x4+x3+x2+x+1a4a+1x4+x+1a5a2+ax2+x+1a6a3+a2x4+x3+x2+x+1a7a3+a+1x4+x3+1a8a2+1x4+x+1a9a3+ax4+x3+x2+x+1a10a2+a+1x2+x+1a11a3+a2+ax4+x3+1a12a3+a2+a+1x4+x3+x2+x+1a13a3+a2+1x4+x3+1a14a3+1x4+x3+12022/12/1029例3.6考慮GF(2)上的本原多項(xiàng)2022/12/1078我們希望確定糾單錯(cuò)的BCH碼的生成多項(xiàng)式，即t=1且n=15。由前面公式可知，一個(gè)BCH碼的生成多項(xiàng)式由LCM[f1(x),f2(x),…,f2t(x)]給出，利用前面的表我們可獲得極小多項(xiàng)式f1(x)和f2(x)，于是有：

g(x)=LCM[f1(x),f2(x)]=LCM[(x4+x+1),(x4+x+1)]=x4+x+1

因?yàn)閐egg(x)=n-k，可得n-k=4，所以k=11,于是我們得到糾單一錯(cuò)誤的BCH(15,11)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=3，可以計(jì)算該碼的實(shí)際最小距離d*也是3。

2022/12/1030我們希望確定糾單錯(cuò)的BCH碼的生成多2022/12/1079

如果希望糾2個(gè)錯(cuò)誤，且n=15。則其生成多項(xiàng)式為

g(x)=LCM[f1(x),f2(x),f3(x),f4(x)]=LCM[(x4+x+1),(x4+x+1),(x4+x3+x2+x+1),(x4+x+1)]=(x4+x+1)(x4+x3+x2+x+1)=x8+x7+x6+x4+1

因?yàn)閐egg(x)=n-k=8，所以k=7,于是我們得到糾2個(gè)錯(cuò)誤的BCH(15,7)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=5，可以計(jì)算該碼的實(shí)際最小距離d*也是5。2022/12/1031如果希望糾2個(gè)錯(cuò)誤，且n=152022/12/1080

如果希望糾3個(gè)錯(cuò)誤，且n=15。則其生成多項(xiàng)式為

g(x)=LCM[f1(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)閐egg(x)=n-k=10，所以k=5,于是我們得到糾3個(gè)錯(cuò)誤的BCH(15,5)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=7，可以計(jì)算該碼的實(shí)際最小距離d*也是7。2022/12/1032如果希望糾3個(gè)錯(cuò)誤，且n=152022/12/1081

如果希望糾4個(gè)錯(cuò)誤，且n=15。則其生成多項(xiàng)式為

g(x)=LCM[f1(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)閐egg(x)=n-k=14，所以k=1。(簡(jiǎn)單的重復(fù)碼)。于是我們得到糾4個(gè)錯(cuò)誤的BCH(15,1)碼的生成多項(xiàng)式。該碼的設(shè)計(jì)距離為d=2t+1=9，可以計(jì)算該碼的實(shí)際最小距離d*是15。在此情況下，設(shè)計(jì)距離不等于實(shí)際最小距離，碼設(shè)計(jì)得太過(guò)度了，該碼實(shí)際可糾(d*-1)/2=7個(gè)隨機(jī)錯(cuò)誤！2022/12/1033如果希望糾4個(gè)錯(cuò)誤，且n=152022/12/10823.5BCH碼的譯碼根據(jù)生成多項(xiàng)式，可以構(gòu)造出快速的硬件編碼器，而對(duì)于BCH碼的譯碼，由于它是循環(huán)碼的一個(gè)子類(lèi)，任何對(duì)循環(huán)碼的標(biāo)準(zhǔn)譯碼過(guò)程都適用于BCH碼。下面我們主要討論專門(mén)針對(duì)BCH碼的更高效的算法:

Gorenstein-zierler譯碼算法設(shè)c(x)為發(fā)送碼字多項(xiàng)式，e(x)為錯(cuò)誤多項(xiàng)式，則接收到的多項(xiàng)式為r(x)=c(x)+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)=0r(yi)=c(yi)+e(yi)=e(yi),i=1,2,…,w2022/12/10343.5BCH碼的譯碼根據(jù)生成多項(xiàng)式2022/12/1083假設(shè)BCH碼是根據(jù)一個(gè)域元素a來(lái)構(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ò)誤，其中0≤v≤t。設(shè)錯(cuò)誤發(fā)生在位置i1,i2,…,iv,則錯(cuò)誤多項(xiàng)式可寫(xiě)為其中為第k個(gè)錯(cuò)誤的大小，對(duì)二元碼，2022/12/1035假設(shè)BCH碼是根據(jù)一個(gè)域元素a來(lái)構(gòu)造2022/12/1084對(duì)糾錯(cuò)問(wèn)題，我們必須知道兩件事：(1)錯(cuò)誤在哪里發(fā)生了，即錯(cuò)誤的位置(2)錯(cuò)誤程度因此，未知量為i1,i2,…,iv和,,…,,它們分別表明錯(cuò)誤發(fā)生的位置和程度。伴隨式可通過(guò)對(duì)接收到的關(guān)于a的多項(xiàng)式計(jì)算得到：定義錯(cuò)誤程度和錯(cuò)誤位置,k=1,2,…,v。其中ik為第k個(gè)錯(cuò)誤的位置，Xk是與這個(gè)位置相關(guān)的域元素。2022/12/1036對(duì)糾錯(cuò)問(wèn)題，我們必須知道兩件事：2022/12/1085現(xiàn)在伴隨多項(xiàng)式可寫(xiě)為

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:2022/12/1037現(xiàn)在伴隨多項(xiàng)式可寫(xiě)為2022/12/1086定義錯(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)過(guò)一系列代數(shù)變換，我們可得如下矩陣：錯(cuò)誤定位多項(xiàng)式的系數(shù)可通過(guò)對(duì)伴隨式矩陣M求逆得到！2022/12/1038定義錯(cuò)誤定位多項(xiàng)式錯(cuò)誤定位多項(xiàng)式的系2022/12/1087BCH碼的譯碼步驟作為測(cè)試值，令v=t，計(jì)算伴隨矩陣M的行列式。如果行列式的值為零，令v=t-1,再一次計(jì)算M的行列式。重復(fù)這個(gè)過(guò)程直到找到一個(gè)v值，使伴隨矩陣的行