《第5章 有限域及BCH码》由会员分享，可在线阅读，更多相关《第5章 有限域及BCH码（171页珍藏版）》请在金锄头文库上搜索。
1、1,第5章 有限域及BCH码,2,第1节 循环群及性质,3,循环群(P113),循环群的定义 循环群的构造及性质 循环群中元素级的性质,4,定义：由一个单独元素的所有幂次所构成的群称为循环群，该元素为循环群的生成元注： 1、幂次的含义与在群上所定义的运算有关。若定义加法运算，幂运算为连加运算；若定义乘法运算，则幂运算为连乘。2、循环群的生成元不止一个。2、凡是循环群必是可换群。,循环群的定义,5,Examples:模4剩余类全体关于加法运算构成循环群，生成元为1和3。模5全体非零剩余类关于乘法构成循环群，生成元为2和3,6,有限循环群和无限循环群若元素a的所有幂次均不相同(无限循环群)存在整数
2、 h和k，使得ak=ah，则有a生成的循环群中元素个数有限(有限循环群)循环群元素的级若ak=ah，则有ah-k=e，定义使an=e的最小正整数为有限循环群元素a的级。,循环群的构造及性质,7,1、若元素a的级为n，则a0=e,a,a2,an-1均互不相同2、若a为n级元素，则a的一切幂次生成的元素都在群G(a)中3、凡是循环群必是可换群4、可换群G中的每一个元素a都能生成一个循环群。若a为有限级，则生成有限循环群， a的级即为循环群中元素的个数(循环群的阶),有限循环群的几个特点,8,1、若a是n级元素，则am=e的充要条件是,2、若a是n级元素， b是m级元素，且(n,m)=1,则 (ab
3、)的级为nm,3、若a是n级元素， 则ak的级为n/(k,n),4、若a是dk级元素， 则ak为d级元素,5、n阶循环群中，每个元素的级是群阶数n的因子,6、n阶循环群中有,个单位原根,有限循环群元素级的性质,9,单位原根：n阶循环群中，每一个n级元素称为n次原根欧拉函数：0,1,2,n-1中与n互素的元素个数称为欧拉函数。,两个定义,10,第2节 有限域及性质,最重要的三个概念 最小多项式 本原多项式 共轭根系,11,域(Field)的定义(p31),非空集合F，若F中定义了加和乘两种运算，且满足：1) F关于加法构成阿贝尔群，加法恒等元记为02) F中所有非零元素对乘法构成阿贝尔群，乘法恒
4、等元记为13) 加法和乘法之间满足分配律,12,一、 有限域的乘法结构,定理5-1 设a为有限域GF(q)中的一个非零元素，则必有,证明：,令,为GF(q)中的q-1个非零元素，,显然,是q-1个互异的元素，因此有,注：GF(q)中的非零元素是方程xq-1-1=0的根,13,一、 有限域的乘法结构,定理5-2 设a为有限域GF(q)中的一个非零元素，n为a的级，则n必能整除q-1,证明：,假设n不能整除q-1，可得到q-1=kn+r,其中，0rn，由定理5-1得到,因此，a的级将小于n，与题设矛盾，故n必能整除q-1.,14,一、 有限域的乘法结构,结论1：域的乘法群必为某一个元素生成的循环群
5、，即q元域中必能找到一个，其级为q-1。,结论2：所有有限域元素都能表示成生成元的幂次的形式，此时的生成元称为本原元。,15,二、有限域的加法结构,域的特征：满足ne=0的最小n值为域的特征，注意这里e为乘法单位元，0为域的零元，n取自正整数 元素的周期：对域中元素a，满足na=0的最小n值为a的周期。（注意对于域而言，在加法上用周期，在乘法上用级）,16,域中非0元的周期都相同，且与域的特征相等GP(q)为GF(qm)的基域，GF(qm)为GF(q)的扩域,二、有限域的加法结构,17,三、最小多项式,系数取自GF(q)的，以w为根的所有首一多项式中，次数最低的称为w的最小多项式m(x)，w的
6、最小多项式的次数m称为w的次数，称w为m次域元素 m(x)在GF(q)上不可约 若w也是f(x)的根，则m(x)可整除f(x),18,四、本原多项式,GF(p)上的m次不可约多项式p(x)，若能被p(x)整除xn-1的最小正整数n=2m-1，则称p(x)为GF(q)上的m次本原多项式。在GF(qm)中，以本原元为根的最小多项式称为该域的本原多项式,19,本原多项式的例子,x4+x+1是GF(2)上的4次本原多项式。x3+x2+x+1是不可约多项式，但由于它能整除x5-1，因此它不是本原多项式。,20,五、有限域GF(2m)的构造,定理5-3 GF(2)上的任意m次不可约多项式必整除,有限域GF
7、(2m)的构造,假设p(x)是GF(2)上的m次本原多项式， 是p(x)的一个根，即,由于,因此可构造集合,21,五、有限域GF(2m)的构造(2),例：设m=4，多项式p(x)=1+x+x4是 GF(2)上的4次本原多项式，设 ，用这个关系构造GF(24),22,五、 有限域GF(2m)的构造(3),GF(24 )中元素的三种表示方法,幂表示,多项式表示,4维向量表示,(0000),(1000),(0100),(0010),(0001),(1100),(0110),(0011),(1101),(1010),(0101),(1110),(0111),(1111),(1011),(1001),2
8、3,六、有限域GF(2m)的性质,很多情况下，实系数的多项式的根不在实数域里，而在以实数域为子域的复数域里。X2+6x+25没有实数域的根，但有两个复根-3+4i和-3-4i以GF(2)中的元素为系数的多项式，可能在GF(2)上没有根，但在GF(2)的扩域中有根。,24,六、有限域GF(2m)的性质(2),x4+x3+1在GF(2)上不可约，因此没有GF(2)上的根，但它在GF(24)上有4个根,25,六、有限域GF(2m)的性质(3),26,六、有限域GF(2m)的性质(4),27,六、有限域GF(2m)的性质(5),也是f(x)的根。,称为一个共轭根系。,28,六、有限域GF(2m)的性质
9、(6),定理5-5,GF(2m)中的2m-1个非零元素构成,的全部根。,对GF中的任一非零元素，有,证明：,29,六、有限域GF(2m)的性质(7),定理5-6,设 是GF(2m)中的元素 的最小多项式，且e,是满足 的最小正整数，则,30,六、有限域GF(2m)的性质(8),31,六、有限域GF(2m)的性质(9),32,六、有限域GF(2m)的性质(10),定理5-8,设 是GF(2m)中的本原元，则 的所有共轭,则 也是GF(2m)的本原元。,定理5-9,设 是GF(2m)中的n级元素，则 的所有共轭,则 也是GF(2m)的 n级元素。,33,有限域GF(2m)的构造,GF(24 )中元
10、素的三种表示方法，由本原多项式x4+x+1生成,幂表示,多项式表示,4维向量表示,(0000),(1000),(0100),(0010),(0001),(1100),(0110),(0011),(1101),(1010),(0101),(1110),(0111),(1111),(1011),(1001),34,最小多项式求解,35,七、多项式因式分解(1),考虑GF(24)，不同元素对应的最小多项式分别为,36,七、多项式因式分解(2),型多项式因式分解方法,步骤1：首先根据GF(2)上的m次本原多项式，构造GF(2m),步骤2：根据共轭根系的概念，将GF(2m)中的除0和1以外的元素进行分类
11、，即同属一个共轭根系的元素作为一组。,步骤3：求每个共轭根系的最小多项式。,步骤4：所有最小多项式的连乘，可得到多项式 ，即多项式可分解的因式是GF(2m)中除0以外所有元素的最小多项式。,37,七、多项式因式分解(3),例 试对GF(2)上的多项式x7-1进行因式分解。,根据GF(2)上的3次本原多项式x3+x+1，得到扩域GF(23)。,为一个共轭根系，对应的最小多项式是本原多项式。,为一个共轭根系，对应的最小多项式为,38,七、多项式因式分解(4),所以,39,七、多项式因式分解(5),问题：,对任意多项式xn-1，如何进行因式分解？,40,七、多项式因式分解(6),基本步骤,步骤1：首
12、先寻找一个扩域GF(2m)，满足2m-1可被n整除,步骤2：从扩域GF(2m)中的所有元素中，挑出级为n的因子的元素。,步骤3：将挑出的元素按照共轭根系进行分组，每组计算一个最小多项式。,步骤4：将得到的所有最小多项式连乘，再乘(x+1)，就得到xn-1的因式分解结果。,41,第3节 用生成多项式的根定义循环码(p152),研究表明，生成多项式有重根的码一般都要比无重根的码差，因此只考虑无重根的码，或构造无重根的多项式。 循环码的编码问题转化为：如何由给定的根来得到生成多项式g(x)? GF(q)上多项式xn-1无重根的充要条件是n与q互素。因此对GF(2)而言，充要条件即为n为奇数。,42,
13、用指定的根确定码长和生成多项式(1),假设循环码的生成多项式以 为根, 且 的最小多项式为mi(x),因此，生成多项式g(x)同时被m1(x),m2(x),mr(x)整除时，它才能以 为根。,生成多项式是所有根的最小多项式的最小公倍式,43,用指定的根确定码长和生成多项式(2),由于生成多项式是多项式xn-1的因式，因此 也是多项式 xn-1的根。n必能被每个根的级整除。,44,用指定的根求生成多项式(3),给定必含根 ，求生成多项式g(x)时，要先找出各个根的最小多项式（可计算或查表），然后求它们的公倍式。由于共轭根系的最小多项式相同，需先要找出必含根中包括哪几个共轭根系,45,用根形成生成
14、多项式举例1,GF(24)中，为本原元，求以 、 2、 4为根的二进制循环码。,GF(24)中，以为根的本原多项式为x4+x+1， 、 2和 4为同一个共轭根系，因此所求的二进制循环码的生成多项式为：,为一个15,11,3的循环汉明码。,46,由生成多项式根定义的校验矩阵(1),若g(x)有r个不相等的根，则每个根必为每个码多项式的根，可将所有根代入是否为零来验证是否为码多项式； 也可由此得到循环码的校验矩阵。（此处的运算是在扩域GF(qm)上的）,47,由生成多项式根定义的校验矩阵(2),有,设15,11循环汉明码的码多项式为,48,由生成多项式根定义的校验矩阵(3),转化为二进制，上述H矩
15、阵是12行15列。,15,11循环码的校验矩阵应该为4行15列的矩阵，因此上式 H矩阵中，仅有4行是线性无关的,如何从上式中，挑出线性无关的4行，构成校验矩阵呢？,49,由生成多项式根定义的校验矩阵(4),定理5-10(P154) 若H矩阵的元素均在GF(qm)中，且第j行元素等于 第i行相应元素的q次幂，则在GF(q)中，由第j行元素所组成的m行， 与第i行元素所组成的m行之间，每行均线性相关。,由定理5-10可知，15,11循环码的校验矩阵为,50,用根形成生成多项式举例2,GF(24)中，为本原元，求以1、 、 2、 4为根的二进制循环码。,GF(24)中，以为根的本原多项式为x4+x+1， 、 2和 4为同一个共轭根系，因此所求的二进制循环码的生成多项式为：,51,用根形成生成多项式举例3,GF(24)中，为本原元，求以 、 2、 3、 4 、 5为根的二进制循环码。,GF(24)中，以为根的本原多项式为x4+x+1， 、 2和 4为同一个共轭根系,
