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

糾錯(cuò)編碼代數(shù)基礎(chǔ)第1頁，共36頁，2023年，2月20日，星期四1第七章糾錯(cuò)編碼代數(shù)基礎(chǔ)

內(nèi)容提要：抽象代數(shù)又稱近世代數(shù)，其研究對(duì)象是定義在某些運(yùn)算下的集合，運(yùn)算對(duì)象可以是數(shù)、多項(xiàng)式、矢量、矩陣、線性空間等。編碼理論是建立在碼的代數(shù)結(jié)構(gòu)基礎(chǔ)上的，為便于初學(xué)者理解，本章簡(jiǎn)單介紹抽象代數(shù)中與編碼直接相關(guān)的基礎(chǔ)知識(shí)，主要涉及整數(shù)及多項(xiàng)式的一些基本概念及群、環(huán)、域的基本知識(shí)。第2頁，共36頁，2023年，2月20日，星期四2本章重點(diǎn)：1.多項(xiàng)式的因式分解及有限域的本原元的基本概念；2.有限域共軛根組的求解。

第3頁，共36頁，2023年，2月20日，星期四37.1群7.1.1群的定義1.整數(shù)的相關(guān)概念定理7.1

設(shè)a為整數(shù)，d為正整數(shù)，且a

d，則存在唯一的整數(shù)q、r滿足a=qd+r，0

r<d。d稱作模，r稱作余數(shù)，r可記作a[modd]。由于0

r<d，模d的全體余數(shù)為{0,1,…,d–1}。余數(shù)間可定義模d加法和模d乘法運(yùn)算，設(shè)D={0,1,…,d–1}，如果a,b

D，有(a+b)[modd]

D及(a

b)[modd]

D說明模d的余數(shù)全體對(duì)模d加法和模d乘法滿足封閉性。

第4頁，共36頁，2023年，2月20日，星期四4定理7.2

任何正整數(shù)a均可表示成其素因數(shù)的冪之積：

p1,p2,…,pn：a的互不相同的素因數(shù)，ri：正整數(shù)。定理7.3

設(shè)a、b是不全為0的整數(shù)，則存在整數(shù)p、q使

pa+qb=(a,b)

(a,b)為a、b的最大公約數(shù)，當(dāng)a、b互素時(shí)，(a,b)=1，pa+qb=1。第5頁，共36頁，2023年，2月20日，星期四52.群的定義群G是一些元素構(gòu)成的集合，該集合中定義一種運(yùn)算*（加法或乘法），滿足：

封閉性，對(duì)任何a,b

G，有a

b

G

(2)結(jié)合律，對(duì)任何a,b,c

G，(a

b)

c=a(b

c)(3)存在單位元eG，使對(duì)任何a

G有a

e=e

a=a

(4)對(duì)任何a

G有逆元a-1

G，使a

a-1

=a-1

a=e

第6頁，共36頁，2023年，2月20日，星期四6l交換群

如果*運(yùn)算還滿足交換律，即對(duì)任何a,b

G，有a

b=b

a，則G稱作交換群。加法群是交換群，而乘法群不一定是交換群，如矩陣乘法不滿足交換律。

l群的階群的階就是群中所含元素的個(gè)數(shù)。如整數(shù)加法群和非0實(shí)數(shù)乘法群的階都是無窮值。l有限群階為有限值的群稱作有限群。第7頁，共36頁，2023年，2月20日，星期四73.群的同構(gòu)

設(shè)在.運(yùn)算下的集合G與在

運(yùn)算下的集合H是兩個(gè)群，若存在一個(gè)G到H的一一對(duì)應(yīng)關(guān)系f，且對(duì)任何a,b

G，有f(ab)=f(a)

f(b)，則稱f是G到H的同構(gòu)。

通常把條件f(a.b)=f(a)

f(b)稱為f保持群的運(yùn)算關(guān)系。一個(gè)同構(gòu)映射f不僅保持運(yùn)算關(guān)系，而且使兩個(gè)群的所有代數(shù)性質(zhì)都一一對(duì)應(yīng)。同構(gòu)的系統(tǒng)本質(zhì)上完全相同，研究其中一個(gè)也就代替了對(duì)另一個(gè)的研究。第8頁，共36頁，2023年，2月20日，星期四87.1.2子群1.子群的定義

若群G的非空子集G′對(duì)于G中所定義的代數(shù)運(yùn)算也構(gòu)成群，則稱G′為G的子群。定理7.4

有限群的子群的階一定整除群的階。

2.循環(huán)群

由一個(gè)單獨(dú)元素

的一切冪次所構(gòu)成的群{0=e,,2,…,n-1n=e}稱為循環(huán)群。該元素

稱為循環(huán)群的生成元。使n=e的最小正整數(shù)n稱為元素的階。定理7.5

交換群G中的每一個(gè)元素

都能生成一個(gè)循環(huán)群，它是G的子群，元素

的階就是循環(huán)群的階。

第9頁，共36頁，2023年，2月20日，星期四9

(3)若a為n階元素，則元素ak（或ka）的階為元素階的性質(zhì)：(1)

若a是n階元素，則am=e（對(duì)于加法為ma=e）的充要條件是n整除m。(2)若某一群中，a為n階元素，b為m階元素，且(n,m)=1，則元素a

b（或a+b）的階為n

m。第10頁，共36頁，2023年，2月20日，星期四107.1.3群的陪集分解1.群的陪集

設(shè)G′為群G的非空子群，取h

G，則稱hG′為G′的左陪集，稱G′

h為G′的右陪集。當(dāng)G是交換群時(shí)，子群G′的左、右陪集是相等的，元素h稱作陪集首。

2.群的陪集分解

設(shè)G′={g1,g2,…,gn}，G′的階為n，又設(shè)G′為群G的非空子群，G的階為nm，那么可將G完備地分成m個(gè)陪集（子群本身也是一個(gè)陪集），

第11頁，共36頁，2023年，2月20日，星期四11陪集說明h1g1=g1=eg2…gn-1gn

陪集首h1=e，子群G′h2g1

h2g2…h(huán)2gn-1h2gn

陪集首h2，陪集h2G′……h(huán)m-1g1

hm-1g2…h(huán)m-1gn-1hm-1gn

陪集首hm-1，陪集hm-G′hmg1

hmg2…h(huán)mgn-1hmgn

陪集首hm，陪集hmG′表7-4陪集分解表第12頁，共36頁，2023年，2月20日，星期四12陪集首的選擇應(yīng)注意：(4)陪集h

G′中的每一個(gè)元素都可作為其陪集首h，陪集元素不變，僅排列順序改變。

(3)若陪集首hj不是陪集hi

G′中的元素，則兩陪集hi

G′與hj

G′相交為空集。(2)若陪集首h不是子群G′中的元素，則陪集h

G′與子群G′相交為空集。(1)若陪集首h是子群G′中的元素，則陪集h

G′

與子群G′相同。第13頁，共36頁，2023年，2月20日，星期四137.2環(huán)7.2.1環(huán)的定義

1.多項(xiàng)式的相關(guān)概念

多項(xiàng)式的性質(zhì)在很多方面類似于整數(shù)的性質(zhì)。系數(shù)取自集合F的多項(xiàng)式的表示形式為f(x)=fnxn+fn-1

xn-1+…+f1

x+f0

fi

F

l

首一多項(xiàng)式

多項(xiàng)式的最高次數(shù)的系數(shù)為1，即fn

=1。

l多項(xiàng)式的階

多項(xiàng)式中系數(shù)不為0的x的最高次數(shù),記為f(x)。l

即約多項(xiàng)式

階大于0且在給定集合F上除了常數(shù)和常數(shù)與本身的乘積外，不能被其它多項(xiàng)式除盡的多項(xiàng)式第14頁，共36頁，2023年，2月20日，星期四14定理7.6

給定任意兩個(gè)多項(xiàng)式f(x)、p(x)，f(x)>p(x)，一定存在唯一的多項(xiàng)式q(x)和r(x)，使f(x)=q(x)p(x)+r(x)

0

r(x)<p(x)

p(x)稱作模多項(xiàng)式，r(x)稱作余式，r(x)記為f(x)[modp(x)]。定理7.7

任何首一多項(xiàng)式可分解為首一即約多項(xiàng)式之積：

定理7.8

一定存在多項(xiàng)式m(x)、n(x)，使

m(x)

a(x)+n(x)b(x)=(a(x),b(x))

(a(x),b(x))為多項(xiàng)式a(x)、b(x)的最大公因式第15頁，共36頁，2023年，2月20日，星期四152.環(huán)的定義

環(huán)是一些元素構(gòu)成的集合，該集合中定義加法和乘法兩種運(yùn)算，滿足：

l

(1)對(duì)加法是一個(gè)交換群；

l

(2)對(duì)乘法具有封閉性和結(jié)合律；

l

(3)滿足分配律：對(duì)任何a,b,c

F，有：

a(

b+c)

=ab+

ac

(

a+b)c=ac+

bc

3.子環(huán)

設(shè)F是一個(gè)環(huán)，S是F的一個(gè)非空子集，若S對(duì)加法和乘法也構(gòu)成一個(gè)環(huán)，則稱S是F的一個(gè)子環(huán)，F(xiàn)是S的一個(gè)擴(kuò)環(huán)。第16頁，共36頁，2023年，2月20日，星期四16

理想理想是一類特殊的子環(huán)。設(shè)F是一個(gè)可換環(huán)，I是F的一個(gè)非空子集，如果對(duì)任意a,b

I，恒有a-b

I，及對(duì)任意a

I和任意

x

F，恒有ax=xa

I，則稱I是F的一個(gè)理想。定理7.9

若S是環(huán)F的一個(gè)非空子集，則S是F的子環(huán)的充要條件是：對(duì)任何a,b

S，有a-b

S和ab

S。

主理想

在可換環(huán)F中，由一個(gè)元素a

F的所有倍數(shù)及其線性組合而生成的理想I[a]={xa+na

xF,n

Z}稱為環(huán)F的一個(gè)主理想，元素a為該主理想的生成元。第17頁，共36頁，2023年，2月20日，星期四174.環(huán)的同構(gòu)

設(shè)A和B是兩個(gè)環(huán)，若存在一個(gè)A到B的一一對(duì)應(yīng)關(guān)系f，并且滿足：對(duì)任何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è)同構(gòu)。第18頁，共36頁，2023年，2月20日，星期四187.2.2整數(shù)剩余類環(huán)

模d的余數(shù)全體F={0,1,…,d-1}對(duì)模d加法運(yùn)算構(gòu)成加法交換群；對(duì)模d乘法運(yùn)算滿足封閉性、結(jié)合律和交換律；還滿足分配律，因此模d的余數(shù)全體構(gòu)成交換環(huán)，稱作整數(shù)剩余類環(huán)。+01…d–2d-1001…d–2d-1112…d-10………………d-2d-2d-1…d-4d-3d-1d-10…d-3d-2表7-6{0,1,…,d-1}的模d加法表第19頁，共36頁，2023年，2月20日，星期四197.2.3多項(xiàng)式剩余類環(huán)

以p(x)為模的多項(xiàng)式的余式全體對(duì)模p(x)的加法運(yùn)算構(gòu)成加法交換群；模p(x)的余式全體對(duì)模p(x)乘法滿足封閉性、結(jié)合律和交換律；其分配律為[a(x)

+b(x)]c(x)[modp(x)

]=[a(x)c(x)

+b(x)c(x)][modp(x)

]a(x)

[b(x)

+c(x)][modp(x)

]=[a(x)b(x)

+a(x)c(x)][modp(x)

]因此模p(x)的余式全體對(duì)模p(x)的運(yùn)算構(gòu)成交換環(huán)，稱作多項(xiàng)式剩余類環(huán)。第20頁，共36頁，2023年，2月20日，星期四207.3域7.3.1域的定義域是一些元素構(gòu)成的集合，該集合中定義加法和乘法兩種運(yùn)算，滿足：l(1)對(duì)加法構(gòu)成交換加群。l(2)非零元素全體對(duì)乘法構(gòu)成交換乘群。l(3)加法和乘法間具有分配律a(b+c)=ab+ac

(a+b)c=ac+bc

域的階域中元素的個(gè)數(shù)。如復(fù)數(shù)域和實(shí)數(shù)域的階都是無窮值。

有限域元素個(gè)數(shù)有限的域，用GF(q)表示q階有限域。如GF(5)={0,1,2,

3,

4}第21頁，共36頁，2023年，2月20日，星期四217.3.2有限域定理7.10設(shè)d為素?cái)?shù)，則以d為模的整數(shù)剩余類環(huán)構(gòu)成d階有限域GF(d)。定理7.11

設(shè)p(x)為系數(shù)取自GF(q)上的n次即約多項(xiàng)式，則以p(x)為模的多項(xiàng)式剩余類環(huán)構(gòu)成qn階有限域GF(qn)。定理7.12

有限域的階必為其子域階之冪，即Q=qn。第22頁，共36頁，2023年，2月20日，星期四227.3.3有限域的本原元

定理7.13

元素個(gè)數(shù)相等的有限域必同構(gòu)。

本原元在GF(q)中，某一元素

的階為q-1，即

q-1=e(q–1是使等式成立的最小正整數(shù))，則稱

為本原元。

本原多項(xiàng)式是以本原元為根的即約多項(xiàng)式。第23頁，共36頁，2023年，2月20日，星期四237.3.4有限域的結(jié)構(gòu)定理7.14

GF(q)的所有元素都是方程xq–x=0的根，反之，方程xq–x=0的根必在GF(q)中。有限域的特征

是有限域中乘法單位元e關(guān)于加法的級(jí)，也就是使p

e=0的最小正整數(shù)p。定理7.15有限域的特征必為素?cái)?shù)。素域是GF(q)的最小子域，表示為GF(p)={0,e,2e,…,(p-1)e}。第24頁，共36頁，2023年，2月20日，星期四24定理7.16有限域的階必為其特征之冪，即q=pm。定理7.17在以p為特征的域GF(q)中，對(duì)于任意、

GF(q)，恒有(+

)p=

p+

p

推論1

若1,2,…,

k是以p為特征的域中的元素，則對(duì)任意正整數(shù)n恒有第25頁，共36頁，2023年，2月20日，星期四257.3.5有限域的共軛根組定理7.18

對(duì)GF(pm)中的任意元素

，恒有。定理7.19設(shè)f(x)是系數(shù)取自GF(p)的k次即約多項(xiàng)式，

GF(pm)，若

是f(x)的根，則(0

r<k)也是f(x)的根。

l最小多項(xiàng)式系數(shù)取自GF(p)，且以

GF(pm)為根的所有首一多項(xiàng)式中，必有一個(gè)次數(shù)最低的多項(xiàng)式，稱作

的最小多項(xiàng)式。

第26頁，共36頁，2023年，2月20日，星期四26最小多項(xiàng)式的性質(zhì)：l(1)最小多項(xiàng)式在GF(p)上是即約的;l(2)每一

GF(pm)，必有唯一的最小多項(xiàng)式;l(3)

的最小多項(xiàng)式能整除任何以

為根的多項(xiàng)式。

推論2設(shè)m1(x),m2(x),…,mt(x)為GF(pm)中各元素的最小多項(xiàng)式，那么可將多項(xiàng)式在GF(p)上分解為第27頁，共36頁，2023年，2月20日，星期四277.3.6有限域的綜合舉例【例7.25】在GF(2)={0,1}系數(shù)域上，以p(x)=x4+x+1為模構(gòu)成有限域GF(24)，在GF(2)上分解多項(xiàng)式x16–x。解：(1)由于GF(2)={0,1}，e=1，1+1=0，所以特征p=2。(2)尋找本原元設(shè)為p(x)的根，則4=

+115=4443

=(+1)(

+1)(+1)3=(2+1)(+1+3)=

2+

5++1=

2+(2+)++1=115=1，因此為本原元，p(x)為本原多項(xiàng)式，GF(24)的15個(gè)非0元素都可以如表7-13所示表示成的方冪：0,

1,…,14第28頁，共36頁，2023年，2月20日，星期四28剩余類線性組合冪級(jí)數(shù)矢量00000001110001x0010x2220100x3331000x

+

1+140011x2+x2+50110x3+x23+261100表7-13GF(24)中元素的四種表示第29頁，共36頁，2023年，2月20日，星期四29剩余類線性組合冪級(jí)數(shù)矢量x3+x+13++171011x2+12+180101x3+x3+91010x2+x+12++1100111x3+x2+x

3+2+111110x3+x2+x+13+2++1121111x3+x2+13+2+1131101x3+13+1141001表7-13GF(24)中元素的四種表示第30頁，共36頁，2023年，2月20日，星期四30(3)按照定理7.19，找出各個(gè)共軛根系，并構(gòu)成相應(yīng)的最小多項(xià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,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)以上最小多項(xiàng)式的下標(biāo)是以共軛根系中的最低冪次表示的第31頁，共36頁，2023年，2月20日，星期四31(4)利用本原多項(xiàng)式4=+1，將最小多項(xiàng)式化簡(jiǎn)。m1(x)=(x–

)(x-2)(x-4)(x-8)=x4+x+1同理得m3(x)=x4+x3

+x2+x+1

m5(x)=x2+x+1m7(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)第32頁，共36頁，2023年，2月20日，星期四32(6)根據(jù)15=1以及元素階的定義及性質(zhì)，可得元素1的階為1；,2,

4,8,7,14,13,11的階為15；3,6,12,9的階