第二章纠错编码代数基础

第二章纠错编码代数基础2.1整数的有关概念2.2群的基本概念2.3环的基本概念2.4域的基本概念2.1整数的有关概念2.1.1整数的概念及性质2.1.2同余和剩余类2.1.3多项式2.1.1整数的概念及性质重述几个在编码中常用的概念。素数：只能被1和它本身整除的整数。合数：除1和自身外，还存在其他因数的整数。最大公约数（a，b）的性质：任意正整数a，b，必存在整数A，B，使（a，b）=Aa+Bb。最小公倍数[a，b]的性质：任意正整数a，b，必存在关系式ab=[a，b](a，b)。2.1.2同余和剩余类1.同余若两整数a，b被同一正整数d除时，有相同的余数，即则称a，b关于d同余，记作)0(,,21drrdqbrdqa][moddba2.剩余类模d运算余数相同的元素构成的集合为模d的剩余类，记为对应代表元常0，1，…d-1，共有d个值，称为有d个剩余类。剩余类之间也可定义加法和乘法运算：][mod][moddbabadbaba,1,1,0d例2-1d=7，则][mod1155353]7[mod32121d,1,1,0dD,,DbaDdba])[mod(Ddba])[mod(模d的全体剩余类对模d加法和模d乘法满足封闭性，即假设如果则必有以及。2.1.3多项式Fffxfxfxfxfinnnn,)(01111nfx)(xf系数取自集合F的多项式的表示形式为首一多项式：多项式最高次数是系数为1，即多项式的阶：多项式中系数不为0的的最高次数，既约多项式：阶大于0且在给定集合F上除了常数和常数与本身的乘积外，不能被其他多项式除尽的多项式。记为12x)(ix)(ix例2-2是阶为2的首一多项式，它在实数上是既约多项式，而在复数上不是既约多项式，因为在复数上可分解为两个因式和定理2-1给定任意两个多项式，，，一定存在唯一的多项式和，使称为模多项式，称为余式，记为。)(xf)(xp)()(xpxf)(xq)(xr)(xp)(xr)()()()(xrxpxqxf)()(0xpxr])()[mod(xpxf)(xr1.同余)()()()(1xrxpxqxa)()()()(2xrxpxqxb)()(0xpxr])()[mod()(xpxbxa若，，则。2.剩余类)(xp)(xr)(xr模运算余数相同的多项式集合，记为或多项式的剩余类具有与整数同样的性质。。1,01)(3xxxp)(xr3)(0xr0122)(rxrxrxr1,0,,210rrr1,,1,,1,,1,02222xxxxxxxx例2-3系数取自上的任意多项式以为模，设所得余式为则有，令，有，因此全体剩余类为1])()[mod1(])())[mod()1((222xxpxxxxpxxx1])()[mod(])())[mod()1((32xpxxxpxxx有2.2群的基本概念2.2.1群的定义2.2.2循环群2.2.3子群和陪集2.2.1群的定义定义1-1群G是一些元素构成的集合，该集合中定义一种运算“*”（加法或乘法），满足：1.封闭性，对任何a,bG，有abG2.结合律，对任何a,b,cG，(ab)c=a(bc)3.存在单位元eG，使对任何aG有ae=ea=a4.对任何aG有逆元a-1G，使aa-1=a-1a=e习惯上，若群的运算是加法，则简称加群；若群的运算是乘法，则简称乘群。例2-4整数集合对加法运算很明显满足封闭性和结合律，任何整数加0等于其自身，故加法单位元为0，任意一个整数x的逆元是其相反数-x，因此可判断全体整数构成加群。类似地，全体偶数、实数、复数也构成加群。另外，n阶方阵对加法运算也构成群，单位元是零矩阵。但对乘法来说，整数集合虽然满足封闭性和结合律，而且乘法单位元为1，但是由于除1和-1外，其他元素均无逆元，所以整数集合不能构成乘群。同样，因为元素0无逆元，故全体实数或复数集合也不能构成乘群。但如果把0排除掉，非0实数和非0复数集合在乘法运算下都是群，乘法单位是1，元素x的逆元为1/x。交换群如果“*”运算还满足交换律，即对任何a,bG，有ab=ba，则G称作交换群。加法群是交换群，而乘法群不一定是交换群，如矩阵乘法不满足交换律。群的阶群的阶就是群中所含元素的个数。如整数加法群和非0实数乘法群的阶都是无穷值。有限群阶为有限值的群称作有限群。例2-5模d的全体剩余类对模d的加法运算如表2-1所示从表看出，模d的全体剩余类对模d的加法运算满足封闭性、结合律和交换率，单位元为0，0的逆元为0，元素i的逆元为d-i，因此构成交换加群。该群的阶为d，是有限群。+01…d-2d-1001…d-2d-1112…d-10………………d-2d-2d-1…d-4d-3d-1d-10…d-3d-21,01)(3xxxp1,,1,,1,,1,02222xxxxxxxx同样，以p(x)为模的多项式的全体剩余类对模p(x)的加法运算也构成交换加群。例2-6集合上的任意多项式以为模，所得全体剩余类为该剩余类对模p(x)的加法运算如表2-2所示。例2-7模6的非0剩余类对模6乘法运算如表2-3所示。从表2-3看出，模6的非0剩余类对模6乘法运算中，单位元为1，元素2，3，4无逆元，因此不构成群。2.2.2循环群eenn|,,,120enn由元素的一切幂次所构成的群称为循环群。称为循环群的生成元。的最小正整数称为元素定义中幂次是相对于乘群而言的。元素使的阶。enne|)1(,2,,enn由生成元的一切倍次构成。循环加群中元素的阶是使的最小正整数。同样，可构成循环加群，循环加群mnnmnm所以循环群都是交换群。由于定理2-2交换群中的每一个元素都能生成一个循环群，元素的阶就是循环群的阶。例2-8模9的全体剩余类8,7,6,5,4,3,2,1,0在模9加法运算“*”下构成群，取生成元为2，则e02789725785236732156128458263462342222因而由2生成的循环加群为7,5,3,1,8,6,4,2,0该循环群和生成元2的阶都为9。66066660636663666,0,3再取生成元为6，则有生成的循环加群为该循环群和生成元6的阶都为3。元素阶的性质2.2.3子群和陪集1.子群的定义若群G的非空子集G′对于G中所定义的代数运算也构成群，则称G′为G的子群。例2-9偶数加群是整数加群的子群。一般来说，某一整数m的所有倍数所构成的集合是整数加群的子群。定理2-3有限群的子群的阶一定整除群的阶。例2-8中生成元6在模9加法运算下构成的群G′={0,3,6}是全体剩余类群G={0,1,2,3,4,5,6,7,8}的一个子群。G′的阶3整除G的阶9。2.群的陪集分解设G′为群G的非空子群，取hG，则称hG′为G′的左陪集，称G′h为G′的右陪集。当G是交换群时，子群G′的左、右陪集是相等的，元素h称作陪集首。设子群G′={g1,g2,…,gn}，G′的阶为n，又设为G′群G的子集，由定理2-3可知，若G的阶为nm，可将G完备地分成m个陪集（子群本身也是一个陪集）。陪集首的选择应注意(1)若陪集首h是子群G′中的元素，则陪集hG′与子群G′相同。(2)若陪集首h不是子群G′中的元素，则陪集hG′与子群G′相交为空集。(3)若陪集首hj不是陪集hiG′中的元素，则两陪集hiG′与hjG′相交为空集。(4)陪集hG′中的每一个元素都可作为其陪集首h，陪集元素不变，仅排列顺序改变。由以上性质可知，两个陪集要么相等要么不相交。为使群的分解完备，应选择前面未出现过的元素作为当前陪集的陪集首，这样，整个群将分解成若干个不相交的陪集，无一遗漏，无一重叠。2.3环的基本概念2.3.1环的定义2.3.2环的性质2.3.3子环2.3.4剩余类环2.3.1环的定义非空集合F中，若定义了加法和乘法两种运算，且满足：1.对加法运算是一个交换群，即满足封闭性、结合律、交换率、存在加法单位元和逆元；2.对乘法具有封闭性，即；aF，bF，有abF；3.满足分配律：对任何a,b,cF，有：a(b+c)=ab+ac(a+b)c=ac+bc(ab)c=a(bc)则称F是一个环。若环F对乘法满足交换率，即对任何元素aF和bF，恒有ab=ba则称此环为交换环。2.3.2环的性质000aaababba)()(根据环的定义，不难看出环具有如下的基本性质：对于任何aF，bF，有2.3.环中可以有零因子。1.4.有单位元且每个非零元素有逆元、非可换的环，称为除环。2.3.3子环设F是一个环，S是F的一个非空子集，若S对加法运算和乘法运算也构成一个环，则称S是F的一个子环，F是S的一个扩环。例2-13某一整数m的倍数全体，构成交换环，且是整数环的一个子环。,3,2,,0mmm2.3.4剩余类环剩余类环是一类重要的环，它是构成有限域的基础。以整数d为模进行除法运算所得的全体剩余类可构成环，称作整数剩余类环。如表2-1所示，模d的全体剩余类F={0,1,…,d-1}对模d加法运算构成交换加群；显然集合F对模d乘法运算满足封闭性、结合律、交换率；对于集合F来说，有])[mod(])[mod(])[mod(][mod)(dacabdcbadbcacdcba说明集合F还满足分配率，因此模d的全体剩余类构成交换环。同理，模p(x)的全体余式对模p(x)的运算构成交换环，称作多项式剩余类环2.4域的基本概念2.4.1域的定义2.4.2有限域的本原元2.4.3二元域的运算2.4.1域的定义1.域的定义域是一些元素构成的集合，该集合中定义加法和乘法两种运算，满足：（1）对加法构成交换加群；（2）非零元素全体对乘法构成交换乘群；（3）加法和乘法间具有分配律a(b+c)=ab+ac，(a+b)c=ac+bc由定义可知，域是一个可换的、有单位元的、非零元素有逆元的环。域比环多三个条件，即乘法满足交换率、存在乘法单位元、非零元素有乘法逆元。1nx12mn1nx域的阶域中元素的个数。有限域元素个数有限的域，用GF(q)表示q阶有限域。有限域，又称为伽罗瓦（Galois）域。（特别是）因式分解，而由剩余类理论基础。纠错码理论中经常需要将多项式构成的有限域是多项式因式分解的定理2-4设d为素数，则以d为模的整数剩余类环构成d阶有限域GF(d)。例2-15d=2构成域GF(2)=｛0，1｝，d=5构成域GF(5)=｛0，1，2，3，4｝。由表2-1已知以任意整数d为模的全体剩余类对对模d加法构成交换加群，因此这里只列出乘法运算。定理2-5设p(x)为系数取自GF(q)上的n次既约多项式，则以p(x)为模的多项式剩余类环构成qn阶有限域GF(qn)。1,0)2(GF1)(3xxxp1,,1,,1,,1,0)2(22223xxxxxxxxGF例2-16系数取自的全体多项式集合用模除，所得余式构成有限域其加法运算见表2-2，乘法运算见表2-6。2.4.2有限域1qeq11q1.有限域的本原元域中全体非零元素构成交换乘群，由定理可知，该乘群中每一个元素都能生成循环群，但各元素阶不一定相等。即(是使等式成立的最小正整数)本原元多项式是以本原元为根的既约多项式。本原元在GF(q)中，某一元素的阶为则称为本原元。2.4.3二元域的运算)2(GF)1(n011222211)(fxfxfxfxfxfxfnnnnnn