编码理论基础

包括群、域、本原多项式、伽罗华域算术。 1． 群

令G是一个集合。现规定G上的二元运算“*”的规则：

对G中的每一对元素a和b，在G中指定一个唯一确定的第三个元素c=a*b。当这样的二元运算“*”定义在G上时，我们就称在“*”运算下G是封闭的。若对G中的任意元素a、b、c有

a(bc)(ab)c则称G上的二元运算“*”是结合的。

定义1.1 设G是非空集合。并在G上定义了一种运算“*”，如果满足以下条件就称做群：

（1） 满足封闭性。若a和b为集合G中的任意元素，即a∈G，b∈G，恒有

abcG

（2） 结合律成立，对任意a∈G，b∈G，c∈G，

a(bc)(ab)c

（3） G中存在一个恒等元e，对任意a∈G，有

aa1e其中a-1∈G，且称为a的逆元素。

例如，整数中，任意两个整数相加还是一个整数，因此满足封闭性；显然也满足结合律；任意一个非零整数Z的逆元素是-Z，Z+（-Z）=0，所以恒等元是0。则整数在实数加法下是一个群。但整数在实数乘法下就不能构成一个群。

若群G中，a∈G，b∈G，有

abba则称群为可交换群或阿贝尔群。

定理1.1 群G的恒等元是唯一的，每个元素的逆元素也是唯一的。

定理1.2 令H是G的非空子集。若H在G的群运算下是封闭的且满足群的所有条件，就称H为G的子群。

例如，偶数是整数的一个非空子集。同样可以证明偶数在实数加法下也是一个群，所以偶数是整数的一个子群。

定理1.3 群中元素的个数称为群的阶。

2． 域

域就是一个集合，在其中可以进行加、减、乘、除而不会超出该集合。加法和乘法都必须满足交换律、结合律和分配律，正式定义：

定义2.1 令F是一个集合，其上定义了两个二元运算，称做加法“+”和乘法“·•”。满足下述条件时，就称集F和两个运算“+”和“·”是域：

1

（1）F关于加法运算构成阿贝尔群；

（2）F中的非零元素在乘法下构成阿贝尔群，其恒等元素以1表示； （3）对加法和乘法分配律成立

a•·（b+c）＝a·b+a·c

根据定义可得出，一个域至少由两个元素即加法恒等元素和乘法恒等元素组成。域中元素的个数叫做域的阶。有限个元素的域叫做有限域。在域中，元素a的加法逆元用-a表示，乘法逆元用a-1表示。域的一些基本性质可以从域的定义导出。

性质1：对域中的每个元素a·0=0·a=0。

性质2：对域中任意两个非零元素a和b，a·b≠0。 性质3：a·b=0且a≠0，这意味着b=0。

性质4：对域中任意两个元素a和b，-（a·b）=（-a）·b=a·（-b） 性质5：对a≠0，a·b = a·c，可推出b=c。 一个重要的概念——素域。

令P为素数，不难证明，整数集{0,1,2,……p-1}在模p加法下是阿贝尔群，非零集合{1,2,……p-1}在模p乘法下也构成阿贝尔群，由于模p加法和模p乘法是可分配的，所以集合{0,1,2,……p-1}是阶为p的域。由于这个域由素数p构成，故称为素域并以GF（p）表示。对于p=2，我们得到二元域GF（2）。例如p=7，模7加法和模7乘法由表1和表2给出。整数集合{0,1,2,3,4,5,6}在模7加法和模7乘法下是一个有7个元素的域,以GF（7）表示。

表1 表2

模7加 0 1 2 3 4 5 6 0 0 1 2 3 4 5 6 1 1 2 3 4 5 6 0 2 2 3 4 5 6 0 1 3 3 4 5 6 0 1 2 4 4 5 6 0 1 2 3 5 5 6 0 1 2 3 4 6 6 0 1 2 3 4 5

模7乘 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 0 1 2 3 4 5 6 2 0 2 4 6 1 3 5 3 0 3 6 2 5 1 4 4 0 4 1 5 2 6 3 5 0 5 3 1 6 4 2 6 0 6 5 4 3 2 1

对于任何素数p都存在一个有p个元素的有限域。对于任何正整数m，可以将素域GF（p）扩展成有pm个元素的域，称它为GF（p）的扩域，并以GF（pm）表示。而且已证明，任意有限域的阶是素数的幂次。有限域以其发现者命名为伽罗华域。大部分代数编码理论，码的构造和译码是围绕有限域建立的。

研究q个元素的有限域GF（q）。因为在加法下域是封闭的，两个元素之和也是域中的元素，即必存在两个正整数m和n，m11i1i1mn nm0 。所以，必存在一个最小正整数λ（读lamuda）使 1则可得 1   0 。这一整数

i1i1

λ叫做域GF（q）的特征。二元域GF（2）的特征是2，1+1=0。素域GF（p）的特征是p ，因为1≤k1k0且10i1i1kp

定理2.1：有限域的特征λ是素数.

2

定理2.2：令a是有限域GF（q）中的非零元素，则a=1。

定理2.3：令a是有限域GF（q）中的非零元素，令n是a的阶，则q-1能被n除尽。 在有限域GF（q）中，若非零元素a的阶是q-1，就称a是本原的。所以，本原元素的各次幂生成GF（q）的所有非零元素，每个有限域都有本原元素。若在群中存在一个这样的元素，其各次幂构成整个群，就称该群是循环的。若a为循环群中的本原元素，使an=e的最小整数n为循环群的级。

有限循环群的性质。

m

性质1：若a∈G是n级元素，则a=e的充要条件是m可以被n除尽。

k

性质2：若a是n级元素，则元素a的级为n /（k, n）。[（k, n）表示k除以n后的余数]。

3． 伽罗华域算术

在数字通信系统中用到的伽罗华域通常是二元域GF（2）及其扩域GF（2m），所以这里仅限于讨论二元域及扩域。

定义3.1 不能分解因式的多项式称为既约多项式。若GF（2）上的m次多项式f（x）不能被GF（2）上任何次数小于m，但大于零的多项式除尽，就称它是GF（2）上的既约多项式。首先我们来分析域上多项式。

例1 x3+x+1=0，由模m加法可得x3=x+1，x= x3+1，若a是多项式的根，则a的所有幂次为：

q-1

a0001a1010a2100a3a1a4aa3a(a1)a2aa5aa4a(a2a)a3a2a2a1a6aa5a(a2a1)a3a2aa1a2aa21a7aa6a(a21)a3aa1a1a8aa7a1a对应三位二进制数001对应三位二进制数010对应三位二进制数100对应三位二进制数011对应三位二进制数110对应三位二进制数111对应三位二进制数101对应三位二进制数001对应三位二进制数010以上分析可知，a的所有幂次共有七个非零元素，再加上0元素，构成了含有八个元素的域GF（23），它是GF（2）的三次扩域。可见，x3+x+1是既约多项式。那么，是不是凡是二元域上的既约多项式的根都能构成m次扩域GF（2m）。为了说明这个问题，再看一个例子。

如：x4+x3+x2+x+1

a010001a10010a2a301001000a4a3a2a11111a510001a6a0010 3

我们发现，a的所有幂次仅有五个元素，加上零元素共有6个，而不是24个，所以x4+x3+x2+x+1不能构成GF（24）扩域。

由GF（2）构造GF（2m）的过程。

例2：令m=4，多项式p（x）=x4+x+1，是GF（2）上的本原多项式。设p（α）=α4+α+1=0，则α4=α+1。利用此式可构造GF（24）。

GF（24）中的元素列如下表3.1。

幂表达式 多项式表达式 4—重表达式 0 0 0000 1 1 0001 0010 α α 0100 α2 α2 1000 α3 α3 0011 α4 α+1 0110 α5 α2+α 1100 6 32αα+α 1011 7 3αα+α+1 0101 α8 α2+1 1010 0111 α9 α3+α 1110 α10 α2+α+1 1111 α11 α3+α2+α 1101 α12 α3+α2+α+1 1001 α13 α3+α2+1 0001 14 3αα+1 15 1 α

可见α是x4+x+1的根,它的所有幂次构成了GF(24)中所有非零元素，加上零元素共有16个元表，α的幂次构成了乘群，且是循环群，α的级是（24-1）。所以α是扩域GF（24）的本原元素。

此外，215=1表明α还是x15+1的根，因此，既约多项式x4+x+1能够被多项式x15+1整除，而不能被其它次数小于15的多项式整除。

归纳：GF（2m）上的m次既约多项式有两大类，一类是能被xn+1整除,但不能被x5+1整除，其中n=2m-1，sm

4． 伽罗华域GF（2）的基本性质

在普通代数中我们经常看到，实系数多项式的根不在实数域中，而是在含实数域作为子域的复数域中。例如，多项式x2+6x+25在实数域中没有根，但有两个复共轭根：-3+4i和-3-4i，

 1共中 i  。系数取自GF（2）的多项式也一样。在此情况下，系数取自GF（2）的多

项式可以没有GF（2）中的根，但在GF（2）的扩域中有根。

例如：x4+x3+1在GF（2）是上既约的，所以根不是GF（2）中的元素。它有取自GF（24）的4个根。 如果我们将上例中给出的GF（24）中的元素代入x4+x3+1， 就会发现， α7、α11、α13及α14是x4+x3+1的根，可以证实：

7:(7)4(7)3128211(321)(32)10 (=α14·α14+α14·α7+1逐步展开)

4

也可以证实α11、α13、α14三个根。由于α7、α11、α13、α14是x4+x3+1的全部根，则（x+α7）（x+α11）（x+α13）（x+α14）≡x4+x3+1。（可以用GF（24）元素进行验算）。

令f（x）是系数GF（2）上的多项式。若GF（2m）中的元素β是f（x）的一个根，则多项式f（x）就可能有其它根在GF（2m）中。这些根是哪些元素呢？下面的定理可给出回答。

定理4.1 令f（x）是系数取自GF（2）的多项式，令β是GF(2)扩域中的元素.若β是f（x）的根，则对任何 l0，β2也是f（x）的根。

证明：

f2(x)(f0f1xfnxn)2f0(f1xf2x2fnxn)(f1xf2x2fnxn)2f02(f1xf2x2fnxn)2

重复展开上述方程，最终得到：

2f02f0(f1xf2x2fnxn)f0(f1xf2x2fnxn)f2(x)f02(f1x)2(f2x2)2(fnxn)2

由于 f f i2  f i ，因此有： i0或1,f2(x)f0f1x2f2(x2)2fn(x2)nf(x2)

从上式得出，对任意 l  0

f(x)2lf(x2)l

将β代入上式得：

f()2

lf(2)2l2ll因f()0,f()0,也是f(x)的根.

2l

元素  称为β的共轭元。 证毕。

m

定理4.1说明，若GF（2）中的元素β是GF(2)上的多项式f（x）的根，则β的所有不

m6543

相同的共轭元(也在GF（2）中)也是f（x）的根。如，多项式f（x）=x+x+x+x+1以前例

4415

（表3.1）GF（2）中的元素α为根，为了证实这一点，利用α=1很容易证明：

5

f(4)(6)4(5)4(4)4(3)4124201612195121(3)(2)(321)10α4的共轭元是：

422423(将前三项折成a15•ai 其中α15=1)

(),()42816,()322

4注意 (  4 ) 2     4 ，由定理4.1得出，α8、α、α2也必是f（x）=x6+x5+x4+x3+1的根。可以检验，α5和它的共轭元α10也是f（x）的根。

令β是域GF（2m）中的非零元素，由定理2.2得：

2mm11两边同加1，得  2 1  1  0 。

m2m121这就是说β是多项式 x  1 的根。因此GF（2m）中的每个非零元素都是 x  1 的

mm211 1x 2 根。由于 x 的次数为2m-1，GF（2m）中的2m-1 个非零元素就形成  1 的所有

根。由此得到下一个定理。

2m1mmmx1定理4.2 GF（2）中的2-1个非零元素形成 的全部根。由于GF（2）中的零

元素“0”是x的根，故定理4.2有下述系。

2m系4.2.1 GF（2m）中的元素形成 x  x 的所有根。

[即x2mxx(x2m11)]

由于GF（2m）中的任何元素β都是多项式x 2m  x 的根，β就可能是GF（2）上次数小于2m的多项式的根。令Φ（x）是GF（2）上使Φ（β）=0的最低次多项式。(不难证明Φ（x）是唯一的)。多项式Φ（x）称作是β的最小多项式。例如，GF（2m）的零元素“0”的最小多项式是x，单位元素“1”的最小多项式是x+1。下面导出最小多项式的一些性质。

定理4.3：域元素β的最小多项式Φ（x）是既约的。（证明略）

定理4.4：令f（x）是GF（2）上的多项式。令Φ（x）是域元素β的最小多项式。若β是f（x）的根，则f（x）可被Φ（x）除尽。（证明略）

由系4.2.1和定理4.4可得出下述结果：

2mmxx。 定理4.5：GF（2）中元素β的最小多项式Φ（x）除尽

这个定理说明，Φ（x）的所有根都在GF（2m）中，那么Φ（x）的根是什么？下面的两个定理将给出回答。

m

定理4.6：令f（x）是GF（2）上的既约多项式。令β是GF（2）中的元素。令Φ（x）是β的最小多项式。若f（β）=0，则Φ（x）= f（x）。

证明：由定理4.4得到，Φ（x）除尽f（x）。由于Φ（x）≠1且f（x）是既约的，必有Φ（x）= f（x）。证毕。

定理4.6说明，若一既约多项式有β为根，它就是β的最小多项式Φ（x）。由定理4.1

e2e2得出，β及其共轭  2 ,  2 ,   2 是Φ（x）的根。令e是使    最小整数，则 ,m2e12 2  2 ,  2   ，故e≤m。 , 就是β的所有不同共轭元。由于e2 的最小非负整数，则 定理4.7：令β是GF（2m）中的元素，并令e是使  

f(x)(x2)i0e1i是GF(2)上的既约多项式 6

证明：

e1ie122if(x)(x)(x2)2i0i02

因(x2)2x2x2x22

iiii1x22ii1f(x)2(x2i0e12i1)(x22)i1eiee12(x2)(x22)i1

因    ，则

2ef(x)2(x)f(x2)2i0e12i 式－b

e f 0 令 f ( x ) f 1 x    fe x ，其中f0=1。展开

f(x)2(f0f1xfexe)2fix(11)fifjxij22ii0ei0j0eeefi2x2ii0(ij) 式－b

由以上2式（式－a，式－b）可得到：

fxii0e2ifi2x2ii0e

则对0≤i≤e，我们必有

fifi2这仅当fi=0或1时才成立。所以。f（x）的系数取自GF（2）。现假设f（x）在GF（2）上不是既约的且f（x）=a（x）b（x）。由于f (β)=0，∴a（β）=0或b (β)=0。若a（β）

e1=0，则a（x）有  ,  2 ,   2 为根，因此a（x）次数为e且a（x）= f（x）。类似地，若b（β）=0，则b（x）= f（x）。所以，f（x）必是既约的。 证毕。

定理4.6和定理4.7可得到定理4.8。

em

定理4.8：Φ（x）是GF（2）中元素β的最小多项式。令e是使 2的最小整数，则

(x)(x)i0e12i 7

例3 前面表3.1给出伽罗华域GF（24）。令β=α3。β的共轭元是

239  6 ,  2   12 , 24   9  ( 15   9 )    3 的最小多项式则为： 2  2 , (x)(x3)(x6)(x12)(x9)

借助于（表3.1例子）GF（24）列表3.1，将上式乘出可得：

(x)x2(36)x9x2(129)x21(x22x9)(x28x6)x4(28)x3(6109)x2(178)x15x4x3x2x1另一种求域元素的最小多项式的方法，用例子说明。

例4：假设我们要决定GF（24）的γ=α7的最小多项式Φ（x）。γ的不同共轭元是

,2142228,13235611

因此Φ（x）为4次式，且必有下述形式：

(x)a0a1xa2x2a3x3x4

将γ代入Φ（x）中，

()a0a1a22a3340

式中γ，γ2，γ3和γ4采用多项式表示时可得到

a0a1(31)a2(31)a3(23)(321)0(a2a1a01)a1(a31)2(a3a2a11)30

为了使上式等号成立，必须使系数为零。

10a0a1a2a10a310a1a2a310

 a解线性方程可得出， a 0  1 , a 1 2  0 , a 3  1 。

∴γ=α7的最小多项式为

8

(x)x4x31GF（24）中所有元素的最小多项式在表4.1中给出。 表4.1 p（x）=x4+x+1的GF（24）中元素的最小多项式

共轭根 最小多项式 0 x 1 x+1 4248x+x+1 α，α，α，α x4+x3+x2+x+1 α3，α6，α9，α12 x2+x+1 α5，α10 x4+x3+1 α7，α11，α13，α14

m

定理4.9：令Φ（x）是GF（2）中元素β的最小多项式。令e是Φ（x）的次数，则e2

是使β=β的最小整数，而e≤m。

特别指出，GF（2m）中任一元素的最小多项式的次数除尽m。上表中表明，GF（24）中每一元素的最小多项式的次数除尽4。

在伽华罗域GF（2m）的构造中，应用m次本原多项式p（x），并要求元素α是p（x）的根，由于α的幂生成GF（2m）中所有非零元素，所以α是本原元素。实际上，α的所有共轭元都是GF（2m）的本原元素。

222m

,,也是GF（2m）定理4.10：若β是GF（2）的本原元素，则它的所有共轭元

的本原元素。

例：考察域GF（24），β=α7的幂是

01,17,214,3216,42813,5355,64212,7494,85611,9633,107010,11772,12849,1391,14988,151051.

显然，β=α7的幂生成GF（24）的所有非零元素，故β=α7是GF（27）的本原元素。β=α7的共轭元是：

214,213,21123(151)

不难验证它们都是GF（2m）的本原元素。

m

定理4.11：若β是GF（2）中的一个n阶元素，则它的所有共轭元有同样阶数n。（定理4.11是定理4.10的更一般形式）

522205例5：考察GF（24）中元素α5。由于 (  )    ，故α5的共轭元只有α10。

α5和α10的阶数都是3。α5和α10的最小多项式是x2+x+1。其次是m=4的因子。α3的共轭元是α6，α9和α12，它们的阶数都是n=5。

例：求GF（24）中元素α5的最小多项式：

522205(由于 )    ，所以α5的共轭元只有α10。

解：γ=α5

(x)a0a1xa2x2（标准形式）

2aaa0012 9

a0a15a2100a0a1()a2(1)0a0a12a1a22a2a20(a0a2)(a1a2)(a1a2)20

为了使等式两边相等，必须使左边的各项系数为0。

22查表3.1521021a20a0a1a20a1a20

2最小多项式：x  x  1

5． 用于伽华罗域GF（2m）算术的计算

研究GF（24）上的下述线性方程：

a0a2a1a2a0a1a21x7y2

将α3乘②式，可得

①

12x8y4②

x11y7x7y2

将②’+①，可得到

②’ ①

(711)Y27已知

73111327112182272321128Y12Y4

将Y=α4代入①式，可得到

x742x9∴方程的解为x=α9，Y=α4

例6 假设要解GF（24）上的方程

10

f(x)x27x0

为了得到此解，可以通过GF（24）中所有元素代替x后找到。试探性做，发现f（α6）=0和 f（α10）=0 ，因为

f(6)(6)27612130f(10)(10)2710520(220)

610)。 因此，α6和α10是f（x）的根，且 f ( x )  ( x   )( x  

上述计算在译BCH分组码所需要的计算中是典型的，而且可以很容易在通用计算机上编制程序。

5．矢量空间

令v是元素的集合，在其上定义了一个称作是加法“+”的二元运算。令F是域。在域F中的元素和v中的元素之间还定义了一个以“· ”表示的乘法运算。若集合v满足下述条件，就称它为域F上的矢量空间：

I. v是加法下的可交换群。

II. 对F中的任意元素a和V中任意元素V，a·v是v中的元素。 III. （分配律）对v中的任意元素u和v，和F中的任意元素a和b。

a•(uv)a•ua•v(ab)•va•vb•vIV. （结合律）对v中任意v和F中任意a和b。

(a•b)•va•(b•v)

V. 令“1”是F的单位元，则对v中任意v，1·v=v。

v中的元素称为矢量，域F中的元素称为标量。V上的加法称作矢量加法，F中的标量和v中的矢量结合成v中矢量的乘法看作是数乘（或积）。V的加法恒元以0表示。

域F上的矢量空间v的一些基本性质可由上述定义导出。 性质Ⅰ：令0是域F中的零元。对v中任意矢量v，0·v=0。 性质Ⅱ：对F中任意标量c，c·0=0。

性质Ⅲ：对F中任何标量c和v中任何矢量v，

(c)•vc•(v)(c•v))

这就是说（-c）·v或c·（-v）是矢量c·v的加法逆元。

下面介绍非常有用的，在编码理论中起着中心作用的GF（2）上的矢量空间。研究n个分量的有序序列。

(a0,a1,an1)其中每个分量ai是二元域GF（2）上中的元素（即ai=0或1）。这个序列一般称作GF（2）

11

上的n—重。由于每个ai有两种选择，我们可以构造2n个不同的n—重。令vn表示2n个不同n—重的集合。现在，我们在vn上定义一个加法：对vn中任何u=（u0，u1，… un-1）和 v=（v0，v1，… vn-1），

uv(u0v0,u1v1,un1vn1)（5-1）

其中ui+vi按模—2进行相加。显然u+v也是GF（2）上的n—重。因此vn在（5-1）式所定义的加法下是封闭的。容易证明，vn在（5-1）式定义的加法下是可交换群。

下面定义以GF（2）中元素a数乘vn中一个n—重v为：

（5-2）

其中a·vi按模2乘法进行。显然， a  , v ) 也是vn中的n—重。若a=1，则： (vv , 01n1a(v0,v1,vn1)(av0,av1,avn1)1(v0,v1,vn1)(1v0,1v1,1vn1)(v0,v1,vn1)

容易证明，式（5-1）和（5-2）定义的矢量加法和数乘分别满足分配律和结合律。所以，GF（2）上所有n—重的集合vn形成GF（2）上的一个矢量空间。

例5-1 令n=5。GF（2）上所有5—重的矢量空间由下述32个矢量组成。 （00000），（00001），……（11111） （10111）和（11001）的矢量和是

（10111）+（11001）=（1+1，0+1，1+0，1+0，1+1）=（01110） 利用（5-2）定义的数乘规则，有 0·（11010）=（0·1，0·1，0·0，0·1，0·0）=（00000） 1·（11010）=（1·1，1·1，1·0，1·1，1·0）=（11010）

任意域F上的所有n—重的矢量空间可用类似的方法构造。但在这里，我们仅关心GF（2）或GF（2m）上的所有n—重的矢量空间。

V是域F上的一个矢量空间。可以会碰到v的一个子集s也是F上的一个矢量空间，这种子集称作是v的子空间。

定理5.1 令s是域F上矢量空间v的一个非空子集，则当s满足下述条件时它是v的一个子空间：

i) 对s中的任意两个矢量u和v，u+v也是s中的矢量。

ii) 对F中的任意元素a和s中的任意矢量v，a·u也在s中。

证明：条件i）和ii）是说在v的矢量加和数乘下s是封闭的。条件ii）保证对s中任意矢量v，其加法逆元（-1）·v也在s中。于是v+（-1）v=0也在s中。所以s是v的子群。由于s的矢量也是v的矢量，s必满足结合律和分配律。因此，s是F上的矢量空间，且是v的一个子空间。证毕。

例5-2 研究例5-1给出的GF（2）上所有5—重的矢量空间v5。集{（00000），（00111），（11010），（11101）}满足定理5.1的两个条件，故它是v5的一个子空间。

令 v 1, v 2 ,  , v k 是域F上矢量空间v中的k个矢量。令 a 1 , a 2 ,  , a k 是F中的k个标量。和

a1v1a2v2akvk 12

称作是 v v 2 ,  , v k 的线性组合。显然， , v 2 ,  , v k 的两个线性组合的和为 v11,

(a1v1a1v2akvk)(b1v1b2v2bkvk)(a1b1)v1(a2b2)v2(akbk)vk

v 2 ,,vv 2 ,,v也是 v 1 , 1 , k 的线性组合的乘积 k 的线性组合。F中的标量c和 v

c(a1v1a2v2akvk)(ca1)v1(ca2)v2(cak)vk

v 2 ,,v也是 v 1 , k 的线性组合。

,v定理5-2 令 v 1 2 ,  , v k 是域F上矢量空间v的k个矢量，则 v 1 , v 2 ,  , v k 的所有

线性组合构成v的一个子空间。

例5-3 分析例5-1给定的GF（2）中所有5—重的矢量空间v5。（00111）和（11101）的线性组合是：

0(00111)0(11101)(00000)0(00111)1(11101)(11101)1(00111)0(11101)(00111)1(00111)1(11101)(11010)

这四个矢量构成例5-2给出的同一子空间。

域F上矢量空间v中的一组矢量 v 1 , v 2 , ,v k 称作是线性相关的，当且仅当在F中存

在k个不都为零的标量使得

a1v1a2v2akvk0

若一组矢量 v 1 , v 2 ,  , v k 不是线性相关的，就称作是线性的，除非 a1a2ak0否则

a1v1a2v2akvk0 例5-4 矢量（10110），（01001）和（11111）是线性相关的，因为

1(10110)1(01001)1(11111)(00000),(模2加)

但是（10110），（01001）和（11011）是线性的。这3个矢量的所有8种线性组合如下：

13

0(10110)0(01001)0(11011)(00000)0(10110)0(01001)1(11011)(11011)0(10110)1(01001)0(11011)(01001)0(10110)1(01001)1(11011)(10010)1(10110)0(01001)0(11011)(10110)1(10110)0(01001)1(11011)(01101)1(10110)1(01001)0(11011)(11111)1(10110)1(01001)1(11011)(00100)

我们称矢量集合张成一矢量空间v，若v中每个矢量都是该集合中矢量的线性组合。在任何矢量空间或子空间中，都至少存在一个线性的矢量的集合B，它张成该空间。这个集合称作矢量空间的基底（或基）。矢量空间基底中矢量的数目称作矢量空间的维数。（注意：任意两个基底中矢量的数目相同）

研究GF（2）上所有n—重构成的矢量空间vn0 我们作下述n个n—重：

e0(1,0,0,0,,0)e1(0,1,0,0,,0)en1(0,0,0,0,1)

其中n—重ei仅在第i位上有一个非零分量，则vn中每个n—重 ( a 0 , a 1 ,  , a n  可以表1)e 示成 ( e 0 ,  , e n  1 ) 的线性组合： 1,

(a0,a1,a2,,an1)a0e0a1e1a2e2an1en1

所以 e 0 ,e 1 ,  , e n  1 张成GF（2）所有n—重的矢量空间。从上述方程可以看出 e0,e 1 ,  , e n 是线性的。因此，它们构成vn的基底，且vn的维数是n，若k“1”每次右移一位

uc1v1c2v2ckvk

的线性组合构成vn的一个k一维子空间S。由于每个ci有两个可能的取值0或1，故有2k个可能不相同的 v 1 , v 2 ,  , v k 的线性组合。因此，S由2k个矢量组成且为vn的一个k一维子空间。

u n 1 ) 和 v 令 u  ( u 0 , u 1 , , ( v 0 , v 1 , , v n 1 ) 是vn中的两个n—重。这里定义u和v

的内积（或点积）为

uvu0v0u1v1un1vn1（5-3）

u iu  v其中 u i  v i 和 u i  v i  1  v i 1 按模2乘法和加法进行。因而内积 是GF（2）中的标

u  v0，就称u和v彼此正交，内积有下述性质： 量。若 

14

v  ui) u  v 

u  wii) u  ( v  w )  u  v 

au)va(uv)iii) (

（内积的概念可以推广到任意伽罗华域）

令S是vn的k维子空间，并令Sd是vn中这样的矢量集合：对S中的任意u和Sd中的任

u  v意v有  0 。集合Sd至少包含全零n—重，0=（0，0，…，0），因为对S中的任一u

有 0  0 。因此Sd是非空的。对GF（2）中任一元素a和Sd中任一v， u 0若a0avv若a1

v所以 a 也在Sd中。令v和w是Sd中任意两个矢量。对S中任意u，

u( v u  v u0 。这就是说，若v和w正交于u，则矢量v+w也与u w )   w  0  0 

正交。因而，v+w也是Sd中一个矢量。由定理5.1得出， Sd也是vn的一个子空间。这个子空间Sd称作是S的零化（或对偶）空间。反之，S也是Sd的零化空间。Sd的维数由定理5.3给定。

定理5.3 令S是GF（2）上所有n—重的矢量空间中的一个k一维子空间，则其零化空间Sd的维数为n-k。换句话说，dim（s）+dim（sd）= n。

例5-5 分析例5-1给定的GF（2）上所有5-重的矢量空间v5。下述8个矢量构成v5的一个3-维子空间S，

(00000),(11100),(01010),(10001)(10110),(01101),(11011),(00111)S的零化空间由以下4个矢量组成：

(00000),(10101),(01110),(11011)

Sd由线性的（10101）和（01110）张成。因此，Sd 的维数是2。

本节给出的所有结果都可直接地推广到GF（q）上所有 n—重 的矢量空间，其中q是一素数幂。

6． 矩阵

GF（2）上（或任意其他域上）k×n阶矩阵是一个有k行和n列的长方阵：

g00g10Ggk1,0g01g11gk1,1g02g12gk1,2g0,n1g1,n1gk1,n1（6-1）

其中每个个元素 g ij ， 0  i 和 n ，都是取自二元域GF（2）中的元素。第一个下 k0 j 标i表示行，第2个下标j表示列。有时以符号 [ g ij ] 来简化表示矩阵（6-1）式。从（6-1）式中看可出，G的每一行都是GF（2）的一个n—重，每一列都是GF（2）上的一个k—重。矩阵G也可用它的k行 g 0 , g 1 ,  , g k  1 表示如下：

15

g0gG1gk1

若G的k行（k≤n）是线性的，则这些行的2k个线性组合形成GF（2）上所有n

—重的矢量空间vn的k一维子空间。这个子空间称为G的行空间，我们可以交换G中任意两行或将一行加到另一行。这些称作是初等行运算。对G进行初等行运算我们得到GF（2）上的另一个矩阵Gˊ。但是，G和Gˊ都给出同一行空间。

例6-1 分析GF（2）上一个3×6阶矩阵G，

110110G001110010011

第三行加到第一行，且第二行和第三行交换，可得到下列矩阵，

100101G010011001110

G和Gˊ都给出如下的行空间，

(000000),(100101),(010011),(001110)(110110),(101011),(011101),(111000)

这是GF（2）上所有6—重矢量空间v6的一个3—维子空间。

令S是GF（2）上一个k×n阶矩阵G的行空间，其k行 g 0 , g 1 ,  , g 1 线性。令kSd是S的零化空间，则Sd的维数是n-k。令 ,  , h n  k 1 是Sd中n-k个线性矢量。h 0 , h1显然，这些矢量张成Sd。我们可以用 h 0 , h 1 k  1作为行构成一个（n-k）×n阶矩阵H， ,,hnh0h00hh10H1hnk1hnk1,0h01h11hnk1,1h0,n1h1,n1hnk1,n1

g i 是 s中的矢量，且H的每一行hi是Sd中的矢量，H的行空间是Sd。由于G的每一行

则gi和hI的内积必是零 (即 g i  h i  0 ) 。由于G的行空间S是H的行空间Sd的零化空间，故我们称S是H的零化（或对偶）空间。综合以上结果可得到：

定理6.1 对GF（2）上有k个线性行的任意k×n阶矩阵，都存在一个有（n-k）个

 0线性行的（n-k）×n阶矩阵，使得对G中任一行 g i 和H中任意行 h j有 g i  h j 。

G的行空间是H的零化空间，反之亦然。

16

例6-2 研究下述GF（2）上的3×6阶矩阵。

110110G001110010011

101100

 1这一矩阵的行空间是 H  0 1 0 1 0 的零化空间。  110001

我们容易验证G的每一行都和H的每一行正交。

a ij 若两个矩阵有相同的行数和相同的列数，它们就可以相加。两个k×n阶矩阵 A 

和 B  b ij 相加，我们简单地将它们的相应元素 a ij 和 b ij 相加如下：

abaijijijbij

因此，得到的矩阵也是k×n阶矩阵。两个矩阵只要第一个矩阵的列数等于第二个矩阵的行数就可以相乘。k×n阶矩阵 A  a ij 乘以 n ij 的积  l 阶矩阵 B  bCABcij 是 k  l 阶矩阵，其元素 c ij 等于A中第i行 a i和B中第j列 b i 的内积，即

cijaibjaijbiji0n1

令G是GF（2）上一个k×n阶矩阵，用GT表示G的转置，它是一个n×k阶矩阵。它的各行是G的各列，而它的各列是G的各行。一个k×k阶矩阵。若在主对角线上都为1而其它处为0。就称作是恒等矩阵。这一矩阵通常用1k表示。矩阵G的子阵是由除去G的给定行或列所得到的矩阵。

17