信息与编码理论 第2版 课件 6.1 有限域

第6章BCH和RS码本章内容：6.1有限域6.2BCH码6.3RS码6.4BCH和RS码的仿真实例§6.1有限域6.1.1有限域的定义阿贝尔群（AbelianGroup）对于集合，定义符号“”表示一种二进制运算，如果满足下面的条件则称该集合为阿贝尔群：该运算具有交换律。即对于任意，有；该运算具有结合律。即对于任意，有；该运算具有可以用“0”表示的幺元（IdentityElement）。即对于任意，有；对于任意一个元素，均存在元素满足，其中元素称为的加法逆。因此，一个阿贝尔群通常可以记作。注意：阿贝尔群也可以改用符号“

”表示的“乘法”运算来定义，此时幺元可以用符号“1”来表示，而该群可以记作，此时元素的乘法逆则可以表示为。有限域（伽罗华域，GaloisField）对于有限个元素构成的一个集合，定义了分别用“”和“”表示的加法和乘法两种二进制运算，如果满足下列条件则称该集合为有限域：是一个阿贝尔群；也是一个阿贝尔群，即集合中的非零元素在乘法运算下也构成一个阿贝尔群；乘法满足分配律：。综上，一个有限域常常记作。显然，由所有实数构成的集合在正常的加法和乘法运算下是一个域（但不是有限域）；集合在模2加法和乘法运算下构成一个有限域，称为二进制域，记作。二进制域上的加法和乘法运算规则如下表：6.1.2域的特征和基域有限域存在的充要条件包含个元素的有限域存在的充要条件是，式中是一个素数，是一个正整数。对于有限域该域在同构（Isomorphism）意义下是唯一的。这意味着任何两个相同尺寸的有限域在重新命名元素之后可以相互转化。对于某素数：当时得到的有限域可以表示成该域中的两种运算是模加法和乘法，例如；当时得到的有限域称为的扩展域（ExtensionField），其中，而称为的基域（GroundField），称为有限域的特征（Characteristic）。6.1.3有限域上的多项式有限域上的多项式有限域上的阶多项式可以表示为

(6-1)式中是取自于上的元素，，且。定义在有限域上的多项式之间的加法和乘法遵循正常的加法和乘法规则，但是多项式系数之间的加法和乘法要按照模运算。首一多项式（MonicPolynomial）如果式(6-1)中的，则该多项式称为首一多项式。不可约多项式（IrreduciblePolynomial）如果定义在上的阶多项式不能分解为同一个域上的两个低阶多项式的乘积，则称该多项式为不可约多项式。例如在有限域上，是一个不可约多项式，而则不是一个不可约多项式，因为。素多项式（PrimePolynomial）同时满足首一和不可约性质的多项式称为素多项式。多项式的根有限域上的阶多项式会有个根（有些可能是重根）。6.1.4扩展域的结构对于有限域上的多项式，根据定义可知阶小于的多项式一共有个，其中包括和两个特殊多项式。扩展域的生成假设是一个上的阶素多项式，那么由上所有阶小于的多项式组成一个集合，该集合中元素之间的运算遵循正常的加法和模的多项式乘法，这样得到的多项式集合构成了一个有限域：该有限域显然是的一个扩展域。【例6-1】利用有限域上的素多项式来构造扩展域。【解】显然，上阶小于2的所有多项式为：0，1，和。这些元素构成的集合便是所求的扩展域：

(6-2)元素之间的加法和乘法运算规则分别如下面两表所示。表6-2GF(4)的加法表6-3GF(4)的乘法所有非零元素均可以表示成的某次幂：

【例6-2】利用有限域上的素多项式来构造扩展域。【解】上阶小于3的所有多项式构成的扩展域为

(6-3)容易验证，该域中所有非零元素都可以写成的某次幂的形式：，，，，，，另外，中各元素也可以用式(6-3)中各个多项式对应的长度为3的系数向量来表示。所以，扩展域中各元素共有三种等价的表示方法，如下页的表6-4所示。表6-4GF(8)元素的三种表示当计算扩展域中元素之间加法的时候，使用多项式形式或向量形式比较简便：当计算元素之间乘法的时候，使用幂形式比较简便：6.1.5本原元素和本原多项式元素的阶（Order）对于任意一个非零元素，满足等式的最小整数称为元素的阶。可以证明等式一定成立，所以元素的阶的最大值等于。本原元素（PrimitiveElement）如果的某个非零元素的阶为，则称该元素为本原元素。本原元素最为重要的特性是：其各次幂可以生成所在有限域的所有非零元素。本原元素不是唯一的。本原多项式（PrimitivePolynomial）设由素多项式生成，如果是的一个本原元素，则称为本原多项式。可以证明：任意阶的本原多项式都存在。所以对于任意的正整数和任意一个素数，均可以生成为本原元素的扩展域，也就说该域中所有的非零元素都可以表示为

，在后面的内容中，均假设有限域是由本原多项式生成的。【例6-3】和都是上的两个4阶素多项式，二者都可以用来生成，请判断它们是不是本原多项式。【解】只需判断下分别由和生成的有限域中元素是否为本原元素即可。（1）首先考查由生成的，元素的各次幂分别为：，，，，，，，，，，，，，，所以是本原元素，从而可知是本原多项式。（2）接着来考查由生成的，在该种情况下元素的各次幂分别为：，，，，所以此时的阶为5，不是本原元素，于是可知不是本原多项式。本原多项式的另一种定义可以证明，上的任意阶素多项式均可以整除。但是，也可能整除，其中。例如，素多项式可以整除，也可以整除。令表示可以使素多项式整除的最小整数，如果，则是一个本原多项式。该定义表明：当时，本原多项式不能整除。显然，阶本原多项式的所有根都将是的本原元素。常用的本原多项式下表给出了时的一些本原多项式：表6-5常用本原多项式【例6-4】利用本原多项式来构造，如果是的一个根，请给出的所有元素。【解】因为是本原多项式的根，所以也是的一个本原元素，于是的所有非零元素都可以写作的形式，其中。表6-6给出了中元素的三种等价表示形式。表6-6GF(16)的元素，，，四个元素的阶均为5；，两个元素的阶为3；，，，，，，，八个元素的阶是15，故均为本原元素。6.1.6最小多项式和共轭元素最小多项式（MinimalPolynomial）某个域元素的最小多项式是指以该元素为根的基域上最低阶的首一多项式。设是上的一个非零元素，则的最小多项式是指系数在上，且满足的最低阶首一多项式。显然，是上一个素多项式，可以整除上以为根的所有其它多项式，例如是上满足的任意一个多项式，则其可以表示成。共轭（Conjugates）和共轭类（ConjugacyClass）任意元素的最小多项式可以表示为

(6-4)式中是满足的最小整数。由上式可知，除了之外的其它所有根均具有形式（），所有这些根都称为的共轭。具有相互共轭关系的所有元素被称为属于同一个共轭类。可以证明：一个有限域中任意元素的共轭均会具有相同的阶，于是本原元素的共轭也会是本原元素。但是，具有相同阶的元素之间却不一定是共轭关系。求解元素的最小多项式的步骤：确定共轭类，即所有具有形式的元素，式中，是满足的最小正整数；使用下式来确定，该式便是以的共轭类为根的首一多项式。上述步骤获得的最小多项式一定会是系数在上的素多项式。【例6-5】确定中所有元素的共轭类与最小多项式。【解】由表6-6可知，如果元素是一个本原元素，因为，所以，于是该元素的共轭类为，其最小多项式为

对于