第7章 纠错编码代数基础.

Presentation on theme: "第7章 纠错编码代数基础."— Presentation transcript:

1 第7章 纠错编码代数基础

2 第7章 纠错编码代数基础 内容提要 抽象代数又称近世代数，其研究对象是定义在某些运算下的集合，运算对象可以是数、多项式、矢量、矩阵、线性空间等。编码理论是建立在码的代数结构基础上的，为便于初学者理解，本章简单介绍抽象代数中与编码直接相关的基础知识，主要涉及整数及多项式的一些基本概念及群、环、域的基本知识。

3 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 < d，模d的全体余数为 {0 , 1 , … , d – 1}。 余数间可定义模d加法和模d乘法运算，设D = {0 , 1 , … , d – 1}，如果a , b  D，有(a + b) [ mod d ]  D 及 (a  b) [mod d ]  D 说明模d的余数全体对模d加法和模d乘法满足封闭性。

4 定理7.2 任何正整数a均可表示成其素因数的幂之积：
p1 , p2 , … , pn：a的互不相同的素因数，ri：正整数。 定理7.3 设a、b是不全为0的整数，则存在整数p、q使 pa + qb = (a , b) (a , b)为a、b的最大公约数， 当a、b互素时，(a , b) = 1，pa + qb =1。

5 2. 群的定义 群G是一些元素构成的集合，该集合中定义一种运算 *（加法或乘法），满足： 封闭性，对任何a , b  G，有a  b  G (2) 结合律，对任何a , b, c  G，(a  b)  c = a  (b  c) (3) 存在单位元e G， 使对任何a  G有a  e = e  a = a (4) 对任何a  G有逆元a-1  G，使 a  a-1 = a-1  a = e

6 l交换群 如果 * 运算还满足交换律，即对任何a , b  G，有a  b = b  a，则G称作交换群。
加法群是交换群，而乘法群不一定是交换群，如矩阵乘法不满足交换律。 l群的阶 群的阶就是群中所含元素的个数。 如整数加法群和非0实数乘法群的阶都是无穷值。 l有限群 阶为有限值的群称作有限群。

7 3. 群的同构 设在 ه 运算下的集合G与在  运算下的集合H是两个群，若存在一个G到H的一一对应关系 f ，且对任何a , b  G，有f (ab) = f (a)  f (b)，则称f是G到H的同构。 通常把条件f (ab) = f (a)  f (b)称为f 保持群的运算关系。一个同构映射f不仅保持运算关系，而且使两个群的所有代数性质都一一对应。同构的系统本质上完全相同，研究其中一个也就代替了对另一个的研究。

8 7.1.2 子群 1. 子群的定义 若群G的非空子集G′对于G中所定义的代数运算也构成群，则称G′为G的子群。
子群 1. 子群的定义 若群G的非空子集G′对于G中所定义的代数运算也构成群，则称G′为G的子群。 定理7.4 有限群的子群的阶一定整除群的阶。 2. 循环群 由一个单独元素 的一切幂次所构成的群 {0 = e ,  , 2 , … , n-1n = e} 称为循环群。该元素 称为循环群的生成元。使n = e的最小正整数n称为元素 的阶。 定理7.5 交换群G中的每一个元素 都能生成一个循环群，它是G的子群，元素 的阶就是循环群的阶。

9 元素阶的性质： (1)  若a是n阶元素，则am = e（对于加法为ma = e）的充要条件是n整除m。 (2) 若某一群中，a为n阶元素，b为m阶元素，且(n , m) = 1，则元素a  b（或a + b）的阶为n  m。 (3) 若a为n阶元素，则元素ak（或ka）的阶为

10 7.1.3 群的陪集分解 1. 群的陪集 设G′为群G的非空子群，取h  G，则称h  G′为G′的左陪集，称G′ h为G′的右陪集。当G是交换群时，子群G′的左、右陪集是相等的，元素h称作陪集首。 2. 群的陪集分解 设G′= { g1 , g2 , … , gn }，G′的阶为n ，又设G′为群G的非空子群，G的阶为n m，那么可将G完备地分成m个陪集（子群本身也是一个陪集），

11 陪 集 说 明 h1g1=g1 =e g … gn gn 陪集首h1=e，子群G′ h2g h2g … h2gn h2gn 陪集首h2，陪集h2G′ … hm-1g hm-1g … hm-1gn hm-1gn 陪集首hm-1，陪集hm-G′ hmg hmg … hmgn hmgn 陪集首hm，陪集hmG′ 表7-4 陪集分解表

12 陪集首的选择应注意： (1) 若陪集首h是子群G′中的元素，则陪集h  G′ 与子群G′相同。 (2) 若陪集首h不是子群G′中的元素，则陪集h  G′与子群G′相交为空集。 (3) 若陪集首hj 不是陪集hi  G′中的元素，则两陪集hi  G′与hj  G′相交为空集。 (4) 陪集h  G′中的每一个元素都可作为其陪集首h，陪集元素不变，仅排列顺序改变。

13 7.2 环 7.2.1 环的定义 1. 多项式的相关概念 多项式的性质在很多方面类似于整数的性质。系数取自集合F的多项式的表示形式为 f (x) = fn xn + fn-1 xn-1 + … + f1 x + f0 fi  F l 首一多项式 多项式的最高次数的系数为1，即fn = 1。 l多项式的阶 多项式中系数不为0的x的最高次数,记为f (x)。 l 即约多项式 阶大于0且在给定集合F上除了常数和常数与本身的乘积外，不能被其它多项式除尽的多项式

14 定理7.6 给定任意两个多项式f (x) 、p (x)，f (x) > p (x)，一定存在唯一的多项式q (x)和r (x)，使 f (x) = 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)的最大公因式

15 2. 环的定义 3. 子环 环是一些元素构成的集合，该集合中定义加法和乘法两种运算，满足： l (1) 对加法是一个交换群；
l (3) 满足分配律 ：对任何a , b , c  F ，有： a ( b + c ) = ab + ac ( a + b ) c = ac + bc 3. 子环 设F是一个环，S是F的一个非空子集，若S对加法和乘法也构成一个环，则称S是F的一个子环，F是S的一个扩环。

16 定理7.9 若S是环F的一个非空子集，则S是F的子环的充要条件是：
对任何a , b  S，有a - b  S和ab  S 。   理想 理想是一类特殊的子环。设F是一个可换环，I是F的一个非空子集，如果对任意a , b  I，恒有a - b  I，及对任意a  I和任意 x  F，恒有ax = xa  I，则称I是F的一个理想。 主理想 在可换环F中，由一个元素a  F的所有倍数及其线性组合而生成的理想I [ a ] = {xa + na  x  F , n  Z }称为环F的一个主理想，元素a为该主理想的生成元。

17 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的一个同构。

18 7.2.2 整数剩余类环 模d的余数全体F = {0 , 1 , … , d - 1}对模d加法运算构成加法交换群；对模d乘法运算满足封闭性、结合律和交换律；还满足分配律，因此模d的余数全体构成交换环，称作整数剩余类环。 表7-6 {0 , 1 , … , d - 1}的模d加法表 + 1 … d – 2 d - 1 2 d - 2 d - 4 d - 3

19 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) ] = [a (x) b (x) + a (x) c (x)] [mod p (x) ] 因此模p (x)的余式全体对模p (x)的运算构成交换环，称作多项式剩余类环。

20 7.3 域 7.3.1 域的定义 域是一些元素构成的集合，该集合中定义加法和乘法两种运算，满足： l(1) 对加法构成交换加群。
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 , a2 , a3 , a4 , a5 , a6 }

21 7.3.2 有限域 定理7.10 设d为素数，则以d为模的整数剩余类环构成d阶有限域GF(d)。
有限域 定理7.10 设d为素数，则以d为模的整数剩余类环构成d阶有限域GF(d)。 定理7.11 设p(x)为系数取自GF(q)上的n次即约多项式，则以p(x)为模的多项式剩余类环构成qn阶有限域GF(qn)。 定理7.12 有限域的阶必为其子域阶之幂，即Q = qn。

22 7.3.3 有限域的本原元 定理7.13 元素个数相等的有限域必同构。
有限域的本原元 定理7.13 元素个数相等的有限域必同构。   本原元 在GF(q)中，某一元素 的阶为q - 1，即 q-1 = e (q – 1 是使等式成立的最小正整数)，则称 为本原元。 本原元多项式 是以本原元为根的即约多项式。

23 有限域的结构 定理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}。

24 定理7.16 有限域的阶必为其特征之幂，即q = pm。
定理7.17 在以p为特征的域GF( q )中，对于任意、  GF( q )，恒有 ( +  ) p =  p +  p 推论1 若1 , 2 ,…, k是以p为特征的域中的元素，则对任意正整数n恒有

25 7.3.5 有限域的共轭根组 定理7.18 对GF(pm )中的任意元素 ，恒有。
有限域的共轭根组 定理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 )为根的所有首一多项式中，必有一个次数最低的多项式，称作 的最小多项式。

26 最小多项式的性质： l(1) 最小多项式在GF( p )上是即约的 l(2) 每一  GF( pm )，必有唯一的最小多项式。 l(3)  的最小多项式能整除任何以 为根的多项式。 推论2 设m1 (x) , m2 (x) , … , mt (x)为GF( pm )中各元素的最小多项式，那么可将多项式在GF( p )上分解为

27 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 =  + 1 15 = 4443 = ( + 1) (  + 1) (  + 1) 3 = (2 + 1) (  3 ) = 2 + 5 +  + 1 = 2 + (2 + ) +  + 1 = 1 15 = 1，因此 为本原元，p (x)为本原多项式，GF(24 )的15个 非0元素都可以如表7-13所示表示成 的方幂：0 , 1 , … , 14

28 表7-13 GF(24)中元素的四种表示 剩余类 线性组合 幂级数 矢量 0000 1 0001 x  0010 x2 2 0100 x3 3 1000 x + 1  + 1 4 0011 x2 + x 2 +  5 0110 x3 + x2 3 + 2 6 1100

29 表7-13 GF(24)中元素的四种表示 剩余类 线性组合 幂级数 矢量 x3 + x +1 3 +  + 1 7 1011 x2 + 1 2 + 1 8 0101 x3 + x 3 +  9 1010 x2 + x + 1 2 +  + 1 10 0111 x3 + x2 + x 3 + 2 + 11 1110 x3+x2+x+1 3+2++1 12 1111 x3 + x2 + 1 3 + 2 + 1 13 1101 x3 + 1 3 + 1 14 1001

30 (3) 按照定理7.19，找出各个共轭根系，并构成相应的最小多项式。
{0} m ( x) = x – 0 = x {0 } 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) = (x – 5) (x - 10) {7 , 14 , 13 , 11} m7 ( x) = (x – 7) (x - 14) (x - 13) (x - 11) 以上最小多项式的下标是以共轭根系中的最低幂次表示的

31 (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 ( x) m3 ( x) m5 ( x) m7 ( x) = x (x + 1) (x4 + x + 1) ( x4 + x3 + x2 + x + 1) ( x2 + x + 1) ( x4 + x3 + 1)

32 (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 + 1即为本原多项式。

33 本 章 小 结 本章是后续纠错编码理论的代数基础，介绍的主要内容有：
(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的子群。 两个群在各自的运算下若存在一一对应关系，则这两个群同构。 循环群是由一个元素的所有幂次（倍次）构成。 群可由其非空子群完备地分解为若干互不相交的陪集。

34 (3) 环中元素对加法是交换群，对乘法满足封闭性、结合律，分配律成立。
模d的余数全体对模d运算构成整数剩余类环； 模p (x)的余式全体对模p (x)运算构成多项式剩余类环。 (4)域中元素对加法是交换群，非零元素对乘法是交换群，满足分配律。 有限域中元素的个数是有限的或可数的。以素数d为模的整数剩余类环构成d阶有限域GF(d)，以n阶即约多项式p (x)为模的多项式剩余类环构成qn阶有限域GF(qn)。 有限域GF(q )中某一元素 的阶为q - 1，则 为本原元。 GF(q)中的q个元素就是方程xq –x = 0的q个根，每一个非零元素可表示为本原元 的方幂或线性组合形式。 有限域GF( pm )中元素与互为共轭，每一个共轭根系对应唯一的最小多项式，最小多项式在GF(p )上是即约的且能整除多项式。 多项式可在GF( p )上因式分解为其所有最小多项式的乘积。

35