信道编码有限域和多项式

《信道编码有限域和多项式》由会员分享，可在线阅读，更多相关《信道编码有限域和多项式（38页珍藏版）》请在金锄头文库上搜索。

1、第四章 多项式与有限域 学习本章目的：对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对*满足封闭性 一、剩余类环 理想 定义: 交

2、换环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 (定理4.1.2)：设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-

3、213-7 . 4+I 4: 49-114-6 . 0,1, 2, 3, 4 对模5+和模5*构成可换 环 二、多项式剩余类环 多项式 w Fq上的多项式： f(x)= fnxn +fn-1xn-1+f2x2 +f1x +f0 fi Fq i=0,1,2,n 次数n记为：f(x), f, degf(x), degf w Why多项式？ 矢量 a = (1,0,1,1,0,1) （位置） 多项式f(x)= x5 +x3+x2 +1 （次数） 为了借用多项式的运算来定义矢量的运算 多项式的除法 例：(x9+x8 +x7 +x2+x +1）/（x4+ x3 + x +1 ） w n次多项式域（群、环

4、）与n维矢量域（群、环）在 下列映射下同构： f(x)= fnxn +fn-1xn-1+f2x2 +f1x +f0 （ fnfn-1f2f1f0 ） 二、多项式剩余类环 w 定理2：集合G与G 同构 （G为群(环、域 ) G为群(环、域) ） w 首一多项式： fn =1，最高次数为1， f(x)1。 w Fqx: 表示系数属于Fq的所有多项式的集 合 多项式环 w 整数是一个环，多项式与整数类似。 w 定理3：Fqx构成一个环 零元：f(x)=0 二、多项式剩余类环 性质整数环多项式环 零元素0f(x)=0 恒等元1f(x)=1 不可分 解的元 素数既约多项式（除提取常数，不能 进行因式分解

5、，定义4.4.2） 素多项式=首一 + 既约多项式 分解的 唯一性 a=p1r1p2r2 (素数幂的积） f(x)=p1(x)r1p2 (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) 倍数 最小公倍

6、数 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)= x9+x8+x7+x2+x+1,g(x)=x4+x3+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

7、 例: Z/(8) 2.定理4 (定理4.3.1)：可换群G的任一n 级元素 a 皆可生成一个n 阶循环子群 。 w 循环群是可换群，所以由其中元素i皆能生成一个 循环群，其阶数为i的级数。 w 这个循环群可以是它本身，或是它的子群。 四、循环群 循环群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 (推论 4.3.3)：n 阶循环群中必有 (n)个单位原根。 (n) =

8、| a| 0 a n-1且 （a, n ）=1| (欧拉函数，小于n且与n互素的自然数的个 数) 四、循环群 5.由已知循环群寻找其全部子群 （定理4.3.2) G(a)为由a生成的n阶有限循环群，H为G(a)的子群 1) H为有限阶循环群，或者是e,或者是由am 生成的q 阶循环群： e，am ，a2m， ， an-m （其中q|n, m= n/q） 1) 若m|n,则G中必有唯一的n/m阶循环子群，生成元是am 五、有限域GF(q)的乘法结构 有限域GF(q)非零元素全体对乘法构成阿 贝尔群，由定理4，任一非零元素可生 成一个有限循环子群，其阶称为的级， 即使n=1的最小正整数n, 称为G

9、F(q)的 n次单位原根，若n=q-1,则称为GF(q)- 0的生成元，称为本原域元素。 w 循环群的单位原根：n级元素称为n次单位原 根。 w 本原域元素 (本原元): 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可分解

10、为 。 五、有限域GF(q)的乘法结构 定理 7：Fq 必有本原域元素存在，所以Fq 0是 一个 q-1阶乘法循环群。所以 Fq 0=, 2, , q-2, q-1 =e 这称为有限域的幂表示法。 推论2 (定理4.4.1)：方程xq-1 1 = 0的全部根构成 Fq 0. Fq为xq x = 0的全部根，即xq x=x Fq称为xq x的最小分裂域 推论3 (费马Ferma定理, 定理4.5.5)： Fq: q = . 五、有限域GF(q)的乘法结构 例 GF(2)上的多项式x15 1= GF(16)-0=1 , , 2, 3 , , 14 每个元素的级是15的因子，15的因子有1、3、5、

11、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)

12、=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): (求分园多项式) xn 1 = Q(d)(x)为分圆多项式， Q(d)

13、(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 （根据分配律）

14、n个 六、有限域GF(q)的加法结构 w 定理8：域中任一非零元素的周期都等于域的特征（定 理4.5.1) w 域整数：a = ze (z Z) (e的倍数) 例如GF(4)=0，1，2，3中， 1+1=0，周期为2 0、1为域整数 w 定理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)的加法结构 w 定理10：在p特征域GF(q)中，全体域整数构成p阶 素子域GF(p),且同构于Z/(p)(定理4.5.3)

15、w GF(p)称为GF(q)的基域，GF(q)称为GF(p)的扩域。 w 定理11：p特征域GF(q)中， (定理4.5.4) aGF(q):(x-a)p=xp ap w 推论4: 若k是p特征域的域整数，则 = k (nN ) (推论4.5.4) 没有真子域 P为素数 X可以取扩域GF(q)中的元素 六、有限域GF(q)的加法结构 w 定理12: 在p特征域Fq中：元素a为域整数 ap-a = 0 (定理4.5.5) 2. 最小多项式与本原多项式 w 最小多项式、元素的次数、本原多项式： 设Fq为FQ 的子域， w FQ, m(x)是Fq上满足 m(w) = 0的次数最低的首一多项式，称 m(x)为w 在Fq上 的最小多项式，m(x)称为w 的次数。若w 为FQ的 本原元，则称m(x)为本原多项式。