纠错编码代数基础

纠错编码代数基础1第1页，共36页，2023年，2月20日，星期二第七章纠错编码代数基础

内容提要：抽象代数又称近世代数，其研究对象是定义在某些运算下的集合，运算对象可以是数、多项式、矢量、矩阵、线性空间等。编码理论是建立在码的代数结构基础上的，为便于初学者理解，本章简单介绍抽象代数中与编码直接相关的基础知识，主要涉及整数及多项式的一些基本概念及群、环、域的基本知识。2第2页，共36页，2023年，2月20日，星期二本章重点：1.多项式的因式分解及有限域的本原元的基本概念；2.有限域共轭根组的求解。

3第3页，共36页，2023年，2月20日，星期二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第4页，共36页，2023年，2月20日，星期二定理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第5页，共36页，2023年，2月20日，星期二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第6页，共36页，2023年，2月20日，星期二l交换群

如果*运算还满足交换律，即对任何a,bG，有ab=ba，则G称作交换群。加法群是交换群，而乘法群不一定是交换群，如矩阵乘法不满足交换律。

l群的阶群的阶就是群中所含元素的个数。如整数加法群和非0实数乘法群的阶都是无穷值。l有限群阶为有限值的群称作有限群。7第7页，共36页，2023年，2月20日，星期二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第8页，共36页，2023年，2月20日，星期二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第9页，共36页，2023年，2月20日，星期二

(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第10页，共36页，2023年，2月20日，星期二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第11页，共36页，2023年，2月20日，星期二陪集说明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第12页，共36页，2023年，2月20日，星期二陪集首的选择应注意：(4)陪集hG′中的每一个元素都可作为其陪集首h，陪集元素不变，仅排列顺序改变。

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

G′与hj

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

与子群G′相同。13第13页，共36页，2023年，2月20日，星期二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第14页，共36页，2023年，2月20日，星期二定理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第15页，共36页，2023年，2月20日，星期二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第16页，共36页，2023年，2月20日，星期二

理想理想是一类特殊的子环。设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第17页，共36页，2023年，2月20日，星期二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第18页，共36页，2023年，2月20日，星期二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第19页，共36页，2023年，2月20日，星期二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第20页，共36页，2023年，2月20日，星期二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第21页，共36页，2023年，2月20日，星期二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第22页，共36页，2023年，2月20日，星期二7.3.3有限域的本原元

定理7.13

元素个数相等的有限域必同构。

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

q-1=e(q–1是使等式成立的最小正整数)，则称为本原元。

本原多项式是以本原元为根的即约多项式。23第23页，共36页，2023年，2月20日，星期二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第24页，共36页，2023年，2月20日，星期二定理7.16有限域的阶必为其特征之幂，即q=pm。定理7.17在以p为特征的域GF(q)中，对于任意、GF(q)，恒有(+)p=p+p

推论1

若1,2,…,k是以p为特征的域中的元素，则对任意正整数n恒有25第25页，共36页，2023年，2月20日，星期二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第26页，共36页，2023年，2月20日，星期二最小多项式的性质：l(1)最小多项式在GF(p)上是即约的;l(2)每一GF(pm)，必有唯一的最小多项式;l(3)的最小多项式能整除任何以为根的多项式。

推论2设m1(x),m2(x),…,mt(x)为GF(pm)中各元素的最小多项式，那么可将多项式在GF(p)上分解为27第27页，共36页，2023年，2月20日，星期二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第28页，共36页，2023年，2月20日，星期二剩余类线性组合幂级数矢量00000001110001x0010x2220100x3331000x

+

1+140011x2+x2+50110x3+x23+261100表7-13GF(24)中元素的四种表示29第29页，共36页，2023年，2月20日，星期二剩余类线性组合幂级数矢量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第30页，共36页，2023年，2月20日，星期二(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第31页，共36页，2023年，2月20日，星期二(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第32页，共36页，2023年，2月20日，星期二(6)根据15=1以及元素阶的定义及性质，可得元素1的阶为1；,2,4,8,7,14,13,11的阶为15；3,6,12,9的阶为5