第二章近世代数简介课件.ppt

1、第二章第二章 近世代数简介近世代数简介 千里之行，始于足下。孔子2.1 群、环、域1 群2 环3 域1 群 定义定义 对于一个非空元素集合G以及定义在G上的一种运算“*”（这里的*泛指任一种代数运算，如 模m加 ，模m乘 等），若满足以下四个条件：封闭性（Closure），即 （Forevery）结合性（Associativity），即 存在惟一的一个单元e（Identity），即 G中的每个元素各自存在惟一的逆元（Inverse），即 这里，泛指逆元，不能狭义的理解为就是1/a。则称这样的代数系统为群（Group），记做（G,*）。,()(*)a bGthere existabcG,*(*)

2、(*)*a bGabcabc,*aGaeeaa11,*aGaGaae-1-1使使a*aa*a1a 若再满足第五个条件：交换律,即 则称这样的代数系统为交换群（Commutative Group），也称阿贝尔群（Abelian Group）。如果群（G，*）中的运算*是加法，则称群（G,+）为加群（Additive Group）。加群一定是交换群。加群中一定包含零元素，零元素正是该加群的单位元e。加群元素a的逆元 是代数中的-a。如果群（G，*）中的运算*是乘法，则称群（G,.）为乘群（Multiplicative Group）。乘群中一定不包含零元素，因为零元素不存在乘法运算下的逆元。乘法不一

3、定是交换群。乘法的单位元是1，乘法元素a的逆元 是代数中的1/a.如果群（G，*）中包含无数个元素，则称该群为无限群。,*a bGa bb a1a1a 如果群（G，*）中包含有限个元素，则称该群为有限群。构成有限群的元素的个数称为该群的阶。如果在群（G，*）中，集合G的非空子集S在同样的运算*下可构成群（S，*），则称群（S，*）为群（G，*）的子群（Subgroup）。（S，*）为（G，*）子群的充要条件是：对于 充要条件的这种表述形式，强调了子群元素逆元的存在性以及子群的封闭性。如果群（G，*）是有限群，则其子群（S，*）也是有限群，且子群的阶数一定是（G，*）阶数的因子。上述性质是由拉格

4、朗日定理（Lagranges）给出的。若（A，*）和（B，*）分别是（G，*）的两个子群，则A和B的交集在同样运算下也构成（G，*）的子群 。群（G，*）的任意个子群的交集也是（G，*）的子群。1,*a bSa bS必必有有(,*)AB 某一元素a（称作生成元a）的一切乘幂 的全体组成一个群，称为循环码，写做 其中 是单位元。若序列 中没有两个元素是相等的，称之为无限循环码。若上述序列中有两个相等的元素 可推出G元素必以n为周期重复，即 ，这样的循环群为有限循环群，写做 循环群也叫幂群，具有以下性质：循环群是交换群；循环群的子群 仍是循环群；n阶有限循环群的子群的阶数一定是n的因子。例2.1

5、若R表示有理数集合，I表示整数集合，E表示偶数集合，则 在加法运算下，（R，+），（I，+）和（E，+）均构成加群，且（I，+）和（E，+）是（R，+）的子群，（E，+）也是（I，+）的子群。该加群的单位元是0。作为对比，奇数集合O在加法运算下构不成群，因为它不满足要求的封闭性。012,aa a 012,Gaaa0ae012,ae a a()ijaa ij0naae21,nGe a aa,EIR 例2.2 若G表示去除0后的有理数集合，则验证条件 后可断言：G在乘法运算下构成（G，.），该乘群又是交换群。例2 2.3.3 集合G=0，1，2，m-1在模m加（用符号 表示）运算下构成一个加群（G

6、，）。该加群是m阶有限群，单位元是0。0的逆元是0，1的逆元是m-1,2的逆元是m-2，。例2 2.4.4 集合G=1,2,，q-1在模q乘（q是素数）运算下构成一个乘群（G，）。这里，符号 表示模q乘。该乘群是q-1阶有限群，又是交换群，单位元是1。乘群的每个元素a都存在一个逆元 满足 ，或写成：b=（nq+1）/a，n为任意正整数 （2-1）mod1abq2 环 对于非空元素的集合R以及定义在R上的乘、加两种运算，如满足以下3种条件：集合R在加运算可构成加群（R，+）。集合R在乘运算下满足群的前三个条件，即封闭性、结合性及单位元存在性（这里由于少了条件而不提构成乘群。因为既然是加群（R,+

7、），R中必然含有零元素0，而0不存在乘法运算下的逆元）。分配律，即 则称该代数系统为环（Ring），记做 简称环R.如果环R还满足第4个条件：乘法交换律，即 则称该环为交换环。,(),()a b cRa bca ba c bc ab ac a,R ,a bRa bb a 有限整数的集合在乘、加运算下可以构成有限环。比如，集合Z=0，1，2，m-1在模m加、模m乘运算下可以构成有限环，也称剩余类环。这里的m是整数，不要求一定是素数。但不是素数时，环内会存在零因子，称之为零因子环。所谓零因子，是这样定义的：则称a,b为零因子。由零因子时，乘法消除律不能成立，即从ab=ac不能推得b=c。不存在零因

8、子的交换环称为整环。集合Z=0，1，2，q-1在模q加、模q乘运算下可构成有限整环，这里q是素数。与群有子群一样，环也有子环。子环的定义是：若S是集合R的子集，且在相同的两种运算下构成环（S，+，）和环（R，+，），则称环S是环R的子环。,0,0,0,a bR aba bR若若 判断S是R子环的充要条件是：条件强调了子环中加法逆元的存在和封闭性，条件强调了乘法的封闭性。一种具有很强聚合力的子环叫做理想子环。理想子环的充要条件是：若R是交换环，I是R的非空子集，如满足 则I是R的理想子环，建成理想。与一般子环相比，理想子环要求更多的条件：R必须是交换环且具有凝聚力，即任意一个子环元素与任意一个非

9、子环的环元素运算后所得的元素一定位于子环内。环R的任意多个理想子环的交集仍是R的理想子环。,a bSabS ,a bSa bS,;,a bIabIaI rRa rr aI 若理想子环的所有元素可有一个元素a的各次幂的线性组合生成，则称该理想子环为主理想子环，简称主理想，元素a称做生成元。例2.5 全体整数在乘、加运算下构成整数环（I，+，），该环又是交换环。某一整数m的整倍数的集合 在加、乘运算下也构成一个环，这个环是整数的子环。m=2时构成的子环就是偶数环，而奇数全体构不成环，因为它不含加法单位元0且不满足封闭性。例2.6 有限整数集合Z=0,1,2,m-1在模m加、模m乘运算下构成交换环

10、模m加、乘的定义分别是：且服从运算规则：及0,2,3,mmm,Z ()mod()mod ab=ab=ababma bm及及()mod modmodmodabmambmm()modmodmodmoda a b b=mam bmm3 域 定义:对于至少含有一个非零元素的交换环F，若每个非零元素都存 在乘法运算下的逆元，则称该交换环为域（Field），记做（F，+，），简称域F。有理数、实数、复数全体在乘、加运算下分别构成有理数域、实数域和复数域，他们包含无限个域元素，因此称之为无限域。有限整数集合F=0,1,2,q-1（q是素数）在模q加、模q乘运算 下构成一个q阶有限域，又称迦逻华（Galois

11、）域，记做GF(q)。例2.7 q=5时的迦逻华域GF(5)=0，1，2，3，4由5个域元素组 成，其中非零元素是1，2，3，4。为了弄清哪些元素可以作为生成元，分别计算各元素的各次幂，结果图下表：从上表可知，域元素2和3的各次幂可以生成全部非零域元素，所以2和3都是本原元。元素1的各次幂只能产生元素1，元素4的各次幂只能产生元素1和4，他们都不是本原元。由元素乘幂能产生的域元素的个数称为该元素的阶。上例中，2和3为4阶域元素，1和4分别为1，2阶域元素。元素各次幂元素的阶加法逆元乘法逆元1111114121243433313424224141421432102.2 多项式剩余类环和域多项式剩

12、余类环和域多项式是码字与代数之间的桥梁。比如，对于码字（1101），可写成代数式 ，其系数代码原取值，x的幂次指示码元位置。系数属于某数域的多项式，称为该数域上的多项式。比如，二进制系数的多项式称为二元域GF(2)上的多项式，q进制系数的多项式称为q元域GF(q)上的多项式。以数为元素可以构成群、环、域，以多项式为元素同样可以构成群、环、域。下面将讨论用多项式构成群、环、域的方法、条件和性质。32xxx 1多项式环和理想子环 2多项式域和群环域1多项式环和理想子环某数域上多项式的集合在乘、加运算下可以构成一个多项式环，它是一个以多项式为环元素的交换环。多项式的两个要素是系数和幂次，只要其中一个

13、有无限取值，比如系数所在数域是无限域（实数、整数等）或多项式的幂次无限，则多项式环元素的数目也就无限，称之为无限环。然而在纠错码的实际使用中，码集总是有限的，对应的多项式环也应是有限环，因此必须在系数和幂次两个方面对构成环的多项式进行限制。最常用的方法就是利用模运算产生数量有限的剩余类。编码中使用的多项式剩余类环的定义如下：GF(q)上的多项式在模q加、模f(x)乘运算下，多项式剩余类的全体所构成的交换环称为多项式的剩余类环，记作 。显然，多项式剩余类环是靠GF(q)与保证系数有限，靠模f(x)乘保证幂次有限的。多项式运算中包含了系数间模q乘、加的数域运算。qf xRx对于元素 和 ，多项式加

14、“+”定义为：(2-2)多项式modf(x)乘“.”定义为:(2-3)n-1iii=0A x=a x n-1iii=0B x=b x -1mod0ABniiiqixxabx -11mod00modABnnj kjkqkjf xxxa bx 多项式剩余类环的环元素是模f(x)乘的产物，即 除以f(x)的余式。余式也就是“剩余”类环名称的来历。如果f(x)的最高次幂是n，称此f(x)是n次多项式，写做 。这里 表示阶次degree。显然，多项式剩余类环 中所有环元素的次数不高于n-1次，通式形式为：如果多项式最高次项的系数为1，则称该多项是首一多项式。仅包含最高次项和常数项1，且形式为 的首一多项

15、式成为n次最简首一多项式。A xB xdeg()f xn deg qf xRx 121210,0,1,1nnnniaxaxa xaaGF qin1nx 例例2.8 剩余类环 中，。若 ，是两个环元素，求 是什么元素？该剩余类环至多有多少元素组成？解：解：本题的多项式系数曲子GF(2)=0，1，系数做模2加、模2乘。第一步，做一般的多项式乘法运算如下：第二步，将结果除以f(x)后取余式，得：所以 qf xRx 32,1qf xxx 21A xxx 21B xx A xB x 224322431111A xB xxxxxxxxxxxx 43321/11xxxxxxxx商余式 2mod()f xA

16、xB xxx 本题f(x)是3次多项式degf(x)=3，因此环元素的幂次不会超过2环元素的通式可以表示为 ，其中 ，3个系数最多可能有8种组合，即该剩余类环至多有8个域元素组成。与整数环存在子环一样，多项式环也存在多项式子环。如果说GF(q)上无线幂次的多项式构成一个无限环，那么任一n次多项式f(x)的一切倍式是该无限环的一个理想子环。以f(x)为模的多项式剩余类的全体构成一个有限元素的多项式剩余类环 ，这个环也可以有子环。可以证明：中的每一理想子环皆为主理想，且该主理想的生成多项式g(x)必定能整除f(x)。2210a xa xa 210,20,1a a aGF qf xRx qf xRx

17、2 多项式域和群环域剩余类环 拥有环的一切性质，包括单位元的存在性。但环对非零元素的逆元是否存在并没有提出任何限定，这促使人们进一步探讨剩余类环的所有非零元素是否都存在逆元？在什么条件下可以构成一个域？域元素之间有什么关系？在讨论这些问题之前，有必要先介绍几个术语。1.既约多项式(Irreducible Polynomials)2.本原多项式(Primary Polynomials)3.多项式循环群(Cycle Group)qf xRx1.既约多项式对于某属于上的多项式 ，若出了常数C以及 外，不能被该数域上的任何其他多项式整除，则称 为该数域上的既约多项式。顾名思义，“既约”就是已经化减到不

18、能再约的程度，因此多项式 为既约的充要条件是不能进一步分解成两个次数低于 的多项式的乘积。由于n次多项式可有n个根，因此最多只能分解为n个一次多项式的乘积，叫做完全分解。显然，一次多项式一定是既约的。同时在定义既约时反复强调了既约所对应的数域。比如，多项式 在实数域是既约的；但在复数域不是既约的，可分解为(x+i)和(x-i)两项的乘积；在二元域也不是既约的，可分解为(x+1)和(x-1)两项的乘积。1P x 1CP x 1CP x 1CP x 1CP x 21fxx2.本原多项式对于有限域GF(q)上的m次既约多项式P(x)，若能被它整除的最简首一多项式 ，则称该多项式为本原多项式。本原多项

19、式一定既约；反之既约多项式未必是本原的。1nx 3.多项式循环群由多项式的各次幂所构成的群称为多项式循环群。多项式是群元素之一，成为该循环群的生成元。比如，构成乘运算下的无限循环群；若 ，必然产生以 为主值的周期性，则称 为乘运算下由7个元素组成（7阶）的有限循环群。讨论多项式域的前提是这个域必须是存在的。因此，首先以定理的形式解决多项式域的存在性问题。23456781,71a 234561,0234561,定理定理2.1 若 是GF(q)上的m次既约多项式，则GF(q)域上次数小于m的多项式的全体，在模q加、模 乘运算下构成一个 阶的有限域，称为GF(q)域的扩域(Extension Fie

20、ld)，写做 。成GF(q)是扩域 的基域。定理定理2.2 若P(x)是GF(q)上的m次本源多项式，则 域上次数小于m的非零多项式的全体（共 个），在模P(x)乘运算下构成一个多项式的循环群。也就是说，扩域 里至少存在一个本原元，（代表一个次数小于m的多项式），它的各次幂 构成了扩域 的全部非零域元素。1P x 1P xmqmGF qmGF qmGF q1mq mGF q01,22,mqmGF q 对照定理对照定理3.1、定理、定理3.2及多项式剩余类环的定义可知：以及多项式剩余类环的定义可知：以GF(q)上的多上的多项式项式f(x)为模的成运算可生成剩余类环，以既约多项式为模的成运算可生成

21、剩余类环，以既约多项式 为模的乘运为模的乘运算可生成多项式域，以本原多项式算可生成多项式域，以本原多项式P(x)为模的乘运算所生成的非零域元为模的乘运算所生成的非零域元素可以构成多项式循环群。可见，模多项式的限制条件越多，环元素具素可以构成多项式循环群。可见，模多项式的限制条件越多，环元素具备的性质越多。备的性质越多。以上两条定理是存在性定理，下面的定理说明如何找到构成循环群的生以上两条定理是存在性定理，下面的定理说明如何找到构成循环群的生成元。成元。1P x 定理定理 2.3 GF(q)上的本原多项式P(x)在扩域 上的根 一定是本原元。证明：证明：由本原多项式的定义知，P(x)能整除 ，即

22、 上式可以改写成：设是本原多项式P(x)的根，即代入P(x)后满足P()=0，则带入上式后可得：所以 。因为 ，而 ，不但构成了全部 个非零扩域元素，而且这些元素构成循环群，所以是本原元。mGF q1nx|1 1nmP xxnq其中 1nxP x q x 110mqPq 11mq01221,1mq101mq021mmqq的个幂次1mq 综合上述三个定理，可知构成循环群的步骤如下：1.找一个GF(q)上的m次本原多项式P(x)。2.取其根及根的各次幂 。3.构成循环群元素。上述过程找到的本原元的各次幂可以产生全部 个非零扩域元素。但事实上，循环群中任一元素的幂次都可以产生一个循环群，只不过有的元

23、素可以产生整个 阶循环群，这样的元素成为本原元，本书中用来表示。有的元素只能产生 阶循环群的一部分即一个循环子群，这样的元素成为非本原元，本书用来表示。究竟什么样的域元素是本原的？什么样的域元素是非本原的？它们的阶又是多少？定理2.4对此作了判定。02,mq1mq1mq1mq 定理定理2.4 扩域上非零元素 的阶一定是 的因子，其值为：这里，GCD表示最大公约数（Greatest Common Divisor)。由式（2-4）算出的非零元素 的阶n，也就是该元素的循环周期，或者说该元素的各次幂所能产生的域元素的个数。如果元素的阶 ，说明它可以产生全部非零域元素，是本原元；如果元素的阶 ，则n一

24、定是 的因子，必能整除 ，该域元素是非本原元。mGF q0,1,2kmkq1mq 1,1 (2-4)mmnqGCD k qk1mnq1mnq1mq1mq 定理定理2.4推论推论 循环群中，n阶元素的n次幂恒等于1。证明：证明：设n阶域元素 是本原元的k次幂，且 ，则上式中，是k的因子，即 是整数而k11mq11,1,11mmmmkqnnkkkqGCD k qGCD k q,1mGCD k q,1mk GCD k q 11mq 定理定理2.5 扩域 上所有非零元素 都是GF(q)上多项式 的根，即 可完全分解为一次项之积：证明：证明：设 是n阶元素，即 。由定理3.4及推论知，n必为 的因子。令

25、 ，将 带入 ，得 ，所以 是 的根。mGF q012,mq11mqx11mqx10121 (2-5)mmqqxxxx k1nk1mq 1mn lq k11mqx 111110mqn lllkkk n k11mqx 定理定理2.6 扩域 上元素和的 幂次等于 幂次的和：（2-6）式中 是 域元素。定理定理2.7 如果是GF(q)上p次多项式f(x)的根，那么 的次幂也一定是f(x)的根。(1,2,)ljqllpmGF qlqlq11ikkqkiiiimGF q 定理定理2.8 GF(q)上的多项式 一定可以分解成若干最小多项式之积，即 (2-8)联系到费尔马定理，各最小多项式的次数不会超过m次

26、。次最小多项式必然有同一根系的 个共轭元作为其根。换言之，若 ，必有：(2-9)这里，本原元的共轭根系对应的最小多项式的次数等于m。综合式2-5、2-8、2-9可得下列关系式：（式2-10）11mqx 21121mkkiixxxxxilil degiixl 10122222liixxxxx degiixlm 10121211 mmkqqkiixxxxxxxx 定理定理2.9 若多项式 是既约多项式，则其反多项式 也是既约的。若多项式 是本原多项式，则其反多项式 也是本原的。若 是多项式 的根，则 必是其反多项式 的根。fx f x f x fx f x1 fx 综上所述，可以从多个角度来描述扩

27、域 的域元素，不同角度有不同的表示方法，使用不同的数学工具。从循环群的观点看，非零域元素写成 的形式，利用的数学工具是近世代数。这种表示有利于研究循环码。从多项式的观点看，域元素写成 的形式，利用的数学工具是代数学。这种表示有利于研究编、解码过程。从码字观点看，与元素写成一个m重 的形式。此m重也可以看成一个矢量或一个矩阵，于是可采用矢量代数、矩阵理论及线性空间为数学工具，有利于研究码的本质特性。mGF q0122,m1110mmfxf xf1110,mmffff2.3矢量空间 定义：对于数域（F，+）上n重有序元素的集合V，集合V在矢量加运算下构成加群（V，+）；矢量与标量的标乘封闭在V中，

28、即 分配律、结合律成立，即 则称矢量集合V是数域F上的n维矢量空间，也叫做n维线性空间。N维矢量也称为n重（n-tuples）。矢量空间中的矢量运算服从矢量运算法则，即若 矢量加 所得结果仍是矢量。标乘（标量乘矢积）所得结果是矢量。点积或内积（矢量乘矢量）所得结果是标量。12,1,iiiiinijVVVvvvvF jn,;iaFVa VVi i和和 V V,(),(),()().jijijiiiiia bFVVa VVaVaVab VaVbVab Va b Vi i和和V V1212,iiiinjjjjnVvvvVvvv及及a aF F,1122,ijijijinjnV Vvv vvvv12(

29、,),iiiinaVavavav1122,ijijijinjnV Vvvvvvv 1.线性组合线性组合 对于域F上的若干矢量 若满足 则称 是 的线性组合。2.线性相关线性相关 对于域F上的若干矢量 若满足 则称矢量 线性相关。如果上述条件不成立，称这些矢量线性无关或线性独立。从定义可以看到，只要线性相关的条件成立，就可以通过移项，将 中的仁一矢量表示为其他矢量的线性结合；相反，若一组矢量线性无关，则这组矢量的任一个都不能从其他矢量的线性组合生成。12,iV VVVk k及及V V1 122(),iijaVa VaV aFk kV Vk kV V12,iV VV12,iV VV V V1 12

30、20(),iijaVa VaVaF且且不不全全为为零零12,iV VV12,iV VV3.矢量空间的基底矢量空间的基底如果存在一组线性无关的矢量 这些矢量的线性组合的集合可构成一个矢量空间，则称这组矢量为这个矢量空间的基底。N维矢量空间包含n个基底，可以说，n个基底“张成”n维矢量空间。例例2.11 直角坐标系中的任何点可用一个二维矢量（x,y）来表示，其中 （实数域）。可以认为两维空间是有两个矢量（1，0）和（0，1）作为基底张成的，空间的仁一矢量可由这两个基底线性组合而成:（x，y）=x（1，0）+y（0，1）。也可以认为该两维空间是由两个矢量（-1，0）和（0，-1）作为基底张成的，他们

31、也可以组合出任何矢量:（x，y）=-x（-1，0）-y（0，-1）。可见，基地不是唯一的。把矢量元素中包含一个1而其余为0的那组基底称为自然基底，如前面的（1，0）和（0，1）。事实上，自然基底在保持正交的前提下任意缩放或旋转后仍是基底。12,kV VV,x yR 例例2.12 二元扩域 上的域元素 可一一对应到三维矢量 其自然基底是（100），（010）和（001）。由于每个系数只有0，1两种选择，自然基底只能组合出8个矢量，构成GF(2)上的三维矢量空间。3(2)GF221020(,(2)f xf xfff fGF20(,),ff f4.子空间若矢量空间 的一个元素子集 也能构成一个矢量空

32、间，称 是 的子空间。例例2.13 GF(2)上的三维矢量空间V的3各自然基底是(100)，(010)和(001)。若以其中一个或两个为基底，也能构成矢量空间，它们是三维矢量空间的子空间。比如：上例中的两个子空间包含了同一个矢量零矢量。事实上，任何子空间都包含零矢量，因为它是矢量加法的单位元。前面提到矢量空间时，n维空间的元素用一个n重来表示，维数和重数是一致的。引入子空间概念后，情况就不同了。比如，二维平面是2重矢量，但如果把该二维平面看成一个三维空间的一部分，平面上的矢量就应和三维空间其余部分的矢量一样，用一个3重来表达。sVsVVV 1100V=000,100 3 张成 以（）为基底子空

33、间一维 重空间 2V=000,001010011 3 张成以 010 和 001 为基底子空间，二维 重空间 这意味着子空间的引入使维数和重数可以不一样。从概念上讲，维数指线性空间基底的个数，重数指构成矢量的有序元素的个数，两者是不同的。比如例2.13中，子空间 是一维3重空间，是二维三重空间，是三维三重空间。维数不能大于重数；而当维数小于重数是，就说明是一个子空间。1V2VV5.矢量正交 1212V V0VV当两个矢量的点积为零,即，称和正交。6.矢量空间正交若某矢量空间中的任意元素与另一矢量空间中的任意元素正交，称这两个矢量空间正交。若两个矢量空间的基底正交，这两个矢量空间一定正交。7.对偶空间若n维矢量空间 中的两个子空间 和 正交，称 和 为对偶空间，其中一个空间是另一个空间的零空间（Null Space，也称零化空间）。在例2.13中，基底(100)与基底(010)和(001)均正交，因此子空间 和 一定正交，它们是对偶空间。1V1V1V2V2V2VnV