信道编码-有限域和多项式PPT课件

-,1,第四章多项式与有限域,学习本章目的：对Xn-1进行因式分解(n=qm-1,q为素数)X15-1=(x+1)(x4+x3+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x+1)Xn-1?循环：只有最高位和最低位,一、剩余类环,环，子环、扩环回顾环（R，+，*）的定义定义了两种运算+和*R对+构成阿贝尔群*满足封闭性、结合律*对+满足分配律*不一定有恒等元1，R的元素不一定有逆元非空子集S是环（R，+，*）的子环的充要条件:a,bS:a-bS;S是群（R，+)的子群a,bS:abSS对*满足封闭性,一、剩余类环,理想定义:交换环R中的非空子集I称为R中的理想，若：a,bI:a-bI;aI,rR:ar=raI;1)+2)理想是个子环，2)I中任一元素a的倍数在I中，即I由R的一些元素（可以是多个）的倍数组成。主理想：由一个元素的的所有倍数组成的理想.这个元素叫生成元.主理想环:每一个理想都是主理想,一、剩余类环,剩余类环定理1(定理4.1.2)：设I为可换环R的一个理想，则R/I构成一个可换环，称为模I的剩余类环。例:Mod5的剩余类环I0:05-510-10.1+I1:16-411-9.2+I2:27-312-8.3+I3:38-213-7.4+I4:49-114-6.0,1,2,3,4对模5+和模5*构成可换环,二、多项式剩余类环,多项式Fq上的多项式：f(x)=fnxn+fn-1xn-1+f2x2+f1x+f0fiFqi=0,1,2,n次数n记为：f(x),f,degf(x),degfWhy多项式？矢量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,二、多项式剩余类环,二、多项式剩余类环,二、多项式剩余类环,三、基于多项式的有限域,基于整数的有限域由素数p的同余类构成一个域，阶为p基于多项式的有限域定理3*：f(x)是Fq上素多项式Fqx/f(x)是一个域。基于多项式的有限域的生成办法：找到次数为n的素多项式，由其倍式组成一个理想，求其商群，共有qn个元素，构成一个qn有限域GF(qn)。,四、循环群,定义循环群:由某个元素的所有整数幂组成的群0,1,2,3,.,成为生成元。为研究有限域服务可以是乘法幂和加法幂，即对环和域，其子集对两种运算都可构成循环群元素a的级：满足an=e的最小正整数n,若nN:ane,则称a的级为无限大。单位原根:n阶循环群的n级元素。,四、循环群,无限循环群：成为生成元，nm(nm)有限循环群：h,kZ,且hk:h=k设hk,n=h-k,n=h-k=h-k=k-k=e一定是0=e,2,n-1例:Z/(8)2.定理4(定理4.3.1)：可换群G的任一n级元素a皆可生成一个n阶循环子群。循环群是可换群，所以由其中元素i皆能生成一个循环群，其阶数为i的级数。这个循环群可以是它本身，或是它的子群。,四、循环群,循环群G的性质：G必为阿贝尔群；a为n级元素，则ak的级为n/(k,n);a为n级元素，则am=en|m;n阶循环群中每个元素的级数m满足m|n.n级元素a与m级元素b满足(n,m)=1,则ab为nm级元素;定理5(推论4.3.3)：n阶循环群中必有(n)个单位原根。(n)=|a|0an-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次单位原根，则xn1可分解为。,五、有限域GF(q)的乘法结构,定理7：Fq必有本原域元素存在，所以Fq0是一个q-1阶乘法循环群。所以Fq0=,2,q-2,q-1=e这称为有限域的幂表示法。推论2(定理4.4.1)：方程xq-11=0的全部根构成Fq0.Fq为xqx=0的全部根，即xqx=xFq称为xqx的最小分裂域推论3(费马Ferma定理,定理4.5.5)：Fq:q=.,五、有限域GF(q)的乘法结构,例GF(2)上的多项式x151=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,105: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):(求分园多项式)xn1=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=0n个a相加，即加法幂，记为na(课本的na不是n乘a）任意aGF(q)(a0),满足na=0的最小正整数或。2）特征：乘法单位元e的周期，即满足ne=0的最小正整数n,如果nN:ne0,则称域的特征为a=a*ena=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(zZ)(e的倍数)例如GF(4)=0，1，2，3中，1+1=0，周期为20、1为域整数定理9：域的特征或为素数，或为。（定理4.5.2)假设特征h不为素数，h=m*n,则he=(m*n)e=m(ne)=0ne的周期mh,这与定理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=xpap推论4:若k是p特征域的域整数，则=k(nN)(推论4.5.4),没有真子域,P为素数,X可以取扩域GF(q)中的元素,六、有限域GF(q)的加法结构,定理12:在p特征域Fq中：元素a为域整数ap-a=0(定理4.5.5)2.最小多项式与本原多项式最小多项式、元素的次数、本原多项式：设Fq为FQ的子域，wFQ,m(x)是Fq上满足m(w)=0的次数最低的首一多项式，称m(x)为w在Fq上的最小多项式，m(x)称为w的次数。若w为FQ的本原元，则称m(x)为本原多项式。问题：f（x)=x-w是不是w的最小多项式？,六、有限域GF(q)的加法结构,定理13(定理4.5.8)：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(相当于定理4.6.2)：令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:=,aiFq证：第一步：证Qqma.形式为的元素在FQ中设=,aiFq，则FQb.不同形式对应不同的元素设1=,aiFq2=,biFq且i:aibi则12反证法，如1=2，则在Fq中有次数比m更小并以为根的素多项式。这与的次数为m矛盾形式为的元素有qm个，全部落在FQ中，所以Qqm,六、有限域GF(q)的加法结构,第二步：证Qqm为FQ的本原域元素，则FQ:=k又设在Fq的最小多项式为f(x)=xm+fm-1xm-1+fm-2xm-2+f1x+f0则f()=m+fm-1m-1+fm-2m-2+f1+f0=0，.k可表示为（m-1，m-2，,1)的线性组合，而（m-1，m-2，,1)的线性组合共qm个，所以Qqm综上述，Q=qm推论5(定理4.6.1)：有限域的阶必为其特征的幂，因此它是素数的幂。,六、有限域GF(q)的加法结构,3共轭根:定理16（定理4.5.6）:f(x)为Fp上的多项式，w为Fp的扩展域上的元素且f(w)=0,则对于nN,有,叫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（modn)P对模n的方次数:满足pm1(modn)的最小整数m称为p对模n的方次数,六、有限域GF(q)的加法结构,定理16*（推论4.5.7）：各个共轭根的级数相同，最小多项式相同。w的级为n,则wp的级为n/(n,p)=n定理17（定理4.5.9）：设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（定理4.6.3）(1)s|r;（正向可直接从定理15推出）(2)定理19（定理4.6.4）Fq,nN:定理20(定理4.6.6）-x=(-x可分解为次数为m的因子的素多项式的积)定理21(定理4.6.7）f(x)为Fq上的d次既约多项式，且d|m,则任一含有f(x)的全部根。,七、有限域GF(q)的代数结构,定理22(定理4.6.8）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=0b)求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(相当于定理4.6.2)：令f(x)为Fq上任意多项式，则存在扩展域FQ,在FQ中f(x)可分解为一次因子的积，称FQ为f(x)