（应用数学专业论文）有限环上的重根循环码的若干问题的研究.pdf

有限环上重根码若干问题的研究 摘要 循环码是一类重要的线性码，目前发现的大部分线性码都可以归结于循环 码，如k e r d o e k 码和p e r p a r a t a i 马就是z 上的循环码。对有限环上的单根循环码的 研究已比较全面，但对重根循环码，由于x 8 一l 在环上的分解不唯一，因此循 环码的结构将变得比较复杂。本文主要研究了环f + “f 和更一般的有限环z ， 一 ， 上重根循环码结构，并讨论了环职+ 幔f v 2 = v 1 上码的性质。主要内容分为以 下几个方面： 第一，给出了环职+ ”e 上长度为2 n 的重根循环码及其对偶码的结构，进一 步讨论了这类重根循环码与单根循环码二者之间的极j x l e e 重量关系。 第二，利用离散傅立叶变换，研究了环z ：上长度为p 丹的重根循环码的结 构及其计数问题。 第三，通过在f 2 上的一组对偶基，定义了环e + 嘎( v 2 = v ) 到其子环 k 、e ，和玟，+ 峨上的g r a y 映射，其中m = 糟，并给出环e + v f ，上码的相关 结论。 关键词：重根循环码；极小l e e 重量；g r a y 映射：离散傅立叶变换：对偶码 r e s e a r c ho ns o m ep r o b l e m so fr e p e a t e d - r o o tc y c l i cc o d e s o v e rf i n i t er i n g s a b s t r a c t c y c l i cc o d e sa r ea ni m p o r t a n tc l a s so fl i n e a rc o d e s m o s tg o o dl i n e a rc o d e s c a na t t r i b u t et oc y c l i cc o d e ss u c ha st h ek e r d o c kc o d e sa n dp r e p a r a t ac o d e sw h i c h a r et h ec y c l i cc o d e so v e rz 4 r i n g t h e r ea r ec o m p r e h e n s i v er e s e a r c h so nt h e s i m p l er o o tc y c l i cc o d e s b u ti t b e c o m e sd i f f i c u l tt or e p e a t e d r o o tc y c l i cc o d e s ， b e c a u s ex ”一1c a nn o tf a c t o ru n i q u e l yo v e raf i n i t er i n gw h e n 珂i sn o tp r i m et o t h ec h a r a c t e r i s t i co ft h er e s i d u ef i e l do ft h er i n g i nt h i sd i s s e r t a t i o n ，w es t u d y r e p e a t e d - r o o tc y c l i c c o d e so v e rt h ef i n i t e r i n g sf 2 + ”f 2 a n d z t h er e s u l t s a b o u tc o d e so v e r 艮+ 以a r ea l s og i v e n t h ed e t a i l sa r eg i v e na sf o l l o w s ： 1 b yt h ed i s c r e t ef o u r i e rt r a n s f o r m s w eg e tt h es t r u c t u r eo ft h er e p e a t e d r o o t c y c l i cc o d e so fl c a g t h2 no v e rf + “r a n dt h e i rd u a lc o d e s t h er e l a t i o no f m i n i m u ml e e w e i g h tb e t w e e nt h er e p e a t e d - r o o tc y c l i cc o d e sa n dt w os i m p l e r o o t c y c l i cc o d e si sg i v e n 2 w eo b t a i nt h es t r u c t u r eo ft h er e p e a t e d - r o o tc y c l i cc o d e so fl e n g t h p 再 o v e rz b yt h ed i s c r e t ef o u r i e rt r a n s f o r i l l s t h en u m b e ro ft h e s er e p e a t e d r o o t p c y c l i cc o d e si sa l s og i v e n 3 w ed e f i n eg r a ym a p sf r o m 艮+ v bt oi t ss u b r i n g s e ，e ，a n de ，+ v f ， f o rd i v i s o r sro fmw i t hr e s p e c tt oaf i x e dt r a c e - o r t h o g o n a lb a s i so f 凡o v e r f ，t h er e s u l t sa b o u tc o d e so v e r 取+ 以a r ea l s og i v e n k e y w o r d s ：r e p e a t e d - r o o tc y c l i cc o d e s ；m i n i m u ml e e w e i g h t ；g r a ym a p s ； d i s c r e t ef o u d e rt r a n s f o r m s ；d u a lc o d e s v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 盒8 b 王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意 学位论文作者签名：j i ：多。锒 签字魄砰钿多日 学位论文版权使用授权书 本学位论文作者完全了解金g 垦王些盍堂有关保留、使用学位论文的规定。有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金壁王些盔堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印，缩印或扫描等复制手 段保存，汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：三孓与露 签字吼啊年6 月6 日 学位论文作者毕业后去向： 工作单位： 通讯地址： i l l 导师 电话 邮编 致谢 光阴似箭，蓦然回首。三年的硕士生学习生涯即将结束这三年，可以说 是我人生的重要转折点和新的起点。在此期间，承蒙恩师朱士信教授对本人学 习的悉心指导，使我顺利地完成了学位课程的学习和硕士论文的研究工作。他 严谨的治学态度、执着的敬业精神将鞭策我不断地探求新的知识；他平易近人、 和蔼可亲的处世方式，让我明白如何去为人师，让我懂得如何去踏踏实实地工 作、堂堂正正地做人。在此，我对他表示深深地敬意和衷心的感谢! 同时，真诚感谢师兄妹的关心和帮助，在此一一表示感谢。 最后，感谢我的父母和丈夫陶有田在我研究生学习阶段对我提供的物质帮 助和精神鼓励。正是有了家人无私的帮助和奉献，我才能在研究生阶段全身心 地投入到学习之中。 v i 作者：王冬银 2 0 0 7 年5 月 第一章绪论 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 yo fc o m m u n i c a t i o n i lz j 中首次提 出了著名的有扰信道编码定理。继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 de 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 f e r r o r c o r r e c t i n gb i n a r yg r o u pc o d e s ) 【39 】一起构成了“代数 编码理论”的基础。无论是从外太空通信还是从消费电子产品都可以看到编码理 论的踪影。事实上，“a l g e b r a i cc o d i n gt h e o r yi sab r a n c ho fe n g i n e e r i n gw i t h r 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 rs c i e n c e ” 二进制码的起源可以追溯到1 7 世纪。当时英国伟大的哲学家f r a n c i sb a c o n 设计了一种称为b i l i t e r a r e i 码或叫做o m n i ap e ro m n i a 的包含五个字母的二进制 码方案。这种码首先由( t h e a d v a n c e m e n to f l e a r n i n g ( 1 6 0 5 年) 一书提及。之 后出于编译外交机密情报的需要，d ea u g m e t t i ss c e n t a r u m 于1 6 2 3 年出版了它 的详细内容。此后有三个人通过不同的渠道接触到了这一学科。第一个人是1 9 世纪早期的法国人j o s e p hm a r i ej a c q u a r d ，他设计了第一种孔式编码卡并将其 应用到织布行业中。另外两个人，一个是英国数学家g e o r g eb o o l e ，他的命题 演算代数学是现代计算机逻辑设计的基础；另一位是法国工程师e m i l eb a u d o t ， 他的循环序列码( 现在通常称之为g r a y 码，因为f r a n kg r a y 于1 9 5 3 年3 月1 7 日获得其专利) 在电信技术方面做出了重要的改进。这种码有着广泛的应用，例 如用它来解决河内塔问题，而且困扰人们3 0 之久的编码理论难题也是用它来解 决的1 9 1 。 我们来说一下这个难题的相关情况。在上世纪7 0 年代初，人们发现了一些 高效的二元非线性码，如k e r d o c k 码、p r e p a r a t a 码、n o r d s t r o m r o b i n s o n 码、 g o e t h a l s 码和d e l s a r t e g o e t h a l s 码 2 , 4 , 1 0 , 1 8 , 1 9 , 3 2 , 3 3 , 3 6 】。在长度相同、极小距离相 等的情况下，这些非线性码所包含的码字个数是现有线性码的两倍。它们不仅 有很好的纠错能力，而且也具有很好的结构，比如二进制非线性p r e p a r a t a 码和 k e r d o c k 码之间就有关系i p ( m ) l l k ( m ) i = 2 ”。许多研究者如m a c w i l l i a m s ，s l o a n e 等都努力去解释其中的奥秘，答案竟出人意料的简单1 9 9 4 年，h a m m o n s 等 人给出了这样的结论：k e r d o c k 码和p r e p a r a t a 码都是z 。上相互对偶的线性码， 同时观察到( z ”，l e e 距离) 和( z ，“，h a m m i n g 距离) 是保持等距的。这样困惑 人们已久的关系式l p ( m ) l l k ( m ) i = 2 2 “得到了解释。在此基础上，大量有关有限环， 特别是z 。环上码的论文不断涌现，文献【5 5 就汇集了大量有关z 。环上码的论文。 而1 9 7 0 年代早期关于模q 的整环上的码的论文较少，部分原因是零因子的出 现。这些码可以将诸如正交频分多路复用技术、相位调制频道技术等应用到如 b e n t 函数、变网格结构等其他不同领域。 循环码是一类重要的线性码而有限环尺上循环码结构研究的关键在于， 将循环码视为多项式环r t x l ( x ”一1 ) 的理想，其中n 是码的长度。因此多项式 z “一1 的分解式显得尤为重要当有限环只的特征p 与码长刀互素时，x 。一1 可 被唯一分解为有限个两两互素的基本不可约多项式之积。而当月的特征p 与码 长n 不互素时，石“一l 在盈上的分解不唯一，此时循环码的结构将变得非常复杂。 作为循环码推广的负循环码和常循环码的研究情况与循环码类似。 当( 2 ，再) = 1 时，环z 上长度为甩的循环码已得到了很好的研究【9 ，5 l - ”】。在码 长栉与剩余域豆的特征互素情形下，更一般的有限环z 、g a l o i s 环和链环r 上 的循环码也得到了研究p 2 瓦”】。 当码长n 与剩余域豆的特征不互素时，有限环r 上的循环码在近几年也受 到了人们的关注。这样的循环码通常称为重根循环码。g c a s t a g n o l i 、j l m a s s c y 、 p a s c h o e l l e r 和n v o ns e e m a n n 2 0 1 以及v a nl i n t t 2 8 1都研究过域上的重根循环 码。t a b u a l m b 和r o e h m k e 在 4 6 】中研究了环乙上长度为2 。的重根循环码。 b l a c k f o r d l 4 7 】利用离散傅立叶变换把z 上长度为2 肝的循环码转化为多项式环 z 。t u 】( u 2 一1 ) 上长度为疗的常循环码，从而对长度为2 n 的循环码给出了研究。 d i n h 和l 6 p e z p e r m o u t h 在【2 5 】中给出了环z ，上长度为2 的重根负循环码的结 构。在此基础上，2 0 0 5 年s t e v e n t d o u g h e r t y 和s a n l i n g 在【4 4 】中给出了环z 4 上偶长度的循环码的结构。在特征与码长n 不互索时，其它有限环职+ ”f 2 、z 。、 g a l o i s 环以及有限链环上的循环码、负循环码和常循环码还有待于研究。 1 2 本文的主要内容 本文主要研究有限环醍+ “f 2 以及z ：上重根循环码的相关问题，一共有五 章。文章首先介绍了循环码的研究背景和现状，然后重点研究了环f ，+ e 和更 一般的有限环z ：上重根循环码的结构，并给出了环e + v f 上码的相关结论。 主要分为如下几个方面： 第一，通过离散傅立叶变换，得出环e + “e 上长度为2 玎的重根循环码及其 对偶码的结构，同时也讨论了这类重根循环码与单根循环码二者之间的极小 l e e 重量关系。 第二，利用离散傅立叶变换，研究了环z ，上长度为p 栉的重根循环码的结 构及其计数问题。 第三，通过e 在e 上的一组对偶基，定义了环吒。+ v f 2 ( v 2 = v ) 到其子环 f 、b 和e ，+ v f ，上的g r a y 映射，其中m = 糟，并得出环f ，+ 峨上码的相关 结论。 这些内容的研究对进一步丰富有限环上纠错码理论及构造一些性能较好的 码都有一定的指导意义。 2 第二章呸+ “呸上长度为2 n ( n 为奇数) 的重根循环码 2 1 预备知识 设r 是有单位元的有限交换环。r 上长度为厅、大小为m 的码c 是科的一 个子集，c 中的元素称为码字。若c 是彤的一个子模，则称c 是r 上的一个线 性码。向量a = ( a o ，q ，n r _ 1 ) ，b - - ( b o ，6 i ，屯i ) e r 4 。定义e u c l i d e a n 内积为 口6 = a o b o + a l b l + + 4 吒i 。若口- b = 0 ，则称向量a , b 是正交的。对月上长为疗的 线性码c ，它的对偶码c 1 是指与c 的所有码字都正交的尺中n 维向量组成的集 合，即c 上= a a b = 0 ，所有b e c 。若c c 1 ，则码c 叫做自正交的：若 c = c 1 ，则称码c 是自对偶的。 设c 是r 上的线性码且口r 是一个单位，若v c - - - - ( c o ，q ，q 一。) c 都有 0 q ，岛，吒- i ，c o ) c ，则称码c 为a - 常循环码。当a = l 时，码c 称为循环码。 通常情形下，当码c 的长度n 与足的特征互素时，我们称c 为单根循环码：若n 与r 的特征不互素对，称c 为重根循环码。 映射； 矗”- r m ( x ”一l 、， ( c o ，c l ，乌一i ) 卜c o + c 1 r + c 2 肖2 + + 1 r 。川 使得r 上的循环码c 与r t x l i ( x 4 一1 ) 中的理想等价，从而循环码就转化为 r e x 】( x “一1 ) 的理想问题，多项式矿一l 在r x 】上的分解就是问题的关键所在。 当有限环r 的特征p 与码长盯互素时，x 。一l 可被唯一分解为有限个两两互素的 基本不可约多项式之积。而当r 的特征p 与码长狞不互素时，x 4 一l 在霆上的分 解不再是唯一的，此时循环码的结构将变得比较复杂。本章和第三章主要讨论 有限环上的重根循环码。 2 2 多项式表示 在这章中我们规定，l 都为奇数，记r = f 2 + f 2 ，贸= r p 】( 2 - i ) 。定义映 射：卯寸r “，即 y ( + t , o o j ，q + 6 l 国，口- i + 吃一i o j ) = ( a o ，a l9 1 1 i ，a n - l b o ，6 l ，吒一1 ) ， 则有 y ( 科口。1 + 吒- i m 】，a o + 6 0 国，口。一2 + 以2 c o ) = 妙( 以- i - i a n - l 脚，a o + 6 0 珊，吒一2 + 吃2 ) = 一i ，a o ，q ，4 。- 2 ，q l ，t , o ，一，瓯- 2 ) ， 易见r 2 4 中向量的一个循环移位对应于映射下孵4 的一个循环移位，从 而我们有下面定理。 定理2 1 设c 为锨上长度为月的g o 循环码，为上面定义的吼。专r 2 “的环 同构映射，则y ( c ) 为震上长度为2 n 的循环码。 易见，9 l 是一个有限的局部环。由h e n s e l s 引理知，x 4 一在吼 柳中可被 3 唯一地分解为x 。一珊= ，：正z ，其中z ( f = l ，2 ，r ) 是首一的两两互素的不可约 多项式。由中国剩余定理知： 虿n x xy 兰器。箦( 4 一m ) 一( 石) 。( z ) 。 下面我们主要研究环瓤x 】积) ，江o ，l ，。 首先我们来回顾一下【1 ，4 5 】中的g a l o i s 环。设h ( x ) 是r 上首一的用次基本 不可约多项式记g r ( u ，m ) = r x l ( h ( x ) ) ，则g r ( u ，m ) 是一个局部环，它的极大 理想为 ，且剩余域为艮取善= z + ( ( z ) ) ，则f 为h ( x ) 的根，且是2 4 一1 次本原单位根。记集合t 。= o 1 ，善，。善r 。2 ) ，从而任意五eg r ( u ，m ) 都有唯一的 越a d i e 表示：五= a + u b ，其中口，b t 。同时定义g r ( u ，搬) 的f r o b e n i u s 变换为 = a 2 + u b 2 ，从g r ( u ，m ) 到尺的广义迹为l ( 五) = 五+ 兄7 + + a 广。 下面我们定义扩环冠( ，m ) 为 心( ，州) = g r ( u ，肌) 【棚】( 国2 - 1 ) ， 易见心( ，1 ) = 巩且有蜀( c a ，m ) = g r ( u ，肌) 0c o g r ( u ，研) ，从而蜀( 由，埘) 中任意元 素a 都可唯一的写成五= a o + 口l 国，其中a o ，q g r ( u ，小) 。若五r 4 ( c o ，珊) ，记 互；五r o o d u 。下面我们来确定环咒( c o ，州) 的理想结构。 引理2 。2 ( 1 ) 兄( 峨小) 是一个局部环，它的极大理想为 ，且剩余域为k ( 2 ) 置( c o ，历) 的理想为 ， ， 或，u o ) + 。当，垡峨( 国，肼) 时，则 理想，模甜后的理想为，= ，从而有一l + u b i ，b t 。，则 。 由上可知r ( m ，m ) 的理想为 ， ， ， ， 和 ，其中t t 。 - 同样，我们可定义见( ，m ) 上的f r o b e n i u s 映射为( 凡+ 矗出) 7 = 矗7 + 7 国，定 义局( 珊，朋) 的广义迹为l ：墨( ，m ) 寸m ，l ( 五) = 2 + + + 一 为了方便，我们记m 为2 模盯的乘法阶，善心( c a ，m ) 为一次本原单位根，c l ( i ) 为包含i 的模n 的分圆陪集，记= p ( f ) | 。 定义2 1 设c 饵) “，则定义c 的离散傅立叶变换为向量 4 ( 磊，磊，乞。) r ( 戤m ) 。，其中磊= c ( m ) = c j m ，i = 0 ，l ，n - 1 ，定义c 的 i o m s 多项式为： ( z ) = z 易见毒e 日( c o ，m i ) ，且乞= 彳，i = 0 , i ，n - 1 ，其中下标模 。 引理2 3 ( 反演公式) 设c e r “，t ( z ) 为c 的m s 多项式，则 归l l c ，卜训，鲐一，1 ) 。吉( 地6 协一，矧- 1 ) ) j ， 其中“，表示分量乘积。 证明：设0 s f s 盯一1 。贝 幽n - ! ，2 n - !、 2 n - in - ! o ( ) = 错4 = l 勺m 矿= 勺7 善= n ( e , 0 2 + q ) ， i 卸 扣0 产0，i o f - o 因为埘2 = 1 ，从而= ：雹君薹，故彩1 丢。皓，) = c ，+ ( - o c t + 。，因此有 c 一5 f ，卜训，蛳“，1 ) 去( 弛，姑”) ) j 成立一 引理2 4 设口( z ) ，6 ( 幻r e x l ( x “一1 ) ，五( z ) ，j ；( z ) 分别为它们的m s 多项式， 则：( 1 ) a ( x ) + 6 ( 彳) 的m s 多项式为a ( z ) + 占( z ) ； ( 2 ) 口( x ) 6 ( x ) m o d ( x 2 “- 1 ) 的m s 多项式为占( z ) 占( z ) = 螭，其中“”表 示分量乘积； ( 3 ) 0 和1 的m s 多项式分别为0 和fz l ； 蜀 ( 4 ) x a ( x ) 的m s 多项式为脚a ( 孝“z ) 。 记a = ( 氐，毛，丸一。) r ( c o ，j 1 ) 。i 五：，= 衫 ，则a 对分量加法和乘法构成一个 环又因为对任意i e i ：有幺r ，) ，且色2 。由磊决定。从而有a 兰o k ，兄( 国i 鸭) ， 其中，为模甩的所有分圆陪集代表元的集合。 定理2 5 映射y ：足 硎( x “一1 ) 寸彳是一个环同构映射，其中 ，( 口( 栅= ( 磊，岛，屯一。) 证明：由引理2 4 知，是环同态的，又由引理2 3 知，是单射，下证，满射。 因为a ( f ) = ( 蝣“) r 4 ( c o ，1 ) ，则 口= ( ( 1 ，m ，l ，m ，1 ) 二( a ( 1 ) ，a ( f ) ，a ( 夕- 1 ) ) ) r “，从而，为满射。 我们知道，当托为奇数时，x ”一1 在r x 内可被唯一地分解为首一的基本 不可约多项式之积。设，( z ) r 【别是首一的，且，( ) 是z 一1 在g x 】内的基本 不可约因子，厂( 孝) = 0 ，则称f ( x ) 为在r 上的极小多项式。易知善。的极小多 项式是唯一的，且它是r 上以为根的次数最低的多项式。 引理2 6 设f j 是在研x 】上的极小多项式，则有 ( 1 ) 乃( 善7 ) om o d ( - 1 ) ； ( 2 ) f j i ( 蝣妒i = 0 ： ( 3 ) 设g ( x ) r 【棚是首一多项式且g = 乃+ u h ，其中d e g ( h ) d e g ( ) ，则有 g ( 国) i om o d ( m l + u t ) ，某t t 证明( 1 ) 记乃( x ) = 工，( x ) + 砑( z ) ，其中l j ，z ，是关于x 2 的多项式。由乃 是善的极小多项式可知，l j 9 7 ) o ，石，g ) o ，且 乃( d ，孝) = f o j g ) + 孝f , a ( f ) = ( 一1 ) 手，：j ( f ) ， 故有乃( 彩f 7 ) ；0m o d p 一1 ) 。 ( 2 ) 乃 ( n 喀) 2 = 乃9 2 ) = 乃皓7 ) 7 = o ( 3 ) 首先有砌 善) 0 r o o d ( c a 一1 ) ，否则 皓勺；0m o d u ，这与五为善7 的极 小多项式矛盾。从而有x , y ，z t 。，a o 使得 g ( “f 7 ) = 0 + l ) ( 国一1 ) + l 坛 = + 砂) - 1 ) + 鼢1 0 + 砂) ， 譬( 工+ l ) ( 国一1 ) + 贼q 】， 因此有g 掌7 ) ( 0 ) - - l + 必。) 。 定理2 7 设以为奇数，c 为r 上长度为2 n 的循环码，则c 形如： ( q ( x 2 ) 吒( x 2 ) 码( x 2 ) 占( x ) c ( x ) ，u a , ( x 2 ) a 2 ( x 2 ) 6 ( z ) ) ， 其中x “一l = 口i a 2 a 3 b c d ， a ia 2 ，a 3 ，b ，c ，d 首一且两两互素于r x 】上， 占( ) i b ( x ) r o o d u 。 证明 设j 为横行分圆陪集代表元的集合，则由定理2 5 知c 兰o 。，q ，其 中g 是墨( ，) 的理想，且g = 信( 国) i g ( 力c 。 下面我们来定义z ”一1 的首一因子q ，a 2 ，a 3 ，b ，c ，d ： 当g = ( 0 ) 时，z i a l ： 当c = ( “+ ”) 时，z i a 2 ： 当e = ( ) 时，z i 口3 ； 当e = ( “，一1 ) 时，石l c ； 当g = p 一1 + 埘) 时，某t 7 - 。时，z i b 。 则对于g ( x ) ( 口l ( z 2 ) 口2 ( x 2 ) a 3 ( x 2 ) 占( x ) c ( x ) ，u a i ( x 2 ) 吒( 肖2 ) 6 ( 彳) ) ，由引理2 6 可知，g ( 蝣) c ，i ，故定理获证。一 推论2 8 设，是2 模 的分圆陪集代表元的集合( 拧为奇数) ，历，为包含i 的 模栉分圆陪集的大小，则只上长度为2 n 的循环码个数为：丌( 5 + 2 “t ) 。 e ， 证明：r m ( x 2 “- 1 ) 兰a 兰o f e ，r 4 ( c o ，肌) ，而r 4 ( o d ，鸭) 中理想的个数为5 + 2 “， 其中2 ”个理想为形式 ，t e t ，则r 上长度为2 以的循环码个数为 兀( 5 + 2 ”) 。 e ， 6 推论2 9 设c 为r 上长度为2 n 的循环码，且 c = ( a d x 2 ) a 2 ( x 2 ) 呜2 ) 占c d c ( 幻，蚴僻2 ) a d x 2 ) 6 ( 棚) ， 其中q 口2 a ，b c d = x 。一1 ，占( x ) 首一且占( z ) = 8 ( 2 0 m o d u ，则c 的大小为4 2 b ， 其中毛= 2 d e g ( d ) + d e g ( b ) + d e g ( c ) ，岛= d e g ( a 2 ) + d e g ( a 3 ) + d e g ( c ) 。 证明 设，是模甩的所有分圆陪集代表元的集合，则l c l = 兀j q l ，其中 g = 信( 蟛) 1 9 ( 功c ) 是r ( o j ，啊) 的理想。 若c ：= ( 1 ) ，贝0 d g 。) = o c fj = 4 2 叶； 若c ：= ( ，国一1 ) ，则c 停) = o ic i = 4 2 叶； 若c i = 铷) ，则吒g 。) = o ，| c i i = 4 叶， 若q = ( w - l + u t ) ，则6 皓) = o k i - 铲； 若c ：= ( “功+ l ，) ，贝。口2 9 ) = o ，fc i = 2 一； 若c = ( o ) ，则q ) = 0 ，| c l i _ l ， 把它们进行乘积，即得结论。 _ 2 3 对偶码 在研究r 上长度为2 n 的循环码的对偶码之前，我们先来看几个引理。 引理2 1 0 若u ，矿是倪m ( x 。一) 的一循环码，则u 和v 对偶营( 【，) 和 ( 矿) 在r 2 4 中互为对偶。 证明 设即= ( a o + 6 0 缈，吒一l + 6 一i ) u ，v = ( + ，一l + 一i ) 矿，则 ( 垠v l = ( q h + 岛t ) + 国( q 茸+ 匆v ) = ( ( 1 f ) ，y 9 ) ) + ( ( ) ，盯y ( p ) ) ， 其中仃为n 次循环移位变换，故结论获证。 _ 由上述引理可知，要研究对偶码，只须找到吼上山循环码的对偶码即可。 引理2 1 1 设邸，p 吼4 ，舞( z ) = 玩z 和t ( z ) = 毫z 分别为y ( “) 和y ( p ) 的 m s 多项式，且岛吃“= o , o i n ，则( v = 0 。 证明由引理2 3 的反演公式可知虬= 二存( f ) ，o ，s n - 1 。因此 坼q = 砉女( 跏( f ) = 专委b - i ( 萎“- it c 乒叫， ( 薹吒c 手啮，) = 专d ，也“ ：去y 女；屯，n = 0 2 了己叶k ，2 易知在环兄 ，肼) 中，( o ) ，( “，一1 ) ，0 ) 和( d o - l + u t ) ( t t 。) 的最大零化因子 分别为( 1 ) ，u ( o + i t ) ，( ) 和( o 口- l + u t ) ，从而有： 引理2 1 2 设c 是r 上长度为2 的循环码，c 上为其对偶码，且c 兰o k ，g ， c 1 兰o m 口，则有 若= ( o ) ，则口= ( 1 ) ； 若g = ( ，珊一1 ) ，则q = ( 材国十甜) ； 若q 。= 0 ) ，则q = 0 ) ， 若g 。= ( o ) - l + u t ) ，则日= 和一1 + 埘) ； 若c = ( “+ ”) ，则q = ( “，c 0 - 1 ) ； 若g 。= ( 1 ) ，则d i = ( o ) 。 定理2 1 3 设c 是长度为2 n 的循环码，且 c ；( q ( x 2 ) a 2 ( x 2 ) 口3 2 ) 占( 柳c ( 如，u a , ( x 2 ) a d x 2 ) 6 ( x ) ) ， 则c 1 = ( ( x 2 ) c ( z 2 ) 西( x 2 ) 占+ ( x ) z ( 的，u d ( 石2 ) c ( x 2 ) 6 ( x ) ) 。 证明 我们设d = c 1 - - ( d i a 日，其中q = g ( r o 孝) l g ( x ) d ) ，同样设 c 兰o 。，q ，其中 q = g ( r o f 训g ( x ) c ) 。 若 g = ( n o ) + u ) ， 则 吒g “) s or o o d ( u ，o o - 1 ) ，对所有g c x ) d 。故见= ( “，c o - 1 ) 。用同样方法可 知对所有i 有c l d 。= 0 。由引理2 1 2 知d = c 1 。 推论2 1 4 设c 是r 上长度为2 的循环码，且c 兰o 。，g ，则c 是自对偶码 营c , g - f = o r l c l l c _ | _ 4 “，f i 。 推论2 1 5设c 是r 上长度为2 甩的循环码，且 c = ( q ( x 2 ) a 2 ( x 2 ) q ( x 2 ) 占( z ) c ( x ) ，u a , ( x 2 ) a 2 ( x 2 ) 6 ( ) ) ， 则c 是自对偶码 营q = d ，a 2 = c ，a 3 = 口：，且占= 占。 2 4 极小l e e 重量 f ( x ) r x 】，d e g ( f ) 丹，我们用( 厂) 。表示厂( x ) 在r t x l x ”- 1 ) 里产生的理 想，用( 厂) 表示，( 柳在r t x l ( x “一1 ) 里产生的理想。 置上长度为2 n 的循环码是个有重根的码，从而它的码字都可写成由长度为 疗的单根循环码的码字构成的连结结构。设c r “，则c 的m s 多项式可写成 五( z ) + 一1 ) 占( z ) ，其中a ( z ) ，占( z ) g r ( u ，删) 【z 】由反演公式可知，c 置换等价于 向量 一6 1 6 ) ，其中a , b 是长度为甩的向量且它们分别以a ( z ) 和占( z ) 为m s 多项 式。下面我们考虑向量a ，b 所对应的长度为以的循环码结构。 定理2 1 6 设c 是r 上长度为2 n 的循环码，且 c = ( q ( x 2 ) a d x 2 ) a d x 2 ) 6 ( x ) c ( x ) ，u a , ( x 2 ) 吒( x 2 ) 6 ( x ) ) ，其中口1 4 2 a 3 b c d = x ”- 1 ，则 c 中每个码字都具有形状( a - b t b ) ，其中口( 口l 口2 a 3 b c ，u a l 口2 6 ) 。，b ( 口i 口2 a 3 ，“q ) 证明 对任意c r “，设它的m s 多项式为占( z ) = 占( z ) + 一0 9 ( z ) ，有 t f = 盈，+ 一1 ) 度，。若是。的根，有a t ( f 7 ) = 0 。由引理2 6 可知对所有g ( x ) c 有g ( c o 善) = 0 。从而若a ( z ) + ( r o - 1 ) b ( z ) 是c 的m s 多项式，则必有赴；= 叠；= 0 ， 故口，6 他) 若是吒的根，有吒g ) = o ，则对所有g ( x ) c 有 g ( 国) ；om o d ( u o ) + u ) ，故a f = o ，毛；om o d u ，从而4 ( a 2 ) 。，6 ( 吒，“) 同理可知若r 是码的根，有口他，“) 。，6 ( a 3 ，”) 。若掌是b 的根，有口( 6 ) 。 若善是c ( x ) 的根，有口e ( g “) 。故由上面的分析可知，向量口，6 所在的循环码 分别为4e ( a l a 2 a 3 b c ，u a l a 2 b ) 。，6 ( a l a 2 a 3 ，“q ) 。_ 推论2 1 7 设c 是r 上长度为2 h 的循环码，且 c = ( a l ( x 2 ) 巳( x 2 ) 呜( x 2 ) 6 ( x ) f ( x ) ，u a l ( x 2 ) 啦( x 2 ) 6 ( z ) ) ， 其中a l a = a 3 b c d = x 。- 1 ，而，如分别为( a l a 2 a 3 b c ，u q a 2 b ) 。和( a l a z a 3 ，u a l ) 。的极小l e e - 重 量，则c 的极小l e e - 重量是m a n a , ，2 畋 证明 a - b 和6 都是( a j a 2 a j ，岫) 的码字，则吼 ( 4 6 1 6 ) 】2 d 2 。而当西= 0 时， r o ( a - b i 】吐，故c 的极小l e e 重量为r a i n 碱，2 吐，。一 定理 2 1 8设c 是足上长度为2 刀的循环码， 且 c = ( 口l ( x 2 ) a 2 ( x 2 ) 吩( x 2 ) 占( j ) c ( 工) ，u a , ( x 2 ) 呸( x 2 ) 6 ( x ) ) ，其中a l a 2 a 3 b c d = x 。- 1 ， 占( x ) 首一且6 ( x ) s 6 ( x ) r o o d u ，则c 中每个码字都有形式 一西1 6 ) ，其中 口q 吒吩施，u a l a 2 b ) 。，6 ( q 吃吗，嘲) 。，且a + u a ( b ) ( 6 ) ，其中仃是连续进行定 数次循环变换。 证明 设f 7 是b 的根，则对所有g ( ) c 有g ( 蟛) ( 国一l + “f o ) ，其中_ ，是 某个整数，0 _ ，n 一1 ( _ ，的值由b 确定) 。若a ( z ) + 一1 ) 占( z ) 是c 的m s 多项式， 则必有钆= “t ，善，故4 ( 6 ，”) 。又因为6 ( f - ，z ) 是矗经过，次循环平移后所得向 量的m s 多项式，从而口+ ”口( 6 ) ( 6 ) 。其中盯是连续进行胛一_ ，次循环平移变换， 而对于f 7 不是b 的根的情形，类似于定理2 1 6 的证明。 推论2 1 9设c 是r 上长度为2 ”的循环码，极小l e e 重量为d 且 c = ( 口l ( z 2 ) a 2 ( x 2 ) q ( z 2 ) 6 ( x ) c ( x ) ，u a 。( x 2 ) 口2 ( x 2 ) 6 ( z ) ) ，其中口l 口2 吗6 c d = x 。- 1 ， 5 ( x ) 首一且5 ( x ) z 6 ( x ) r o o d u ，则有 m i n 碱，2 d 2 d 蔓4 以， 其中西，吐分别为他吒q 6 c ，u a 。a 2 ) 。和似呸呜，蛔) 。的极小l e e 一重量，以是长度为行 的二进制码( - ) 的极小h a m m i n g - 重量。 证明 对于d 2 m i n d i ，2 d 2 的证明类似于推论2 1 7 ，但未必能达到最小值。 那是因为条件4 + “盯( 6 ) ( 6 ) 。的限制设6 = 圳，其中v 是佰) 。中极小重量码字， 有6 ( 口i a 2 q ，明) ，则( 6 1 6 ) c ，而吼【( 6 l6 ) 】= 4 以，故d s 4 力 9 第三章z ，上长度为p k n 的重根循环码 本章同样利用离散傅立叶变换，使得环z ，z 上长度为p b 的循环码等价于形 如g r ( p 2 ，朋) 陋】( ”，一1 ) ，o e j r ) 的扩环上理想直和， 并给出了扩环 g r ( p 2 ，历) m 】( “，一1 ) 的理想结构以及环z ，上长度为p k n 的循环码的结构和计 数问题。 3 1 基本结构 首先我们来看一些基本定义，若c 是环z ，上的码，则定义其剩余码和挠码 分别为勋s ( c ) = p 哗l 存在即q 使得v + p u c ) 和t o r ( c ) = 扣嘭i