92西电纠错码课件---第五章 有限域及BCH码

国家重点实验室第五章有限域及BCH码课件下载地址[e-mail]密码:111111国家重点实验室第1节循环群及性质国家重点实验室循环群(P113)•循环群的定义•循环群的构造及性质•循环群中元素级的性质国家重点实验室•定义：由一个单独元素的所有幂次所构成的群称为循环群，该元素为循环群的生成元注：1、幂次的含义与在群上所定义的运算有关。若定义加法运算，幂运算为连加运算；若定义乘法运算，则幂运算为连乘。2、循环群的生成元不止一个。2、凡是循环群必是可换群。循环群的定义国家重点实验室•Examples:模4剩余类全体关于加法运算构成循环群，生成元为1和3。模5全体非零剩余类关于乘法构成循环群，生成元为2和3国家重点实验室•有限循环群和无限循环群若元素a的所有幂次均不相同(无限循环群)存在整数h和k，使得ak=ah，则有a生成的循环群中元素个数有限(有限循环群)•循环群元素的级若ak=ah，则有ah-k=e，定义使an=e的昀小正整数为有限循环群元素a的级。循环群的构造及性质国家重点实验室1、若元素a的级为n，则a0=e,a,a2,…an-1均互不相同2、若a为n级元素，则a的一切幂次生成的元素都在群G(a)中3、凡是循环群必是可换群4、可换群G中的每一个元素a都能生成一个循环群。若a为有限级，则生成有限循环群，a的级即为循环群中元素的个数(循环群的阶)有限循环群的几个特点国家重点实验室1、若a是n级元素，则am=e的充要条件是mn2、若a是n级元素，b是m级元素，且(n,m)=1,则(ab)的级为nm3、若a是n级元素，则ak的级为n/(k,n)4、若a是dk级元素，则ak为d级元素5、n阶循环群中，每个元素的级是群阶数n的因子6、n阶循环群中有()nϕ个单位原根有限循环群元素级的性质国家重点实验室单位原根：n阶循环群中，每一个n级元素称为n次原根欧拉函数：0,1,2,…,n-1中与n互素的元素个数称为欧拉函数。SSpppnαααK2121=()()∏=−−=Siiippni111αϕ两个定义国家重点实验室第2节有限域及性质昀重要的三个概念昀小多项式本原多项式共轭根系国家重点实验室域(Field)的定义(p31)•非空集合F，若F中定义了加和乘两种运算，且满足：1)F关于加法构成阿贝尔群，加法恒等元记为02)F中所有非零元素对乘法构成阿贝尔群，乘法恒等元记为13)加法和乘法之间满足分配律国家重点实验室一、有限域的乘法结构定理5-1设a为有限域GF(q)中的一个非零元素，则必有证明：令121,,,−qbbbL为GF(q)中的q-1个非零元素，121,,,−qabababL显然是q-1个互异的元素，因此有()()()121121−−=⋅⋅⋅qqbbbabababLL1211211−−−=qqqbbbbbbaLL11=−qa注：GF(q)中的非零元素是方程xq-1-1=0的根11=−qa国家重点实验室一、有限域的乘法结构定理5-2设a为有限域GF(q)中的一个非零元素，n为a的级，则n必能整除q-1证明：假设n不能整除q-1，可得到q-1=kn+r其中，0rn，由定理5-1得到rrknqaaa===+−11因此，a的级将小于n，与题设矛盾，故n必能整除q-1.国家重点实验室一、有限域的乘法结构结论1：域的乘法群必为某一个元素生成的循环群，即q元域中必能找到一个α，其级为q-1。结论2：所有有限域元素都能表示成生成元的幂次的形式，此时的生成元称为本原元。国家重点实验室二、有限域的加法结构•域的特征：满足ne=0的昀小n值为域的特征，注意这里e为乘法单位元，0为域的零元，n取自正整数•元素的周期：对域中元素a，满足na=0的昀小n值为a的周期。（注意对于域而言，在加法上用周期，在乘法上用级）国家重点实验室•域中非0元的周期都相同，且与域的特征相等•GP(q)为GF(qm)的基域，GF(qm)为GF(q)的扩域二、有限域的加法结构国家重点实验室三、昀小多项式•系数取自GF(q)的，以w为根的所有首一多项式中，次数昀低的称为w的昀小多项式m(x)，w的昀小多项式的次数m称为w的次数，称w为m次域元素•m(x)在GF(q)上不可约•若w也是f(x)的根，则m(x)可整除f(x)国家重点实验室四、本原多项式•GF(p)上的m次不可约多项式p(x)，若能被p(x)整除xn-1的昀小正整数n=2m-1，则称p(x)为GF(q)上的m次本原多项式。•在GF(qm)中，以本原元为根的昀小多项式称为该域的本原多项式国家重点实验室本原多项式的例子•x4+x+1是GF(2)上的4次本原多项式。•x3+x2+x+1是不可约多项式，但由于它能整除x5-1，因此它不是本原多项式。国家重点实验室五、有限域GF(2m)的构造定理5-3GF(2)上的任意m次不可约多项式必整除112−−mx有限域GF(2m)的构造假设p(x)是GF(2)上的m次本原多项式，是p(x)的一个根，即α()0=αp由于()()xqxpxm=−−112()()0112==−−αααqpm112=−mα因此可构造集合{}222*,,,,1,0−=mFαααL()mGF2国家重点实验室五、有限域GF(2m)的构造(2)例：设m=4，多项式p(x)=1+x+x4是GF(2)上的4次本原多项式，设，用这个关系构造GF(24)()251ααααα+=+=()41ααα++=p解：由于()41ααα++=pαα+=14所以()3226αααααα+=+=()43327αααααα+=+=31αα++=()42381ααααααα++=++=ααα+++=1221α+=()3291ααααα+=+=()42310αααααα+=+=21αα++=()322111ααααααα++=++=()4323212αααααααα++=++=321ααα+++=()43232131ααααααααα+++=+++=321αα+++=()4332141ααααααα++=++=31α+=()114315=+=+=ααααα国家重点实验室五、有限域GF(2m)的构造(3)2αα+GF(24)中元素的三种表示方法幂表示多项式表示4维向量表示01α2α3αα+101α2α3α4α5α6α7α8α9α10α11α12α13α14α32αα+31αα++21α+3αα+21αα++32ααα++321ααα+++321αα++31α+(0000)(1000)(0100)(0010)(0001)(0011)(1101)(0101)(0111)(1011)(1001)(1100)(0110)(1010)(1110)(1111)国家重点实验室六、有限域GF(2m)的性质•很多情况下，实系数的多项式的根不在实数域里，而在以实数域为子域的复数域里。•X2+6x+25没有实数域的根，但有两个复根-3+4i和-3-4i•以GF(2)中的元素为系数的多项式，可能在GF(2)上没有根，但在GF(2)的扩域中有根。。国家重点实验室六、有限域GF(2m)的性质(2)•x4+x3+1在GF(2)上不可约，因此没有GF(2)上的根，但它在GF(24)上有4个根7α11α13α14α()()13747++αα12128++=αα1613++=αα113232+++++=αααα0=国家重点实验室六、有限域GF(2m)的性质(3)()()()()1413117αααα++++xxxx()()2714132181172αααααα++++++=xxxxxx()()1222382αααα++++=xxxx155232021038212324αααααααα++++++++=xxxxxxxx()()()15202310123824++++++++=xxxxααααααα134++=xx国家重点实验室六、有限域GF(2m)的性质(4)()()2102nnxfxffxf+++=Ll2β0≥l定理5-4设f(x)是一个以GF(2)中元素为系数的多项式，是βGF(2)扩域中的一个元素，若是f(x)的一个根，则对任意β，也是f(x)的一个根。()(()21101020nnnnnxfxfxfxffxfxfff+++++++++=LLL()2120nnxfxff+++=L国家重点实验室六、有限域GF(2m)的性质(5)()()21202nnxfxffxf+++=L()()22120nnxfxff+++=L()2xf=()()llxfxf22=()()022==llffββl2β也是f(x)的根。l2222,,ββββL称为一个共轭根系。国家重点实验室六、有限域GF(2m)的性质(6)112=−mβ对GF中的任一非零元素，有0112=−−mβ证明：定理5-5GF(2m)中的2m-1个非零元素构成112−−mx的全部根。国家重点实验室六、有限域GF(2m)的性质(7)()()∏−=+=Φ102eiixxβ定理5-6设是GF(2m)中的元素的昀小多项式，且eββ=e2是满足的昀小正整数，则()xΦβ国家重点实验室六、有限域GF(2m)的性质(8)()()()()()91263αααα++++=Φxxxxx()34823244αααβ===例考虑GF(24)，令，求的昀小多项式()xΦ3αβ=β3αβ=()6232ααβ==()1223222ααβ==()92423233αααβ===国家重点实验室六、有限域GF(2m)的性质(9)()()()()()91263αααα++++=Φxxxxx()()()()2191229632αααααα++++++=xxxx()()682922αααα++++=xxxx()()()15178210693284αααααααα++++++++=xxxx1234++++=xxxx国家重点实验室六、有限域GF(2m)的性质(10)定理5-7设是GF(2m)中的元素的昀小多项式，且e是的次数，则e是满足的昀小正整数。()xΦβ()xΦββ=e2定理5-8设是GF(2m)中的本原元，则的所有共轭则也是GF(2m)的本原元。βL222,,ββββ定理5-9设是GF(2m)中的n级元素，则的所有共轭则也是GF(2m)的n级元素。βL222,,ββββ国家重点实验室有限域GF(2m)的构造2αα+GF(24)中元素的三种表示方法，由本原多项式x4+x+1生成幂表示多项式表示4维向量表示01α2α3αα+101α2α3α4α5α6α7α8α9α10α11α12α13α14α32αα+31αα++21α+3αα+21αα++32ααα++321ααα+++321αα++31α+(0000)(1000)(0100)(0010)(0001)(1100)(0110)(0011)(1101)(1010)(0101)(1110)(0111)(1111)(1011)(1001)0124836121151071415139国家重点实验室昀小多项式求解设是GF(2m)中的元素的昀小多项式，且e()()∏−=+=Φ102eiixxβ定理5-6ββ=e2是满足的昀小正整数，则()xΦβl2β0≥l定理5-4设f(x)是一个以GF(2)中元素为系数的多项式，是βGF(2)扩域中的一个元素，若是f(x)的一个根，则对任意β，也是f(x)的一个根。国家重点实验室七、多项式因式分解(1)考虑GF(24)，不同元素对应的昀小多项式分别为3α6α7α11α12α14α9α13α1234++++xxxx134++xxα2α4α8α14++xx5α10α()()105αα++xx()151052ααα+++=xx12++=xx()()()()()111111234344215+++++++++++=−xxxxxxxxxxxx国家重点实验室七、多项式因式分解(2)型多项式因式分解方法112−−mx步骤1：首先根据GF(2)上的m次本原多项式，构造GF(2m)步骤2：根据共轭根系的概念，将GF(2m)中的除0和1以外的元素进行分类，即同属一个共轭根系的元素作为一组。步骤3：求每个