纠错码Lecture12-有限域(II)

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Lecture 12,有限域,(II),信道编码理论,信道编码理论,邢莉娟，李卓，西安电子科技大学,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Lecture 12,有限域,(II),2,内容,有限域的加法结构,有限域的代数结构,多项式的因式分解,正规基和对偶基,3,有限域的加法结构,域的特征,满足,ne,=0,的最小,n,值为,域的特征,，这里,e,为乘法单位元，,0,为域的零元，,n,取自正整数,GF(,p,),的特征为,p,每一个域的特征或为素数，或为,域的,特征,说明了域中,加法运算的循环性,，而域中元素的,级,则说明了,乘法运算的循环性,。,元素的周期,对域中元素,a,0,，满足,na,=0,的最小,n,值为,a,的,周期,。（注意对于域而言，,在加法上用周期，在乘法上用级,）,域中非,0,元的周期都相同，且与域的特征相等,在,p,特征域中，域整数全体（形如,ne,的全体域元素,:,n,=,-2,-1,0,1,2,）构成,p,阶素子域，它与模,p,的整数域,GF(,p,),同构,4,有限域加法性质,GF(,p,),为,GF(,p,m,),的,基域,，,GF(,p,m,),为,GF(,p,),的,扩域，,GF(,p,m,),的特征为,p,。,如,GF(2,2,),的,4,个元素,:00,01,10,11,中的每一个特征均为,2,；故,GF(2,2,),是一个特征为,2,的域,在特征为,p,的域中，恒有,其中，,a,是域中的任一元素,在,p,特征域中，对任何域元素,a,b,，恒有,在,p,特征域中，任一元素的级均不是,p,的倍数,5,有限域加法性质,若,w,1,w,2,w,k,是,p,特征域的元素，则对于一切自然数,n,，恒有,若,k,是,p,特征域的域整数，则对于一切自然数,n,，必满足方程 ，即,Fermat,定理,：对,GF(,p,m,),中的任何元素,w,，恒有,任何小于素数,p,的整数,b,满足 ，如,p,特征域中，元素为域整数的充要条件是满足,6,最小多项式,若 为方程,的根，则,GF(,p,m,),中互不相同的,m,个元素,是,f,(,x,),的,m,个不同的根。这,m,个根称为方程,f,(,x,),的,共轭根系,能满足,p,m,=1(mod,n,),的最小整数,m,，称为,p,对模,n,的方次数,系数取自,GF(,p,),的，以,w,为根的所有首一多项式中，次数最低的称为,w,的最小多项式,m,(,x,),，,w,的最小多项式的次数,m,称为,w,的,次数,，称,w,为,m,次域元素,7,最小多项式,性质,m,(,x,),在,GF(,p,),上不可约,若,w,也是,f,(,x,),的根，则,m,(,x,),可整除,f,(,x,),若,w,取自,GF(,p,m,),，则有,m,(,x,),可整除,设,w,是,p,特征域,GF(,p,m,),中的,n,级元素，而,p,m,=1(mod,n,),，则,w,的最小多项式,m,(,x,),是,m,次多项式，且,在,GF(,p,m,),域中完全分解,m,(,x,),为一次因式之积，所以称,GF(,p,m,),为,m,(,x,),的,分离域,或,分解域,8,本原多项式,在,GF(,p,m,),中，以本原元为根的最小多项式称为该域的,本原多项式,GF(,p,m,),的本原多项式的根级数均为,p,m,-1,，且本原多项式必为,m,次多项式,w,为最小多项式的根，若,w,是特征为,p,的有限域,F,上的,m,次域元素，则所有小于,m,次的多项式,f,(,x,),将,w,代入，得到的集合构成,p,m,阶子域。（以最小多项式为模）,如：,GF(2),上,f,(,x,)=,x,3,+,x,+1,，以,GF(2,3,),上的元素,w,为根，则,GF(2),上小于,3,次,w,多项式全体构成,2,3,阶子域：,0,1,w,w,+1,w,2,w,2,+1,w,2,+,w,w,2,+,w,+1,对于,m,次元素,w,，有,1,w,w,2,w,m,-1,线性无关，可作为域空间的,基。,可以由,GF(,p,),上的一个,m,次本原或既约多项式，用它的根,w,构成的这组基底的线性组合，构造一个,GF(,p,m,),有限域,9,互反多项式,定义,设,GF(,p,),上的,m,次多项式,则,称为,互反多项式,例：,性质,若,为,f,(,x,),的根，则,-1,为,f*,(,x,),的根,若,f,(,x,),既约，则,f*,(,x,),也为既约；反之亦然,若,f,(,x,),为本原多项式，则,f*,(,x,),也为本原多项式；反之亦然,10,多项式的周期,定义,设,f,(,x,),F,p,x,f,(0)0,（即,x,!,|f,(,x,),），则,f,(,x,)|(,x,l,-1),的最小正整数,l,，称为,f,(,x,),的,周期,（或,指数,），记为,p,(,f,),性质,f,(,x,),的周期,l,是以,f,(,x,),为模所构成多项式剩余类环中乘法群内元素 之级,f,(,x,),F,p,x,f,(0)0,，则,f,(,x,)|(,x,l,-1),的充要条件是,p,(,f,)|,l,多项式,(,x,m,-1)|(,x,n,-1),的充要条件是,m|n,若,f,(,x,),是,F,p,x,中,m,次既约多项式，则,f,(,x,),之周期,p,(,f,),等于,f,(,x,),在,GF(,p,m,),中的根的级,11,多项式的周期,性质,(cont.),GF(,p,),上多项式,f,(,x,),的标准分解式若为,则,f,(,x,),的周期,式中,是,x,的最小整数,12,多项式的周期,Example,GF(2),上的多项式,因为 以,5,级元素为根,以,15,级元素为根,13,有限域的代数结构,有限域的阶必为其特征（素数）之幂,设,f,(,x,),为,p,阶有限域,GF(,p,),上的一个,d,次既约多项式，则多项式剩余类集合,F,p,x,/,f,(,x,),构成,p,d,阶有限域,GF(,p,d,),。即,GF(,p,d,),是,GF(,p,),的扩域，且,f,(,x,),在,GF(,p,d,),内有根,GF(,p,r,),含有子域,GF(,p,s,),的充要条件是,s|r,若,GF(,p,r,),，则,GF(,p,s,),中的充要条件是 。特别是在任何域中若 ，则,是,0,或,1,p,阶有限域上的每一个,d,次首一既约多项式，皆能整除 ，只要,d|m,14,最小扩域,系数取自,GF(,p,),上的多项式,=,所有次数除尽,m,的,GF(,p,),上的首一既约多项式之积,如：,x,4,-,x,=,x,(,x,+1)(,x,2,+,x,+1),若,f,(,x,),为,GF(,p,),上的,m,次既约多项式，且,m|d,，则任何,p,d,阶有限域必含有,f,(,x,),的全部根,若,d=m,，则,m,次首一既约多项式,f,(,x,),的全部根在,GF(,p,m,),中，称,GF(,p,m,),为,f,(,x,),的包含所有根的,最小扩域,，称为,f,(,x,),的,分裂域,或,分解域,例：,GF(2),上的既约多项式 必在,GF(2,4,),上完全分裂，但不能在任何中间域,GF(2,2,),完全分裂,15,既约多项式的数目,GF(,p,),上,m,次既约多项式的数目是,式中 为,Mobius,函数,例：,GF(2),上,3,次既约多项式的数目,分别为,16,同构,m,重、多项式剩余类以及,多项式之间均同构，都可用来表示,p,m,阶有限域,17,因式分解,分解,注意到,2,2,=1(mod 3),Q,(3),(,x,),既约,2,4,=1(mod 5),Q,(5),(,x,),既约,2,4,=1(mod 15),Q,(15),(,x,),非既约，进一步分解为（待定系数法）,18,待定系数法,Q,(15),(,x,),的既约因式必为,x,4,+,Ax,3,+,Bx,2,+,Cx,+1,1,不是,15,级元素,A+B+C,=1,1),A=B=C,=1,x,4,+,x,3,+,x,2,+,x,+1=,Q,(5),(,x,);rejected,2),A,、,B,、,C,中只有,1,个为,1,B,=1,x,4,+,x,2,+1=(,x,2,+,x,1,+1),2,;,rejected,A,=1,x,4,+,x,3,+1;,accepted,C,=1,x,4,+,x,+1;,accepted,Remark:,x,4,+,x,3,+1,，,x,4,+,x,+1,为互反多项式,因此,19,因式分解,均以,15,级元素为根。因此，若以此多项式作剩余类，就能得到,2,4,阶有限域,GF(2,4,),。若以,的根,表示，则上的,15,个非,0,元素如下所示,20,因式分解,把,x,9,-1,分解为,GF(2),上的既约因式乘积,找,9,级元素的最小多项式，注意到,2,6,=1(mod 9);,故,9,级元素的最小多项式的次数为,6,，因此,9,级元素必在,GF(2,6,),上。设,为,GF(2,6,),上的本原域元素,63,=1,，则,(,7,),9,=1,，,7,为,9,级元素。因此,故,21,正规基和对偶基,定义,为,GF(,p,m,),域的,正规基,，这里，,是,GF(,p,m,),中的本原域元素,GF(,q,m,),，则它在,GF(,q,),上的,迹,定义为,其中，,q,为素数或素数幂,对所有的,、,GF(,q,m,),，有,22,正规基和对偶基,Example:,是,f,(,x,)=,x,3,+,x,2,+1,的根，则,与,GF(,p,m,),的基底 相对应，若,满足，则称,GF(,p,m,),的基底 是,B,的,对偶基,23,Example,若,是本原多项式,f,(,x,)=,x,3,+,x,2,+1,的根，则,自然基,自然基的对偶基,正规基,24,Example(Continued),