（应用数学专业论文）剩余码及环fpufpu2fp上的循环码.pdf

剩余码及环乃+ 峨+ “2 上的循环码 摘要 随着通信系统的发展与应用，以有限域代数为基础，循环码为代表的代数 编码技术得到了迅速发展。近十几年来，有限环上的编码理论成为编码界新的 研究热点，原因是通过g r a y 映射，一些高效的二元非线性码可以看作是环乙上 线性码的二元象。 剩余码是性能良好的循环码，有着非常高的纠错能力，并且其码率高于或 等于l 2 。 本文主要研究了域上的剩余码以及环c + 峨+ 甜2 兄上重根循环码的结构。 具体内容如下： 研究了域e 上的四次剩余码的若干性质； 研究了环+ z 哆+ “2 c 上长为p 。的循环码的具体生成元。 关键词：剩余码；对偶码；幂等生成元；环上的码；重根码 r e s i d u ec o d ea n dc y c l i cc o d eo v e r 乃+ 绵+ 甜2 c a b s t r a c t w i t ht h ed e v e l o p m e n ta n da p p l i c a t i o no fc o m m u n i c a t i o ns y s t e m s ，a l g e b r a i c c o d i n gt e c h n o l o g y ，w h i c hi sb a s e do nf i n i t ef i e l d sa n dr e p r e s e n t e db yc y c l i cc o d e s ， h a sar a p i dd e v e l o p m e n t o v e rt h el a s td e c a d e ，t h et h e o r yo fe r r o r c o r r e c t i n gc o d e s o v e rf i n i t er i n g sh a sb e e nh o tr e s e a r c h e d ，i t sb e c a u s e dt h a tu n d e rt h eg r a ym a p s e v e r a lf a m o u sf a m i l i e so fg o o dn o n l i n e a rb i n a r yc o d e sc a nb ei d e n t i f i e da si m a g e s o fl i n e a rc o d e so v e r z 4 q u a d r a t i cr e s i d u ec o d ei sg o o dc y c l i cc o d ew i t hh i g he r r o r c o r r e c t i n gc a p a c i t y a n di t sc o d er a t ei sg r e a t e rt h a no re q u a lt o1 2 i nt h i st h e s i s ，w es t u d yr e s i d u ec o d e so v e rf i n i t ef i e l d sa n dr e p e a t e d - r o o tc o d e s o v e rr i n g + 嵋+ “2 a sf o l l o w i n g ： b i q u a d r a t i cr e s i d u ec o d e so v e rea n dt h eg e n e r a t o rp o l y n o m i a l so fc y c l i c c o d e so fl e n g t hp 5o v e r 乞+ 峨+ 甜2 a r er e s e a r c h e d k e yw o r d s ：r e s i d u ec o d e ；d u a lc o d e ；i d e m p o t e n tg e n e r a t o r ；c o d eo v e rr i n g ； r e p e a t e d - r o o tc o d e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已 经发表或撰写过的研究成果，也不包含为获得 金壁工些太堂 或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 岛芳 签字日期：功f 。年中月埸日 学位论文版权使用授权书 本学位论文作者完全了解金月巴工些盔堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权盒照工些太堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：幻7 存肇月8 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签 签字日期：( 湃( 细f 庐 电话： 邮编： 致谢 逝者如斯，不知不觉两年半的硕士生涯即将结束，而这一切又好像如昨天 般的近在眼前。在漫长的人生旅程中，两年半的时间并不算长，但对我而言，是磨 砺青春、挥洒书生意气的两年半，也是承受师恩、增长才干、提高学识的两年半。如 今，我将以一个全新的面貌，投入社会、投入到工作中。在此，谨向培育我的母校、 教导我的老师、帮助我的同学们致以最诚挚的谢意。这两年半里，我经历了很多事 情，也感悟到很多道理，而这些对我的人生都有着重大影响，是一笔宝贵的财 富，相信硕士毕业是我人生新的起点。 作为2 1 1 工程的重点高校，合工大如今已是桃李芬芳，它有着雄厚的师资力量、 悠久的文化积淀、笃定的治学理念，在此硕士毕业之际，也谨祝我的母校能够越办越 好，早日成为国内一流、国际知名的大学，为祖国培育出更多高素质的人才。 校园之景四季迭换，令人汲取；校园之人来来往往，使人感动；更忆师长学友， 点滴教诲和丝丝关怀，无不教人深刻于心。 首先，向我最尊敬的导师朱士信教授表达我最诚挚的谢意。恩师朱士信对 我学业上的悉心指导，使我顺利地完成了学位课程的学习和硕士论文的研究工 作。朱老师严谨的治学态度、执着的敬业精神将鞭策我不断地探求新的知识， 让我懂得如何去踏踏实实地工作；他处处为学生着想，让我明白如何去为人师， 如何彰显一名教师的独特人格魅力。在此，再次向朱老师表示深深的敬意和衷 心的感谢! 感谢实验室里的开晓山、唐永生、王玉、施敏加等师兄以及王菊香师姐在 学习上和生活中对我的帮助。在我情绪低落的时候，他们给予我鼓励；在我学 习中出现困惑的时候，他们给予我指导。和他们的交流总是使我受益匪浅。 感谢硕士研究生期间同在一起思考学习的同学谢雯、杨名慧、丁健、王军、 张秋红等，平时和他们的讨论拓宽了我的思维，丰富了我的知识。 感谢我的家人，没有他们的奉献、关怀和支持我不可能顺利完成这份学业。 尤其要感谢我的母亲，她始终在背后默默地支持着我，这份伟大而无私的母爱 是我最珍贵的财富，激励我走好人生的每一步。 感谢所有曾经关心和帮助过我的同学、朋友、老师和亲戚。 作者：高芳 2 0 1 0 年3 月 第一章绪论 1 1 引言 美国数学家s h a n n o n 在1 9 4 8 年所发表的著名论文“am a t h e m a t i c a lt h e o r y o fc o m m u n i c a t io n 口h 中提出了著名的抗干扰信道编码定理，从而开创了一门 现代科技中具有重大意义的崭新学科一信息论。h a m m i n g 和g o l a y 分别发表的 论文e r r o rd e t e c t i n ga n de r r o rc o r r e c t i n gc o d e s 和“n o t e so nd i g i t a l c o d i n g 北h 开创了与应用相结合的编码理论方法的研究。信息理论的发展和编 码方法的发展始终是相互依赖、相互促进的。信息论的应用从底层的通信到电 子的损耗都涉及到编码理论。 在信息的传输过程中有可能发生错误，能够在接收端自行发现或纠正的码称 为纠错码。上世纪五十年代s h a n n o n 发表论文指出，只要采用适当的纠错码， 就可在多类信道上传输消息。自s h a n n o n 的论文发表以来，人们经过持续不懈 的努力已经找到多种好码，可以满足许多实用要求，但在理论上，仍存在一些问 题未能解决。纠错码的纠错能力，由码字的极小距离决定。纠错码实现中最复杂 的部分是译码，它是纠错码能否应用的关键。纠错码传输的都是数字信号。这既 可用硬件实现，也可用软件实现。 分组码和卷积码是两类较重要的纠错码。分组码是对信源待发的信息序列进 行分组( 每组尼位) 编码，它的校验位仅同本组的信息位有关。自2 0 世纪5 0 年代分组码的理论获得发展以来，分组码在数字通信和数据存储系统中已被广泛 应用。卷积码不对信息序列进行分组编码，它的校验元不仅与当前的信息元有关， 而且同以前有限时间段上的信息元有关。卷积码在编码方法上尚未找到像分组码 那样有效的数学工具和系统的理论。但在译码方面，不论在理论上还是实用上都 超过了分组码，因而在差错控制和数据压缩系统中得到广泛应用。 迄今，纠错码已有4 0 多年的历史，其发展过程大致分以下几个阶段： l 、理论建立时期。5 0 年代至6 0 年代初，主要研究各种有效的编、译码方法，奠定了 线性分组码的理论基础；提出了著名的b c h 码的编码及译码方法以及卷积码的序列译 码：给出了纠错码的基本码限。 2 、线性分组码发展时期。6 0 年代至7 0 年代初，以代数方法特别以有限域理论为基础 的线性分组码理论得到成熟发展。不仅提出了许多有效的编译码方法，如门限译码、 迭代译码、软判决译码和卷积码的维特比译码等。而且注意到了纠错码的实用化问题， 讨论了与实用有关的各种问题，如码的重量分布、译码错误概率和不可检错误概率的 计算、信道的模型化等，所有这些问题的研究为纠错码的实用打下了坚实基础。 3 、纠错码应用于实际。7 0 年代初至8 0 年代，以g o p p a 为首的一批学者，构造了一类 g o p p a 码，在这期间大规模集成电路和微机的迅速进展，为纠错码的实用打下了坚实 的物质基础，因而与实用相关的各种技术及有关问题得到了极大关注，并在实用中取 得了巨大成功。如美国在7 0 年代初发射的“旅行者”号宇宙飞船中，成功地应用了 纠错码技术，使宇宙飞船在极其遥远的距离( 3 0 亿公里) ，向地面传回了天王星、海王 星等星体的天文图片，发现了天王星的9 个卫星和光环以及海王星的6 个卫星和光环 等许多极其宝贵的资料。若不应用纠错码，这些成就的取得是不可想象的。应当指出， 在此期间利用f f l 技术，从频谱观点研究纠错码，受到了特别重视，使得很多熟悉信 号处理技术但不熟悉有限域理论的工程师们，能够较快地掌握纠错码理论，并能熟 练地应用于实际中，从而为纠错码在各类通信系统中的广泛使用，起到了极好的推动 作用。 4 、环上码的发展。1 9 9 4 年a h a m m o n s 1 等人通过适当的定义发现了几种著名 的非线性码可表示为环z 4 上多项式环中的理想，其本质就是环z 4 上的线性码， 从而使得环上码的研究成为编码界讨论的热点。 1 2 编码理论的发展 数学和计算机科学中的最新研究成果被应用于编码理论和密码学中，不仅 促进了编码理论和现在密码学的迅速发展，也刺激了数学和计算机科学中的一 些分支的发展。 编码理论在近几年来主要有以下几方面的发展： 环上的码：1 9 9 4 年a h a m m o n s 口3 等人通过适当的定义发现了几种著名的非 线性码可表示为环z 4 上多项式环中的理想，其本质就是环乙上的线性码，从而 使得环上码的研究成为编码界讨论的热点，并对另一四元素环e + 甜e 也进行了 研究。目前讨论环上的码，主要问题集中在对环上码的参数估计、环上码的译 码方式、环上循环码的结构和分布等； 代数几何码：该码是由上世纪八十年代由一位苏联数学家将代数几何通过 编码理论而应用到通信工程中去。由于代数几何码的卓越纠错和检错性能， 代数几何码的研究仍然是信息论中的一个热点。代数几何码研究的热点主要是 集中于渐进问题、码的构造、译码、最小重量、重量分布等问题上； 纠错码在密码学中的应用：m c e l i e c e 在1 9 7 8 年首次提出基于纠错码的公 钥密码体制之后，利用纠错码构造各种密码体制和认证体制的研究得到了迅速 的发展； t u r b o 码：该码是法国学者在1 9 9 3 年发现的一种新的差错控制码，这种 码的纠错性能几乎接近s h a n n o n 限，在诸如远程数据通信、数据的磁记录等广 泛的应用领域是性能最好的码。它的出现是信道编码研究的一项重大突破。 时空码：该码是美国学者t a r o k h 和c a l d e r b a n k 等人发现的一种码，它 用在多通道、多天线、无线通信信道中，可以极大地改进这些信道的性能； 量子码：量子纠错码和量子密码是量子信息论的两个基本方面，他们都 基于量子计算和量子算法，研究量子计算和量子算法是当今信息科学中的最前 沿方向之一。 2 一 1 3 本文的主要内容 本文第一章介绍编码理论的产生及其发展；第二章介绍了域只上的二次剩 余码及整数环上二次剩余码的相关性质；并研究了域只上的四次剩余码，给出 了四次剩余码的定义，研究其码字重量、极小汉明距离、幂等生成元等好的性 质；第三章介绍了四元素环z 4 及最+ 幔上长为2 8 的循环码的结构；研究了环 疋+ z 以+ 甜2 e 上长为p 5 的循环码，给出了循环码的具体生成元；第四章给出本 文总结以及下一步研究计划。 3 一 第二章有限域e 上的四次剩余码 2 1 二次剩余码 原始二次剩余码是素数长度的循环码，它具备良好的性能，在编码理论中 有着重要的地位。在1 9 6 6 年，a n d r e wg l e a s o n 首次给出了二次剩余码的定义， 而在二次剩余码随后的发展中g l e a s o n 也起到了深远的影响参数为 2 3 ，1 2 ， 7 】的二元g o l a y 码和参数为【1 1 ，6 ，5 】的三元g o l a y 码都是二次剩余码，且二次 剩余码的扩展码的自同构群具有很好的性质。 群表示、二次剩余、互反性、格、散在单群、h a d a m a r d 矩阵、区组设计等 代数数论和编码理论方面的知识为二次剩余码的研究提供了理论依据。二次剩 余码有着极高的纠错检错能力，其极小h a m m i n g 距离所具有的平方限定理，为 研究该码的重量分布提供了一个重要指标。 1 9 7 1 年之后，二次剩余码的扩展码被研究，码的素数长度得到了推广。 d e l s a r t 利用反演平面推广了二次剩余码，获得素数幂分组长度的二次剩余码， 被称为广义二次剩余码，随后c a m i o n 和w a r d 应用非二元域给出了广义二次 剩余码的另一种描述。s h a n n o n 和m a c w i l l i a m s 在纠错码理论一书中详细介绍 了二次剩余码及其广义二次剩余码的线性特征，而h u f f m a n 则具体讨论了有关 扩展广义二次剩余码的自同构群。 随着有限环上循环码研究的深入，一些学者试着将有限域上二次剩余码的 研究工作转移到环上二次剩余码上来。c a l d e r b a n k 等人初步研究了环上二次剩 余码，并给出了2 一a d i c 整数环乙上的幂等生成元的形式，但没有讨论所定义 环上二次剩余码的具体性质其后b o n n e c a z e 等人较详尽的讨论了环乙上二次 剩余码，它利用h e n s e l 提升很好的定义了环z 4 以及2 - a d i c 整数环上的二次剩 余码，讨论了其扩展码的自同构群并部分讨论了其一些相关性质。p l e s s 等 人则用更基础的编码和数学理论来定义环乙上二次剩余码，进而说明它们具有 类似有限域上二元二次剩余码的性质。其后一些作者利用p l e s s 的思想去推广 了环z 4 上的二次剩余码，m e ih u ic h i u 就讨论了环乙上的二次剩余码，更一 般的，卢慧敏讨论了环z 1 。上的二次剩余码 2 1 1e 上的二次剩余码 考虑二次同余方程 x 2 主a ( m o d p ) 当p i an o ，方程仅有一个解x 三o ( m o d p ) ，所以一般考虑p 不整除口的情形。 如果以上同余方程有解，则称a 是模p 的二次剩余；否则称a 是模p 的二次非剩 4 一 余。若口是模p 的二次剩余，则方程恰有两个解。此外，若a 是模p 的二次剩余， 则模p 的a 的同余类中的每个数都是二次剩余。对于二次非剩余亦是如此。 设p 是奇素数，则模p 的任一完系中恰有( p 一1 ) 2 个二次剩余，以及 ( p 一1 ) 2 各二次非剩余；并且模p 的全部二次剩余在数 1 2 , 2 2 ，( 孚) 2 所属的( 模p 的) 同余类中。 设p 是素数，则模p 的两个二次剩余之积是二次剩余，模p 的一个二次剩 余和一个非二次非剩余之积是二次非剩余，模p 的两个二次非剩余之积是二次 剩余。 对每个整数口，定义模p 的l e g e n d r e 符号： ，、l 1 ，如果口是蝴二次剩余 l 旦l ： 一1 ，如果a 是模瑚二次非剩余 、p 10 ，如果p i 口 ( 欧拉判别法则) 设p 为奇素数，则 i 旦l _ 口( 川) 2 ( m o d p ) p 由欧拉判别法则可以直接有下面的两个式子： 设p 为奇素数，则 f ，一1 1f1 ，p 晕l ( m o d 4 ) l l 暑 lp 【_ 1 ，p 玺3 ( m o d 4 ) f ，2 、f1 ，p 兰+ l ( m o d 8 ) t p j 【一1 ，p 兰+ 3 ( r o o d 8 ) 由上式知，如果p 为奇素数，且p - - + _ 1 ( m o d 8 ) ，那么2 是模p 的二次剩余。 设q 是模p 的二次剩余之集，n 是模p 的二次非剩余之集。因为2 q ，从 而q = 2 0 ，因此 g ( x ) = 兀r q ( x 一口7 ) e 孙，z ( x ) = 兀舢( x 一口厅) 日z 】 其中口是最的某扩域上的p 次本原单位根。显然有x p 一1 = 一1 ) g ( x ) 船( x ) 。 定义2 1 1 n 们称以g ( x ) ，( x - 1 ) q ( x ) ，珂 ) ，o 一1 ) n ( x ) 为生成多项式而生成的 f ： x l ( x 一1 ) 上的循环码为二次剩余码，分别记作c l ，e ，c 2 ，五。 显然c l3 互，g3 己，且e 由c 1 中重量为偶数的所有码字组成，己由c 中 重量为偶数的所有码字组成。g ，g 是码长为p ，维数为( p + 1 ) 2 的二次剩余码， 称之为增广二次剩余码；g ，g 是码长为p ，维数为( p 一1 ) 2 的二次剩余码，称 之为删除二次剩余码。 5 一 设p = 7 ，则c 1 的生成多项式为 + 口) ( x + 口2 ) + 口4 ) = x 3 + x + 1 ，其中口r ， c l 是参数为 7 ，4 ，3 的h a m m i n g 码。己是c 1 的子码，参数为 7 ，4 ，3 的h a m m i n g 码，c 2 的生成多项式为( x + 口3 ) ( x + 口5 ) ( x + 口6 ) = x 3 + x 2 + 1 ，与c i 等价。 二次剩余码有很高的极小距离，有以下平方根限定理： 定理2 1 2 n 们用d 表示c l 或g 的极小距离，则d 2 p 。更进一步地，如果 p 暑一l ( m o d 4 ) ，则极小距离d 有更好的性质，d 2 一d + l p 。 d 常常比定理2 1 2 中的下界要大很多。 二次剩余码又常常用幂等生成多项式来描述，下面考虑剩余码的幂等元， 首先介绍幂等元的概念及基本性质，然后给出剩余码的幂等生成元以及其对偶 码的相关性质。 商环e b 】0 p - 1 ) 中的多项式e ( x ) ，如果满足e 2 ( x ) = e ( x ) 则称e ( x ) 是幂等 多项式。在e 中，显然有，如果e ( x ) 是幂等多项式，则1 + e ( x ) 也是幂等多项式。 循环码伊= 有唯一的幂等生成元e ( x ) ，使得伊= ；且存在p ( x ) ， 使得e ( 石) = p o ) g ( 功；e ( a ) = 0 当且仅当g ( a ) = 0 ；e ( x ) 是幂等多项式当且仅 当e ( a 。) = 0 或l ，i = o ，1 ，n - 1 。 定理2 1 3 n 町若p 三一l ( m o d4 ) ，则选择适当的p 次本原单位根口，使得 c i ，e ，c 2 ，己的幂等生成元分别为 毛( x ) = 嘲， 乞( x ) = l + 。矿，e ( x ) = 。矿，c ( x ) = 1 + ，e q 证明：因为2 是模p 的二次剩余，所以毛2 ( x ) = 日( x ) ，从而毛( x ) 是幂等多 项式。因此岛似) = o 或l 。对任一二次剩余s ，我们有 气( 口。) = ，e q - e ，f e ( 口，= 乓( 口) 同理对任一二次非剩余，我们有 毛( 口) = ，e q 口= 哪口= 岛( 口_ ) 由于e ) + 乓 一) = l ，从而 对任意s q ，e 5 ) = 0 且对任意t n ，e q 。) = 1 ，或者 对任意s q ，乓 5 ) = 1 且对任意，n ，乞 。) = 0 。 选择适当的饼，使得对任意s q ，毛 5 ) = oh _ 对任意t n ，乓 ) = 1 成立， 从而e ) 是c l 的幂等生成元。 对任意，n ， e ，( 口) = 。e 口州= ，。d 口7 = o ； 对任意s q ， e ( 口。) = 。口”- z 以口盯= 1 从而e ( x ) 是c 2 的幂等生成元。 对任意s q ， 。) = o 且( 1 ) = o ，从而( x ) 是e 的幂等生成元，同理e ( x ) 是 6 一 c 2 的幂等生成元。 若p = l ( m o d 4 ) ，则选择适当的p 次本原单位根口，c l ，己，c 2 ，己的幂等生成元分 别为l + ，e 口，删r ，l + 删r ，嗍x 7 二次剩余码的对偶码有以下性质： 定理2 1 4n 们若p 暑一l ( m o d4 ) ，则c l 上= 己，c 2 上= 己；若p - l ( m o d 4 ) ，则c l 上= 己， c 2 上= 己。在这两种情形中都有，c l 由己和1 生成，c 2 由己和1 生成。 2 1 2 乙上的二次剩余码1 二次剩余码是可以由幂等生成元定义的循环码。设p 为奇素数，且 p 兰l ( m o d 8 ) ，用q 表示模p 的二次剩余之集，n 表示模p 的二次非剩余之集。 令 e l = 卸，乞= 洲z 则e l ，e 2 是二元幂等多项式。 命题2 1 5 设p 为奇素数且p 暑+ l ( m o d 8 ) ，则存在，使得p + l 或p - 1 = 8 r ，以下 两种情形成立： 1 ) 当，为奇数时，e f + 2 e j 7 f 【i1 + 3 q + 2 e j 是z 4 上的幂等元，其中f ，= 1 ，2 ；i ，。 2 ) 当，为偶数时，匏，和l + q 是z 4 上的幂等元，其中f = l ，2 。 定义2 1 6 由命题2 1 5 中的幂等生成元所生成的z 4 一循环码称为z 4 一二次剩 余码。 令h = l + 白+ p 2 ，则当p 兰l ( m o d 8 ) 时，h 是乙中的幂等元；当p 暑- l ( m o d 8 ) 时， 3 办是z 4 中的幂等元。 设c 是环z 4 上的循环码，其幂等生成多项式为p ( x ) ，则c 的对偶码c 上的幂 等生成多项式为1 - e ( x 一) ；如果循环码c l ，c 2 的幂等生成多项式分别为e ie ：，那 么c lr 、c 2 的幂等生成多项式为q 乞，c i + c 2 的幂等生成多项式为q + 乞一q p 2 。 定理2 1 7 设p 为奇素数且p + l = 8 r ， 若，为奇数，令q = ( e l + 2 e 2 ) ，q 2 = ( e 2 + 2 q ) ，g = ( 1 + 3 e 2 + 2 岛) ，q = ( 1 + 3 e l + 2 e 2 ) ； 若，为偶数，令q = ( 3 e 。) ，q = ( 3 e 2 ) ，g = ( 1 + 吃) ，q 2 = ( 1 + q ) ； 则以下结论成立： 1 ) q l ，q 2 等价，q 7 ，q 2 等价； 2 ) iq 1 l = i q l 4 印+ 1 彬，l 纠l = l g l = 4 q - 1 班； 3 ) q ir 、q 2 = ( 3 h ) ，q l + q 2 = z 4 b 】o p 一1 ) ； 4 ) q = q ；f + ( 3 h ) ，q 2 = g + ( 3 h ) ； 5 ) 纠，鲮是自正交码，且甜= 纠，酣= 残。 定理2 1 8 设p 为奇素数且p 一1 = 8 r ， 若，为奇数，令q l = ( 1 + 3 e l + 2 e 2 ) ，0 2 = ( 1 + 3 e 2 + 2 e 1 ) ，q 1 7 = ( e 2 + 2 e 1 ) ，q 2 = ( g l + 2 e 2 ) ； 若，为偶数，令q l = ( 1 + 巳) ，q = ( 1 + 巳) ，q = ( 3 e ：) ，0 2 = ( 3 q ) ； 则以下结论成立： 1 ) q ，0 2 等价，g ，q 2 7 等价： 2 ) l g l = i q l = 4 p “班，l 纠| = lq ! ；i = 4 印1 v 2 ； 3 ) q lr 、q 2 = ( 而) ，q l + q 2 = z 4 【x 】( x p 一1 ) ； 4 ) q = 斜+ ( j 2 ) ，q 2 = 鳞+ ( 向) ； 5 ) 讲= 残，酣= 纠。 2 1 3 z 8 上的二次剩余码3 设p 为奇素数，且p 兰l ( m o d 8 ) ，用q 表示模p 的二次剩余之集，n 表示模 p 的二次非剩余之集。令 q = ，。口x ，巳= 旭x 。 设h = 1 + e i + e 2 ，当p 兰1 ( r o o d 8 ) 时，h 是z 8 中的幂等元；当p 兰一l ( m o d 8 ) 时， 7 乃是z 8 中的幂等元。 当p 暑- l ( m o d 8 ) 时，2 e l e 2 = 6 + 7 e ? + 7 + 5 e j + 5 e 2 ：当p 暑l ( m o d 8 ) 时， 2 e i e 2 = 7 彳+ 7 霹+ 7 q + 7 e 2 。 定理2 1 9 设p 是奇素数，且p 暑_ + l ( m o d 8 ) 当p + l = 8 r 时 1 ) 当，= 4 k 时，l + q ，7 q 是磊【z 】 p 一1 ) 上的幂等元，其中，= 1 ，2 ； 2 ) 当，= 4 k + 1 时，4 + 2 e i + 5 e ，5 + 3 e , + 6 p ，是z 8 x 】 p - 1 ) 上的幂等元，1 f 2 ； 3 ) 当，= 4 k + 2 时，3 巳+ 4 e j ，1 + 4 岛+ 5 9 ，是z 8 【z 】( x p 一1 ) 上的幂等元，1 j 2 ； 4 ) 当，= 4 k + 3 时，4 + e ，+ 6 e ，5 + 2 e _ f + 7 p ，是z 8 【x 】( 扩- 1 ) 上的幂等元，l f j f 2 ； 当p - 1 = 8 r 时 1 ) 当，= 4 k 时，l + q ，7 口，是z 8 x 】( x p 1 ) 上的幂等元，其中f = 1 ，2 ； 2 ) 当，= 4 k 十1 时，4 + e ，+ 6 e ，5 + 2 e _ f + 7 p ，是磊【x 】 p - 1 ) 上的幂等元，l f 2 ； 3 ) 当，= 4 k + 2 时，3 e j + 4 e ，1 + 4 呼+ 5 f ，是z x l ( x p 一1 ) 上的幂等元，1 ，2 ； 4 ) 当，= 4 k + 3 时，4 + 2 e ，+ 5 p ，5 + 3 e f + 6 p ，是z 8 x 】 p - 1 ) 上的幂等元，l f 2 。 定义2 1 1 0 称由定理3 1 中的幂等元生成的循环码为z 8 上的二次剩余码，简 称为z 8 一二次剩余码。 8 一 关于互一二次剩余码，有以下性质： 定理2 1 1l 设p 是奇素数，p + l = 8 r ， 当，= 4 k 时，令q = ( 7 e j ) q 2 = ( 7 e 2 ) ，纠= ( 1 + e 2 ) ，g = ( 1 + q ) ； 当，= 4 k + l 时，令g = ( 4 + 2 e l + 5 e 2 ) ，q i = ( 4 + 2 e 2 + 5 e 1 ) ，q f = ( 5 + 3 e i + 6 e 2 ) ， 残= ( 5 + 3 e 2 + 6 e 1 ) ； 当，= 4 k + 2 时，令q = ( 强+ 4 p 2 ) ，q = ( 3 e 2 + 4 e 1 ) ，研= ( 1 + 4 e i + 5 e 2 ) ， 奶= ( 1 + 4 e 2 + 5 e 1 ) ； 当，= 4 k + 3 时，令q l = ( 4 + q + 6 e 2 ) ，q 2 = ( 4 + e 2 + 6 e 1 ) ，g = ( 5 + 2 e l + 7 e 2 ) ， 残= ( 5 + 2 e 2 + 7 q ) ； 则对于z 8 上的二次剩余码q ，q 2 ，纠，g ，以下结论成立： 1 ) q ，q 2 等价，g ，q 等价； 2 ) i o , l = l o ：l = 8 q “班，例= 例= 8 一v 2 ； 3 ) qn q = ( 7 h ) ，g + 9 2 = z 8 【x 】( 矿一1 ) ； 4 ) q = 纠+ ( 7 h ) ，q 2 = g + ( 7 h ) ； 5 ) 纠，g 是自正交码，且甜= 纠，酣= 残。 定理2 1 1 2 设p 是奇素数，p 一1 = 8 r ， 当 ，= 4 k 时，令q = ( 1 十f ) ，q 2 = ( 1 + e 2 ) ，q ；= ( 7 e 2 ) ，鲮= ( 7 岛) ； 当厂= 4 k + l 时，令q 1 = ( 5 + 2 e 2 + 7 e 1 ) ，0 2 = ( 5 + 2 e 1 + 7 e 2 ) ， 纠= ( 4 + e 2 + 6 e 1 ) ，g = ( 4 + q 十6 e 2 ) ； 当r = 4 k + 2 时，令q l = ( 1 + 4 e 2 + 5 q ) ，q 2 = ( 1 + 4 q + 5 p 2 ) ， 纠= ( 3 e 2 + 4 e i ) ，残= ( 3 e l + 4 e 2 j ； 当，i = 4 k + 3 时，q l = ( 5 + 3 e 2 + 6 q ) ，q 2 = ( 5 + 3 q + 6 e 2 ) ， 纠= ( 4 + 2 e 2 + s e l ) ，残= ( 4 + 2 q + 5 e 2 ) ； 则对于互上的二次剩余码q ，q ，纠，g ，以下结论成立： 1 ) g ，q 等价，q ，易等价： 2 ) iq l l = i q i _ 8 川v 2 ，l 纠l = l 残i _ 8 。v 2 ； 3 ) gr 、q = ( 办) ，g + q = 乙 x 】 p 1 ) ； 4 ) q l = 纠+ ( 厅) ，皱= 残+ ( 向) ； 5 ) 甜= 残，醇= 纠。 2 1 4 z 2 。上的二次剩余码3 1 由于参数的增加，在z 4 ，z 8 上涉及的参数运算的证明在乙上变得复杂。 命题2 1 1 3 在z 2 。上存在，使得力是幂等元。 在z 4 ，磊上，二次剩余码是以嘲+ v e 2 + w ( “，v ，we 乙或z 8 ，u 1 ，) 形式的多项式 为幂等生成元生成的码，可以证明在z 2 。上，这种幂等元同样存在。 9 一 命题2 1 1 4 设p 是奇素数，p + l = 8 r ，= 2 卜1 彩+ 2 卜3 m + a ， 其中国，m ，a 乙，a 2 卜3 ，则以下结论成立 1 ) 存在u e j + r e ，+ w ( 材，v ，z ，1 i 2 ) 形式的幂等元，其中w - ( 2 k - i m + 4 a - 1 ) y 。 2 ) 似+ y ) p j + ( v + y ) p ，+ w ( 1 i 歹2 ) 也是幂等元，其中= ( 2 扣1 m + 4 a ) y 。 令u = u + y ，= v + y 。 定义2 1 1 5 令q = ( u e l + v e 2 + 川，纠= ( u e 2 + 嵋+ 们，q = 0 i + v e 2 + w ，) ， 踢= e 2 + v e l + w ) ，这匹个循环码叫做z ：。【x 】( 妒- d 上的二次剩余码。 定理2 1 1 6 当p = 8 r 一1 时，互。e x i ( x p 一1 ) 上的二次剩余码具有如下性质： 1 ) 蜴，纠等价，q ，q 2 等价； 2 ) i q , i = i q ：i = ( 2 ) p 1 们，1 0 2 i = 残i _ ( 2 ) 川v 2 ； 3 ) 0 2r 、踢= ( y 矗) ，0 2 + 残= z 2 。 x l ( x p - 1 ) ； 4 ) q = g + ( 7 办) ，残= g + ( ， ) ； 5 ) q ，纠是自正交码，且甜= g ，g 上= 纠。 当p = 8 r + l 时，类似的结论也成立。 2 2 有限域最上的四次剩余码 s h a n n o n 和m a c w i l l i a m s 在纠错码理论一书中详细介绍了二次剩余码的线 性特征。本节研究了压上四次剩余码的相关性质。首先给出e 上四次剩余码的 定义，其次研究了四次剩余码的码字距离及其对偶码的生成多项式，最后讨论 了四次剩余码的幂等生成元的性质。 2 2 1 四次剩余码的定义 由潘承洞等人在代数数论一书中给出的一个关于四次剩余码的存在定理 出发，首先介绍这个定：哩： 引理2 2 1n 4 1 设p 为奇素数，且p 兰l ( m o d 4 ) ，若p = 甜2 + 1 ，2 ，其中u 三l ( m o d 4 ) ， 1 ，暑o ( m o d s ) ，则关于x 的同余方程x 4 暑2 ( m o d p ) 有解。 下面介绍四次剩余码的性质，以下的p 满足引理2 2 1 中的条件。 令q 为所有模p 的四次剩余之集，即 q o = 口4 c i o f ( p 一1 ) 4 并设q = 口和“l o f ( p 一1 ) 4 ，q 2 = 口4 “2 f p l o - i = ：易g 州一， 进一步，设 q l = ( 国l ，国2 ，) 7 ，q 2 = ( “，2 ，以) r m n 。，( r ) ， 定义q 。，q 2 的内积为 ( q 。，q ： = 2 。 c 的对偶码定义为 c 上= q 2 眠。，( 足) i ( q 2 ，q i = o ，v q l c ) ， 易知c 上仍是鸠。，( 尺) 上的线性码。 设 g = ( 三吕 ，( 主3 ) ) ，g = ( 33 ) ，( 3 言) ) 这两个码的p 重量计数器均为l + z 2 。设c l 上和c 2 上分别是c l 和c 2 的对偶码。由于c i 上和 c 2 上都包含1 2 8 个码字，我们只给出它们的重量计数器； ( z ) = l + 6 z + 1 7 2 2 + 2 4 2 3 + 8 0 2 4 ， ( z ) = 1 + 4 z + 2 1 2 2 + 3 0 2 3 + 7 2 2 4 。 p 重量与其行元素的阶有着密切的联系。为了克服发生在上面的例子中的问题， 我们可以定义一个保持矩阵中元素阶并包含码的更多信息的重量计数器。在我们给出 完全重量计数器的定义之前，先定义如下映射。 设# = ( a 。，p 舻，p i 产。) ，p = ( 墨，最，c ) 7 。 缈：鸠。( 尺) 专m 。l ( 尺【胡( x 5 ) ) p b ( a o + p i l z + + a ，j l x s - i 见o + 见l x + + 见，s l x 5 1 ) 了 此映射是一个尺模同构。它将使后面的引理和定理的证明中的计算容易一些。一 个多项式p ( x ) e x ( x 。) 的p 重量即为d e g ( p ( x ) ) + 1 。 设p ( x ) = p o + p i x + + 凤一l x 卜1 r x ( x 5 ) ，p ( x ) 的第，个系数定义为 q ( p ( x ) ) = p t ，0 z s l ， 设 p ( x ) = ( 只( x ) ，芝( x ) ，p a x ) ) 7 ，q ( x ) = ( q l ( x ) ，耍1 2 ( x ) ，受l ( x ) ) 7 厶。( r 【x 】( x 5 ) ) 其中 ( x ) = a o + 易l x + + 易，j l x 5 ， q j ( x ) = q ，o + 鼋f l x + + g f 。卜i x 。一， 则尸( x ) ，q ( x ) 的内积相应的变为： ( 尸( x ) ，q ( x ) = ：，c s 一，( 只( x ) q ( x ) ) 记元素a r 的h a r e m i n g 重量为w ( a ) ，若口= 0 ，则w ( a ) = 0 ，否则即有w ( a ) = 1 。 设p = ( 既) 黼，k ，= ( m o ，乃p 1 ，一，儿o ，见产1 ) ，其中1 f 刀，o 歹 c ，其中c 是复数 集。 设z 是g 的一个非平凡的特征。则： 6 e g z ( 6 ) = o 设r = 铴，a l ，一。) 是一个有限交换环。用丫l 表示和r 中元素1 相对应的特征。 设厄( 6 ) = t l ( 动) ，口，b r 。厄是r 的一个加群特征。 尸。j ，。c 丫。c c 尸c x ，q c x ，= l 兰i ：g 二；茎三二。 设厂：鸠。，( r 【乩( _ ) c 。) )c y 。，y l , s - l ，蚝0 ，- 此产i 】，z 定义如前，则 1 9 _ _ 一 c 厂( q ( x ) ) = p ( , ) c - c 夕( 尸( x ) ) ， 其中夕( 尸( x ) ) = q ( ，) 。 k ，( r 【，l ( ，) ) y ，( ( p ( x ) ，q ( x ) ) 厂( q ( x ) ) ， p ( x ) = ( 墨( x ) ，( x ) ) 丁， q ( x ) = ( q l ( x ) ，q ( x ) ) 7 。 设c 是鸠。，( 尺) 上的一个线性码，则有： 腓c 瑶吼0 ) 一趱一蛾) 璐h 高( 兀m 珈+ ( ，州) 均) ) m 脚i - i ；：。兀一。- i 坳1 - 叫y 肼妇) 以) 。 设c 是长为刀的一个乙一线性码， p ( x ) = p o + p a x + + 见一l 戈川 ， 口( x ) = q o + g l x + + q ，一l x ”一。贝0 有： 船妒- 硝州蟛叭) 2 而i ( 11 瑚n ( 1 + 3 乃) ) m 脚兀2 。( 吉费”( 舶) 。 3 2 四元素环上的重根循环码 2 0 世纪9 0 年代，人们发现一尺码等价于整数模4 剩余类环z 4 上的线性码， 此外人们发现，通过g r a y 映射，一些非常著名的非线性码如k e r d o c k 、 p r e p a r a t a 、g o e t h a l s 码可以看作是环乙上的线性码，而这一性质为研究线性 码及非线性码开辟了新的思路，使得环乙上码和一般整数环上码成为近十几年 来的研究热点，并逐渐推广到其他四元素环和一般的环上。环z 4 上奇长度的循 环码的结构在很多文章中都有讨论 4 - 7 j ，环z 4 上奇长度的循环码是环 z 4 x 】( 矿一1 ) 上的主理想，有唯一的生成元，它是x ”- 1 的一个因子。而环z 4 上 偶长度的循环码的结构较奇长度的复杂，这是因为当以为偶数时，x ”一1 在z 4 上 的分解不唯一。 3 2 1 环z 4 上