（应用数学专业论文）z2α上重根负循环码.pdf

环z r 上重根负循环码 摘要 经典的编码理论以有限域上的向量空间为背景。二十世纪九十年代，人们 发现一些高效的二元非线性码可以看作是z 上线性码在g r a y 映射下的二元象， 有限环上的编码理论获得重要突破。自此，有限环上的编码理论成为编码研究 的热点。本文主要研究了整数模2 4 的剩余类环即z 。上长为2 疗( k 1 ，r l 是 奇数) 的负循环码及其对偶码，探讨了自对偶负循环码的性质；还研究了 g r ( 2 4 ，所) 上长为2 的负循环码的h a m m i n g 距离和齐次距离。具体内容如下： 1 运用离散的f o u r i e r 变换，给出了环z 。上长为2 k 月的负循环码的生成 多项式和个数的计算公式。 2 利用m a t t s o n - s o l o m o n 多项式，给出了环z 。上长为2 n 的负循环码的 对偶码的生成多项式。 3 得到了环z 上长为2 k n 的自对偶负循环码的一些性质，并给出了环 z 。上长为2 k 以的非平凡自对偶负循环码存在性及其一个充要条件。列举了z 。上 码长小于等于6 0 的g r a y 象是二元线性自对偶循环码的非平凡自对偶负循环码。 4 给出了g r f 2 4 ，所) 上长为2 为的所有负循环码的h a m m i n g 距离和齐次距 离，特别地，得到了z 上长为2 为的负循环码的l e e 距离，利用g r a y 映射得到 这些负循环码的二元象。 关键词：g a l o i s 环负循环码循环码h a n h n i n g 距离齐次距离g r a y 映射 对偶码自对偶码 r e p e a t e d - r o o tn e g a c y c l i cc o d e so v e r z ，。 a b s t r a c t c l a s s i c a lc o d i n gt h e o r yt a k e sp l a c ei nt h es e t t i n go fv a c t o rs p a c e so v e rf i n i t e f i e l d s i nt h e1 9 9 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 so v e rf i n i t er i n 萨h a s e x p e r i e n c e d t 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 t d i s c o v e r yt h a t s e v e r a l w 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 l lb ei d e n t i f i e da s i 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 e r 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 nt h i sp a p e r , w es t u d yn e g a c y c l i cc o d e so f l e n g t h 2 kj l ( k 1 ，ni so d d ) o v e rt h ei n t e g e r sm o d u l o2 4a n dt 1 1 e i rd u a l s ，a n d i n v e s t i g a t es o m ep r o p e r t i e so fs e l f - d u a ln e g a c y c l i cc o d e s w ea l s os t u d yt h e h a m m i n gd i s t a n c e sa n dh o m o g e n e o u sd i s t a n c e so fn e g a e y c l i cc o d e so f2 o v e r g r ( 2 4 ，肌) t h ed e t a i l sa r eg i v e n 嬲f o l l o w s ： 1 u s i n gt h ed i s c r e t ef o u r i e rt r a n s f o r m ，w eg i v et h eg e n e r a t o r so fn e g a c y c l i c c o d e so f l e n g t h2 k 肛o v e rz 。a n dt h ee n u m e r a t i o nf o r m u l ao f t h en u m b e ro f s u c h n e g a e y c f i cc o d e s 2 u s i n gt h em a t t s o n - s o l o m o np o l y n o m i a lo fac o d e w o r d ，w ed e r i v et h e g e n e r a t o r so f t h ed u a l so f n e g a c y c l i cc o d e so f l e n g t h2 n o v e rz 。 3 s o m ep r o p e r t i e so fs e l f - d u a ln e g a c y c l i cc o d e so fl e n g t h2 j zo v e rz 。a r e o b t a i n e d , a n dan 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 nf o rt h ee x i s t e n c eo fs e l f - d u a l n e g a c y c l i cc o d e so fl e n g t h2 n o v e rz i sp r o v e d w el i s tn o n t r i v i a ls e l f - d u a l n e g a c y c l i cc o d e so v e rz 4o fl e n g t h 6 0 ，w h o s eg r a yi m a g e sa r eb i n a r yl i n e a r s e l f - d u a lc y c l i cc o d e s 4 t h eh a n n n i n gd i s t a n c e sa n dh o m o g e n e o u s d i s t a n c e so fa l ln e g a c y c i cc o d e s o fl e n g t h o v e rt h eg a l o i sr i n g g r ( 2 , n 1a r e g i v e n i np a r t i c u l a r , t h el e e d i s t a n c e so fa l l n e g a c y e l i cc o d e so v e rz 4o fl e n g t h2 a r eo b t a i n e d t h eg r a y i m a g e so f s u c hn e g a c y c l i cc o d e so v e rz 4 a r ea l s od e t e r m i n e du n d e rt h eg r a ym a p k e yw o r d s ：g a l o i sr i n g ：n e g a e y c l i cc o d e s ；c y c l i cc o d e s ；h a m m i n gd i s t a n c e s ： h o m o g e n e o u sd i s t a n c e s ：g r a ym a p ；d u a lc o d e s ；s e l f d u a ic o d e s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果。也不包含为获得金毽王些盔堂 或其他教育机构的学位或证书而使 用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明 并表示谢意 学位论文作者签名： 签字日期：歹萨声占月石日 | 学位论文版权使用授权书 本学位论文作者完全了解金墼至些太堂有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅本人授权金 照王些盔堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日期：7 年5 月易日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导 签字日期：秽7 年且参日 f 电话。 邮编。 致谢 我首先要感谢我的导师朱士信教授，朱老师严谨的治学态度，一丝不苟的 工作作风深深地感染和激励着我。三年来，朱老师不仅在学业上给我细心地指 导同时还在思想和生活上给我无微不至的关怀，在此谨向朱老师表示诚挚的 感谢和崇高的敬意! 感谢我的家人三年来在物质以及精神上给我的支持，这为我完成学业和论 文奠定了重要的基础，在此祝愿他们永远健康，永远快乐! 我还要感谢我的师兄妹和同学，他们给我的鼓励和帮助，我永远铭记 在心! 最后，感谢学校为我提供了良好的学习环境和优越的学习条件，感谢理 学院机房老师认真负责的工作和热情的服务l 作者：开晓山 2 0 0 7 年5 月 第一章绪论 编码理论诞生于二十世纪四十年代后期，以s h a n n o n 的开创性论文通信 的数学理论“1 为标志，这篇论文奠定了通信的数学基础。自此以后，根据 s h a n n o n的思想，h a m m i n g 、 m a s s e y 3 , 4 刀、 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 , s l 、g o p p a 9 , 1 0 1 、m 刖：l t v i | l i a m s o t , 1 2 1 等入设计出一系列好 码，并给出了有效译码的方法。域上的纠错码，即经典的纠错码经过三十多年 的研究，到八十年代初，在理论和实践中都获得到了重要的进展。在理论上以 g o p p a 为首的一批学者构造了一类g o p p a 码，其中一类子码能达到s h a n n o n 在 信道编码定理中所提出的s h a n n o n 码所能达到的性能，这在纠错码历史上具有 划时代意义。在实际中，大规模集合电路和微机的迅速发展为纠错码的实用打 下了坚实的物质基础，与实用相关的各种技术及有关问题得到了逐步解决，经 典的纠错码在实用中也取得了巨大的成功二十世纪九十年代，n e c h e v i i 、 h a m m o n s 1 4 3 等人发现了二元k e r d o c k 码和其他的一些高效的二元非线性码如 p r e p a r a t a 、d e l s a r t e - g o e t h o l s 和g o e t h o l s 码等可以看作是z 4 上线性码在 g r a y 映射下的二元象，有限环上的编码理论获得重要突破。这也使有限环上的 编码理论受到了广泛的关注。 1 1 有限环上负循环码的研究进展 有限环上循环码，常循环码以及自对偶码是研究的热点。c a l d e r b a n k 和 s l o a n e “”将n e c h e v “3 1 、h a m m o n s m l 等人的结论加以推广，得到了z ，上单根循环 码的结构，k a n w a r 和l 6 p e z p e m o u t h “”用不同的方法研究了z ，上单根循环码 的结构。万哲先“”将k a n w a r 和l 6 p e z - p e r m o u t h “6 3 的结论推广到g a l o i s 环上。 同时，有限环上的重根循环码也受到了学者的关注。a b u a l r u b 和o e h m k e 1 8 1 讨论 了z 。上长为z 的循环码的生成元；b l a c f o r d “利用变换的方法给出了z 。上长为 2 c n 是奇数) 的循环码及自对偶码的结构；最近，s t e n v et d o u g h e r t y 和s a n l i n g b 叮得到了z 。上任意偶长的循环码的结构。 有限域上的负循环码最初由b e r l e k a m p 乜1 1 在二十世纪六十年代后期提出，而 有限环上的负循环码最初见于z 上的单根负循环码，由w o l f m a n n 1 提出。 w o i f m n n m 3 利用一个同构研究了z 上奇长的负循环码，即单根负循环；d i n h 和 l e z - p e r m o u t h 1 将其推广到有限链环上。自此，有限链环上单根负循环码的 结构得到基本解决。与此同时，有限环上的重根常循环码( 码长与有限链环的 剩余域的特征不互素的情况) 也引发了众多学者的兴趣。b l a c k f o r d 1 运用燹换 的方法分类了z 上所有的偶长的负循环码；d i n h 陋“3 研究了g a l o i s 环 g r f 2 4 ，m 1 上长为2 的负循环码，并给出了z ，上长为z 的负循环码的h a m m i n g 距离。l e e 距离，e u c l i d e a n 距离。a n n a s s l 5 9 e a n 田1 证明了g r ( 2 。，聊1 上偶长的 负循环码是主理想。朱士信、李平等“8 卸研究了环e + 洒：上重根( 1 + “) 一常 循环码的结构和性质。总体上看，有限环上的重根负循环码的研究进展比较缓 慢。 1 2 本文的主要内容 本文主要研究z 。鄱整数模z 的剩余类环上的任意偶长的负循环码，给出这 类负循环码及其对偶码的结构；研究z 。上的任意偶长的自对偶负循环码的性 质。还研究了g 援( 2 4 ，历) 上长为2 的负循环码的h a m m i n g 距离和齐次距离。本文 的研究结果为构造z ，上的码特别是z 。上的码提供重要的理论依据。 ( 1 ) 研究了环z 。上长为磐疗的负循环码的结构。运用离散的f o u r i e r 变换， 给出这类负循环码的生成多项式和个数的计算公式。 ( 2 ) 研究了环z ，上长为行的负循环码的对偶码的结构。利用 m a t t s o n - s o l o m o n 多项式，给出这类负循环码的对偶码的生成多项式。 ( 3 ) 讨论了环z ，上长为2 k n 的自对偶负循环码的性质。在( 1 ) ( 2 ) 基础上， 给出自对偶负循环码的一些性质并确立了环z 。上长为2 k 疗的非平凡自对偶负 循环码存在性，并给出了存在的一个充分必要条件。列举了z 。上码长小于等于 6 0 的g r a y 象是二元线性自对偶循环码的非平凡的自对偶负循环码。 ( 4 ) 给出了g 埋f 2 4 ，r a l 上长为2 k 为的负循环码的h a m m i n g 距离和齐次距离。 、， 特别地，给出z 。上长为2 为的负循环码的l e e 距离，并且利用g r a y 映射得到这 些负循环码的二元象。 2 第二章有限环z ，。上偶长的负循环码 2 1 基础知识 环r 的理想叫做主理想，若它由一个元素生成。若r 的所有理想都是主理 想，则称五是主理想环。若r 有唯一的右( 左) 理想，则稼r 是局部环。而且， 若r 的所有右( 左) 理想按集合包含关系排序，则月叫做链环对有限交换链 环， 我们有下面已知结论。 命题2 1 1 m 1 设足是有限交换环，则下面的条件等价： ( 1 ) r 是局部环，且最大理想肘是主理想； ( 2 ) 胄是局部主理想环； ( 3 ) 五是链环。 本文我们主要考虑有限交换链环。设口是矗的最大理想肘的一个固定生成 元，则显然口是幂零元。设它的幂零指数是t ，则r 的理想形成一个链： r = a 0 ) 3 ( 口1 ) ，3 ( 口l - ld ( a t ) = ( o ) 设豆= r m ，用”一”表示由置p 1 到豆【工】的自然同态，影射”一”将，变成 ，+ m ，而x 不变。 命题2 1 2 叭设r 是有限交换链环，最大理想m = ( a ) ，设r 是a 的幂零指数， 则 ( 1 ) 存在素数p 和正整数，t ( k 2 f ) 使得h = 矿，同= ，歪的特征是p ，r 的特征是p 的方幂。 ( 2 ) 肛) i = 旷，i = o , k 山特别地，h = 阱e p k = i t 。 两个多项式石o ) ，a ( x ) q x 】叫做互素的，若“( 工) ) + ( 五( x ) ) = r x 1 ，或 等价地，若存在9 1 ( x ) ，( 工) 剐司使得石( 工) 蜀( x ) + 正( x ) g ：( 工) = 1 若厂( 工) 在 豆【x 】中不可约，则厂( x ) e 叫x 】叫做基本不可约多项式一个多项式厂( 工) r x 】 被称为规则的，若它不是零因子 命题2 l3 。”设，( 善) = + q x + + 只【x 】，则以下条件等价： ( 1 ) ，( x ) 是规则的： ( 2 ) ( ，q ，) = r ； ( 3 ) 存在某个q 是单位，o s f 月： ( 4 ) 于( 工) o h e n s e l 引理保证了多项式在r 中两两互素的分解可以提升到豆上。 引理2 i 4 ( h e n s e l 引理) 3 ”设s ( x 1 是r 上的多项式，且 于( x ) = 蜀o ) g ：( x ) g ，0 ) 。其中g l ( x ) ，g ：o ) ，g r ( x ) 是豆上两两互素的多项 式，则r 上存在两两互素多项式彳( z ) ，石( 工) ，z o ) 使得 3 ，( x ) = 石( 工) 正( x ) z ( x ) ，且z ( 善) = 蜀( x ) ，i = l ，2 ， 根据h e n s e l 引理，当( 玎，p ) = l 时，矿一l 在z ，i x 中可以唯一分解成基本 不可约多项式石( x ) , d * l l , i z ( x ) 之积。若是z ，的某个扩域中的栉次单位根，则 对某个厶1 兰i ，z ( ) = 0 。z ( x ) 叫做在z 一上的极小多项式若于o ) 是 r l 在e x l 中的不可约园子，则根据h e n s e l 引理，一1 在z ，融中存在难一 的不可约因子使得于( 工) z ，( x ) ( m o d p ) 。f ( x ) 叫做灭x ) 的h e n s e l 提升。 设d 表示满足尹( x ) 在豆的代数闭域中有不同的根的所有多项式 f ( x 1 r x 1 的集合。下面的性质给出了规则多项式与d 中元素不可约与基本不 可约之间的关系。 命题2 1 5 设f ( x 1 是规则多项式，则 ( 1 ) 若f ( x 1 是基本不可约的，则f ( x ) 是不可约的； ( 2 ) 若，( x ) 是不可约的，则于( z ) = 略o 广，其中“夏，g ( x ) 是夏扛】中首 一不可约多项式。 ( 3 ) 嵩i f ( x ) e d ，则i ( x ) 是不可约当且仅当s ( x ) 是基本不可约 对有限局部交换环，多项式的e u c l i d e a n 的算法如下： 命题2 1 6 嘲设置是有限交换局部环，厂( 工) ，g ( x ) 是r 嗍中的非零多项式。若 g ( x ) 是规则的，则存在着g ( x ) ，r o ) r 【x 】使得f ( x ) = g ( 工) 9 1 ) + ，( 工) ，且 d e g ( r ( x ) ) d e g ( g ( x ) ) 设z o ) ，a ( x ) r x 1 ，如果存在可逆元素，e r 使得z o ) = 呒x ) t 那么 石( 工) 叫做正o ) 的相伴元。如果由f ( x ) = g ( 工) o ) ，其中g ( x ) ，h ( x ) r 【x 】， 则可推出g ( x ) ，或螽( x ) 是震中的可逆元，那么我们称厂( x ) r 【x 】是不可约的 若f ( x ) 不是不可约的，则f ( x ) 是可约的。注意多项式的不可约性处决于它所 在的环，例如，+ l 在整数环z 中不可约，但在z ，中可约。 经典的编码理论以有限域上的向量空间为背景口对，自从有限环上的编码获 得重大突破后，有限域上的编码理论自然地就推广到有限环上。 有限交换局部环太上长为的码是的一个非空子集，若它是的震一 子模，则它是线性码。r 上长为 r 的线性码c 称为名一常循环码。若对某个单 位z e 足，c 在自同构 t ：( c o ，q ，c 。) i - 1 ( 弛- l ，岛，c , 4 ：) 下不变。根据这个定义，当a = 1 ( 或一1 ) 时，a 一常循环码是循环码( 或负循环 码) 。每个码字c = ( c o ，q ，c n i ) 都对应一个多项式c ( x ) = c o + q 工+ + c u l x “。， 这个多项式叫做码字多项式。习惯上，我们视码字与码字多项式为同一概念。r 上长为的力一常循环码可以看作是商环r 工】( 一五) 中的理想。 给定向量u = ( ，m ，i ) ，1 ，= ( v o ，v l ，- 1 ) 仨r “，定义e u c l i d e a n 内积 或点积为v = “o v o + v 1 + + “m v 一l ( 在足中计算) 。若v = 0 则称向量“，v 是正交的。对月上长为的线性码c ，它的对偶码c 1 是指与c 的所有码字都正 4 交的丑的维向量组成的集合，即c 1 = u l u v = 0 ，对所有的v e c l 若c ec 1 ，则码c 叫做自正交的；若c = c 1 ，则称码c 是自对偶的。若r 是有限链环，最大理想是( m ) ，m 的幂零指数，是偶数，则码m ；) 是自对 偶码，我们称其为平凡自对偶码。本文中，我们将更为详细地讨论有限环上非 平凡的自对偶负循环码。先给出下面的结论 命题2 1 7 嘲设五是阶为p 。的有限环，则r 上长为刀的线性码c 中码字的数目 是矿，其中k 是集合 o ，i ，a n 中的某个整数。而且，对偶码c 。中码字的数目 是一，其中k + l = a n 我们知道如果z 一【司中的多项式，( x ) 模p 约化，用于( 力表示，在f ，【x 】中 不可约，那么，o ) 是z ，【善】中的基本不可约多项式特征为p 4 ，维数为m 的 g a l o i s 环定义为环z ，的次数为m 的扩环用g r 矿，m ) 表示，即 馓( p 4 ，删) = z ，【工】瓴( 工) ) ， 其中k ( x ) 是z ，【工】中次数为m 的首一基本不可约多项式。注意若口= l ，则 g 胄( 矿，m ) = g f ( p ”) ，若脚= l ，l i | g r ( p * ，m ) = z ，僦( ，肌) 具有以下性质： 命题2 1 8 嘲设g r ( 矿，m ) = z ，【工】( 吒( 工) ) 是g a l o i s 环，则 ( 1 ) g r ( p 4 ，m ) 的每个理想形如( 矿) = 矿g 置( 矿，m ) ，o k l 。先给 出关于有限交换环上负循环码的一个定理。 定理2 1 9 设置有限交换环，c 是置上长为的负循环码，则它的对偶码也 是负循环码。 证明设( 而，而，x n - i ) 是c 1 中的码字。任取( c o ，c i ，厶。) c ，因为c 是负循 环 码，所以( 岛，心，- - c n - l ，c o ) ec 因此， ( x o ，为，x n - 2 ，毛- 1 ) ( q ，吃，- - c n - l ，c o ) = 0 即 一- l c o x o c , 一却吃- 一2 - l + 毛一i c o = o ， 由此推出， 一矗一l c o + x o q + x a c 2 + + 毛一2 气i = 0 ， 故 ( 毛- l ，而，一2 ) ( ，q ，c “) = o 因此，( - i ，x o ，而，毛一2 ) c 1 ，由此得到c 1 是负循环码。 口 2 2 剩余类环 定义环倪= z r 【“】( “矿+ 1 ) 。定义孵到z ；的同构映射矿： 9 ( q 啪+ 口o 1 u + a o 。“2 + + 口0 ，- l p - 1 ，a n _ l , 0q - - 1 一+ a n _ l , 2 1 2 - i - - t - a - 1 。妒一妒- 1 ) = ( 口o ，q o 吒m ，一i t o ，4 0 l q j ，4 2 1 ”，小，口o - 1 ，q 2 | _ i ，口2 ，矿_ l ，巳- 1 ：i - 1 ) 于是，我们有： 缈( “l 篓a n - i j u j ，篓a o j u j , 篓q 。甜，薹一：。甜 - - ( - a 廿- i ，。，q ，。，巴吐“) 。 由此得到 中l f 循环移位与z ；中府循环移位相对应我们得到下面的定理 定理2 2 1 z 2 - 上长为的负循环码经映射伊与吼上的长为以的“一常循环码对 应 t $ i ，我们引入多项式剩余类环孵。( ”，m ) = g r ( 2 4 ，m ) p 1 ( + 1 ) 。文献【2 5 】 对任意的口给出了环孵。( 甜，m ) 的理想结构。为了我们的研究，我们对文献【2 5 】 第三节中的相关结论作微小的改动。 引理2 2 2 对任意的i - i = 整数，存在多项式嘶( “) z “】使得 0 1 ) = + l + 2 q ) ，其中嘶( ”) 是孵。( “，m ) 中的单位。特别地， ( u - 1 ) 7 = 2 吒0 ) ，其中0 ) 是孵。( “，m ) 中的单位。 6 引理2 2 3 环飒。( “，m ) 是有限链环，其最大理想是 一1 ) ，剩余域是g f ( 2 ”) ， 孵。( 1 f ，肌) 的理想是( ( u - 1 ) ) ，o f s 2 口 在( ”，m ) ，引理2 2 2 推出( o l 尸) = ( 2 ) 。因此，( “，1 ) 的理想也可 以写成2 ， 一1 ) ) ，o s f s 2 - 1 ，o j a - 1 。 定理2 , 2 4 设c 是婀。( 虬m ) 的理想，则 ( 1 ) c = ( 一1 ) 。) ， 其中f 是集合 o ，1 ，2 口 中的某一整数，且 i c l ：2 啦“) 。 ( 2 ) c 1 = ( ( 州) m ) ，且h = 2 “。 2 3 离教的f o u r i e r 燹抉 设m 是2 模厅的阶，是2 模疗的分圆配集的代表集。是2 模厅的含i 的 分圆配集的长度，f 是础( 2 4 ，m ) 中疗次本原单位根 定义2 3 1 设c ；( 0 q _ ，乞，d o j ，c i l ，巳- i 1 一，c 0 2 。- i q r ，l ，巳- i 2 1 ) z ；， c ( 工) = c j ，工“加是它的多项式表示c ( 工) 的离散的f o u r i e r 变换是指向量 ( 磊，磊，瓦一) 毗。u ，m ) 4 ， 其中瓦：c ( “一纠：s - i2 t - i q 户州，o s h - - n 一1 ，肋，暑1 ( m o d 2 + 1 ) 。 定义c 的m a t t s o n - s o l o m o n 多项式为享( z ) = 磊“矿，这里磊2 磊 引理2 3 2 ( 反演公式) 设ce z ：，手( ：) 是它的m a t t s o n - s o l o m o n 多项式，则 吲”，y ) 扣) 爿加穆“) ) ， 其中表示分量积。 证明设0 s t s n i 则 a ( ) = 毛广= ( q ，“肌7 尹垮嘶 ：ee l , j z l n i j f “ = ( 删“) q j “ 因此，u - n t ( 1 ，n ) ；( f ) = 艺c f 。注意到在暇，( ”，小) “= “可，即得结论。口 定理2 3 3 设n = 2 甩，其中疗是奇数，则 ，：z 2 l 卜】e ”+ 1 ) 专。刚孵。u ，m 。) 7 是环同构。特别地，若c 是z - 上长为n 的负循环码，则c 同构于q 。，q ，其中 g 是理想 c ( “。r ) ：c ( x ) c 孵。( ，镌) 证明设c = 瓴，磊，弘) 9 t 。( ”，小) “e 9 1 。u ，小) ，毛= 可 ( 下标模刀计算) 。 对分量加法和乘法c 做成一个环。易验证c 兰o 。9 1 。u ，) 。定义映射 ，：z r 卜】( + 1 ) c ，0 ( x ) ) = ( 磊，磊，毛一。) ， 其中磊= c ( 材”尹) = q “肌7 是c 的第h 个f o u r i _ e r 系数易得 ，( 口( 工) 十6 0 ) ) = ，p o ) ) 十，p ( 工) ) 若口( 工) ，6 ( j ) 是z r 上次数小于栉的多项 式，r a ( x ) b ( x ) = g ( x ) ( + 1 ) + r ( x ) ，d e g ( r ( x ) ) ，则 a ( u 。尹) b ( u 。尹- - - - p ( i g 。尹) 因此，y ( 口( x ) 6 ( x ) ) = y ( 口( 工) ) r ( b c x ) ) ，其中，( 五妒) ( 岛p ) = 五晶矿。 若，0 ( x ) ) = o ，则由反演公式可得，对任意o f 玎一1 ，q “7 = o 因此，钆= o 由此推出口o ) = o 于是，是个单射 构映射。口 又l c l = 兀( 2 。) 矿叶= 2 “。因此，是同 i | ， 结合定理2 3 3 与引理2 2 3 ，立即可以得到下面的计算结果 推论2 3 4z 2 上长为= 珂( 行是奇数) 的不同的负循环码的数目为( 2 口+ l ， 其中l ，l 表示集合，的阶。 2 4 多项式表不 现在，我们用多项式来刻画z 2 上长为n 的负循环码首先给出下面重要引 理 引理2 4 1 设z ( x ) 是r 在z r 【x 】中的极小多项式，定义如前，则 ( 1 ) z ( “”善) o ( m o d 2 ) ； ( 2 ) z ( ”。孝1 ) ( u - 1 ) ，但正( “。f ) 芒( ( 一1 ) 2 ) 。 证明 ( 1 ) 设v = 2 “1 ，则z ( x ) 可以表示成z ( x ) 2 x j x 。( r ) 因为z ( 工) 不是常数多项，所以不可能有z ( 工) = ，。( r ) + ，z ，( ，) ，否则，这个多项式 模2 可约，矛盾。同理，也不能有z jx ) + 一矿( r ) = o 。于是 z ( “”f 5 ) 2 阻( f “) 一o ( 善“) + 王。材帕善声z 。，( ，) 若工( “) - - - o ( m o c l 2 ) ，则比较不含的项可得f 是多项式 l ox ) + 一正2 ix ) 的解将其模2 ，可得 8 正，。( ，) + ，o ( ，) ；( g ( x ) ) 2 ( r o o d 2 ) ， 其中g ( x ) 是某个多项式，d e g ( g ) ) d e g ( z ( 工) ) 由此得到善5 是g ( x ) 的根， 矛盾因此， z ( “。r ) 暑o ( m o d 2 ) ( 2 ) 因为z ( 善) = z 。( o ”) + 班z ( f “) = o ，所以 z ( “。r ) = ( 扩一1 ) f 厶( ，) 。 x u l l u 嵋一1 ，l ，故z ( ”。f ) e ( u - 1 ) 假设z ( 材”善。) ( o 一1 ) 2 ) 。注意到 ( u - - 1 ) 2 = ( “2 - 1 ) 一2 0 1 ) 。将其模2 约化，则有 o e 正( 例2 l 基善p z ，胪) 懈，赢纵妒) j ( d ( 2 ，以1 ) ) ) 特别地，善p ，( ，) m 0 ( m o d 2 ) 观察到z ( r ) 中x 的所有指数都 胆儡敢j是儡敦 。 是偶数，因此， x 7 z ( r ) - - h ( x ) 2 ( r o o d 2 ) ，其中h ( x ) 是某一多项 式，d e g ( h ( x ) ) d e g ( f ，( x ) ) 。故i l ( 尸) ；o ( m o d 2 ) ，这与z ( z ) 的极小性相矛盾。 因此，z ( “。r ) ( ( ”一1 ) 2 ) 。 口 定理2 4 2 设c 是z 2 上长为n = 2 t n ( n 是奇数) 的负循环码若将c 看作是 z ，【工】( + 1 ) 中的理想，n c = ( 行 蜀o ) ) ，其中蜀( 是z ：【x 】中r 一1 的 、叫， 首一互素因子。 证明由定理2 3 3 ，c 同构于直和o 。c i ，其中q 是孵。( ，m j ) 中的理想 口( 甜。) ：口( x ) c 。对每个，定义毋( x ) 是使得e = ( ( “一1 ) 7 ) 的所有的极 小多项式的积。若口( x ) 是c = ( g ( x ) ) 的理想，则口( x ) = 6 ( x ) 岛o y ，其中6 ( 工) 是与邑( 工) 互素的多项式。 运用引理2 4 1 ，我们有 口( 群訾) = 6 ( “7 r ) 毋( 鼙訾) je q 。 口 推论2 4 3 若c 是z 2 上长为n = 2 t n ( 疗是奇数) 的负循环码，且 c = ( 巅 毋( 并) y ) ，其中岛( 工) 是z r 【x 】中r 一1 的首一互素因子，贝 j l c l = 箩， 、j 。”， 其中譬= ( 口一f ) d e g ( g , ( ：) ) 。 证明由定理2 3 3 ，c 的阶是兀l c l ，其中c 是孵。u ，m f ) 的理想，由集合 g ( “。) ：g ( x ) c 生成。注意到c l = ( ( “一1 ) 7 ) ，故g j ( 手) = o ，i c , 1 = 2 啊2 p 力 计算上面的积，即得结果。 口 9 2 5 对偶和自对偶 定义孵到吼的“共轭，映射一：篁q ：窆q 一，其中在吼中“一：甜一。显 然，这个映射可以拓展到飒。( 甜，研) 上我们定义h m t i 锄内积如下： 对 c ，；( c o ，c ：。) 识” ， = ( 哦，屯。) 吼”，( c ，d ，) ：艺q 万假设对 j - o o r 片一i ，q = c l 。一，4 = 正。，贝 妒( c ) = c ，伊( d ) = d ， 其中 c = ( c o 冉，q 一，q 1 o c o j ，c l - l ，q - l j ，气_ 2 l - l ，c l ，i ，巳一l - 1 ) z ；， d = ( 磊p ，磊o ，呔。 。，咴j ，反“，如l ，d 0 。，。，吃。) ez ； 引理2 5 1 概念定义如上，设仃表示z ；中的负循环移位， 表不- - 。r n 中 e u c l i d e a n 内积，则对所有o s j 2 k 一1 ，( c ，d ) = 0 当且仅当 仃哪( 妒( c ) ) 矿( d ) = o 。 证明( c ，d ) = o 等价于 喜( 如顶缸。) = 。 对所有的o s s 2 一1 ，比较两边矿的系数，( 1 ) 式等价于 即 h i ，矿1 。 r i 、 i c l j + h d 。一q 儡，| - 0 i l o lj - 0 - p “ ( 2 ) i d + h ) 九+ q 川4 。，l = 0 ， ( 3 ) i , - 0 j - o j = 2 。- h 其中下标j + h 模计算驴。等式( 3 ) 恰表明盯“( 妒( ，) ) 伊( ) = o 因此， ( c ，d ) = 0 当且仅当对所有的o j 2 - 1 ，仃可p ( ，) ) 伊( d ) = 0 口 设多表示p 的逆映射，运用引理2 5 1 ，我们得到下面 定理2 5 2 设c 是z ，上长为n = 2 n ( n 是奇数) 的负循环码，妒( c ) 是在妒映 射下它在坩中的象。则妒( c ) 上= ( c 1 ) ，其中在z ；中关于e u c l i d e a n 内积作对 偶，而在吼”中关于h e r m i t i a n 内积作对偶。 根据定理2 5 2 ，若c 和d 是吼上长为珂的“一常循环码，则c 和d 是对偶 的( 毛eh e r m i t i a n 内积下) 当且仅当伊( c ) 和妒( d ) 在z 芸是对偶的( 在e u c l i d e a n 内积下) 。 为了得到长为 ，的负循环码的对偶码，我们现在考虑吼”中h e r m i t i a n 内积 和离散的f o u r i e r 变换的系数之间的关系。 设于( ：) ：- i k z j i 和j ( ：) ：芝乏山矿分别是c 和d 的m a r t s 。n s 。i 。m o n 多项式，根据反演公式，对o s f 万一l ，q = 甜“吉孑( f ) 和西= “去孑( r ) 因此， 善q 乏2 专善弓侈) 五够) = 专善n - i ( 萎n - i 弓手呻 = i 。- x , z 丑f ” = 丢萎互云 引理2 5 3 若c = 2 0 1 ) ，) 9 t 。( 甜，小) ，0 i d e g g ，则( 厂( x ) + g ( 工) ) = 厂( 工) + 产7 嘶gx ) ； ( 2 ) ( ，( x ) g ( 工) ) = 厂( x ) g x ) 。 显然，f ( x ) 的根是，( x ) 相应根的倒数。下面我们给出负循环码对偶码的生成 多项式。 定理2 5 5 若c 是z 2 - 上长为的负循环码，且c = ( 兀2 a 毋( x ) 7 ) ，其中& o ) 是z 2 【工】中r 一1 的首一互素因子，则 c - ：( f i 西( z ) 妒州) ，且i c - i ：2 o 蚓蜀。 证明定义g j ( x ) 如定理2 4 2 。设q 表示蜀( 工) 的常数项，0 s f 2 k 4 。因为 g oc 工) g , ( x ) 目。( x ) = r 一1 ，所以q 。= 一1 故q 是z ：。中的逆元，且吩 是爵( j ) 的首项系数。设局( 工) = 坼矿( 工) ，其中吩是使得吩( x ) 是首一多项式的 z r 中的逆元注意到q = 町1 ，毡。= a 9 1 百1 a ，- i 。= 一1 因此， ( 工) 鱼( 工) b 。( 工) = ( “o u t 。) 盛( x ) g ：( x ) g 。( 工) = - - x 衄“小螗。似”+ 蛔和扣9 0 ( x - ! ) 蜀( x 1 ) 9 2 i 。( x “) = ( z ”一1 ) = x 。- 1 。 于是，吩( 工) 是z ：。卜】中，一l 的首一互素因子 设d ：( 赍n ( 工) 2 州) ，则d ：( 靠 西( j ) r 叫i ) 。 设q = g ( “矿) ：g ( 工) d ) 。若q = ( o 一1 ) ) ，则毋( ) = o ，由此得到 巧( 掌1 ) = o ，于是q ( f - - o 从而一( 工) 是使得c ，= ( ( 甜一1 ) 。) 的所有f “的极 小多项式的积，则g o ) = ，( x ) 厅j ) r 一，其中，( x ) 是与吩( x ) 互素的多项式。 于是，g ( 善“) = r ( 善”) 巧( 善”明如1 ( o 一1 ) 2 b 叫) ，但萑( o 一1 广州“) 。 因此，乜= ( 一1 ) 2 1 7 ) 。故对所有的f ，c 见一，= o 。根据 定理2 5 4 ，d = c