（应用数学专业论文）有限环上循环码的中国积和线性码的mac+williams恒等式的研究.pdf

有限环上循环码的中国积和线性码的 m a c w i l l i a m s 恒等式的研究 摘要 二十世纪九十年代，人们发现了有限域上许多非线性码( 如k e r d o c k 码、 p r e p a r a t a 码、g o e t h a l 码) 可以利用有限环上线性码经过g r a y 变换得到，于 是有限环上的编码理论成为人们研究热点。本文主要研究了有限环乙 ( k = ( 兀乞。只) “，码长n 不能被只整除) 上中国积循环码；还研究了g a l o i s 上线 性码关于李重量和欧几里德重量的m a c w i l l i a m s 恒等式；并且研究了环z ：( p 是素数) 上线性码关于任一分划的m a c w i l l i a m s 恒等式和支重量。具体内容如 下： ( 1 ) 描述了中国剩余定理，定义了环乙( k = ( 兀j 1 1 只) _ ，码长 不能被b 整除) 上中国积循环码，给出了中国积循环自对偶码存在的充要条件并且进一步给出 中国积循环码的最小上界和最小生成子。 ( 2 ) 定义了z 。( 七2 ) 环上李重量和欧几里德重量的m p l y 重量计数器， 给出了乙环上一类新型的李重量和欧几里德重量的m a c w i l l i a m s 恒等式。视环 础( p 。，m ) 为z 一上秩为m 的自由模，考虑生成矩阵在z 。上的环锹( 矿，m ) 上线性 码， 环g r ( p 。，聊) 上线性码的李重量和欧几里德重量计数器和环z ，上线性码的 李重量和欧几里德重量的m p r y 重量计数器关系，得到了环g r ( p 8 ，m ) 上李重量 和欧几里德重量的m a c w i l l i a m s 恒等式。 ( 3 ) 定义了z 4 上长度为n 的线性码的广义l e e 重量计数器，给出了乙上长 度为n 的线性码的广义l e e 重量的m a c w i l l i a m s 恒等式。定义了乙环上长度为刀 的线性码的广义l e e 重量计数器的等价形式，相应地得到了乙环长度为船的线 性码的等价形式的广义l e e 重量的m a c w i l l i a m s 恒等式。 ( 4 ) 研究了z ：( p 是素数) 上关于任一分划的m a c w i l l i a m s 恒等式，当i u l = f ， 视c ，为码c 的限制码时，给出了c ，和码c 的重量分布之间的联系；当视c u 为 码c 的子码时，给出了型为( p 2 ) 的z ：线性码关于任一分划的m a c w i l l i a m s 恒等 ， 式。 ( 5 ) 研究了z ，( p 是素数) 上线性码的支重量及其广义p l o t k i n 界，给出了 p 环z ，上线性码的广义齐次重量的p l o t k i n 界。 关键词：循环码；中国剩余定理；g a l o i s 环； m a c w i l l i a m s 恒等式； m - p l y 重量计数器； 李重量计数器；欧几里德重量计数器；支 重量：齐次重量；广义p l o t k i n 界 r e s e a r c ho nt h ec h i n e s ep r o d u c to fc y c l i cc o d e sa n dt h e m a c w i l l i a m si d e n t i t i e sf o rl i n e a rc o d e so v e rf i n i t er i n g s a b s t r a c t a g r e a td e a lo fa t t e n t i o nh a sb e e np a i dt oc o d e so v e rf i n i t er i n g sf r o mt h e 19 9 0 s ，b e c a u s es c h o l a r sh a v ef o u n dt h a tc e r t a i nn o n l i n e a rc o d e s ( s u c ha sk e r d o c k c o d e s ，p r e p a r a t ac o d e s ，g o e t h a lc o d e s ) o v e rf i n i t ef i e l d sc a nb ec o n s t r u c t e df r o m l i n e a rc o d e so v e rf i n i t er i n g sv i ag r a ym a p s s i n c et h e n ，s t u d y i n gc o d i n gt h e o r y o v e rf i n i t er i n g si sah o tt o p i c i nt h i sp a p e r ，w es t u d yt h ec h i n e s ep r o d u c to fc y c l i c p r i m e ) t h ed e t a i l sa r eg i v e na sf o l l o w s ： 1 w ed e s c r i b et h ec h i n e s er e m a i n d e rt h e o r e mf o rs t u d y i n gc y c l i ca n dd u a l c y c l i cc o d e so v e rz k ，( k = ( 兀p f ) ”，w i t ht h ec o n d i t i o nt h a tt h ec o d el e n g t h n c a n i = l n o tb ed i v i d e db yp ，) an e c e s s a r ya n ds u f f c i e n tc o n d i t i o no ft h ee x i s t e n c eo f n o n t r i v i a ls e l f - d u a lc y c l i cc o d e si sg i v e n t h eu p p e rb o u n do fm i n i m u md i s t a n c eo f c y c l i cc o d e si sa l s oo b t a i n e d f u r t h e r m o r e ，w ed e t e r m i n et h em i n i m u mg e n e r a t o r s o f s u c hc y c l i cc o d e s 2 t h e m p y l e ea n de u c l i d e a nw e i g h te n u m e r a t o r so fl i n e a rc o d e so v e r 乙 a r ed e f n e d a n dt h e nw eo b t a i nan e wk i n do fm a c w i l l i a m si d e n t i t i e sf o rt h el e e a n de u c l i d e a nw e i g h t so f s u c hc o d e s f u r t h e r m o r e ，w e r e g a r d g a l o i sr i n g 锹( p 8 ，聊) a saf r e ez m o d u l eo fr a n km ，t h e nw ed i s c u s st h er e l a t i o n s h i p s b e t w e e nt h el e ea n de u c l i d e a nw e i g h te n u m e r a t o r so fl i n e a rc o d e so v e r 础( p 8 ，m ) ， w h i c hh a v e g e n e r a t o rm a t r i c e s o v e r z ，a n d t h e m p l y l e ea n de u c l i d e a n w e i g h te n u m e r a t o r so fl i n e a rc o d e so v e rz ，a tl a s t ，w eg e tt h el e ea n de u c l i d e a n w e i g h t sm a c w i l l i a m si d e n t i t i e so fl i n e a rc o d e so v e rg r ( p 。，聊) 3 t h eg e n e r a l i z e dl e ew e i g h te n u m e r a t o r sf o rl i n e a rc o d e so fl e n g t h 以o v e r 乙a r ed e f i n e d i ti sg i v e nt h a tt h eg e n e r a l i z e dl e ew e i g h tm a c w i l l i a m si d e n t i t i e s f o rl i n e a rc o d e so fl e n g t hno v e r 乙t h ee q u i v a l e n tf o r mo fg e n e r a l i z e dl e e w e i g h te n u m e r a t o r sf o r l i n e a rc o d e so f l e n g t h 押o v e r z 4 a r ed e f i n e d c o r r e s p o n d i n 9 1 y ，t h ee q u i v a l e n tf o r mo fg e n e r a l i z e dl e ew e i g h tm a c w i l l i a m s i d e n t i t i e sf o rl i n e a rc o d e so fl e n g t hno v e r z 4 a r eo b t a i n e d 4 w h e nw ei n t e r p r e tc r a sr e s t r i c t i o nc o d e so fc ，w eg i v e a ne q u a t i o n w h i c hc o n n e c t st h ew e i g h td i s t r i b u t i o no fac o d ew i t ht h o s eo fi t sr e s t r i c t i o n st o s e t so fag i v e ns i z e ；w h e nw ei n t e r p r e tc “a ss u b c o d e s o fc ，w eg e tas e to f m a c w i l l i a m si d e n t i t i e sb e t w e e na n yp a r t i t i o no ft h ec o o r d i n a t es e to fa z 。2 。l i n e a r e n s a n u d p= 辫 d n r 胛 砌g 附 h e h (呼k 骼 豇 r 犯m 北 衙 d s 、盯 甜 8 ；j 芎 陈m 北 咖由“ 州 诎咖如 h s e 瞳 t n 山 t i 、 0 =m 罴蛳 毗 m m 一 1 l r v t 1 l 硫 吾w m 踮n 蒜器 ，r、，l h 此m “ y b 踟 m 一 ， t 爿0 m s 垤m羔蕊 = e ， 旧眠= 办蚕m 瞅蚵以沁 叭 d b 幽裟 “ m w w c o d ew i t ht y p e ( p 2 ) 七a n dt h a to fi t sd u a la r ee s t a b l i s h e d 5 w ea l s os t u d ys u p p o r tw e i g h ta n dt h eg e n e r a l i z e dp l o t k i nb o u n do fl i n e a r c o d e so v e r 乙2 ，a n dg i v et h eg e n e r a l i z e dp l o t k i nb o u n df o n o m 。g e n o u sw e l g h o f l i n e a rc o d e so v e rz p k e yw o r d s ：c y c l i cc o d e s ；t h ec h i n e s er e m a i n d e rt h e o r e m ； g a l o i sr i n g s ； m a c w i l l i a m si d e n t i t i e s ；m p 陟w e i g h te n u m e r a t o r ；l e e w e i g h te n u m e r a t o r ； e u c l i d e a nw e i g h te n u m e r a t o r ； s u p p o r t w e i g h t ；h o m o g e n o u sw e i g h t ； g e n e r a l i z e dp l o t k i nb o u n d 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金目曼王些盔堂 或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签字旌批签字日期炒产够月日 学位论文版权使用授权书 本学位论文作者完全了解 金目垦兰些太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金目曼王些态堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 黧嚣菇签字日期：力砷年够月 学位论文作者毕业后去向： 似俐多 签字日期：年月日 电话：。哆口砂p 邮编： 致谢 三年紧张而又忙碌的硕士生活即将结束了，值此论文完成之际，首先感谢 我的导师朱士信教授。是朱老师把我领进了代数编码这个极具挑战性的研究领 域，使我对它产生了浓厚的兴趣。朱老师严谨的治学作风、勤奋认真地科研态 度、一丝不苟的工作作风都深深地感染了我，并将使我终生受益。另外，朱老 师在生活方面也给了我许多帮助和照顾，使我能够顺利完成学业，在此谨向朱 老师表示诚挚的感谢和崇高的敬意! 感谢我的家人，特别是父母三年来在物质以及精神上给我的支持，这为我 完成学业和论文奠定了重要的基础，在此祝愿他们永远健康，幸福! 还要感谢刘丽老师和师兄开晓山。他们给了我许多帮助，关心和支持。也感谢 我的其他师兄妹和同学，他们给我的鼓励和帮助，我都将永远铭记在心! 感谢 学校为我提供了良好的学习环境和优越的学习条件，使我能够静心，愉快地学 习! 最后，感谢审阅硕士论文和出席硕士论文答辩会的各位专家学者。敬请各位 专家学者和同行批评指正! 作者：唐永生 2 0 0 9 年4 月 第一章绪论 1 1 纠错码理论及其发展史 在日常实践中，电话和广播传送的是声音，电视和无线电传真传送的是文 字和图像，而电报传送的则是数字信息。将信息源的信息转化成数字信息传送 给收信者就叫数字通信。数字信息在传送过程中可能受到干扰( 如对于无线电 信号来说，自然界存在的电磁源以及其他无线电系统发射的信号等等) ，这样接 收到的数字信息可能就不是原来信息源发送的数字信息。为了使信息源发送的 数字信息能正确地传送到收信者，可以采取种种技术上的措施。更好的办法则 是在采用种种技术上的措施的同时，再采用抗干扰编码的办法。这就是说，在 数字信息传送之前先进行一次抗干扰编码，然后再发送抗干扰编码后的数字信 息。抗干扰编码有检错编码和纠错编码。那么什么是编码? 所谓的编码，更准 确地说，信道编码，通过引入冗余信息，使得一部分比特发生错误下，仍有可 能按照一定的规则纠正这些错误，以实现无失真地传送和处理信息。 编码理论诞生于二十世纪四十年代后期，以美国数学家s h a n n o n 的开创性 论文通信的数学理论( am 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 的思想h a m m in g 乜3 、 m a s s e y d , 4 , 5 】、b o s e 、 c h a u d h u r i 、h o c q u e n g h e m ( b c h ) 【6 , 7 , 8 】、g o p p a 9 , 1 0 】、m a c w i l l i a m s 11 , 1 2 】等人设 计出一系列好码，并给出了有效译码的方法。使纠错码理论实现了跨越式发展， 也使得纠错码理论受到了越来越多的学者关注，特别是数学家的重视，这使纠 错码理论无论在理论上还是在实际应用中都得到飞速发展。迄今，纠错码理论 将近六十年的历史，其发展过程大致分以下几个阶段： 2 0 世纪5 0 年代至6 0 年代初，这是纠错码从无到有得到迅速发展的年代。主 要研究各种有效的编码方法和译码方法，奠定了线性分组码的理论基础。 2 0 世纪6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期，不仅 提出了各种各样的编码译码方法，而且还研究了码的重量分布、译码错误概率 等纠错码实用化问题，所有这些问题的研究为纠错码理论的应用打下了坚实基 础。在此期间，以有限域理论为基础的线性分组码理论已趋成熟。 2 0 世纪7 0 年代至8 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 0 世纪9 0 年代，可以说，这是纠错码理论研究达到辉煌时期。在1 9 8 9 年， n e c h a e v u 副研究发现k e r d o c k 码可以看成环乙上的循环码，这开创了纠错码的一 个新的研究方向一环z j 上的纠错码的理论研究。在1 9 9 4 年，h a m m o n s u 4 1 等人发 现了二元k e r d o c k 码和其他的些高效的二元非线性码可以看作是环z 。上线性 码在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 恒等式。万 哲先n 6 1 出版了一q u a t e r n a r yc o d e s 。从此以后，人们在深入研究环z 。上的 编码理论的同时，又开始研究更一般的有限环上的编码理论。这使有限环上的 编码理论的研究进入一个全新的研究方向。 1 2 有限环上循环码的中国积和线性码的m a c w i l l i a m s 恒等式的研究进展 有限环上循环码，线性码的m a c w i l l i a m s 恒等式以及线性码的支重量一直 是编码研究的热点。c a l d e r b a n k 和s 1 0 a n e n 5 1 将n e c h e v n 引、h a m m o n s n 4 1 等人的结 论加以推广，得到了环z 。上单根循环码的结构；p l e s s 和q i a n u 研究了环z d 上循环码的幂等多项式；p 1 e s s ，s o l 6 和q i a n n 刚研究了环乙上非平凡循环自 对偶码存在的条件并且他们的结论让k a n w a r 和l 6 p e z p e r m o u t h n 引推广到环 z 。上；万哲先心叫又将k a n w a r 和l 6 p e z p e r m o u t h 的结论推广到g a l o i s 环 上：更一般，d i n h 和l 6 p e z p e r m o u t h 比 给出了有限链环上循环码和负循 环码的结构。钱建发比2 1 ，等人给出了多项式环只+ 识+ + “扣1 e 上循环码的结 构；朱士信和开晓山阳朝讨论了环z 。上负循环的对偶与自对偶码。同时，利用中 国剩余定理来研究有限环上的编码问题受到关注。d o u g h e r t y 和 s h i r o m o t o 北钉 通过广义中国剩余定理，研究了环乙上m d r 码；d o u g h e r t y ，h a r a d 和s 0 1 4 2 5 1 利用中国剩余定理，研究了有限环上自对偶码；p a r k 心引利用中国剩余定理，研 究了环乙上线性码的生成矩阵和模的独立性：d o u g h e r t y ，k i m 和k u l o s m a n 心 通过广义的中国剩余定理，讨论了有限主理想环上m d s 码和自对偶码。 m a c w i l l i a m s n h 趵l 叵等式是描述线性码与其对偶码各种重量分布之间的相 互关系。这一等式是编码理论中最伟大的结论之一，在编码理论中已经得到广 泛应用。同时，这一等式也得到广泛推广，主要是根据定义各种不同的线性码 重量计数器。s h i r o m o t o 口叫给出一类新型的w l a c w i l l i a m s 恒等式并且在文献中 讨论了生成矩阵在g f ( q ) 上的g f ( q ”) 线性码的重量计数器。w e i n 2 1 提出了广义 汉明重量在第二型密窃信道中的应用后；k l o v e 阳3 3 给出了有限域上线性码的支 重量分布和s i m o n i s 口4 3 53 分别给出了有限域上线性码的两种不同的广义 m a c w ill i a m s 恒等式。二十世纪末，人们发现g a l o is 域上许多非线性码( 如 k e r d o c k 码、p r e p a r a t a 码、g o e t h a l 码) 可以利用g a l o i s 环上线性码经过g r a y 变 换得到，于是g a l o i s 环上线性码的结构特性研究成为编码领域中热点问题。当 然，研究有限环上m a c w i l l i a m s 恒等式仍然是当前编码领域中热点。k l e m m 口6 1 2 给出了环乙上线性码的m a c w i l l i a m s 恒等式；朱士信 给出了环乙上线性码的 对称式m a c w i l l i a m s 恒等式。a s h i k h m i n 8 3 们分别讨论了环乙上线性码的广义汉 明重量和g a l o i s 环上线性码的广义汉明重量；崔杰h0 3 分别给出了环乙上自由 的线性码广义的m a c w i l l i a m s 恒等式和支重量分布；d o u g h e r t y 引，等人研究了 环乙上线性码的广义李重量并且给出了有限环上广义汉明重量的m a c w i l l i a m s 恒等式：s h i r o m o t o h 引给出环z f 上线性码关于李重量和欧几里德重量的 m a c w i l l i a m s 恒等式；万哲先h 给出了g a l o i s 环上线性码关于汉明重量的 m a c w i l l i a m s 恒等式。 1 3 本文的主要内容 本文主要研究了有限环上循环码的中国积和线性码的m a c w i l l i a m s 恒等 式。研究了环乏( k = ( 兀：。只) ”，码长以不能被b 整除) 上中国积循环码的性质； 还研究了g a l o i s 环上线性码关于李重量和欧几里德重量的m a c w i l l i a m s 恒等 式；而且研究了z ：( p 是素数) 环上线性码关于任一分划的m a c w i l l i a m s 恒等 式和支重量。本文的研究结果丰富了有限环上循环码的研究和弥补了有限环上 线性码的m a c w i l l i a m s 恒等式的研究，并且为将来构造有限环上的码提供重要 的理论依据。具体内容如下： ( 1 ) 描述了中国剩余定理，定义了环乙( k = ( 1 7 ；- _ 。髟) ”，码长n 不能被只整 除) 上中国积循环码，给出了中国积循环自对偶码存在的充要条件并且进一步 给出中国积循环码的最小上界和最小生成子。 ( 2 ) 定义了z 。( 尼2 ) 环上李重量和欧几里德重量的m p l y 重量计数器，给 出了z 。环上一类新型的李重量和欧几里德重量的m a c w il lj a m s 恒等式。视环 锹( p 8 ，聊) 为z 一上秩为m 的自由模，考虑环础( p 。，聊) 上的线性码的生成矩阵在 z 一上，环锹( p 。，聊) 上线性码的李重量和欧几里德重量计数器和环z 。上线性 码的李重量和欧几里德重量的聊一p r y 重量计数器关系，得到了环础( p 8 ，m ) 上线 性码的李重量和欧几里德重量的m a c w i l l i a m s 恒等式。 ( 3 ) 定义了z 4 环上长度为，z 的线性码的广义l e e 重量计数器，给出了乙环 长度为玎的线性码的广义l e e 重量的m a c w i l l i a m s 恒等式。定义了z d 环上长度 为n 的线性码的广义l e e 重量计数器的等价形式，得到了相应的乙环长度为，2 的 线性码的等价形式的广义l e e 重量的m a c w i l l i a m s 恒等式。 ( 4 ) 研究了z ，( p 是素数) 上关于任一分划的m a c w i1 1j a m s 恒等式，当 p l u l = f ，视g ，为码c 的限制码时，给出了c ，和码c 的重量分布之间的联系；当 视c 矿为码c 的子码时，给出了型为( p 2 ) 的z 。线性码关于任一分划的 ， m a c w i l lj a m s 恒等式。 ( 5 ) 研究了z ，( p 是素数) 上线性码的支重量和广义p l o t k i n 界，给出了 z ，线性码的广义齐次重量的p l o t k i i i 界。 第二章乙环上循环码的中国积 2 1 本章的预备知识 设互= o ，1 ，k 一1 ，尼( 2 ) 为自然数，v = z ：是秩为n 的自由模。环互上长度 为n 的码c 是乏的加法子群，c 也是乏的乙子模。一个码字c = ( c o ，巳一。) c 可 以看作多项式c o + c l x + + 巳一。z ”1 r x - 乙b 】( 矿一1 ) 。如果给定一个码字 ( ，巳一，) c ，它的变换( c n 掣c o ，巳一：) c ，那么我们称码c 是循环码。如果 长度为n 的码c 是循环码，那么它的码字的多项式就是r x 】的理想。码c 的秩， 定义为最小生成码c 的个数，记为r a n k ( c ) ，特别码c 的最大的自由的r 子模， 则称码c 的秩为自由秩，记为厂一r a n k ( c ) 。z 。n 中任两个向量的内积为： v u = ( u 1 , “2 ，u n ) ，v v = ( ，屹，1 2 n ) v ， ( “，v ) = 芝：“f v f ( m o d k ) ， 如果沁v ) = 0 ，则称u 和v 正交。设c 是z ，线性码，令 “川 c 上= v 矿j ( “) = o ，对v uec 。 则容易证明c 上也是长为，z 的z 。线性码，并称c 上为c 的对偶码。如果c c 1 ，称 c 为自正交；如果c = c 1 ，称c 为自对偶。 2 2 中国剩余定理和多项式码 设k = ( 兀二只) “，对v c 乙，定义映射少：五_ z 。? ，即y 一( c ) = c ( m o dp 7 ) ，此 映射可以自然推广乏到z 二。对环z 七上的码c ，定义c 渤ky 一( c ) 。设 ：彳一e z ；，则少( v ) = o y ( 1 ，) 。根据中国剩余定理，y 是模同构，因此 c 兰0 c 。反过来，给定z 。上一个长度为聆的码c 刚，对f = l ，s 有： 门 c r t ( c 见，c 儿) = - 1 ( h ，k ) iv c 嘞 = v z ：iy 一( y ) c 咖 。 那么c r t ( c ，c 魄) 是环乙上长度为n 码。如果c 分别是z 一上循环码；也 就是说，c 锄分别是z 一 x ( 矿- 1 ) 里的理想，根据广义的中国剩余定理， c r t ( c 川，c 冉) 是环z k x ( x ”一1 ) 里长度为n 的循环码。称c r 丁( c ，：，c 魄) 是 码c 剐，码c n 的中国积循环码。 定义： ：z ： x ( x ”一1 ) 专z 【x 】( x ”一1 ) 使得一( c o + c t x + + 巳一l x ”1 ) = c o ( m o d ) + c 。( m o d p 7 ) x + + c 。一。( m o d ) z ”1 。 那么定义：o 。：五 z 】0 ”一1 ) 寸( z 一 x 】( 矿- o ) x x ( z 毋 石 ”一1 ) ) 即：。( p ( z ) ) = ( 。，( p ( x ) ) ，一( p ( x ) ) ) 。 设c 舟分别是z 一上长度为，z 的循环码，如果，( z ) 分别是z 。上矿一l 的因子， 那么很容易得到：( z ( x ) ，f a x ) ) 也是乙【x 】里x ”- 1 的因子。在z 一 x 】里，存在 彼此互素的n ( x ) z d ( x ) ，使得z o ( x ) 以d ( x ) = - 1 。并且 4 d e g ( f ) o ( x ) ) = d e g ( f ) 7 ( x ) ) ，对所有的，0 s m ，1 f ，i 7 s 。而且，定义： 户( 7 ( z ) = o ) 露；( x ) 露 ) z 7 ( z ) 。习惯上，对次数为，的多项式( z ) ，定义 x f ( x q ) 为互反多项式，记为厂( x ) 。 2 3 中国积循环码及其对偶码 我们将需要引理 2 3 卜2 3 3 来分析乙上的中国积循环码的对偶码。 引理2 3 1 n 钔c 是乙上长度为疗的循环码，那么在乙【x 里，存在彼此互 素的多项式f o ( x ) ，鼻( 戈) ，c ( x ) ，使得e ( x ) f ( x ) e ( x ) = 矿- 1 ，并且 c = ( 丘( x ) 以丘( x ) ，毫一。( x ) ) 。 引理2 3 2 n 引c 是乙上长度为，z 的循环码，并且 c = ( 丘( x ) ，只定( x ) ，二1 毫一。( x ) ) ， 这里e ( x ) e ( x ) c ( x ) = 矿- 1 ，那么 c 1 = ( 露( x ) ，只定( x ) ，。1 定( x ) ) 。 引理2 3 3 乜引如果每一个c 功分别是乙上长度为玎的循环码，并且 c n ) - ( 丘( x ) ；只窟d ( x ) ；一定d ( x ) ) ， 那么c r t ( c 削，c n ) 也是互上的循环码，并且生成子 q = ( 戽1 ) ，丘c $ ，( x ) ) ；( 血b ) ：1 ( 窟1 ，( x ) ，毫5 ，( x ) ) - ；( 血b ) ”1 ：( 定( x ) ，宪2 ( x ) ) 。 i = 1 ， 现在我们将先证明下面的定理，然后给出五上的中国积循环码的对偶码的生 成子。 定理2 3 4 - 如果乙= o 乙并且c 是z 上长度为刀的循环码， c 凡) - ( 印( z ) ；只窟d ( x ) ；。1 毫o ( x ) ) ， 那么 l ( c 刖，c 儿) 上= ( 硝( c n ) 上，刀( c 以) 上) 。 证明 首先证 硝( c n ) 上，露( c “) 上) 呈啦( c 削，c 儿) 上。 假设g ( x ) ( 刀( c 功) 1 ，力( c n ) 上) ，那么存在f ，( x ) ( c 庙) 上，f - 1 ，s ， 使得g ) = ( o 卯( f 1 ( x ) ，刀( t ( x ) ) ，对任意的z ( x ) ( c a ) ，i = 1 ，s ，有 g ( x ) ( 一( 彳 ) ，力( z ) ) = ( 印( ( _ ) c ) ，刀( ( x ) ) ) 。( 卯( z ( x ) ，刀( z ( x ) ) ) = ( 硝( ( x ) ，刀( t ( x ) ) ) ( 刀( z ( x ) ) ，刀( ，( x ) ) ) = 硝( o ) ，中刀( o ) ) = ( o ，0 ) 因此g ( x ) ( c n ，c ) 上。 下面只需证i 。( c ，c 魄) 上i = i ( 开( c n ) 1 ，刀( c 慨) 上) l 。 由于吼是同构的，则 l ( 硝( c | p l ) 上，刀( c ，i ) 上) i _ l ( 硝( c n ) 上i l ( c n ) 上) l = i ( c n ) 1j i ( c ( p i ) 1j = ( i ! i b ) 这里的= 量，d e g ( f j ( x ) ) 。另一方面，根据引理2 3 3 ，i 。( c c 川，c 丹) i = ( 卉b ) 。， 这里的= m - 1 ( 聊一歹) d e g ( 硝( x ) ) 。因此l 。( c 川，c n ) 上i = 卉( 只) 一h = 血只) 4 。口 推论2 3 5 如果每一个c n 分别是乙上长度为聆的循环码，并且 c 聊) _ ( 丘( x ) ；只窟o ( x ) ；_ 定o ( x ) ) ， 那么c r t ( c ，c 慨) 上是z 。，上长度为刀的循环码，记为q ，则 q = ：1 ( 彦咿( x ) ，雇印( z ) ) ；( 卉b p ：1 ( 毫驴o ) ，毫咖( x ) ) ；( 血只) ”1 ：( 窟巾( x ) ，窟咖 ) ) 。 i = l j 证明根据定理2 3 4 ，有c r t ( c 刖，c 几) 上= ：1 ( ( c n ) 上，( c 几) 1 ) ， 然后根据引理2 3 2 和2 3 3 得证。口 注：为了方便，设q = c r t ( c 协，c 慨) ，q 记为q 的对偶码。 现在我们给出环互上的自对偶码存在的充要条件。 定理 2 3 6 假设c 崩是乙上长度为甩的循环码， c 研) _ ( 印( x ) ；b 窟d ( x ) ；一定o ( x ) ) ， 那么q 是循环自对偶码的充要条件是对0 f ，- ，m ，i + j 薹l ( m o d m + 1 1 ，f o 是 e 伊的伴随，1 f j 。 证明先证充分性，如果对0 i , y 聊，i + j 兰l ( m o d m + 1 ) ，f o 是碍o 的伴随， 1 f s ，根据是同构的，q = a 。f ，那么q 是自对偶的。下面证必要性，只需 证每一个c n 是z ，上自对偶码。设印d = e o ，对0 f ，m ，使得 i + j - 1 ( m o d m + 1 ) ，那么有卅d 霹) = 碍n e o = r - 1 ， 并且 ( c 咖，) 上= ( 邱，) ；b 窟，) ；一母) 。 由于( c 所) 上= c 刖，根据引理2 3 1 ，知生成多项式是唯一的，对所有的f ，f ， o f m ，0 f s ，f n 是碰。的伴随：也就是说，f 是y 伊的伴随，1 f s ， 对0 i , j m ，i + j 兰1 ( m o dr e + 1 ) 。口 下面我们将给出c 聊的另一种表达方式。 6 定理 2 3 7 假设c 渤是z 卯上长度为刀的循环码， c 所) - ( 丘( x ) ；b 窟7 ( x ) ；一定，) ( x ) ) ， 那么存在o ( x ) ，f ( o ( x ) ，使得c o 。= ( f o 订( x ) ；只z o ( x ) ；1 2 2 ( z ) ) ，这里 嚣。( x ) 卜i ，f 。m 0 ( x ) 。 证明根据引理2 3 1 ，在z 。，上存在彼此互素的多项式g o ( x ) ，e 7 ( x ) 使 得，曩d ( x ) e o ( z ) - x ”一1 并且 c t 日) = ( 印( x ) ；b 忘订( z ) ；。1 定，) ( x ) ) 。 设矗糸x ) = 碍力( x ) ，z u ( x ) = f o 力( x ) 鼻等( x ) ，对0 i m 一2 ，1 j s 。那么得到新 的生成子。口 2 4 中国积循环码的最小上界和最小生成子 在这一部分，我们先讨论中国积循环码的最小上界，然后再决定循环码的 最小生成子( 秩) 。 定理2 4 1 设假设c 渤是z 。上长度为n 的循环码， c 协= f o d ( 工) ；只z “( x ) ；q 础( x ) ) ，这里d ) j jz 3 ( 功。那么 d ( q ) d e g ( o ：1 ( 。f 。o 一) ( 、x ) ，以2 ( x ) ) ) + 1 。 证明 根据引理2 3 7 我们得到q 新的形式， q = ：1 ( 刀”( x ) ，”( x ) ) ；( r i b ) ：1 ( z o ( z ) ，彳o ( x ) ) i f f i l m 一1、 ；( n 只) ( z ：( x ) ，以2 ( x ) ) i = 1 ， 根据是同构的和定理2 3 7 的证明，知 设糸x ) = 胃d ( x ) ，z u ( x ) = 碍力 ) 只譬( x ) ，对0 i m - 2 ，1 _ ，j ，因此 ：1 ( z o ( x ) ，z 。( x ) ) = ：1 ( ( x ) ，2 ( x ) ) ：1 ( 1 2 0 ) ( 、x ) ，f 譬( x ) ) 即：1 ( f o u ( x ) ，刀町( 力) j i ：1 ( 筏( 功，厂o - l ( x ) ) 。 对v g ( x ) q ，存在f ( x ) ，使得g ( x ) = ：1 ( z ：( x ) ，f 2 2 , ( x ) ) t ( x ) ，所以 d e g ( g ( x ) ) d e g ( o ；1 ( z 三( x ) ，z ：( x ) ) ) 。 又因为：1 ( z 三( x ) ，以：( x ) ) q ，那么d ( q ) d e g ( q ) 2 1 ( z ) ，z 2 ( x ) ) + 1 。口 我们知道对0 i 聊一1 ，记码c ，是由- 1 ( z 1 ( x ) ，z 。( x ) ) 生成的，c 卅一。是由 ：( ：( x ) ，芷 ( z ) ) 生成的，那么c ：是巴一。的子码，因此d ( q 一。) d ( e ) ；也就是 说上面的上界是g 。的最小的上界。 根据文献 2 8 中的定理2 ，利用相似的方法，可以得到下面的定理。 定理2 4 2 如果生成子是q ， q = ：1 ( ”( z ) ，f o ” ) ) ；( 1 只归：1 ( z a ( x ) ，z o ( x ) ) f f i l j m 一1 、 ；( 1 - i p ，) o ：1 ( z 1 ( x ) ，z 2 ( x ) ) 。 7 设仍( x ) = ：1 ( z o ( x ) ，z 。( x ) ) 磊瞳】，那么( x ) i l 一，( x ) i ( 一1 ) ，并且假 设d e