信道編碼有限域和多項式

1、第四章 多項式與有限域?qū)W習(xí)本章目的：對Xn-1進(jìn)行因式分解(n=qm-1,q為素數(shù))X15-1=(x+1)(x 4 + x 3+1)(x4+x3+x2 +x +1)(x2 +x +1)(x4+x +1)Xn-1?循環(huán)：只有最高位和最低位一、剩余類環(huán)環(huán)，子環(huán)、擴環(huán)回顧環(huán)（R，+，*）的定義定義了兩種運算+和*R對+構(gòu)成阿貝爾群*滿足封閉性、結(jié)合律*對+滿足分配律*不一定有恒等元1，R的元素不一定有逆元非空子集S是環(huán)（R，+，*）的子環(huán)的充要條件:a,b S:a-b S ; S是群（R，+)的子群a,b S:ab S S對*滿足封閉性一、剩余類環(huán)理想理想定義定義: 交換環(huán)R中的非空子集I稱為R中的

2、理想，若： a, b I: a-b I; a I, r R: ar =ra I;1)+2) 理想是個子環(huán)，2) I 中任一元素a的倍數(shù)在I中，即I由R的一些元素（可以是多個）的倍數(shù)組成。主理想主理想：由一個元素的的所有倍數(shù)組成的理想.這個元素叫生成元.主理想環(huán)主理想環(huán): :每一個理想都是主理想每一個理想都是主理想一、剩余類環(huán)剩余類環(huán)定理定理1 1 (定理4.1.2)：設(shè)I 為可換環(huán)R的一個理想，則R/I構(gòu)成一個可換環(huán)，稱為模模I I的剩余類的剩余類環(huán)環(huán)。例: Mod5的剩余類環(huán)I 0: 05-510-10 .1+I 1:16-411-9.2+I 2:27-312-8 .3+I 3:38-213

3、-7 .4+I 4:49-114-6 . 0,1, 2, 3, 4 對模5+和模5*構(gòu)成可換環(huán)二、多項式剩余類環(huán)多項式wFq上的多項式： f(x)= fnxn +fn-1xn-1+f2x2 +f1x +f0fi Fq i=0,1,2,n次數(shù)n記為：f(x), f, degf(x), degfwWhy多項式？矢量 a a = (1,0,1,1,0,1) （位置）多項式f(x)= x5 +x3+x2 +1 （次數(shù)）為了借用多項式的運算來定義矢量的運算多項式的除法 例：(x9+x8 +x7 +x2+x +1）/（x4+ x3 + x +1）wn次多項式域（群、環(huán)）與n維矢量域（群、環(huán)）在下列映射下同

4、構(gòu)：f(x)= fnxn +fn-1xn-1+f2x2 +f1x +f0 （ fnfn-1f2f1f0）二、多項式剩余類環(huán)w定理定理2 2：集合G與G 同構(gòu) （G為群(環(huán)、域) G為群(環(huán)、域) ）w首一多項式： fn =1，最高次數(shù)為1，f(x)1。wFqx: 表示系數(shù)屬于Fq的所有多項式的集合多項式環(huán)整數(shù)是一個環(huán)，多項式與整數(shù)類似。定理定理3 3：Fqx構(gòu)成一個環(huán)零元：f(x)=0二、多項式剩余類環(huán)性質(zhì)整數(shù)環(huán)多項式環(huán)零元素0f(x)=0恒等元1f(x)=1不可分解的元素數(shù)既約多項式（除提取常數(shù)，不能進(jìn)行因式分解，定義4.4.2）素多項式=首一 + 既約多項式分解的唯一性a=p1r1p2r2

5、(素數(shù)冪的積）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)二、多項式剩余類環(huán)性質(zhì)整數(shù)環(huán)多項式環(huán)約數(shù) 最大公約數(shù)(a,b),GCD(a,b)最高公因式(定義4.2.3)(是首一多項式）（f(x),g(x), GCD(f(x),g(x)倍數(shù) 最小公倍數(shù)a,b,LCM(a,b)最低公倍式(定義4.2.4)(是首一多項式）f(x),g(x), LCM(f(x),g(x)歐幾里德

6、算法a=qb+r(a,b)=(b,r)(a,b)=Aa+BbA,B為正整數(shù)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例: Z/(8)2.定理定理4 4 (定理4.3.1)：可換群G的任一n 級元素a 皆可生成一個n 階循環(huán)子群 。 循環(huán)群是可換群，所以由其中元素i皆能

7、生成一個循環(huán)群，其階數(shù)為i的級數(shù)。這個循環(huán)群可以是它本身，或是它的子群。四、循環(huán)群循環(huán)群G 的性質(zhì)：G 必為阿貝爾群；a為n 級元素，則 ak 的級為n /(k,n);a為n 級元素，則am = e n| m ;n 階循環(huán)群中每個元素的級數(shù)m滿足m|n. n 級元素a與m 級元素 b 滿足 (n, m) =1, 則 ab為nm 級元素;定理 5 (推論 4.3.3)：n 階循環(huán)群中必有(n)個單位原根。(n) = | a| 0 a n-1且 （a, n ）=1| (歐拉函數(shù)，小于n且與n互素的自然數(shù)的個數(shù))四、循環(huán)群5.由已知循環(huán)群尋找其全部子群 （定理4.3.2)G(a)為由a生成的n階有限

8、循環(huán)群，H為G(a)的子群H為有限階循環(huán)群，或者是e,或者是由am 生成的q階循環(huán)群： e，am ，a2m， ， an-m （其中q|n, m= n/q）1) 若m|n,則G中必有唯一的n/m階循環(huán)子群，生成元是am五、有限域GF(q)的乘法結(jié)構(gòu)有限域GF(q)非零元素全體對乘法構(gòu)成阿貝爾群，由定理4，任一非零元素可生成一個有限循環(huán)子群，其階稱為的級，即使n=1的最小正整數(shù)n, 稱為GF(q)的n次單位原根，若n=q-1,則稱為GF(q)-0的生成元，稱為本原域元素。循環(huán)群的單位原根：循環(huán)群的單位原根：n級元素稱為n次單位原根。 本原域元素本原域元素 ( (本原元本原元):): q-1級元素五

9、、有限域GF(q)的乘法結(jié)構(gòu)定理定理 6 6 ：Fq上的n級元素 生成的n階循環(huán)群G()是方程 xn -1 = 0的全部根。證明：設(shè) G() 的級為h h,由定理4，可生成一個階為h的循環(huán)子群，而子群的階必為G()的階n的因子，所以h|n, n = ( h)n/h=1方程xn-1 = 0的根不多于n個，而G()中，n個元素都是它的根，所以全部根落在G()中。推論推論1 1：若Fq含有n次單位原根 ，則xn 1可分解為 。10)(niix五、有限域GF(q)的乘法結(jié)構(gòu)定理定理 7 7：Fq 必有本原域元素存在，所以Fq 0是一個 q-1階乘法循環(huán)群。所以 Fq 0=, 2, , q-2, q-1

10、 =e這稱為有限域的冪表示法。 推論推論2 2 (定理4.4.1)：方程xq-1 1 = 0的全部根構(gòu)成Fq 0. Fq為xq x = 0的全部根，即xq x=x Fq稱為xq x的最小分裂域 推論推論3 3 (費馬費馬FermaFerma定理定理, 定理4.5.5)： Fq: q = . 20)(qiix五、有限域GF(q)的乘法結(jié)構(gòu)例 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,

11、6,7, 8, 9,10, 11,12,13,14級:1,15,15, 5, 15, 3, 5, 15, 15, 5, 3, 15, 5, 15,15級數(shù)為 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)140)(iix140)(iix140)(iix五、有限域GF(q)的乘

12、法結(jié)構(gòu)分園多項式 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至少可分解為分園多項式的積10)(niix ksnqGFndddnsxQxx1)(|)()()1級元素的中為（五、有限域GF(q)的乘法結(jié)構(gòu)定理定理7 7* * (定理4.4.5, p120): (求分園多項式) xn 1 = Q(d)(x)為分圓多項式， Q(d)(x)

13、 = = 為MobiusMobius函數(shù)函數(shù)， (m)= 0, m有平方因子 =(-1)k, m 不含平方因子, 且可分 解為k個因子的積 = 1 , m =1ndddxQ|)()(dmmmdmx|)/() 1(dmmmmdx|)(/) 1(六、有限域GF(q)的加法結(jié)構(gòu)基本概念周期:模擬乘法的級 a+a +a +a +a =na =0 n個a 相加，即加法冪，記為na (課本的na不是n乘a） 任意aGF(q)(a0),滿足na =0的最小正整數(shù)或。2）特征：乘法單位元e的周期，即滿足ne=0的最小正整數(shù)n,如果nN:ne 0,則稱域的特征為 a=a*e na = a+a + +a =a*e

14、+a*e+ +a*e =a*(e+e+e)= a*(ne)=0（根據(jù)分配律）n個六、有限域GF(q)的加法結(jié)構(gòu)定理8：域中任一非零元素的周期都等于域的特征（定理4.5.1)域整數(shù)：a = ze (z Z Z) (e的倍數(shù)) 例如GF(4)=0，1，2，3中， 1+1=0，周期為2 0、1為域整數(shù)定理9：域的特征或為素數(shù)，或為。（定理4.5.2) 假設(shè)特征h不為素數(shù)，h=m*n,則 he=(m*n)e = m(ne)=0 ne的周期 m h,這與定理8矛盾。 （根據(jù)結(jié)合律）m*n個e相加 m個(ne)相加六、有限域GF(q)的加法結(jié)構(gòu)定理10：在p特征域GF(q)中，全體域整數(shù)構(gòu)成p階素子域GF

15、(p),且同構(gòu)于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特征域的域整數(shù)，則 = k (nN N )(推論4.5.4) 沒有真子域P為素數(shù)X可以取擴域GF(q)中的元素npkkezezezezezkZzezknnnnnpppppppp)()()()() ,1111（六、有限域GF(q)的加法結(jié)構(gòu)定理定理1212: 在p特征域Fq中：元素a為域整數(shù) ap-a = 0 (定理4.5.5)2. 最小多項式與本原多項式 最小多項式、元素的次數(shù)

16、、本原多項式最小多項式、元素的次數(shù)、本原多項式： 設(shè)Fq為FQ 的子域， w FQ, m(x)是Fq上滿足 m(w) = 0的次數(shù)最低的首一多項式，稱 m(x)為w 在Fq上的最小多項式，m(x)稱為w 的次數(shù)。若w 為FQ的本原元，則稱m(x)為本原多項式。問題：f（x)=x-w 是不是w的最小多項式？ 六、有限域GF(q)的加法結(jié)構(gòu)定理定理 13 13 (定理4.5.8)：w 在Fq上最小多項式m(x)的性質(zhì)：m(x)在GF(p)上既約；存在且唯一；若Fq上多項式f(x) 滿足 f (w) = 0, 則 m(x) | f (x); （以w為根的多項式是m(x) 的倍式）；m(x) | xq

17、-x. 定理定理 14 14 (相當(dāng)于定理4.6.2)：令f(x)為Fq上任意多項式，則存在擴展域FQ, 在FQ中f(x)可分解為一次因子的積，稱FQ為f(x)的分裂域分裂域。 以素多項式f(x)生成一個有限域Fqx/f(x),在這個域中， 。0)(xf可見，如果f(x)是GF(p)上的素多項式，而且f(w)=0, 則f(x)為w的最小多項式。六、有限域GF(q)的加法結(jié)構(gòu)定理定理 15 15 (課本沒有)：設(shè)Fq為FQ的真子域，是FQ的本原元， 的次數(shù)為m, 則 Q =qm， 且 FQ: = , ai Fq 證：第一步：證Q qm a.形式為 的元素在FQ中設(shè) = , ai Fq ，則 FQ

18、 b.不同形式對應(yīng)不同的元素 設(shè)1= , ai Fq 2= ,bi Fq 且i: aibi 則1 2 反證法，如1 =2，則 在Fq中有次數(shù)比m更小并以為根的素多項式。這與的次數(shù)為m矛盾 形式為 的元素有qm個，全部落在FQ中，所以Q qm10miiia10miiia10miiia10miiia10miiib0)(1021miiiiba10miiia六、有限域GF(q)的加法結(jié)構(gòu)第二步：證Q qm 為FQ的本原域元素，則 FQ: = k 又設(shè)在Fq的最小多項式為 f(x)=xm+fm-1xm-1+ fm-2xm-2+f1x+f0 則f( )= m+fm-1 m-1+ fm-2 m-2+f1 +

19、f0 =0， . k可表示為（ m-1， m-2 ， ,1)的線性組合，而（ m-1， m-2 ， ,1)的線性組合共qm個，所以Q qm 綜上述，Q=qm推論推論5 (定理4.6.1)：有限域 的階必為其特征的冪，因此它是素數(shù)的冪。 10miiimf2011012011101miiimiiimmiiimmmiiimmffffff）（六、有限域GF(q)的加法結(jié)構(gòu)3共軛根: 定理定理1616 （定理4.5.6）: f(x)為Fp上的多項式， w為Fp的擴展域上的元素且f (w) = 0, 則對于n N N, , 有 ,叫w的共軛根共軛根，共軛根的集合組成共軛根系共軛根系 設(shè)w為f(x)的根（F

20、pm 的元素）,觀察共軛根:n=0, 1, 2, ,m-1, m, m+1, , w,wp, , , , , 所以 ，方程f(x)=0的共軛根,最多m個。設(shè)m為滿足wpk=w的最小正整數(shù)k, 則w的共軛根有m個，這m個根實際上是由m個共軛根組成的m/ m 個循環(huán)。所以m|m 設(shè)w的級數(shù)為n,則n|pm-1, 所以pm1 （mod n)P P對模對模n n的方次數(shù)的方次數(shù): 滿足pm 1 (mod n )的最小整數(shù)m稱為p對模n的方次數(shù)0)(npwfnpw2pw1mpwwwmppppppwwwmm)(六、有限域GF(q)的加法結(jié)構(gòu)定理定理1616* * （推論4.5.7）：各個共軛根的級數(shù)相同，

21、最小多項式相同。 w的級為n,則wp的級為n/(n,p)=n定理定理17 17 （定理4.5.9）：設(shè)w是Fq的擴展域FQ的n級元素，而m是q對模n的方次數(shù)，則w的次數(shù)為m, 且其在Fq上的最小多項式m(x) = 多項式的周期 多項式多項式 f(x)f(x)的周期的周期p(f):p(f): 設(shè)f(x) Fqx, f(0)0, 滿足 f(x)|(xl-1) 的最小正整數(shù)l. 定理定理17 17 * * p(f)p(f)的性質(zhì)的性質(zhì): p(f)等于Fqx/f(x)中 的級數(shù)。10)(miqiwxx七、有限域GF(q)的代數(shù)結(jié)構(gòu)定理定理18 18 （定理4.6.3）(1) s | r ; （正向可直

22、接從定理15推出）(2) 定理定理19 19 （定理4.6.4）Fq,nN N: :定理定理20 20 (定理4.6.6） - - x = = ( - - x可分解為次數(shù)為m的因子的素多項式的積)定理定理21 21 (定理4.6.7） f(x)為Fq上的d次既約多項式，且d|m, 則任一 含有f(x)的全部根。 rpFspFmqxmxfxfxf| )()()(且，為素多項式mqxmqFrrspppFF:0nq七、有限域GF(q)的代數(shù)結(jié)構(gòu)定理定理22 22 (定理4.6.8） Fq上的m次既約多項式的數(shù)目是 . (d)為Mobius函數(shù)。 mdddmqdm1|/)(/八、小結(jié)乘法結(jié)構(gòu)Fq-0一

23、定是q-1階乘法循環(huán)群，F(xiàn)q=0， 2，, q-2， q-1=e,叫 有限域的冪表示法Fq 一定是方程xq-x=0的全部根，所以xq-x可分解為1次因式的積加法結(jié)構(gòu)Fq的特征p一定是素數(shù),而且滿足q = pm.給出任一素數(shù)p和正整數(shù)m,一定存在GF(pm). . 任意兩個同階的域同構(gòu).所有方法生成的有限域本質(zhì)上是一樣的，只是表示方法（即加法表與乘法表不一樣）不一樣，只要找到一種方法生成即可。0)(11qiiqxxxx八、小結(jié)如何求GF(pm)?a)求以P為特征的域Fp=e,2e,pe=0b) 求Fp上的m次素多項式f(x).（可查表,共有 個,見定理22)c) 求有限域的剩余類表示法，去掉帽子

24、得多項式表示法，可映射為矢量表示法(f(x)=fmxm+fm-1xm-1+,+f1x+f0映射為(fm,fm-1,.,f1,f0)f(x)=0（定理14）,f(x)為x的最小多項式，設(shè)f(x)的周期為n,則x為n級元素（定理17*），m為p關(guān)于模n的方次數(shù)（定理17），如n=pm-1,則f(x)為本原多項式，x為本原元, 這時多項式表示法與冪表示法結(jié)合起來例，構(gòu)造GF(4)mdddmqdm1|/)(/,., 1 , 0)(/ 1, 0mFfkkkppkxfxxfxF考察元素x八、小結(jié)因式分解定理定理 14 14 (相當(dāng)于定理4.6.2)：令f(x)為Fq上任意多項式，則存在擴展域FQ, 在FQ中f(x)可分解為一次因子的積，稱FQ為f(x)的分裂域分裂域。GF(pm) 是方程xpm-x=0的全部根，所以在GF(pm)中， xpm-1-1可分解為一次因式的積，即 （1）把（1）式同級元素相乘，得分園多項式（Fp上，但不一定是素多項式），所以根據(jù)定理7*，Q(d)(x) = =根據(jù)定理17，把（1）式共軛根的一次因式相乘，得最小多項式(Fp上，是素多項式),所以 其中，r為ws對模n的方次數(shù)，n為ws的級數(shù)，ms(x)為第s個共扼根系共扼根對應(yīng)的最小多項式