第六章纠错编码3近世代数简介

1、信道编码理论信道编码定理和方法 之 近世代数简介近世代数简介近世代数简介群、环、域群、环、域多项式剩余类环和域多项式域和循环群集合的运算 如果在集合G中任意两个元素按照一定的结合法则结合起来仍等于G中一个确定的元素，则这个结合法则称为集合G的一个运算。群 ( Group ) 定义 对于一个非空元素集合G以及定义在G上的某种运算“ * ”，满足以下3个条件，则称G关于运算“*”构成一个群，记作（G，*） -1-11,( * )*( * ),*,*a bGa bcab ceaGa ee aaGaGaGa aeaa 结合性： 存在唯一的单位元 ： 中的每个元素各自存在唯一的逆元： 使群 ( Grou

2、p )-1-1-1-1/,*,*0;* ;*;,*1;* ;1*;a bGa bb aGea ee aa aeaaGea ee aa aeaa 交换群 阿尔贝群： 满足交换律的群 加群：群（）中运算是加法 加群的单位元为零元素， 加群的逆元： 乘群：群（）中运算是乘法 乘群的单位元为壹元素， 乘群的逆元： 群 ( Group ) 加群一定是交换群，加群一定含零元素 乘群不一定是交换群，乘群一定不含零元素 无限群：包含无数个元素的群称为无限群。 有限群：包含有限个元素的群称为有限群。 群的阶：有限群元素的个数称为该群的阶。子群 (Sub-Group)-1,*,*,*,*,*( ,*),*( ,*

3、)GGSSSGa bSa bSGSG 子群：如果在群（）中，集合 的非空子集 在同样的运算 下，可构成群（）， 则成群（）为群（）的子群。 对于任何，必有 该充要条件强调了逆元的存在性和子群的封闭性。如果群是有限群，则其子群（）也是有限群；且子群的子群的充要条件： 子群的阶数： 阶数一定是群阶数的因子Lagranges。（定理）子群 (Sub-Group),*.,*ABABC 若（A,*）和（B,*）分别是群（G,*）的两个子群，则A，B的交集在同样的运算下也构成群（G,*）的子群,记作。群（G,*）的任意多个子群的交集也是（G,*）的子群，记作例2-1 群与子群基本概念例2-1：令R、I、E

4、分别是有理数、整数、偶数集合， 则： (E,+) 是 (I,+)的子群；单位元均是0； (I,+)是(R,+)的子群；单位元均是0； 奇数集合O在加法运算下构不成群（不满足封闭性）例2-2 单位元与逆元例2-2： 集合G = 0,1,2 m-1在模m加（用符号表示）运算下构成一个群（G，）。 则： 该加群是m阶有限群； 单位元是e=0； 逆元：元素0的逆元是0； 元素1的逆元是m-1； 元素2的逆元是m-2；例2-3 有限乘群例2-3：集合G = 1,2 q-1在模q乘（q是素数）运算下构成一个乘群（G，）。-11;,mod1(1)qebGabqbn qan则： 该乘群是阶有限群； 该乘群是交

5、换群，单位元 每个元素都存在一个逆元 问题：为什么q要是素数？ 满足 即 （ 为任意整数）例2-3 有限乘群的模结论：结论：有限乘群的模一定要是素数，如果模有限乘群的模一定要是素数，如果模为合数，其某个元素（因子）一定能整除它，为合数，其某个元素（因子）一定能整除它，不会产生一个余数不会产生一个余数1 1（单位元），由此将导致（单位元），由此将导致该元素的逆元不存在。该元素的逆元不存在。域 (Field) 定义 F是一个非空集合，在F中规定两种运算，一种叫做加法，他的运算结果记为a+b,一种叫乘法，它的运算结果记为a b，且满足如下性质：则该F对所规定的两种运算是一个域，记作（,+, ）。 a

6、,b,cF,(a+b) ca cb c 加法运算构成交换群； 所以非零元素在乘法运算下构成交换群。 元素服从乘法对加法分配律，即： 域 (Field)qGF 无限域：包含无限个域元素的域，如有理数、实数、 复数全体在乘加运算下分别构成的有理数 域、实数域和复数域都是无限域。伽逻华域GF（q)： 如果存在一个域，它只包含有限个 元，我们就称它为有限域或伽罗华 域。如果这个域还有 个元素，则 域简记为（q）。域 (Field)eg:有限整数集合F=0,1,2,.,q-1(q是素数)在模q加、模q乘运算下构成一个q阶有限域，成为Galois域，记作GF(q)。二元域GF(2)：q=2的伽逻华域称为二

7、元域GF(2)近世代数简介群、环、域多项式剩余类环和域多项式剩余类环和域多项式域中和循环群多项式剩余类环和域111032.11011(2)( )nnnnia xaxa xaaxxxGFqqGF q，其中系数 代表了码元的取值， 的幂次则表示了码元的位置，系数属于某数域的多项式，称为该数域上的多项式。例如： 码字多项式 二进制系数的多项式成为二元域上的多项式。 进制系数的多项式成为 多项式是码字和代数之间元域上的多项式桥梁。的多项式环和理想子环 模运算 多项式环：某数域上多项式的集合在乘、加运算下可 以构成一个多项式环，它是一个以多项式 为环元素的交换环。 无限环：多项式环的两个要素是系数和幂次

8、，只要其 中一个有无限取值（比如系数所在的数域是 实数域、整数域等），则多项式环元素的数 目也是无限的，称为无限环。无限环有限环 系数、幂次都有限（剩余类环）纠错码多项式环和理想子环( )( )f xxq 多项式剩余类环： GF(q)上的多项式在模q加、模f(x)乘运算下，多项式剩余类的全体所构成的交换环称为多项式剩余类环，记做R。 显然剩余类环是靠GF(q)域保证系数有限，靠模f(x)乘保证幂次有限。且多项式运算中包含了系数间模q乘、加的数域运算。多项式环和理想子环-1-100-1mod0mod( )( )( )( )( )()( )-1-1( )( )mod00()nniiiiiiniii

9、qif xA xa xB xb xA xB xabxf xnnj kA xB xj kqkja bx 多项式加 对于环元素 和 多项式模乘 多项式环和理想子环( )12( )1210( ),( )deg ( ),deg ( )-1( )( )0,1, -1qf xnnqf xnnif xnf xnf xnR xnR xaxaxa xaaGF qin 特点：如果最高次幂是称此是 次多项式，写做这里表示阶次。显然，多项式剩余类环中所有环元素的次数都不高于次，其通用表达式为： 其中： 多项式环和理想子环1110( )111( )( )nnnnqf xxaxa xanxf xR x 首一多项式：最高次

10、项的系数为 的多项式。 即 次最简首一多项式：仅包含最高次项和常数项 ， 且形式为的多项式。 以为模的多项式剩余类的全体构成一个有限元素的多项式剩余类环，可证明这个剩余类环中的每一理想子环都是主理想，且该主理想的生多项式以成( )( )g xf x必定能整除。例2-7 剩余类环3( )222243222-7( )2,( )1,( )1 ,( )1( )( )212(2)0,1( )( )2( )( )1 (1)1qf xiR xqf xxxA xxxB xxA xB xqGFaA xB xA xB xxxxxxxxx例： 剩余类环中 若 是两个环元素，求是什么元素？（ ）该剩余类环至多由多少元

11、素组成？解：（）多项式系数取自域，即 将的系数做模 加（）431xxx 例2-7 剩余类环2mod( )22102102( )( )( )( )( )13( )3deg ( )3deg ( )-120,18f xiA xB xf xA xB xxxxf xf xf xa xa xaaaaa解：（ ）将的结果除以后取余式，即求模 （商为） （ ）是 次多项式， 环元素的幂次 环元素的通式：，而 由 、 、 三个系数组成的组合最多有 种8 该剩余类环最多有 个域元素组成。 近世代数简介群、环、域多项式剩余类环和域多项式域和循环群多项式域和循环群多项式域和循环群( )( ).qf xR xab 剩余

12、类环具有环的一切属性，包括单位元的存在性。但环对于非零元素的逆元是否存在并没有限定，这促使人们进一步： 探讨剩余类环的所有非零元素是否都存在逆元？ 在什么条件下可以构成一个域，域元素之间有 什么关系?多项式基本术语( ),( )( )IIIP xCCP xP xnnn 既约多项式：对于某数域上的多项式若除了 常数 以及外，不能被该数域 上的任何其他多项式整除，则称 为该数域上的既约多项式。 既约：已经化简到不能再约的程度。完全分解： 次多项式可以有 个根，最多只能分解为 个一次多项式的乘积，称为完全分解。多项式基本术语22( )( )( )( )1( )1( )()()( )(1)(1)III

13、P xP xP xf xxf xxf xxi xif xxx为既约多项式的： 不能再进一步分解为两个次数低于的多项式的乘积。显然既，一次多项式是既约的。注意：，如实数域：不可以再分解既约 复数域：非既约 约所对应的二元域：数域非充件约要条既多项式基本术语( )( )11nmGF qmP xxnq 本原多项式：对于有限域上的 次既约多项式 ，若能被它整除的最简首一多项 式（）的次数，则称 该多项式为本原多项式。 ，而既约未必是本原 多项式循环群：由多项式 的各次幂所构成的群称为 多本原多项式项式循环群一;定多项式 是群是既约的元素之一 称为循环群的生成元。例2-8本原多项式和既约多项式例例2-8

14、:(1) x4+x+1 (q=2, m=4, 2m-1=15) 不能被不能被 x5+1 , x6+1 x14+1 整除整除 能被能被 x15+1 整除整除 x4+x+1 是本原多项式是本原多项式 (2) x4+ x3+ x2+ x+1 能被能被 x5+1 整除整除 能被能被 x15+1 整除整除 x4+x3+x2+x+1是既约的，但不是本原的是既约的，但不是本原的例2-9循环群2345678923456234562-91.1117例： ， 构成乘运算下的无限循环群 若则产生以 ，为主值的周期性，则称 ，为乘运算下由7个元素组成的（7阶）的有限循环群。多项式域存在定理22( )( )( )( )

15、( )( )(2)0,1,2,2,( )2.1(12 )ImImmIP xGF qmGF qmqP xqGF qGF qGF qGF qGFmqP xxxGF若是上的 次既约多项式，则 域上次数小于 的多项式的全体，在模 加、 模乘运算下构成一个阶的有限域，称为 域的扩展域，写做）。称为 扩域）的基域。例：基域 扩域 定理0,1, ,12(2)x xGF 个元素的组合 00,01,10,11多项式域存在定理22( )( )()( )(,2(.,2mmmP xGF qmGF qmP xGF qGF q mm01q 若是上的 次本原多项式，则域上次数小于 的非零多项式的全体(共q -1)个，在模乘

16、运算下构成一个多项式循环群。也就是说，扩域）里至少存在一个本原元（ 代表一个次数小于m的多项式），它的各次幂构成了扩域）全部非定理零域元素。多项式域存在定理( )( )( )( )IGF qf xP xP x 以上的多项式为模的乘运算可生成 剩余类环； 以既约多项式为模的乘运算可生成多项式域； 以本原多项式为模的乘运算所生成非零域 元素可以构成多项模多项式的限制条件越多，环元式素循环具备的性质越多群。 。寻找循环群的生成元11( )( )( )1( ) (1),11( ) ( )( )( )012.( ) (3)0mmmnnmnqqGF qP xGF qP xxP xxnqxP x q xP

17、xPPq 上的本原多项式在扩域） 上的根 一定是本原元。 是本原多项式，可以整除 其中 设 为本原多项式的根，即 将 代入上式得 即： 证明：定理1 寻找循环群的生成元122112( )( )(11111.312mmmqmqmGF qP xGF qqqmm0qq00 上的本原多项式在扩域） 上的根 一定是本原元。：又， 由 可得: 可见： 的个幂次不但构成了全部个非零扩域元素，而且这些元素构成循环群因此 是本原元定理得证明（证。）定理续 构成循环群的步骤2,1mq0m由以上三个定理可知构成循环群的步骤：找一个GF(q)上的m次本原多项式P(x)；取本原多项式的根 及其各次幂； 构成循环群元素；

18、 实际上，循环群中任一元素的幂次都可以产生一个循环群，只不过只有本原元 才可以产生整个q个非零扩域元素。而只能产生。非本原元循环子群判断本原元和非本原元11( ,( ,1)(0,1,21(1)/( ,1)2.4mmmkqnkkqGCD kGCD kmkmmmmqGGF qkqqCDnqGCD k q其中 ）扩域上非零元素 （） 的阶一定是的因子，其值为： 循环群表示最大公约数（greatest common div中，n阶元素的n次幂恒isor） 即： 定理：推等。论于1：1)111( ,1)mmqqmkGCD k q（是本原元，是整数，而）判断本原元和非本原元1111(2 )kmmmmmnn

19、qnqnqqGF 非零元素的阶 也就是该元素的循环周期， 或该元素的各次幂所能产生的域元素的个数。 如果元素的阶，说明它可以产生全 部非零元素，是本原元。 如果元素的阶，则 一定是的因 子，必能整除，该域元素是非本原元。 二元扩域的所有域元素均为奇次阶。例2-10 二元扩域和循环群的构成444444152-10( )1(2)(2 )( )14,( )|1012121151xmP xxxGFGFP xxxmP xn 例 是上的本原多项式。试用本原元的各次幂生成二元扩域的全部域元素，并计算各元素的阶。解：令 为本原多项式的根，则 又 为本原元，其阶为例2-10 二元扩域和循环群的构成0122214

20、44228421,2151(2)1,411 (2)mGF 解（续1）：（） 各次幂可以生成（ ） 的全部域元素，且这些域元素构成一个乘运算下 阶的循环群。（见第 列）利用关系式可将 的各次幂化为低于 次 的多项式，比如 第 列例2-10 二元扩域和循环群的构成5234443(4)2.415/(15,5)15/5333mmGCD解（续 ）：（ ）将 多项式的 个系数抽出后按顺序排列，形成一个 重 结构。推广到一般，一个重 可以和一个包 含 码元的码字相关联。与 各次幂对应的重 结构 见第 列。 元素的阶可以用定理来计算，也可以通过求幂 运算来验证。比如的阶是 由于是 阶的， 次乘运算后应归一完成

21、一个循环。1577说 明： 本原元不是唯一的，但并非所有的元素都是本原元。 凡15阶的域元素都是本原元，共有8个；它们中任 意一个的各次幂都可以生成全部的域元素。 以为例，做完第次乘运算后归一，它能生成 全部15个域元素，的确是本原元。例2-10 二元扩域和循环群的构成域元素 / 根 / 最小多项式01211111012(),( )111()(2.12.4,11,11)5)1(mmmmmmmmqqqnkmqqmkqqn lkkGF qGF qxxnnqn lqxxxxx 扩域上所有非零元素都是上多项式的根，即可以完全分解为一次项的乘积： 证明： 设 为 阶元素，则；而定理可知必为的因子。令定理

22、完全分解性将代入可得 1(1)10lk nl 域元素 / 根 / 最小多项式()2.6()llmllqqkkiii li limGF qqqGF q 扩域上元素和的 幂次等于元素 幂次的和,即： 式中，是扩域定理幂和特性域元素。域元素 / 根 / 最小多项式00000( )( )( )1,2,( )( )( )02.7( )()0lllllllljppiiiiiiiqppqqqiiiiiipiqqqiiGF qpf xqf xllpf xf xfGF qfffffff 如果 是上 次多项式的根，那么 的 次幂也一定是的根。（）证明：令 定理共轭 根系 域元素 / 根 / 最小多项式123111

23、2.5()110,1mmmmmqqqqqqqGF qxx 费尔马定理共轭元和共轭根 根据定理，上任意域元素 一定是的根，即整理后可得。 由定理2.6可知，都是多项式的根，称为共轭元，这些共轭元有共同的基底，构成一系个共轭根系。域元素 / 根 / 最小多项式11,()( )mmmqqqqmGF qmmGF q 受费尔马定理的约束，又循环回 ，可见在扩域中，共轭根系最多包含个共轭元，以共轭根系为根的多项式的最高次数不会超过 。 一个多项式的根可以来自多个根系，如果一个首一多项式的所有根来自同一个 根系，称这样的多项式为 的最小多项式，最小多项式在一定是既约的。域元素 / 根 / 最小多项式1211

24、21( )11( )( )( )8)2.(mmqkkkiGF qxxxxxxm 定理最小多项式 上的多项式一定可以分解成若干最小多项式之积，即： 由费尔马定理可知各最小多项式的次数不会超因分。式过解次域元素 / 根 / 最小多项式1)0122222( )deg( ),( )()()()()deg( )liiiiiiiiilxlxlxxxxxxlmm（ 共轭元与最小多项式的关次最小多项式必然有同一根系的 个共轭元作为其根。也就是说，若必有： 这里，本原元的共轭根系对应的最小多项式的次数等于系。域元素 / 根 / 最小多项式10121212.52.82.91()()()( )( )( )( )mmqqkkiixxxxxxxx 共轭元与最小多项 综合定理、定理和定理可得： 式的关系例2-11 共轭元与最小多项式41151(2 )2,4,11)mqxGFqmxx 44例2-11 找出由本原多项式P(x)=x生成的二元扩域上各非零元素的共轭元，并计算与这些共轭元对应的最小多项式。解： 由于是二元域，可以直接用+替换- GF(2 上非零元素的循环群已经在例2-10中给出，现在要依次寻找各元素的共轭元和对应的最小多项式。例2-11 共轭元与最小多项式234200001122242821615 1248