07纠错编码代数基础

1、第7章 纠错编码代数基础 内容提要 抽象代数又称近世代数，其研究对象是定义在某些运算下的集合，运算对象可以是数、多项式、矢量、矩阵、线性空间等。编码理论是建立在码的代数结构基础上的，为便于初学者理解，本章简单介绍抽象代数中与编码直接相关的基础知识，主要涉及整数及多项式的一些基本概念及群、环、域的基本知识。7.1 群 7.1.1 群的定义 1. 整数的相关概念定理7.1 设a为整数，d为正整数，且a d，则存在唯一的整数q 、r满足a = qd + r ，0 r d 。d称作模，r称作余数，r可记作a mod d 。由于0 r p (x)，一定存在唯一的多项式q (x)和r (x)，使 f (x

2、) = q (x) p (x) + r (x) 0 r (x) p (x) p (x)称作模多项式，r (x)称作余式，r (x)记为f (x) mod p (x) 。定理7.7 任何首一多项式可分解为首一即约多项式之积： 定理7.8 一定存在多项式m (x)、n (x)，使 m (x) a (x) + n (x) b (x) = (a (x), b (x) (a (x), b (x)为多项式a (x)、b (x)的最大公因式 2. 环的定义 环是一些元素构成的集合，该集合中定义加法和乘法两种运算，满足： l (1) 对加法是一个交换群； l (2) 对乘法具有封闭性和结合律； l (3) 满

3、足分配律 ：对任何a , b , c F ，有： a ( b + c ) = ab + ac ( a + b ) c = ac + bc 3. 子环 设F是一个环，S是F的一个非空子集，若S对加法和乘法也构成一个环，则称S是F的一个子环，F是S的一个扩环。 理想 理想是一类特殊的子环。设F是一个可换环，I是F的一个非空子集，如果对任意a , b I，恒有a - b I，及对任意a I和任意 x F，恒有ax = xa I，则称I是F的一个理想。 定理7.9 若S是环F的一个非空子集，则S是F的子环的充要条件是：对任何a , b S，有a - b S和ab S 。 主理想 在可换环F中，由一个元

4、素a F的所有倍数及其线性组合而生成的理想I a = xa + na x F , n Z 称为环F的一个主理想，元素a为该主理想的生成元。4. 环的同构 设A和B是两个环，若存在一个A到B的一一对应关系f，并且满足：对任何a , b A，有 f (a + b) = f (a) + f (b) f (a b) = f (a) f (b) 则称f是环A到环B的一个同构。7.2.2 整数剩余类环 模d的余数全体F = 0 , 1 , , d - 1对模d加法运算构成加法交换群；对模d乘法运算满足封闭性、结合律和交换律；还满足分配律，因此模d的余数全体构成交换环，称作整数剩余类环。+ 0 1 d 2d

5、 - 1 0 0 1 d 2d - 1 1 1 2 d - 10 d - 2d - 2d - 1 d - 4d - 3d - 1 d - 1 0 d - 3d - 2表7-6 0 , 1 , , d - 1的模d加法表 7.2.3 多项式剩余类环 以p(x)为模的多项式的余式全体对模p (x)的加法运算构成加法交换群；模p (x)的余式全体对模p (x)乘法满足封闭性、结合律和交换律；其分配律为 a (x) + b (x) c (x) mod p (x) = a (x) c (x) + b (x) c (x) mod p (x) a (x) b (x) + c (x) mod p (x) =

6、a (x) b (x) + a (x) c (x) mod p (x) 因此模p (x)的余式全体对模p (x)的运算构成交换环，称作多项式剩余类环。7.3 域 7.3.1 域的定义 域是一些元素构成的集合，该集合中定义加法和乘法两种运算，满足：l(1) 对加法构成交换加群。l(2) 非零元素全体对乘法构成交换乘群。l(3) 加法和乘法间具有分配律 a (b + c) = ab + ac (a + b) c = ac + bc 域的阶 域中元素的个数。如整数域和复数域、实数域的阶都是无穷值。 有限域 元素个数有限的域，用GF(q)表示q阶有限域。如上例可表示为GF(8) = 0 , 1 , a

7、 , a2 , a3 , a4 , a5 , a6 7.3.2 有限域 定理7.10 设d为素数，则以d为模的整数剩余类环构成d阶有限域GF(d)。 定理7.11 设p(x)为系数取自GF(q)上的n次即约多项式，则以p(x)为模的多项式剩余类环构成qn阶有限域GF(qn)。定理7.12 有限域的阶必为其子域阶之幂，即Q = qn。 7.3.3 有限域的本原元 定理7.13 元素个数相等的有限域必同构。 本原元 在GF(q)中，某一元素 的阶为q - 1，即 q-1 = e (q 1 是使等式成立的最小正整数)，则称 为本原元。 本原元多项式 是以本原元为根的即约多项式。 7.3.4 有限域的

8、结构 定理7.14 GF(q)的所有元素都是方程xq x = 0的根，反之，方程xq x = 0的根必在GF(q)中。 l有限域的特征 是有限域中乘法单位元e关于加法的级，也就是使p e = 0的最小正整数p。 定理7.15 有限域的特征必为素数。 l素域 是GF(q)的最小子域，表示为GF(p) = 0 , e , 2e , , (p - 1)e。 定理7.16 有限域的阶必为其特征之幂，即q = pm。 定理7.17 在以p为特征的域GF( q )中，对于任意、 GF( q )，恒有( + ) p = p + p 推论1 若1 , 2 , k是以p为特征的域中的元素，则对任意正整数n恒有

9、7.3.5 有限域的共轭根组 定理7.18 对GF(pm )中的任意元素 ，恒有。 定理7.19 设f ( x)是系数取自GF( p )的k次即约多项式， GF( pm )，若 是f ( x)的根，则(0 r k )也是f ( x)的根。 l最小多项式 系数取自GF(p )，且以 GF( pm )为根的所有首一多项式中，必有一个次数最低的多项式，称作 的最小多项式。 最小多项式的性质：l(1) 最小多项式在GF( p )上是即约的l(2) 每一 GF( pm )，必有唯一的最小多项式。l(3) 的最小多项式能整除任何以 为根的多项式。 推论2 设m1 (x) , m2 (x) , , mt (

10、x)为GF( pm )中各元素的最小多项式，那么可将多项式在GF( p )上分解为 7.3.6 有限域的综合举例 【例7.25】 在GF(2 ) = 0 , 1系数域上，以p (x) = x4 + x + 1为模构成有限域GF(24 )，在GF(2 )上分解多项式x16 x 。 解：(1) 由于GF(2 ) = 0 , 1，e = 1，1 + 1 = 0，所以特征p = 2。 (2) 寻找本原元 设为p (x)的根，则 4 = + 115 = 4443 = ( + 1) ( + 1) ( + 1) 3 = (2 + 1) ( + 1 + 3 )= 2 + 5 + + 1 = 2 + (2 +

11、) + + 1 = 1 15 = 1，因此 为本原元，p (x)为本原多项式，GF(24 )的15个 非0元素都可以如表7-13所示表示成 的方幂：0 , 1 , , 14 剩余类线性组合幂级数矢量00000001110001x0010 x2220100 x3331000 x + 1 + 140011x2 + x2 + 50110 x3 + x23 + 261100表7-13 GF(24)中元素的四种表示 剩余类线性组合幂级数矢量x3 + x +13 + + 171011x2 + 12 + 180101x3 + x 3 + 91010 x2 + x + 12 + + 1100111x3 + x

12、2 + x 3 + 2 +111110 x3+x2+x+13+2+1121111x3 + x2 + 13 + 2 + 1131101x3 + 13 + 1141001表7-13 GF(24)中元素的四种表示 (3) 按照定理7.19，找出各个共轭根系，并构成相应的最小多项式。0 m ( x) = x 0 = x0 m0 ( x) = x 0 = x + 1 , 2 , 4 , 8 m1 ( x) = (x ) (x - 2) (x - 4) (x - 8) 3 , 6 , 12 , 9 m3 ( x) = (x 3) (x - 6) (x - 12) (x - 9) 5 , 10 m5 ( x

13、) = (x 5) (x - 10)7 , 14 , 13 , 11 m7 ( x) = (x 7) (x - 14) (x - 13) (x - 11) 以上最小多项式的下标是以共轭根系中的最低幂次表示的(4) 利用本原多项式4 = + 1，将最小多项式化简。m1 ( x) = (x ) (x - 2) (x - 4) (x - 8) = x4 + x + 1 同理得 m3 ( x) = x4 + x3 + x2 + x + 1 m5 ( x) = x2 + x + 1 m7 ( x) = x4 + x3 + 1(5) 将x16 x因式分解x16 x = m ( x) m0 ( x) m1

14、( x) m3 ( x) m5 ( x) m7 ( x) = x (x + 1) (x4 + x + 1) ( x4 + x3 + x2 + x + 1) ( x2 + x + 1) ( x4 + x3 + 1)(6) 根据15 = 1以及元素阶的定义及性质，可得元素1的阶为1； , 2 , 4 , 8 ,7 , 14 , 13 , 11的阶为15；3 , 6 , 12 , 9的阶为5；5 , 10的阶为3。 因为阶为q - 1的元素为本原元，所以除为本原元外，2 , 4 , 8 , 7 , 14 , 13 , 11也都是本原元，其相应的两个最小多项式x4 + x + 1 , x4 + x3

15、+ 1即为本原多项式。本 章 小 结本章是后续纠错编码理论的代数基础，介绍的主要内容有：(1)任何整数可表示为a = qd + r的形式，任何多项式可表示为f (x) = q (x) p (x) + r (x) 的形式，d、p (x)为模，r、r (x) 为余数(式)。首一多项式的最高次数的系数为1，每一个首一多项式必可分解为首一即约多项式之积。(2) 群是一些元素在某种运算下构成的集合，满足封闭性、结合律、存在单位元和逆元。 群G的非空子集G对于G中所定义的代数运算也构成群，则称G为G的子群。 两个群在各自的运算下若存在一一对应关系，则这两个群同构。 循环群是由一个元素的所有幂次（倍次）构成。 群可由其非空子群完备地分解为若干互不相交的陪集。 (4)域中元素对加法是交换群，非零元素对乘法是交换群，满足分配律。 有限域中元素的个数是有限的或可数的。以素数d为模的整数剩余类环构成d阶有限域GF(d)，以n阶即约多项式p (x)为模的多项式剩余类环构成qn阶有限域GF(qn)。 有限域GF(q )中某一元素 的阶为q - 1