编码理论第2章

编码理论第二章数学基础李丽香二元运算定义：设G是一个集合，G上的二元运算*是这样的规则，它对G中的每对元素a,b，在G中指定第三个唯一元素c=a*b例如：加法是实数域中的二元运算，乘法也是集合在二元运算*之下是封闭的：如果a,b∈G,那么a*b∈G二元运算*是结合的：a*(b*c)=(a*b)*c群的定义定义：一个集合G，在其上定义了一个二元运算*，若它满足以下条件称为群满足封闭性，即对G中任意两个元素a,b,有a*b∈G二元运算*满足结合律G中存在一个元素e，称为恒元或单位元，使得G中任何元素，有a*e=e*a=a对于G中任何一个元素a，G中存在另一个元素，称作a的逆元，使得aeaaaa交换群：若群G的二元运算*还满足，对G中任意的元素a和b有a*b=b*a,那么称此群是可交换的，或称为阿贝尔群群的例子例1：全体整数集合在实数加法运算下构成可交换群，整数0为恒元，整数-a是整数a的逆元。全体整数集合对乘法不构成群，因为不存在乘法逆元例2：除0以外的所有有理数集合，在实数乘法下是一个交换群例3：全体除0以外的有理数集合，在实数乘法下是一个交换群例4：全体实数集合对加法构成交换群，单位元是0，a的逆元是-a。全体除0以外的实数集合对乘法运算构成交换群，单位元是1，逆元是1/a群的例子例5：全体n阶方阵集合对矩阵加法构成交换群，单位元是零矩阵；全体非奇异的n阶矩阵集合对矩阵乘法构成交换群，单位元是n阶单位矩阵例6：集合{0,1}对模2加运算构成交换群，单位元是0，元素1的逆元是1例7：集合{0,1,...,m-1}对模m加运算构成交换群例8：集合{0,1,...,p-1},p为素数，对模p乘法构成交换群；如果p不是素数，该集合不是群群的性质阶的定义：群中元素的个数称为群的阶有限群：有限阶的群；反之就是无限群定理1：群G的恒元是唯一的证明：假定G中有两个的恒元e和，则有证毕定理2：任何一个群元素的逆元是唯一的证明：假定元素a有两个逆元，则证毕eeeeeaa,aaeaaaaaaeaa群的性质定理3：若a,b∈G，则证明：所以a*b和互为逆元定理4：给定G中任意两个元素a和b，则方程a*x=b和y*a=b在G中有唯一解证明：方程a*x=b的解是x=a-1*b，这是因为a*a-1*b=e*b=b，同理，y*a=b的解是y=b*a-1。下面证明解的唯一性。如果在方程a*x=b中，除了x=a-1*b，还有另外一个解x1，使a*x1=b,则把该式两边左乘以a的逆元a-1，则有a-1*a*x1=a-1*b，由此可得e*x1=x1=a-1*b。同理，可证方程y*a=b的解的唯一性111abba11abeaaabbaabba11111循环群定义：若存在a∈G是一个集合，使得G中的每个元素都是a的某次幂，即an(n是整数)，则称G是循环群生成元：该循环群由a生成，a是该群的生成元例1：全体整数集合关于加法构成循环群，1是生成元，因为该群有无限多个元素，故称为无限循环群例2：在乘法下是一个交换循环群，该群只有3个元素，该群是有限循环群，1是乘法单位元，其中代表虚数单位,1,,,10233/423/210aeaeaeaaiii1i循环群的性质定义：使an=1的最小正整数n称为元素a的阶(注意将元素的阶和群的阶要分开)性质1：若a是n阶元素，则群G中的n个元素a0=1,a1,…,an-1互不相同性质2：若a是n阶元素，则由a的一切幂次生成的元素都在群G中性质3：若a是n阶元素，则am=1的充要条件是n|m性质4：若a,b∈G，a是n阶元素，b是m阶元素，且(n,m)=1,则ab的阶是nm,(n,m)表示n和m的最大公因数循环群的性质性质5：若a是n阶元素，则ai元素的阶为n/(i,n)性质6：若a是mn阶元素，则am元素的阶为n性质7：在n阶循环群中，每个元素的阶都是群阶数n的因子例如：设a的阶为63，a7的阶为m，a9的阶为k，根据性质5，有m=63/(63,7)=9,k=63/(63,9)=7;令b1=a7,b2=a9，而(7,9)=1,根据性质4，b1b2的阶为63循环群的生成元根据性质5，群G中的每个元素ai的阶为n/(i,n),若(i,n)=1,则元素ai的阶为n，即ai的全部幂次也可生成该循环群的全部元素定义：循环群G中的每个元素都是某个元素a∈G的幂次的形式，此时称该群由a生成，a是该群的生成元环的定义定义：非空元素集合R中，定义了两种二元运算，称作加法和乘法，这样的代数系统(R,+,·)称为一个环，若它满足以下条件R中全体元素在加法下构成交换群，单位元为0，逆元记为-a乘法运算满足封闭性满足乘法结合率，即(a·b)·c=a·(b·c)，加法和乘法之间满足分配律a·(b+c)=a·b+a·c,(b+c)·a=b·a+c·a,,,,RcbaRcba,,交换环：若环关于乘法满足交换律，即对任意的a,b∈R,都有a·b=b·a环的例子例1：全体整数集合在实数加法和乘法运算下构成交换环例2：所有元素为实数的全体n阶方阵集合，对矩阵加法和乘法构成环例3：集合{0,1,...,n-1}在模n的加法运算和乘法运算下，构成交换环例4：全体实数多项式集合构成环例5：全体偶数集合构成环域的定义定义：非空元素集合F中，定义了两种二元运算，称作加法和乘法，这样的代数系统(F,+,·)称为一个域，若它满足以下条件F中全体元素在加法下构成交换群，恒元为0F中非零元素在乘法下为交换群，恒元为1加法和乘法之间满足分配律(a+b)·c=a·c+b·cFa,b,c从域的定义可以看出：一个域中至少包含2个元素0和1。元素a的加法逆元用-a表示，其乘法逆元用a-1表示域的性质性质1：对域中的任意元素a，有a·0=0·a=0证明：a=a·1=a·(1+0)=a+a·0,该式左右两边同时左加上-a，得到-a+a=-a+(a+a·0),推出0=0+a·0，即a·0=0;同理可证0·a=0，证毕性质2：若a,b非零，则a·b≠0性质3：若a·b=0且a≠0，则b=0(性质2的推论)性质4：-(a·b)=-a·b=a·(-b)证明提示：0=0·b=(a+(-a))·b=ab+(-a)·b性质5：若a≠0，a·b=a·c，则b=c证明提示：用a-1左乘两边即可域的例子阶：域中元素的个数有限域：阶为有限的域，也称为Galois(伽罗华)域例1：二元集合{0,1}对模2加法和模2乘法构成一个域，记为GF(2)例2：令p为素数。考虑模p加法和模p乘法，则集合{0,1,…,p-1}构成一个p元有限域，也称为素域,记为GF(p)例3：全体有理数集合、全体实数集合、全体复数集合在加法和乘法运算下，构成域，它们都是无限域有限域的扩域从域的例子2可看出，对任何素数p都存在一个p阶有限域扩域的定义：对任何正整数m，可以将素域GF(p)扩展为有pm个元素的域，称为GF(p)的扩域，记为GF(pm)。称GF(p)为GF(pm)的基域。此外已经证明：任何有限域的阶都是素数的幂次有限域的特征：设F是域，0和e是加法和乘法的单位元，若对任意正整数n，都有ne≠0，则称域F的特征是0；若有正整数n，使ne=0，则称使ne=0成立的最小正整数n为域F的特征。域的特征或是0，或是有限的素数有限域的特征在域中必有乘法单位元1，若做1+1+…+1运算，对于无限域，则有可能n·1≠0，但在有限域中，必存在1+1+…+1=0，否则该域必成无限域，例如，在GF(2)中，1+1=0GF(2)的特征是2；若p为素数，GF(p)的特征是p定理：在特征为p的域中，若a是域中的任意元素，则均有pa=0证明：若a≠0，则pa=a+a+…+a=1·a+1·a+…+1·a=(1+1+…+1)·a=p·1·a=0·a=0，定理成立；若a=0，定理显然成立。证毕有限域的性质定理1：有限域的特征n是素数证明：设n≠0，假设n不是素数，即n=n1n2,1n1n,1n2n,于是0=ne=(n1n2)e=(n1e)(n2e),因此n1e=0或者n2e=0，但这与n的最小性相矛盾，所以n只能是素数。对于任意有限域，由于其只有有限个元素，所以其特征不可能为0，从而其特征一定为素数。有限域的性质定理2：设a是有限域GF(q)的非零元素，则aq-1=1证明：令b1,b2,…,bq-1为GF(q)的q-1个非零元素，显然q-1个非零元素ab1,ab2,…,abq-1非零且互不相同，因此(ab1)·(ab2)·…·(abq-1)=b1·b2·…·bq-1所以aq-1(b1·b2·…·bq-1)=b1·b2·…·bq-1即有aq-1=1有限域的性质定理3：设a是有限域GF(q)的非零元素，令n是a的阶，则q-1能被n整除，即n|(q-1)证明：假设q-1不能被n整除，则q-1=kn+r,其中0rn，于是aq-1=akn+r=aknar=(an)kar=ar,根据aq-1=1，an=1，推出ar=1，这与n的定义矛盾，所以q-1必能被n整除。证毕有限域的阶：设a是有限域GF(q)的非零元素，因为aq-1=1，所以有限域的阶是q-1有限域的阶定理1：有限域GF(q)的阶是q-1或者是q-1的约数定理2：GF(q)中每个非零元素是xq-1-1=0的根，反之，xq-1-1=0的根必在GF(q)中证明：q-1次方程至多q-1个根。因为GF(q)中q-1个非零元素构成循环乘群，它由级为q-1的本原元a的所有次幂生成，即1,a,a2,…,aq-2，对本原元有aq-1=1，所以对于GF(q)中的每个元素ai，我们有(ai)q-1=(aq-1)i=1,i=0,1,…,q-2，所以GF(q)中每个非零元素是xq-1-1=0的根。反之，如果b是方程xq-1-1=0的根，则bq-1=1，因此b必是由GF(q)中的本原元的幂次，即b是GF(q)中的元素。有限域的特征定理1：在特征为p的域中，若a是域中的任意元素，则有pa=0证明：若a≠0，则有pa=a+a+…+a=1·a+1·a+…+1·a=(1+1+…+1)·a=p·1·a=0·a=0，定理成立；若a=0，定理也成立。证毕。定理2：在特征为p的域中，若a是域中的任意元素，则有(x-a)p=xp-ap证明：由二项式定理知其中已知p为素数，当k=1,2,…,p-1时，(k!,p)=1，由上式知含有素因子p，记，由于域的特征是p，故，所以(x-a)p=xp+(-a)p=xp-appkkpkpkpxaCax0!11!!!kkpppkpkpCpk1pnCpk0][11kkkpkapnapnaCpkC有限域的特征推论1：在特征为p的域中，若a,b是域中的元素，则(a±b)p=ap+bp推论2：若k为p特征域GF(pm)中的域整数，则有证明：推论3：对GF(pm)中的任意域元素a，恒有证明：GF(pm)中的任意域元素都是的根，所以,...2,1nkknpkkkkikippkippnnnn1111111aamp011mpxaaammpp1101有限域的特征定理：在p特征域中，元素为域整数的充要条件是，该元素是xp-1-1=0的根证明：若k为特征域GF(q)中的域整数，根据上一页ppt的推论3，可知kp=k,kp-k=0,kp-1-1=0，因此k是方程xp-1-1=0的根，反知，若k是方程xp-1-1=0的根，则kp-1-1=0，由第20页ppt的定理2可知，它必在域GF(q)中本原元本原元：在有限域GF(q)中，若非零元素a的阶为q-1，则称之为