纠错编码代数基础

《纠错编码代数基础》由会员分享，可在线阅读，更多相关《纠错编码代数基础（34页珍藏版）》请在金锄头文库上搜索。

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

2、r称作余余数数，r可记作a mod d 。由于0rp (x)，一定存在唯一的多项式q (x)和r (x)，使 f (x)=q (x) p (x)+ r (x) 0r (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.环的定义环的定义环是一些元素构成的集合，该集合

3、中定义加法和乘法两种运算，满足：l(1)对加法是一个交换群；l(2)对乘法具有封闭性和结合律；l(3)满足分配律：对任何a ,b ,c F，有：a (b+c) =ab +ac (a+b) c =ac +bc3.子环子环设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的子环的充要条件是：对任何

4、a ,b S，有a -b S和ab S 。主主理理想想 在可换环F中，由一个元素a F的所有倍数及其线性组合而生成的理想I a =xa +nax 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乘法运算满足封闭性、结合律和交换律；还满

5、足分配律，因此模d的余数全体构成交换环，称作整整数剩余类环数剩余类环。+ 0 1 d 2d - 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-60,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)mo

6、d 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)的运算构成交换环，称作多项式剩余类环多项式剩余类环。纠错编码代数基础7.3 7.3 域域 7.3.1 域的定义域的定义 域是一些元素构成的集合，该集合中定义加法和乘法两种运算，满足：l(1)对加法构成交换加群。l(2)非零元素全体对乘法构成交换乘群。l(3)加法和乘法间具有分配律a (b +c)=ab +ac (a +b)c=ac +bc 域的阶域的阶 域中元素的个数。如整数域和复数域、实数域的阶都是无穷值。有有限限域

7、域 元素个数有限的域，用GF(q)表示q阶有限域。如上例可表示为GF(8)=0,1,a, 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=

8、e(q1是使等式成立的最小正整数)，则称 为本原元。 本原元多项式本原元多项式是以本原元为根的即约多项式。纠错编码代数基础7.3.4 有限域的结构有限域的结构 定理定理7.14 GF(q)的所有元素都是方程xqx=0的根，反之，方程xqx=0的根必在GF(q)中。l有限域的特征有限域的特征 是有限域中乘法单位元e关于加法的级，也就是使pe =0的最小正整数p。定理定理7.15有限域的特征必为素数。l素域素域是GF(q)的最小子域，表示为GF(p)=0,e,2e,(p -1)e。纠错编码代数基础定理定理7.16有限域的阶必为其特征之幂，即q = pm。定理定理7.17在以p为特征的域GF( q)

9、中，对于任意、 GF(q)，恒有(+ )p= p+ p推论推论1 若1,2, k是以p为特征的域中的元素，则对任意正整数n恒有纠错编码代数基础7.3.5 有限域的共轭根组有限域的共轭根组 定理定理7.18 对GF(pm)中的任意元素 ，恒有。定理定理7.19设f(x)是系数取自GF( p)的k次即约多项式，GF( pm)，若 是f( x)的根，则(0r k)也是f( x)的根。l最小多项式最小多项式系数取自GF(p )，且以 GF( pm)为根的所有首一多项式中，必有一个次数最低的多项式，称作 的最小多项式。纠错编码代数基础最小多项式的性质：l(1)最小多项式在GF( p)上是即约的l(2)每

10、一 GF( pm)，必有唯一的最小多项式。l(3) 的最小多项式能整除任何以 为根的多项式。推论推论2设m1(x),m2(x),mt(x)为GF( pm)中各元素的最小多项式，那么可将多项式在GF( p)上分解为纠错编码代数基础7.3.6 有限域的综合举例有限域的综合举例 【例例7.25】在GF(2)=0,1系数域上，以p (x)=x4+x +1为模构成有限域GF(24)，在GF(2)上分解多项式x16x 。解：(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)

11、= 2+ 5+1= 2+(2+)+1=115=1，因此为本原元，p (x)为本原多项式，GF(24)的15个非0元素都可以如表7-13所示表示成的方幂：0, 1,14纠错编码代数基础剩余类线性组合幂级数矢量00000001110001x 0010x2 2 20100x3 3 31000x + 1 + 1 40011x2 + x 2 + 50110x3 + x2 3 + 2 61100表7-13GF(24)中元素的四种表示纠错编码代数基础剩余类线性组合幂级数矢量x3 + x +1 3 + + 1 71011x2 + 1 2 + 1 80101x3 + x 3 + 91010x2 + x + 1

12、2 + + 1 100111x3 + x2 + x 3 + 2 + 111110x3+x2+x+1 3+ 2+ +1 121111x3 + x2 + 1 3 + 2 + 1 131101x3 + 1 3 + 1 141001表7-13GF(24)中元素的四种表示纠错编码代数基础(3)按照定理7.19，找出各个共轭根系，并构成相应的最小多项式。0m( x)=x0=x0m0( x)=x0=x+1 ,2, 4, 8m1( x)=(x)(x-2)(x-4)(x -8)3,6,12,9m3( x)=(x 3)(x-6)(x-12)(x -9)5,10m5( x)=(x5)(x-10)7,14,13, 1

13、1m7( x)=(x7)(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+1m5( x)=x2+x+1 m7( x)=x4+x3+1(5)将x16x因式分解x16x=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)纠错编码代数基础(6)根据15=1

14、以及元素阶的定义及性质，可得元素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即为本原多项式。纠错编码代数基础本本 章章 小小 结结本章是后续纠错编码理论的代数基础，介绍的主要内容有：(1)(1)任何整数可表示为a = qd+r的形式，任何多项式可表示为f (x)=q (x) p (x)+ r (x)的形式，d、p (x)为模，r、r (x)为余数(式)。首一多项式的最高次数的系数为1，

15、每一个首一多项式必可分解为首一即约多项式之积。(2)群是一些元素在某种运算下构成的集合，满足封闭性、结合律、存在单位元和逆元。群G的非空子集G对于G中所定义的代数运算也构成群，则称G为G的子群。两个群在各自的运算下若存在一一对应关系，则这两个群同构。循环群是由一个元素的所有幂次（倍次）构成。群可由其非空子群完备地分解为若干互不相交的陪集。纠错编码代数基础(4)域中元素对加法是交换群，非零元素对乘法是交换群，满足分配律。有限域中元素的个数是有限的或可数的。以素数d为模的整数剩余类环构成d阶有限域GF(d)，以n阶即约多项式p(x)为模的多项式剩余类环构成qn阶有限域GF(qn)。有限域GF(q)中某一元素的阶为q-1，则为本原元。GF(q)中的q个元素就是方程xqx=0的q个根，每一个非零元素可表示为本原元的方幂或线性组合形式。有限域GF(pm)中元素与互为共轭，每一个共轭根系对应唯一的最小多项式，最小多项式在GF(p)上是即约的且能整除多项式。多项式可在GF(p)上因式分解为其所有最小多项式的乘积。(3)环中元素对加法是交换群，对乘法满足封闭性、结合律，分配律成立。模d的余数全体对模d运算构成整数剩余类环；模p (x)的余式全体对模p (x)运算构成多项式剩余类环。纠错编码代数基础