《信息论第九讲-代数基础与线性分组码》由会员分享，可在线阅读，更多相关《信息论第九讲-代数基础与线性分组码（69页珍藏版）》请在金锄头文库上搜索。
1、群的定义：如果一个元素集合G，在其中 定义一种运算“*”，并满足下列条件则称为一个 群(Group)。a,b,c,e,a-1G。 自闭性，c=a*b 结合律，a*(b*c)=(a*b)*c 单位元（恒元），a*e=e*a=a 逆元， a*a-1=a-1*a=e 如果还满足交换律，a*b=b*a, 则称为交换群。 5.4 代数基础 5.4.1 群(Group) Date1 定理1：群G中的单位元是唯一的。 定理2：群G中任一元素的逆元是唯一的。 有限群：群中元素的个数称为元素的阶，有限元素 的群称为有限群。（m阶有限群） 模运算： G=0，1为一个模2加法群， 0+0=0，0+1=1，1+0=1
2、，1+1=0 0是单位元， 元素本身是逆元，满足结合律，交换律和自闭性，为 一个加法交换群。 当p为一个素数，则集合G=1,2,p-1在模p乘法下为 一个群。 Date2 例如：p=5为一个素数, G=1,2,3,4为一个乘法 群， *1234 11234 22413 33142 44321 全体实数集合为一个普通加法的交换群； 全体非零实数集合为一个普通乘法的交换群； Date3 子群：如果集合G在某种运算*下为一个群，集合H 为G中的一个非空子集。若H在运算*下也满 足自闭性，结合律，单位元和逆元，则称H 为G的一个子群。 偶数集合H:2n为整数加法群的一个子群。 定理：如果集合G在运算*
3、下为一个群，H为一个子 群，则G中的所有元素都可以由子群H中的 元素表示。 单位元：如果H为G的一个子群，则G中唯一的单 位元一定在子群H中。 Date4 分元陪集：利用子群和陪集，可以用子群H的元素 表示所有G中的元素。 例：设G是整数集合，在普通加法+下为一个交 换群，而H为G的一个子群，它由整数m的倍数 构成，那么，所有正整数均可用H中的元素表示 ，且划分为子群H的若干个陪集。 H:nm; n=0,1,2,。 例如m=3,则子群H的元素为： H:0, 3, 6, 9, 12, 15, 18, 利用分元陪集的方法，用H的元素表示G中的所 有元素。 Date5 将子群H中的元素放在表的第一行
4、，且单位元0 放在首位，称为陪集首。 将H中没有的，但G中的元素1作为陪集首，放在 表的第二行的首位，将陪集首分别与第一行的元 素做加法运算，组成的二个陪集。 将第一行，第二行中没有的，但在群中有的元素 2作为第二个陪集的陪集首，构成第三个陪集。 这样，利用分元陪集的方法，可以构成所有G中 的元素。 陪集103-36-69-9 陪集2 1+0= 1 1+3= 4 -27-510-8 陪集3 2+0= 2 2+3= 5 -18-411-7 Date6 5.4.2 域(Field) 域的定义：如果一个元素集合F，在其中定义加法 和乘法两种运算，并满足下列条件则称为一个域 (Feild)。a,b,c
5、,d,e,a-1F。 在加法下为一个交换群，即满足自闭性，交换律， 结合律，单位元为0，逆元。 在乘法下也为一个交换群，即满足非零元素自闭性 ，交换律，结合律，单位元，逆元。 在加法乘法下满足分配律。 有限域：域中的元素个数m称为域的阶，有限个元 素的域称为有限域或叫作伽罗华域，记为GF(m)， GF-Galois Field， Date7 循环群：如果一个群中存在一个元素，其各次幂 可以构成整个群的所有元素，这种群称为循环群。 定理：有限域GF(q)的非零元素构成一个循环群。 设a是GF(q)中的一个非零元素，由于GF(q)的非零元 素在乘法下为自闭的，所以a，a2，a3，也必然是 GF(q
6、)中的非零元素，又因为GF(q)为有限元素，所 以必然有一个最小的正整数n，使an=1。这个正整数 n称为元素a的阶。 令a为有限域GF(q)的非零元素，则aq-1=1。 令a为有限域GF(q)的非零元素，且n为a的阶， 则q-1一定能被n除尽。 Date8 本原元：如果有限域GF(q)中，非零元素a的 阶n=q-1，就称a为GF(q)的本原元素。 本原元素的各次幂构成有限域FG(q)的所有元素。 每个有限域都有其本原元素。 例如：素数q=7，模7运算下构成有限域GF(7)，域中 元素为0,1,2,3,4,5,6，其非零元素集合为1,2,3,4,5,6 ，考虑其中的非零元素a=3，可知：31=
7、3，32=33=2 ，33=323=6，34=333=4，35=5，36=1 ，（3的阶=6） 可以看到3的各次幂构成了GF(7)中所有非零元素，所 以3的阶n=q-1=6，3为GF(7)的一个本原元。 Date9 如果取a=4，可知：41=4，42=2，43=1(4的阶=3）， 44= 43 4=4，45= 42 43=2， 46= 43 43=1(4q-1=46=1) 即元素4的阶为n=3，并且3可以除尽q-1=6。 如果取a=5，可知：51=5，52=25=4，53=5251=20=6 54= 53 5=30=2，55= 51 54=10=3， 56= 52 54=8=1(2q-1=26
8、=1) 即元素5的阶为n=6=q-1，即5也为GF(7)的本原元。 可以验证： 如果取a=6，可知：61=6，62=36=1 (6的阶=2） ，63=6 ， 64= 1，65= 6， 66= =1(6q-1=66=1) 如果取a=2，可知：21=2，22=4，23=8=1 (2的阶=3）， 24= 23 2=2，25= 22 23=4， 26= 23 23=1(2q-1=26=1) Date10 5.4.3 域上多项式 域上多项式： 如果多项式f(x)=f0+f1x+f2x2+fnxn的系 数取自二元有限域GF(2)，则称f(x)为域FG(2) 上的多项式。fi=0或fi=1; 域上多项式计算
9、： 加法： 如果f(x)=f0+f1x+f2x2+fnxn; g(x)=g0+g1x+g2x2+gnxn 则： f(x)+g(x)= (f0+ g0)+(f1 +g1)x +(f2 +g2)x2+(fn+gn)xn Date11 乘法： 如果 f(x)=f0+f1x+f2x2+fnxn; g(x)=g0+g1x+g2x2+gmxm 则： f(x)g(x)=c(x)=c0+c1x+c2x2+cn+mxn+m; c0=f0g0 c1=f0g1+f1g0 cn+m=fngm Date12 除法：如果f(x)=1+x+x4+x5+x6; g(x)=1+x+x3; 则f(x)/g(x)的结果可以写作：
10、其中：q(x)=x3+x2为商式; r(x)=x2+x+1为余式; 利用展转相除法（欧几里得除法）可以计算多项式 除法。 Date13 x3+x+1x6+x5+x4 +x+1 x5+ x3 +x+1 x2+x+1 x3+x2 x6 +x4+x3 x5 +x3+x2 如果r(x)=0，即f(x)能被g(x)除尽，则称g(x)为f(x)的因式； f(x)为g(x)的倍式。 Date14 多项式的模运算： 如果GF(2)上多项式，F(x),N(x),Q(x),R(x)满足： 则称在模N(x)条件下，F(x)=R(x)。 Date15 不可约多项式： 如果f(x)为GF(2)上的m次多项式，它不能被任
11、 何次数小于m，大于0的多项式除尽，则称其为 GF(2)上的不可约多项式，既约多项式。 f(x)=x3+x+1; f(x)=x4+x+1;均为不可约多项式。 GF(2)上的多项式若有偶数项，则一定可被x+1除 尽。 对于任意m1,都存在m次不可约多项式。 GF(2)上的任意m次不可约多项式，一定能除尽 xn+1，其中n=2m-1。 例如：x3+x+1,可以除尽x7+1。 Date16 x3+x+1x7+ 1 x5+ x4 +1 x4+x3+x2+1 x4+x2+x+1 x7 +x5+x4 x5 +x3+x2 x4+x2+x x3+x+1 x3+x+1 0 Date17 本原多项式： 如果n=2
12、m-1，f(x)为GF(2)上的m次不可约多项 式，且f(x)可除尽xn+1，则称f(x)为本原多项式 。 不可约多项式不一定是本原多项式，本原多项式 一定为不可约的。 m次本原多项式是不唯一的。 性质： 对于GF(2)上的多项式f(x)，有 f(x)2=f(x2)。 Date18 5.4.4 GF(2)上的矢量空间 域上矢量空间：令V是一个矢量集合，在其上定 义一个加法运算。令F是一个域，在域中的元素和V 中的元素之间定义了一个乘法运算。 如果集合V满足下例条件，称其为域F上的矢量空间 （线性空间）。 V是加法可交换群； F中的任意元素a和V中的元素Vi的乘积，aVi 是V中的元素； 满足分
13、配律：a,bF; Vi,VjV; a(Vi+Vj)=aVi+aVj; (a+b) Vi=aVi+bVi; 满足结合律：(ab) Vi=a(bVi); F中的单位元为1，1Vi=Vi。 V中的单位元为0矢量。 Date19 域上矢量空间的性质： 0为F上的零元，则0Vi=0; c为F上的任意标量，则c0=0; c为F上的任意标量和V中的任意矢量Vi，(-c) Vi=c(- Vi)=-(cVi); GF(2)上的矢量空间： 一个有n个分量的序列；(a0,a1,an-1) 其中每个分量是二元域上的元素(ai=0,1)，这个序列 称为GF(2)上的n-重。 GF(2)上共有2n个n-重。令Vn表示这2
14、n个n-重的集合 ，则可以证明Vn是GF(2)上的一个矢量空间。 Date20 例如： n=5, GF(2)上的5-重矢量空间V5由32个矢量 组成。 (00000),(00001),(11111)。 这个空间中任意两个矢量之和仍然是这个空 间中的矢量。 GF(2)中的元素0，1乘上空间中的任意矢量仍 然是这个空间中的矢量。 Date21 V的子空间： 如果V是F上的矢量空间，V的一个子集也 是F上的一个矢量空间，则称S为V的一个 子空间。 例如：V5上的子集， (00000),(00111),(11010),(11101) 为一个子空间。 Date22 线性组合： 令V1,V2,Vk是F上矢
15、量空间V中的k个矢量。 令a1,a2ak是F中的k个标量。 则: a1V1+a2V2+akVk称为他们的线性组合。 如果：除非a1=a2=ak=0,否则 a1V1+a2V2+akVk0； 则称V1,V2,Vk是线性独立的。 如果：a1,a2ak是不都为0，而可以使 a1V1+a2V2+akVk=0； 则称V1,V2,Vk是线性相关的。 Date23 定理：子空间的构成 如V1,V2,Vk是F上矢量空间V中的k个矢量， 则V1,V2,Vk的所有线性组合构成V的一个 子空间。 Date24 矢量空间的基底与维数： 如果一个矢量空间或子空间中的所有矢量， 都是由其中的一组矢量V1,V2,Vk的线性组 合得到，则称这组矢量张成这个矢量空间或 子空间。 如果这组矢量是线性无关的，则称这组矢量 是这个矢量空间的基底。 基底中矢量的个数称为矢量空间的维数。 Date25 例如： GF(2)上的三维矢量空间V3的所有8个矢量都可 以由(001),(010),(100)这三个矢量的线性组合构 成，而且它们是线性无关的，因此
