信道编码-代数基础

1、第二章 代数基础 一、整数的一些基本性质 n基本概念 n素数 n合数 n因数（约数） 素因数 公约数 最大公约数（greatest common divisor) a,b的最大公约数记为的最大公约数记为GCD(a,b) 或或(a,b) n最小公倍数 (least common multiple） a,b的最小公倍数记为的最小公倍数记为LCM(a,b) 或或 a,b n 整数的初等运算及性质 加、减、乘、除 定理1。任何正整数a均可唯一地分解为素因数的积。 a=p1r1p2r2pnrn (p1、p2 、 pn素数， r1、r2、rn为正整数） 水浒 天罡星：3622 32 地煞星：7223 32

2、 好汉： 10822 32 + 23 32 = 22 32（12） 22 33 3. 欧几里德除法（求最大公约数） 定理2（欧几里德除法）：设b是正整数，则任意大于b的正整数a 可唯一地表示为： a=qb+r 0r b, 设a=bq+r, 则(a,b)=(b,r)。 解释：利用欧几里德除法求最大公约数。 例2.1. 求(150,42) 150=342+24 42=24+18 24=18+6 18=3 6 (150,42)=(42,24)=(24,18)=(18,6)=6 求（a,b,c)=(a,b),c) 4. 欧几里德算法 定理4：给定任意a、b， (a,b)=Aa+Bb, (A、B为整数）

3、。 解释：两个正整数的最大公约数可表示为它们的线性组合。 如何求？ (150,42) 150=342+24 42=24+18 24=18+6 18=3 6 (150,42)=(42,24)=(24,18)=(18,6)=6 （150，42）=24-18=24-（42-24）=2 24-42 =2 (150-3 42)-42 =2 (150-3 42)-42 = 2 150- 7 42 5. 最小公倍数(1) n法1（利用定理1）：把a、b分解为素因子，取不同素因子最高 次幂的积。 198，240，360 198=2 32 11 240=2 43 5 360=2 332 5 198，240，36

4、0=2 432115 =7920 n法2. I.求两个正整数的GCM 定理5：若a、b为正整数，a,b=ab/(a,b) 5. 最小公倍数(2) 求：24871,3468 II. 求两个以上正整数的GCM a,b,c = a,b,c 求：198,240,360 6. 同余和剩余类 同余(余数相同）：a、b、m为正整数，由欧几理德除法，a,b可 唯一地表示为： a=q1m + r1 b=q2m + r2 若r1=r2,则称a,b关于模m同余，记为ab(mod m) 6. 同余和剩余类(2) n模m的剩余类（同余）：全体整数按模m同余的分为一类， 共有m类，称为模m的同余或剩余类，记为： 1 .,

5、 , 1 0m， 或或0，1， , m-1 定义：定义：a+b=a+ba+b=a+b a.b=a.b a.b=a.b 定理定理6：若若a1 b1(mod m), a2 b2(mod m), 则则 （1）a1+a2 b1+b2 (mod m); (2) a1.a2 b1.b2 (mod m). a1 a2 b1 b2 a1+a2 b1+b2 同余同余 二、代数系统 1. 映射 ：A - B 单射、满射、双射（一一对应映射） 2. 2. 变换：变换：A=BA=B的映射（到自身的映射）的映射（到自身的映射） 单变换变换、满变换变换、一一变换变换( (置换置换) )、恒等变换（、恒等变换（ a a A

6、:A: (a)=a )(a)=a ) 3. 同态与同构 同态：若映射：A - B满足条件：a1,a2A: (a1a2)=(a1) * (a2)，则 称为A到B的同态映射，其中 ,*分别为集合A和B的运算。称A与B同态。 同构：若同态映射为双射（课本有错），则称为同构映射，称A与B同构。 a1 a2 (a1) a1 a2 AB (a2) (a1) * (a2) a3b a1 a2 (a1) a1 a2 AB (a2) (a1) * (a2) 同态同态同构同构 三、群 Group 只有一种运算的代数系统只有一种运算的代数系统 定义：定义：设设G是非空集合，并在是非空集合，并在G定义了一种代数运算定

7、义了一种代数运算“ ” ，若下述公理，若下述公理 成立，则称成立，则称G为群，记为为群，记为(G, ）：）： (1) 满足封闭性：满足封闭性： a,b G:a b G; (2) 结合律成立：结合律成立： a,b G: （a b） c = a ( b c) ; (3) 存在恒等元：存在恒等元： e G: a G: a e =e a =a; (4) 每一元素存在逆元：每一元素存在逆元： a G: a-1 G: a a-1=a-1 a=e. 群的群的阶阶：|G| 有限群有限群： |G| 无限群无限群： |G|= 阿贝尔群、交换群阿贝尔群、交换群： a,b G: a b=b a. 例：例：全体整数对于

8、加法构成群，对乘法不构成群。全体整数对于加法构成群，对乘法不构成群。 全体偶数对于加法构成群，对乘法不构成群。全体偶数对于加法构成群，对乘法不构成群。 全体实数全体实数R对于加法构成群，对乘法不构成群，但对于加法构成群，对乘法不构成群，但R-0对乘法构成群。对乘法构成群。 恒恒 等等 元元 为为 0 1.群的定义（2） 全体矩阵对矩阵加法构成群，恒等元为零矩阵。全体矩阵对矩阵加法构成群，恒等元为零矩阵。 满秩矩阵对矩阵乘法构成群，满秩矩阵对矩阵乘法构成群，恒等恒等元为单位矩阵。元为单位矩阵。 模m的同余全体0，1，, m-1在模m加法运算下构成群。 -n = m-n A=1,2,3 置换1,

9、2, 3定义为： 2 1 3 3 2 1 1 3 2 3 2 1 3 2 1 3 2 1 321 ， ， ：， ， ， ：， ， ， ： 定义 为置换的复合，即1 2(a)= 1( 2(a),则 S=1, 2, 3对 构成群，称为置换群。 3 1 2 3 2 1 1 2 3 3 2 1 2 3 1 3 2 1 324 ， ， ：， ， ， ：， ， ， ： 3!=6, 定义定义 ，则S3=1, 2, 3, 4, 5, 6 对 构成群，称为对称群（定义2.2.11) 历史上人们很早就已经知道了一元一次和一元二次方程的求解方法。关于三次方程， 我国在公元七世纪，也已经得到了一般的近似解法，这在唐朝

10、数学家王孝通所编的 缉古算经就有叙述。到了十三世纪，宋代数学家秦九韶在他所著的数书九章 的“正负开方术”里，充分研究了数字高次方程的求正根法，也就是说，秦九韶那时 候已得到了高次方程的一般解法。 在西方，直到十六世纪初的文艺复兴时期，才由意大利的数学家发现一元三次方程解 的公式卡当公式。在数学史上，相传这个公式是意大利数学家塔塔里亚首先得到 的,后来被米兰地区的数学家卡尔达诺(15011576年)骗到了这个三次方程的解的公 式，并发表在自己的著作里。所以现在人们还是叫这个公式为卡尔达诺公式(或称卡 当公式)，其实，它应该叫塔塔里亚公式。 三次方程被解出来后，一般的四次方程很快就被意大利的费拉里

11、(15221560年)解 出。这就很自然的促使数学家们继续努力寻求五次及五次以上的高次方程的解法。遗 憾的是这个问题虽然耗费了许多数学家的时间和精力，但一直持续了长达三个多世纪， 都没有解决。法国数学家拉格朗日更是称这一问题是在“向人类的智慧挑战”。 1770年，拉格朗日精心分析了二次、三次、四次方程根式解的结构之后，提出了方程 的预解式概念，并且还进一步看出预解式和方程的各个根在排列置换下的形式不变性 有关，这时他认识到求解一般五次方程的代数方法可能不存在。此后，挪威数学家阿 贝尔利用置换群的理论，给出了高于四次的一般代数方程不存在代数解的证明。 伽罗华通过改进数学大师拉格朗日的思想，即设法

12、绕过拉氏预解式，但又从拉 格朗日那里继承了问题转化的思想，即把预解式的构成同置换群联系起来的思 想，并在阿贝尔研究的基础上，进一步发展了他的思想，把全部问题转化或归 结为置换群及其子群结构的分析。 这个理论的大意是：每个方程对应于一个域，即含有方程全部根的域，称为这 方程的伽罗华域，这个域对应一个群，即这个方程根的置换群，称为这方程的 伽罗华群。伽罗华域的子域和伽罗华群的子群有一一对应关系, 这样，伽罗华 把代数方程可解性问题转化为与方程相关的置换群及其子群性质的分析问题， 这就是伽罗华工作的重大突破。对于任一个取有理数值的关于根的多项式函数， 伽罗华群中的每个置换都使该函数的值不变。反过来，

13、如果伽罗华群中的每个 置换都使一个根的多项式函数的值不变，则这多项式函数的值是有理的。因此 一个方程的伽罗华群完全体现了他的根（整体）的对称性。伽罗华的工作主要 基于两篇论文“关于方程根式解的条件”和“用根式求解的本原方程”。在 这些论文中，伽罗华将其理论应用于代数方程的可解性问题，由此引入了群论 的一系列重要概念。在关于方程代数解法论文的分析中，伽罗华提出了一 个重要定理（未加证明）：一个素数次方程可用根式求解的充要条件是这个方 程的每个根都是其中两个根的有理函数。伽罗华用它判别特殊类型方程的根式 解问题。 2. 群的性质 定理7：群(G, ）具有如下性质：）具有如下性质： (1)恒等元是唯

14、一的，每个元素的逆元也是唯一的。（定理2.2.1) (2)a,bG: (a b)b)-1 -1=b =b-1 -1 a a-1-1。（定理 。（定理2.2.2)2.2.2) (3)a,bG: 方程a x=b有唯一解x x=a-1 b;方程y a=b有唯一解y= b a-1 。（定理2.2.3) (4)消去律成立： a x=a y x=y。 3. 半群与弱群 半群：无恒等元，当然也无逆元（定义2.2.9） 弱群（Monoid群，类群）：有恒等元，无逆元（定义2.2.10） 4.子群 （1）定义：群(G, (G, ）的非空子集）的非空子集H H对于对于 构成群，称构成群，称H H为为G G的子群。

15、的子群。 G, e:假子群，平凡子群假子群，平凡子群 H G且且H e:真子群真子群 （2）定理定理8：群(G, ）的非空子集）的非空子集H为子群的充要条件：为子群的充要条件： i. a, b H: a b H (对对H的封闭性），且的封闭性），且 ii. a H: a-1 H (逆元也在逆元也在H内）。内）。 或或 a, b H: a b-1 H。 5. 有限群的陪集 群群G: e, g1, g2, 子群子群H: h1=e, h2, h3, 若若g1 H, 则用则用g1构成一个集合构成一个集合g1 H: g1, g1 h2, g1 h3, 。 叫叫H的左陪集的左陪集 若若g2 H且且g2 g

16、1 H，用，用g2构成第构成第2个左陪集个左陪集g2 H: g2, g2 h2, g2 h3, 。 G= 0, 1, 8对模对模9加构成群加构成群 H=0, 3, 6 对模对模9加构成子群加构成子群 1+H = 1, 4, 7 2+H = 2, 5, 8 定理定理9（陪集的性质）（陪集的性质） 两个陪集两个陪集g1 H， g2 H满足：满足： i. g1 H g2 H g1 H g2 H = ii. g1 H g2 H g1 H = g2 H 陪集之间不会相交陪集之间不会相交,可见，有限群可见，有限群G可以按可以按H划分为有限个不交的陪集，个数为划分为有限个不交的陪集，个数为 |G|/|H|

17、问题：陪集是从什么概念抽象出来的？问题：陪集是从什么概念抽象出来的？ 5. 有限群的陪集(2) (2) (2) 拉格朗日（拉格朗日（Lagranges)Lagranges)定理：子群的阶一定是群的阶的因子定理：子群的阶一定是群的阶的因子 6. 正规子群（不变子群） 定义：设H为G的子群，若aG: aH=Ha, 称H是G的正规子群。 定理10：子群(H,)为(G, )的正规子群的充要条件： aG，h H:a-1 h aH (定理2.4.4) (3) 定理定理1111（子群的性质）：设（子群的性质）：设(H, )为为(G, )的正规子群，定义的正规子群，定义G 的两个陪集的两个陪集a H和和b H

18、的运算的运算 *为：为： （a H）* （b H）= （a b) H，则正规子群的陪集对，则正规子群的陪集对 *构成群。构成群。 G= 0, 1, 8对模对模9加构成群，加构成群，H=0, 3, 6 对模对模9加构成子群加构成子群 1+H = 1, 4, 7 ，2+H = 2, 5, 8 （1+H)+ H= 1+H (1+H)+(2+H) = H 7. 商群 G= 0, 1, 8对模对模9加构成群加构成群 H=0, 3, 6 对模对模9加构成子群加构成子群 1+H = 1, 4, 7 2+H = 2, 5, 8 （1+H)+ H= 1+H ( 2+H)+ H=2+H (1+H)+(2+H) =

19、 H H, 1+H, 2+H对对+构成群构成群。 商群是构成新群的方法之一。商群是构成新群的方法之一。 定义：群G的正规子群H的全体陪集构成的群称为G关于H的商群， 记为G/H。 四、环与域 1. 环 定义：非空集合R中，定义了两种代数运算“+”和“*”， 若满足下述公理， 则称R构成一个环，记为（R,+,*)。 R在+下构成阿贝尔群； (2) 运算*满足封闭性： a,ba,b R:aR:a* *b b R;R; (3) (3) 运算*结合律成立：结合律成立： a,ba,b R: (aR: (a* *b b）* *c c = a a* *(b(b* *c)c) ; (4) *对+的分配律成立：

20、 a,b,c R: a*(b+c)=a*b+a*c且且(b+c)*a=b*a+c*a 可见，可见，R在在*下为半群，不一定有恒等元，当然也不一定有逆元。下为半群，不一定有恒等元，当然也不一定有逆元。 若有恒等元（这时为弱群），称为有单位元环。若有恒等元（这时为弱群），称为有单位元环。 若每个非零元素有逆元，但对乘法不可换，则称为除环（商域、斜域、若每个非零元素有逆元，但对乘法不可换，则称为除环（商域、斜域、Skew域）域） 全体整数对于整数加法和乘法构成环。 全体偶数对于整数加法和乘法构成环。 m的全体剩余类对剩余类加和乘构成环，称为剩余类环，记为Zm.（可扩展到商群， 见定理4.1.2） n

21、由于有分配律，环的两个运算地位不是一样的 n由于有分配律，运算的单位元0与任何一个元素进行*运算， 结果都为0，即： a R: a*0=0*a=0 设设a*0=b R, a*0=a*(0+0)=a*0+a*0,则则 b=b+b, b+ (-b)=b+b+(-b), 得，得， b=0, 即即a*0=0 2. 域 域：乘法可换，有乘法单位元，非零元素对乘法有逆元的环 定义：非空集合F中，定义了两种代数运算“+”和“*”， 若满足下述公理， 则称F构成一个域，记为（F,+,*)。 (1)F在+下构成阿贝尔群； (2)F-0在*下构成阿贝尔群； (3)*对+的分配律成立： a,b,c R: a*(b+

22、c)=a*b+a*c且且(b+c)*a=b*a+c*a 若每个非零元素有逆元，但对乘法不可换，则称为除环（商域、斜域、若每个非零元素有逆元，但对乘法不可换，则称为除环（商域、斜域、 Skew域）域） 有理数、实数、复数对普通加法和乘法构成域，分别称为有理数域、实 数域、复数域。 q阶有限域，记为GF(q),或Fq 六、线性空间 1. 线性空间（矢量空间）的定义线性空间（矢量空间）的定义 若域(F,+,)上的n重数组（a1,a2, ,ai,an), aiF的集合V满足下述条件， 称V是F上的一个n维线性空间，记为 n F V 定义运算定义运算 为矢量加，则（为矢量加，则（V, )构成阿贝尔群；构

23、成阿贝尔群； v V称矢量，称矢量， c F称标量或纯量，定义运算称标量或纯量，定义运算c*v，c*v V, 称称*为矢量的数为矢量的数 乘；乘； 分配律成立，即分配律成立，即 u,v V, c,d F: c*(u v) =c*u c*v且且(c +d)*v =c*v d*v; 结合率成立，即结合率成立，即 v V, c,d F: (cd)*v=c*(d*v)。 如不引起混淆，如不引起混淆，*、 可省略，+、 统一记为统一记为+ 例，例，GF(2)上的上的n重数组全体，重数组全体， 定义定义 为各位相加，定义为各位相加，定义*为标乘，则构成一线为标乘，则构成一线 性空间。性空间。 六、线性空间

24、2 2. 子空间子空间 若若V1 V且且V1满足线性空间的条件满足线性空间的条件, 称称V1为为V的子空间的子空间. 3. 线性组合线性组合 域域F的矢量的矢量v1,v2, , vk的线性组合定义为的线性组合定义为u=b1*v1+b2*v2+bi*vi+bk*vk, bi F 4. 定理定理12 (定理定理2.6.1) 线性空间线性空间V中矢量中矢量v1,v2, , vk的所有线性组合的集合的所有线性组合的集合S是是V的子空间的子空间. 5. 线性相关线性相关 设设v1,v2, , vk是线性空间是线性空间V中的一组非全零矢量中的一组非全零矢量, 当且仅当存在有一组不全为当且仅当存在有一组不全

25、为 零的标量零的标量c1,c2, , ck (ci F; i =1,2, , k) 使使 c1*v1+c2*v2+ + ck * vk=0 成立成立,则称这组矢量线性相关则称这组矢量线性相关,否则称矢量线性无关否则称矢量线性无关(或线性独立或线性独立). 六、线性空间3 GF(2)上的三重上的三重(0 1 0), (1 0 0), (0 0 1) 线性无关线性无关, 但但(0 1 0), (1 0 0), (1 1 0) 线线 性相关性相关. 6. 定理定理13 (定理定理2.6.2, 线性相关的充要条件线性相关的充要条件) 非零矢量非零矢量v1,v2, , vk线性相关的充要条件是存在矢量线

26、性相关的充要条件是存在矢量vi(i=1,2, ,k)可以表示可以表示 为其余矢量的线性组合为其余矢量的线性组合. 7. 张成张成 线性空间线性空间V中每一个矢量可以由矢量集中每一个矢量可以由矢量集S的矢量线性组合生成的矢量线性组合生成, 则称则称S张成了张成了V. 当当S内的矢量线性独立时，内的矢量线性独立时，S称为称为V的基底的基底. 8. 定理定理14 (定理定理2.6.3) 如果两组线性独立矢量集如果两组线性独立矢量集S1, S2张成同一空间张成同一空间, 则则|S1|=|S2|. |S1|称为空间的维数称为空间的维数, |S1| : 有限维线性空间有限维线性空间, |S1|= : 无限维线性空间无限维线性空间. 六、线性空间4 9. 定理定理15 (定理定理2.6.4) 若若V是是k维线性空间维线性空间, 则则V中任意中任意k个线性独立的矢量是个线性独立的矢量是V的基底的基底. 推论推论: V1 V2且且V1与与V2维数相同维数相同 V1=V2. 七、矩阵 1. 定义定义 从环（从环（R,+, *)中选出中选出m n个元素个元素aij (i =1,2 , ., m; j =1, 2, , n)按如下次