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

群是抽象代数中最基本的概念。假设 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加表如下所示：

接下来我们看一个乘法交换群的例子。假设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}是一个子群。对于这个子群有陪集:

事实上，我们可以检验对于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的逆。则有：

其中 h^{''} = h^{'}*h^{-1} 是H中的一个元素。 a=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是一个集合，在该集合上定义两个双目运算：加法+和乘法\cdot. 定义了加法和乘法运算的集合F是一个域，当且仅当：

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

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

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

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

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

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

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

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

接下来我们再给一个质数域的例子。假设p是一个素数了，那么\{0,1,2,\ldots,p-1\}是一个模p加下的交换群，同样我们也知道\{1,2,\ldots,p-1\}形成了模p的乘法交换群。根据模p加法和乘法定义，结合实数乘法在模p加法下满足乘法分配率。所以，\{0,1,2,\ldots,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。对于除法，我们使用乘法表。假设要计算\frac{3}{2}，则我们首先找到2^{-1}的逆3\cdot 4 = 5。综上，我们验证了在一个有限域中，加法减法乘法除法可以像普通的代数运算一样进行计算。

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

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

因为有限域在加法下是封闭的，这些和一定在有限域中；又由于有限域中的元素个数是有限的，这些和不可能无限的加下去而不出现重复。因此在些和组成的序列中一定存在重复，即一定存在两个正整数m和n, m < n 且满足\sum_{i=1}^{m}1=\sum_{i=1}^{n} 1 这意味着\sum_{i=1}^{n-m}1=0。因此一定存在一个最小的正整数\lambda满足\sum_{i=1}^{\lambda}1=0，我们称\lambda为GF(q)的特征值。二进制域GF(2)的特征值是2，因为1+1=0。更进一步，质数域GF(p)的特征值是p。因为\sum_{i=1}^{k}1 = k \neq 0, \forall 1\leq k < p 并且 \sum_{i=1}^{p}1 = 0

定理 有限域的特征值\lambda是一个质数。 假设\lambda不是一个质数，那么\lambda可以表示成两个整数的乘积\lambda = km，由于域在乘法下是封闭的，则有\left(\sum_{i=1}^{k}1 \right)\cdot \left(\sum_{i}^{m}1\right) 也是域中的一个元素 利用分配率，有\left(\sum_{i=1}^{k}1 \right)\cdot \left(\sum_{i}^{m}1\right) = \sum_{i}^{km}1 由于\sum_{i}^{km}1 = 0 则，\sum_{i}^{k}1或者\sum_{i}^{m}1中至少有一个为0；然而这是不可能的，因为\lambda是满足\sum_{i}^{\lambda}1 = 0的最小整数。矛盾产生，因此\lambda是一个质数。

因此，我们可以进一步推论，对于GF(p)中的任何两个小鱼\lambda的正整数k,m，有\sum_{i}^{k}1 \neq \sum_{i}^{k}1 \neq 0 同样我们可以用反证法来证明，假设\sum_{i}^{k}1 \neq \sum_{i}^{k}1 则有\sum_{i}^{k-m}1 = 0, 不失一般性我们假设k > m . 然而这是不可能的，因为k - m < \lambda

接下来我们有\lambda个不相同的数：1= \sum_{i}^{1}1, \sum_{i}^{2}1,\sum_{i}^{3}1, \ldots, \sum_{i}^{\lambda -1}1, \sum_{i}^{\lambda}1=0. 事实上，这个求和集合本上构成了加法和乘法下阶数为\lambda的域。由于GF(\lambda)是GF(q)的一个子集，我们称GF(\lambda)是GF(q)的一个子域. 因此，我们可以说任何特征为\lambda 的域GF{q}都有子域GF(\lambda). 另外可以证明 如果\lambda \neq q ，那么q是\lambda的幂次方

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

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

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

证明：假设b_{1},b_{2},\ldots,b_{q-1}是q-1个GF(q)的非零元素，那么q-1个元素a\cdot b_{1}, a\cdot b_{2}, \ldots , a\cdot b_{q-1}非零且各不相同。因此：

由于a\neq 0 并且b_{1}\cdot b_{2}\ldots b_{q-1}\neq 0,因此a^{q-1}=1

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

证明：采用反证法。假设n不整除q-1，则q-1 = kn +r, 0 < r < n a^{q-1} = a^{kn+r} = a^{kn}a^{r} 因为a^{q-1} = a^{n} =1所以一定有a^{r}=1 因为 0 < r < n且n是满足a^{n}=1的最小整数 ，矛盾产生。因此 n一定整除q-1.

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

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

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

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

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

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

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

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

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

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

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

GF(2)多项式可以执行加减乘除运算。假设g(x) = g_{0} + g_{1}X + g_{2}X^{2} + \ldots + g_{m}X^{m}，则

其中f_{i} + g_{i}是模2加。例如，a(X) = 1+ X + X^{3} + X^{5} b(X) = 1 + X^{2} + X^{3} + X^{4} + X^{7}。我们有：

当我们f(X)和g(X)相乘时，有: f(X)\cdot g(x) = c_{0} + c_{1}X + c_{2}X^{2} + \ldots + c_{n+m}X^{n+m} 其中:

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

交换律 :

结合律 ：

分配率 :

假设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+X^{4}+X^{5}+X^{6},g(X)=1+X+X^{3}，用我们小时候学过的长除法，我们有：X^{6}+X^{5}+X^{4}+X+1=(X^{3}+X^{2})(X^{3}+X+1) + X^{2} + X + 1 我们注意到x^{2} + X + 1的阶数小于g(X)的阶数。

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