糾錯編碼代數(shù)基礎(chǔ)

1、第第7章章 糾錯編碼代數(shù)糾錯編碼代數(shù) 基礎(chǔ)基礎(chǔ) 糾錯編碼代數(shù)基礎(chǔ) 第第7章章 糾錯編碼代數(shù)基礎(chǔ)糾錯編碼代數(shù)基礎(chǔ) 糾錯編碼代數(shù)基礎(chǔ) 7.1 7.1 群群 7.1.1 群的定義群的定義 1. 整數(shù)的相關(guān)概念整數(shù)的相關(guān)概念 定理定理7.1 設(shè)a為整數(shù)，d為正整數(shù)，且a d，則存在唯一的整 數(shù)q 、r滿足a = qd + r ，0 r d 。d稱作模模，r稱作余數(shù)余數(shù)，r 可記作a mod d 。 由于0 r p (x)，一定存在唯一的多項式q (x)和r (x)，使 f (x) = q (x) p (x) + r (x) 0 r (x) p (x) p (x)稱作模多項式，r (x)稱作余式， r

2、(x)記為f (x) mod p (x) 。 定理定理7.7 任何首一多項式可分解為首一即約多項 式之積： n r n rr xpxpxpxf)()()()( 21 21 定理定理7.8 一定存在多項式m (x)、n (x)，使 m (x) a (x) + n (x) b (x) = (a (x), b (x) (a (x), b (x)為多項式a (x)、b (x)的最大公因式 糾錯編碼代數(shù)基礎(chǔ) 2. 環(huán)的定義環(huán)的定義 環(huán)是一些元素構(gòu)成的集合，該集合中定義加法和乘法兩 種運算，滿足： l (1) 對加法是一個交換群； l (2) 對乘法具有封閉性和結(jié)合律； l (3) 滿足分配律 ：對任何a

3、 , b , c F ，有： a ( b + c ) = ab + ac ( a + b ) c = ac + bc 3. 子環(huán)子環(huán) 設(shè)F是一個環(huán)，S是F的一個非空子集，若S對加法和乘 法也構(gòu)成一個環(huán)，則稱S是F的一個子環(huán)，F(xiàn)是S的一個 擴環(huán)。 糾錯編碼代數(shù)基礎(chǔ) 理想理想 理想是一類特殊的子 環(huán)。設(shè)F是一個可換環(huán)，I是F 的一個非空子集，如果對任意 a , b I，恒有a - b I，及對 任意a I和任意 x F，恒有 ax = xa I，則稱I是F的一個 理想。 定理定理7.9 若S是環(huán)F的一個非空子集，則S是F的子環(huán)的充 要條件是： 對任何a , b S，有a - b S和ab S 。

4、主理想主理想 在可換環(huán)F中， 由一個元素a F的所 有倍數(shù)及其線性組合而 生成的理想I a = xa + na x F , n Z 稱 為環(huán)F的一個主理想， 元素a為該主理想的生 成元。 糾錯編碼代數(shù)基礎(chǔ) 4. 環(huán)的同構(gòu)環(huán)的同構(gòu) 設(shè)A和B是兩個環(huán)，若存在一個A到B的一一對應(yīng)關(guān)系f， 并且滿足： 對任何a , b A，有 f (a + b) = f (a) + f (b) f (a b) = f (a) f (b) 則稱f是環(huán)A到環(huán)B的一個同構(gòu)同構(gòu)。 糾錯編碼代數(shù)基礎(chǔ) 7.2.2 整數(shù)剩余類環(huán)整數(shù)剩余類環(huán) 模d的余數(shù)全體F = 0 , 1 , , d - 1對模d加法運算構(gòu)成加 法交換群；對模d

5、乘法運算滿足封閉性、結(jié)合律和交換律； 還滿足分配律，因此模d的余數(shù)全體構(gòu)成交換環(huán)，稱作整整 數(shù)剩余類環(huán)數(shù)剩余類環(huán)。 + 0 1 d 2d - 1 0 0 1 d 2d - 1 1 1 2 d - 10 d - 2d - 2d - 1 d - 4d - 3 d - 1 d - 1 0 d - 3d - 2 表7-6 0 , 1 , , d - 1的模d加法表 糾錯編碼代數(shù)基礎(chǔ) 7.2.3 多項式剩余類環(huán)多項式剩余類環(huán) 以p(x)為模的多項式的余式全體對模p (x)的加法運算構(gòu)成 加法交換群；模p (x)的余式全體對模p (x)乘法滿足封閉性、 結(jié)合律和交換律；其分配律為 a (x) + b (x

6、) c (x) mod p (x) = a (x) c (x) + b (x) c (x) mod p (x) a (x) b (x) + c (x) mod p (x) = a (x) b (x) + a (x) c (x) mod p (x) 因此模p (x)的余式全體對模p (x)的運算構(gòu)成交換環(huán)，稱作 多項式剩余類環(huán)多項式剩余類環(huán)。 糾錯編碼代數(shù)基礎(chǔ) 7.3 7.3 域域 7.3.1 域的定義域的定義 域是一些元素構(gòu)成的集合，該集合中定義加法和乘法兩種運 算，滿足： l(1) 對加法構(gòu)成交換加群。 l(2) 非零元素全體對乘法構(gòu)成交換乘群。 l(3) 加法和乘法間具有分配律 a (b

7、+ c) = ab + ac (a + b) c = ac + bc 域的階域的階 域中元素 的個數(shù)。如整數(shù)域和 復(fù)數(shù)域、實數(shù)域的階 都是無窮值。 有限域有限域 元素個數(shù)有限的 域，用GF(q)表示q階有限域。 如上例可表示為GF(8) = 0 , 1 , a , a2 , a3 , a4 , a5 , a6 糾錯編碼代數(shù)基礎(chǔ) 7.3.2 有限域有限域 定理定理7.10 設(shè)d為素數(shù)，則以d為模的整數(shù)剩余類環(huán)構(gòu) 成d階有限域GF(d)。 定理定理7.11 設(shè)p(x)為系數(shù)取自GF(q)上的n次 即約多項式，則以p(x)為模的多項式剩余 類環(huán)構(gòu)成qn階有限域GF(qn)。 定理定理7.12 有限域

8、的階必為其子域階之冪，即Q = qn。 糾錯編碼代數(shù)基礎(chǔ) 7.3.3 有限域的本原元有限域的本原元 定理定理7.13 元素個數(shù)相等的有限域必同構(gòu)。 本原元本原元 在GF(q)中，某一元素 的階為q - 1， 即 q-1 = e (q 1 是使等式成立的最小正整數(shù))，則 稱 為本原元。 本原元多項式本原元多項式 是以本原元為根的即約多項式。 糾錯編碼代數(shù)基礎(chǔ) 7.3.4 有限域的結(jié)構(gòu)有限域的結(jié)構(gòu) 定理定理7.14 GF(q)的所有 元素都是方程xq x = 0 的根，反之，方程xq x = 0的根必在GF(q) 中。 l有限域的特征有限域的特征 是 有限域中乘法單位 元e關(guān)于加法的級， 也就是使

9、p e = 0的 最小正整數(shù)p。 定理定理7.15 有限域的特征必為素數(shù)。 l素域素域 是GF(q)的最小子域，表示為GF(p) = 0 , e , 2e , , (p - 1)e。 糾錯編碼代數(shù)基礎(chǔ) 定理定理7.16 有限域的階必為其特征之冪，即q = pm。 定理定理7.17 在以p為特征的域GF( q )中，對于任 意、 GF( q )，恒有 ( + ) p = p + p 推論推論1 若1 , 2 , k是以p為特征的域中的元 素，則對任意正整數(shù)n恒有 糾錯編碼代數(shù)基礎(chǔ) 7.3.5 有限域的共軛根組有限域的共軛根組 定理定理7.18 對GF(pm )中的任意元素 ，恒有。 定理定理7.

10、19 設(shè)f ( x)是系數(shù)取自GF( p )的k次即約多項 式， GF( pm )，若 是f ( x)的根，則(0 r k ) 也是f ( x)的根。 l最小多項式最小多項式 系數(shù)取自GF(p )，且以 GF( pm )為根的所有首一多項式中，必有一個 次數(shù)最低的多項式，稱作 的最小多項式。 糾錯編碼代數(shù)基礎(chǔ) 最小多項式的性質(zhì)： l(1) 最小多項式在GF( p )上是即約的 l(2) 每一 GF( pm )，必有唯一的最小多項式。 l(3) 的最小多項式能整除任何以 為根的多項式。 推論推論2 設(shè)m1 (x) , m2 (x) , , mt (x)為GF( pm )中各元 素的最小多項式，那

11、么可將多項式在GF( p )上分 解為 糾錯編碼代數(shù)基礎(chǔ) 7.3.6 有限域的綜合舉例有限域的綜合舉例 【例例7.25】 在GF(2 ) = 0 , 1系數(shù)域上，以p (x) = x4 + x + 1 為模構(gòu)成有限域GF(24 )，在GF(2 )上分解多項式x16 x 。 解：(1) 由于GF(2 ) = 0 , 1，e = 1，1 + 1 = 0，所以特征p = 2。 (2) 尋找本原元 設(shè)為p (x)的根，則 4 = + 1 15 = 4443 = ( + 1) ( + 1) ( + 1) 3 = (2 + 1) ( + 1 + 3 ) = 2 + 5 + + 1 = 2 + (2 + )

12、 + + 1 = 1 15 = 1，因此 為本原元，p (x)為本原多項式，GF(24 )的15個 非0元素都可以如表7-13所示表示成 的方冪：0 , 1 , , 14 糾錯編碼代數(shù)基礎(chǔ) 剩余類線性組合冪級數(shù)矢量 0000000 1110001 x 0010 x2 2 20100 x3 3 31000 x + 1 + 1 40011 x2 + x 2 + 50110 x3 + x2 3 + 2 61100 表7-13 GF(24)中元素的四種表示 糾錯編碼代數(shù)基礎(chǔ) 剩余類線性組合冪級數(shù)矢量 x3 + x +1 3 + + 1 71011 x2 + 1 2 + 1 80101 x3 + x 3

13、 + 91010 x2 + x + 1 2 + + 1 100111 x3 + x2 + x 3 + 2 + 111110 x3+x2+x+1 3+ 2+ +1 121111 x3 + x2 + 1 3 + 2 + 1 131101 x3 + 1 3 + 1 141001 表7-13 GF(24)中元素的四種表示 糾錯編碼代數(shù)基礎(chǔ) (3) 按照定理7.19，找出各個共軛根系，并構(gòu)成相應(yīng)的最小多項 式。 0 m ( x) = x 0 = x 0 m0 ( x) = x 0 = x + 1 , 2 , 4 , 8 m1 ( x) = (x ) (x - 2) (x - 4) (x - 8) 3 ,

14、 6 , 12 , 9 m3 ( x) = (x 3) (x - 6) (x - 12) (x - 9) 5 , 10 m5 ( x) = (x 5) (x - 10) 7 , 14 , 13 , 11 m7 ( x) = (x 7) (x - 14) (x - 13) (x - 11) 以上最小多項式的下標(biāo)是以共軛根系中的最低冪次表示的 糾錯編碼代數(shù)基礎(chǔ) (4) 利用本原多項式4 = + 1，將最小多項式化簡。 m1 ( x) = (x ) (x - 2) (x - 4) (x - 8) = x4 + x + 1 同理得 m3 ( x) = x4 + x3 + x2 + x + 1 m5 (

15、 x) = x2 + x + 1 m7 ( x) = x4 + x3 + 1 (5) 將x16 x因式分解 x16 x = m ( x) m0 ( x) m1 ( x) m3 ( x) m5 ( x) m7 ( x) = x (x + 1) (x4 + x + 1) ( x4 + x3 + x2 + x + 1) ( x2 + x + 1) ( x4 + x3 + 1) 糾錯編碼代數(shù)基礎(chǔ) (6) 根據(jù)15 = 1以及元素階的定義及性質(zhì)，可得元素1的 階為1； , 2 , 4 , 8 ,7 , 14 , 13 , 11的階為15；3 , 6 , 12 , 9的階為5；5 , 10的階為3。 因為

16、階為q - 1的元素為本原元，所以除為本原元外， 2 , 4 , 8 , 7 , 14 , 13 , 11也都是本原元，其相應(yīng)的兩 個最小多項式x4 + x + 1 , x4 + x3 + 1即為本原多項式。 本本 章章 小小 結(jié)結(jié) 本章是后續(xù)糾錯編碼理論的代數(shù)基礎(chǔ)，介紹的主要內(nèi)容有： (1)(1)任何整數(shù)可表示為a = qd + r的形式，任何多項式可表示為f (x) = q (x) p (x) + r (x) 的形式，d、p (x)為模，r、r (x) 為余數(shù)(式)。首一 多項式的最高次數(shù)的系數(shù)為1，每一個首一多項式必可分解為首一 即約多項式之積。 (2) 群是一些元素在某種運算下構(gòu)成的集合，滿足封閉性、結(jié)合律 、存在單位元和逆元。 群G的非空子集G對于G中所定義的代數(shù)運算也構(gòu)成群，則稱 G為G的子群。 兩個群在各自的運算下若存在一一對應(yīng)關(guān)系，則這兩個群同構(gòu)。 循環(huán)群是由一個元素的所有冪次（倍次）構(gòu)成。 群可由其非空子群完備地分解為若干互不相交的陪集。 (4)域中元素對加法是交換群，非零元素對乘法是交換群，滿足分 配律。 有限域中元素的個數(shù)是有限的或可數(shù)的。以素數(shù)d為模的整數(shù)剩 余類環(huán)構(gòu)成d階有限域GF(d)，以n階即約多項式p (x)為模的多項式剩 余類環(huán)構(gòu)成qn階有限域GF(qn)。 有限域GF(q