（计算数学专业论文）reedsolomon码的多重循环编码算法的研究.pdf

i i i i ii iii ii i i i iir i lli i i y 17 4 017 2i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：王堡盆礁日期：动p 年石月g 日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：画篮缝导师签名： b 觏：二d b 年f 5 f 具，9 b r 摘要 摘要 本文首先介绍了多项式系统中，用于求解多项式组的吴特征列方法和g r o e b n e r 基方法及它们在计算机上实现的算法。 通过对多项式系统中理想的生成元的求解算法的分析和研究，并在对 r e d s o l o m o n 码的结构特点及其它码的一重和多重循环编码算法的分析、研究的 基础上，把多项式系统中的吴特征列方法应用于r e d s o l o m o n 码的多重循环编码 算法的实现。 本文在对线性码中的基本概念和基本性质作出描述的前提下，介绍了g r o b n e r 基方法用于求解零维理想的生成元的思想如何应用于对r e d s o l o m o n 码( 简记r s 码) 的多重循环编码的算法。本文还论证了零维多项式组p 生成的理想的吴特征列 c 是p 生成的理想的研o b n e r 基g 。在此论证的基础上，本文给出了一个用吴特 征列方法对r s 码进行多重循环编码的算法，并给予例子说明用吴特征列方法对 r s 码进行多重循环编码的可行性。 关键词：循环码， o b n c r 基，特征列，r e e d s o l o m o n 码，编码 一 a b s t r a c t ， a b s t r a c t i nt h i sp a p e r , w ei n t r o d u c et h em e t h o do fg r o b n e rb a s e sa n dt h em e t h o do fw u c h a r a c t e r i s t i cs e t ，w h i c ha l l o wu st os o l v et h ep r o b l e mo fs o l v i n gp o l y n o m i a le q u a t i o n s a n dw eg i v et h e i ra l g o r i t h mo nt h ec o m p u t e r b a s e do ns t u d y i n gt h ea l g o r i t h m st os o l v et h ep r o b l e mo fs o l v i n gp o l y n o m i a lo f g e n e r a t o ro fp o l y n o m i a li d e a l s ，a n da n a l y s i st h es t r u c t u r a lc h a r a c t e r i s t i c so ft h ec o d i n g a l g o r i t h mo faw e i g h tc y c l ec o d ea n dm u l t i p l ec y c l ec o d e ( r e e d s o l o m o nc o d e s ) ，w e g i v ea l la l g o r i t h mw h i c hb a s eo nt h em e t h o do fw uc h a r a c t e r i s t i cs e tf o rm u l t i c y c l e c o d e s t h eb a s i cc o n c e p ta n dt h eb a s i cp r o p e r t i e so ft h el i n e a rc o d et ob ed e s c r i b e d b a s e d o nt h eg r o b n e rb a s e sm e t h o di su s e dt os e e kt h eg e n e r a t o r so fz e r o - d i m e n s i o n a li d e a l ， w ei n t r o d u c et h em e t h o do fg r o b n e rb a s e s ，w h i c hu s e df o rt h ec o d i n ga l g o r i t h mo f m u l t i - c y c l eo fr e e d s o l o m o nc o d e ( r sc o d e ) w es h o wt h a ta n o t h e ru s e f u lp r o p e r t yo f t h ez e r o d i m e n s i o n a lp o l y n o m i a li d e a lw h i c hg e n e r a t e db yp o l y n o m i a le q u a t i o n sp o f w h i c hw uc h a r a c t e r i s t i cs e tci sag e n e r a t o ro ft h i si d e a lo fg r o e b n e rb a s i sg b a s e do n t h ep r o v e ，w eg i v ea l lc o d i n ga l g o r i t h mo fm u l t i p l ec y c l er sc o d e s s o m ed i r e c t a p p l i c a t i o no fo u rn o t ea r ea l s oi l l u s t r a t e d k e yw o r d s ：c y c l i cc o d e ，g r o b n e rb a s e s ，w u sc h a r a c t e r i s t i cm e t h o d ，r sc o d e ，e n c o d e i i 目录 目录 第一章绪论l 1 1 研究的背景和意义1 1 2 循环码编码理论的现状2 1 3 本文的主要内容2 1 4 本文的结构安排2 第二章特征列方法4 2 1 三角列与特征列4 2 2 吴砌t t 算法7 2 3 小结1 2 第三章g r o b n e r 基方法1 8 3 1 项序1 8 3 2 多项式的约化1 5 3 3g r o b n e r 基及b u c k b e r g e r 算法1 9 3 4 约化的g r o b n e r 基2 1 3 5 小结2 2 第四章r e e d s o l o m o n 码的多重循环编码算法2 4 4 1 线性码2 4 4 2r e e d s o l o m o n 码的一重编码2 8 4 3r e e d s o l o m o n 码的多重循环编码的g r o b n e r 基算法3 1 4 4r e e d s o l o m o n 码的多重循环编码的吴特征列算法3 6 4 5 小结4 3 第五章结论和后继工作展望4 4 致谢4 5 参考文献4 6 i u 第一章绪论 1 1 研究的背景和意义 第一章绪论 通信是指把一条信息有效地从甲地传送到乙地。通常信息源( 简称发方) 是指 发信方，收信者( 简称收方) 指接收信息的一方。一个完整的通信过程可以用以下 模型( 图1 1 ) 来简单表示。 图1 1 信道指的传送介质，比如空气或电线等。一个完整的通信主要以下步骤：对 信息的调制，比如将信息源的信息调制成电信号，发送，接受和解调等部分。解 调是指将接收到的电信号还原成信息源发送的信息，如声音，文字和图像，以及 单纯的数字等。将信息源的信息转化成数字信息传送给收信者称为数字通信。在 工程应用上主要是对二元数字信息研究。 数字信息在传送过程很容易受到各种各样的干扰，造成收信者接收到的信息 可能不是原来信息源发送的信息。为了使信息源发送的数字信息能正确的传送到 收方，工程技术人员采取了各种技术设备上的改进和更新来确保信息在传送时受 到的干扰降到最低。更为有效的抗干扰的办法，就是在进行信息传送前对要传信 息选择一种好的抗干扰编码方法进行编译。换句话说就是在数字信息传送之前先 进行一次具有较强抗干扰性的编码后，再发送通过抗干扰编码后的数字信息。这 样，当收方收到数字信息后再进行解码就得到了发方发送的信息。 比较有效的抗干扰编码方法有两类：一是检错编码，二是纠错编码。通过对 抽象代数和数论等有限域的知识的研究。人们找到了纠错码中一类重要的码 循环码。起初，人们认识到并感兴趣的是循环码的外在结构特点，即循环码的码字 循环移位之后仍然是循环码。这一特点给循环码的编译码的实现带来了极大的便 利。在后来的实践应用中，人们从抽象代数及代数几何的相关知识方出发，找到了 循环码的纠错性能控制等方面更加吸引人的优越之处。 电子科技大学硕士学位论文 1 2 循环码编码理论的现状 当今是一个信息时代，时刻都有各种的信息进行传送，而对信息的准确性和 安全性要求也比以往更高了，尤其是商业领域体现得更加突出。在信息传送过程 中，首要的是保证信息的准确性。在数字通信中码字的准确传送是信息高准确率 的前提。对于单个或较少发生差错的编码方法的研究有了比较成熟方法和技巧。 而对多个或成区间发生差错的代数编码方法还可做很多工作。 循环码是一类能纠正成区间的差错的码。实际生活中码字在信道( 尤其短波 信道) 中传送时，通常是成区间出现差错，即连续几个位的码元都发生差错，或 连续几个位的码元除其中几个以外都发生差错。因此，循环码的编码和解码方法 在通信工程有广泛研究和应用。 循环码所拥有的高效的解码算法和极强纠错能力得益于它的编码方法。随着 代数几何的不断发展，循环码的编码算法也从当初的一重编码发展到多重编码。 g r o b n e r 基的在代数几何中的广泛应用，为多重循环码的编码提供数学工具。 1 3 本文的主要内容 本文首先介绍了吴特征列方法的一些基本概念及基本定理，接着对g r o b n e r 基方法给出比较详实的介绍。介绍了线性码的一些基本概念和定理。 在研究用g r o b n e r 基方法求零维理想的生成元的基础上，介绍了一种用 g r o b n e r 基方法对一重和多重循环码( 以r s 码为例) 进行编码的算法。我们论证了 多项式组p 生成的零维理想的吴特征列就是这个理想的g r o e b n e r 基g ，并以此为 基础，给出一个以吴特征列方法为基础的多重循环码( r s 码) 的编码算法，并给例 子证明所用方法的可行性。 1 4 本文的结构安排 本学位论文共分五章。 第一章是绪论，主要概述了循环码编码研究的背景和意义、以及循环码编码 理论的研究现状，并介绍了循环码编码方法的研究和本文中的主要工作。 2 第一章绪论 第二章重点介绍了代数簇分解中的吴特征列( 三角列) 方法及其算法实现。 第三章介绍了代数簇分解中g r o b n e r 基方法及g r o b n e r 基的性质和应用。 第四章分为两部分，第一部分主要介绍了编码理论中线性码及其实现编码的 一些基础知识理论和一些编码算法。第二部分是本文的主要工作。介绍了一种用 g r o b n e r 基方法求零维理想的生成元的基础上，对一重和多重循环码保s 码) 进行编 码的算法。我们论证了多项式组p 生成的零维理想的吴特征列是这个理想的 g r o e b n e r 基g ，并以此为基础，给出一个以吴特征列方法为基础的多重循环码( r s 码) 的编码算法。 第五章给出了本文总结并及以后工作的展望。 电子科技大学硕士学位论文 第二章特征列方法 特征列的概念是j f r i t t 在其微分代数的工作中对( 微分) 多项式理想引进的。 但p i t t 的概念和方法未曾引起人们的注意。2 0 世纪7 0 年代末，吴文俊 2 , 2 0 , 2 1 , 2 2 , 2 3 在 创立他的几何定理机器证明方法时注意到了r i t t 的工作，并以此作为完善其机械 化方法的构造性代数工具。吴方法在理论、算法、效率和实用上都大大发展了特 征列方法，并将其用于各种几何推理和计算问题，从而引发了大量后续工作。吴 的方法在于计算多项式组( 而非理想) 的特征列，它避免了r i t t 算法中的不可约 性限制，因而使得从任意多项式组有效地构造特征列成为可能。本章中介绍的特 征列方法大多基于吴的工作。 2 1 三角列与特征列 设k 是一特征为0 的可计算数域有理数域q 是| 7 | ( 的一个实例。我们将变元x 排成固定的次序x i _ x 2 一 0 ，称x p 为多项式尸的导元，记为i v ( p ) ，d e g ( p ，x p ) 为p 的导次数，记 为l d e g ( p ) ，而l c ( p ，x 口) 为尸的初式，记为i m ( p ) 。 本章中，多项式组都是指阻x 】中非零多项式构成的有限集合。有限集s 中元 素的个数用吲表示，它也称为s 的长度。通常我们将有序集合的元素列入一对方 括号中。 定义2 1 1 4 1 阻x 中非常数多项式组成的有限非空有序集合 - i = 【正，疋，t 】 如果c l s ( 互) c l s ( t 2 ) c l s ( 7 , ) ，称为三角列或非矛盾拟升列。 4 第二章特征列方法 可将任意三角列写成如下形式 其中， = z ( x l ，一，x p l ，x n ，x p ，) 0 p l p 2 p ，刀， p f = c l s ( t ) ，= 1 v ( 正) ，i = 1 ， ( 2 1 ) 设为( 2 - 1 ) 式所示的三角列，而尸为任一多项式，如果d e g ( p ，。) l d e g ( t t ) 对所有i 成立，则称尸对t 是约化的；在可= 【t 时，我们也说尸对丁是约化的。将 多项式 r = p r e m ( p r e m ( p ，乃，) ，五，。) 简记为p r e m ( p , ) ，并称其为p 对- 的伪余式，容易导出下面的伪余公式 ，h ，多7p = q ，t ，+ r( 2 2 ) f = l 这里g ，是非负整数，而 l i = i n j ( z ) ，o f 枫x ，i = 1 ，。 明显地，在尸对是约化的情形有p r e m ( p , 匹) 叩。对任意多项式组p ，p r e m 口， i f ) 代表 p r e m ( p , q i ) l p p ) 。 例2 1 1 考虑 # = x l x 2 + x ；一而x 2 x 4 一x 2 x 4 + x l x 2 + 3 x 2 ， 最= x i x 4 + x 3 一x l x 2 ， p 32 屯x 4 2 4 一x l x 2 一l ， 只= p r e m ( p 1 ，忍，以) = j c l + 豸- g x ：3 - x a x 2 x 3 + x 1 3 x 2 + 3 # 恐 只对弓是约化的，但置对b 是非约化的。而且忍与b 二者中没有一个对另一个是 5 、- 、 晚 埔 、- 、 ， 砌砀 ， ， 一， 一， 互疋 电子科技大学硕士学位论文 约化的。关于_ 一 一 黾， ，= 只，忍 是三角列，鼻和b 对。都不是约化的。可 以验算 p 6 = p r e m ( 只，1 ) = 2 x l x ；+ 2 # x 2 2 - 2 x ? x 2 + x i ! + 而， p r e m ( p i ，1 ) = 0 。 设必是一数域，对任意多项式组p ，q 与多项式，定义z e r o ( f ) i n i o r ) = i n i ( p ) i p p ) ， z e r o ( f ) = z e r o ( f ) ， z e r o ( p f ) = z e r o ( p ) z e r 0 ( d ， z e r o ( p q ) 2z e r o ( 驯n 出qq ) 。 引理2 1 1 【5 1 对阻x 中的任意三角列q r 与尸多项式，如果p r e m 妒，) = o 则 z e r o ( q l i n i ( y ) ) 三z e r o ( p ) 。 简要说明一下，不妨设x z e r o w i n i c y ) ) f f ：是对任意，i n i ( | ) 有1 ( x ) 0 。 因此由伪余公式( 2 2 ) 可得p ( x ) = 0 。 定义2 1 2 3 1 三角列面= 【互，z ck x 称为非矛盾升列，如果对所有 2 f ，霉对 正，正一1 是约化的。 称为是良好的，如果对所有2 i 厂都有 p r e m ( i n i ( t t ) ， 正，互- l 】) 0 。 显然，每个非矛盾的升列都是良好的三角列。任意多项式对一矛盾升列的伪 余式都为0 。 例2 1 2 设五 x 2 屯 一一2 ，( z ? - 4 ) x 3 + 恐 是三角列，但既不是良好的也 不是升列。三角列 【x ? 一2 ，x ；一2 x l x 2 + 2 ，( x 2 一而) x 3 + 1 】 是良好的，也是非矛盾的升列。 6 第二章特征列方法 定义2 1 3 t 5 1 升列c 称为非空多项式组p c 阻x 】的特征列，如果 c c ，p r e m 口，c ) = o ) 。 这里，p 的特征列是按照吴的方式定义的，r i t t 关于特征列的定义是对( p 生 成的) 理想歹而言，而且要求p r e m c ) = 0 ) ；因此，为了计算c ，需要考虑它 的不可约性。 命题2 1 2 设c = ( c l ，c 为多项式组p c 阻x 的特征列，且命 i i = i n i ( c f ) ，i p j = i p u 1 f ) ，f _ l ， = i n i ( c ) = ，1 ，) 。 则 z e r o ( c ) cz e r o ( p ) cz e r o ) ( 2 3 ) z e r o ( p ) = z e r o ( d ) u uz e r o ( f ) ( 2 - 4 ) 在k 以及k 的任意扩域中成立。 证明因c c ，故z e r o ) c z e r o ( c ) 。 另一方面，对任意p p 都存在非负整数g ；与多项式q 使 由此可见z e r o ( c d c z e r o ) 。很明显，这一关系对灭及k 的任意扩域都成立 因而关系式( 2 3 ) 获证。 注意到p 和i ；的公共零点是p ，的零点。因此容易得出零点关系式( 2 - 4 ) 。证毕。 2 2 吴斑t t 算法 定义2 2 1 如果c l s ( f ) 0 ，且l d e g ( f ) _ 。 例2 2 1 对例2 1 1 中的多项式鼻，最，忍由工。- g _ - ，或叮一 t 。此时，也称r 比- 有较低的秩。如果 和- - - n - - $ = n n ，其秩永不递增。则存在 整数尼使得t t - t k , ，对所有j i 尼成立。 下面的算法给出了命题2 2 1 的实现过程。 算法b a s s e t ：i b = b a s s e t ( i p ) ，任给非空多项式组p c 砸x 】，本算法计算p 的基 列b 。 b 1 命母= p ，璐= 矽。 b 2 重复下列步骤直至肚矽： b 2 1 从f 中选取一秩最低的多项式曰。 b 2 2 命1 8 3 = b u b 】。 b 2 3 如果e l s ( b ) = 0 ，则命肚矽；否则命 = 扩i f - b i f 对b 是约化的) 。 p 的某一基列是矛盾的当且仅当p 含有常数。在这一情形下，算法b a s s e t 终 止于b 2 的第一个循环。关于基列的例子，参阅例2 2 3 。 下面我们描述吴鼬t t 的特征列算法，该算法指出了如何从任意多项式组求得 其特征列。 算法c h a r s e t ：c = c h a r s e t ( p ) 任给非空多项式组p ck x ，本算法计算p 的 特征列c 。 c 1 命f = p ，鼹= p c 2 重复下列步骤直至瞎西： c 2 。1 计算c = b a s s e t ( i f ) 。 c 2 2 如果c 是矛盾列，则命r = o ；否则计算 i i 跫= p r e m ( 殂| e ，c ) o ) ， 且命f = 碾u 风。 特征列算法是吴- r i t t 零点分解算法的核心。 命题2 2 2 设p c 灭 x 】是以 i b = 昼，b 2 ，毋 9 皇王型垫奎堂堡圭堂垡笙壅 _ - _ - _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ - _ - _ _ - _ - _ _ _ _ _ - _ _ - i _ _ - _ _ _ - _ - _ _ _ _ _ _ _ _ - _ _ - _ 一 为基列的非空多项式组，这里c l s ( b ，) o 。如果b 是一对璐约化的非零多项式，那 么p u ) 有一基列，其秩比璐的秩低。 证明命p + = p u b ) ，若c l s ( b 1 ) = 0 ，则 召 是p + 的基列，并且比璐有较低 的秩。否则，假定c l s ( b 1 ) = p 0 。因b 对璐是约化的，故存在f ( 1 f ，) 使p 1 时有p d s ( b ，- 1 ) 。而且在p = c l s ( b ，) 时：f i d e g ( b ，x ，) - 至多由有限项构成。换言之，m 是有限的，因而算法c h a r s e t 必然终止。 正确性由( 2 2 ) 式知，对任意多项式f 口，有p r e m ( f ，b f ) 础fu f ) 因而 1 0 第二章特征列方法 对所有i 成立。于是 = = 。 c = 璐。c f 朋c 胗 由于飓。= ，我们有 p r e m ( f 。，c ) = p r e m ( 珂。e ，c ) u p r e m ( c ，c ) = 0 ) ， 根据定义，c 是p 的特征列。 上述从多项式组p 获取特征列c 的过程称为吴一鼬t t 整序原理。 例2 2 3 命p = 亿，只) ，其中 弓= x l x ；+ x ；一x i x 2 x 4 - - x 2 2 4 + x l x 2 + 3 x 2 ， 最= x i x 4 + x 3 一x l x 2 ， 只= x 3 x 4 2 x ；一z l 工2 - 1 这些多项式以在例2 2 1 中出现，对应于式( 2 4 ) 中的多项式组及其基列如下： 肛。= 亿，忍，只) c f ：= 亿，e ) c 口，= 亿，圪 u 璐。= 眨】 u 璐：= 瞳，忍】 u b ，= 眈，只，最】= c 碾。= 识，)取：= 识)风，= 矽， 其中只，只，只已在例2 1 1 和例2 2 2 中给出。所以，最后一个基列1 8 3 ，即是p 的特 征列c 。将多项式只，只，另重新命名为q ，c 2 ，c 3 ，抄录如下： c = 【c 1 ，c 2 ，c 3 x l ( 2 x l x ；+ 2 x ；- 2 x l x 2 + _ + 1 ， 为+ 一彳屯一l x 2 屯+ x ? x 2 + 3 x 2 1x x x 22 ，为+ 一彳屯一l x 2 屯 + 2 ， x 1 x 4 + 石3 一五x 2 q ，q ，g 的初式分别为厶= 2 x t ( x l + 1 ) ，厶= 而+ 1 ，厶= 屯。 由于厶和l 都是厶的因子，0 意味着厶厶厶0 于是只有初式厶需要进一 步考虑设p ，与p ：是由p 通过分别添加而+ 1 与毛所扩大的多项式组，即 电子科技大学硕士学位论文 l 一 p l = p u 扛+ 1 ) ，p2 = p u k ) 于是有下面的零点关系 z e r o ) = z e r o ( c 厶) uz e r o ( p 1 ) u z e r o ( p2 ) 。 需要指出的是，在用c h a r s e t 计算特征列的过程中，必然会出现某些初式的多 余因子。这些因子应被删除，以便控制多项式的膨胀。 2 3 小结 本章主要介绍了三角列与特征列定义，及其一些基本的性质详细介绍了用吴 一砒t t 算法来计算给出多项式组的吴特征列的算法( c h a r s e t 算法) 。并给出了具体 例子来对该算法的实现加以论证。 1 2 第三章g r o b n e r 基方法 第三章g r o b n e r 基方法 g r o b n e r 基方法是b b u c h b e r g e r 在他的博士论文中首先引进的。该方法能从任 一多项式理想的一组给定生成元有效地计算出另一组性质良好的生成元，称为该 理想的g r o b n e r 基。g r o b n e r 基的性质使其可以用来判断任意多项式是否属于该理 想。因而它已成为计算机代数以及计算交换代数与代数几何中的基本工具，并在 代数数论、代数编码、整数规划等许多领域中有广泛应用。本章主要介绍g r o b n e r 基的基本概念、算法、性质和应用。 3 1 项序 定义3 1 11 1 1 集合s 上满足传递性的二元关系 ，如果对s 中任意两个不同 的元口和6 ，或者a ，b ，或者b ，a 称为全序。在意义清楚时，将 ，简记为 。 又将a b 或a = b 合记a b 。 定义3 1 2 t 3 1 集合s 上满足传递性的二元关系 ，如果s 的任意非空集有极小 元称为良序。一个等价的定义是，s 上不存在严格无穷递降的链。 本章中所提到的多项式和理想都假定在阻x 中，其中尺是域。我们用表示 非负整数的全体，并将瞰x 】中所有项的全体记为r ，即 z = 群1 砖砖ia f ，汪1 ，z ) 。 通常将群x 2 a 2 x 玎a ”简记为x 口或( 口1 ，一，口。) 。对任意x 口r 都有l x 口且 对任意x 口，x ，xy t ，都有x 口 x 卢，则x 口xy x xy 成立，那么集合t 上的全序 称为项序。 上述两个条件中的第二个条件通常称为保持乘法。 电子科技大学硕士学位论文 定理3 1 4 设 为r 上项序，如果x 口ix ，则x 口 x 。 证明存在xy t t ，使得x 色x 口xy 。因为1 x ，所以证明存在x 。，使得x 尸= x “x7 。因为1 x 尸，所以 口ayj xxx 。= x 。 对固定的变元序x 。- 4 - 4 x 。，可以引进不同的项序三种常用的项序是纯字典 序，全幂序( 又称分次字典序) 和分次反字典序。它们的定义如下： 定义3 1 5 3 1 项集合z 上的序分别称为纯字典序 出，全幂序 ，d c g ，或分次反 字典序 抛，如果对任意口= ( 口1 ，一，a 。) ，= ( b l ，玩) t ， ( a ) 口 加营3 i ( 1 f 以) ，使得口j b i ，而口，= b j ( 1 ，) ； 打开月玎 ( b ) 口 ，d e g q 岛或以，= 岛，且j f ( 1 f ，z ) ，使得口， 岛， 而口，= b j ( 1 j 胛) ； ( c ) 历 妇pc , q 6 ， i = li = 1i = 1i = 1 而口j = b j ( i j 咒) 。 上面定义的三种序都是r 上的项序就消元而言，使用纯字典序。 例3 1 1 对变元序z _ y 是丁上的无穷严格递降链。将 这条链上的所有元素生成的理想记为歹由d i c k s o n 引理，r 是有限生成的。不妨 设乒 。对任意xq ( ， 后) 都存在f 尼，使得x 啦ix 岛。于是由 命题3 1 1 可得，x 嘶x 肼。矛盾。 推论3 1 5 【7 】全序 是丁上的项序当目 又当它是良序而目保持乘法运算。 3 2 多项式的约化 首先介绍本节中常用的记号设f 阻x 】在给定项序下按降序排列为 ，：石xq + + 以x 讥，= zx + + 以x “， 饶伪 则l t ( f ) = x1 ，l m ( f ) = zx1 ，l c ( f ) = z 分别称为f 的首项，首单项式和首项系 数。我们常用z ( ，) = xq ，x ) 记，中出现的项集合。 多项式约化实际上是一种多项式的除法，是域上一元多项式e u c l i d 除法在多 元多项式环上的一种推广。 定义3 2 1f 1 1 给定f 上项序 ，并设尸，p 阻x ，且p 0 。如果存在t t ( f ) ， s t 使得t = s i t ( p ) ，则称，是模尸可约化的，这时，令 g = f 一二一s p 1 c ( p ) 7 其中c 是f 关于t 的系数，并说，通过模p 消去t 一步约化到g ，记作f 与g 。 电子科技大学硕士学位论文 定义3 2 2 t 3 1 设p 为阻x 】中的多项式组。如果存在多项式尸p 使得，与g ， 则称f 是模p 可约化的，记为f 山g 。如果没有这样p 的存在，则称f 对p 为约化的或为范式。 如果f 可有p 中的多项式经多步约化到范式r ，则记为，与尺。 例3 2 1 多项式 f = x 2 y 2 + 2 砂+ y 2 + l ，p = 舅，昱) 其中置- - x y + l ，= y ，并取定纯字典项序。那么 f 屿x y + y 2 + l 山y 2 山o 是，模p 的一个约化过程。还有另一个约化过程 f 山拶+ y 2 + 1 马y 2 + 1 马0 。 由此可以看出，对于不同的约化过程，最终得到的范式可以是不同的。另一 个问题是，对任意多项式，和多项式组p ，模p 的约化过程最终会结束。 定义3 2 3 ”1 设f ，g q x 在给定项序 ，下，将f ，g 按降序排列如下： f - - f l x + + z x 嘶， g = g i x 晟十+ g m x i m 定义尺 x 】上的二元关系 ，( 称为由项序 ，诱导的灭 x 】上的多项式序) 如下： f ，g 铮( 口) j 后( 1 k ，) 使得 ，孱而口f = f l f ( 1 f 尼) 或( 6 ) ， m ，而 = 届( 1 f ，) 。 定理3 2 4 3 1 二元关系 ，是必 x 上的良序。 定理3 2 5 给定r 上项序 ，并设_ 是 诱导的多项式序。对任意f ，g n x 若 f - 一g ，贝ug - x 。的纯字典序排列。用符号表示，我们有 l t ( p 1 ) = x i x 4 ，l t ( p 2 ) = x 4 2 ，i t ( f ) = x l x 2 4 ； l c ( p 1 ) = l c ( f ) = 1 ，l c ( 忍) = 2 设p = 翻，lf 对p 明显可约，如 f 马h ，f = b 九p l + h ， 其中 b = - 1 ，五= x 2 ， h = 而x ；+ x ；x 2 - + x 2 x 3 一x 1 x ；+ x l x 2 + 3 x 2 对于上面的约化，消去的项关于项序不是极大。若选极大项，需要先约化f 中的 首单项式x l x ：。对p ，f 到其范式的约化如下： f 山且生一日2 互专日3 1 7 电子科技大学硕士学位论文 其中 三= f - x 4 只2 巧2 一工3 x 4 一x 2 h + z l x 2 + 3 x 2 ， h 2 - - h 。一丢最= 一丢x i x 2 x 4 - - x 2 x 4 - - 丢x 1 x 2 x 3 - 五z ：+ 3 x ：， 也= 吼+ 吾恐乌= 一x 2 x 4 + 恐恐+ 主确。蝎屯如 现在h ，对p 已约化，因而不可能有进一步的约化。所以 r = n f o r m ( f , p ) = h 3 = ，+ ( j 5x 2 一x 4 ) 只一j 1 p 2 一般来说，范式r 是不惟一的；也就是说，对于公式( 3 一1 ) 从鼻中p 的不同选 取可以产生不同的范式。我们在例3 2 1 中已经看到这种情况。那些使每个多项式 对其都有惟一范式的多项式组具有特殊的意义。 3 3g r o b n e r 基及b u c k b e r g e r 算法 定义3 3 1 u 多项式组g c 阻x 称为给定项序 。 每个理想都有一个由有限多个多项式构成的g r o b n e r 基。这一点可以由下面的 h i l b e r t 基定理保证。一个理想的约化g r o b n e r 基( 附加一定条件的c r r o b n e r 基) 在 某种意义下是惟一的。所以，通常在提到多项式的理想的g r o b n e r 基时，总认为 它是有限的。 定理3 3 1 【3 洌( h i l b c r t 基定理) ：每个多项式理想3 c _ 必 x 都是有限生成的， 即存在日l ，l 一，h s 男使得f f = - 。 推论3 3 2 3 捌设只c 只c 确x 】为理想升链，则存在正整，使得对任意 t n 都奄，t = ，n o 第三章g r o b n e r 基方法 证明令 贰，t ， - - 1 显然，歹也是砸x 】中的理想。根据h i l b e r t 基定理，歹是有限生成的。设有e ，只歹 使得声互， 。那么对每个f ( 1 f 尼) 都有五，使得e j 。取动l 一，j 。中 的最大者即可。证毕。 定理3 3 3 设g 为k x 中关于变元序x i nk x ， 则n f o r m ( g ，g ) = 0 。注意到 在将g 约化为0 的过程中，所有多项式都只涉及到变元x ，。因而，对相应的范式 公式( 3 - 1 ) ，有r = o ，e g nk x 小g k x 小所以g 属于( 3 2 ) 式的右边。证毕。 g r o b n e r 基的意义不仅在于它具有良好的性质，更因为它是可计算的。也就是 说，给定一个理想的任意一组生成元，可以按照确定的算法步骤计算出该理想的 g r o b n e r 基。我们在这里介绍由b b u c h b e r g e r 提出的第一个g r o b n e r 基算法。 g r o b n e r 基方法已被深入研究并被应用到各个领域。各种改进算法也已在计算机上 成功实施。 定义3 3 4 5 1 阻x 中两个非零多项式，和g 的s 一多项式定义为 s p o l ( f , g ) = l c ( g o f l e ( f ) v g 式中和y 是使得l t ( f ) - = l t ( g ) v = l e m ( 1 t ( f ) ，i t ( 6 3 ) 成立的项。 例3 3 1 多项式只= x 1 x 4 + x 3 一x 1 x 2 和t 2 = 2 - 2 x 3 x 4 + 5 x l x 2 x 4 - 5 x l x 2 x 3 ，有 s p o l ( 互，) - 1 c ( 最) 鸽丘一1 c ( 鼻) 2 2 最 1 9 电子科技大学硕士学位论文 = 2 x , x