信道编码有限域和多项式

信道编码有限域和多项式第1页，共35页，2023年，2月20日，星期三学习本章目的：对Xn-1进行因式分解(n=qm-1,q为素数)X15-1=(x+1)(x4+x3+1)(x4+x3+x2+x+1)(x2+x+1)(x4+x+1)Xn-1?循环：只有最高位和最低位第2页，共35页，2023年，2月20日，星期三一、剩余类环环，子环、扩环回顾环（R，+，*）的定义定义了两种运算+和*R对+构成阿贝尔群*满足封闭性、结合律*对+满足分配律*不一定有恒等元1，R的元素不一定有逆元非空子集S是环（R，+，*）的子环的充要条件:a,bS:a-bS;S是群（R，+)的子群a,bS:abSS对*满足封闭性

第3页，共35页，2023年，2月20日，星期三一、剩余类环理想定义:交换环R中的非空子集I称为R中的理想，若：

a,bI:a-bI;aI,rR:ar=raI;1)+2)

理想是个子环，2)

I中任一元素a的倍数在I中，即I由R的一些元素（可以是多个）的倍数组成。主理想：由一个元素的的所有倍数组成的理想.这个元素叫生成元.主理想环:每一个理想都是主理想第4页，共35页，2023年，2月20日，星期三一、剩余类环剩余类环 定理1(定理4.1.2)：设I

为可换环R的一个理想，则R/I构成一个可换环，称为模I的剩余类环。例:Mod5的剩余类环I {0}: 0 5 -5 10 -10 …. 1+I{1}: 1 6 -4 11 -9 ….2+I{2}: 2 7 -3 12 -8 ….3+I{3}: 3 8 -2 13 -7 ….4+I{4}: 4 9 -1 14 -6 ….{{0},{1},{2},{3},{4}}对模5+和模5*构成可换环第5页，共35页，2023年，2月20日，星期三二、多项式剩余类环多项式Fq上的多项式：f(x)=fnxn+fn-1xn-1+…+f2x2+f1x+f0 fiFqi=0,1,2,…,n次数n记为：f(x),f,degf(x),degfWhy多项式？

矢量a=(1,0,1,1,0,1)（位置）

多项式f(x)=x5+x3+x2+1（次数）为了借用多项式的运算来定义矢量的运算多项式的除法例：(x9+x8+x7+x2+x+1）/（x4+x3+x+1）n次多项式域（群、环）与n维矢量域（群、环）在下列映射下同构：f(x)=fnxn+fn-1xn-1+…+f2x2+f1x+f0（fnfn-1…f2f1f0）第6页，共35页，2023年，2月20日，星期三二、多项式剩余类环定理2：集合G与G

同构

（G为群(环、域)

G为群(环、域)）首一多项式：fn=1，最高次数为1，f(x)1。Fq[x]:表示系数属于Fq的所有多项式的集合多项式环整数是一个环，多项式与整数类似。定理3：Fq[x]构成一个环 零元：f(x)=0第7页，共35页，2023年，2月20日，星期三二、多项式剩余类环性质整数环多项式环零元素0f(x)=0恒等元1f(x)=1不可分解的元素数既约多项式（除提取常数，不能进行因式分解，定义4.4.2）素多项式=首一+既约多项式分解的唯一性a=p1r1p2r2…(素数幂的积）f(x)=p1(x)r1p2(x)

r2…每一个首一多项式可唯一分解为素多项式的幂的积(定理4.2.3)欧几里德除法若a>b,则a可唯一表示为:a=qb+r,0rb若f(x)

>g(x),则:f(x)=q(x)g(x)+r(x)0r(x)g(x)(定理4.2.2)第8页，共35页，2023年，2月20日，星期三二、多项式剩余类环性质整数环多项式环约数最大公约数(a,b),GCD(a,b)最高公因式(定义4.2.3)(是首一多项式）（f(x),g(x)),GCD(f(x),g(x))倍数最小公倍数[a,b],LCM(a,b)最低公倍式(定义4.2.4)(是首一多项式）[f(x),g(x)],LCM(f(x),g(x))欧几里德算法a=qb+r(a,b)=(b,r)(a,b)=Aa+BbA,B为正整数f(x)=q(x)g(x)+r(x)(f(x),g(x))=(g(x),r(x))(例f(x)=x9+x8+x7+x2+x+1,g(x)=x4+x3+x+1)(f(x),g(x))=A(x)f(x)+B(x)g(x)0A(x)<g(x)-(f(x),g(x))0B(x)<f(x)-(f(x),g(x))[a,b]=ab/(a,b)[f(x),g(x)]=f(x)g(x)/(f(x),g(x))第9页，共35页，2023年，2月20日，星期三二、多项式剩余类环性质整数环多项式环主理想Im为生成元（m的一切倍数的集合）以f(x)为生成元:f(x)的一切倍式组成的集合If(x)组成一个理想（引理4.2.1)例I(x2+1)剩余类环以模m的剩余类为元素,记为Zm或Z/(m)以f(x)对If(x)的陪集为元素,记为Fq[x]/f(x)（定理4.2.8)主理想环是主理想环是主理想环（定理4.2.10)有限域m为素数Zm是一个域f(x)为既约多项式Fq[x]/f(x)是一个域（定理4.2.9)第10页，共35页，2023年，2月20日，星期三三、基于多项式的有限域基于整数的有限域

由素数p的同余类构成一个域，阶为p基于多项式的有限域定理3*：f(x)是Fq上素多项式

Fq[x]/f(x)是一个域。

基于多项式的有限域的生成办法：找到次数为n的素多项式，由其倍式组成一个理想，求其商群，共有qn个元素，构成一个qn有限域GF(qn)。第11页，共35页，2023年，2月20日，星期三四、循环群定义循环群:由某个元素的所有整数幂组成的群{0,1,

2,

3,….},

成为生成元。为研究有限域服务可以是乘法幂和加法幂，即对环和域，其子集对两种运算都可构成循环群

元素a的级：满足an=e的最小正整数n,若nN:an

e,则称a的级为无限大。

单位原根:n阶循环群的n级元素。第12页，共35页，2023年，2月20日，星期三四、循环群无限循环群：成为生成元，nm(nm)有限循环群：h,kZ,且hk:h=k

设h>k,n=h-k,n=h-k=h-k=k-k=e

一定是{0=e,,2,……,n-1}

例:Z/(8)2.定理4

(定理4.3.1)：可换群G的任一n级元素a

皆可生成一个n阶循环子群

。

循环群是可换群，所以由其中元素i皆能生成一个循环群，其阶数为i的级数。

这个循环群可以是它本身，或是它的子群。第13页，共35页，2023年，2月20日，星期三四、循环群循环群G的性质：G必为阿贝尔群；a为n级元素，则

ak的级为n/(k,n);a为n级元素，则am=e

n|m;n阶循环群中每个元素的级数m满足m|n.n级元素a与m级元素b

满足(n,m)=1,则ab为nm级元素;定理5(推论4.3.3)：n阶循环群中必有(n)个单位原根。 (n)=|{a|0an-1且（a,n）=1}|(欧拉函数，小于n且与n互素的自然数的个数)第14页，共35页，2023年，2月20日，星期三四、循环群5.由已知循环群寻找其全部子群（定理4.3.2)G(a)为由a生成的n阶有限循环群，H为G(a)的子群H为有限阶循环群，或者是{e},或者是由am生成的q阶循环群：{e，am，a2m，…

，

an-m}（其中q|n,m=n/q）若m|n,则G中必有唯一的n/m阶循环子群，生成元是am第15页，共35页，2023年，2月20日，星期三五、有限域GF(q)的乘法结构有限域GF(q)非零元素全体对乘法构成阿贝尔群，由定理4，任一非零元素可生成一个有限循环子群，其阶称为的级，即使n=1的最小正整数n,称为GF(q)的n次单位原根，若n=q-1,则称为GF(q)-{0}的生成元，称为本原域元素。循环群的单位原根：n级元素称为n次单位原根。

本原域元素(本原元):

q-1级元素第16页，共35页，2023年，2月20日，星期三五、有限域GF(q)的乘法结构定理6

：Fq上的n级元素

生成的n阶循环群G()是方程

xn-1=0的全部根。证明：设´G()

的级为h,由定理4，´可生成一个阶为h的循环子群，而子群的阶必为G()的阶n的因子，所以h|n,´n=(´

h)n/h=1方程xn-1=0的根不多于n个，而G()中，n个元素都是它的根，所以全部根落在G()中。推论1：若Fq含有n次单位原根，则xn–1可分解为

。第17页，共35页，2023年，2月20日，星期三五、有限域GF(q)的乘法结构定理7：Fq

必有本原域元素存在，所以Fq

–{0}是一个

q-1阶乘法循环群。所以

Fq

–{0}={,2,…,q-2,q-1=e} 这称为有限域的幂表示法。

推论2

(定理4.4.1)：方程xq-1–1=0的全部根构成Fq

–{0}.

Fq为xq–x=0的全部根，即xq–x=x

Fq称为xq–x的最小分裂域

推论3(费马Ferma定理,定理4.5.5)：

Fq:q=.

第18页，共35页，2023年，2月20日，星期三五、有限域GF(q)的乘法结构例GF(2)上的多项式x15–1=

GF(16)-{0}={1,,2,3,…,14}

每个元素的级是15的因子，15的因子有1、3、5、15，所以GF(16)非0元素的级为1、3、5、15，其中i的级为15/（15,i)，所以 1,,2,3,4,5,6,7,8,9,10,11,12,13,14级:1,15,15,5,15,3,5,15,15,5,3,15,5,15,15级数为1:1, 3:5,10

5:

3,6,9,12, 15:

,2,4,7,8,11,13,14把同级的一次因式相乘得

=(x-1)[(x-5)(x-10)][(x-3)(x-6)(x-9)(x-12)]

[(x-)(x-2)(x-4)(x-7)(x-8)(x-11)(x-13)(x-14)]=Q(1)(x)Q(3)(x)Q(5)(x)Q(15)(x)第19页，共35页，2023年，2月20日，星期三五、有限域GF(q)的乘法结构分园多项式

xn-1=

为n级元素,则i为n/(n,i)级元素,把同级的分为一类,得k类,即n1=n/(n,i1),nd=n/(n,id),…,nk=n/(n,ik)

以d级元素为根的所有一次因式的积叫分园多项式(定义4.4.3)

分园多项式是GF(2)上的多项式,并且可以通过后面介绍的方法求得,亦即xn-1至少可分解为分园多项式的积第20页，共35页，2023年，2月20日，星期三五、有限域GF(q)的乘法结构定理7*(定理4.4.5,p120):(求分园多项式)

xn

–1=

Q(d)(x)为分圆多项式，Q(d)(x)==

为Mobius函数，(m)=0,m有平方因子 =(-1)k,m

不含平方因子,且可分解为k个因子的积 =1,m=1第21页，共35页，2023年，2月20日，星期三六、有限域GF(q)的加法结构基本概念周期:模拟乘法的级a+a+a+…+a+a=n`a=0

n个a相加，即加法幂，记为n`a

(课本的na不是n乘a）任意aGF(q)(a0),满足n`a=0的最小正整数或。2）特征：乘法单位元e的周期，即满足n`e=0的最小正整数n,如果nN:n`e0,则称域的特征为

a=a*e

n`a=a+a+…+a=a*e+a*e+…++a*e

=a*(e+e+…+e)=a*(n`e)=0（根据分配律）n个第22页，共35页，2023年，2月20日，星期三六、有限域GF(q)的加法结构定理8：域中任一非零元素的周期都等于域的特征（定理4.5.1)域整数：a=z`e(z

Z)(e的倍数)例如GF(4)={0，1，2，3}中，1+1=0，周期为20、1为域整数定理9：域的特征或为素数，或为。（定理4.5.2)假设特征h不为素数，h=m*n,则

h`e=(m*n)`e=m`(n`e)=0

n`e的周期m<h,这与定理8矛盾。

（根据结合律）m*n个e相加m个(n`e)相加第23页，共35页，2023年，2月20日，星期三六、有限域GF(q)的加法结构定理10：在p特征域GF(q)中，全体域整数构成p阶素子域GF(p),且同构于Z/(p)(定理4.5.3)GF(p)称为GF(q)的基域，GF(q)称为GF(p)的扩域。定理11：p特征域GF(q)中，(定理4.5.4)aGF(q):(x-a)p=xp

–ap推论4:若k是p特征域的域整数，则=k(nN)(推论4.5.4)

没有真子域P为素数X可以取扩域GF(q)中的元素第24页，共35页，2023年，2月20日，星期三六、有限域GF(q)的加法结构定理12: 在p特征域Fq中：元素a为域整数

ap-a=0

(定理4.5.5)2.最小多项式与本原多项式

最小多项式、元素的次数、本原多项式：设Fq为FQ

的子域，w

FQ,m(x)是Fq上满足

m(w)=0的次数最低的首一多项式，称

m(x)为w在Fq上的最小多项式，m(x)称为w的次数。若w为FQ的本原元，则称m(x)为本原多项式。问题：f（x)=x-w

是不是w的最小多项式？

第25页，共35页，2023年，2月20日，星期三六、有限域GF(q)的加法结构定理13

(定理4.5.8)：w在Fq上最小多项式m(x)的性质：m(x)在GF(p)上既约；存在且唯一；若Fq上多项式f(x)

满足

f(w)=0,则

m(x)|f(x);（以w为根的多项式是m(x)的倍式）；m(x)|xq-x.

定理14

(相当于定理4.6.2)：令f(x)为Fq上任意多项式，则存在扩展域FQ,在FQ中f(x)可分解为一次因子的积，称FQ为f(x)的分裂域。

以素多项式f(x)生成一个有限域Fq[x]/f(x),在这个域中，。可见，如果f(x)是GF(p)上的素多项式，而且f(w)=0,则f(x)为w的最小多项式。第26页，共35页，2023年，2月20日，星期三六、有限域GF(q)的加法结构定理15(课本没有)：设Fq为FQ的真子域，是FQ的本原元，

的次数为m,则

Q=qm，

且

FQ:

=,ai

Fq

证：第一步：证Q≥qm

a.形式为的元素在FQ中

设=,ai

Fq，则FQ

b.不同形式对应不同的元素 设1=,ai

Fq

2=,bi

Fq

且i:ai≠bi则1≠2反证法，如1=2，则

在Fq中有次数比m更小并以为根的素多项式。这与的次数为m矛盾

形式为的元素有qm个，全部落在FQ中，所以Q≥qm第27页，共35页，2023年，2月20日，星期三六、有限域GF(q)的加法结构第二步：证Q≤qm 为FQ的本原域元素，则

FQ:

=k

又设在Fq的最小多项式为

f(x)=xm+fm-1xm-1+fm-2xm-2+…+f1x+f0 则f()=

m+fm-1

m-1+fm-2

m-2+…+f1

+f0=0，

….

k可表示为（

m-1，

m-2，

,1)的线性组合，而（

m-1，

m-2，

,1)的线性组合共qm个，所以Q≤qm

综上述，Q=qm推论5(定理4.6.1)：有限域的阶必为其特征的幂，因此它是素数的幂。

第28页，共35页，2023年，2月20日，星期三六、有限域GF(q)的加法结构3．共轭根:定理16

（定理4.5.6）:f(x)为Fp上的多项式，

w为Fp的扩展域上的元素且f(w)=0,则对于n

N,有,叫w的共轭根，共轭根的集合组成共轭根系

设w为f(x)的根（Fpm的元素）,观察共轭根:n= 0,1,2,…,m-1, m,m+1,…,w,wp,,…, ,,,…,

所以

，方程f(x)=0的共轭根,最多m个。设m´为满足wpk=w的最小正整数k,则w的共轭根有m´个，这m个根实际上是由m´个共轭根组成的m/m´

个循环。所以m´|m设w的级数为n,则n|pm-1,所以pm≡1（modn)P对模n的方次数:满足pm

1(modn)的最小整数m称为p对模n的方次数第29页，共35页，2023年，2月20日，星期三六、有限域GF(q)的加法结构定理16*（推论4.5.7）：各个共轭根的级数相同，最小多项式相同。w的级为n,则wp的级为n/(n,p)=n定理17（定理4.5.9）：设w是Fq的扩展域FQ的n级元素，而m是q对模n的方次数，则w的次数为m,且其在Fq上的最小多项式m(x)=多项式的周期

多项式

f(x)的周期p(f):

设f(x)

Fq[x],f(0)0,

满足

f(x)|(xl-1)

的最小正整数l.

定理17*p(f)的性质:

p(f)等于Fq[x]/f(x)中的级数。第30页，共35页，2023年，2月20日，星期三七、有限域GF(q)的代数结构定理18（定理4.6.3）(1)

s|r;（正向可直接从定理15推出）(2)

定理19（定理4.6.4）Fq,nN:定理20(定理4.6.6）

-x=(-x可分解为次数为m的因子的素多项式的积)定理21(定理4.6.7）

f(x)为Fq上的d次既约多项式，且d|m,则任一含有f(x)的全部根。

第31页，共35页，2023年，2月20日，星期三七、有限域GF(q)的代数结构定理22(定理4.6.8）

Fq上的m次既约多项式的数目是.

(d)为Mobius函数。

第32页，