（应用数学专业论文）关于循环码周期分布的研究.pdf

关于循环码周期分布的研究 摘要 纠错码的周期分布成为编码理论的一个新的研究方露。对纠错码匏周期分枢 问题，特别是循环码的周期分布问题的研究，有利于更好地了解循环码的结构，有利于 构造非线性循环等重码和循环置换码，有利于设计有良好特性的信号因此对它的研 究显然是有理论意义与实用价值的，已经引起了国内外编码与密码学者的一定 关注 本文在前人已有的工作基础之上，进一步研究了有限域和有限环上循环码 的周期分布问题，第一章综述了周期分布的研究现状与意义；第二章给出了全文 的预备知识；第三章分别研究了有限域疋上纠错码和常循环码的周期分布，并绘 出了计算公式；在第四章中，定义了有限环z 。上周期分布的概念，分别研究了 z 。和z 。上循环码的周期分布，并给出了计算公式；第五章研究了z 。上一类特殊 的循环码和其映射如下的象，比较这蘸类循环码周期分布之间的关系，此章建立了前 两章之间的一座桥梁；第六章对全文作了一个总结，并对未来可能的发展方向提出 了一些有待研究的问题。 码的重量分布和深度分布一直是编码理论的两个重要的研究方向，周期分 布的提出和研究进一步丰富了编码理论，又具有一定的实际意义 关键词：纠错码；循环码；对偶码；g r a y 映射；周期；周期分毒 r e s e a r c ho nt h ep e r i o dd i s t r i b u t i o no f c y c l i cc o d e s a b s t r a c t t h ep e r i o dd i s t r i b u t i o no f e r r o r c o r r e c t i n gc o d e s ，i nac l a s s i c a lc o d i n gt h e o r y i san e wi n v e s t i g a t i o nf i e l d r e s e a r c ho nt h ep e r i o dd i s t r i b u t i o no fc v c l i c c o d e s m u s tb ep r o p i t i o u st ok n o wt h es t r u c t u r eo fc y c l i cc o d e s ，t oc o n s t r u c tn o n l i n e a r c y c l i cc o n s t a n tw e i g h tc o d e sa n dc y c l i ct r a n s p o s i t i o n a lc o d e sa n dt od e s i g ns i g n a l w i t hg o o ds p e c i a l i t y s ot h es t u d yo fi ti s s i g n i f i c a n tf r o mb o t hat h e e r e t i c a la n da p r a c t i c a lv i e w p o i n t t h e r eh a sb e e nar e c e n tg r o w t ho fi n t e r e s ti nc o d e sw i t h r e s p e c tt ot h i sp e r i o dd i s t r i b u t i o no fc y c l i cc o d e s i n t h i sp a p e r ，t h ep e r i o dd i s t r i b u t i o no fc y c l i cc o d e so v e rf i n i t e f i e l d sa n d f i n i t er i n g si se x p l o r e da tt h eb a s eo fp r e v i o u sw o r k t h ef i r s tp a r t ，w eg i v et h e s u m m a r i z ef o rt h ec o n d i t i o na n dt h es i g n i f i c a n c e ；t h es e c o n dp a r t ，w e g i v et h e p r e p a r a t i o nk n o w l e d g eo ft h ew h o l ep a p e r ；t h e3 一r dp a r t ，t h ep e r i o dd i s t r i b u t i o no f c y c l i cc o d e sa n dc o n s t a n t c y c l i cc o d e so v e rcw e r es t u d i e dr e s p e c t i v e l y , a n d e x a c tc a l c u l a t i o nf o r m u l a sa r ee s t a b l i s h e dt o o t h e4 t hp a r t ，t h ed e f i n i t i o n o ft h e p e r i o dd i s t r i b u t i o no fc y c l i cc o d e so v e rz i so b t a i n e d ，t h ep e r i o dd i s t r i b u t i o no f c y c l i cc o d e s o v e rz 4 a n dz ，w e r es t u d i e dr e s p e c t i v e l y ，a n de x a c tc a l c u l a t i o n f o r m u l a sw e r ea l s oe s t a b l i s h e d ；t h e5 一t hp a r t ，ak i n do f s p e c i a lc y c l i cc o d e so v e rz 4a n d t h e i ri m a g e su n d e rt h em a p 舡w e r ei n t r o d u c e d ，t h e s ei m a g e sa r ea l lb i n a r yc y c l i cc o d e s o v e rt h ef i e l df 2 ，t h er e l a t i o no fp e r i o dd i s t r i b u t i o n sb e t w e e nt h e s et w ok i n d so fc y c l i c c o d e sw a sp r e s e n t e d ，b yt h i sp a r tab r i d g ew a se s t a b l i s hf r o m p a r t3t op a r t4 ：t h e6 t h p a r t ，w es u m m a r i z et h et o t a lp a p e r ，a n dp u tf o r w o r ds o m ep r o b l e m sw h i c hi n p e r h a p sd e v e l o p m e n td i r e c t i o ni nt h ef u t u r e t h ep e r i o dd i s t r i b u t i o na n dd e p t hd i s t r i b u t i o no fe r r o r c o r r e c t i n gc o d e sa r e b o t hi m p o r t a n ti n v e s t i g a t i o nf i e l d s i nac l a s s i c a lc o d i n gt h e o r y s ot h es t u d yo f p e r i o dd i s t r i b u t i o nw i l lh a v en o to n l yi m p o r t a n tt h e o r e t i c a ls i g n i f i c a n c et oe x p a n d t h ec o d i n gt h e o r yb u ta l s ov e r yi m p o r t a n tp r a c t i c a lv a l u e k e yw o r d s ：e r r o r c o r r e c t i n gc o d e ；c y c l i cc o d e ；g r a ym a p ；d u a lc o d e ；p e r i o d ； p e r i o dd i s t r i b u t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 金胆王些太堂或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 暴辩缈么夕 学位论文版权使用授权书 本学位论文作者完全了解盒起王些去堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金月里王些丕堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 签字日参盯伊v u 石辣l导师削乞 学位论文作者毕业后去向 工作单位： 通讯地址： 电话： 邮编： 致谢 三年的时闻稍纵酃逝，研究生阶段的学习生活虽然短暂，但却会影响着我的 一生。 首先，我要衷心地感谢我的硕士生导师朱士信教授几年来在学业上对我的谆 谆教导及在生活上给予我的关怀和帮助，朱老师严谨的治学态度，对学生热心指导、 精心培养的精神以及宽广的胸怀和豁达的处世之道使我终身难忘，他是我人生长、淫 中的一座永恒的灯塔，将指引我以后学习、生活和工作的方向值此论文完成之际，谨 向我敬爱的导师朱士信教授致以崇高的敬意和我最诚挚的谢意i ， 同时，我要衷心感谢在研究生学习期间所有给予我悉心关怀和热心帮助的 数学系老师，还要感谢师兄李平、童宏玺、开晓山和施敏加等对我的关心和学业 上的帮助，感谢几年来与我朝夕相处的同学们，他们是张道福、许和乾、陈安顺、 姜光峰和孙琳，与他们的讨论开拓了我的思路，使我受益菲浅。 另外，我还要感谢我的父母、二舅、二舅妈和姐姐，在我研究生学习阶段对 我提供的物质帮助和精神鼓励正是亲人的默默付出和全力支持，无私的帮助和 奉献，才使我在研究生阶段全身心的投入到学习之中，才使我能够顺利完成学业， 在此表示我由衷的感谢 最后，还要感谢审阅硕士论文和出席硕士论文答辩会的各位专家学者，感谢 他们在酉忙中给予批评指正。 作者：宛金龙 2 0 0 8 年5 月2 8 霸 第一章绪论 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 ，【l 】 中首次提出了著名的有扰信道编码定理，开创了纠错码理论的研究方向，奠定了 纠错码理论的基石根据s h a n n o n 的思想，h a m m i n g 2 1 、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 ) 【3 5 1 、m a s s e y 6 - 8 1 、m a c w i l l i a m s 9 - 1 1 1 、g o p p a 【1 2 ，l3 1 、n e c h a e v 1 4 、 冯贵良 1 5 , 1 6 等纠错码理论专家先后给出了一系列设计好码和有效译码的方法 而后，纠错码受到了越来越多的通信和数学工作者，特别是数学家的重视，使纠错 码无论在理论上还是在实际中都得到飞速发展8 0 年代末，编码理论中的一个突 破性的进展是h a m m o n s 等人证明了一些高效的二元非线性码，如p r e p a r a t a 码、 k e r d o c k 码等，可视为环乙上循环码在g r a y 映射下的像，从而使环z 4 乃至更一般 的有限环上纠错码理论的研究进入一个全新方向 纠错码的重量分布是代数编码理论中的一个重要课题【1 7 - 1 9 1 它其实是一个码字计 数问题，即求出码中重量为f 的码字个数该课题历史悠久，成果丰富而遗留问题也很多 周期分布是与重量分布相似的另一类计数问题，其实质就是求出纠错码中最小周期为 为f 的码字个数码的周期分布是一个新参数，但它并不是凭空提出来的，也不是毫无实 用价值8 0 年代末国外学者n g u y e n 就发现【2 0 】利用r e e d - - s o l o m o n 码中的无内周期码字 可以造出一类新的具有良好相关特性并且在序列密码中有用的密钥流序列但是在 n g u y e n 的构造过程中就需要解决如下两个问题：r - s 码中是否真的存在着无内周期的 码字? 如果存在，那么这样的码字又有多少个? 众所周知循环码具有独特的性质，即它的码字按循环等价分为若干个互不相交的 等价类b ，j = 1 , 2 ，3 ，( 码字c 和d 彼此等价意味着c = s 7 d 对某个非负整数r 成立) ，且每 个等价类b ，的容量ib ，i 刚好就是该等价类中所含码字的最小周期于是周期分布 鼻，1 f 刀) 与等价类容量lb ，l 之间满足只= fb ，i ，可见周期分布对揭示循环码的 i 乃。i = 。1 。 内容结构特征是很有价值的，由上等式和周期分布的定义可得到周期分布 只，1 f r 1 ) 打 的两个简单性质：( 口) 只= ci ，( 6 ) fi 鼻上面n g u y e n 在构造过程中面临的两个问题的 百 实质就是要确定r s 码的周期分布 只，1 f 刀) 中的丑，这已经在文献 2 1 】中得到了解 决 在文献 2 1 d f l ，杨义先教授很好的解决- r n g u y e n 在构造密钥流序列过程中所面临 的两个问题，1 9 9 2 年后又给出了( 以，k ，d ) 纠错码的周期分布 只，1 f 1 1 ) 的概念和它的 实际背景，接着从周期分布的定义出发求出了r - s 码，扩充r s 码和一般循环码的周期 分布精确公式【2 2 之3 1 记r ( 七，厂( 工) ) 为g f ( q ) x 】中次数不超过k 一1 且能被多项式f ( x ) 整 除的多项式的个数则g f ( q ) 中g ( x ) 为生成多项式( 校验多项式为h ( x ) ) 的( 刀，k ，d ) 循 环码的周期分布为： 只= w ( k ，i ) 一w ( k ，i - 1 ) ，1 i 刀 其中函数w ( a ，) ( 1 r n ) 定义为 w ( k ，) = ( 一1 ) ”1t k ，l c m 办( x )1 7 z ( x ) g c d ( h ( x ) ，工 一1 ) g c d ( h ( x ) ，石屯一1 ) ，面筹两】) 注：( 1 ) 函数t ( k ，厂( x ) ) = g 扣吲m ) ) ，这里d e g ( 厂( x ) ) 表示多项式f ( x ) 的次数； ( 2 ) g c d ( ，) 和l c m ( ，) 分别表示最大公因式和最小公倍式 不难看出在文献 2 2 ，2 3 d p 确给出了一般循环码周期分布的表达式，但该式过于复 杂，寻找一个更简洁而具体的表达式显然是一个有价值的课题1 9 9 6 年符方伟教授在文 献【2 2 ，2 3 】的基础上进一步分析了循环码周期分布的性质，从凹( g ) 上【拧，k 】循环码c 的 校验多项式h ( x ) 的分解出发，给出了循环码c 周期分布新的计算方法和公式【2 4 1 若c 为 g f ( q ) l z n ，k 循环码，校验多项式h ( x ) = 啊( x ) ( x ) h 。( x ) ，这里( x ) 为g f ( q ) 上互 不相同的不可约多项式，d e g ( h , ) = 墨，r ( 吃) = ( r ( 曩) 表示g f ( q ) _ l 多项式啊的周期，即 能使i 。- 1 ) 成立的最小正整数e ) ，1 f m ，令k = j l + j 2 + j 。，则c 的周期分布为： 山 h ，= q “”， 1 ，以 文 2 4 中，在给出循环码c 周期分布新的计算方法和公式后，还进一步讨论了一些熟 知循环码的周期分布问题，例如g f ( q ) 上m ，k 】r - s 码 1 9 9 7 年，李超教授又在文 2 4 】的基础上，进一步分析循环码的周期分布特点，给出 循环码的周期分布与其对偶码的周期分布之间内在联系，并确定了一般循环码及其对 偶码内无内周期码字的精确计数公式【2 5 】在文e 2 5 中有下列两个重要结论： ( 1 ) 如果 ( z ) 是g f ( q ) 上胁，k 】循环码c 的校验多项式，则码c 的周期分布 e ，1 i n ) 和最小周期分布 只，1 is 以) 为： h ，= g d c 8 f 8 c d 【6 ( 。) 一1 i l 1 ，刀 e = ) g 蚓酬“d 一1 1 l t n ( 2 ) 为g f ( g ) 上 n ，k 卜循环码，校验多项式为办( 功，这里乃( x ) 10 ”一1 ) ，d e g h ( x ) = k ， 如果h ( x ) 中含有属于4 的不可约因式的个数为q ，( 1 i m ) ，则 ( a ) c 中无内周期码字的数目为： 伽喜c 旁胁饥； ( b ) c 上中无内周期码字的数目为： 瓦= 喜峙，盟毗 2 1 2 本文的主要内容 近几十年来，码的各种重量分布一直是编码理论的一个重要研究方向无论 是域上还是环上的编码理论，利用线性码的码字的各种重量分布研究其对偶码 的相应的重量分稚都是很有意义的，重量分布其实是一个码字计数阍题，即求出码 中重量为f 的码字个数该课题历史悠久，成果丰富而遗留问题也很多周期分布是与重 量分布相似的另一类计数问题，其实质就是求出纠错码中最小周期为为f 的码字个数 基前，国内许多学者对予有限域g f ( q ) 上纠错码周期分布闻题的研究已经取得了一 些可喜成果【2 l 川j 8 0 年代末，编码理论中的一个突破性的进展是h a m m o n s 等人证 明了一些高效的二元非线性码，如p r e p a r a t a 码、k e r d o c k 码等，可视为环z 4 上循 环码在g r a y 映射下的像，从丽使环乙乃至受一般的有限环上纠错码理论的研究 进入一个全新方向所以随着环乞上纠错码的研究和深入，我们有必要讨论环乙上 循环码的周期分布问题本文主要是利用代数的基本原理和方法对有限域e 和有 限环上z 。上循环码码字属期闻题加以研究。箕孛主要研究各种循环码的周期分衣。 如上所述，本文主要在前人已有的工作基础之上，进一步研究了有限域和有限环 上循环码的结构、性质和周期分布问题，具体内容如下： ( 1 ) 讨论了有限域g f ( q ) 上码长为n ( ( 箨，譬) = 1 ) 的戈一常循环码相关性质，揭示了 a 一常循环码的周期分布及其对偶码的周期分布的关系，并给出了精确计算公式 ( 2 ) 讨论了有限环乙上码长为奇数n ( n 3 ) 的循环码的性质，揭示了该类循环码 的属裳分布及其对偶码的属期分布的关系，给出了精确计算公式，定义了溺耢分布多项 式以便更好的展现循环码的周期分布状态，并把有限环乙上的相关结论推广到有限环 z 矿上 ( 3 ) 最后研究了z 4 上一类特殊的循环码和其映射秘下的二元象，此二元象为 g f ( 2 ) 上重搬循环码，结合( 1 ) 、( 2 ) 中的相关结论和文献【2 6 】中的知识，给出了它们的精 确计算公式，并比较了这两类循环码周期分布之间的关系，此内容建立了( 1 ) 和( 2 ) 之间的 一座桥梁 码的周期分布是与其重量分毒相似的另一类计数阋题，它的提如和研究进一步 丰富了编码理论，而且研究循环码的周期分布有利于更好地了解循环码的结构，有利 于构造非线性循环等重码和循环置换码贸，有利于设计有良好特性的信号箨司既具有理 论意义又具有一定的实际意义。 3 第二章预备知识 2 1 线性码和循环码 在本文中记曩= g f ( q ) 表示具有g 个元素的有限域，其中拿是一个素数的幂 2 1 1 线性码的定义和一般性质 定义2 1 1 1 称乓上刀维线性空间露中的一个线性子空间c 为f 上的一个。 线性码。 如果这个线性予空闻的维数是k ，则称c 是一个【静，k 】线性码，捍是码长，k 是 码的维数称任一长为胛的向量x 一( 而，x 2 ，) 蠛碍为碍中的一个字，若x c ，则 称x 为【栉，k 】线性码c 的一个码字 称震一k n 力一个【嚣，k 】线性码e 的码率，它表示了e 中信息位在码字率所占 的比重r 是衡量线性码有效性的一个基本参数 定义2 1 1 2 设c 是一个忉，k 】线性码，工= 0 q ，x 2 ，毛) 联c ，称码字x 中不为o 的分量的个数为它的h a m m i n g 重量，用w ( 曲表承即： 以力爿 薯c | x j 0 ， = l ，2 ，撵 | 定义2 1 1 3 设c 是一个陬k 】线性码，x = ( 一，x 2 ，靠) ，y = ( m ，儿，以) c ， 称d ( x ，y ) 黑w ( x - y ) 为c 中码字x 和y 的h a m m i n g 距离 定义2 1 1 。4 在一个【硌k 】线性码c 中，将任意两个不圊的码字之闻h a m m i n g 距离的最小值称为c 的最小h a m m i n g 距离d ，简称为最小距离，即 d = m i n d ( x ，j ，) iv x ，y 岜c ，x y ) 一个【，l ，k 】线性码c 的最小距离d 是c 的另一个重要的参数，它表明了线性 码c 抗干扰能力的大小。 下面的定理说明了一个【n , k 】线性码c 中的最小h a m m i n g 距离d 与纠错能 力的关系 定理2 1 。1 1e l l 】对任一阮k 】线性码c ，若要在码字内： ( 1 ) 检测8 个睫机错误，则要求码的最小h a m m i n g 距离d e + l ； ( 2 ) 纠正，个随机错误，则要求码的最小h a m m i n g 距离d 2 t 十1 ； ( 3 ) 纠正，个随机错误，同时检测e q 0 个错误，则要求d h e + 1 ； ( 4 ) 纠正f 个错误和p 个删除，则要求d f + 2 p + l 。 因此今后也经常用【稳，k ，棚表示一个长为辫维数是k 最小( h a m m i n g ) 距离为 d 的线性码，而用( 殇m ，d ) 表示一个长为刀码字个数为m 最小( h a m m i n g ) 距离 为d 的非线性码对于一个【，l ，k ，d 】线性码，若码字 x = ( 鼍，毪，东) ，y = ( 麓，魏，魏) e ，则由线性窆闯的封翔性可知x + y c ，登有 d ( x ，力= w ( x + y ) 因此，一个翻，k ，明线性码c 的最小h a m m i n g 距离必等于码c 中 的最小h a m m i n g 重量，由此可得知下定理 定理2 1 1 2 f “】一个 嚣，k ，胡线性码c 的最小h a m m i n g 距离等于c 中非零码 字的最小h a m m i n g 重量。即 4 d = m i n w ( x ) i 坛c ，x o ) 关予一个【雅，k ，d 】线性码c 的最小h a m m i n g 距离d 还有如下非常重要的一个 定理。 定理2 1 1 3 】( s i n g l e t o n 边界) 设c 是一个 以，k ，d 】线性码，则：d 珂一k + 1 2 1 2 线性码的校验矩阵与生成矩阵 设e 是只上的一个i n ，k 】线性码，c 的码字共有g 个。 如果设q = ( q l ，q 2 ，c i 。) ，乞然( ，锄，) ，吼= ( ，& 2 ，) 颤c 是只上 的露个线性无关的码字；那么c 1 ，岛，c k 构成线性码c 的一组基，由它可以生成线 性鹦c 中矿个码字。即对于c 中的每一个码字x = ( 薯，憨，而) ，总存在k 个系数 a z ，a 29 ep a k ，其中q 仨c ，使得x = q q + a 2 c 2 + a k c k 即 x ：( 为，毪，酩) ：( 矗，吒，龟) | 龟t q 2q 。 吃。 龟l 取2 = ( q ，岛，吼) g 显然g 是一个露栉阶矩阵 定义2 1 2 1 称上述矩阵g 为线性码c 的一个生成矩阵 设算= ( 而，x 2 ，毛) 麟c ，考虑矩阵方程g x 丁= 0 因为生成矩阵g 的秩是k ，方程 的所有解构成碍的n - k 维解空阉，设穗= 编。，毳：，磊。) ，趣= ( k ，h 2 2 ，嘎。) ， ，恁砖= ( 吃- k , l 吃吨2 ，h n - k , n ) 是矩阵方程g x r = o 的线性无关的一组解。则对每一 个x = ( 五，x 2 ，毛) 有：x c 当且仅当 f 囊， 曩： h x t = 吆 i 墨一 k _ 穗一硝魂4 。2 壤。一 ；1 = o ， 刊 即又可表示为x c h x r = 0 。 定义2 1 2 2 称上述矩阵日是线性码c 的一个校验矩阵 定理2 1 2 1 设c 是一个【玎，k ，棚线性码，日是它的校验矩阵，则嚣的侄何d - 1 列都是线性无关的，且存在d 列线性相关，反之亦然 定义2 1 2 3 设c 是一个【殇意，棚线性码，如果由c 构成的线性空间的一个子 集p 是霹的r o r k ) 维子空间，则称d 是线性码c 的一个，维子码 2 。1 。3 线性码的对偶码及其重量分布 设搿= ( 毛，x z ，矗) ，j ，= ( m ，儿，儿) 毛露，x 和y 的欧氏内积定义为 x y = 而乃+ 恐y 2 + + 耽 定义2 。1 。3 。l 设c 是一个【嚣，k ，d 】线性码，则它的对偶码为 c 上= 秒碍l x y = o ，v x e c 5 显然( c 上) 上= c ，如果c 的生成矩阵是g ，校验矩阵为h ，则c 上生成矩阵为日， 校验矩阵为g 定义2 1 3 2 设c 是一个i n ，七】线性码，令4 表示c 中h a m m i n g 重量等于f 的 码字个数，我们称下面的序列 4 ，4 ，4 i ) 为c 的h a m m i n g 重量分布( 或h a m m i n g 权分布) 定义2 1 3 3 码c 的h a m m i n g 重量分布计数器是指 w c ( x ，y ) = 4 矿川y - - e x ”吣y 呻 j | ：o c c - c 2 1 4 循环码的定义及其生成多项式和生成矩阵 定义2 1 4 1 c 为石上码长为挖的线性码，如果当( c oc l ，一，c 州) 是c 中的码字 时，( c n - ic 。，c l ”，c 柚) 也是c 中的码字，那么c 就叫( c 上码长为刀的) 循环码 e q 上长度为，z 的循环码c ，经过从”到 工】 ”一1 ) 的同构映射，即 ( c o ，q ，c h 1 ) jc o + c l x , + + c n - i x “_ 1 记，( c ) = c o + c i x + + c n _ 1 x ”1l ( c o ，c l ，c 川) c ) ( 码c 的多项式代表) ，则定义 2 1 4 1 等价于 定义2 1 4 1 c 为上码长为，z 的线性码，如果c o + c l x + + c 川x ”1 x ( c ) ， 都有x ( c o + c l x + + q l x 卜1 ) ( c ) 成立，那么c 就叫循环码 注2 1 4 1 今后将不再区分c 与，( c ) 定理2 1 4 1 【36 j 设c 为e 上码长为疗的循环码令 ，( c ) = c o + c l 工+ + c n _ i x ”_ 1l ( c o ，c i ，c 。一1 ) c ) ， 那么i ( c ) 是环【x 】o ”- 1 ) 中的一个理想设g ) 是i ( c ) 中任意一个次数最低的非。 多项式，那么1 ( c ) 是由g ( x ) 生成的理想且g ( x ) i ( x ”一1 ) 更设d e g ( g ( x ) ) = i - - k ，那么 ( ，q ，c 剃) c ，当且仅当有一个e 上的次数小于k 的多项式h ( x ) 存在使 c o + t t l x + + c n _ i x ”一= h ( x ) g ( x ) 写 一 g ( x ) = g o + g l x + 9 2 x 2 + + g 一t x “一， g o g n i 0 ， 那么k r l 矩阵 g =k 行 就是c 的一个生成矩阵，因此c 是个( 玎，k ) 码 显然，( c ) 的生成多项式，除差一个中的元素作为因子外，是唯一决定的我 6 o 枞g 譬 七 即 趾 & & 踟 舒 自岛 岛 o 们把，( c ) 的生成多项式叫做c 的生成多项式，也说c 是由它的生成多项式生成的 循环码因此定理2 1 4 1 有下面这个逆定理 定理2 1 4 2 【3 6 】设g ( x ) 是c m 中的一个多项式，而g ( x ) i ”一1 ) ，用( g ( x ) ) 表示 g ( x ) 在【x 】( x 一一1 ) 中生成的理想，即 ( g ( x ) ) = h ( x ) g ( x ) ld e g ( h ( x ) ) 刀一d e g ( g ( x ) ) ) ， 令 c = ( ，c 1 ，c n 1 ) l ( c 0c l ，c 。一1 ) 圪( c ) 而c o + c l 工+ + c 。一l x ”1 ( g ( x ) ) ) ，那 么c 为e 上一个码长为玎的循环码，它的信息位的个数等于万一d e g ( g ( x ) ) 定义2 1 4 2 设办( x ) = h o + h a x + h 2 x 2 + + 玩x 是i x 】中的一个多项式，则称 x 】中的多项式h ( x ) = x 七h o x ) = 以+ 以一i x + 吃一2 x 2 + + h l x 七- 1 + h o x 与厅( z ) 互反的 多项式 定理2 1 4 2 1 3 6 j 设g ( x ) 是c i x 】中的一个多项式，而g ( x ) io “一1 ) ，令 h ( x ) = ”一1 ) g ( x ) ，那么以 ( x ) 为生成多项式的循环码与以g ( x ) 为生成多项式的循环 码的对偶码等价更进一步，以g ( x ) 为生成多项式的循环码的对偶码恰好是以h ( x ) 的 互反多项式 ( z ) 为生成多项式的循环码 注2 1 4 2 如果把上述内容中的只改为z ，就得到了z 。上码长为r l 的循环码 的相关定义和定理【3 7 1 2 2 纠错码的周期分布和有限域c 上纠错码的周期分布定理 设c 为c 上一个纠错码，设c = ( c oc l ，一，c 川) c 是一个码字，s 为一个循环移位算 子，使s c = ( c n - ic o ，c l ，一，c 柚) 定义2 2 1设c c ，如果有正整数r ( o ，拧) 使得s 7 c = c ，那么r 为c 的一个周 期c 的所有周期中的最小者被称为c 的最小周期 注2 2 1 设c 为兄上一个纠错码，c c ，显然n 是c 的周期，若r 是c 的最小周期， 又有r l n 定义2 2 2 设c 为上一个纠错码，记 只爿 c ：c c ，c 的最小周期为f l ， 1 f 刀 那么就称集合亿，l 逛刀) 为该纠错码的( 最小) 周期分布显然只刊cl ；若c 是 f 鼻l 循环码，则f1 只，除此之外，周期分布 只，1 f o ，却l ，p 2 ，p 肼【x 】，其中p l ，p 2 ，p 。 是一组首1 互异的不可约多项式，使得厂在c i x 】中能唯一分解： f = a p i e t p 2 “p 。，其中a c ，p ， 0 ，1 f m 由定理3 1 1 ，若厂( 工) 是首1 多项式，则显然有下推论成立 推i k 3 1 1 设疋i x 】中任首1 多项对( x ) ，d e g f ( x ) o ，却。，p 2 ，p 。 z 】，其中 p 。，p 2 ，p 。是一首1 互异的不可约多项式组，使得厂在【x 】中能唯一分解： f = p l qp 2 屯p 。，其中q 0 ，l f m 由定理3 1 1 知，e 【x 】中非常数多项式都可唯一分解，由此即可定义i x 】中两多 项式的最大公约式和最小公倍式 9 定义3 1 4 设首1 多项式厂( x ) ，嚣( x ) i x 】，d e g f ( x ) ，d e g g ( x ) 0 ，易，p 2 ，是 x 】中一组首1 互异的不可约多项式，厂= p l q p 2 勺p 。，g = p l t t p 2 如p 。o ，其中 鬈，t o ，l m 。则称多项式是( 曲= p l 赶p 瓣k ( 麓= m i n ( e ，乓) ，l m ) 为多项式 厂( x ) 和g 轴) 的最大公因式，记h ( x ) = g o d f ( x ) ，g ( x ) 】。称多项式苫( x ) = p l 镪p 。萼- ( q ，= m a x ( ，) ，l f m ) 为多项对( 砷和g ( x ) 的最小公倍式，记s ( x ) = l c m f ( x ) ，g c x ) 】 。注3 1 1 设f ( x ) g 【x 】，i 己g c d f ( x ) ，l 】= l ，l c m f ( x ) ，l 】- ( ，g c d f ( x ) ，0 】= 八曲， l c m f ( x ) ，0 】= 0 。 由定义3 1 2 和3 1 4 ，有下定理成立 定理3 1 3 【3 8 】设多项式口( x ) ，6 ( x ) ec i x 】，口( x ) 与6 ( x ) 互素当且仅当 g e d a ( x ) ，6 ( x ) 】= 1 3 。2 疋上循环码及其对偶码的周期分布 前面2 2 节给出了几个定义和基本定理，下面将对疋上循环码及其对偶码的周期 分布进行研究 罨l 理3 2 。1 在上给定的多项式豁0 ) 囊0 ) 喾o ) 后，则i x 】中存在9 2 嘲”妨个阶数 不超过k - 1 的多项式y ( x ) 使得u ( x ) ly ( z ) ，记丁( 惫，甜( 功) = q k - 嘲。( 引 证明由定义3 1 1 知，“( x ) iy ( x ) 等价于3 r ( x ) c 【x 使得y ) = r ( x ) u ( x ) 其中 d e g r ( x ) 一d e g v ( x ) - d e g u ( x ) k - 1 - d e g u ( x ) ，而这样的r ( 力共有q 扣d o g ”) 个。证毕 设c 是f , t x ：i ( x 弹- 1 ) 中豹一码长为疆的循环码，其生成多项式为 g ( x ) ，d e gg ( x ) = n - k ，g ( x ) i ( x “- 1 ) ，记办( x ) = o ”- 1 ) g ( x ) ，则办( 曲的互反多项式h ( x ) 是 c 的对偶码c 上的生成多项式。 引理3 2 。2 在循环码e 中与信息多项式a ( x ) = y a ，x 相对应的码字e 具有周期f 磊 的充要条件是 口( z ) ( x 一1 ) m o d h ( x ) = 0 ( 1 ) n - ! 证明 ( x ) = g x = 口( 曲g o ) i = 0 c ( x ) x 7m o d ( x ”- 1 ) = 【a ( x ) x 7 9 ( x ) m o d ( x ”- 1 ) = 【a ( x ) x g ( x ) m o d g ( x ) h ( x ) 】 = 【d ( x ) x 7 m o dh ( x ) g ( x ) 由于码字多项式与信息多项式相互唯一确定，因此码字c 具有周期r 就等价于 a ( x ) g ( x ) 溉程露( 盖弦7 m o dh ( x ) g ( x ) ，又等价子a ( x ) a ( x ) x 7 m o dh ( x ) 证毕 在e 上的多项式中记：e ，垒 口( 并) ：d e g a ( x ) k - 1 ，并且信息多项式口( x ) 所对应的 玛字具有周期r 由引理3 2 2 a ( x ) ：d e g a ( x ) 七一1 ，h ( x ) l 口 ) 7 - 1 ) 显然 | h ，目tl ，1 r r 1 由定理3 1 2 和定义3 1 4 知g c d 【j j l ( x ) ，一l 】有意义，由定义3 1 4 知吾揣 与i 面瓦x r 聂- - 而1 互素，再由定理 3 l l可知a ( x ) la ( x ) 0 7 1 ) 等价于 1 0 吾热i 口( x ) ，于是利用弓l 理3 2 1 可得 ig ，i 刊e , i = r ( 七，三苫热) = g 如g i 鲥【k j ) 1 1 l r n ( 2 ) 由定理2 2 1 和( 2 ) 式，有下面定理 定理3 2 1 由g ( x ) ( g ( x ) | l z ( x ) = x ”一1 ) 生成的码长1 1 的循环码c 的周期分布 h i ，1 i 力) 和最小周期分布把，1 f 玎 分别为： h ，= g 血8 8 甜【6 ( 。一1 】l 1 ，刀 z = ( 吾) g 蚓鲫。肛1 1 1 ，l r r l t ( 3 ) ( 4 ) 由定理2 1 4 3 知上循环码c 的对偶码c 上也是上循环码，根据两个循环码生 成多项式之间的关系及定理3 2 1 ，有下面推论 推论3 2 1 由g ( x ) ( g ( x ) h ( x ) = x ”一1 ) 生成的码长为n 的循环码c 的对偶码c 上的 周期分布h f i 1 f 刀 和最小周期分布k 上，1 毽，z 分别为： h ，上= g d c g g c d 【g ( 。) 一1 】 1 ，刀 上= l t ( l ，) q 衄鲥