编码理论基础

编码理论基础包括群、域、本原多项式、伽罗华域算术。

1． 群令G 是一个集合。

现规定G 上的二元运算“*”的规则：对G 中的每一对元素a 和b ，在G 中指定一个唯一确定的第三个元素c=a *b 。

当这样的二元运算“*”定义在G 上时，我们就称在“*”运算下G 是封闭的。

若对G 中的任意元素a 、b 、c 有则称G 上的二元运算“*”是结合的。

定义1.1 设G 是非空集合。

并在G 上定义了一种运算“*”，如果满足以下条件就称做群：（1） 满足封闭性。

若a 和b 为集合G 中的任意元素，即a ∈G ，b ∈G ，恒有（2） 结合律成立，对任意a ∈G ，b ∈G ，c ∈G ，（3） G 中存在一个恒等元e ，对任意a ∈G ，有其中a -1∈G ，且称为a 的逆元素。

例如，整数中，任意两个整数相加还是一个整数，因此满足封闭性；显然也满足结合律；任意一个非零整数Z 的逆元素是-Z ，Z+（-Z ）=0，所以恒等元是0。

则整数在实数加法下是一个群。

但整数在实数乘法下就不能构成一个群。

若群G 中，a ∈G ，b ∈G ，有则称群为可交换群或阿贝尔群。

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

定理1.2 令H 是G 的非空子集。

若H 在G 的群运算下是封闭的且满足群的所有条件，就称H 为G 的子群。

例如，偶数是整数的一个非空子集。

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

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

2． 域域就是一个集合，在其中可以进行加、减、乘、除而不会超出该集合。

加法和乘法都必须满足交换律、结合律和分配律，正式定义：定义2.1 令F 是一个集合，其上定义了两个二元运算，称做加法“+”和乘法“·•”。

满足下述条件时，就称集F 和两个运算“+”和“·”是域：cb ac b a **=**)()(Gc b a ∈=*cb ac b a **=**)()(ea a =*-1ab b a *=*（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对于任何素数p 都存在一个有p 个元素的有限域。

对于任何正整数m ，可以将素域GF （p ）扩展成有p m 个元素的域，称它为GF （p ）的扩域，并以GF （p m ）表示。

而且已证明，任意有限域的阶是素数的幂次。

有限域以其发现者命名为伽罗华域。

大部分代数编码理论，码的构造和译码是围绕有限域建立的。

研究q 个元素的有限域GF （q ）。

因为在加法下域是封闭的，两个元素之和也是域中的元素，即必存在两个正整数m 和n ，m<n ，使则可得 。

所以，必存在一个最小正整数λ（读lamuda ）使 。

这一整数λ叫做域GF （q ）的特征。

二元域GF （2）的特征是2，1+1=0。

素域GF （p ）的特征是p ，因为1≤k<p ，定理2.1：有限域的特征λ是素数.∑∑===m i ni 1111∑-==m n i 101∑==λ101i ∑∑===≠=pi k i k 11101且定理2.2：令a 是有限域GF （q ）中的非零元素，则a q-1=1。

定理2.3：令a 是有限域GF （q ）中的非零元素，令n 是a 的阶，则q-1能被n 除尽。

在有限域GF （q ）中，若非零元素a 的阶是q-1，就称a 是本原的。

所以，本原元素的各次幂生成GF （q ）的所有非零元素，每个有限域都有本原元素。

若在群中存在一个这样的元素，其各次幂构成整个群，就称该群是循环的。

若a 为循环群中的本原元素，使a n =e 的最小整数n 为循环群的级。

有限循环群的性质。

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

性质2：若a 是n 级元素，则元素a k的级为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 x 3+x+1=0，由模m 加法可得x 3=x+1，x= x 3+1，若a 是多项式的根，则a 的所有幂次为：以上分析可知，a 的所有幂次共有七个非零元素，再加上0元素，构成了含有八个元素的域GF （23），它是GF （2）的三次扩域。

可见，x 3+x+1是既约多项式。

那么，是不是凡是二元域上的既约多项式的根都能构成m 次扩域GF （2m ）。

为了说明这个问题，再看一个例子。

如：x 4+x 3+x 2+x+1aa a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a a aa a a a a a a a a a a =⋅=⋅==++=+=+⋅=⋅=+=+++=++=++⋅=⋅=++=+=+=⋅=+=+⋅=⋅=+====111)1(11)1(1)()1(110001000178326722232562232452343210010001101111110011100010001对应三位二进制数对应三位二进制数对应三位二进制数对应三位二进制数对应三位二进制数对应三位二进制数对应三位二进制数对应三位二进制数对应三位二进制数0010000111111110000100001000011652343210⇒=⇒=⇒+++=⇒⇒⇒=⇒=a a a a a a a a a a a我们发现，a 的所有幂次仅有五个元素，加上零元素共有6个，而不是24个，所以x 4+x 3+x 2+x+1不能构成GF （24）扩域。

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

例2：令m=4，多项式p （x ）=x 4+x+1，是GF （2）上的本原多项式。

设p （α）=α4+α+1=0，则α4=α+1。

利用此式可构造GF （24）。

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

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

所以α是扩域GF （24）的本原元素。

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

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

它的根是GF （2m ）扩域中的本原元素，这一类多项式称为本原多项式。

另一类既约多项式既能被x n +1整除，又能被x 5+1整除，称为非本原多项式。

只有本原多项式的根才能构成GF （2m ）域。

4． 伽罗华域GF （2m）的基本性质在普通代数中我们经常看到，实系数多项式的根不在实数域中，而是在含实数域作为子域的复数域中。

例如，多项式x 2+6x+25在实数域中没有根，但有两个复共轭根：-3+4i 和-3-4i ，共中 。

系数取自GF （2）的多项式也一样。

在此情况下，系数取自GF （2）的多项式可以没有GF （2）中的根，但在GF （2）的扩域中有根。

例如：x 4+x 3+1在GF （2）是上既约的，所以根不是GF （2）中的元素。

它有取自GF （24）的4个根。

如果我们将上例中给出的GF （24）中的元素代入x 4+x 3+1， 就会发现， α7、α11、α13及α14是x 4+x 3+1的根，可以证实：(=α14·α14+α14·α7+1逐步展开)1-=i 01)()1(11)()(:2323212837477=+++++=++=++ααααααααα也可以证实α11、α13、α14三个根。

由于α7、α11、α13、α14是x 4+x 3+1的全部根，则（x+α7）（x+α11）（x+α13）（x+α14）≡x 4+x 3+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 ）的根，则对任何 ，β2也是f （x ）的根。

证明：重复展开上述方程，最终得到：由于 ，因此有：从上式得出，对任意将β代入上式得：元素 称为β的共轭元。

证毕。

定理4.1说明，若GF （2m）中的元素β是GF(2)上的多项式f （x ）的根，则β的所有不相同的共轭元(也在GF （2m ）中)也是f （x ）的根。

如，多项式f （x ）=x 6+x 5+x 4+x 3+1以前例（表3.1）GF （24）中的元素α4为根，为了证实这一点，利用α15=1很容易证明：0≥l []22212022212210221020222102102)()()()()()()(n n n n n n n n n n n n x f x f x f f x f x f x f x f x f x f f x f x f x f f f x f x f x f f x f x f f x f ++++=+++++++⋅++++⋅+=++++=+++= 222221202)()()()(n n x f x f x f f x f ++++= i i i f f f ==2,10或)()()()(222222102x f x f x f x f f x f n n =++++= 0≥l [])()(22llx f x f =[])()(22llf f ββ=.)(,0)(,0)(22的根也是因x f f f llβββ∴==l2βα4的共轭元是：注意 ，由定理4.1得出，α8、α、α2也必是f （x ）=x 6+x 5+x 4+x 3+1的根。