纠错码Lecture12-有限域(II)

1、信道编码理论信道编码理论邢莉娟，李卓，西安电子科技大学邢莉娟，李卓，西安电子科技大学Lecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论2有限域的加法结构有限域的加法结构有限域的代数结构有限域的代数结构多项式的因式分解多项式的因式分解正规基和对偶基正规基和对偶基Lecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论3域的特征域的特征 满足满足ne=0的最小的最小n值为值为域的特征域的特征，这里，这里e为乘法单位元，为乘法单位元，0为域的零为域的零元，元，n取自正整数取自正整数 GF(p)的特征为的特征为p 每

2、一个域的特征或为素数，或为每一个域的特征或为素数，或为 域的域的特征特征说明了域中说明了域中加法运算的循环性加法运算的循环性，而域中元素的，而域中元素的级级则说明则说明了了乘法运算的循环性乘法运算的循环性。元素的周期元素的周期 对域中元素对域中元素a0，满足，满足na=0的最小的最小n值为值为a的的周期周期。（注意对于域。（注意对于域而言，而言，在加法上用周期，在乘法上用级在加法上用周期，在乘法上用级） 域中非域中非0元的周期都相同，且与域的特征相等元的周期都相同，且与域的特征相等在在p特征域中，域整数全体（形如特征域中，域整数全体（形如ne的全体域元素的全体域元素: n=, -2, -1,

3、0 ,1, 2, ）构成）构成p阶素子域，它与模阶素子域，它与模p的整数域的整数域GF(p)同构同构0,1,2 1,(1) 10,1,2,1pRppLecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论4GF(p)为为GF(pm)的的基域基域，GF(pm)为为GF(p)的的扩域，扩域，GF(pm)的特征为的特征为p。如如GF(22)的的4个元素个元素: 00, 01, 10, 11中的每一个特征均为中的每一个特征均为2；故；故GF(22)是一个特征为是一个特征为2的域的域在特征为在特征为p的域中，恒有的域中，恒有 其中，其中，a是域中的任一元素是域中的

4、任一元素在在p特征域中，对任何域元素特征域中，对任何域元素a, b，恒有，恒有在在p特征域中，任一元素的级均不是特征域中，任一元素的级均不是p的倍数的倍数pppxaxapppababLecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论5若若w1, w2, , wk是是p特征域的元素，则对于一切自然数特征域的元素，则对于一切自然数n，恒有恒有若若k是是p特征域的域整数，则对于一切自然数特征域的域整数，则对于一切自然数n，必满足方，必满足方程程 ，即，即Fermat定理定理：对：对GF(pm)中的任何元素中的任何元素w，恒有，恒有任何小于素数任何小于素数

5、p的整数的整数b满足满足 ，如，如p特征域中，元素为域整数的充要条件是满足特征域中，元素为域整数的充要条件是满足npxxnpkk11nnpkkpiiiiwwmpww(mod )pbbp621(mod7)0pxxLecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论6若若 为方程为方程 的根，则的根，则GF(pm)中互不相同的中互不相同的m个元素个元素 是是f(x)的的m个不同的根。这个不同的根。这m个根称为方程个根称为方程f(x)的的共轭根系共轭根系能满足能满足pm=1(mod n)的最小整数的最小整数m，称为，称为p对模对模n的方次数的方次数系数取自

6、系数取自GF(p)的，以的，以w为根的所有首一多项式中，次数为根的所有首一多项式中，次数最低的称为最低的称为w的最小多项式的最小多项式m(x)，w的最小多项式的次数的最小多项式的次数m称为称为w的的次数次数，称，称w为为m次域元素次域元素GF()mwp0( )0; GF( )kiiiif xf xfp21, , , , mpppw wwwLecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论7性质性质 m(x)在在GF(p)上不可约上不可约 若若w也是也是f(x)的根，则的根，则m(x)可整除可整除f(x) 若若w取自取自GF(pm)，则有，则有m(x

7、)可整除可整除设设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)的本原多项式的根级数

8、均为的本原多项式的根级数均为pm-1，且本原多项式必为，且本原多项式必为m次多项次多项式式w为最小多项式的根，若为最小多项式的根，若w是特征为是特征为p的有限域的有限域F上的上的m次域元素，则次域元素，则所有小于所有小于m次的多项式次的多项式f(x)将将w代入，得到的集合构成代入，得到的集合构成pm阶子域。（以阶子域。（以最小多项式为模）最小多项式为模） 如：如：GF(2)上上f(x)=x3+x+1，以，以GF(23)上的元素上的元素w为根，则为根，则GF(2)上上小于小于3次次w多项式全体构成多项式全体构成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线性无关，可作为域空间的线性无关，可作为域空间的基。基。 可以由可以由GF(p)上的一个上的一个m次本原或既约多项式，用它的根次本原或既约多项式，用它的根w构成的构成的这组基底的线性组合，构造一个这组基底的线性组合，构造一个GF(pm)有限域有限域Lecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论9定义定义设设GF(p)上的上的m次多项式次多项式 则则 称为称为互反多项式互反多项式例：例：性质性质若若为为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定义定义设设f(x) Fpx, f(0) 0（即（即x !| f(x) ），则），则f(x)|(xl-1)的最的最小正整数小正整数l，称为，称为f

11、(x)的的周期周期（或（或指数指数），记为），记为p(f)性质性质f(x)的周期的周期l是以是以f(x)为模所构成多项式剩余类环中乘法为模所构成多项式剩余类环中乘法群内元素群内元素 之级之级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性质性质(cont.)GF(p)上多项式上多项式f(x)的标准分解式若为的标准分解式若为 则则f(x)的周期的周期 式中式中 是是x的最小整数的最小整数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有限域的阶必为其特征（素数）之幂有限域的阶必为其特征（素数）之幂设设f(x)为为p阶有限域阶有限域GF(p)上的一个上的一个d次既约多项式，则多项次既约多项式，则多项式剩余类集合式剩余类集合Fpx/f(x)构成构成pd阶有限域阶有限域GF(pd) 。即。即GF(pd)是是GF(p)的扩域，且的扩域，且f(x)在在GF(

14、pd)内有根内有根GF(pr)含有子域含有子域GF(ps)的充要条件是的充要条件是s|r若若 GF(pr) ，则，则 GF(ps)中的充要条件是中的充要条件是 。特。特别是在任何域中若别是在任何域中若 ，则，则是是0或或1p阶有限域上的每一个阶有限域上的每一个d次首一既约多项式，皆能整次首一既约多项式，皆能整除除 ，只要，只要d|msp2mpxxLecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论14系数取自系数取自GF(p)上的多项式上的多项式 =所有次数除尽所有次数除尽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)的包含所有根的的包含所有根的最小扩域最小扩域，称为，称为f(x)的的分裂域分裂域或或分解域分解域例：例：GF(2)上的既约多项式上的既约多项式 必在必在GF(24)上完全分裂，上完全分裂，但不能在任何中间域但不能在任何中间域GF(22)完全分裂完全分裂mpxx4( )1f xxx2484( )(

16、)()()(); GF(2 )f xxxxxLecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论15GF(p)上上m次既约多项式的数目是次既约多项式的数目是 式中式中 为为Mobius函数函数例：例： GF(2)上上3次既约多项式的数目次既约多项式的数目 分别为分别为( )d|1( )mdmdd mId pm31311(1)2(3)2(82)233I323( )1, 1f xxxxxLecture 12 Lecture 12 有限域有限域(II)(II)信道编码理论信道编码理论16m重、多项式剩余类以及重、多项式剩余类以及多项式之间均同构，都多项式之

17、间均同构，都可用来表示可用来表示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)非既约，进一步分解为（待定系数非既约，进一步分解为（待定系数法）法）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级元素级元素的最小多项式的次数为的最小多项式的次数为6，因此，因此9级元素必在级元素必在GF(26)上。设上。设为为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)