糾錯編碼代數基礎1第一頁，共三十六頁，2022年，8月28日第七章糾錯編碼代數基礎

內容提要：抽象代數又稱近世代數，其研究對象是定義在某些運算下的集合，運算對象可以是數、多項式、矢量、矩陣、線性空間等。編碼理論是建立在碼的代數結構基礎上的，為便于初學者理解，本章簡單介紹抽象代數中與編碼直接相關的基礎知識，主要涉及整數及多項式的一些基本概念及群、環、域的基本知識。2第二頁，共三十六頁，2022年，8月28日本章重點：1.多項式的因式分解及有限域的本原元的基本概念；2.有限域共軛根組的求解。

3第三頁，共三十六頁，2022年，8月28日7.1群7.1.1群的定義1.整數的相關概念定理7.1

設a為整數，d為正整數，且ad，則存在唯一的整數q、r滿足a=qd+r

，0r<d

。d稱作模，r稱作余數，r可記作a[modd]。由于0r<d，模d的全體余數為{0,1,…,d–1}。余數間可定義模d加法和模d乘法運算，設D={0,1,…,d–1}，如果a,bD，有(a+b)[modd]

D及(ab)[modd]

D說明模d的余數全體對模d加法和模d乘法滿足封閉性。

4第四頁，共三十六頁，2022年，8月28日定理7.2

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

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

設a、b是不全為0的整數，則存在整數p、q使

pa+qb=(a,b)

(a,b)為a、b的最大公約數，當a、b互素時，(a,b)=1，pa+qb=1。5第五頁，共三十六頁，2022年，8月28日2.群的定義群G是一些元素構成的集合，該集合中定義一種運算*（加法或乘法），滿足：

封閉性，對任何a,bG，有abG

(2)結合律，對任何a,b,cG，(ab)

c=a(bc)(3)存在單位元eG，使對任何aG有ae=ea=a

(4)對任何aG有逆元a-1

G，使aa-1

=a-1

a=e

6第六頁，共三十六頁，2022年，8月28日l交換群

如果*運算還滿足交換律，即對任何a,bG，有ab=ba，則G稱作交換群。加法群是交換群，而乘法群不一定是交換群，如矩陣乘法不滿足交換律。

l群的階群的階就是群中所含元素的個數。如整數加法群和非0實數乘法群的階都是無窮值。l有限群階為有限值的群稱作有限群。7第七頁，共三十六頁，2022年，8月28日3.群的同構

設在.運算下的集合G與在運算下的集合H是兩個群，若存在一個G到H的一一對應關系f，且對任何a,bG，有f(ab)=f(a)f(b)，則稱f是G到H的同構。

通常把條件f(a.b)=f(a)f(b)稱為f保持群的運算關系。一個同構映射f不僅保持運算關系，而且使兩個群的所有代數性質都一一對應。同構的系統本質上完全相同，研究其中一個也就代替了對另一個的研究。8第八頁，共三十六頁，2022年，8月28日7.1.2子群1.子群的定義

若群G的非空子集G′對于G中所定義的代數運算也構成群，則稱G′為G的子群。定理7.4

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

2.循環群

由一個單獨元素的一切冪次所構成的群{0=e,,2,…,n-1n=e}稱為循環群。該元素稱為循環群的生成元。使n=e的最小正整數n稱為元素的階。定理7.5

交換群G中的每一個元素都能生成一個循環群，它是G的子群，元素的階就是循環群的階。

9第九頁，共三十六頁，2022年，8月28日

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

若a是n階元素，則am=e（對于加法為ma=e）的充要條件是n整除m。(2)若某一群中，a為n階元素，b為m階元素，且(n,m)=1，則元素ab（或a+b）的階為nm。10第十頁，共三十六頁，2022年，8月28日7.1.3群的陪集分解1.群的陪集

設G′為群G的非空子群，取hG，則稱hG′為G′的左陪集，稱G′h為G′的右陪集。當G是交換群時，子群G′的左、右陪集是相等的，元素h稱作陪集首。

2.群的陪集分解

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

11第十一頁，共三十六頁，2022年，8月28日陪集說明h1g1=g1=eg2…gn-1gn

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

h2g2…h2gn-1h2gn

陪集首h2，陪集h2G′……hm-1g1

hm-1g2…hm-1gn-1hm-1gn

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

hmg2…hmgn-1hmgn

陪集首hm，陪集hmG′表7-4陪集分解表12第十二頁，共三十六頁，2022年，8月28日陪集首的選擇應注意：(4)陪集hG′中的每一個元素都可作為其陪集首h，陪集元素不變，僅排列順序改變。

(3)若陪集首hj不是陪集hiG′中的元素，則兩陪集hi

G′與hj

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

與子群G′相同。13第十三頁，共三十六頁，2022年，8月28日7.2環7.2.1環的定義

1.多項式的相關概念

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

xn-1+…+f1

x+f0

fiF

l

首一多項式

多項式的最高次數的系數為1，即fn

=1。

l多項式的階

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

即約多項式

階大于0且在給定集合F上除了常數和常數與本身的乘積外，不能被其它多項式除盡的多項式14第十四頁，共三十六頁，2022年，8月28日定理7.6

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

0r(x)<p(x)

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

任何首一多項式可分解為首一即約多項式之積：

定理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)的最大公因式15第十五頁，共三十六頁，2022年，8月28日2.環的定義

環是一些元素構成的集合，該集合中定義加法和乘法兩種運算，滿足：

l

(1)對加法是一個交換群；

l

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

l

(3)滿足分配律：對任何a,b,cF

，有：

a(b+c)

=ab+ac

(a+b)c=ac+bc

3.子環

設F是一個環，S是F的一個非空子集，若S對加法和乘法也構成一個環，則稱S是F的一個子環，F是S的一個擴環。16第十六頁，共三十六頁，2022年，8月28日

理想理想是一類特殊的子環。設F是一個可換環，I是F的一個非空子集，如果對任意a,bI，恒有a-bI，及對任意aI和任意

xF，恒有ax=xaI，則稱I是F的一個理想。定理7.9

若S是環F的一個非空子集，則S是F的子環的充要條件是：對任何a,bS，有a-bS和abS。

主理想

在可換環F中，由一個元素aF的所有倍數及其線性組合而生成的理想I[a]={xa+naxF,nZ}稱為環F的一個主理想，元素a為該主理想的生成元。17第十七頁，共三十六頁，2022年，8月28日4.環的同構

設A和B是兩個環，若存在一個A到B的一一對應關系f，并且滿足：對任何a,bA，有f(a+b)=f(a)+f(b)

f(ab)=f(a)f(b)

則稱f是環A到環B的一個同構。18第十八頁，共三十六頁，2022年，8月28日7.2.2整數剩余類環

模d的余數全體F={0,1,…,d-1}對模d加法運算構成加法交換群；對模d乘法運算滿足封閉性、結合律和交換律；還滿足分配律，因此模d的余數全體構成交換環，稱作整數剩余類環。+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第十九頁，共三十六頁，2022年，8月28日7.2.3多項式剩余類環

以p(x)為模的多項式的余式全體對模p(x)的加法運算構成加法交換群；模p(x)的余式全體對模p(x)乘法滿足封閉性、結合律和交換律；其分配律為[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)的余式全體對模p(x)的運算構成交換環，稱作多項式剩余類環。20第二十頁，共三十六頁，2022年，8月28日7.3域7.3.1域的定義域是一些元素構成的集合，該集合中定義加法和乘法兩種運算，滿足：l(1)對加法構成交換加群。l(2)非零元素全體對乘法構成交換乘群。l(3)加法和乘法間具有分配律a(b+c)=ab+ac

(a+b)c=ac+bc

域的階域中元素的個數。如復數域和實數域的階都是無窮值。

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

3,

4}21第二十一頁，共三十六頁，2022年，8月28日7.3.2有限域定理7.10設d為素數，則以d為模的整數剩余類環構成d階有限域GF(d)。定理7.11

設p(x)為系數取自GF(q)上的n次即約多項式，則以p(x)為模的多項式剩余類環構成qn階有限域GF(qn)。定理7.12

有限域的階必為其子域階之冪，即Q=qn。22第二十二頁，共三十六頁，2022年，8月28日7.3.3有限域的本原元

定理7.13

元素個數相等的有限域必同構。

本原元在GF(q)中，某一元素的階為q-1，即

q-1=e(q–1是使等式成立的最小正整數)，則稱為本原元。

本原多項式是以本原元為根的即約多項式。23第二十三頁，共三十六頁，2022年，8月28日7.3.4有限域的結構定理7.14

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

是有限域中乘法單位元e關于加法的級，也就是使pe=0的最小正整數p。定理7.15有限域的特征必為素數。素域是GF(q)的最小子域，表示為GF(p)={0,e,2e,…,(p-1)e}。24第二十四頁，共三十六頁，2022年，8月28日定理7.16有限域的階必為其特征之冪，即q=pm。定理7.17在以p為特征的域GF(q)中，對于任意、GF(q)，恒有(+)p=p+p

推論1

若1,2,…,k是以p為特征的域中的元素，則對任意正整數n恒有25第二十五頁，共三十六頁，2022年，8月28日7.3.5有限域的共軛根組定理7.18

對GF(pm)中的任意元素，恒有。定理7.19設f(x)是系數取自GF(p)的k次即約多項式，GF(pm)，若是f(x)的根，則(0r<k)也是f(x)的根。

l最小多項式系數取自GF(p)，且以GF(pm)為根的所有首一多項式中，必有一個次數最低的多項式，稱作的最小多項式。

26第二十六頁，共三十六頁，2022年，8月28日最小多項式的性質：l(1)最小多項式在GF(p)上是即約的;l(2)每一GF(pm)，必有唯一的最小多項式;l(3)的最小多項式能整除任何以為根的多項式。

推論2設m1(x),m2(x),…,mt(x)為GF(pm)中各元素的最小多項式，那么可將多項式在GF(p)上分解為27第二十七頁，共三十六頁，2022年，8月28日7.3.6有限域的綜合舉例【例7.25】在GF(2)={0,1}系數域上，以p(x)=x4+x+1為模構成有限域GF(24)，在GF(2)上分解多項式x16–x。解：(1)由于GF(2)={0,1}，e=1，1+1=0，所以特征p=2。

(2)尋找本原元設為p(x)的根，則4=+115=4443

=(+1)(+1)(+1)3=(2+1)(+1+3)=2+5++1=2+(2+)++1=115=1，因此為本原元，p(x)為本原多項式，GF(24)的15個非0元素都可以如表7-13所示表示成的方冪：0,1,…,1428第二十八頁，共三十六頁，2022年，8月28日剩余類線性組合冪級數矢量00000001110001x0010x2220100x3331000x

+

1+140011x2+x2+50110x3+x23+261100表7-13GF(24)中元素的四種表示29第二十九頁，共三十六頁，2022年，8月28日剩余類線性組合冪級數矢量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第三十頁，共三十六頁，2022年，8月28日(3)按照定理7.19，找出各個共軛根系，并構成相應的最小多項式。{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)以上最小多項式的下標是以共軛根系中的最低冪次表示的31第三十一頁，共三十六頁，2022年，8月28日(4)利用本原多項式4=+1，將最小多項式化簡。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第三十二頁，共三十六頁，2022年，8月28日(6)根據15=1以及元素階的定義及性質，可得元素1的階為1；,2,4,8,7,14,13,11的階為15；3,6,12,9的階為5；