（应用数学专业论文）一类任意长度的1u常循环码的研究.pdf

一类任意长度的口+ 矽一常循环码的研究 摘要 近年来，很多从事编码密码理论的研究者将研究的兴趣从有限域上的编码 密码理论转移到有限环上，特别是多项式剩余整环y 阻】 ) 引起了学者们的广。 泛关注。本文主要研究环疋+ 髹疋上任意长度的( 1 + “) 一常循环码。 本文给出了环e + u y , 上任意长度的( 1 + 甜) 一常循环码的定义。定义了环 c + “上任意长度，? 的( 1 + ”) 一常循环码到商环c x 】( r 1 ) 的映射9 ，通过映 射伊确定了环疋+ u v o 上任意长度n 的( 1 + 甜) 一常循环码的结构，从而给出了环 疋+ 材c 上的( 1 + “) 一常循环码的分类，并给出了( 1 + 甜) 一常循环码的例子。进一步 讨论了( 1 + u ) 一常循环码对偶码的情况。最后，研究了环t + 以上g r a y 映射。 关键词：线性码：循环码：理想：常循环码 r e s e a r c ho f ( 1 + n ) 一c o n s t a c y c l i cc o d e so f a r b i t r a r yl e n g t ho v e rak i n do fr i n g s a b s t r a c t i nr e s e n ty e a r s ，t h et h e o r yo fr i n go f c o d i n ga n dc r y p t o g r a p h yi st h ek e yf o r r e s e a r c h e ri nc o d i n ga n dc r y p t o g r a p h y i np a r t i c u l a r ，t h es t u d yo fc o d eo v e rt h er i n g z f 】 ) w es t u d y ( 1 + u ) 一c o n s t a c y c l i ec o d e so v e rt h er i n g c + 材c w eg i v et h ed e f i n t i o no f ( 1 + u ) - c o n s t a c y c l i cc o d e so fa na r b i t r a r yl e n g t hno v e rt h e r i n g + 趾w ed e f i n eam a p 矿，w h i c h i sf r o mt h ea r b i t r a r yl e n g t h ( 1 + 甜) - c o n s t a c l i c c o d et ot h eq u o t i e n tr i n g s t h r o u g ht h em a p ，w eg i v et h es t r u c t u r ea n dt h ec l a s s i f i c a t i o n o f ( 1 + u ) 一c o n s t a c y c l i cc o d e so fa na r b i t r a r yl e n g t hno v e rt h er i n gc + 峨a n dw e c o n c l u d eb yg i v i n ga ne x a m p l eo f ( 1 + u ) 一c o n s t a c y c l i cc o d e s w e p r o v et h a tt h e 研a yi m a g e o fa n y ( 1 + u ) c o n s t a c y c l i ec o d e sw h i c hi sac y c l i cc o d eo fl e n g t hp n f u r t h e r m o r e ，w e d i s c u s st h ed u a lc o d e so f ( 1 + u ) 一c o n s t a c y e l i cc o d e s f i n a l l y , w es t u d yt h eg r a ym a po f ( 1 + u ) c o n s t a c y c l i cc o d e s k e y w o r d s ：l i n e a rc o d e ；c y c l i cc o d e ；i d e a l ； c o n s t a c y c l i cc o d e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得 金壁王些盍堂 或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：谢重l 签字日期：f 口年牛月j 矿日 学位论文版权使用授权书 本学位论文作者完全了解金目巴r 王些太堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权金日巴王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师 签字日期： 电话： 邮编： ( 滓妒l 扣 啶舯 谢 名 年 签 ， 者 “ 作 ： 文 期 沧 日 位 字 学 签 致谢 首先要向我的导师朱士信教授表示深深的谢意。两年多来，朱老师严谨的 治学态度、敏锐的思路、锲而不舍的精神和为人师表的风范是我今后从事学术 研究的楷模，他对我的悉心教诲将使我终身受益。感谢他对我的论文和工作给 以悉心指导和关怀，我的每一点进步和成果都是他无私的帮助和精心培养的结 果。 我同时要感谢开晓山师兄以及代数编码实验室的全体同学，正是与他们的 多次交流给予了我极大的帮助，开阔了我的思路和视野，使得我在完成论文的 工作中少走了很多弯路。 当然，我也要感谢我的父母和亲人，我的学业的顺利完成离不开他们长期 以来的鼓励和支持。 最后，谨向参加论文评审和论文答辩的专家教授们致谢! 作者：谢雯 2 0 1 0 年3 月2 0 日 第一章绪论 1 1 引言 近年来，关于编码理论的研究，以下几方面是比较活跃的：( 1 ) 环上码；( 2 ) 纠错码应用于密码学；( 3 ) 代数几何码；( 4 ) s p a c e - t i m e 码；( 5 ) t u r b o 码： ( 6 ) 量子纠错码及量子密码。就目前的几个发展方向来说，s p a c e t i m e 码以及 t u r b o 码这两个研究方向涉及更多的是有关通信工程方面的技术问题，而数学 工作者们更多讨论的是代数几何码与环上码的理论研究。 随着数字信息交换、处理和存储的大规模、高速数据网的快速发展，如何 保证数据在有噪声的信道中无误差的高速传输也变得越来越重要。正是社会的 这一巨大需求促进了纠错码理论及其工程应用的迅猛发展。到目前为止，经过 各国专家学者几十年的努力，己经在纠错编码理论方面取的了众多的科研成果。 特别是从本世纪6 0 年代起，由于有限域等数学理论的引进使得编码理论的研究 成果叠出。经过7 0 年代一段时间的沉寂后，学者们又引入新的数学工具，从而 开辟了新的研究领域，从另一个侧面入手对各种编码形式进行了系统而深入的 研究，纠错码不管在理论和还是实际应用方面都取得了极大的进展。各种纠错 码以其能自动地纠正或检测出数据传输过程中的误差为鲜明特点。 循环码是其中一类重要的纠错码，它建立在严密的代数理论基础之上。对 它的研究不仅取得了许多理论成果，而且在工程中也得到了广泛的应用。特别 是因电路设备简单、编译码快速、具有较高的纠错能力，而一直受到研究者的 关注。1 9 5 7 年p r a n g e 首先开始在有限域c 上研究循环码，此后，由于有限域 等数学理论的引进和不断完善，使得编码理论，特别是纠错码理论方面的研究 成果迭出。7 0 年代后，为了进一步深入开发编码理论所蕴含的潜力，编码工作 者又引入了布尔函数和矩阵方法等数学工具，从一个新的侧面入手对各种编码 形式进行了系统深入的研究( 如循环码、最佳二进制列、h a d a m a r d 编码、c o s t a s 列阵、并元码、光正交码、等重码和w a l s h 编码等) 。有限域上循环码的研究具 有重大的理论和实际意义。因此，循环码的研究格外引人注目。 随着有限域上循环码理论的日益成熟，循环码的基本理论发展至今已相当 的完善，但仍有许多的问题值得进一步地研究，通过引用新的数学工具来从不 同侧面入手更加完整地认识它的性质。因此对循环码的研究起着举足轻重的作 用。为了得到更一般的结论，学者们把循环码的定义进行推广。所以越来越多 的学者开始致力于有限环上循环码的研究。 在2 0 世纪7 0 年代就有学者开始关注有限环上的循环码，但真正成为热点问 题则是从2 0 世纪9 0 年代开始的。有限环上的循环码研究具有重大的理论和实际 意义。一方面，通过g r a y 映射，我们可以从某些有限环上的循环码映射为性质 较好的二进制码：另一方面，有限环上循环码的结构、性质以及各种参数的估计 也引起了大批学者的关注。研究有限环上不同码字的一般结构和对码字集合进 行分类是有限环上的纠错码理论研究中的两类热点问题，特别地，有限域上的多 项式剩余类环陋】 ) 引起了学者们的广泛关注。其中，当c 阻】 ) 中 七= 2 ，q = 2 时即环r = e + 蜗= 0 ，1 ，uu + 1 ) ，其中u 2 = 0m o d2 ，是介于环与域 之间的一种四元素环，因此分享了环z 。，域只的一些好的性质。我们可以把乙视 作环r 的子环，这意味着乙上的多项式分解在r 上同样有效。 从最初的文献 2 用e + “只上的线性码构造模格，至今已有大量的文献1 3 8 j 对环e m 】( “) 上的编码理论进行了研究文献 3 研究了环最+ 蜗上奇长度的 常循环码，并证明了只+ 以上的( 1 + “) 一常循环码的g r a y 象是二元线性循环码； 文献 4 研究了环e + 幔上任意长度的( 1 + 材) 一常循环码，并构造出参数为【1 2 ，7 ， 4 1 的最优二元线性循环码本文将环e + 蜗上的主要内容进行推广，得到了环 足+ “只上任意长度的( 1 + 铭) 一常循环码的一些基本性质。 1 2主要内容 目前，随着生产技术的飞速发展和理论研究的不断深入，有限环上的纠错 码理论和序列密码理论的研究不仅具有重要的理论意义而且具有重要的实际应 用价值。 近些年来，有限环上的纠错码理论的研究是纠错码理论研究领域的一个研 究热点。e + 幔是介于环z 。，域f 4 之间的一种四元素环，因此分享了环z 。， 域e 的一些好的性质；p u d a y a 等人首先将环c + 扰c + + 甜七- 1 巴用于最优频率 跳跃序列的构造，此类环上的编码理论研究成为一个新的热点。 本文从多方面研究了+ “0 + + “1 中的一类特殊环+ 峨上的常循 环码的各种性质，更为一般地研究了环兄+ 蛾上任意长度的( 1 + “) 一常循环码。 本文定义了环只+ 蛾上任意长度r 的( 1 + 豺) 一常循环码到商环c 缸】( r i ) 的映射伊，通过映射缈确定了环艺+ 甜c 上任意长度力的( 1 + 甜) 一常循环码 的结构，从而给出了环+ “兄上的( 1 + “) 一常循环码的分类，并给出了( 1 + u ) 一常 循环码的例子。进一步讨论了( 1 + u ) 一常循环码对偶码的情况。最后，研究了环 + 珥上g r a y 映射。 本文其它的部分是如下组织的： 第二章，给出了基本定义和本文需要的一些结果。 第三章，对比环最+ z 幔任意长度的( 1 + u ) 一常循环码，定义了环巴+ z ，c 上任意长度刀的( 1 + “) 一常循环码到商环艺嘲( 矿一1 ) 的映射矽，通过映射伊确定 了环凡+ u f 上任意长度聍的( 1 + 材) 一常循环码的结构。o 第四章，通过对兄+ 甜c 上任意长度，z 的( 1 + ) 一常循环码的结构的分析，讨 论各种可能情况，从而给出了环c + 甜c 上的( 1 + 材) 一常循环码的分类，并给出了 例子。 2 第五章，研究了环e + 甜c 上的( 1 + “) 一常循环码的对偶码。 第六章，研究了环t + u f 上的映射。og r a y 第七章，本文的总结与下一步研究计划。 本文针对有限环上的纠错码理论和序列密码理论中的若干问题作了一系列 的扩展和创新性研究。这些内容的研究对进一步丰富纠错码在环上的理论及构 造一些性能较好的码有一定的作用。 3 第二章预备知识 2 1常循环码简介 循环码是线性分组码中的一种非常重要的码，它是建立在严密的代数理论 基础之上。循环码的研究不仅在理论取得了许多丰硕的成果，而且在工程中也 得到了非常广泛的应用，特别是因电路设备简单、编译码快速、具有较高的纠 错能力等几个特点而一直受到关注。 上世纪5 0 年代后期首先开始在有限域凡上研究循环码，此后，由于有限 域等数学理论的引进和不断完善，使得编码理论，特别是纠错码理论方面的研 究成果迭出，码格外引人注目，为了进一步深入开发编码理论所蕴含的潜力， 编码工作者又引入了矩阵和布尔函数等数学工具，从一个新的侧面入手对各种 编码形式，进行了系统而又深入的研究。 但随着有限域上循环码理论的日益成熟，循环码基本理论发展至今虽已相 当地完善，但仍然有着许多的问题值得我们进行进一步的研究，通过不同的工 具从不同的侧面更加完整地认识它的性质。因此为了得到更一般的结论，学者 们将循环码的定义推广，由此常循环码的研究成为了新的热点。 设c 是 n ，k 线性码，若( c o ，c i ，c n - 1 ) c ，有心- ，c o ，巳一2 ) c ，则称c 为循环码。若( c o ，c l ，c 。一1 ) c ，有( 织- ，c o ，c n 一2 ) c ，其中力是固定的数， 则称c 为常循环码( 当旯= 一l 时，码c 称为负循环码) 。 对于任一码字c = ( c 。，c ，c 。一。) ，我们也可看做是一个刀维向量，可以用次 数不超过玎一1 的多形式c ( x ) = c o + c l x + + 乞一l x ”1 惟一的确定，c ( 功称为码字c 的对应多项式。显然c ( x ) 和c 是一一对应的。 码字c 循环移动f 位得到c = ( g w , 掣a 州，2 c , - l c o ，巳讲1 ) ，对应得码字多项 式为： c ( 功= 力厶一，+ 知。一j + l x + 十a c , i x i - 1c o x ，厶一“1 1 易知( x ) 量x t c ( x ) r o o d ( x “a ) ，这揭示了常循环码中多项式与码字循环移动之 间的关系，对于常循环码的研究起着重要的作用。 定义在环上常循环码可这样理解： 环r 上长为t l 的线性码是r “的加法子群，如果对尺的单位旯，长为以的线性 码c 在自同构： ：( c o ，q ，厶一1 ) hc o + q x 巳一l x ”。1 称c ( x ) = c o + q x 一q l x ”1 为c = ( c o ，c 1 ，c 。一1 ) 的码字多项式。只上长为刀的常循环 码可看作是商环c x l ( x ”一旯) 上的理想。 2 2 环e + 联e 简介 在有限域上纠错码，已有大量的文章进行研究。最近，环上码的研究引起 4 了研究者的极大兴趣。近年来，很多从事编码理论研究的学者将研究兴趣从有 限域上编码理论逐渐地转移到有限环上来。已经证明了某些好的非线性二元码 如k e r d o c k 码是一些z 4 线性码的g r a y 映射，使用g r a y 映射，一些线性和非线性二 元码可以构建为环上某些码的g r a y 映射。因此，这种方法有助于把某些非线性 二元码看作线性四元码的像。因此，四元环上的线性码的研究开始流行起来。 在四元环中有四个非同构环，他们是有限域g f ( 4 ) ，环z 。，环z ，u z ，和环r = z ，+ u z ，= 0 ，1 ，u ，u + 1 其中“2 = 0m o d2 环e + 饵是介于环与域 之间的一种四元素环，因此分享了环z 。，域e 的一些好的性质，所以此类环上 的编码理论研究成为继z 。环之后又一研究热点研究。我们可以把z ，视作环r 的 子环。这意味着z 上的多项式分解在r 上同样有效。例如n 为奇数时，多项式 ( r 一1 ) 在r 上和在乙上的分解相同。 b o f l n e c a z e 和u d a y a 研究了环r = 只+ f 2 上的奇长度循环码，证明了循环 码是疋= r x r x ”一1 ) 里的主理想。t b l a c k f o r d 研究了z 4 上的偶长度的负循环 码，证明了偶长度的负循环码是主理想环。最近，j f q i a n 等人研究了 s n = r x ( x “( u + 1 ) ) 上奇长度的( 1 + u ) 一常循环码，证明了( 1 + u ) 一常循环码 是& 中的主理想，同时也证明了e + 幔上奇长度n 的线性的( 1 + u ) 一常循环码 的g r a y 像是二元距离不变的线性循环码。 考虑环r = 最+ u r n = o ，l ，u ，u + 1 )其中甜2 = 0m o d2 ，域e 是r 的子环。 环r 也即剩余类环红陬】似2 ) ，其运算法则如下表： 水 0lu1 + u ooooo l01u1 + u u0u0u 1 十uo1 十uu1 + 01u1 + u 001ul + u 110l + uu uul + u0 1 1 + ul + uu1 0 显然，环r 为局部环，其惟一极大理想是 0 ，u ) ，特征为2 ，且e 可视为 其子环。 r 上长为n s j 线性码c 被定义为r - m o d u l er ”的加法子模。长为n 的线性码在 自同态盯作用下不变的是循环码，其中 仃瓴，c i ，靠d ) = 瓴- 1 ，q c 2 ，c n - 2 ) 5 长度为n 的线性码若在自同态y 作用下是不变得的，则称为线性( 1 + u ) 一常循环 码，其中 v ( c o q ，巳一1 ) = ( ( 1 + 材) q l ，q ，c 2 ，q 一2 ) 。 尺”的子集c 为线性循环码当其多项式表达式是r 。= r x ( x “- 1 ) 的理想。r ”的子 集c 为线性( 1 + u ) 一循环码当其多项式表达为s n = r t x ( x n 一( u + 1 ”的理想。 码u 的汉明重定义为嘞 ) 爿 fiu ；0 ) i ，即“中非零项的数日。线性码c 的极 小汉明重幽( c ) 定义为 如( c ) = m i n w m ( u ) ：甜c 且u o ) 。 码c 的汉明重量计数器昨( y ) 定义为 ( ) ，) = 户c = 4 少 其中4 = fp cl 0 j 鼍i i ，即c 中码重为i 的码字个数。 r 中的元素o ，1 ，u 和l + u 的李重嵋分别为0 ，l ，2 和3 进一步，中的n 元组的李重量是其各部分的李重量之和。 r 中码c 的李重量计数器定义为 厶( x ，y ) = = x 2 “唧y 。 令“= ( “。，u n 一，) 和v 虢，吒一。) 是环上的任意两个向量，我们定义他们的 内积豁。v = u o v o + u n i 一l 。若都v = 0 ，则u 和v 是正交的。定义循环码c 的对偶是 集合c 上： “r 或c 中所有v 有s ：甜1 ，= o ) 。显然c 上也是循环码。对于r 上任意线 性码c 有ic i ic 上i _ 4 ”。 定义商环r x 是ri 拘g o l o i s 环，其中厂( x ) 是r 上次数为朋的首一多 项式，一般用g r ( r ，m ) 表示。显然g r ( r ，m ) 是局部环，其最大理想是 ，剩余 类域是。 g r ( r ，m ) 中存在( 2 所一1 ) 次本原单位根号，若令f 。= - - 0 ，1 ，号，号卜2 ) ，则 g r ( r ，聊) 中的每个元素cn - - i 惟一的表示为c = 么+ 诏，其中a ，口f 辨由厂生成的 g r ( r ，聊) 的自同构群是阶为m 的循环群。 定义2 1令i 为r 。的理想，定义a ( o 为 a ( i ) = g ( 功：对i 中所有( 曲有厂( 功g ( 功= o ) ， 集合彳( j ) 称为i 在r 。中的零化因子。 定义2 2若f ( x ) = a o + q x + q ，是次数为r 的多项式，则八功的互反多项 式是多项式f ) = 口，+ a r l x + a o x 7 厂o ) 可以表达为厂( x ) = ，厂( 三) 显然若循环码c 的理想为i ，则c 上的理想为a ( j ) = f ( 功：，( 砷彳( z ) ) 。 6 2 3 环疋+ 即e 简介 环+ 嵋是指剩余类环r = c 【“】 2 ) ，其中u 2 = 0 ，p 为素数。环+ 蟛是 具有惟一的极大理想f ，口，) 的局部环。其运算法则如下： 环r = + “中的元素c 可以表示为c = ，+ 叼，其中，和g 都在中。 v c f ，c 2 天，其中c f = + u q j ，c 2 = r 2 + 叼2 ， 则加法定义为c = q + 巳= r + u q ，其中，暑乃+ 乃r o o dp ，q - q l + 劬r o o dp 。 乘法定义为c = c ，巳= r + u q ，其中，三乃r 2r o o dp ，q 兰q t q 2r o o dp 。 由于域e 是r 的子环，所以e 上的因式分解在r 上同样有效。r 上长为r l 的线性码是r ”的加法子群。如果r 上长为n 的线性码c 在自同构： 仃五：瓴，c i ，c 2 ，乞_ ) h ( 五乞。，c o ，乞一2 ) 下不变，则称码是见一常循环码。特别地，当名= 1 时，称c 为r 上的循环码；当 2 = l + u 时，c 为r 上的( 1 + u ) 一常循环码。定义r ”到r 【胡必矿一名) 上的映射 p ：( c o ，q ，乞，1 ) 一c o + c z x + c 2 x 2 + 一l x 卜1 称c ( x ) = c o + c x + c 2 x 2 + c n l x 加1 为c = ( c o ，c i ，c 2 ，一1 ) 的码字多项式。若将c 中的 码字( c o ，q ，c 2 ，c n 一1 ) 等同于码字多项式e ( x ) = c o 4 - c x + c 2 x 2 + 巳一l x 州，则r 上长 为n 的常循环码可看作商环r 【x 】，( 一旯) 的理想。特别的，记1 , = l + u 时， s 。= rm ( x ”- 0 + z ，) ) 。 本文中设定任意长度珂= p 。朋，其中p 为素，g c d ( p ，柚= 1 。 令u1 1 ( u o ，一。) 和 ，= ( ，一。) 是环上的任意两个向量，我们定义他们的 内积u v = u o + 1 吒1 0 若u - v = 0 ，n u 和v 是正交的。定义循环码c 的对偶是 集合c 上= 伽r 或c 中所有v 有s ：1 ，= o ) 。显然c 上也是循环码。 定义2 3令i 为r 。的理想，定义么a ) 为 a ( i ) = g ( x ) ：对i 中所有f ( x ) 有厂( x ) g ( 功= o ， 集合a ( t ) 称为i 在r 。中的零化因子。 定义2 4若厂( x ) - - c t 0 + 口l x + q ，是次数为r 的多项式，则f ( x ) 的互反多项 式是多项式f ( x ) = q + q l x + a o x 7 厂( x ) 可以表达为厂( x ) = ，( 三) 显然若循环码c 的理想为i ，则c 上的理想为彳( ，) = f ( x ) ：厂( x ) 彳( ，) ) 。 2 4 理论比较及研究的立意 2 3 1 理论比较及优缺点 相对于环五+ 嵋来说，环+ 晦的范围扩大了，从2 维的形式扩展到了 7 p 维的形式，因此对于实际环境来说b 环疋+ 啦的情况更加一般化，适用性更 广泛，因为当p 取2 的时候，环c + 圯的形式就是环e + 峨的形式。 通常来说，应用于只+ u 6 上的编码的优点在于：机器语言中存在着0 ，1 的表示方式，而环e + 以中的2 维定义比较契合机器语言的表达，因而理论 到具体应用的过程更加直观方便，四元码e + u 6 本身可以应用于扩频通信、 保密通信等领域。但是，从研究背景的多元性和复杂性来说，e + 蜗的表达 相对来说有一定的局限性，所以有进一步研究和扩展的必要。 在f n + u f 的形式具有以下的优势：o 1 ) 维数的扩展决定了只+ “c 上编码表示范围更广。 2 ) 只+ u f 上编码的多元性和复杂性保证了生成的编码更加安全可靠。o 2 3 2 研究立意 基于环c + 呜相对环最+ u 6 的优势，以及现有的环+ 甜乞的研究现 状，本文着重研究了环+ 材任意长度上的( 1 + u ) 一常循环码。 8 第三章结构 3 1 环e + 峨上的( 1 + u ) 一常循环码的结构 定理3 1 设c 为s 中的线性码，定义 缈：c 专z 2 【z 】0 ”+ 1 ) q p ( a o + 口l x 十a n l 石”1 ) = 饰2 + 彳x + 2 一l x ”- 1 m o d2 则p 是环同态。 证明根据在r 和z 2 中有 + 6 ) 2 = 口2 + 6 2 ，证明可得。 f o 的像是个理想，因此是z 2 x l ( x ”+ 1 ) 中的循环码，这意味着h i l 妒= ( g ( x ) ) 其 中g ( x ) l ( 矿- 1 ) m o d2 。并且k e r 缈是由( 船( 功) 生成的，其中( 口( 功) 是z 2 i x ( x ”+ 1 ) 中 的循环码。因此a ( x ) l ( 一1 ) 。由此我们可以得到以下定理。 定理3 2 令c 是s 。中的线性常循环码，则c = ( g + 蜗口) ，其中 a lg ( 矿- 1 ) r o o d2 且d e g a d e g p 。 注意到c 的生成子g ( 曲，a ( x ) 都是 糟一1 ) r o o d2 的因子，不是o ”一( 1 + 掰) ) 的 因子。相信这个事实使( 1 + z 1 ) 一常循环码的研究更容易理解。 3 2 环c + “上的( 1 + u ) 一常循环码的结构 为了得到更一般的结论，把循环码的定义推广，对r 中任意元素a ，我们 记a 模u 为一a ，即一a - a ( m o d u ) 。注意到当p ，i l l 不互素时，x n l 在r 中分解不惟 一，例如在e + z 幔中x 2 - 1 = o + 1 ) 2 = + ( 1 + 甜”2 ， 我们用a ( x ) l ( x “- 1 ) m o dp 表示a ) 在e 【x 1 中整除矿- 1 。 定义3 1设c 为r 上长为n 的线性( 1 + u ) 一常循环码，定义c 到商环 乃【x 】( x ”- i ) 之间的映射 伊：c 一乞 x 】( x 再一1 ) 口o + 口i x + a 2 x 2 + 口x 扣1h 瓦+ 昂+ 一a 2 x 2 + 一a ni x 舻1 易验证9 是c 到商环c 【x 】o ”- i ) 的环同态。 任意r 中元素口( z ) = a , x ，6 ( x ) = b , x ，和c 【x 】( 矿- 1 ) 中元素 雨：n - i 承，丽= n - i 玑有q ( = 雨，q ( ：丽， 则显然有 9 ( p ( 口( x ) + 6 ( x ) ) = a ( x ) + 6 ( x ) ， 由定义的映射缈，可得到以下定理： 定理3 3 c 为r 上长为n 的线性( 1 + 甜) 一常循环码，c = ( 翻+ 印( x ) ，u a ( x ) ) ， 其中口( x ) ig ( x ) i ( 矿- 1 ) ，且d e g ( a ( x ) ) d e 甙( p ( 砌。 证明由t , o 的定义知，缈的像是c 【x 】o ”一1 ) 中的理想，这意味着h i l 伊= ( g ( x ) ) ， 其中g ) io ”- 1 ) m o dp 。而且k e r t p 是由獬( x ) 生成的理想，其中0 ( x ) ) 是 c 【x 】( 矿- 1 ) 中的理想，所以口( x ) i ( 矿- 1 ) r o o dp 。因此存在p ( 功c 【x 】，使得 c = ( g ( x ) + z 妒( x ) ，u a ( x ) ) ，其中d e g ( a ( x ) ) d e g ( ( p ( 石) ) 。 3 3 小结 通过对比环e 十“e ，我们在环e + 髓上定义了一个映射伊，并证明了这 个由环+ 盯到商环【x 】 ”一1 ) 之间的映射是环同态。通过这个映射伊我 们找到了找出了环之间的联系，从而确定了环+ 阳上长为n 的线性( 1 + 甜) 一 常循环码的结构。 1 0 第四章分类 4 1 环e + 以e 上的( 1 + u ) 一常循环码的分类 引理4 1 对任意整数l ，有o + + 1 ) ) 牡= o 十1 ) 牡。 证明 ( x + ( “+ 1 ) ) 2 l = ( x + ( z ，+ 1 ) 2 ) = “x + 1 ) 2 ) l = ( x + 1 ) 2 。 引理4 2 设n = 2 8 m 其中( 2 ，功= 1 ，则u 在最中属于理想( o + 1 ) ”) 和( o + 1 ) 2 ) 。 证明 在最中有， 材= 工”+ l = x 丁“+ l = ( x ”+ 1 ) r = ( ( x + 1 ) 厂( x ”r = o + 1 ) r 厂( x ) z = ( + 1 ) ( x ) z 因此，甜( ( x + 1 ) 2 ) 且甜( ( x ”+ 1 ) ) 。 引理4 3 若忍= 2 8 ，则对任何多项式p 且e o ，( 1 + 十1 ) p ) 在最中是单位。 证明 令k = 2 n i ，贝u ( 1 + ( x + 1 ) 7 p ) = 1 + ( x + 1 ) 肫p 七= 1 + ( x + 1 ) 2 ”p 七= l 定理4 1 令c = ( g ( x ) + 妒( 功，擞( x ”为鼠中的( 1 + 材) 一常循环码，其中甩= 2 。， 贝0c = ( d ( x + 1 ) 。) 其中d = 1 或u ，i 0 ，fi ( x ”- 1 ) ，gl ( x m - 1 ) ，且g c d ( 2 ，聊) = 1 。贝0c = ( 办) ，其中 h = g c d ( f , ( ，+ 1 ) g 。) 。 证明 注意到最中“= ( ，- 1 ) ，f 和( 矿+ 1 ) g 。是z 2 【x 】中的多项式， 因此h = g e d ( f , ( 矿+ 1 ) g 。) 存在。 令h = g c d ( f , ( 矿+ 1 ) 矿) ，则厂和( 矿+ 1 ) 矿( h ) 。因此c ( 功。 另一方面，h = 口厂+ p ( x ”+ 1 ) 矿j h c 。因此，c = ( j 1 2 ) 。 由引理4 4 知，( u g ) = ( 彳正如z ) ，其中2 ，之2 什1 。 若c = ( 厂。，u g 。) ，且f 2 ，则h = g e d ( f f , ( x ”+ 1 ) g ) = f 。 若f ，其中z = f ，则h = g c d ( f , u g ) = 。 定理4 3令c = ( g ( x ) + 妒( x ) ，幽( x ) ) 为最中任意的( 1 + “) 一常循环码，其中 甩= 2 8 m 且g o d ( 2 ，m ) = 1 。假设p ( 力0 ，则c = ( z “五b z 。) ，其中石，五，z 是 册一1 ) r o o d2 的首一二元因子且f l ，如，2 外1 。 证明假设p 0 ，考虑 非i x n 酉- - 1 ) ( 如) + 绯) ) 】吲( 弘1 m ( 器顺堋 = 咖+ “钳x n - - 1p ( 瑚= 咖( 1 + ( 蔷) p ( 瑚】_ og l 叫g 怫j 因此，”( 1 + ( x n 石- - 1 ) p ( x ) ) k e r 伊：( “口( z ) ) ， g ( x ) 所以，l + x 删 - 1 ，) 删= 口( x ) g ( x ) + ( x ”- 1 ) p ( x ) = g ( x ) 口( x ) 七( x ) 1 2 g ( 力+ 妒( 功= g ( 功口( 功七( 力。 因此c = ( g ( 功口( 功后( 力，加( 功) 。 但是 l + ( x g 【 x - j 1 ，) p ) = 口( x ) 后 ) 或l = 葛功( x ) + 口( x ) 尼( x ) g ( x ) a ( x ) = u a ( x ) p ( x ) + g ( x ) a 2 ( x ) 七( x ) 。 这意味着g ( x ) 口( 曲c 且c = ( g ( 砷口( x ) ，獬( 功) 。所以，我们可假定 c = ( g l - ( x ) g ：( x ) g ? ( _ x ) ，甜口( z ) ) ，其中吕( x ) i ( x ”一1 ) 。 因为( x ”- 1 ) = ( x ”- 1 ) r ，则每个蜀( x ) = z ( x ) ，其中z 是( x m 一1 ) m o d2 的首一的因子， 2 8 。所以c = ( z 1 月2 ，蜕) ，其中 z ) 是( x 卅- 1 ) m o d2 的首一互素的因子。由弓 理4 4 和引理4 5 知，c = ( z 力) ，其中丘l ( 矿- 1 ) m o d 2 且，f 2 ，2 “1 。 根据这个定理，我们可以把( 1 + 甜) 一常循环码分为以下三类。 推论4 1 令c = ( g ( 功+ 印( z ) ，绷( 瑚为最中任意的( 1 + 甜) 一常循环码，其中 n = 2 8 m 且g c d ( 2 ，胁) = 1 。则c 是以下形式之一： 1 c = ( g ) 其中gl ( 矿- 1 ) m o d2 2 c = ( 馏) 其中g l ( 矿- i ) m o d 2 3 c = ( 石五如，) 其中zl ( 矿一1 ) ，且存在i ，使得2 。 。( u f l ) c u r , 2t 。 o , f f 7 ) u f 。似；f 2 ) ( 可) 。( 蟛；) 。似) 。似；) i ；1 ( 1 ；1 2 ) 。( 1 ；f j1 g ；) 。( i1 2 ) 。( 1 ；l ；1 g ；1 ( o ) 4 3 小结 通过对环疋+ u f 的结构的分情况讨论，从而给出环疋+ 甜c 上任意长度的 ( 1 + u ) 一常循环码的分类。但是由于环疋+ u f o 比环e + z 幔情况更一般化，在 环e + 幔中有“2 _ 0 ，2 u = 0 ，而在环e + 砧c 中“2 - 0 而2 u = 0 不成立，所 以在处理过程中，原来的方法不能直接套用，处理过程也更加复杂。比如说在 环e + 幔上的( 1 + “) 一常循环码有一类是c = ( f ) ，k 的范围限定在k 2 什1 证 明时可利用平方后得到甜2 和2 的倍数的方法来简化过程，而e + 甜疋时就得有技 巧的多次尝试后才能找到一些多项式，利用互素得到结果，并且经证明后我们 发现在c + 甜c 上的一类( 1 + u ) 一常循环码c = ( 广) ，k 的范围限定在k 2 p 8 。 1 6 第五章对偶 5 1 环e + 髓e 上的( 1 + u ) 一常循环码的对偶 引理5 1 令c = ( g ) 为最中长为，7 = 2 。朋的( 1 + 甜) 一常循环码，其中g c d ( 2 ，朋) = 1 ， gf ( 矿一1 ) m o d2 ，d e gg = ，。则c 在欠中有极小生成集 = g ，x g x n - r - 1 9 ，u ，x u x u ) ， 且l c f = 4 n - , 2 7 。 证明 因为在瓯中u = o ”- 1 ) ， gl ( 矿一1 ) ，则u c 。 余下的证明类似于 6 中的定理3 证明。 引理5 2 令c = ( 昭) 为邑中长为 = 2 。m 的( 1 + 甜) 一常循环码，其中且 g c d ( 2 ，所) = 1 ，g l ( 矿一1 ) m o d 2 ，d e g g = ，。则c 在r 中有极小生成集 夕= 咯，u x g 1 t 3 c n 吖一g _ ， 且i c l = 2 卜7 。 证明因为由g ( x ) 生成6 f l - 元码的基为 g ，x g ，x n - r - i g ， 则码c = ( 昭) 有极小生成集夕= u g ，u x g ，娥n - r - i 蓟，因此lci - 2 ”7 引理5 3 令c = ( z 五如z 。) 为最中长为刀= 2 。m 的( 1 + l ，) 一常循环码， 其中 g c d ( 2 ，肼) = l ，假设存在且2 。 ，一，则， d e g ( q u f ) _ r + t - 1 n + t - 1 = d e g ( x n - r - i f g ) ， 因此譬矽s p a n o 。于是p 生成c 。 由c 的构造知，夕是极小生成集，且i c 悻矿叶2 “。 定理5 1 令c 为鼠中长为刀= 2 m 的( 1 + 甜) 一常循环码， 其中g o d ( 2 ，朋) = 1 。 1 若c = ( g ( x ”，则 2 若c = ( 曙( x ) ) ，则 4 ( c ) ：0 盟) ， g 彳( c ) ：掣) ， g c 上：( 铭0 盟) ) 。 g c - i - _ ：( 掣) ) 。 g 3 若c = ( z 五如z ) ，存在有2 。 注意到在环f ，+ h 上有“2 = o ，由n o l ( g + 印) = o 得“q g = o ， 于是 ula t g ，所以营la i 。又注意到u 营( g + u p ) - o ，于是a il 宫。所以q = 雪 由u a ( g l + u p i ) = 0 得u a g l = o ，于是u la g , ，所以磊l 口。又注意到 堙。( 岛+ 妒i ) = 0 ，于是口i 雪l 。所以g i = 舀。 1 8 由( g + 印) ( 岛+ 嗡) = 0 可得( g + u p ) ( 3 + u p l ) = 0 ，解得 a ：一删：一g + u p ， u gu a g 所以彳( c ) ： ， “口g c 上：彳( c ) ：枣+ 婀