信道编码理论中用到的代数基础

群是抽象代数中最基本的概念。假设 G是一个集合，在G上，我们定义一个二元运算规则 ∗。通过这个二元运算规则和 G中的任意两个元素 a和b，我们可以定义第三个元素 c=a∗b. 当c∈G，我们称 ∗在 G上是封闭的。比如，假设G是所有整数的集合，二元运算是加法，则对于 G中的任意整数 i和j，有(i+j)∈G。我们称所有整数组成的集合在加法下是封闭的。 二元运算 ∗满足结合律，当且仅当 ∀a,b,c∈G：a∗(b∗c)=(a∗b)∗c

现在我们给出群的完整定义：

在一个集合G上定义二元运算，当满足以下条件时我们称G是一个群：

1. 二元运算满足结合律;
2. G中有一个元素 e, ∀a∈G满足： a∗e=e∗a=a
   我们称e是单位元素。
3. ∀a∈G, G中有一个元素a′ 满足: a∗a′=a′∗a=e
   我们称a′是逆元。

群G是交换群，当且仅当对于任何两个元素 a,b∈G，有 a∗b=b∗a

对于群G，单位元素e和逆元都是唯一存在的。对于整数加法群，单位元是0，−i是i的逆元。所有除0以外的有理数构成一个乘法交换群：单位元是1，b/a是a/b的逆元。无论是整数加法群还是除零外的有理数乘法群，其元素个数都是无穷多个。当然，只有有限个元素的群也是存在的，我们称这样的群为有限群。

接下来考虑一个集合 G={0,1}，这个集合只有两个元素，并定义一个二元运算：0⊕0=0,0⊕1=1,1⊕0=1,1⊕1=0

我们称这样的二元运算为模二加。显然，定义了⊕运算的集合G是一个交换群。

群中元素的个数叫做群的阶数。具有有限阶的群叫做有限群。接下来我们来阐述一个事实：对于任何的正整数m，我们都有可能定义一个有限群，群上的二元运算与实数加法非常相似。考虑一个整数集合G={0,1,2,…,m−1} 定义+是实数加法，定义⊞是G上的二元运算满足 i⊞j=r

其中 r=i+jmod(m), 我们称其为模m加。显然0≤r≤(m−1) 并且r∈G.因此在二元运算符号⊞运算下 G是封闭的。对于 0<i<m ， i和m−i都在G中. 因为 i+(m−i)=(m−i)+i=m 所以有i⊞(m−i)=(m−i)⊞i=0 因此，i和m−i在⊞运算下互逆。0的逆是它本身。另外我们还可以证明模m加满足结合律，即(i⊞j)⊞k=i⊞(j⊞k) 综上，我们可以说集合G={0,1,2,…,m−1}在模m加运算下是一个群。我们称这样的群为加法群。我们给出一个模4加群计算中的模4加表如下所示：

Table 1: 模4加法表

⊞	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

接下来我们看一个乘法交换群的例子。假设p是一个素数，考虑集合G={1,2,3,…,p−1}。我们定义⋅为乘法，定义⊡ 为模p乘，具体表示为 i⊡j=r,r=i⋅jmodp

首先我们知道i⋅j不能被p整除，因此 0<r<p 且r是G中的一个元素。进而得出，r是G中的一个元素。可以证明在模p乘运算下，G是一个交换群。

显然1是单位元素。接下来我们证明对于每一个元素i都有且只有一个逆元存在。由于p是一个素数，i<p， i和p之间没有任何大于1的公约数。另外根据欧几里德定理存在两个整数满足 a⋅i+b⋅p=1

其中a,p之间没有除1之外的最大公约数。把上式重排，我们有 a⋅i=−b⋅p+1 这说明a是 i在G中模p乘的逆。值得一提的是当p不是质数时，G不是群。

接下来我们定义子群的概念。假定H是群G的一个子集，那么H是群G的一个子群当且仅当H在群G中的运算下是封闭的。

定理 假设G是二元运算∗下的群。H是G的一个子集，那么H是一个子群，当且仅当：

1. H在二元运算∗ 下封闭；
2. 对于H中的任何一个元素a，其逆也在H中。

接下来我们顶一个非常重要的概念：陪集。假设H是G的一个子群，二元运算为∗，假设a是G中的任何一个元素。那么集合 a∗H≜{a∗h:h∈H}叫做 H的左陪集；集合 H∗a≜{h∗a:h∈H}叫做 H的右陪集。显然，当G是交换群的时候，左陪集等于右陪集。

考虑一个模16加法群G={0,1,2,…,15}。可以检验H={0,4,8,12}是一个子群。对于这个子群有陪集:

0⊞H={0,4,8,12}1⊞H={1,5,9,13}2⊞H={2,6,10,14}3⊞H={3,7,11,15}

事实上，我们可以检验对于H只有这4个陪集。这4个陪集是互斥的，他们的并集构成了G.

定理 子群H的任意两个陪集的交集是空集。

假设a∗H和b∗H是H的两个不同的陪集，且a∗h和b∗h′是a∗H和b∗H中的两个元素。假设a∗h=b∗h′，h−1是h的逆。则有：

(a∗h)∗h−1=(b∗h′)∗h−1a∗(h∗h−1)=b∗(h′∗h−1)a∗e=b∗h″a=b∗h″

其中 h″=h′∗h−1 是H中的一个元素。 a=b∗h″意味着：

a∗H=(b∗h′)∗H={(b∗h″)∗h:h∈H}={b∗(h″∗h):h∈H}={b∗h⁗,h‴∈H}=b∗H

此时，a∗H和b∗H是两个相同的陪集，与假设矛盾。

通过以上几个定理，我们发现群G的子集H的陪集具有以下性质：

1. 每一个G中的元素只出现在H的一个陪集中。
2. H的所有陪集是互斥的，即没有相同的元素。
3. H的所有陪集构成群G，即H的所有陪集是群G的一个划分我们用G/H来表示。

定理 (朗格朗日定理) 假设G是一个阶数为n的群，H是其阶数为m的子群。那么m可以整除n，并且G/H有n/m个H的陪集。

现在基于群的概念，我们引入抽象代数的另一个概念：域。粗略来讲，域是一些元素的集合，在这个集合中加减乘除都是封闭的。并且加法，乘法满足交换律，结合律和分配率。域的正式定义如下：

定义 (域) 令F是一个集合，在该集合上定义两个双目运算：加法+和乘法⋅. 定义了加法和乘法运算的集合F是一个域，当且仅当：

1. F是一个加法交换群。零元是0；
2. F中除0以外的元素是一个乘法交换群。乘法单位元用1表示。
3. F乘法满足分配率，即对F中的三个元素 a,b,c满足 a⋅(b+c)=a⋅b+a⋅c

通过以上定义，我们知道域中必须包含两个元素：加法零元和乘法单位元。域的元素个数叫做域的阶数。如果一个域中元素个数是有限的，我们称这个域是有限域。在一个域中，定义元素a的加法逆元为−a;乘法逆元为a−1,a≠0。从一个域元a中减去另一个元素b定义为a加上b的逆元 −b。如果b是一个非零元，则定义a除以b为a乘以b的逆元b−1。

从域的定义中可以推导出域的一些基本性质：

1. 对于域中每一个元素a， a⋅0=0⋅a=0
2. 对于域中任何两个非零元素a和b，有a⋅b≠0
3. a⋅b=0a≠0意味着：b≠0
4. 对于域中任何两个元素 a和b，有−(a⋅b)=(−a)⋅b=a⋅(−b)
5. 对于a≠0,a⋅b=a⋅c，有b=c

易得，实数在实数加法和乘法下是一个域。这个域有无穷多个元素。接下来我们给一个有限域的例子。

考虑带有模2加法和乘法的集合{0,1}

Table 2: 模2加法表

+	0	1
0	0	1
1	1	0

Table 3: 模2乘法表

⋅	0	1
0	0	0
1	0	1

我们知道{0,1}是一个模2加交换群，{1}是一个模2乘群。同样我们可以很容易的验证模2乘在模2乘下满足分配率。

上面例子中的群我们成为二进制域，用GF(2)表示。GF(2)是一个非常重要的二进制域，这个域在编码理论，计算机理论和通信与存储系统中有广泛的应用。

接下来我们再给一个质数域的例子。假设p是一个素数了，那么{0,1,2,…,p−1}是一个模p加下的交换群，同样我们也知道{1,2,…,p−1}形成了模p的乘法交换群。根据模p加法和乘法定义，结合实数乘法在模p加法下满足乘法分配率。所以，{0,1,2,…,p−1}是一个p阶域。由于这个域是从质数构造而来的所以这个域也叫作质数域。特别的当p=2时，我们有GF(2)。

以p=7为例，集合0,1,2,3,4,5,6是一个模7加法和乘法下的7阶域，用GF(7)表示。加法表对减法也适用。比如，如果我们要计算3−6，首先我们找到−6的加法逆1。然后，把1和3相加，既得4。对于除法，我们使用乘法表。假设要计算32，则我们首先找到2−1的逆3⋅4=5。综上，我们验证了在一个有限域中，加法减法乘法除法可以像普通的代数运算一样进行计算。

我们知道对于任何的质数p，存在一个p阶的有限域。事实上，对于任何的正整数m，可以扩展质数域GF(p)到pm个元素。更进一步，已经证明任何有限域的阶数是质数的幂次方。有限域也叫伽罗华域，这是为了纪念有限域的发明者：法国数学家伽罗华。很大一部分的代数编码理论，码的构建和译码都是基于有限域展开的。在接下来的几个章节，我们会考察有限域的几个基本性质：包括他们的代数结构，质数扩展域的构造。

考虑一个q阶有限域，GF(q)，让我们做以下加法：

1∑i=11=12∑i=11=1+13∑i=11=1+1+1…=…k∑i=11=1+1+…+1⏟k

因为有限域在加法下是封闭的，这些和一定在有限域中；又由于有限域中的元素个数是有限的，这些和不可能无限的加下去而不出现重复。因此在些和组成的序列中一定存在重复，即一定存在两个正整数m和n,m<n 且满足m∑i=11=n∑i=11

这意味着∑n−mi=11=0。因此一定存在一个最小的正整数λ满足∑λi=11=0，我们称λ为GF(q)的特征值。二进制域GF(2)的特征值是2，因为1+1=0。更进一步，质数域GF(p)的特征值是p。因为∑ki=11=k≠0,∀1≤k<p 并且 ∑pi=11=0

定理 有限域的特征值λ是一个质数。 假设λ不是一个质数，那么λ可以表示成两个整数的乘积λ=km，由于域在乘法下是封闭的，则有(k∑i=11)⋅(m∑i1)

也是域中的一个元素 利用分配率，有(k∑i=11)⋅(m∑i1)=km∑i1 由于∑kmi1=0 则，∑ki1或者∑mi1中至少有一个为0；然而这是不可能的，因为λ是满足∑λi1=0的最小整数。矛盾产生，因此λ是一个质数。

因此，我们可以进一步推论，对于GF(p)中的任何两个小鱼λ的正整数k,m，有k∑i1≠k∑i1≠0

同样我们可以用反证法来证明，假设k∑i1≠k∑i1 则有k−m∑i1=0, 不失一般性我们假设k>m. 然而这是不可能的，因为k−m<λ

接下来我们有λ个不相同的数：1=1∑i1,2∑i1,3∑i1,…,λ−1∑i1,λ∑i1=0

. 事实上，这个求和集合本上构成了加法和乘法下阶数为λ的域。由于GF(λ)是GF(q)的一个子集，我们称GF(λ)是GF(q)的一个子域. 因此，我们可以说任何特征为λ 的域GFq都有子域GF(λ). 另外可以证明 如果λ≠q，那么q是λ的幂次方

现在，假设a是域GF(q)中的一个非零元素。由于GF(q)中的所有非零元素在乘法下是封闭的，则下面的a的幂次方序列a1=1,a2=a⋅a,a3=a⋅a⋅a,…

一定全都是GF(q)中的非零元素。又因为GF(q)中元素的格式是有限的，所以a的幂次方序列中元素个数肯定不可能是无限的。因此，在某个点上，一定会出现重复，即：一定有两个整数k,m,m>k，且am=ak。定义a−1是a的逆。则有(a−1)k=a−k是ak的逆。在am=ak两边乘ak的逆，则有am−k=1。这个等式说明一定存在一个最小的正整数n满足an=1，我们称这个整数是元素a的阶。因此序列a,a2,a3,…在an=1之后重复。同时，a1,a2,a3,…,an−1,an=1互不重复。事实上，这个序列中的元素集合构成了GF(q)下的乘法群。首先，我们知道这个集合包含单位元1，然后考虑ai⋅aj,如果i+j≤n 则ai⋅aj=ai+j。如果i+j>n，我们有i+j=n+r,0<r≤n，因此ai⋅aj=ai+j=an⋅ar=ar 因此，幂序列a1,a2,a3,…,an−1,an=1 在GF(q)乘法下是封闭的。an−i,1≤i<n的逆是ai。又因为a的幂在GF(q)中是非零的，它们又满足交换路和结合律。因此a1,a2,a3,…,an−1,an=1构成了GF(q)下的交换群。

如果群中的一个元素的幂构成这个群中的所有元素，那么这个群是交换群。

定理 如果a是有限域GF(q)中的非零元素，那么aq−1=1

证明：假设b1,b2,…,bq−1是q−1个GF(q)的非零元素，那么q−1个元素a⋅b1,a⋅b2,…,a⋅bq−1非零且各不相同。因此：

(a⋅b1)⋅(a⋅b2)⋅(a⋅bq−1)=b1⋅b2…bq−1aq−1⋅(b1⋅b2…bq−1)=b1⋅b2…bq−1

由于a≠0 并且b1⋅b2…bq−1≠0,因此aq−1=1

定理 令a 是GF(q)域的非零元素，n是a的阶数，则n整除q−1

证明：采用反证法。假设n不整除q−1，则q−1=kn+r,0<r<n

aq−1=akn+r=aknar 因为aq−1=an=1所以一定有ar=1 因为 0<r<n且n是满足an=1的最小整数 ，矛盾产生。因此 n一定整除q−1.

在有限域GF(q)中 ，一个非零元素a是本源的，如果a的阶数是q−1. 因此一个域的本源元素生成了该域中的所有非零元素。每一个有限域中含有一个本源元素。

以GF(7)为例，该域的特征值为7， 如果我们计算3的幂会

31=332=233=634=435=536=1

我们发现3的阶数是6，并且3生成了所有的GF(7)中的元素，所以3是GF(7)中的本源元。对于整数4，我们有

41=442=243=1

因此4的阶数是3，3是6的一个因子。

原则上讲，基于GF(q) （q是质数或者质数的幂），我们可以构建任何编码方案。但是在数字通信系统中，基于GF(2)或者GF(2m)的码是用的最多的编码方案。因此在这一节我们着重讨论二进制域上的代数运算。

在二进制域中，我们使用模2的加法和乘法。事实上这些代数和普通的代数运算没有什么区别，需要注意的是在GF(2)中2=0.比如1+1=2=0。另外需要注意1+1=0所以1=−1。因此在二进制域中减法等于加法。为了演示在二进制域中的计算我们考虑下面的方程组：

X+Y=1X+Z=0X+Y+Z=1

这个方程可以通过第一和第三个方程相加，得到Z=0。然后，利用第二个方程，得X=0；利用第一个方程Y=1。

因为我们可以唯一解这个方程，所以这个方程一定是线性独立的，左边部分行列式的值一定非零。如果行列式值非零又是在GF(2)上的行列式，那么行列式一定1。因此我们可以通过Cramer准则解这个方程。

X=|110001111||110101111|=01=0 Y=|110101111||110101111|=11=1 Z=|111100111||110101111|=01=0

接下来我们考虑计算GF(2)域的多项式计算。单变量多项式f(X)表示为：

f(X)=f0+f1X+f2X2+…+fnXn

其中fi=0或者1。多项式的度是多项式中具有非零洗漱的X的最大幂次。如果fn=1，那么f(X)是一个度为n的多项式。如果fn=0，那么f(X)是一个度小于n的多项式。f(x)=f0的度是0。

一共有两个度为1的多项式，分别是X和1+X。一共有四个度为2的多项式：非别是X2,1+X2,X+X2,1+X+X2. 推而广之，一共有2n个度为n的GF(2)多项式。

GF(2)多项式可以执行加减乘除运算。假设g(x)=g0+g1X+g2X2+…+gmXm

，则

f(X)+g(X)=(f0+g0)+(f1+g1)X+…+(fm+gm)Xm+fm+1Xm+1+…+fnXn

其中fi+gi是模2加。例如，a(X)=1+X+X3+X5 b(X)=1+X2+X3+X4+X7。我们有：

a(X)+b(X)=(1+1)+X+X2+(1+1)X3+X4+X5+X7=X+X2+X4+X5+X7

当我们f(X)和g(X)相乘时，有: f(X)⋅g(x)=c0+c1X+c2X2+…+cn+mXn+m

其中:

c0=f0g0c1=f0g1+f1g0c2=f0g2+f1g1+f2g0⋮=⋮ci=f0gi+f1gi−1+f2gi−1+…+fig0⋮=⋮cn+m=fngm

乘法和加法结果中的系数都是GF(2)中计算得出的。显然如果g(X)=0则f(X)⋅0=0. 我们可以很快确认在二进制域中，多项式满足如下性质：

交换律 :

a(X)+b(X)=b(X)+a(X)a(X)⋅b(X)=b(X)⋅a(X)

结合律 ：

a(X)+[b(X)+c(X)]=[a(X)+b(X)]+c(X)a(X)⋅[b(X)⋅c(X)]=[a(X)⋅b(X)]⋅c(X)

分配率 :

a(X)⋅[b(X)+c(X)]=a(X)⋅b(X)+a(X)⋅c(X)

假设g(X)是非零多项式，则用g(X)去除f(X)我们会得到一个唯一的GF(2)多项式q(X)，我们称之为商多项式，另外还有r(X)我们称之为余多项式。f(X)可以表示为f(X)=q(X)g(X)+r(X)

其中r(X)的度小于g(X)的度。上式成为欧几里得算法。作为一个例子我们假设f(X)=1+X+X4+X5+X6,g(X)=1+X+X3，用我们小时候学过的长除法，我们有：X6+X5+X4+X+1=(X3+X2)(X3+X+1)+X2+X+1 我们注意到x2+X+1的阶数小于g(X)的阶数。

如果r(X)=0，我们说g(X)可以整除f(X)，g(X)是f(X)的一个因子。