（应用数学专业论文）有限环上线性码及其自对偶码的研究.pdf

有限环上线性码及其自对偶码的研究 摘要 纠错码理论的理论基础是由数学为支撑。在实际应用中，它的发展则源于 现代通信电子计算机技术中差错控制的研究的需要。随着信息技术的发展，编 码理论得到迅速的发展。尤其是二十世纪九十年代，人们发现一些高效的二元 非线性码可以看作是z 。上线性码在g r a y 映射下的二元象，有限环上的编码理 论获得重要突破。自此，有限环上的编码理论成为研究的热点。 本文主要讨论线性纠错码，就编码理论研究的热点一一环上码做了一些工 作。 本文的组织结构如下： 第一章综述回顾编码理论研究的历史及概况，以及当前编码理论研究的 若干发展方向，并在最后陈述本文的工作。 第二章概述乙码的基本概念和环只+ 以上的线性码c 和其对偶码。最 后，介绍环尺上循环码与其剩余码及挠码的关系。 第三章研究环只+ 饵+ + 铭七只上的自对偶码。证明得到环r 。上自对偶 码存在的一个充分必要条件。然后定义f e + 幔+ + “最) 4 到( e + 幔) “的一个 映射，利用此映射研究自正交码的一些性质。最后，定义环r 上的g r a y 映射 ：r _ 砰“，证明当c 是r 。上的长度为n 的线性码，且k 3 时，似c ) 是自 正交的。 关键词：线性码；循环码；自对偶码；自正交码；生成矩阵 r e s e a r c ho nl i n e a rc o d e sa n ds e l f - d u a lc o d e so v e rf i n i t e r i n g s a b s t r a c t t h e o r e t i c sf o u n d a t i o no fc o d i n gt h e o r yi sb a s e do nm a t h e m a t i c s h o w e v e r ，t h i s t h e o r yi sa p p l i e di nm a n ys i t u a t i o n sw h i c hh a v e a sac o m m o nf e a t u r et h a t i n f o r m a t i o nc o m i n gf r o ms o m es o u r c ei st r a n s m i t t e do v e ran o i s yc o m m u n i c a t i o n c h a n n e lt oar e c e i v e w i t ht h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , c o d i n g t h e o r ym a k e sp r o g r e s sr a p i d l y i nt h e19 8 0 s ，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 se x p e r i e n c e dt r e m e n d o u sg r o w t hs i n c et h es i g n i f i c a n td i s c o v e r y t h a ts e v e r a lw e l l k n o w np r o m i n e n tf 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 e i d e n t i f i e da si m a g e so fl i n e a rc o d e so v e rz 4u n d e rt h eg r a ym a p s i n c et h e n ， c o d e so v e rf i n i t er i n g sh a v eb e e ng i v e nm o r ea t t e n t i o n i nm ep r e s e n tp a p e r ，a n t h o rs t u d y ss o m el i n e a re r r o r - c o r r e c t i n gc o d e s a u t h o r d os o m ew o r ka b o u tt h ek i n do fc o d e so v e rr i n g s t h eo r g a n i z a t i o no ft h ec o r r e s p o n d e n c ei sa sf o l l o w s ： c h a p t e r1i tp r o v i d e sa ni n t r o d u c t o r yc o u r s ei nc o d i n gt h e o r ya n dd e v e l o p m e n t h i s t o r y , a n ds o m ea s p e c t so fd e v e l o p m e n to fm o d e r nc o d i n gt h e o r yr e s e a r c h ，a n d s t a t e sr e s e a r c hc o n c l u s i o n so ft h i sp a p e ra tl a s t c h a p t e r2 i th a sa no v e r v i e wo ft h eb a s i cc o n c e p to fc o d e so v e rz 4 a n dt h e l i n e a rc o d ea n di t sd u a lc o d eo v e rt h er i n ge + 蜗f i n a l l y , w ei n t r o d u c tt h e r e l a t i o n s h i pb e t w e e nc y c l i cc o d et or e s i d u ec o d ea n d t o r s i o nc o d eo ft h ec o d eo v e r r i n g r c h a p t e r3w es t u d yt h es e l f - d u a lc o d eo v e rr i n ge + 矩e + + “。互f i r s to f a l l ， w eg e tan e c e s s a r ya n ds u f f i c i e n tc o n d i t i o no fs e l f - d u a lc o d e se x i s t e n c eo v e r r t h e ng i v e nt h ed e f t n i t i o no fam a p p i n gf r o m ( 最+ 优艺+ + t l 。e ) ”t o ( r 2 + “f 2 ) ”， w es t u d ys o m ep r o p e r t i e so fs e l f - o r t h o g o n a lc o d e sb yt h i sm a p p i n g f i n a l l y , g i v e n t h ed e f i n i t i o no ft h eg r a ym a p p i n g ：r j 巧，w ep r o v et h a tw h e nt h ec o d e ci st h el e n g t hno ft h el i n e a rc o d eo v e rr i n gr ，o i ss e l f - o r t h og o n a l k e yw o r d s ：l i n e a rc o d e ；c y c l i cc o d e ；s e l f - d u a lc o d e ；s e l f - o r t h o g o n a l c o d e ； g e n e r a t o rm a t r i c 独创性说明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金胆互些太堂 或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签字：汤签字日期：哆年争月厂夕日 学位论文版权使用授权书 本学位论文作者完全了解 金目巴王些太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金胆王些太堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：物氮妥 签字日期：拜年争月f p 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师洲易 签字日期：矿尹午月z 口日 由话7 哆，洲p 电话：矽7 pys f 致谢 我首先要感谢我的导师朱士信教授。在硕士阶段的三年时间里，朱老师严 谨的治学态度、深厚的学术水平、精湛的教学方式给我留下深刻的印象，并将 成为我在以后的工作上的榜样。朱老师不仅在学业上给我细心地指导，同时还 在思想和生活上给我无微不至的关怀，在此谨向朱老师表示诚挚的感谢和崇高 的敬意! 在学习期间，我还受到苏化明老师，刘丽老师等很多老师所给予的关 心、支持和帮助，我在此十分感谢与敬佩他们。 感谢我的家人三年来在物质以及精神上给我的支持，正是由于他们无私的 帮助和奉献，才使我在研究生阶段全身心的投入到学习之中，这为我完成学业 和论文奠定重要的基础，在此祝愿他们永远健康，永远快乐! 我还要感谢我的师兄妹和同学，他们给我的鼓励和帮助，我永远铭记在心! 最后，感谢合肥工业大学为我提供良好的学习环境和优越的学习条件，我对合 肥工业大学有深厚的感情，祝愿合肥工业大学发展的越来越好! 作者：汤道安 2 0 0 9 年3 月 第一章绪论 1 1 纠错编码理论 信息安全理论是研究信息在传输或存储过程中保证信息的可靠性、秘密性、 真实性等要求的一门学科。它以数学和计算机等学科为基础，现代密码学和纠+ 错码理论( 也即编码理论) 都是信息安全理论的基础。信息论的理论研究对于 科技及其应用都具有直接的和长远的影响。s h a n n o n 在1 9 4 8 年发表的论文a m a t h e m a t i c a lt h e o r yo fc o m m u n i c a t i o n ) ) 中首次提出著名的有扰信道编码定理。 继s h a n n o n 之后不久，1 9 5 0 年h a m m i n g 发表了他的论文e r r o rd e t e c t i n ga n d e r r o rc o r r e c t i n gc o d e s ，这两篇论文与g o l a y 的论文o nac l a s so fe r r o r c o r r e c t i n g b i n a r yg r o u pc o d e s ) ) 一起构成“代数编码理论”的基础。 编码理论是信息理论的一个专门分支，其理论基础由数学支撑，在实际应 用中，它的发展则源于现代通信技术与电子计算机技术中差错控制研究的需要。 因此，这一领域既是通信工作者也是数学工作者研究的热点。随着信息技术的 发展，编码理论得到了迅速的发展。现在我们利用计算机进行复杂运算时，不 再担心结果的可靠性，但是在计算机概念刚提出时，曾经有人提出如下反驳： 在计算机这样一个复杂系统中，外界噪声的干扰是不可避免的，只要噪声使得 计算机中任一部件发生一次错误，最后的运算结果都会变得面目全非，因此可 以断言利用计算机进行复杂运算是不可能的。这一困难后来是如何克服的呢? 编码在这过程中起了关键性的作用。什么是编码? 编码，更准确地说，信道编 码，指的是通过引入冗余信息，使得在一部分比特发生错误下，仍有可能按照 一定的规则纠正这些错误，以实现无失真地传送和处理信息。举一个最简单的 重复码为例，我们可以将信号0 编码为0 0 0 ，信号1 编码为1 1l ，这样如果最多只 有一个比特发生错误，譬如，0 0 0 变成了0 0 1 ，我们仍然可以按照少数服从多数 的原则，找出错误的比特就是第三个比特并纠正该错误。纠错编码理论是上世 纪四十年代末由s h a n n o n ，h a m m i n g ，g o l a y 等人创立【。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 n d i g i t a lc o d i n g ”中，提出了从充分利用检验元的观点来看，是最佳的纠正二元序 列中一位错和三位错的完备码( p e f e c tc o d e s ) ，开创了与应用相结合的编码理论 方法的研究，可以说，信息理论的发展和编码方法的成长始终是相互依赖、相 互促进的。h a m m i n g经说过：“从逻辑上来说，编码理论导致信息理论，信息 理论则为适当的信息编码提供所能达到的限度 。事实上，信息论的应用从底 层的通信到电子的损耗都涉及到编码理论，所以说“a l g e b r a i cc o d i n gt h e o r yi sa b r a n c ho fe n g i n e e r i n gw i t hr o o t si nm a t h e m a t i c sa n da p p l i c a t i o n st oc o m p u t e r s c i e n c e ”。 编码理论主要包括以下两个方面：以保证数字信息传输和处理的可靠性为 目的的差错控制编码( e r r o r c o n t r o lc o d i n g ) ，又称信道编码( c h a n n e lc o d i n g ) 以提 高数字信息传输、存储处理的有效性为宗旨的信源编码( s o u r c ec o d i n g ) 。差错 控制编码技术类别繁多、应用面广，通常所使用的编码理论中的“编码 指的 就是差错控制编码译码技术。每一个通信系统都依赖有效的编码技术，差错控 制编码技术也是伴随着数字通信业务的发展而发展起来的，因此在相当长的一 段时间内，编码的要求和编码译码器的结构特点，都体现了数字通信技术的特 征，这就是要求码率高、冗余度小，以便在串行信道中保证尽可能高的通过能 力，编码译码器的速度只要能跟上信号在串行信道上传送的节拍就可以。在这 种工程技术背景下，以有限域和代数为基础，以循环码为代表，以线性反馈移 位寄存器为主要编码译码器件的代数编码技术得到迅速发展并且日臻完善，其 中象b c h 码、r s 码以及h a m m i n g 码、g o l a y 码等都是应用广泛的代数码。从结构 上来看，差错控制编码一般可以划分为分组码( b l o c kc o d e s ) 和卷积码 ( c o n v o l u t i o nc o d e s ) 两大类。所谓分组码，是首先将来自信源的信号分成若干消 息组，每个消息组由k 位连续的信息符号组成，编码器接收一组消息并按一定 规则将之变换为一组较长的，z 位( n k ) 码字符号输出，这种结构不同于卷积码， 卷积码是利用编码器接收一个连续的信号流并在编码后相应地生成一个连续的 输出流。由于卷积码类在工程技术中的实用性，使得通信工程工作者们更倾向 于卷积码类的研究，近年来通信工程工作者们在t u r b o 码上的研究热潮反映了这 一特点。分组码则以其较完美的数学特点吸引了更多编码理论和理论数学研究 者。 1 2 纠错码的发展史 迄今，纠错码已有五十多年的历史，其发展过程大致分为以下几个阶段： 2 0 纪5 0 年代至6 0 年代初，主要研究各种有效的编码、译码方法，奠定了 线性分组码的理论基础，提出了著名的b c h 码，同时也给出纠错码的基本码限。 这是纠错码从无到有得到迅速发展的年代。 2 0 纪6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期。不仅 提出许多有效的编译码方法，而且注意到了纠错码的实用化问题，讨论了与实 用有关的各种问题，所有这些问题的研究为纠错码的实用打下坚实基础。在此 期间，代数方法特别是以有限域理论为基础的线性分组码理论已趋成熟。 2 0 纪7 0 年代至8 0 年代初，这是纠错码发展史中具有极其重要意义的时期。 在理论上以g o p p a 为首的一批学者，构造了一类g o p p a 码，其中一类子码能达 到s h a n n o n 在信道编码定理中所提出的s h a n n o n 码所能达到的性能，这在纠错 码历史上具有划时代意义。在这期间大规模集合电路和微机的迅速发展，为纠 错码的实用打下坚实的物质基础，因而与实用相关的各种技术及有关问题得到 2 极大关注，并在实用中取得巨大的成功。 自2 0 纪8 0 年代初至今，g o p p a 等从几何观点讨论分析码，利用代数曲线 构造一类代数几何码，在这些码中，某些码的性能达到s h a n n o n 码所能达到的 性能。由于代数几何码是一类范围非常广的码，在理论上已证明它具有优越性 能，因而受到编码理论研究者，尤其是代数几何学家的重视，使代数几何码的 研究得到迅速发展，取得许多成果。7 自上世纪7 0 年代末以来，纠错码技术已开 始渗透到很多领域。利用纠错码中的许多编码、译码原理和方法，与通信系统 中其它有关技术相结合，得到一些令人惊喜的结果。如：纠错码与调制技术相 结合所产生的t c m 技术，已作为国际通信中标准技术而推广使用；纠错码与密 码结合，可以构造出一类既能加密签名，又具有纠错功能的密码系统；纠错码 与信源编码相结合的结果，使得通信系统更为有效与可靠。不仅如此，纠错码 中的许多译码思想和方法，与神经元网络中的能量函数有密切关系，可以用来 解决神经元网络中的一些问题。因此，可以预料，随着科学的进步和实际需要， 纠错码理论必将进一步发展，它的应用范围必将进一步扩大。 1 3 目前研究的现状 近二十年来，数学和计算机科学中的一些强有力工具和最新研究成果被用 到编码理论中，不仅促进编码理论的迅速发展，也刺激数学和计算机科学中的 一些分支的发展。以下几个方面是编码理论在近几年来比较活跃的研究方向： ( 1 ) 环上码。1 9 9 4 年，a h a m m o n s 等人通过适当的定义发现几种著名的 非线性码可表示为z 4 多项式环中理想，其实质是z 4 环上的线性码。从而使得环 上的线性码的研究成为近二十年来编码界的热点之一。目前，环上码的研究主 要集中在对环上码的参数估计、设计环上码、环上循环码的分析、用环上码构 造c d m a 序列、环上码的译码等。 ( 2 ) 代数几何码是上个世纪八十年代由苏联数学家发现。这一发现使数学 中最抽象的分支之一的代数几何，通过编码理论被天才的应用到通信工程中去。 由于代数几何码的卓越纠错和检错性能，持续三十多年的研究之后，代数几何 码仍然是信息论的一个热点。代数几何码的研究主要集中于渐进问题、码的构 造、译码、最小重量、重量分布等问题上。 ( 3 ) 时空码( s p a c e t i m ec o d e ) 是美国学者t a r o k h 和c a l d e r b a n k 等人近几 年发现的一种码，它用在多通道、多天线、无线电通信一例如手机通信中， 可以极大地改善这些通道的性能。 ( 4 ) 量子纠错码和量子密码是量子信息论的两个基本方面，它们都基于量 子计算和量子算法。研究量子计算和量子算法是当今信息科学中的最前沿方向 之一。 3 1 4 本文的主要内容 目前就信息科学中纠错码研究的几个发展方向来说，数学工作者关注更多 的是代数几何码与环上码的理论研究。因此，很多从事这方面研究的学者把兴 趣转移到有限环上的编码理论的研究。 本文作者在纠错编码理论里主要对环上的码的性质做了部分研究，主要研 究有限环上线性码及其自对偶码，具体内容如下： 1 研究了环只+ 饵+ + 掰露只上的自对偶码的存在的条件，给出k 为奇数 时，此环上的自对偶码是一定存在的；k 为偶数时，给出此环上自对偶码的存 在的充要条件。 2 把环只+ 以上循环码的剩余码和挠码的概念推广到环 只+ u f 2 + + u k f 2 上，定义环只+ u f 2 + 十u 七f 2 上的生成矩阵和高阶挠码的概 念，证明环r 。上的自对偶码的型的一些性质。 3 构造尺h 到( e + 峨1 “的新映射，证明当c 是r 。上长为n 的自正交码时， 矽( c ) 仍然是最+ 幔上长为珂的自正交码，并且进一步证明得到( c ) 是五+ 蜗上 长为n 的自对偶码的充分必要条件。 4 定义环e + 以+ + 甜七只上的g r a y 映射，证明当c 是 e + u g + + “七只上的长度为以的线性码，且k 3 时，似c ) 是自正交的。 以上这些内容的研究，对进一步丰富纠错码在有限环上的理论及构造一些 性能好的码有一定的指导和实际意义，特别是对研究有限环上的对偶码的性质 方面有重要的指导意义。 4 第二章有限环上线性码的结构 从1 9 4 8 年s h a n n o n e l 】开创纠错码理论以后，人们利用有限域理论作为工具， 建立起系统的有限域上的纠错码理论，这些理论在文献p l l 】中有全面的研究。 近年来，编码理论中的一个突破性的进展是h a m m o n s 等人在文献【1 5 1 中证明出 一些高效的二元非线性码，如p r e p a r a t a 码、k e r d o e k 码等可视为环z 4 上循环码 在g r a y 映射下的像，而且他们还解决了在编码理论中一个古老而公开的问题， 即证明了非线性二元p r e p a r a t a 码和k e r d o c k 码满足m a c w i l l i a m s 恒等式。文献 【1 4 j 一q u a t e r n a r yc o d e s 的出版标志着环乙上的纠错码理论已有基本框架， 随后，环乙上的纠错码理论进入全面发展时期。b o n n e c a z e 在文献【1 6 引入一种 介于乙于e 之间的四元环r = 只+ “只= 只【“】 ，讨论了环尺的结构和性 质，将有限环上的编码理论的研究引入一个全新的研究方向。 2 1 z 4 码 在本节中，我们介绍一些关于z 4 码的基本知识。 令z 4 是整数环模4 的剩余类环，n 是一个正整数，鬈是由z 4 上的n 维向量 所组成的集合，即 公= ( 五，x 2 ，吒) l 薯z 4 ，江1 ，2 ，刀 所有分量为o 的，z 维向量以及所有分量为1 的n 维向量分别记为o 栉和l 疗。我们用 哆表示z ? 中第i 个分量为1 而其余分量均为o 的向量。掣中任一非空子集c 称 为四元码，或称为z 4 码，其中n 称为码的长度。z ：中的刀维向量称为字，四元 码c 中的n 维向量称为码元。召中任一子群称为四元线性码，或简称为z 4 线 性码。 对于任意的x = ( 五，x 2 ，矗) ，y = ( y i ，y 2 ，以) 公，定义 x 。y = 五y l + + y 。， 称为j c 和y 的内积。若x y = 0 ，则称x 与y 是正交的。 令c 是任意一个长度为n 的四元线性码，定义 c 上= 缸蜀n 弦y = o ，v y c ) 易证c 上也是一个四元线性码，称为c 的对偶码。 设g 和e 是两个长度为n 的四元线性码，如果通过分量的置换，若必要的 话，再改变某些分量的正负号，可以由c 1 得到c ，我们就称这两个码是等价的。 如果仅仅通过分量的置换就可以把一个码变成另一个码，这两个码就称为是置 换等价的。 易证任意一个码都与以下面形式的矩阵为生成矩阵的码c 置换等价， g = f 气 么 曰1 ( 2 1 ) i o 2 k 2 c j 其中a 和c 是z 2 上的矩阵，b 是z 4 上的矩阵。这样一个码显然是一个类型为 4 南2 如的交换群，包含2 2 毛+ 如个码元。我们称c 的类型为4 k , 2 k 2 。 若码c 以矩阵( 2 1 ) 为生成矩阵，则对偶码c 上的生成矩阵为 一，羞厶州 2 ) 且码c 上的类型为4 n _ 岛一乞2 乞。 z 4口p ) ， 0ooo 1101 2011 31lo 很自然地，我们可以把这三个映射扩张为由z ：到露的映射。我们通常通过 g r a y 映射矽把四元码与二元码联系起来，其中矽的定义为： 矽( c ) = ( f l ( c ) ，y ( c ) ) ，c 露 对于一个四元码c ，当我们谈到它的二元像时，通常指的是它在g r a y 映射 下的像c = 矽( c ) 。我们用大写的书写体字母表示四元码，而用相应的大写拉丁 字母表示其二元像。 g r a y 映射的最重要的性质在于它是一个保距映射 定理2 1 1 矽是一个保重量的映射，由( 刃，l e e 重量) 到 ( 爱疗，h a m m i n g 重量) 即： 毗( x ) = w ( 矽( x ) ) ，v x 召 并且，矽是一个保距离映射，由( 召，l e e 重量) 到( 乏一，h a m m i n g 重量) ，即 吒( x ，y ) = 九( 矽( x ) ，矽( y ) ) ，v x ，y 鬈 证明：见 1 4 定理3 1 。 通常情况下，c = 矽( c ) 并不一定是线性的，故未必有对偶码。我们定义它 的z 4 对偶码为c i = 矽( c 上) ，注意c ，未必是c 的对偶码。尽管如此，由下面这 个命题，我们知道，码c 和码c 的h a m m i n g 重量计数多项式满足 m a c w i l l i a m s 恒等式。 定理2 1 2 令c 与c 上是对偶码，且c = 矽( c ) ，c = 矽( c 上) 分别是它 们的- - y n 像，则c 上与c 的重量计数多项式w c ( x ，y ) 与w c ( x ，y ) 满足 讹c 耽l l i a m s 恒等式 1 w c 。( x ，】r ) = 南( x + y ，x y ) i 乙i 证明：见 1 4 定理3 7 。 一般地，除了码c 的二元像c = 矽( c ) 以外，还有两个码c ( n ，c ( 2 与c 相关 6 联，它们分别定义为： c 1 = a ( c ) ：c c ， c 2 = ( c ) ：c c ，a ( c ) = 0 ) 。 若c 具有生成矩阵( 2 1 ) ，则c 1 是一个【儿，毛】码，其生成矩阵为 ( 4 口( b ) ) 而c 2 是- - h 孢，矗 若c 是自正交 则c ( 2 ) = c ( 1 ) 上。 + 红】码，其生成矩阵为 一气a 口 的，则c ( 1 ) 是双偶的且c ( 1 c ( 2 ) c ( 1 ) 上。若c 是自对偶的， 双偶是指码c 的汉明重量是4 的倍数。 定理2 1 3 给定两个分别长为n 的二元线性码c 和c ”且c c ”，有z 4 上的线性码c 使得c ( 1 ) = c ，c ( 2 ) = c ”。若c 是双偶的且c ”互c “，则c 是自 正交的。更进一步，若c ”= c “，则c 是自对偶的。 证明：见【1 4 】性质3 1 9 。 z 4 上的任意码c 的生成矩阵( 2 1 ) 可以记为如下的另一种等价形式： f x k + 2 e 1 ( 2 3 ) lo2 k2 z 其中x ，x ，k ，z 是二元矩阵。则c 是型为4 1 , 2 h 的初等可换群，包含2 2 南+ 如个字。 定理2 1 4 具有( 2 3 ) 式的生成矩阵的z 4 上的码c 是对偶的当且仅当 c ( 1 是双偶的，c ( 2 ) = c ( n 上。 证明：见 3 9 中的证明。 以下我们介绍四元循环码的概念 定义2 1 5一个四元线性码c 称为四元循环码，如果c 满足： v ( c o ，c i ，c n 一1 ) cj ( 巳- 1 ，c b ，c 1 ，c n 一2 ) c 有时，我们也把四元循环码称为z 4 循环码。同二元的情形一样，为了研究 循环码，我们把i 维向量( ，a l 一，口一一1 ) z ：表示成剩余类环z 4 x 】o 一一1 ) 中 以多项式+ q x + + a n l x 肛1 公为代表元的剩余类，则我们有双射 z ? z 4 x 】( x 万一1 ) ( a 0 口l ，a n 1 ) 一a o + 以l x + + a n _ i x 扣1 + ( x 一一1 ) 其中( 矿一1 ) 是z 4 x 】中由多项式x 一1 生成的主理想。为简单计，我们把剩余 类a o + q z + + a n 一1 x 卜1 + ( r 一1 ) 记作多项式a o + 口l x + + a n l x 卜1 。我们把一 个长度为n 的四元码c 在上述双射下的像仍记为c 。显然有 c b + c l x + + 巳一l x 九- 1 c = 今x ( c o + c l x + + c n - 1 x 万1 ) c 7 因此，c 是z 4 循环码当且仅当是c 是剩余类环z 4 z 】( ，一1 ) 的一个理想。此外 我们知道z 4 【x ( - 1 ) 是- - 个主理想环，即：对于任意的z 4 循环码c ，存在多 项式a ( x ) z 4 【x ( x 一1 ) 满足c = ( 口( x ) ) 。 令z 4 x 是z 4 上的以z 为变量的多项式环，定义如下环同态： 优：z 4 寸z 2 o ，2ho 1 ，3h l 为简单计，我们把这个映射仍然记为“一”。即0 = 2 = 0 ，l = 3 = l 。映射 “一 ：z j z 2 可以自然的扩展为如下的，从z 4 x 到z 2 x 】的映射： z 4 x 一z 2 x a o + a l x4 - + 口n x n 卜专a o4 - a l x + + 口n x ” 显然此扩张映射是从z 4 【x 】到z 2 【x 的环同态。此扩张的环同态也用“一” 表示，厂 ) z 4 叫在此映射“一下的像，表示为厂( x ) 。对于任意厂 ) z “x 】， 我们定义 ( 厂( x ) ) = z 4 x ( x ) = g ( x ) 厂( x ) i g ( x ) z 4 x 】) 定义2 1 6z 2 i x 】中的一个首项系数为1 的多项式( x ) 称为基本不可约多 项式( 或基本本原多项式) ，如果( x ) 在z 2 x 】中是不可约的( 或本原的) 。 定义2 1 7 令彳( x ) ，六( x ) 是z “石 中的多项式，它们称为互素的。如果 存在a ，五z 4 x 】满足 a 石( x ) + 如五( x ) = 1 或等价地， z 4 x 】石( x ) + z j x 】厶( x ) = z 4 x 】 定理2 1 8 令a ( x ) 和五( x ) 是z 4 i x 】中的多项式，a ( x ) 和五( x ) 分别表示 在“一 映射下的z 2 x 】中的像，则z ( x ) 与五( x ) 在z 4 i x 】中是互素的当且仅当 a ( x ) 与五( x ) 在z 2 i x 中是互素的。 证明：见 1 4 引理5 1 。 定理2 1 9 ( 亨泽尔引理) 令z ) ，五 ) 是z 4 i x 中的多项式，f ( x ) 是 z 4 i x 中的首一多项式，假设f ( x ) = 彳( x ) a ( x ) ，其中石( x ) 和五( x ) 是 z 2 i x 中的互素的多项式，则存在首一的多项式自( x ) ，9 2 ( x ) z 4 x 】有如下性 质： ( 1 ) 厂( x ) = g l ( x ) 9 2 ( x ) ， ( 2 ) g 。 ) = a ( x ) ，g ：( x ) = a ( x ) ( 3 ) d e g g l ) = d e g f ( x ) ，d e 9 9 2 ( x ) = d e g 以( x ) ( 4 ) g l ( x ) 和( x ) 在z 4 i x 中是互素的。 证明：见 1 4 引理5 2 。 通过数学归纳法可以证明得到如下更一般的亨泽尔引理： 定理2 1 1 0 令厂( 石) 是z 4 z 】中的首一多项式，假设 厂( x ) = a ( x ) 五( x ) ，( x ) ， 其中石( x ) ，五( x ) ，z ( x ) 是z 2 i x 】中的两两互素的多项式。则存在z 4 k 中的首多项式g l ( 工) ，9 2 ( x ) ，g ，( x ) 具有以下性质： ( 1 ) f ( x ) = g l ( 石) 9 2 ( x ) 毋( x ) ， ( 2 ) g f ( x ) = a ( x ) ， f = l ，2 ， ( 3 ) d e g g i ( x ) = d e g f ( x ) ， f _ 1 ，2 ， ( 4 ) g l ( x ) ，9 2 ( x ) ，g ，( x ) 在z 4 【x 】中两两互素。 2 2 环e + 幔上的线性码及其对偶码的生成矩阵 令环尺= 最+ 幔= 0 ，1 ，“，云= l + “) 。其中元素的运算法则如下 木 o1万u + 0 1 万u o0ooo0o1订” 101万“ 1 10材万 一 0万 1 “虿 万“01 u 0 “”0球u万lo 这个环可以看作域e 上维数是2 的向量空间，而且 o ，1 ， 0 ， ， o ，订 形成 环r 的三个子空间，而且子空间 o ，1 ( = 只) 是尺的一个子环。环犬同构于商环 z x ( 2 ，( x + 1 ) 2 ) ，环r 有一个极大理想 o ，u ) ，因此r 是局部环。环尺的特征 是2 。环r 上的线性码c 是指尺一模r 4 的一加法子模。对r ”中任意的 x = ( 五，屯，x n ) ，y = ( y l ，y 2 ，y 。) ，定义x 与y 的内积为x y = x a y l + - i - 吒y 。， 若x y = 0 ，则称x 与】厂正交。设c 是环r 上长为n 的线性码，令 c 上： x r n l x y ：o ，对v y c 1 ，则容易证明c 上也是环尺上长为n 的线性码，称 、i ， 为线性码c 的对偶码。若环r 上线性码c 满足c c 上，则称c 为环尺上的自正 交码。若环尺上线性码与其对偶码相等，即c = c 上，则称c 为环r 上的自对偶 码。任意x = ( x a ，恐，矗) 的l e e 重量屹定义为n 1 ( x ) + 2 n 2 ( x ) ，其中n 1 ( x ) 表示 x 中符号u 的个数，n ，( x ) 表示x 中1 或者u 的个数。 设q ，c 2 均是环r 上长为n 的线性码，若c l 通过坐标置换，必要时将码元1 与1 + 甜互换，能得到码q ，则称c l 和巴为环尺上等价的线性码。类似于文献1 3 1 中的讨论，可以证明： 命题2 2 1 【3 7 1r 上任意一非零的线性码c 都等价于一个由 g = ( 0 最u b c 、i ) 4 ， (畋 所生成的线性码，其中a ，b 均为环r 上的矩阵，b 为域e 上的矩阵。此时也称 9 码c 的生成矩阵为( 2 4 ) 式，因此码c 中共包含4 k , 2 屹个码字。 命题2 2 2 【3 7 】若c 为命题2 2 1 所设的r 上任一非零的线性码，则其对偶 码c 上的生成矩阵为 日：p + 芬c 厶七如1 ， ( 2 5 ) l u a l 纠如o 且码c 上中共包含4 舻向一屹2 屹个码字。 证明：设c l 为r 上的由( 2 5 ) 式所生成的线性码，则显然有c 1 c 上， v c = ( c 1 ，乞，q ) c 上，将( 2 5 ) 式中的前n 一向一心行的一个适当线性组合 加到c 上，则可得到c 上上的一个码字c 。= ( c 1 ，c 岛，c 岛+ l ，吒+ 如，o ，0 ) ，且又 因c 。与( 2 4 ) 式中后哎行正交，故气+ l ，气+ 七2 只能取o 或u ，将( 2 5 ) 式中 后也行的一个线性组合加到c 。上，则可得c 上中的码字c “= ( c l ，气，0 ，o ) ， 因c 与( 2 4 ) 式中前白行正交，故c l = = 气= 0 ，因此c c l ，即c 上q ， 综上即有c 上= q 。 由命题2 2 1 和命题2 2 2 ，我们即可得到： 推论2 2 3 3 7 1 任意长度为n 的尺上的自对偶码恰好包含2 ”个码字。 2 3 环只+ 以上线性码及其对偶码的g r a y 像 对于环r 上任一元素旯，均可表示为力= r ( 允) + 叫( 名) ， 其中 r ( 咒) ，g ( 兄) e ，则可定义从r 到巧的g r a y 映射：( 旯) = ( g ( 旯) ，g ( 旯) + ，( 旯) ) ，若 令s ( 旯) = g ( 兄) + ，( 旯) ，则有：西( 旯) = ( g ( 旯) ，s ( 允) ) 。可自然延伸至尺疗上向量x 及r 上的矩阵m 上的g r a y 映射，即 ( 1 ) 若设x = ( 五，x n ) r ，其中誓= i + u q i ，f = 1 ，2 ，聆。定义 r ( x ) = ( 巧，吃，) ，g ( x ) = ( g 。，9 2 ，g 刀) ，贝0 有 ( x ) = ( g ( 曲，g ( 曲+ ，( 曲) 。 ( 2 ) 若设r 上的矩阵m = ( ) 所。一，其中a 盯= + u q 驴，定义r ( m ) = ( 吩) ， g ( m ) = ( q f ，) ，则有r 上的矩阵m 的g r a y 映射： ( m ) = ( g ( m ) ，g ( m ) + “m ) ) 若设s ( m ) = 丸m ) + g ( m ) ，则( m ) = ( g ( m ) ，s ( m ) ) 。 引理2 3 1( 1 ) 帆，少r ，则有( x + y ) = 西( x ) + 西( y ) ( 2 ) v x ，y r 竹，则有( x + y ) = ( x ) + ( 】厂) 证明：( 1 ) 记x = r ( x ) + u q ( x ) ，少= r ( y ) + “g ( 少) ，则有 ( x + 少) = r ( 工) + 厂( 少) + “( g ( x ) + g ( 少) ) ) = ( g ( x ) + g ( 少) ，g ( x ) + g ( 少) + ，( x ) + ，( 少) ) = ( x ) + ( 夕) ( 2 ) 是( 1 ) 的自然延伸。 证毕。 引理2 3 2 【1 6 1若c 是尺上的线性码，则( c ) 为域只上的线性码。c 的 1 0 l e e 重量等于( c ) 的h a m m i n g 重量。 定理2 3 3若c 是尺上长为n 的线性码，其生成矩阵如( 2 4 ) 所示，则 ( c ) 的生成矩阵为 f 气a 厂( 曰) 气a r ( b 1 0 k c0 l k 2 c l0 0 q ( j b ) 乇a s ( b ( 2 6 ) 即西( c ) 为域f 2 上的 2 n ，2 k l + 也】线性码。 证明：由命题2 3 2 知，( c ) 为域e 上长为2 n 的线性码，而( c ) 是r r 毫 三 三 1 吨 以 妇i i ( 1 + 甜) 气( 1 + u ) a ( 1 + “) bl l o 吨“c j 行向量的二元象所生成，因此a ，c 均是域f 2 上矩阵，b 为r 上的矩阵，故有 ( 气 a b ) = ( g ( 气 a j b ) s ( i 电 a b ) ) = ( o 0 g ( b ) 乇 as ( 刀) ) ( 咄u au b ) = ( g u au b ) s ( u u a 诏) ) = 皈ar ( b ) a ，- ( 曰) ) 币( ( 1 + “) l( 1 + u ) a ( 1 + “) b ) = ( g ( ( 1 + 甜) 厶 ( 1 + “) 么 ( 1 + “) 曰) j ( ( 1 + 甜) 气 ( 1 + “) 么( 1 + “) b ) ) = ( l as ) 00 g ( b ) ) 巾( o 吆u c ) = ( g ( o 咄u c ) s ( o 畋u c ) ) = ( 0 乇 c 0 气c ) 因s ( 曰) = ，( 曰) + g ( b ) ，故 ( aj ) 00 g ( b ) ) = ( o 0 g ( b ) a s ( 曰) ) + ( ar ( b ) 气 a ，( 刀) ) 是线性无关的，故( 2 6 ) 式是( c ) 的生成矩阵。 定理2 3 4设c 为r 上长为n 的线性码，c 上为其对偶码，则( c ) 与 ( c 上) 也为域f 2 上的对偶码。 证明：由引理( 2 3 2 ) 知( c ) 与m ( c