現(xiàn)代編碼理論：第七章 BCH碼

第七章BCH碼一、在擴(kuò)展域描述和構(gòu)成循環(huán)碼

Fq g(x)

=f1(x)f2(x)….fj(x)存在最小分裂域 Fqm g(x)=(x-1)(x-2)…(x-j)….(x-n-k)

素多項(xiàng)式最小多項(xiàng)式g(x)=LCM(m1(x),m1(x),…,mj(x),….,mn-k(x))m1(x)m2(x)mj(x)mn-k(x)最小多項(xiàng)式如果j1，j2是共扼根，則mj1(x)=mj2(x)一、在擴(kuò)展域從描述和構(gòu)成循環(huán)碼定理1：設(shè)Fq上的循環(huán)碼的生成多項(xiàng)式g(x)在最小分裂域Fqm上的根為1， 2，…,n-k。則Fq上多項(xiàng)式c(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0是一個(gè)碼字多項(xiàng) 式的充要條件是HcT=0,其中:

計(jì)算在Fqm上進(jìn)行。證明：（一）必要性 設(shè)c(x)=a(x)g(x)=cn-1xn-1+cn-2xn-2+…+c1x+c0

c(j)=cn-1j

n-1+cn-2j

n-2+…+c1j+c0=a(j)g(j)=a(j)*0=0，(j=1,2,…,n-k)

(二）充分性

設(shè)c(x)滿足HcT=0，c(x)=g(x)q(x)+s(x)，對(duì)于j=1,2,…,n-k，

c(j)=g(j)q(j)+s(j)=0*q(j)+s(j)=cn-1j

n-1+cn-2j

n-2+…+c1j+c0=0

則s(j)=0，即s(x)在Fqm上的根為1，2，…,n-k，又s(x)<g(x),所以s(x)=0

即c(x)=g(x)q(x)，所以c(x)是碼字多項(xiàng)式。(1)n-1(1)t(1)0(j)n-1(j)0線性相關(guān)把H中的jt(j=1,…n-k,t=0,..n-1）用Fq上的m重表示共扼根(i)t去掉線性相關(guān)的行一、在擴(kuò)展域從描述和構(gòu)成循環(huán)碼定理2:若H在Fqm中第j行元素和第i行相應(yīng)元素為q次冪，則在Fq

中，第j行分裂的m行與第i行分裂的m行之間，行線性相關(guān)。已知g(x)在擴(kuò)展域Fqm中根，生成Fq上的循環(huán)碼Fqm={0,,2,…,qm-1}設(shè)i1,i2,…,in-k為g(x)的根，且：g(x)根 共扼根系 級(jí) 最小多項(xiàng)式 i1 R

i1 ei1 mi1(x)

i2 R

i2 ei2 mi2(x)

… … … ….in-k R

in-k ein-k min-k(x)

而g(x)|xn-1,i1,i2,…,in-k也為xn-1的根，即(ik)n=1,由循環(huán)群的性質(zhì)（a為n級(jí)元素，則am=e

n|m),得i1,i2,…,in-k的級(jí)數(shù)為n的因數(shù)(必要條件)，可取n=LCM(ei1,ei2,…,ein-k)方法1：g(x)=LCM(mi1(x)

,mi2(x)

,…,min-k(x)

)方法2：直接由構(gòu)造H。i1,i2,…,in-k中共扼根屬于同一共扼根系，即Ri1,R

i2,…,R

in-k中可能重復(fù)，而mi1(x),m

i2(x),…,m

in-k(x)有相同。去掉重復(fù)部分一、在擴(kuò)展域從描述和構(gòu)成循環(huán)碼方法1：g(x)=LCM(mi1(x)

,mi2(x)

,…,min-k(x)

)方法2：直接由構(gòu)造H。

在每個(gè)共扼根系選取一個(gè)共扼根（一般選次數(shù)最小的，計(jì)算簡(jiǎn)單）,得

j1,j2,…,jw,構(gòu)成H:把H中的j1,j2,…,jw轉(zhuǎn)為m重，H仍有線性相關(guān)的行，在這些行中保留一行，其余去掉。一、在擴(kuò)展域從描述和構(gòu)成循環(huán)碼例（例5.5)：求以F16中,2,3,4,5為根的F2上的循環(huán)碼。分析：,2,3,4,5同一共扼根系,級(jí)15，最小多項(xiàng)式x4+x+1另一共扼根系,級(jí)5，最小多項(xiàng)式x4+x3+x2+x+1另一共扼根系,級(jí)3，最小多項(xiàng)式x2+x+1g(x)=LCM(x4+x+1,x4+x3+x2+x+1,x2+x+1)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1) (素多項(xiàng)式）=x10+x8+x5+x4+x2+x+1n=LCM(15,5,3)=15g(x)=n-k=15-k=10,k=5與課本不同，可按個(gè)人習(xí)慣全0，去掉相同，去掉1行共43-2=10行二、二進(jìn)制BCH碼若g(x)在擴(kuò)展域Fqm上的根為i1,i2,…,in-k，則若i1,i2,…,in-k中含有1,2,…,d-1,則抽這d-1行和任意d-1列，得每一列提取公因式，得二、二進(jìn)制BCH碼若i1,i2,…,in-k中含有1,2,…,d-1,則抽這d-1行和任意d-1列，得每一列提取公因式，得范得蒙行列式，若g(x)沒(méi)有重根，即ju，jv,則行列式不為零，行列式對(duì)應(yīng)的矩陣滿秩，原矩陣任意d-1列線性無(wú)關(guān)，所以碼的距離至少為d。定理3：Fq上多項(xiàng)式xn-1在最小分裂域無(wú)重根的充要條件為

(n,q)=1。二、二進(jìn)制BCH碼2.定義：設(shè)F2上循環(huán)碼的生成多項(xiàng)式g(x)在擴(kuò)展域F2m上的根含有,2, 3,

…,d-1(其中為本原元），則這種循環(huán)碼稱(chēng)為二元（狹義）本 原BCH碼3.定理4：本原BCH碼的最小距離dmind.4.BCH碼設(shè)計(jì)步驟1）給定n,t,找合適的F2m，使n=2m-1或n|2m-1,且(n,2m)=1(保證無(wú)重根);2）選,2,3,

…,2t為根，把它們組成不同的根系R1,R2,…,Rj,…,Rs,

對(duì)于每一根系Rj，求其最小多項(xiàng)式mj(x),則

g(x)=m1(x)m2(x)…mj(x)…ms(x)

g(x)=n-kmt(mj(x)m)

n=LCM(e1,e2,…,ej,…,es) 最多2t個(gè)，而j和2j屬于同一共扼根系，偶數(shù)下標(biāo)一律取消，所以st。ej為Rj根系的根的級(jí)數(shù)，含本原元。二、二進(jìn)制BCH碼例：求n=15,能糾t=2,3,4,5,6,7個(gè)錯(cuò)的F2上的本原BCH碼(1)t=2,g(x)的根為,2,3,4同一共扼根系,階15，最小多項(xiàng)式(本原多項(xiàng)式)x4+x+1另一共扼根系,階15/(15,3)=5，方次數(shù)4最小多項(xiàng)式(4次素多項(xiàng)式）x4+x3+x2+x+1g(x)=(x4+x+1)(x4+x3+x2+x+1)=x8+x7+x6+x4+1(15,7,5)BCH碼(2)t=3,g(x)的根為,2,3,4,5,6同一共扼根系,級(jí)15，最小多項(xiàng)式(本原多項(xiàng)式)x4+x+1同一共扼根系,級(jí)15/(15,3)=5，方次數(shù)4，最小多項(xiàng)式(4次素多項(xiàng)式）x4+x3+x2+x+1另一共扼根系,級(jí)15/(15,5)=3，方次數(shù)2，最小多項(xiàng)式(2次素多項(xiàng)式）x2+x+1g(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)=x10+x8+x5+x4+x2+x+1(15,5,7)BCH碼二、二進(jìn)制BCH碼(3)t=4,g(x)的根為,2,3,4,5,6,7,8同一共扼根系,階15，最小多項(xiàng)式(本原多項(xiàng)式)x4+x+1同一共扼根系,階15/(15,3)=5，方次數(shù)4，最小多項(xiàng)式(4次素多項(xiàng)式）x4+x3+x2+x+1另一共扼根系,階15/(15,5)=3，方次數(shù)2，最小多項(xiàng)式(2次素多項(xiàng)式）x2+x+1另一共扼根系,階15/(15,7)=15，方次數(shù)4，最小多項(xiàng)式(本原多項(xiàng)式）x4+x3+1g(x)=(x4+x+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x3+1)=x14+x13+x12+…+x+1h(x)=x+1h*(x)=x+1g(x)的次數(shù)已到極限，而t=5,6,7必須以g(x)為因子，所以等于g(x)。g(x)的根為,2,3,4,5,6,7,8,9,10同一共扼根系

同一共扼根系

同一共扼根系

同一共扼根系

重復(fù)碼三、多元BCH碼當(dāng)n很大時(shí)，可以查表(p255-259),其中b和z分別表該碼糾突發(fā)錯(cuò)誤能力和最佳程度5.BCH碼的擴(kuò)展三、多元BCH碼定義：若Fq上循環(huán)碼的生成多項(xiàng)式g(x)在擴(kuò)域Fqm上的根含有

m0,m0+1,…,m0+d-2,則稱(chēng)為q元BCH碼，d稱(chēng)為設(shè)計(jì)距離。

m0=0或1，為狹義BCH碼。

g(x)=LCM(m0(x),m1(x),…,md-1(x)) n=LCM(e0,e1,…,ed-2)定理5(定理7.1.1,7.1.9)：BCH碼的最小距離ddminqd+q-2(下限稱(chēng)為BCH限） 尚有各種距離限，HT限,CHT限,ROOS限,GR限，ER限，LW限等，力圖縮小dmin的范圍。下面給出dmin=d的兩個(gè)充分條件。定理6(定理7.1.7)：若二進(jìn)制BCH碼的設(shè)計(jì)距離d|n,則dmin=d。定理7(定理7.1.8)：若Fq上BCH碼的碼長(zhǎng)n=qm-1,其設(shè)計(jì)距離d=qh-1,則dmin=d三、多元BCH碼漢明碼，實(shí)際距離等于設(shè)計(jì)距離（23,12)戈萊碼，典型的非本原元BCH碼，n<2n-1g1(x)=x11+x9+x7+x6+x5+x+1或g2(x)=x11+x10+x7+x6+x5+x4+x2+1d=5,dmin=7其擴(kuò)展碼（24，12，8）用于ITU-TH.324中ITU-TH.261n×384kb/s可視音頻業(yè)務(wù),(511,493,11)本原BCH碼n=29-1=511國(guó)際無(wú)限尋呼標(biāo)準(zhǔn)（32，21，6）擴(kuò)展本原BCH碼模擬蜂窩移動(dòng)通信系統(tǒng)TACS和AMPS采用（63，51，5）本原BCH碼，下行縮短為（40，28），上行縮短為（48，36）。日本數(shù)字蜂窩移動(dòng)通信PDC采用(15,11)BCH碼和縮短的（12,8)和（14，10,3）BCH碼，生成多項(xiàng)式g(x)=x4+x+1 H.324是用28.8kb/s調(diào)制解調(diào)器在模擬電話線連接的設(shè)備之間共享圖像、聲音和數(shù)據(jù)。H.324系列是一個(gè)低位速率多媒體通信終端標(biāo)準(zhǔn)，在它的旗號(hào)下的標(biāo)準(zhǔn)包括：

H.263：電視圖像編碼標(biāo)準(zhǔn)，壓縮后的速率為20kb/s。H.223：低位速率多媒體通信的多路復(fù)合協(xié)議。H.245：多媒體通信終端之間的控制協(xié)議。T120：實(shí)時(shí)數(shù)據(jù)會(huì)議標(biāo)準(zhǔn)（可視電話應(yīng)用中不一定是必須的）。

里德－索洛蒙60年構(gòu)造Reed－solomonFqFqm1.基本概念令m=1定義：Fq(q≠2)上碼長(zhǎng)N=q-1的本原BCH碼稱(chēng)為RS碼

g(x)的根：αm0，αm0＋1

，…，αm0+d-2最小多項(xiàng)式x-αm0，x-αm0＋1

，…，x-αm0+d-2g(x)=(x-αm0)(x-αm0＋1

)···(x-αm0+d-2)一般取m0=1,得g(x)=(x-α)(x-α2)···(x-αd-1)n=LCM(e1,e2,…,ed-1),

e1,e2,…,ed-1分別為α,

α2,

…,

α2的級(jí)數(shù),其中,α為本原元,得e1=q-1,所以:n=q-1n-k=?og(x)=d-1↓四、RS碼----基本概念碼域（符號(hào)域）與根域一樣的多元BCH碼d=n-k+1H的秩為n-k，所以線性碼的最小距離dmin上限為n-k+1n-k+1

dmind=n-k+1,所以d=dmin

=n-k+1,RS碼達(dá)到上限k=n-d+1=q-1-d+1=q-d∴生成（q-1，q-d，d）循環(huán)碼列向量所張開(kāi)的空間的維數(shù)存在n-k線性無(wú)關(guān)的列不存在n-k+1線性無(wú)關(guān)的列由定理4，dmind稱(chēng)為Singleton限。達(dá)到Singleton限的碼稱(chēng)為極大最小距離可分碼（MDS)。定理7也支持非系統(tǒng)碼：系統(tǒng)碼：例：構(gòu)造F8上d=5的RS碼F8見(jiàn)表4-1n=8-1=7,k=8-5=3,(7,3,5)g(x)=(x-α)(x-α2)(x-α3)(x-α4)經(jīng)運(yùn)算F8上的加法、乘法表式化為多項(xiàng)式運(yùn)算g(x)=x4+α3x3+x2+αx+α3四、RS碼h(x)=(x7-1)/g(x)=x3+α3x2+α2x+α42編碼電路q進(jìn)制(第五章介紹)↓q=pm，多項(xiàng)式或m元，當(dāng)p＝2用二進(jìn)制實(shí)現(xiàn)乘g(x)電路非系統(tǒng)碼除g(x)電路系統(tǒng)碼}n-k級(jí)基于h(x)電路：系統(tǒng)碼：n級(jí)四、RS碼---編碼電路h(x)=(x7-1)/g(x)=x3+α3x2+α2x+α4寄存器3重，所以為3級(jí)乘法：任一元素可以表示為自然基1,α,α2的線性組合？(p127例4.11下面一段，但課本沒(méi)有說(shuō)清楚）因?yàn)橛枚囗?xiàng)式a2x2+a1x+a0表示,而x為本原元,換為冪表示法a2α2+a1α+a0用二進(jìn)制電路實(shí)現(xiàn)(p172-174)乘另一元素如α2則α2(a2α2+a1α+a0)=a2α4+a1α3+a0α2

表示為=a2(α2+α)+a1(α+1)+a0α2

=(a2+a0)α2+(a2+a1)α+a1↘↓同理，乘α3，則α3

(a2α2+a1α+a0)=a2α5+a1α4+a0α3=(a2+a1)α2+

(a2+a1+a0)

α+(a2+a0)

乘α4，則α4(a2α2+a1α+a0)=(a2+a1+a0)α2+(a1+a0)α+(a2+a1)替代課本有錯(cuò)四、RS碼---頻域編碼3.頻域編碼信息多項(xiàng)式m(x)=mk-1xk-1+mk-2xk-2+…+m1x+m0

c(x)=m(αq-2)xq-2+m(αq-3)xq-3+…+m(α)x+m(1)可證，c(x)以α,α2,…,αq-k

為根,

d=q-k頻域？有限域的離散傅立葉變換(p178,定義5.8.1):GF(q)多項(xiàng)式a(x)在GF(qm)上的譜多項(xiàng)式A(z)=a(αn-1)zn-1+a(αn-2)zn-2+…+a(α)z+a(1),其中=a(αi)，α為GF(qm)中的n級(jí)單位原根。譜多項(xiàng)式也稱(chēng)MS(Mattson-Solomon)多項(xiàng)式，稱(chēng)A=(An-1,…,A1,A0)為a=(an-1,…,a1,a0)的GF(qm)離散傅立葉變換。數(shù)字信號(hào)處理中，x(n)的離散傅立葉變換X(k)為：αST=H·RT=H·ETS'=H'·ET

====五、BCH碼的一般譯碼方法BCH譯