糾錯(cuò)碼Lecture11-有限域(I)

1、信道編碼理論信道編碼理論邢莉娟，李卓，西安電子科技大學(xué)邢莉娟，李卓，西安電子科技大學(xué)Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論2近世代數(shù)基本知識(shí)復(fù)習(xí)近世代數(shù)基本知識(shí)復(fù)習(xí)子環(huán)與理想子環(huán)與理想循環(huán)群循環(huán)群有限域的乘法結(jié)構(gòu)有限域的乘法結(jié)構(gòu)Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論3同余同余若整數(shù)若整數(shù)a和和b被同一正整數(shù)被同一正整數(shù)m除時(shí)，有相同的余數(shù)，則稱除時(shí)，有相同的余數(shù)，則稱a、b關(guān)于模關(guān)于模m同余，記為同余，記為若若 則則剩余類剩余類給定正整數(shù)給定正整數(shù)m，將全體整數(shù)按余數(shù)相同進(jìn)行分類，可獲，

2、將全體整數(shù)按余數(shù)相同進(jìn)行分類，可獲得得m個(gè)剩余類：個(gè)剩余類：)(modmba 1, 1 , 0mbabababa,1122(mod), (mod),abmabm12121212(mod), (mod)aabbmaab bmLecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論4代數(shù)系統(tǒng)代數(shù)系統(tǒng) 滿足一定規(guī)律或定律的系統(tǒng)稱為滿足一定規(guī)律或定律的系統(tǒng)稱為代數(shù)系統(tǒng)代數(shù)系統(tǒng)。且有：。且有：1. 有一群元素構(gòu)成一個(gè)集合；有一群元素構(gòu)成一個(gè)集合；2. 在元素集合中有一個(gè)等價(jià)關(guān)系；在元素集合中有一個(gè)等價(jià)關(guān)系；3. 在集合中定義了一個(gè)或數(shù)個(gè)運(yùn)算，通過運(yùn)算建立起元在集合中定

3、義了一個(gè)或數(shù)個(gè)運(yùn)算，通過運(yùn)算建立起元素之間的關(guān)系；素之間的關(guān)系；4. 有一組假定。有一組假定。同態(tài)與同構(gòu)：同態(tài)與同構(gòu)： 設(shè)設(shè)f是代數(shù)系統(tǒng)是代數(shù)系統(tǒng)(A, )到到( (B,*)的映射，如果它滿足條件的映射，如果它滿足條件 f(a1 a2) =f(a1) *f(a2) a1 ,a2 A, f(a1) ,f(a2) B 則稱則稱f是是A到到B的的同態(tài)映射同態(tài)映射，集合，集合A與與B同態(tài)同態(tài)。如果同態(tài)。如果同態(tài) 映射映射f又是雙射，則稱為又是雙射，則稱為同構(gòu)映射同構(gòu)映射，集合，集合A與與B同構(gòu)同構(gòu)。若若f是是A 到到A自身的同構(gòu)映射，則稱為自身的同構(gòu)映射，則稱為自同構(gòu)自同構(gòu)。Lecture 11 Le

4、cture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論5設(shè)設(shè)G是一個(gè)非空集合，并在是一個(gè)非空集合，并在G內(nèi)定義了一種代數(shù)運(yùn)算內(nèi)定義了一種代數(shù)運(yùn)算 “ ?！保魸M足：，若滿足： 則稱則稱G構(gòu)成一個(gè)群。構(gòu)成一個(gè)群。 若加法，恒等元用若加法，恒等元用0表示，表示， 若為乘法，恒等元稱為單位元若為乘法，恒等元稱為單位元阿貝爾群阿貝爾群(Abelian Group)、可換群、交換群：、可換群、交換群：滿足交換律滿足交換律Gba,1) 封閉性。對(duì)任意，恒有GbaGcba,2) 結(jié)合律。對(duì)任意，恒有cbacba3) G中存在一恒等元e,對(duì)任意Ga，使aaeea4) 對(duì)任意Gaeaaaa11，存在

5、a的逆元Ga1，使Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論6非空集合非空集合R中，若定義了兩種代數(shù)運(yùn)算中，若定義了兩種代數(shù)運(yùn)算加加和和乘乘，且滿足：且滿足：1) 集合R在加法運(yùn)算下構(gòu)成阿貝爾群2) 乘法有封閉性3) 乘法結(jié)合律成立，且加和乘之間有分配律環(huán)環(huán)阿貝爾加群乘法半群阿貝爾加群乘法半群相關(guān)概念相關(guān)概念有單位元環(huán)（乘法有單位元）交換環(huán)（乘法滿足交換率）整環(huán)（無零因子環(huán)）Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論7定義：非空集合定義：非空集合F，若，若F中定義了中定義了加加和和乘乘兩種運(yùn)算，

6、且滿兩種運(yùn)算，且滿足：足： 1) F關(guān)于關(guān)于加法構(gòu)成阿貝爾群加法構(gòu)成阿貝爾群，加法恒等元記為，加法恒等元記為0 2) F中所有中所有非零元素對(duì)乘法構(gòu)成阿貝爾群非零元素對(duì)乘法構(gòu)成阿貝爾群，乘法恒等元，乘法恒等元 記為記為1 3) 加法和乘法之間滿足加法和乘法之間滿足分配律分配律域是一個(gè)域是一個(gè)可換的、有單位元、非零元素有逆元可換的、有單位元、非零元素有逆元的環(huán)，且域的環(huán)，且域中一定中一定無零因子無零因子。元素個(gè)數(shù)無限的域稱為元素個(gè)數(shù)無限的域稱為無限域；無限域；元素個(gè)數(shù)有限的域稱為元素個(gè)數(shù)有限的域稱為有有限域限域，用，用GF(q)或或Fq表示表示q階有限域。有限域也稱為階有限域。有限域也稱為伽邏華

7、伽邏華域域。Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論8定義定義若環(huán)若環(huán)R中的子集中的子集S，在環(huán)，在環(huán)R中的定義的代數(shù)運(yùn)算也構(gòu)中的定義的代數(shù)運(yùn)算也構(gòu)成環(huán)，則稱成環(huán)，則稱S為為R的子環(huán)，的子環(huán)，R為為S的擴(kuò)環(huán)的擴(kuò)環(huán)判定判定非空子集非空子集S是是R的子環(huán)的充要條件是：的子環(huán)的充要條件是： 對(duì)任何兩個(gè)元素對(duì)任何兩個(gè)元素a, bS ， 恒有恒有a-b S； 對(duì)任何兩個(gè)元素對(duì)任何兩個(gè)元素a, bS， 恒有恒有ab S；例子例子全體整數(shù)集合構(gòu)成一個(gè)可換環(huán)。以某一整數(shù)全體整數(shù)集合構(gòu)成一個(gè)可換環(huán)。以某一整數(shù)m的倍的倍數(shù)全體構(gòu)成其中的一個(gè)子環(huán)。如數(shù)全體構(gòu)成其中

8、的一個(gè)子環(huán)。如m=3, 集合集合, -3, 0, 3, 構(gòu)成一個(gè)子環(huán)構(gòu)成一個(gè)子環(huán)Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論9理想理想非空子集非空子集I是是交換環(huán)交換環(huán)R的理想的充要條件是：的理想的充要條件是： 對(duì)任何兩個(gè)元素對(duì)任何兩個(gè)元素a, bI ， 恒有恒有a-b I；Abel加群加群 對(duì)任何兩個(gè)元素對(duì)任何兩個(gè)元素a I, rR， 恒有恒有ar=ra I；若若I包含了包含了a，則包含了則包含了a的一切倍元的一切倍元I構(gòu)成一個(gè)構(gòu)成一個(gè)Abel加群，所以可用它作為一個(gè)正規(guī)子群，加群，所以可用它作為一個(gè)正規(guī)子群，把把R中的元素進(jìn)行分類劃分陪集中的

9、元素進(jìn)行分類劃分陪集主理想主理想若理想中的元素由一個(gè)元素的所有倍數(shù)及其線性組合若理想中的元素由一個(gè)元素的所有倍數(shù)及其線性組合生成，則稱這個(gè)理想為生成，則稱這個(gè)理想為主理想主理想。在可換環(huán)在可換環(huán)R中，由一個(gè)元素中，由一個(gè)元素a R所生成的理想所生成的理想I(a)=ra + na|r R, n Z稱為環(huán)稱為環(huán)R的一個(gè)的一個(gè)主理想主理想，稱元素，稱元素a為為該主理想的該主理想的生成元生成元Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論10定義定義設(shè)設(shè)R是可換環(huán)，是可換環(huán)，I為為R的一個(gè)理想，于是的一個(gè)理想，于是R模模I構(gòu)成一構(gòu)成一個(gè)可換環(huán)，稱它為環(huán)個(gè)可

10、換環(huán)，稱它為環(huán)R以理想以理想I為模的為模的剩余類環(huán)剩余類環(huán)例例R=Z，I3=, -3, 0, +3, ，R以以I劃分陪集為劃分陪集為集合集合 構(gòu)成一個(gè)可換環(huán)構(gòu)成一個(gè)可換環(huán)0, 3,0,3,;1, 2,1,4,;2, 1,2,5,0, 1, 2 Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論11多項(xiàng)式多項(xiàng)式 f(x)=fnxn+ fn-1xn-1+ f1x+f0 其中其中 i=0,1,n，該多項(xiàng)式稱為域該多項(xiàng)式稱為域Fp上的多項(xiàng)式上的多項(xiàng)式多項(xiàng)式次數(shù)多項(xiàng)式次數(shù) degf(x)系數(shù)不為零的系數(shù)不為零的x的最高次數(shù)稱為多項(xiàng)式的最高次數(shù)稱為多項(xiàng)式f(x)的

11、次數(shù)的次數(shù)首一多項(xiàng)式首一多項(xiàng)式最高次數(shù)的系數(shù)為最高次數(shù)的系數(shù)為1的多項(xiàng)式的多項(xiàng)式既約多項(xiàng)式既約多項(xiàng)式設(shè)設(shè)f(x)是次數(shù)大于零的多項(xiàng)式，若除常數(shù)和常數(shù)與本是次數(shù)大于零的多項(xiàng)式，若除常數(shù)和常數(shù)與本身的乘積以外，再不能被域身的乘積以外，再不能被域Fp上的其他多項(xiàng)式整除，上的其他多項(xiàng)式整除，則稱則稱f(x)為域?yàn)橛騀p上的既約多項(xiàng)式上的既約多項(xiàng)式f(x)是否既約與討論的域有關(guān)：是否既約與討論的域有關(guān)：f(x)=x2+1在實(shí)數(shù)域上在實(shí)數(shù)域上既約，但在復(fù)數(shù)域上既約，但在復(fù)數(shù)域上f(x)=(x+i)(x-i)piFf Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理

12、論12每一個(gè)首一多項(xiàng)式必可分解為首一既約多項(xiàng)式之積，并且每一個(gè)首一多項(xiàng)式必可分解為首一既約多項(xiàng)式之積，并且當(dāng)不考慮因式的順序時(shí)，該分解是唯一的當(dāng)不考慮因式的順序時(shí)，該分解是唯一的 其中，其中，pi(x)為首一既約多項(xiàng)式，為首一既約多項(xiàng)式， 為正整數(shù)為正整數(shù)d次多項(xiàng)式次多項(xiàng)式f(x)不可能有多于不可能有多于d個(gè)的一次因式個(gè)的一次因式, 至多有至多有d個(gè)根個(gè)根為之根的充要條件是為之根的充要條件是 (x-)| f(x) 若若p(x)是是f(x)的的k重既約因式，則重既約因式，則p(x)必是必是f(x)的的k-1重既約重既約因式因式1212( )( )( )( )iif xp xp xp xiLect

13、ure 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論13GCD (f(x), g(x)：同時(shí)除盡：同時(shí)除盡f(x)和和g(x)的次數(shù)最高的首一多的次數(shù)最高的首一多項(xiàng)式項(xiàng)式LCM f(x), g(x)：同時(shí)被：同時(shí)被f(x)和和g(x)除盡的次數(shù)最低的首一除盡的次數(shù)最低的首一多項(xiàng)式多項(xiàng)式f(x) g(x)= (f(x), g(x) f(x), g(x)Euclidean算法算法 (f(x), g(x)=A(x) f(x)B(x) g(x)98725343343335343( )1 ()(1) (1)( )1 (1)(1)( ), ( )1 1( ) ()(1) (

14、 ) ( )( ) ( )f xxxxxxxxx xxxxg xxxxxxf x g xxf xxxx xxxA x f xB x g x Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論14設(shè)設(shè) f(x)=fnxn+ fn-1xn-1+ f1x+f0 g(x)=gmxm+ gm-1xm-1+ g1x+g0多項(xiàng)式相等多項(xiàng)式相等若若m=n，且對(duì)所有，且對(duì)所有i, fi=gi, 則則f(x)=g(x)多項(xiàng)式加（若多項(xiàng)式加（若nm) f(x)+g(x)= fn xn+fm+1xm+1+ (fm + gm)xm+ (f1 + g1)x+(f0 + g0)多項(xiàng)

15、式乘多項(xiàng)式乘 f(x) g(x)=hn+m xn+m+ hn+m-1 xn+m-1+ h1x+h0piFf piFg 0 0,1, 1,iiijjiiiijj i mf gimnmhf gimmn Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論15結(jié)論結(jié)論按上述定義的加法和乘法運(yùn)算，按上述定義的加法和乘法運(yùn)算，F(xiàn)px構(gòu)成一個(gè)構(gòu)成一個(gè)具有單具有單位元、無零因子的可換環(huán)位元、無零因子的可換環(huán)多項(xiàng)式剩余類環(huán)多項(xiàng)式剩余類環(huán)以一個(gè)以一個(gè)Fp上的多項(xiàng)式上的多項(xiàng)式f(x)=fnxn+ fn-1xn-1+ f1x+f0為模的為模的剩余類全體構(gòu)成一個(gè)剩余類全體構(gòu)成一

16、個(gè)多項(xiàng)式剩余類環(huán)多項(xiàng)式剩余類環(huán)Fpx上任一多項(xiàng)式上任一多項(xiàng)式f(x)的一切倍式集合的一切倍式集合If(x)組成一個(gè)理組成一個(gè)理想。以此理想把想。以此理想把Fpx劃分陪集，這些陪集全體就構(gòu)成劃分陪集，這些陪集全體就構(gòu)成了模了模f(x)的剩余類環(huán)的剩余類環(huán)剩余類之間的加法和乘法運(yùn)算規(guī)則剩余類之間的加法和乘法運(yùn)算規(guī)則 xbxaxbxa xbxaxbxaLecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論16GF(2)上的多項(xiàng)式上的多項(xiàng)式 f(x)=x2+1的剩余類全體為：的剩余類全體為：對(duì)所定義的加法和乘法運(yùn)算，對(duì)所定義的加法和乘法運(yùn)算， 構(gòu)成剩余類環(huán)構(gòu)成剩余

17、類環(huán)元素 沒有乘法逆元1, 1 , 0 xx22223322332230: 0 1 (1) (1)(1) 1: 1 1 : 1 1 1:1+ + 1 xx xxxxxxxxxxxxxxxxxxxxx32 xx1x 221 00; 1 11; 111110 xxxxxxxxxxx Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論17GF(2)上的多項(xiàng)式上的多項(xiàng)式 f(x)=x2+x+1的剩余類全體為：的剩余類全體為：對(duì)所定義的加法和乘法運(yùn)算，對(duì)所定義的加法和乘法運(yùn)算， 構(gòu)成域構(gòu)成域結(jié)論：若結(jié)論：若n次首一多項(xiàng)式次首一多項(xiàng)式f(x)在域在域Fp上上既約既

18、約，則，則f(x)的剩余類環(huán)構(gòu)成一個(gè)有的剩余類環(huán)構(gòu)成一個(gè)有pn個(gè)元素的個(gè)元素的有限域有限域1, 1 , 0 xx2222323232320: 0 1 (1) (1)(1) 1: 1 + 1 : 1 1 1:1+ xxx xxxxxxxxxxxxxxxxxxxxx323 1 xxxxLecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論18多項(xiàng)式環(huán)多項(xiàng)式環(huán)Fpx的一切理想均是主理想的一切理想均是主理想多項(xiàng)式剩余類環(huán)多項(xiàng)式剩余類環(huán)Fpx/f(x)中的每一個(gè)理想都是主中的每一個(gè)理想都是主理想。且該主理想的生成元必除盡理想。且該主理想的生成元必除盡f(x)GF(2

19、)上二次多項(xiàng)式與上二次多項(xiàng)式與GF(2)上的三重。它們的元上的三重。它們的元素具有如下的一一對(duì)應(yīng)關(guān)系素具有如下的一一對(duì)應(yīng)關(guān)系 且在適當(dāng)定義運(yùn)算之后具有同樣的性質(zhì)與結(jié)構(gòu)。且在適當(dāng)定義運(yùn)算之后具有同樣的性質(zhì)與結(jié)構(gòu)。稱具有這種對(duì)應(yīng)關(guān)系的兩個(gè)集合為稱具有這種對(duì)應(yīng)關(guān)系的兩個(gè)集合為同構(gòu)同構(gòu)2; , ,0,1abxcxabca b cLecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論19定義定義：由一個(gè)單獨(dú)元素的所有由一個(gè)單獨(dú)元素的所有冪次冪次所構(gòu)成的群稱所構(gòu)成的群稱為為循環(huán)群循環(huán)群，該元素為循環(huán)群的，該元素為循環(huán)群的生成元生成元冪次的含義與在群上所定義的運(yùn)算有關(guān)。

20、若定義加法冪次的含義與在群上所定義的運(yùn)算有關(guān)。若定義加法運(yùn)算，冪運(yùn)算為連加運(yùn)算；若定義乘法運(yùn)算，則冪運(yùn)運(yùn)算，冪運(yùn)算為連加運(yùn)算；若定義乘法運(yùn)算，則冪運(yùn)算為連乘。算為連乘。循環(huán)群的生成元不止一個(gè)。循環(huán)群的生成元不止一個(gè)。凡是循環(huán)群必是可換群凡是循環(huán)群必是可換群。例：模例：模4剩余類全體關(guān)于加法運(yùn)算構(gòu)成循環(huán)群，生成剩余類全體關(guān)于加法運(yùn)算構(gòu)成循環(huán)群，生成元為元為1和和3。23411; 2111 ;31111 ; 01111132413333 ; 2333 ;33; 033333Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論20有限循環(huán)群和無限循環(huán)群有限循環(huán)

21、群和無限循環(huán)群 若元素若元素a的所有冪次均不相同的所有冪次均不相同(無限循環(huán)群無限循環(huán)群) 存在整數(shù)存在整數(shù) h和和k，使得，使得ak=ah，則有，則有a生成的循環(huán)群中生成的循環(huán)群中元素個(gè)數(shù)有限元素個(gè)數(shù)有限(有限循環(huán)群有限循環(huán)群)循環(huán)群元素的級(jí)循環(huán)群元素的級(jí) 若若ak=ah，則有，則有ah-k=e，定義使，定義使an=e的最小正整數(shù)為的最小正整數(shù)為有限循環(huán)群元素有限循環(huán)群元素a的的級(jí)級(jí)。 a0=e, a1, , an-1均不相同均不相同 an=e ，則，則a的一切冪次生成的元素都在的一切冪次生成的元素都在 G(a)=a0=e, a1, , an-1 中中 可換群可換群G中的每一個(gè)元素中的每一個(gè)

22、元素a都能生成一個(gè)循環(huán)群。都能生成一個(gè)循環(huán)群。若若a為有限級(jí)，則生成有限循環(huán)群，為有限級(jí)，則生成有限循環(huán)群， a的級(jí)即為循的級(jí)即為循環(huán)群中元素的個(gè)數(shù)環(huán)群中元素的個(gè)數(shù)(循環(huán)群的階循環(huán)群的階)Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論21若若a是是n級(jí)元素，則級(jí)元素，則am=e的充要條件是的充要條件是n|m若若a是是n級(jí)元素，級(jí)元素， b是是m級(jí)元素，且級(jí)元素，且(n,m)=1,則則 (ab)的級(jí)為的級(jí)為nm若若a是是n級(jí)元素，級(jí)元素， 則則ak的級(jí)為的級(jí)為n/(k,n)若若a是是dk級(jí)元素，級(jí)元素， 則則ak為為d級(jí)元素級(jí)元素n階循環(huán)群中，每個(gè)元

23、素的級(jí)是群階數(shù)階循環(huán)群中，每個(gè)元素的級(jí)是群階數(shù)n的因子的因子單位原根：?jiǎn)挝辉簄階循環(huán)群中，每一個(gè)階循環(huán)群中，每一個(gè)n級(jí)元素稱為級(jí)元素稱為n次單位原根次單位原根n階循環(huán)群中有階循環(huán)群中有 個(gè)單位原根個(gè)單位原根 歐拉函數(shù)：歐拉函數(shù)：0, 1, , n-1中與中與n互素的個(gè)數(shù)互素的個(gè)數(shù) 如如n=12=322，則，則 n n 111isiiinpp1212ssnp pp2 11 1122(21)3(3 1)4Lecture 11 Lecture 11 有限域有限域(I)(I)信道編碼理論信道編碼理論22域的乘法群必為某一個(gè)元素生成的循環(huán)群，即域的乘法群必為某一個(gè)元素生成的循環(huán)群，即q元域中必元域中必能找到一個(gè)能找到一個(gè) ，其階為，其階為q-1。即所有有限域元素都能表示成。即所有有限域元素都能表示成生成元的冪次的形式，此時(shí)的生成元稱為生成元的冪次的形式，此時(shí)的