信道编码有限域和多项式

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,信道编码有限域和多项式,学习本章目的：对Xn-1进展因式分解(n=qm-1,q为素数),X15-1=(x+1)(x 4 + x 3+1)(x4+x3+x2 +x +1)(x2 +x +1)(x4+x +1),Xn-1?,循环：只有最高位和最低位,一、剩余类环,环，子环、扩环,回忆环R，+，*的定义,定义了两种运算+和*,R对+构成阿贝尔群,*满足封闭性、结合律,*对+满足分配律,*不一定有恒等元1，R的元素不一定有逆元,非空子集S是环R，+，*的子环的充要条件:,a,b S:a-b S ; S是群R，+)的子群,a,b S:ab S S对*满足封闭性,一、剩余类环,理想,定义: 交换环R中的非空子集I称为R中的理想，假设：, a, b I: a-b I;, a I, r R: ar =ra I;,1)+2) 理想是个子环，,2) I 中任一元素a的倍数在I中，即I由R的一些元素可以是多个的倍数组成。,主理想：由一个元素的的所有倍数组成的理想.这个元素叫生成元.,主理想环:每一个理想都是主理想,一、剩余类环,剩余类环,定理1 (定理)：设I 为可换环R的一个理想，那么R/I构成一个可换环，称为模I的剩余类环。,例: Mod5的剩余类环,I 0: 05-510-10 .,1+I 1:16-411-9.,2+I 2:27-312-8 .,3+I 3:38-213-7 .,4+I 4:49-114-6 ., 0,1, 2, 3, 4 对模5+和模5*构成可换环,二、多项式剩余类环,多项式,Fq上的多项式：,f(x)= fnxn +fn-1xn-1+f2x2 +f1x +f0,fi Fq i=0,1,2,n,次数n记为：f(x), f, degf(x), degf,Why多项式？,矢量 a = (1,0,1,1,0,1) 位置,多项式f(x)= x5 +x3+x2 +1 次数,为了借用多项式的运算来定义矢量的运算,多项式的除法 例：(x9+x8 +x7 +x2+x +1/x4+ x3 + x +1,n次多项式域群、环与n维矢量域群、环在以下映射下同构：,f(x)= fnxn +fn-1xn-1+f2x2 +f1x +f0 fnfn-1f2f1f0,二、多项式剩余类环,定理2：集合G与G 同构 G为群(环、域) G为群(环、域) ,首一多项式： fn =1，最高次数为1，f(x)1。,Fqx: 表示系数属于Fq的所有多项式的集合,多项式环,整数是一个环，多项式与整数类似。,定理3：Fqx构成一个环,零元：f(x)=0,二、多项式剩余类环,性质,整数环,多项式环,零元素,0,f(x)=0,恒等元,1,f(x)=1,不可分解的元,素数,既约多项式（除提取常数，不能进行因式分解，,定义4.4.2,）,素多项式=首一 + 既约多项式,分解的唯一性,a=p,1,r1,p,2,r2,(,素数幂的积）,f(x)=p,1,(x),r1,p,2,(x),r2,每一个首一多项式可,唯一,分解为素多项式的幂的积(,定理4.2.3,),欧几里德除法,若,ab,则,a,可唯一表示为:,a=qb+r,0, r b,若,f(x),g(x),则:,f(x),=q(x)g(x)+r(x),0,r(x) ,g(x),(,定理4.2.2,),二、多项式剩余类环,性质,整数环,多项式环,约数,最大公约数(,a,b),GCD(a,b),最高公因式,(定义4.2.3),(,是首一多项式）,（,f(x),g(x), GCD(f(x),g(x),倍数,最小公倍数,a,b,LCM(a,b),最低公倍式,(定义4.2.4),(,是首一多项式）,f(x),g(x), LCM(f(x),g(x),欧几里德算法,a=qb+r,(a,b)=(b,r),(a,b)=Aa+Bb,A,B,为正整数,f(x),=q(x)g(x)+r(x),(,f(x),g(x)=(g(x),r(x),(,例,f(x)=,x,9,+x,8,+x,7,+x,2,+x+1,g(x)=x,4,+x,3,+x+1),(,f(x),g(x)=A(x)f(x)+B(x)g(x),0,A(x),g(x)-,(,f(x),g(x),0,B(x)k,n=h-k,n,=,h-k,=,h,-k,=,k,-k,= e,一定是 ,0,=e, ,2, ,n-1,例:,Z/(8),2.,定理,4,(,定理,),：,可换群,G,的任一,n,级元素,a,皆可生成一个,n,阶循环子群,。,循环群是可换群，所以由其中元素,i,皆能生成一个循环群，其阶数为,i,的级数。,这个循环群可以是它本身，或是它的子群。,四、循环群,循环群G 的性质：,G 必为阿贝尔群；,a为n 级元素，那么 ak 的级为n /(k,n);,a为n 级元素，那么am = e n| m ;,n 阶循环群中每个元素的级数m满足m|n.,n 级元素a与m 级元素 b 满足 (n, m) =1, 那么 ab为nm 级元素;,定理 5 )：n 阶循环群中必有(n)个单位原根。,(n) = | a| 0 a n-1且 a, n =1|,(欧拉函数，小于n且与n互素的自然数的个数),四、循环群,5.由循环群寻找其全部子群 定理4.3.2),G(a)为由a生成的n阶有限循环群，H为G(a)的子群,H为有限阶循环群，或者是e,或者是由am 生成的q阶循环群：, e，am ，a2m， ， an-m ,其中q|n, m= n/q,假设m|n,那么G中必有唯一的n/m阶循环子群，生成元是am,五、有限域GF(q)的乘法构造,有限域GF(q)非零元素全体对乘法构成阿贝尔群，由定理4，任一非零元素可生成一个有限循环子群，其阶称为的级，即使n=1的最小正整数n, 称为GF(q)的n次单位原根，假设n=q-1,那么称为GF(q)-0的生成元，称为本原域元素。,循环群的单位原根：n级元素称为n次单位原根。,本原域元素 (本原元): q-1级元素,五、有限域GF(q)的乘法构造,定理 6 ：Fq上的n级元素 生成的n阶循环群G()是方程 xn -1 = 0的全部根。,证明：,设 G() 的级为h,由定理4，可生成一个阶为h的循环子群，而子群的阶必为G()的阶n的因子，所以h|n, n = ( h)n/h=1,方程xn-1 = 0的根不多于n个，而G()中，n个元素都是它的根，所以全部根落在G()中。,推论1：假设Fq含有n次单位原根 ，那么xn 1可分解为 。,五、有限域GF(q)的乘法构造,定理,7,：,F,q,必有本原域元素,存在，所以,F,q, 0,是一个,q-1,阶乘法循环群。所以,F,q, 0=, ,2, , ,q-2, ,q-1,=e,这称为有限域的幂表示法。,推论,2,(,定理,),：,方程,x,q-1, 1,= 0,的全部根构成,F,q, 0.,F,q,为,x,q, x,= 0,的全部根，即,x,q, x=x,F,q,称为,x,q, x,的最小分裂域,推论,3,(,费马,Ferma,定理,定理,),：,F,q,:,q,=,.,五、有限域GF(q)的乘法构造,例 GF(2)上的多项式x15 1=,GF(16)-0=1 , , 2, 3 , , 14,每个元素的级是15的因子，15的因子有1、3、5、15，所以GF(16)非0元素的级为1、3、5、15，其中i的级为15/15,i)，所以,1, , 2, 3, 4,5, 6,7, 8, 9,10, 11,12,13,14,级:1,15,15, 5, 15, 3, 5, 15, 15, 5, 3, 15, 5, 15,15,级数为 1: 1,3: 5 , 10,5: 3 ,6 ,9 ,12,15: ,2 ,4 ,7, 8, 11, 13, 14,把同级的一次因式相乘得,=(x-1)(x-5)(x-10 )(x-3)(x-6)(x-9)(x-12),(x-)(x-2)(x-4)(x-7)(x-8)(x-11)(x-13)(x-14),=Q(1)(x) Q(3)(x) Q(5)(x) Q(15)(x),五、有限域GF(q)的乘法构造,分园多项式,xn-1=,为n级元素, 那么i为n/(n,i)级元素, 把同级的分为一类,得k类, 即n1=n/(n,i1), nd=n/(n,id), nk=n/(n,ik),以d级元素为根的所有一次因式的积叫,分园多项式 (定义4.4.3),分园多项式是GF(2)上的多项式, 并且可以通过后面介绍的方法求得,亦即xn-1至少可分解为分园多项式的积,五、有限域GF(q)的乘法构造,定理,7*,(,定理,4.4.5,p120):,(,求分园多项式),x,n,1,=,Q,(d),(x),为分圆多项式，,Q,(d),(x) =,=,为,Mobius,函数,，,(,m)= 0, m,有平方因子,=(-,1,),k,m,不含平方因子,且可分,解为,k,个因子的积,=,1 ,m =1,六、有限域GF(q)的加法构造,根本概念,周期:模拟乘法的级,a+a +a +a +a =na =0,n个a 相加，即加法幂，记为na,(课本的na不是n乘a,任意aGF(q)(a0),满足na =0的最小正整数或。,2特征：乘法单位元e的周期，即满足ne=0的最小正整数n,如果nN:ne 0,那么称域的特征为,a=a*e,na = a+a + +a =a*e+a*e+ +a*e,=a*(e+e+e)= a*(ne)=0,根据分配律,n,个,六、有限域GF(q)的加法构造,定理8：域中任一非零元素的周期都等于域的特征定理4.5.1),域整数：a = ze (z Z) (e的倍数),例如GF(4)=0，1，2，3中，,1+1=0，周期为2,0、1为域整数,定理9：域的特征或为素数，或为。定理4.5.2),假设特征h不为素数，h=m*n,那么,he=(m*n)e = m(ne)=0,ne的周期 m h,这与定理8矛盾。,根据结合律,m*n,个,e,相加,m,个(,ne),相加,六、有限域GF(q)的加法构造,定理10：在p特征域GF(q)中，全体域整数构成p阶素子域GF(p),且同构于Z/(p)(定理4.5.3),GF(p)称为GF(q)的基域，GF(q)称为GF(p)的扩域。,定理11：p特征域GF(q)中， (定理4.5.4),aGF(q):(x-a)p=xp ap,推论4: 假设k是p特征域的域整数，那么 = k (nN ),(推论),没有真子域,P,为素数,X,可以取扩域,GF(q),中的元素,六、有限域GF(q)的加法构造,定理12:,在p特征域Fq中：元素a为域整数 ap-a = 0 (定理),2. 最小多项式与本原多项式,最小多项式、元素的次数、本原多项式：,设Fq为FQ 的子域， w FQ, m(x)是Fq上满足 m(w) = 0的次数最低的首一多项式，称 m(x)为w 在Fq上的最小多项式，m(x)称为w 的次数。假设w 为FQ的本原元，那么称m(x)为本原多项式。,问题：fx)=x-w 是不是w的最小多项式？,六、有限域GF(q)的加法构造,定理 13 (定理)：w 在Fq上最小多项式m(x)的性质：,m(x)在GF(p)上既约；,存在且唯一；,假设Fq上多项式f(x) 满足 f (w) = 0, 那么 m(x) | f (x); 以w为根的多项式是m(x) 的倍式；,m(x) | xq-x.,定理 14 (相当于定理)：令f(x)为Fq上任意多项式，那么存在扩展域FQ, 在FQ中f(x)可分解为一次因子的积，称FQ为f(x)的分裂域。,以素多项式f(x)生成一个有限域Fqx/f(x),在这个域中， 。,可见，如果f(x)是GF(p)上的素多项式，而且f(w)=0, 那么f(x)为w的最小多项式。,六、有限域GF(q)的加法构造,定理 15 (课本没有)：设Fq为FQ的真子域，是FQ的本原元， 的次数为m, 那么 Q =qm， 且, FQ: = , ai Fq,证：第一步：证Q qm,a.形式为 的元素在FQ中,设 = , ai Fq ，那么 FQ,b.不同形式对应不同的元素,设1= , ai Fq,2= ,bi Fq 且i: aibi 那么1 2,反证法，如1 =2，那么,在Fq中有次数比m更小并以为根的素多项式。这与的次数为m矛盾,形式为 的元素有qm个，全部落在FQ中，所以Q qm,六、有限域GF(q)的加法构造,第二步：证Q qm,为FQ的本原域元素，那么 FQ: = k,又设在Fq的最小多项式为,f(x)=xm+fm-1xm-1+ fm-2xm-2+f1x+f0,那么f( )= m+fm-1 m-1+ fm-2 m-2+f1 +f0 =0，,.,k可表示为 m-1， m-2 ， ,1)的线性组合，而 m-1， m-2 ， ,1)的线性组合共qm个，所以Q qm,综上述，Q=qm,推论5 )：有限域 的阶必为其特征的幂，因此它是素数的幂。,六、有限域GF(q)的加法构造,3共轭根:,定理16 定理: f(x)为Fp上的多项式， w为Fp的扩展域上的元素且f (w) = 0, 那么对于n N, 有,叫w的共轭根，共轭根的集合组成共轭根系,设w为f(x)的根Fpm 的元素,观察共轭根:,n=0, 1, 2, ,m-1, m, m+1, ,w,wp, , , , ,所以，方程f(x)=0的共轭根,最多m个。设m为满足wpk=w的最小正整数k, 那么w的共轭根有m个，这m个根实际上是由m个共轭根组成的m/ m 个循环。所以m|m,设w的级数为n,那么n|pm-1, 所以pm1 mod n),P对模n的方次数: 满足pm 1 (mod n )的最小整数m称为p对模n的方次数,六、有限域GF(q)的加法构造,定理16* 推论：各个共轭根的级数一样，最小多项式一样。,w的级为n,那么wp的级为n/(n,p)=n,定理17 定理：设w是Fq的扩展域FQ的n级元素，而m是q对模n的方次数，那么w的次数为m, 且其在Fq上的最小多项式m(x) =,多项式的周期,多项式 f(x)的周期p(f): 设f(x) Fqx, f(0)0, 满足 f(x)|(xl-1) 的最小正整数l.,定理17 * p(f)的性质: p(f)等于Fqx/f(x)中 的级数。,七、有限域GF(q)的代数构造,定理18 定理,(1) s | r ; 正向可直接从定理15推出,(2),定理19 定理Fq,nN:,定理20 (定理 - x =,( - x可分解为次数为m的因子的素多项式的积),定理21 (定理 f(x)为Fq上的d次既约多项式，且d|m, 那么任一 含有f(x)的全部根。,七、有限域GF(q)的代数构造,定理22 (定理 Fq上的m次既约多项式的数目是 .,(d)为Mobius函数。,八、小结,乘法构造,Fq-0一定是q-1阶乘法循环群，,Fq=0， 2，, q-2， q-1=e,叫,有限域的幂表示法,Fq 一定是方程xq-x=0的全部根，所以xq-x可分解为1次因式的积,加法构造,Fq的特征p一定是素数,而且满足q = pm.,给出任一素数p和正整数m,一定存在GF(pm).,任意两个同阶的域同构.,所有方法生成的有限域本质上是一样的，只是表示方法即加法表与乘法表不一样不一样，只要找到一种方法生成即可。,八、小结,如何求GF(pm)?,a)求以P为特征的域Fp=e,2e,pe=0,b) 求Fp上的m次素多项式f(x).,可查表,共有 个,见定理22),c) 求,有限域的剩余类表示法，去掉帽子得多项式表示法，可映射为矢量表示法(f(x)=fmxm+fm-1xm-1+,+f1x+f0映射为(fm,fm-1,.,f1,f0),f(x)=0定理14,f(x)为x的最小多项式，设f(x)的周期为n,那么x为n级元素定理17*，m为p关于模n的方次数定理17，如n=pm-1,那么f(x)为本原多项式，x为本原元, 这时多项式表示法与幂表示法结合起来,例，构造GF(4),考察,元素,x,八、小结,因式分解,定理 14 (相当于定理)：令f(x)为Fq上任意多项式，那么存在扩展域FQ, 在FQ中f(x)可分解为一次因子的积，称FQ为f(x)的分裂域。,GF(pm) 是方程xpm-x=0的全部根，所以在GF(pm)中， xpm-1-1可分解为一次因式的积，即 1,把1式同级元素相乘，得分园多项式Fp上，但不一定是素多项式，所以,根据定理7*，Q(d)(x) = =,根据定理17，把1式共轭根的一次因式相乘，得最小多项式(Fp上，是素多项式),所以,其中，r为ws对模n的方次数，n为ws的级数，ms(x)为第s个共扼根系共扼根对应的最小多项式,八、小结,根据定理20,-x =,(素多项式,f(x),可查表),八、小结,例：对x7-1进展因式分解,构造GF(8),查表得GF(2)上的素多项式f(x)=x3+x+1,求F2x/f(x), 得GF(8) ,p134,表4-1,GF(8)=(0，1,，2， 3， 4， 5， 6),元素,级,方次数,共轭根,最小多项式,1,0,1,x+1,7,3（2,3,1mod 7),，,2,，,4,(x-,)(,x-,2,) (,x-,4,)=,x,3,+x+1,3,7,3(2,3,1mod 7),3,，,5,，,6,(x-,3,)(,x-,5,) (,x-,6,),=,x,3,+x,2,+1,(x-)(x- 2 ) (x- 4 )=(x 2 +(+ 2)x+ 3 ) (x- 4 )= (x 2 + 4x+ 3 ) (x- 4 ),= x 3 + 4x2 + 4x2 + 8 x + 3 x + 7 = x 3 +x+1,(x- 3)(x- 5 ) (x- 6 )=(x 2 +( 3 + 5)x+ 8 ) (x- 6 )= (x 2 + 2x+ ) (x- 6 ),= x 3 + 6x2 + 2x2 + 8 x + x +1 = x 3 +x 2+1,x7-1=(x+1)(x 3 +x+1)(x 3 +x 2+1)1,事实上，根据定理20，(x3+x+1)| (x7-1), x7-1/ (x3+x+1)=(x4+ x2+x+1),又x=1必为x7-1的根，所以x+1)| (x4+ x2+x+1),求,(x4+ x2+x+1)/ x+1)= x 3 +x 2+1，为素多项式，所以得1式,谢谢大家！,