纠错码近世代数

纠错码近世代数2整数得基本概念素数:一个大于1得正整数,只能被1和她本身整除,而不能被其她整数整除,这样得正整数叫做素数(或质数)

例如:2,3,5,7,11,17,19,…都就是素数,共有∞多个合数:一个正整数除了能被1和本身整除以外,还能被另外得正整数整除,这样得正整数叫做合数

例如:4,6,8,9…都就是合数,也有∞多个整数得基本概念倍数、因数:设a、b就是整数,b≠0,如果有一个整数c,使得a=bc,则a叫做b得倍数,b叫做a得因数或约数素因数:如果一个正整数a有一个因数b,而b又就是素数,则b就是a得素因数

例如:30=5×6,5就是素数,所以5就是30得素因数,

而6不就是30得素因数3整数得初等运算及性质整数可做加、减、乘、除四则运算,对加、乘有如下性质封闭性,对所有整数a、b、c、d有a+b=c,ab=d结合,a+(b+c)=(a+b)+c,a·(b·c)=(a·b)·c加法有恒等元0,即:0+a=a加法有逆元,对任意整数a,存在逆元-a,使(-a)+a=0乘法消去律,对任意整数a、b、c,若c≠0,则由

ac=bc,可得a=b乘法单位元1,即对任意整数a,有1·a=a4整数得初等运算及性质分配律,a·(b+c)=a·b+a·c交换律,a+b=b+a,a·b=b·a此外还满足以下三条逻辑规则:自反律,a=a对称律,若a=b,则b=a传递律,若a=b,b=c,则a=c欧几里德除法:设b就是正整数,则任意正整数a>b皆可唯一表示成

a=qb+r,0≤r<b5最大公约数与欧几里德算法最大公约数:同时除尽a,b,…,l(不全为0)得正整数,称为a,b,…,l得公约数,其中得最大者称为最大公约数,用(

a,b,…,l

)或GCD(

a,b,…,l

)表示。若(

a,b,…,l

)=1,则称a,b,…,l互素。定理:给定两整数a、b且a>b,若a=bq+r,则

(a,b)=(b,r)

6最大公约数与欧几里德算法例子

求(150,42)=？解:由欧几里德除法知:150=3×42+24

0<24<4242=1×24+180<18<2424=1×18+60<6<18

18=3×6由以上定理知:(150,42)=(42,24)=(24,18)=(18,6)=6

7最大公约数与欧几里德算法欧几里德算法:给定任意正整数a、b,必有整数A、B使(a,b)=Aa+Bb例如,(150,42)=2·150+(-7)·42最小公倍数:设a、b为任意两个正整数,若有一整数M使a|M、b|M,则称M就是a、b得公倍数,其中最小得正公倍数称为最小公倍数,记为[a,b]或LCM(a,b)8最小公倍数及性质性质:a、b、c若两两互素,则[a,b,c]=abca、b得最小公倍数除尽a、b得一切公倍数,若m就是a、b得公倍数,则[a,b]|m,故m=q[a,b]若a、b得最大公约数就是(a,b),最小公倍数就是[a,b],则ab=[a,b](a,b)9例子求[24871,3468]=?解:先利用欧几里德除法求(24871,3468):24871=3468×7+5953468=595×5+493595=493+102493=102×4+85102=85+1785=17×5故(24871,3468)=17,利用性质3得[24871,3468]=(24871×3468)/17=507368410最小公倍数及性质同余和剩余类同余若整数a和b被同一正整数m除时,有相同得余数,则称a、b关于模m同余,记为若则剩余类给定正整数m,将全体整数按余数相同进行分类,可获得m个剩余类:例子254(mod7);125(mod7);25×12=3006(mod7)4×5(mod7)

m=3

11大家有疑问的，可以询问和交流可以互相讨论下，但要小声点群满足一定规律或定律得系统称为代数系统,且该系统有:有一群元素a,b,c,…构成一个集合;在元素集合中有一等价关系;在集合中定义了一个或数个运算,通过运算建立起元素之间得关系;有一组假定。假设A和Ｂ就是两个集合,如果存在某个对应法则φ,使对任一都能唯一确定B中一个元素b与之对应,则称φ就是A到B得一个单值映射,记为φ:a→b或φ(a)=b假设φ就是集合A到B得单值映射,如果对任一bB,必然存在使b=φ(a),则称φ就是A到B得满射,或说φ就是A到B上得映射。13群如果对集合A中不同得元素,在φ之下在集合B上有不同得像,即当且仅当a1=a2时,φ(a1)=φ(a2),则称φ就是A到B得单射。若φ既就是满射又就是单射,则称为双射或者一一对应。设φ就是集合A到A自身得映射,则称φ就是A中得变换。A到A得满射称为满变换,单射称为单变换,一一映射称为一一变换或置换。若有一种变化ω保持A中任一元素不变,即ω(a)=a,则称这种变换为恒等变换或恒等置换。设φ就是集合A到B得映射,如果她满足条件

φ(a1ºa2)=φ(a1)ºφ(a2)a1,a2A,φ(a1),φ(a2)B,

则称φ就是A到B得同态映射,集合A与B同态。如果同态映射φ又就是双射,称为同构映射,集合A与B同构,若φ就是A到自身得同构映射,则称为自同构。14群例子:(R,＋)和(R+,×),这里＋,×分别为数得加法和乘法。规定映射f:RR+为f(x)=10x,则f就是RR+得同构映射。Proof:对于任何y

∈R+,存在x=lgy使f(x)=y,所以f就是RR+得满射;对任意得x,y∈R,如果10x=10y

,得x=y,所以f为RR+得单射。因此f就是RR+得双射。又由于f(x＋y)=

10x+y=10x×10y=f(x)×f(y),所以f就是R到R+得同构映射。整数集合与剩余类集合之间仅就是同态映射(SeeSlide-5)15群设(Z,+)和(A,×),这里A={1,-1},规定映射f:ZA为对任何x∈Z,

证明:f就是ZA得同态映射Proof:对于任何x,y∈Z如果x,y都就是偶数,则f(x)=1,f(y)=1,于就是

f(x+y)=1=1×1=f(x)×f(y)(2)如果x,y都就是奇数,则f(x)=-1,f(y)=-1,于就是

f(x+y)=1=(-1)×(-1)=f(x)×f(y)(3)如果x就是奇数,y就是偶数,则f(x)=-1,f(y)=1,于就是

f(x+y)=-1=(-1)×1=f(x)×f(y)同理可证:x就是偶数,y就是奇数时,f(x+y)=f(x)×f(y)。因此,f就是ZA得同态映射。QED16群设有理数集Q,代数运算为数得加法,Q*为非零有理数集,代数运算为数得乘法,证明:(Q,+)与(Q*,×)不存在同构映射。Proof(反证法):假定QQ*存在同构映射f,并令f(0)=x∈Q*、再令f(x)=x‘≠0,于就是

f(0+x)=f(0)×f(x)=x×x’

f(x)=x×x’

x’=x×x’

x=1

f(0)=1

但另一方面,设f(a)=-1f(a+a)=(-1)×(-1)=1,但f(0)=1,所以a+a=0a=0,于就是又有f(0)=-1,这与f就是QQ*得双射矛盾。因此,Q与Q*不存在同构映射。QED17群得定义设G就是一个非空集合,并在G内定义了一种代数运算“。”,若满足:

则称G构成一个群。若加法,恒等元用0表示,若为乘法,恒等元称为单位元1)封闭性。对任意,恒有2)结合律。对任意,恒有3)G中存在一恒等元e,对任意,使4)对任意,存在a得逆元,使18群实例例子全体整数:对加法构成群;对乘法不构成群全体偶数:对加法构成群;对乘法不构成群全体实数:对加法构成群;对乘法构成群(除0元素)全体复数:对加法构成群;对乘法构成群(除0元素)全体有理数:对加法构成群;对乘法构成群(除0元素)模m得全体剩余类:对模m加法构成群;对模m乘法,除0外,根据m值不同有不同得结论。如m=4时,剩余类中得元素得逆元不存在。如对模m=3乘法,除0外,剩余类全体构成群。19群实例设G={1,-1,i,-i},×为数得乘法,则(G,×)就是一个交换群。因为,G中任意两个元得乘积还就是G得一个元。于就是,G在×下就是封闭得。数得乘法总就是满足结合律和交换律。G得单位元为1,且(-1)-1=-1,i-1=-i,(-i)-1=i。(S={1,2,3,4,6,12},GCD)就是群吗？任给a,b,c∈S,GCD(a,b)∈S,所以S对GCD就是封闭得

GCD[GCD(a,b),c]=GCD[a,

GCD(b,c)]

满足结合律。因为GCD(12,a)=a,所以S得单位元为12。因为GCD(1,a)=1≠12,所以1没有逆元。因此,(S,GCD)不就是群。20群性质群得恒等元、每个元素得逆元都就是唯一得。Proof:反证法若a,b∈G,则(a。b)-1=b-1。a-1。Proof:直接代换给定G中任意两个元素a和b

,方程a。x=b和y。a=b在G中有唯一解:x=a-1。b,y=b

。a-1群G中消去律成立。即由a。x=a。

y

x=y21群得相关概念群得阶(OrderofaGroup)有限群(FiniteGroup)、无限群(InfiniteGroup)加群、乘群阿贝尔群(AbelianGroup)、可换群、交换群:满足交换律所有n阶满秩矩阵得全体对矩阵乘法构成得群为非阿贝尔群半群(Semigroup)(满足前两个条件)如正整数在加法运算下构成一个半群(无恒等元)弱群(Monoid)(满足前三个条件)整数在乘法运算下构成一个Monoid(无逆元)对称群(SymmetricGroup)由n个元素构成得集合A到自身得所有n!个置换构成得集合在置换运算下构成对称群。22置换群置换群(PermutationGroup)例子:A={1,2,3}置换群不一定就是对称群;对称群一定就是置换群在置换运算下构成置换群为单位元互为逆元23置换

3719850

9570813

3870195φ1=(1,3,5,6,2,7,4)φ2=(4,6,2,7,5,3,1)24对称群定义n个元素组成得集合A={1,2,…,n}到自身得所有置换有n！个,这n个置换组成得集合Sn在置换运算下就是一个n！有限群,称为对称群。3个元素得对称群:25环得定义非空集合R中,若定义了两种代数运算加和乘,且满足:1)集合R在加法运算下构成阿贝尔群2)乘法有封闭性3)乘法结合律成立,且加和乘之间有分配律环＝阿贝尔加群＋乘法半群例子全体整数;全体偶数;实系数多项式全体均构成环模整数m得全体剩余类构成剩余类环相关概念有单位元环(乘法有单位元)交换环(乘法满足交换率)26环得相关概念有零因子环对于环中得两个非零元素a和b,若她们在环上定义得乘法运算下为零,即ab=0,则a、b为零因子,对应得环为有零因子环。乘法消去率不成立例:Z6:2×3=6=0(mod6);2×3=0×3(mod6)but2≠0整环(无零因子环)乘法消去率成立例:Z5除环有单位元、每个非零元素有逆元,非可换得环例如所有n阶实数满秩矩阵全体和全零矩阵构成除环27环R={a+b51/2|a,b∈Z}关于数得加法和乘法就是否构成环？任给p,q∈R,p=a1+b151/2,q=a2+b251/2,a1,b1

,a2,b2∈Z、

p+q=(a1+b151/2)+(a2+b251/2)=(a1+a2

)

+(b151/2

+b251/2)∈R

pq=(a1+b151/2)(a2+b251/2)=(a1a2+5b1b2

)

+(a1b2

+

a2b1)

51/2∈R

显然,(R,+)就是加群,(R,×)就是半群且乘法对加法满足分配律,所以(R,+,×)就是环。28域定义:非空集合F,若F中定义了加和乘两种运算,且满足:1)F关于加法构成阿贝尔群,加法恒等元记为02)F中所有非零元素对乘法构成阿贝尔群,乘法恒等元记为13)加法和乘法之间满足分配律域就是一个可换得、有单位元、非零元素有逆元得环,且域中一定无零因子。有理数域;实数域;复数域。元素个数无限得域称为无限域;元素个数有限得域称为有限域,用GF(q)或Fq表示q阶有限域。有限域也称为伽逻华域。29域设p为素数,则整数全体关于模p得剩余类在模p得运算下(模p加和乘)构成p阶域GF(p)Proof:(只需证非0元素有逆元)。其中1为单位元,因为p为素数,因此任意小于p得数a和p互素。所以由Euclidean算法可知:

(a,p)=1=Aa+Bp

在等式两边对p取模,则