糾錯碼Lecture12-有限域(II)

1、信道編碼理論信道編碼理論邢莉娟，李卓，西安電子科技大學(xué)邢莉娟，李卓，西安電子科技大學(xué)Lecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論2有限域的加法結(jié)構(gòu)有限域的加法結(jié)構(gòu)有限域的代數(shù)結(jié)構(gòu)有限域的代數(shù)結(jié)構(gòu)多項式的因式分解多項式的因式分解正規(guī)基和對偶基正規(guī)基和對偶基Lecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論3域的特征域的特征 滿足滿足ne=0的最小的最小n值為值為域的特征域的特征，這里，這里e為乘法單位元，為乘法單位元，0為域的零為域的零元，元，n取自正整數(shù)取自正整數(shù) GF(p)的特征為的特征為p 每

2、一個域的特征或為素數(shù)，或為每一個域的特征或為素數(shù)，或為 域的域的特征特征說明了域中說明了域中加法運(yùn)算的循環(huán)性加法運(yùn)算的循環(huán)性，而域中元素的，而域中元素的級級則說明則說明了了乘法運(yùn)算的循環(huán)性乘法運(yùn)算的循環(huán)性。元素的周期元素的周期 對域中元素對域中元素a0，滿足，滿足na=0的最小的最小n值為值為a的的周期周期。（注意對于域。（注意對于域而言，而言，在加法上用周期，在乘法上用級在加法上用周期，在乘法上用級） 域中非域中非0元的周期都相同，且與域的特征相等元的周期都相同，且與域的特征相等在在p特征域中，域整數(shù)全體（形如特征域中，域整數(shù)全體（形如ne的全體域元素的全體域元素: n=, -2, -1,

3、0 ,1, 2, ）構(gòu)成）構(gòu)成p階素子域，它與模階素子域，它與模p的整數(shù)域的整數(shù)域GF(p)同構(gòu)同構(gòu)0,1,2 1,(1) 10,1,2,1pRppLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論4GF(p)為為GF(pm)的的基域基域，GF(pm)為為GF(p)的的擴(kuò)域，擴(kuò)域，GF(pm)的特征為的特征為p。如如GF(22)的的4個元素個元素: 00, 01, 10, 11中的每一個特征均為中的每一個特征均為2；故；故GF(22)是一個特征為是一個特征為2的域的域在特征為在特征為p的域中，恒有的域中，恒有 其中，其中，a是域中的任一元素是域中的

4、任一元素在在p特征域中，對任何域元素特征域中，對任何域元素a, b，恒有，恒有在在p特征域中，任一元素的級均不是特征域中，任一元素的級均不是p的倍數(shù)的倍數(shù)pppxaxapppababLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論5若若w1, w2, , wk是是p特征域的元素，則對于一切自然數(shù)特征域的元素，則對于一切自然數(shù)n，恒有恒有若若k是是p特征域的域整數(shù)，則對于一切自然數(shù)特征域的域整數(shù)，則對于一切自然數(shù)n，必滿足方，必滿足方程程 ，即，即Fermat定理定理：對：對GF(pm)中的任何元素中的任何元素w，恒有，恒有任何小于素數(shù)任何小于素數(shù)

5、p的整數(shù)的整數(shù)b滿足滿足 ，如，如p特征域中，元素為域整數(shù)的充要條件是滿足特征域中，元素為域整數(shù)的充要條件是滿足npxxnpkk11nnpkkpiiiiwwmpww(mod )pbbp621(mod7)0pxxLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論6若若 為方程為方程 的根，則的根，則GF(pm)中互不相同的中互不相同的m個元素個元素 是是f(x)的的m個不同的根。這個不同的根。這m個根稱為方程個根稱為方程f(x)的的共軛根系共軛根系能滿足能滿足pm=1(mod n)的最小整數(shù)的最小整數(shù)m，稱為，稱為p對模對模n的方次數(shù)的方次數(shù)系數(shù)取自

6、系數(shù)取自GF(p)的，以的，以w為根的所有首一多項式中，次數(shù)為根的所有首一多項式中，次數(shù)最低的稱為最低的稱為w的最小多項式的最小多項式m(x)，w的最小多項式的次數(shù)的最小多項式的次數(shù)m稱為稱為w的的次數(shù)次數(shù)，稱，稱w為為m次域元素次域元素GF()mwp0( )0; GF( )kiiiif xf xfp21, , , , mpppw wwwLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論7性質(zhì)性質(zhì) m(x)在在GF(p)上不可約上不可約 若若w也是也是f(x)的根，則的根，則m(x)可整除可整除f(x) 若若w取自取自GF(pm)，則有，則有m(x

7、)可整除可整除設(shè)設(shè)w是是p特征域特征域GF(pm)中的中的n級元素，而級元素，而pm=1(mod n)，則，則w的最小多項式的最小多項式m(x)是是m次多項式，且次多項式，且在在GF(pm)域中完全分解域中完全分解m(x)為一次因式之積，所以稱為一次因式之積，所以稱GF(pm)為為m(x)的的分離域分離域或或分解域分解域mpxx10( )impim xxwLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論8在在GF(pm)中，以本原元為根的最小多項式稱為該域的中，以本原元為根的最小多項式稱為該域的本原多項式本原多項式GF(pm)的本原多項式的根級數(shù)

8、均為的本原多項式的根級數(shù)均為pm-1，且本原多項式必為，且本原多項式必為m次多項次多項式式w為最小多項式的根，若為最小多項式的根，若w是特征為是特征為p的有限域的有限域F上的上的m次域元素，則次域元素，則所有小于所有小于m次的多項式次的多項式f(x)將將w代入，得到的集合構(gòu)成代入，得到的集合構(gòu)成pm階子域。（以階子域。（以最小多項式為模）最小多項式為模） 如：如：GF(2)上上f(x)=x3+x+1，以，以GF(23)上的元素上的元素w為根，則為根，則GF(2)上上小于小于3次次w多項式全體構(gòu)成多項式全體構(gòu)成23階子域：階子域：0, 1, w, w +1, w 2, w 2 +1, w 2 +

9、w, w 2 +w +1對于對于m次元素次元素w，有，有1, w, w2, , wm-1線性無關(guān)，可作為域空間的線性無關(guān)，可作為域空間的基。基。 可以由可以由GF(p)上的一個上的一個m次本原或既約多項式，用它的根次本原或既約多項式，用它的根w構(gòu)成的構(gòu)成的這組基底的線性組合，構(gòu)造一個這組基底的線性組合，構(gòu)造一個GF(pm)有限域有限域Lecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論9定義定義設(shè)設(shè)GF(p)上的上的m次多項式次多項式 則則 稱為稱為互反多項式互反多項式例：例：性質(zhì)性質(zhì)若若為為f(x)的根，則的根，則-1為為f*(x)的根的根若若f(

10、x)既約，則既約，則f*(x)也為既約；反之亦然也為既約；反之亦然若若f(x)為本原多項式，則為本原多項式，則f*(x)也為本原多項式；反之亦然也為本原多項式；反之亦然0100( ) ,0mkmkmmkf xa xaa xa xaa*10100( )mmmkm kmmkkmkkfxxa xa xa xa xa31( )1f xxx*32( )1fxxxLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論10定義定義設(shè)設(shè)f(x) Fpx, f(0) 0（即（即x !| f(x) ），則），則f(x)|(xl-1)的最的最小正整數(shù)小正整數(shù)l，稱為，稱為f

11、(x)的的周期周期（或（或指數(shù)指數(shù)），記為），記為p(f)性質(zhì)性質(zhì)f(x)的周期的周期l是以是以f(x)為模所構(gòu)成多項式剩余類環(huán)中乘法為模所構(gòu)成多項式剩余類環(huán)中乘法群內(nèi)元素群內(nèi)元素 之級之級f(x) Fpx, f(0) 0，則，則f(x)|(xl-1)的充要條件是的充要條件是p(f)|l多項式多項式(xm-1)|(xn-1)的充要條件是的充要條件是m|n若若f(x)是是Fpx中中m次既約多項式，則次既約多項式，則f(x)之周期之周期p(f)等于等于f(x)在在GF(pm)中的根的級中的根的級(mod( )xf xLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理

12、論信道編碼理論11性質(zhì)性質(zhì)(cont.)GF(p)上多項式上多項式f(x)的標(biāo)準(zhǔn)分解式若為的標(biāo)準(zhǔn)分解式若為 則則f(x)的周期的周期 式中式中 是是x的最小整數(shù)的最小整數(shù)1( )( )ikmiif xfx( )Rp fnp12LCM,knn nn(), 1,2,iinp fik12logmax,pkRm mmx Lecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論12ExampleGF(2)上的多項式上的多項式 因為因為 以以5級元素為根級元素為根 以以15級元素為根級元素為根4324( )(1)(1)f xxxxxxx4321xxxx41xx2lo

13、g max(1,1)0R LCM(15,5)15n 0( )15 215p f (5)432(15)87543434( )1( )1(1)(1)QxxxxxQxxxxxxxxxx Lecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論13有限域的階必為其特征（素數(shù)）之冪有限域的階必為其特征（素數(shù)）之冪設(shè)設(shè)f(x)為為p階有限域階有限域GF(p)上的一個上的一個d次既約多項式，則多項次既約多項式，則多項式剩余類集合式剩余類集合Fpx/f(x)構(gòu)成構(gòu)成pd階有限域階有限域GF(pd) 。即。即GF(pd)是是GF(p)的擴(kuò)域，且的擴(kuò)域，且f(x)在在GF(

14、pd)內(nèi)有根內(nèi)有根GF(pr)含有子域含有子域GF(ps)的充要條件是的充要條件是s|r若若 GF(pr) ，則，則 GF(ps)中的充要條件是中的充要條件是 。特。特別是在任何域中若別是在任何域中若 ，則，則是是0或或1p階有限域上的每一個階有限域上的每一個d次首一既約多項式，皆能整次首一既約多項式，皆能整除除 ，只要，只要d|msp2mpxxLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論14系數(shù)取自系數(shù)取自GF(p)上的多項式上的多項式 =所有次數(shù)除盡所有次數(shù)除盡m的的GF(p)上的首上的首一既約多項式之積一既約多項式之積 如：如：x4-x

15、=x(x+1)(x2+x+1)若若f(x)為為GF(p)上的上的m次既約多項式，且次既約多項式，且m|d，則任何，則任何pd階有限域必含有階有限域必含有f(x)的全部根的全部根若若d=m，則，則m次首一既約多項式次首一既約多項式f(x)的全部根在的全部根在GF(pm)中，稱中，稱GF(pm)為為f(x)的包含所有根的的包含所有根的最小擴(kuò)域最小擴(kuò)域，稱為，稱為f(x)的的分裂域分裂域或或分解域分解域例：例：GF(2)上的既約多項式上的既約多項式 必在必在GF(24)上完全分裂，上完全分裂，但不能在任何中間域但不能在任何中間域GF(22)完全分裂完全分裂mpxx4( )1f xxx2484( )(

16、)()()(); GF(2 )f xxxxxLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論15GF(p)上上m次既約多項式的數(shù)目是次既約多項式的數(shù)目是 式中式中 為為Mobius函數(shù)函數(shù)例：例： GF(2)上上3次既約多項式的數(shù)目次既約多項式的數(shù)目 分別為分別為( )d|1( )mdmdd mId pm31311(1)2(3)2(82)233I323( )1, 1f xxxxxLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論16m重、多項式剩余類以及重、多項式剩余類以及多項式之間均同構(gòu)，都多項式之

17、間均同構(gòu)，都可用來表示可用來表示pm階有限域階有限域0122230 0 0 0001 1 001 010 100 1 1+ xxx422522622 011 + 110 1 1+ + 111 1 1+ 101xxxxx3( )1f xxxLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論17分解分解注意到注意到22=1(mod 3) Q(3)(x)既約既約24=1(mod 5) Q(5)(x)既約既約24=1(mod 15) Q(15)(x)非既約，進(jìn)一步分解為（待定系數(shù)非既約，進(jìn)一步分解為（待定系數(shù)法）法）16xx1615(1)(3)(5)(15

18、)(1)(3)2(5)432(15)875431( )( )( )( )( )(1)( )1( )1( )1xxx xxQx Qx Qx QxQxxQxxxQxxxxxQxxxxxx(15)434( )11QxxxxxLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論18Q(15)(x)的既約因式必為的既約因式必為 x4+Ax3+Bx2+Cx+11不是不是15級元素級元素A+B+C=1 1) A=B=C=1 x4+x3+x2+x+1= Q(5)(x); rejected 2) A、B、C中只有中只有1個為個為1 B=1 x4+x2+1=(x2+x1

19、+1)2; rejected A=1 x4+x3+1; accepted C=1 x4+x+1; acceptedRemark: x4+x3+1， x4+x+1為互反多項式為互反多項式因此因此(15)434( )11QxxxxxLecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論19 均以均以15級元素為根。因此，若以級元素為根。因此，若以此多項式作剩余類，就能得到此多項式作剩余類，就能得到24階有限域階有限域GF(24)。若以。若以 的根的根表示，則上的表示，則上的15個非個非0元素如下所示元素如下所示4341, 1xxxx41xx08293210

20、23113241232521 1 = + =+1 =+= + 1 = +1= 13326321436315= 1= = 1=1 = 1Lecture 12 Lecture 12 有限域有限域(II)(II)信道編碼理論信道編碼理論20把把x9-1分解為分解為GF(2)上的既約因式乘積上的既約因式乘積找找9級元素的最小多項式，注意到級元素的最小多項式，注意到26=1(mod 9); 故故9級元素級元素的最小多項式的次數(shù)為的最小多項式的次數(shù)為6，因此，因此9級元素必在級元素必在GF(26)上。設(shè)上。設(shè)為為GF(26)上的本原域元素上的本原域元素63=1，則，則(7)9=1 ， 7為為9級元級元素。因此素。因此故故9(1)(3)(9)1( )( )( )xQx Qx Qx (9)7142856493563( ) 1Qxxxxxxxxx92631111xxxxxx Lecture 12 Lecture 12 有限域有限域(II)(II)