第六章糾錯(cuò)編碼3近世代數(shù)簡(jiǎn)介

1、信道編碼理論信道編碼定理和方法 之 近世代數(shù)簡(jiǎn)介近世代數(shù)簡(jiǎn)介近世代數(shù)簡(jiǎn)介群、環(huán)、域群、環(huán)、域多項(xiàng)式剩余類環(huán)和域多項(xiàng)式域和循環(huán)群集合的運(yùn)算 如果在集合G中任意兩個(gè)元素按照一定的結(jié)合法則結(jié)合起來(lái)仍等于G中一個(gè)確定的元素，則這個(gè)結(jié)合法則稱為集合G的一個(gè)運(yùn)算。群 ( Group ) 定義 對(duì)于一個(gè)非空元素集合G以及定義在G上的某種運(yùn)算“ * ”，滿足以下3個(gè)條件，則稱G關(guān)于運(yùn)算“*”構(gòu)成一個(gè)群，記作（G，*） -1-11,( * )*( * ),*,*a bGa bcab ceaGa ee aaGaGaGa aeaa 結(jié)合性： 存在唯一的單位元 ： 中的每個(gè)元素各自存在唯一的逆元： 使群 ( Grou

2、p )-1-1-1-1/,*,*0;* ;*;,*1;* ;1*;a bGa bb aGea ee aa aeaaGea ee aa aeaa 交換群 阿爾貝群： 滿足交換律的群 加群：群（）中運(yùn)算是加法 加群的單位元為零元素， 加群的逆元： 乘群：群（）中運(yùn)算是乘法 乘群的單位元為壹元素， 乘群的逆元： 群 ( Group ) 加群一定是交換群，加群一定含零元素 乘群不一定是交換群，乘群一定不含零元素 無(wú)限群：包含無(wú)數(shù)個(gè)元素的群稱為無(wú)限群。 有限群：包含有限個(gè)元素的群稱為有限群。 群的階：有限群元素的個(gè)數(shù)稱為該群的階。子群 (Sub-Group)-1,*,*,*,*,*( ,*),*( ,*

3、)GGSSSGa bSa bSGSG 子群：如果在群（）中，集合 的非空子集 在同樣的運(yùn)算 下，可構(gòu)成群（）， 則成群（）為群（）的子群。 對(duì)于任何，必有 該充要條件強(qiáng)調(diào)了逆元的存在性和子群的封閉性。如果群是有限群，則其子群（）也是有限群；且子群的子群的充要條件： 子群的階數(shù)： 階數(shù)一定是群階數(shù)的因子Lagranges。（定理）子群 (Sub-Group),*.,*ABABC 若（A,*）和（B,*）分別是群（G,*）的兩個(gè)子群，則A，B的交集在同樣的運(yùn)算下也構(gòu)成群（G,*）的子群,記作。群（G,*）的任意多個(gè)子群的交集也是（G,*）的子群，記作例2-1 群與子群基本概念例2-1：令R、I、E

4、分別是有理數(shù)、整數(shù)、偶數(shù)集合， 則： (E,+) 是 (I,+)的子群；單位元均是0； (I,+)是(R,+)的子群；單位元均是0； 奇數(shù)集合O在加法運(yùn)算下構(gòu)不成群（不滿足封閉性）例2-2 單位元與逆元例2-2： 集合G = 0,1,2 m-1在模m加（用符號(hào)表示）運(yùn)算下構(gòu)成一個(gè)群（G，）。 則： 該加群是m階有限群； 單位元是e=0； 逆元：元素0的逆元是0； 元素1的逆元是m-1； 元素2的逆元是m-2；例2-3 有限乘群例2-3：集合G = 1,2 q-1在模q乘（q是素?cái)?shù)）運(yùn)算下構(gòu)成一個(gè)乘群（G，）。-11;,mod1(1)qebGabqbn qan則： 該乘群是階有限群； 該乘群是交

5、換群，單位元 每個(gè)元素都存在一個(gè)逆元 問(wèn)題：為什么q要是素?cái)?shù)？ 滿足 即 （ 為任意整數(shù)）例2-3 有限乘群的模結(jié)論：結(jié)論：有限乘群的模一定要是素?cái)?shù)，如果模有限乘群的模一定要是素?cái)?shù)，如果模為合數(shù)，其某個(gè)元素（因子）一定能整除它，為合數(shù)，其某個(gè)元素（因子）一定能整除它，不會(huì)產(chǎn)生一個(gè)余數(shù)不會(huì)產(chǎn)生一個(gè)余數(shù)1 1（單位元），由此將導(dǎo)致（單位元），由此將導(dǎo)致該元素的逆元不存在。該元素的逆元不存在。域 (Field) 定義 F是一個(gè)非空集合，在F中規(guī)定兩種運(yùn)算，一種叫做加法，他的運(yùn)算結(jié)果記為a+b,一種叫乘法，它的運(yùn)算結(jié)果記為a b，且滿足如下性質(zhì)：則該F對(duì)所規(guī)定的兩種運(yùn)算是一個(gè)域，記作（,+, ）。 a

6、,b,cF,(a+b) ca cb c 加法運(yùn)算構(gòu)成交換群； 所以非零元素在乘法運(yùn)算下構(gòu)成交換群。 元素服從乘法對(duì)加法分配律，即： 域 (Field)qGF 無(wú)限域：包含無(wú)限個(gè)域元素的域，如有理數(shù)、實(shí)數(shù)、 復(fù)數(shù)全體在乘加運(yùn)算下分別構(gòu)成的有理數(shù) 域、實(shí)數(shù)域和復(fù)數(shù)域都是無(wú)限域。伽邏華域GF（q)： 如果存在一個(gè)域，它只包含有限個(gè) 元，我們就稱它為有限域或伽羅華 域。如果這個(gè)域還有 個(gè)元素，則 域簡(jiǎn)記為（q）。域 (Field)eg:有限整數(shù)集合F=0,1,2,.,q-1(q是素?cái)?shù))在模q加、模q乘運(yùn)算下構(gòu)成一個(gè)q階有限域，成為Galois域，記作GF(q)。二元域GF(2)：q=2的伽邏華域稱為二

7、元域GF(2)近世代數(shù)簡(jiǎn)介群、環(huán)、域多項(xiàng)式剩余類環(huán)和域多項(xiàng)式剩余類環(huán)和域多項(xiàng)式域中和循環(huán)群多項(xiàng)式剩余類環(huán)和域111032.11011(2)( )nnnnia xaxa xaaxxxGFqqGF q，其中系數(shù) 代表了碼元的取值， 的冪次則表示了碼元的位置，系數(shù)屬于某數(shù)域的多項(xiàng)式，稱為該數(shù)域上的多項(xiàng)式。例如： 碼字多項(xiàng)式 二進(jìn)制系數(shù)的多項(xiàng)式成為二元域上的多項(xiàng)式。 進(jìn)制系數(shù)的多項(xiàng)式成為 多項(xiàng)式是碼字和代數(shù)之間元域上的多項(xiàng)式橋梁。的多項(xiàng)式環(huán)和理想子環(huán) 模運(yùn)算 多項(xiàng)式環(huán)：某數(shù)域上多項(xiàng)式的集合在乘、加運(yùn)算下可 以構(gòu)成一個(gè)多項(xiàng)式環(huán)，它是一個(gè)以多項(xiàng)式 為環(huán)元素的交換環(huán)。 無(wú)限環(huán)：多項(xiàng)式環(huán)的兩個(gè)要素是系數(shù)和冪次

8、，只要其 中一個(gè)有無(wú)限取值（比如系數(shù)所在的數(shù)域是 實(shí)數(shù)域、整數(shù)域等），則多項(xiàng)式環(huán)元素的數(shù) 目也是無(wú)限的，稱為無(wú)限環(huán)。無(wú)限環(huán)有限環(huán) 系數(shù)、冪次都有限（剩余類環(huán)）糾錯(cuò)碼多項(xiàng)式環(huán)和理想子環(huán)( )( )f xxq 多項(xiàng)式剩余類環(huán)： GF(q)上的多項(xiàng)式在模q加、模f(x)乘運(yùn)算下，多項(xiàng)式剩余類的全體所構(gòu)成的交換環(huán)稱為多項(xiàng)式剩余類環(huán)，記做R。 顯然剩余類環(huán)是靠GF(q)域保證系數(shù)有限，靠模f(x)乘保證冪次有限。且多項(xiàng)式運(yùn)算中包含了系數(shù)間模q乘、加的數(shù)域運(yùn)算。多項(xiàng)式環(huán)和理想子環(huán)-1-100-1mod0mod( )( )( )( )( )()( )-1-1( )( )mod00()nniiiiiiniii

9、qif xA xa xB xb xA xB xabxf xnnj kA xB xj kqkja bx 多項(xiàng)式加 對(duì)于環(huán)元素 和 多項(xiàng)式模乘 多項(xiàng)式環(huán)和理想子環(huán)( )12( )1210( ),( )deg ( ),deg ( )-1( )( )0,1, -1qf xnnqf xnnif xnf xnf xnR xnR xaxaxa xaaGF qin 特點(diǎn)：如果最高次冪是稱此是 次多項(xiàng)式，寫(xiě)做這里表示階次。顯然，多項(xiàng)式剩余類環(huán)中所有環(huán)元素的次數(shù)都不高于次，其通用表達(dá)式為： 其中： 多項(xiàng)式環(huán)和理想子環(huán)1110( )111( )( )nnnnqf xxaxa xanxf xR x 首一多項(xiàng)式：最高次

10、項(xiàng)的系數(shù)為 的多項(xiàng)式。 即 次最簡(jiǎn)首一多項(xiàng)式：僅包含最高次項(xiàng)和常數(shù)項(xiàng) ， 且形式為的多項(xiàng)式。 以為模的多項(xiàng)式剩余類的全體構(gòu)成一個(gè)有限元素的多項(xiàng)式剩余類環(huán)，可證明這個(gè)剩余類環(huán)中的每一理想子環(huán)都是主理想，且該主理想的生多項(xiàng)式以成( )( )g xf x必定能整除。例2-7 剩余類環(huán)3( )222243222-7( )2,( )1,( )1 ,( )1( )( )212(2)0,1( )( )2( )( )1 (1)1qf xiR xqf xxxA xxxB xxA xB xqGFaA xB xA xB xxxxxxxxx例： 剩余類環(huán)中 若 是兩個(gè)環(huán)元素，求是什么元素？（ ）該剩余類環(huán)至多由多少元

11、素組成？解：（）多項(xiàng)式系數(shù)取自域，即 將的系數(shù)做模 加（）431xxx 例2-7 剩余類環(huán)2mod( )22102102( )( )( )( )( )13( )3deg ( )3deg ( )-120,18f xiA xB xf xA xB xxxxf xf xf xa xa xaaaaa解：（ ）將的結(jié)果除以后取余式，即求模 （商為） （ ）是 次多項(xiàng)式， 環(huán)元素的冪次 環(huán)元素的通式：，而 由 、 、 三個(gè)系數(shù)組成的組合最多有 種8 該剩余類環(huán)最多有 個(gè)域元素組成。 近世代數(shù)簡(jiǎn)介群、環(huán)、域多項(xiàng)式剩余類環(huán)和域多項(xiàng)式域和循環(huán)群多項(xiàng)式域和循環(huán)群多項(xiàng)式域和循環(huán)群( )( ).qf xR xab 剩余

12、類環(huán)具有環(huán)的一切屬性，包括單位元的存在性。但環(huán)對(duì)于非零元素的逆元是否存在并沒(méi)有限定，這促使人們進(jìn)一步： 探討剩余類環(huán)的所有非零元素是否都存在逆元？ 在什么條件下可以構(gòu)成一個(gè)域，域元素之間有 什么關(guān)系?多項(xiàng)式基本術(shù)語(yǔ)( ),( )( )IIIP xCCP xP xnnn 既約多項(xiàng)式：對(duì)于某數(shù)域上的多項(xiàng)式若除了 常數(shù) 以及外，不能被該數(shù)域 上的任何其他多項(xiàng)式整除，則稱 為該數(shù)域上的既約多項(xiàng)式。 既約：已經(jīng)化簡(jiǎn)到不能再約的程度。完全分解： 次多項(xiàng)式可以有 個(gè)根，最多只能分解為 個(gè)一次多項(xiàng)式的乘積，稱為完全分解。多項(xiàng)式基本術(shù)語(yǔ)22( )( )( )( )1( )1( )()()( )(1)(1)III

13、P xP xP xf xxf xxf xxi xif xxx為既約多項(xiàng)式的： 不能再進(jìn)一步分解為兩個(gè)次數(shù)低于的多項(xiàng)式的乘積。顯然既，一次多項(xiàng)式是既約的。注意：，如實(shí)數(shù)域：不可以再分解既約 復(fù)數(shù)域：非既約 約所對(duì)應(yīng)的二元域：數(shù)域非充件約要條既多項(xiàng)式基本術(shù)語(yǔ)( )( )11nmGF qmP xxnq 本原多項(xiàng)式：對(duì)于有限域上的 次既約多項(xiàng)式 ，若能被它整除的最簡(jiǎn)首一多項(xiàng) 式（）的次數(shù)，則稱 該多項(xiàng)式為本原多項(xiàng)式。 ，而既約未必是本原 多項(xiàng)式循環(huán)群：由多項(xiàng)式 的各次冪所構(gòu)成的群稱為 多本原多項(xiàng)式項(xiàng)式循環(huán)群一;定多項(xiàng)式 是群是既約的元素之一 稱為循環(huán)群的生成元。例2-8本原多項(xiàng)式和既約多項(xiàng)式例例2-8

14、:(1) x4+x+1 (q=2, m=4, 2m-1=15) 不能被不能被 x5+1 , x6+1 x14+1 整除整除 能被能被 x15+1 整除整除 x4+x+1 是本原多項(xiàng)式是本原多項(xiàng)式 (2) x4+ x3+ x2+ x+1 能被能被 x5+1 整除整除 能被能被 x15+1 整除整除 x4+x3+x2+x+1是既約的，但不是本原的是既約的，但不是本原的例2-9循環(huán)群2345678923456234562-91.1117例： ， 構(gòu)成乘運(yùn)算下的無(wú)限循環(huán)群 若則產(chǎn)生以 ，為主值的周期性，則稱 ，為乘運(yùn)算下由7個(gè)元素組成的（7階）的有限循環(huán)群。多項(xiàng)式域存在定理22( )( )( )( )

15、( )( )(2)0,1,2,2,( )2.1(12 )ImImmIP xGF qmGF qmqP xqGF qGF qGF qGF qGFmqP xxxGF若是上的 次既約多項(xiàng)式，則 域上次數(shù)小于 的多項(xiàng)式的全體，在模 加、 模乘運(yùn)算下構(gòu)成一個(gè)階的有限域，稱為 域的擴(kuò)展域，寫(xiě)做）。稱為 擴(kuò)域）的基域。例：基域 擴(kuò)域 定理0,1, ,12(2)x xGF 個(gè)元素的組合 00,01,10,11多項(xiàng)式域存在定理22( )( )()( )(,2(.,2mmmP xGF qmGF qmP xGF qGF q mm01q 若是上的 次本原多項(xiàng)式，則域上次數(shù)小于 的非零多項(xiàng)式的全體(共q -1)個(gè)，在模乘

16、運(yùn)算下構(gòu)成一個(gè)多項(xiàng)式循環(huán)群。也就是說(shuō)，擴(kuò)域）里至少存在一個(gè)本原元（ 代表一個(gè)次數(shù)小于m的多項(xiàng)式），它的各次冪構(gòu)成了擴(kuò)域）全部非定理零域元素。多項(xiàng)式域存在定理( )( )( )( )IGF qf xP xP x 以上的多項(xiàng)式為模的乘運(yùn)算可生成 剩余類環(huán)； 以既約多項(xiàng)式為模的乘運(yùn)算可生成多項(xiàng)式域； 以本原多項(xiàng)式為模的乘運(yùn)算所生成非零域 元素可以構(gòu)成多項(xiàng)模多項(xiàng)式的限制條件越多，環(huán)元式素循環(huán)具備的性質(zhì)越多群。 。尋找循環(huán)群的生成元11( )( )( )1( ) (1),11( ) ( )( )( )012.( ) (3)0mmmnnmnqqGF qP xGF qP xxP xxnqxP x q xP

17、xPPq 上的本原多項(xiàng)式在擴(kuò)域） 上的根 一定是本原元。 是本原多項(xiàng)式，可以整除 其中 設(shè) 為本原多項(xiàng)式的根，即 將 代入上式得 即： 證明：定理1 尋找循環(huán)群的生成元122112( )( )(11111.312mmmqmqmGF qP xGF qqqmm0qq00 上的本原多項(xiàng)式在擴(kuò)域） 上的根 一定是本原元。：又， 由 可得: 可見(jiàn)： 的個(gè)冪次不但構(gòu)成了全部個(gè)非零擴(kuò)域元素，而且這些元素構(gòu)成循環(huán)群因此 是本原元定理得證明（證。）定理續(xù) 構(gòu)成循環(huán)群的步驟2,1mq0m由以上三個(gè)定理可知構(gòu)成循環(huán)群的步驟：找一個(gè)GF(q)上的m次本原多項(xiàng)式P(x)；取本原多項(xiàng)式的根 及其各次冪； 構(gòu)成循環(huán)群元素；

18、 實(shí)際上，循環(huán)群中任一元素的冪次都可以產(chǎn)生一個(gè)循環(huán)群，只不過(guò)只有本原元 才可以產(chǎn)生整個(gè)q個(gè)非零擴(kuò)域元素。而只能產(chǎn)生。非本原元循環(huán)子群判斷本原元和非本原元11( ,( ,1)(0,1,21(1)/( ,1)2.4mmmkqnkkqGCD kGCD kmkmmmmqGGF qkqqCDnqGCD k q其中 ）擴(kuò)域上非零元素 （） 的階一定是的因子，其值為： 循環(huán)群表示最大公約數(shù)（greatest common div中，n階元素的n次冪恒isor） 即： 定理：推等。論于1：1)111( ,1)mmqqmkGCD k q（是本原元，是整數(shù)，而）判斷本原元和非本原元1111(2 )kmmmmmnn

19、qnqnqqGF 非零元素的階 也就是該元素的循環(huán)周期， 或該元素的各次冪所能產(chǎn)生的域元素的個(gè)數(shù)。 如果元素的階，說(shuō)明它可以產(chǎn)生全 部非零元素，是本原元。 如果元素的階，則 一定是的因 子，必能整除，該域元素是非本原元。 二元擴(kuò)域的所有域元素均為奇次階。例2-10 二元擴(kuò)域和循環(huán)群的構(gòu)成444444152-10( )1(2)(2 )( )14,( )|1012121151xmP xxxGFGFP xxxmP xn 例 是上的本原多項(xiàng)式。試用本原元的各次冪生成二元擴(kuò)域的全部域元素，并計(jì)算各元素的階。解：令 為本原多項(xiàng)式的根，則 又 為本原元，其階為例2-10 二元擴(kuò)域和循環(huán)群的構(gòu)成0122214

20、44228421,2151(2)1,411 (2)mGF 解（續(xù)1）：（） 各次冪可以生成（ ） 的全部域元素，且這些域元素構(gòu)成一個(gè)乘運(yùn)算下 階的循環(huán)群。（見(jiàn)第 列）利用關(guān)系式可將 的各次冪化為低于 次 的多項(xiàng)式，比如 第 列例2-10 二元擴(kuò)域和循環(huán)群的構(gòu)成5234443(4)2.415/(15,5)15/5333mmGCD解（續(xù) ）：（ ）將 多項(xiàng)式的 個(gè)系數(shù)抽出后按順序排列，形成一個(gè) 重 結(jié)構(gòu)。推廣到一般，一個(gè)重 可以和一個(gè)包 含 碼元的碼字相關(guān)聯(lián)。與 各次冪對(duì)應(yīng)的重 結(jié)構(gòu) 見(jiàn)第 列。 元素的階可以用定理來(lái)計(jì)算，也可以通過(guò)求冪 運(yùn)算來(lái)驗(yàn)證。比如的階是 由于是 階的， 次乘運(yùn)算后應(yīng)歸一完成

21、一個(gè)循環(huán)。1577說(shuō) 明： 本原元不是唯一的，但并非所有的元素都是本原元。 凡15階的域元素都是本原元，共有8個(gè)；它們中任 意一個(gè)的各次冪都可以生成全部的域元素。 以為例，做完第次乘運(yùn)算后歸一，它能生成 全部15個(gè)域元素，的確是本原元。例2-10 二元擴(kuò)域和循環(huán)群的構(gòu)成域元素 / 根 / 最小多項(xiàng)式01211111012(),( )111()(2.12.4,11,11)5)1(mmmmmmmmqqqnkmqqmkqqn lkkGF qGF qxxnnqn lqxxxxx 擴(kuò)域上所有非零元素都是上多項(xiàng)式的根，即可以完全分解為一次項(xiàng)的乘積： 證明： 設(shè) 為 階元素，則；而定理可知必為的因子。令定理

22、完全分解性將代入可得 1(1)10lk nl 域元素 / 根 / 最小多項(xiàng)式()2.6()llmllqqkkiii li limGF qqqGF q 擴(kuò)域上元素和的 冪次等于元素 冪次的和,即： 式中，是擴(kuò)域定理冪和特性域元素。域元素 / 根 / 最小多項(xiàng)式00000( )( )( )1,2,( )( )( )02.7( )()0lllllllljppiiiiiiiqppqqqiiiiiipiqqqiiGF qpf xqf xllpf xf xfGF qfffffff 如果 是上 次多項(xiàng)式的根，那么 的 次冪也一定是的根。（）證明：令 定理共軛 根系 域元素 / 根 / 最小多項(xiàng)式123111

23、2.5()110,1mmmmmqqqqqqqGF qxx 費(fèi)爾馬定理共軛元和共軛根 根據(jù)定理，上任意域元素 一定是的根，即整理后可得。 由定理2.6可知，都是多項(xiàng)式的根，稱為共軛元，這些共軛元有共同的基底，構(gòu)成一系個(gè)共軛根系。域元素 / 根 / 最小多項(xiàng)式11,()( )mmmqqqqmGF qmmGF q 受費(fèi)爾馬定理的約束，又循環(huán)回 ，可見(jiàn)在擴(kuò)域中，共軛根系最多包含個(gè)共軛元，以共軛根系為根的多項(xiàng)式的最高次數(shù)不會(huì)超過(guò) 。 一個(gè)多項(xiàng)式的根可以來(lái)自多個(gè)根系，如果一個(gè)首一多項(xiàng)式的所有根來(lái)自同一個(gè) 根系，稱這樣的多項(xiàng)式為 的最小多項(xiàng)式，最小多項(xiàng)式在一定是既約的。域元素 / 根 / 最小多項(xiàng)式1211

24、21( )11( )( )( )8)2.(mmqkkkiGF qxxxxxxm 定理最小多項(xiàng)式 上的多項(xiàng)式一定可以分解成若干最小多項(xiàng)式之積，即： 由費(fèi)爾馬定理可知各最小多項(xiàng)式的次數(shù)不會(huì)超因分。式過(guò)解次域元素 / 根 / 最小多項(xiàng)式1)0122222( )deg( ),( )()()()()deg( )liiiiiiiiilxlxlxxxxxxlmm（ 共軛元與最小多項(xiàng)式的關(guān)次最小多項(xiàng)式必然有同一根系的 個(gè)共軛元作為其根。也就是說(shuō)，若必有： 這里，本原元的共軛根系對(duì)應(yīng)的最小多項(xiàng)式的次數(shù)等于系。域元素 / 根 / 最小多項(xiàng)式10121212.52.82.91()()()( )( )( )( )mmqqkkiixxxxxxxx 共軛元與最小多項(xiàng) 綜合定理、定理和定理可得： 式的關(guān)系例2-11 共軛元與最小多項(xiàng)式41151(2 )2,4,11)mqxGFqmxx 44例2-11 找出由本原多項(xiàng)式P(x)=x生成的二元擴(kuò)域上各非零元素的共軛元，并計(jì)算與這些共軛元對(duì)應(yīng)的最小多項(xiàng)式。解： 由于是二元域，可以直接用+替換- GF(2 上非零元素的循環(huán)群已經(jīng)在例2-10中給出，現(xiàn)在要依次尋找各元素的共軛元和對(duì)應(yīng)的最小多項(xiàng)式。例2-11 共軛元與最小多項(xiàng)式234200001122242821615 1248