（应用数学专业论文）关于λ循环码的λ周期分布和广义λ周期分布.pdf

摘要 内容摘要：纠错码的周期分布成为编码理论的一个新的研究方向 自1 9 9 2 年杨义先教授提出纠错码的周期分布后，国内许多学者对纠错 码的周期分布问题展开探讨，特别是循环码的周期分布周期分布对 研究循环码的内容结构特征是很有价值的研究循环码的周期分布有 利于更好的对循环码的结构进行了解，有利于非线性等重码和循环 置换码的构造，有利于良好特性的信号的设计而有限域b 上入一循环 码进一步推广了循环码的概念，了解其内容结构特征有重要意义，这 就有必要研究其码字的周期特性本文在前人已有的工作基础上，定 义了有限域日上一个纠错码的入一周期分布和广义入周期分布，证明了 它们与f q 上坌q 错码的周期分布和广义周期分布具有类似的性质，还 分别找出了循环码和a 一循环码具有入一周期的充要条件，并给出了有限 域f q 上码长为礼( ( 扎，q ) = 1 ) 的a 一循环码的a 周期分布与最小入一周期分 布精确的计算公式，推广了文献中已有的关于r 上纠错码周期分布和 广义周期分布的一些结果 关键词：x 循环码，入周期分布，广义a 一周期分布 ab s t r a c t c o n t e n t ：t h ep e r i o dd i s t r i b u t i o n so fe r r o r - c o r r e c t i n gc o d e s ，i nt h e c 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 s i n c ep r o f e s s o ry a n g y i - x i a np r o p o s e dt h ep e r i o dd 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 si n 1 9 9 2 ，m a n yd o m e s t i cs c h o l a r sh a v ep r o b e dt h ep e r i o dd i s t r i b u t i o n s o fe r r o r - c o r r e c t i n gc o d e s ，e s p e c i a l l yt h ep e r i o dd i s t r i b u t i o n so fc y c l i c c o d e s t h ep e r i o dd i s t r i b u t i o no fa c y c l i cc o d ei sv a l u a b l ef o rt h ec o n - t e n to ft h ec y c l i cc o d e 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 n so fc y c l i c c o d e sm 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 o c o n s t r u c tn o n l i n e a rc 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 lw i t hg o o ds p e c i a l i t y a c y c l i c c o d e so v e rt h ef i n i t ef i e l d 日i st h ep r o m o t i o no ft h ec o n c e p to fc y c l i c c o d e s u n d e r s t a n d i n gs t r u c t u r e so fa c y c l i cc o d e si sv e r yi m p o r t a n t s o i t i sn e c e s s a r yt os t u d yp e r i o ds t r u c t u r e so f 入一c y c l i cc o d e s i nt h i sp a - p e r w ed e f i n et h ea p e r i o dd i s t r i b u t i o na n dt h eg e n e r a l 入一p e r i o dd 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 so v e rf i n i t ef i e l dro nt h eb a s i so f p r e v i o u sw o r k ，a n ds h o wt h a tt h e yh a v es o m ep r o p e r t i e sw h i c ha r ea n a l - o g o u si ns o m er e s p e c t st op r o p e r t i e so ft h ep e r i o dd i s t r i b u t i o na n dt h e g e n e r a lp e r i o dd 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 so v e r 日i ti sf o u n d t h a tt h en 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 n sw h i c hc y c l i cc o d e sa n d 入一 c y c l i cc o d e sh a v e 入一p e r i o dd i s t r i b u t i o nr e s p e c t i v e l y w ea l s og i v et h e e x a c tc a l c u l a t i o nf o r m u l a so f 入一p e r i o dd i s t r i b u t i o na n dt h es m a l l e s t a - p e r i o dd i s t r i b u t i o nw h i c h 入一c y c l i cc o d e sh a v el e n g t hn ( ( n ，q ) = 1 ) o v e r 日，a n dg e n e r a l i z et h er e s u l t sc o n t a i n e di nt h er e f e r e n c el i t e r a t u r e s a b o u tt h ep e r i o dd i s t r i b u t i o na n dt h eg e n e r a lp 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 so v e r 日 k e yw o r d s ：a - c y c l i cc o d e s ，a p e r i o dd i s t r i b u t i o n ，g e n e r a l 入一p e r i o dd i s - t r i b u t i o n 学位论文独创性声明 本人承诺：所呈交的学位论文是本人在导师指导下所取得的研究成果。论文中除特 别加以标注和致谢的地方外，不包含他人和其他机构已经撰写或发表过的研究成果，其 他同志的研究成果对本人的启示和所提供的帮助，均已在论文中做了明确的声明并表示 谢意。 学位论文作者躲 捌 学位论文版权的使用授权书 本学位论文作者完全了解辽宁师范大学有关保留、使用学位论文的规定，及学校有 权保留并向国家有关部门或机构送交复印件或磁盘，允许论文被查阅和借阅。本文授权 辽宁师范大学，可以将学位论文的全部或部分内容编入有关数据库并进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质 论文的内容相一致。 保密的学位论文在解密后使用本授权书。 学位论文作者签名：垄酗 指导教师签名： 签名日期： 砷毛艮b 关于a 一循环码的a 周期分布和广义入一周期分布 1引言 关于入一循环码的入一周期分布 和广义入一周期分布 1 1 课题背景与发展 美国科学家s h a n n o n 在1 9 4 8 年发表的论文“通信的数学理论”【1 】中首次提出 了著名的有扰信道编码定理，开创了纠错码理论的研究方向，奠定了纠错码理论 的基石自s h a n n o n 的论文发表以来，纠错码受到了越来越多的通信和数学工作 者，特别是数学家的重视，使纠错码无论在理论上还是实际中都得到飞速发展 迄今，纠错码已有五十多年的历史，其发展过程大致分为以下几个阶段： 2 0 世纪5 0 年代至6 0 年代初，主要研究各种有效的编译码方法，奠定了线性分 组码的理论基础，提出了著名的b c h ( b o s e ，c h a u d h u r i ，h o c q u e n g h e m ) 2 4 】码，同 时也给出了纠错码的基本码限这是纠错码从无到有得到迅速发展的年代 2 0 世纪6 0 年代至7 0 年代初，这是纠错码发展过程中最为活跃的时期不仅提 出了许多有效的编码方法，而且注意到了纠错码的实用化问题，讨论了与实用有 关的各种问题，所有这些问题的研究为纠错码的应用打下了坚实的理论基础在 此期间，以代数方法特别是以有限域理论为基础的线性分组码理论已趋成熟 2 0 世纪7 0 年代至8 0 年代初，这是纠错码发展史中具有极其重要意义的时期 在理论上以g o p p a l s , 6 】为首的一批学者，构造了一类g o p p a 码，其中一类子码能达 至u s h a n n o n 在信道编码定理中所提出的s h a n n o n 码所能达到的性能，这在纠错码 历史上具有划时代意义在这期间大规模集成电路和计算机技术迅速发展，为纠 错码的应用打下了坚实的物质基础，因而与实用相关的各种技术及有关问题得到 了极大关注，并在实践中取得了巨大的成功 自2 0 世纪8 0 年代初至今，g o p p a 等从几何观点讨论分析码，利用代数曲线构 造了一类代数几何码【6 j ，在这些码中，某些码的性能达到了s h a n n o n 码所能达到 的性能由于代数几何码是一类范围非常广的码，在理论上已证明它具有优越性 能，因而受到了编码理论研究者，尤其是代数几何学家的重视，使代数几何码的 研究得到迅速发展，取得了许多成果 纠错码的重量分布问题是代数编码理论的一个重要课题【7 】一f 9 】，它其实是一 个码字计数问题，这个课题历史悠久，成果丰富但遗留问题也很多周期分布是 与重量分布类似的另一类计数问题，其实质就是求出周期为i 的码字的个数由文 献 1 0 】提出纠错码的周期分布后，国内许多学者对纠错码的周期分布问题进行了 探讨，特别是循环码的剧期分布问题，周期分布对研究循环码的内容结构特征是 1 关于a 一循环码的入周期分布和广义入周期分布 很有价值的 1 0 】， 1 1 】对( n ，k ，d ) 码给出了周期分布与广义周期分布的概念及其背 景，解决了r - s 码，扩充r - s 码和一般循环码的周期分布问题，并计算了r - s 码中无 内周期码字的个数；文献( 1 2 】提供了计算任意线性码的周期分布和广义周期分布 的方法；文献 1 3 】进一步对循环码的周期分布的性质进行了分析，给出了新的计 算方法和公式，并且确定了一些熟知的循环码的周期分布；文献 1 4 1 在文献f 1 3 1 的 基础上进一步对循环码的周期分布的特点进行了分析，给出了循环码周期分布与 其对偶码的周期分布之间的关系，并针对一般循环码及其对偶码无内周期码字给 出了精确的计算公式 循环码是一类非常重要的纠错码，其最大的优点就是可以简单的编译码，进 一步是构造其它码的基础，因此对循环码的研究起着举足轻重的作用正如文 献 1 3 】中写的那样，研究循环码的周期分布的动机和意义在于：( 1 ) 有利于更好 地了解循环码的结构；( 2 ) 可用于构造非线性等重码和循环置换码 1 5 】；( 3 ) 可用 于设计良好特性的信号【1 6 f 为了得到更般的结论，文献 17 】， 1 8 】对循环码的定 义加以推广，给出了最上入一循环码，也就是常循环码的定义和一些结果文献f 1 9 1 讨论了有限域b 上码长为礼的入循环码的周期分布及其对偶码周期分布的关系， 并给出了精确的计算公式 1 2 本文主要安排 本文主要安排： 第一部分介绍了纠错码的发展历史，并且综述了周期分布的研究现状和意 义 在第二部分中，给出了线性码和循环码的一些基本概念和结果，还介绍了纠 错码的周期分布和广义周期分布的定义和简单结果 在第三部分，定义了有限域日上纠错码的a 一周期分布，并且分别证明了循环 码及其对偶码存在入一周期的充要条件 在第四部分，前两小节通过对循环码定义的推广引入了b 上a 一循环码的定 义，并找出了a 一循环码的生成矩阵和校验矩阵在此基础上，后面两小节对于有 限域b 上码长为扎( ( 他，口) = 1 ) 的入循环码的a 一周期分布与最小a 一周期分布给出了 精确的计算公式，通过证明得到当( 凡，q ) = 1 时，入一循环码的a 一周期与广义a 一周期 为r 的码字集合是相同的，从而a 一周期分布与广义a 一周期分布是完全一致的 第五部分得出结论，并提出了未来可能的发展方向以及有待研究的问题 2 关于入循环码的a 周期分布和广义a 周期分布 2预备知识 本文讨论的都是有限域上的编码，记b 表示具有g 个元素的有限域，其中g 是 一个素数的幂这一部分的相关内容可以在【1 0 】， 1 1 】，【2 0 】中找到 2 1线性码 定义2 1 1向量空间毋的一个昂上的线性子空间c 叫作q 元线性码换句 话说，曰的一个非空子集合c 叫作口元线性码，是指若c ，c ，c ，则对任意a r b ， 望查竺璺：垡曼q 如果这个线性子空间的维数是k ，则称c 是一个hk 】线性码，扎是码长，k 是码 的维数，称任一长礼的向量z = ( z 1 ，z 2 ，z 竹) 碍为曰中的一个字，若z c ， 则称z 为m ，纠线性码c 的一个码字 定义2 1 2 设c 是一个h ，叫线性码，z = ( z 1 ，z 2 ，z n ) c ，称码字z 中不 为0 的分量的个数为它的h a m m i n g 重量，用w ( z ) 表示，即 g = ( 二) = ( 二三二：3 ：二三) 1 ； 【k 一詹，1 2 1 + 6 竹一屉，2 2 2 + + 6 竹一忌，n z 仃= 0 关于a 一循环码的入周期分布和广义入一周期分布 的全部解，其中日= ( 幻) 1 n k ，1 9 n 是b 上( 礼一k ) n ( n k 行n y l j ) 矩阵，并且秩 为n k 定义2 1 6称上述矩阵日叫作线性码c 的一个校验矩阵 由定义可知，对每个v 毋，口c 乍兮 矿= 0 ( 长为n 一七的零向量) ， 所以可用圩来检查向量u 是否为c 中的码字( 这里日t 表示日的转置矩阵) 设x = ( x l ，x 2 ，x n ) ，y = ( y l ，y 2 ，鲰) 曰， 那么z 和可的内积( z ，可) 定义为： ( x ，y ) = x l y l + x 2 y 2 + + x n y n 如果这两个向量的内积是0 ，我们就说这两个向量是正交的 定义2 1 7设c 是一个h ，翻的q 元线性码，则它的对偶码为 c 上= u 露i ( v ，c ) = o ，v c g ) 显然( c 上) 上= c ，如果c 的生成矩阵是g ，校验矩阵是h ，则c 上的生成矩阵 为日，校验矩阵为g 2 2循环码 循环码是线性分组码的一个重要子集，是目前研究得最成熟的一类码它有 许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码， 且易于实现；同时循环码的性能也较好，具有较强的检错和纠错能力 定义2 2 1码长为礼的口元线性码c n 作循环码，是指若c = ( c o ，c 1 ，c r i 一1 ) c ，则c 的循环移位( 一1 ，c o ，c 1 ，c n 一2 ) c ( 从而c 的任意多次循环移位所 得向量均属于c ) 把码字c = ( c o ，c l ，c ，l 一1 ) 写成多项式形式 c ( x ) = c o + e l x + + a n l x n 一1 日k 】，d e g c ( x ) 佗一1 则 x c ( x ) = c o x + c l x 2 + 一2 x n 一1 + c n 一1 z 竹 - - - - c n 一1 + c o x + + 一2 x n 一1 ( m o d x 佗一1 ) 所以看成是商环兄= 日m ( 扩一1 ) 中的元素，( c n 一1 ，c o ，c 1 ，一2 ) 恰好对应于兄 中元素z c ( z ) 曰中的g 元线性码c 按上述方式( c 看成c ( z ) ) 等同于尉拘一个日一线性子空 间( 仍记为c ) 如果c 是循环码，这就相当于c 满足如下条件： c ( x ) c 车兮x c ( x ) c 4 关于k 循环码的a 一周期分布和广义周期分布 g = ( z 乏， = ( 卯：! 乏七：j ：鲰一七 c 后行n 歹u ) 日：i - 1 h l ( n - k 行硎) 9 + ) = g o x n 一后+ 9 1 z n 一七一1 + + 鲰一知= x - k g ( x 一1 ) + ( z ) = h o x 七十h l x 南一1 + + h k = x a h ( x 一1 ) 它们给出的首1 多项式h 上 ) = 酊1 9 + ( z ) ，矿( z ) = h 0 1 h + ( z ) 分别为循环码c 上的校 验式和生成式 杰3纠错码的周期分布与广义周期分布 假设c = ( c o ，e l ，c n 一1 ) 是日中的一个长为n 的向量，c 的亡步循环移位( 1 t 礼) 定义为( c ) ，这旱( c ) = ( c t ，c t + 1 ，c n 一1 ，c o ，色一1 ) 定义2 3 1 设c 是玛上的( 礼，m ，d ) 码，c = ( c o ，e l ，a n 一1 ) 是c 中的一个码 字，如果存在正整数( 1 t n ) ，以及日中的元u ，使得s c = c + ( 仳，u ，饥) 成 5 关于a 循环码的a 一周期分布和广义a 周期分布 立，其中( u ，u ，u ) 表示有礼个u i f i 成的向量，则称t 为码字c 的一个广义周期，c 的 广义周期中的最小者( 设为t o ) 称为c 的最小广义周期 特别地，u = 0 时，上面定义中的t 和t o 分别为c 的一个周期和c 的最小周期 定义2 3 2 假设c 是日上( n ，m ，d ) 码，只，虿分别表示c 中最小周期为i ，最小 广义周期为i 的码字集合，则集合 | 只l ：1 i 几】和 l 再1 1 i n 分别称为c 的 周期分布和广义周期分布这里j a i 表示集合a 中元素的个数 引理2 3 1如果码字c = ( c o ，c 1 ，一1 ) 具有广义周期( 或周期) 亡，则c 的最 小广义周期( 或最小周期) 芒。必整除t ，也就是t o 陋 证明由于周期是广义周期的特例，这里只证广义周期的情形 设t = t o k + r ，0 r t o ，则存在昂中的元乱1 ，让2 ，使得下面两式成立： s 。c = c + ( u 1 ，u l ，u 1 ) ，s o c = c + ( u 2 ，t 正2 ，乱2 ) ， 于是 c = o 詹打c = y ( o 七c ) = 酽 c + k ( u 2 ，u 2 ，u 2 ) 】 = c + ( k u 2 ，k u 2 ，k u 2 ) 这里后( 抛，抛，乱2 ) 是向量的数乘，这样 c + ( u l ，u l ，u 1 ) = s r c + ( k u 2 ，k u 2 ，k u 2 ) ， 那么 c = ( 乱1 一k u 2 ，u l k u 2 ，u 1 一k u 2 ) + c ， 由定义2 3 1 可知r 也是c 的广义周期，且由于0 r t o 知亡。不可能是最小广义周 期，与题设矛盾，所以r = 0 ，t = t o k ，即亡o i t 定义2 3 3假设c 是日上( n ，m ，d ) 码，定义d r = c = ( c o ，c 1 ，一1 ) c ， c 具有周期r ) ，瓦= c = ( c o ，c 1 ，一1 ) c ，c 具有广义周期r ) ( 1 7 n ) 引理2 3 2b ，耳，研，瓦定义如上，那么有 吲= 弘( 五r 刚) ( 1 ) d l r 闻= p ( 三网) ( 2 ) d l r 这里p ( ) 是m o b i u s i 函数 证明由引理2 3 1 有： i n , i = 唰，i 瓦i = 闹， d i r d 1 7 再由m o b i u s 反演公式就可以得到( 1 ) ，( 2 ) 。 6 关于入一循环码的a 周期分布和广义入一周期分布 3 有限域日上纠错码的入一周期分布 3 1 局上纠错码的入- 周期分布 假设c 是日上一个纠错码，设c = ( c o ，e l ，a n 1 ) c 是一个码字，& 为一 个a 一循环移位算子，使& c = ( 入一1 ，c o ，c l ，c ，l 一2 ) ，其中入日，且= m ( a 在 乘群日中的阶) 关于a 一循环移位算子& c = ( 入一1 ，c o ，e l ，一2 ) ，有 鲰c = ( 入一1 ，入一2 ，c o ，e l ，c n 一3 ) ，s 癸c = a c 又假设& c ，= ( a 一l ，c 6 ，厶一2 ) ，那么 文( c + c ，) = ( 入( 一1 + 厶一1 ) ，c o + 晶，e l + 西，c n 一2 + 厶一2 ) = ( a c n 一1 + a 厶一1 ，c o + 晶，e l + 西，a n 一2 + 厶一2 ) = ( 入一1 ，c o ，c 1 ，a n 一2 ) + ( a 一1 ，晶，西，厶一2 ) = s 烬+ s k d & ( k c ) = ( 入忌c n 一1 ，k c o ，k c l ，忌c 竹一2 ) = k ( a c 竹一1 ，c o ，e l ，c n 一2 ) = 南风c ( v k 露) 所以a 一循环移位算子满足线性性 定义3 1 1 设c c ，如果存在正整数r ( 1 r 扎) 和正整数t o t m ) ， 使s r c = c ，则称r 为c 的一个入一周期，c 的所有入一周期中的最小者称为c 的最 小八周期 注3 1 1 设c 是日上一个纠错码，c c ，则凡是c 的入一周期 引理3 1 1 若r 为c 的最小a 一周期，贝u r l n 证明设死= r k + r l ，0 r 1 r ，则 a c = s c = 歌蚪n c = 磁1 ( 又七c ) 、 ， = s 1 入佧c = 七s 1 c 所以s 1 c = a - 柏a c 因为a 在乘群日中的阶为m ，所以a m 一1 = a 一，那么 即 a r k a c ：a ( m 一1 ) r k + l c 双1c ：a ( m 一1 ) r k + l c 这样r 1 也是c 的一个入一周期，由已知r 为c 的最小入一周期，所以r 1 = 0 ，n = r k ，耳 j r l n 7 关于a 循环码的周期分布和广义a 周期分布 定义3 1 2 假设c 是上一个纠错码，记只= ic ：c c ，c 的最小人周期 为圳，1 i 礼，那么称集合 只，1 i 礼) 是这个纠错码的最小入一周期分布 显然只= i c l 弓l 理3 1 2 1 1 9 】 若i 十n ，贝0 最= 0 证明 假设c c ，则c 的一个凡周期为佗，由引理3 1 1 可知最小入一周期t i n ，所 以如果i 十佗，只= 0 记皿= h ( i ) = ic ：c c ，c 的一个入一周期为i 1 ，1 i 钆，那么称集 合 鼠，1 i 佗) 为c 的a 一周期分布 注3 1 2( 1 ) 由上面的定义得皿= 只 ( 2 ) 当1 i 几时，0 h i i e l ，特别地，风= i e l 定理3 1 1 r 上纠错码c 的入一周期分布为 只= 茅：似日 扪计j h 这里p ( ) 是m o b i u s 函数 证明 若引佗，则有 鼠= 日( i ) = 只， f i l 利用m o b i u s 反演公式就可以得到 只= 肛( d ) 日( z d ) ， 再由引理3 1 2 就能证明( 3 ) 式成立 3 2 b 上循环码具有入一周期的充要条件 在这一小节，设c 是日m ( z n 一1 ) 上一个码长为n ( ( 佗，q ) = 1 ) 的循环码，生成 多项式为夕( z ) ，d e g g ( x ) = 几一k ，i g h ( x ) = ( 矿一1 ) g ( x ) 南一1 定理3 2 1 在循环码c 中与信息多项式a ( x ) = a i x 对应的码字c 具有入一 i = 0 周期的充要条件是：存在正整数t ( 1 t m ) ，使 n ( z ) ( z 7 一入。) m o d h ( x ) = 0 ，1 t m 证明码字多项式c ( x ) = q ，有前面的生成多项式的讨论, - i 矢u ，c ( x ) = 8 关于入一循环码的入一周期分布和广义入周期分布 n ( z ) 9 ( z ) 另b 么 c ( x ) x r m o d ( x n 一1 ) = o ( z ) 9 ( z ) z r m o d ( x n 一1 ) = a ( x ) x r g ( x ) m o d g ( x ) h ( x ) = 陋( z ) 矿 m o d h ( x ) g ( x ) 因为码字多项式和信息多项式相互唯一确定，根据码字c 具有入一周期的定义： 存在正整数t ( 1 t m ) s c = a r c ，码字c 具有a 一周期就等价于存在正整 数t ( 1 t m ) ， a t a ( x ) g ( x ) 三“o ( z ) 矿 m o d h ( x ) g ( x ) 又等价于 也就是 a a ( z ) 三 a ( z ) z r m o d h ( x ) n ( z ) ( z r a ) m o d h ( x ) = 0 由定理2 2 2 可知b 上的循环码的对偶码c 上也是循环码，根据这两个循环码 生成多项式之间的关系及定理3 2 1 ，有下面的推论 七一1 推论3 2 1 在循环码c 的对偶码c 上中与信息多项式a ( x ) = a i x 对应的 i = o 码字c 具有a 一周期的充要条件是：存在正整数t ( 1 t m ) ，使 o ( z ) ( z r a t ) m o d g ( z ) = 0 ，1 t m n 一1 证明循环码c 的对偶码c 上中码字多项式c ( x ) = q ，由定理2 2 2 可 知 ( z ) 为对偶码g 上的生成多项式，所p a c ( x ) = 口( z ) ( z ) 那么 c ( z ) x r m o d ( x 竹一1 ) = a ( x ) h ( x ) x r m o d ( x n 1 ) = a ( z ) z r h ( x ) m o d g ( x ) h ( x ) 】 = n ( 。) z m o d h ( x ) g ( x ) 因为码字多项式和信息多项式相互唯一确定，根据码字c 具有a 一周期的定义： 存在正整数t ( 1 t m ) 必c = a t c ，码字c 具有a 一周期就等价于存在正整 数t ( 1 t 总是入一循环码，我们称这些是 平凡入。循环码 ( 2 ) 当a = i 时，c 是循环码当a l 时，我们说这个码是负循环的 例4 1 1 ( 1 ) c 1 = o o o o ，1 1 2 0 ，0 1 1 2 ，1 0 1 1 ，2 1 0 1 ，2 2 1 0 ，0 2 2 1 ，2 0 2 2 ，1 2 0 2 露是忍上长为4 的一个负循环码 ( 2 ) q = o o o o o o o ，4 2 1 3 4 2 1 ，3 4 2 1 3 4 2 ，1 3 4 2 1 3 4 ，2 1 3 4 2 1 3 g 碟是屁上长为7 的 一个3 - 循环码 正如上一个码长为凡的循环码是主理想环f q m ( z n 一1 ) 的理想，我们利用 一个从日上的向量空间曰到f 口渊( z n 一入) 的同构映射7 1 , k ，其中 啾( ( 岫，u 1 ，一1 ) ) = 0 j 0 + u l z + 一1 x 几一1 那么可以把日上一个码长为n 的入一循环码看成是主理想环日m ( z n a ) 的理 想，于是有下面的定理4 1 1 定理4 1 1设c 是曰的一个非空子集，那么c 是日上一个码长为n 的入一循环 码当且仅当7 r a 是r q m ( z 竹一入) 的一个理想 证明 假设c 是f g 的一个a 一循环码，下面来证明7 r a ( c ) 是日m ( z n 一入) 的一 个理想 设n ( z ) ，6 ( z ) n ( z ) ，那么就存在a ，b c 满足 7 h ( 口) = o ( z ) r x ( b ) = 6 ( z ) 由于c 是线性的，a b c ，所以 以( o ) = 矾( 6 ) = 以( n b ) 叽( c ) 设a = ( a o ，a l ，a - 1 ) ，那么 仃入( o ) = ( h a n 一1 ，a o ，a n 一2 ) c 1 1 关于入循环码的a 周期分布和广义a 一周期分布 因此对每一个p 日，我们有 p z 7 氓( n ) = 7 队( p a 叹( n ) ) 7 r a ( c ) 设f ( x ) = f o - t - z + + 厶一l x 俨1 日p 】( z n 一入) ，那么 n 一1 m ) 7 r a ( n ) = 以( n ) 以( c ) i = 0 对每一个0 i n 一1 ，五r x ( a ) n ( c ) ，因此啾( c ) 是日m ( z n 一入) 的一个理 想 反之，假设啾( c ) 是日纠( z n a ) 的一个理想，设a ，b c ，那么对任意p ，p 最，因为以( c ) 是b z 】( z n 一入) 的一个理想， 7 r 入( p o + p b ) = 肛7 队( 口) + p l r 入( b ) 以( g ) 因此p 口+ p b c ，所以c 是线性的又矾( 叭( n ) ) = x r n ( a ) 以( c ) ，因此盯a ( n ) g ，所以c 是入一循环码 4 2 入循环码的生成矩阵和校验矩阵 定理4 1 1 已经说明日上所有码长为佗的a 一循环码是b m ( z n 一入) 的理想，那 么用与循环码类似的结果可以定义a 一循环码的“生成多项式” 定理4 2 1 设硝邑环日m ( z 竹一a ) 的一个非零理想，g ( x ) ，是一个次数最 低的非零首一多项式，那么j = 白( z ) ) 和g ( z ) | z n a 都在i x 】中，进一步，夕( z ) 是 唯一的 证明 显然g ( x ) j 设a ( x ) i ，对6 ( z ) ，r ( x ) f g m ，有 a ( x ) = b ( x ) g ( x ) + r ) ， 其中d e g r ( x ) d e g g ( x ) 因为口( z ) ，6 ( z ) 9 ( z ) i ，r ( x ) = a ( x ) 一b ( x ) g ( x ) i ， 又由于夕( z ) 是i c e 次数最低的非零首一多项式，所以 r ( x ) = 0 ，a ( x ) = 6 ( z ) 夕( z ) ( 9 ( z ) ) ， 这样，( 9 ( z ) ) ，所以j = 幻( z ) ) 假设对，( z ) ，s ( x ) 日 z 】，z n 一入= f ( x ) g ( x ) d - 8 ( x ) ，其中d e g s ( x ) d e g g ( x ) ， 又一a = 0 ，所以 s ( x ) = z n a f ( x ) g ( x ) i 1 2 关于入一循环码的k 周期分布和广义入一周期分布 这样s ( z ) = 0 ，x n 一入= ，( z ) 9 ( z ) ，所以9 ( z ) f 一入 最后证唯一性 假设夕7 ( z ) ，是另一个次数最低的非零首一多项式，由前面的论证得， 夕( z ) 1 9 ，( z ) ，g l ( z ) 1 9 ( z ) ，又都是首一的，所以夕( z ) = 夕7 ( z ) ，唯一性得证 定义4 2 1设，是环日m ( z n a ) 的一个非零理想，夕( z ) 矾( c ) 是( 唯一 的) 次数最低的非零首一多项式，那么9 ( z ) 被称为c 的生成多项式 注4 2 1 ( 1 ) 为了和前面的定义一致，规定r h ( z 竹一入) 的零理想的生成多 项式是一a ( 2 ) 如果一个非平凡线性码c 既是一个a 一循环码，又是一个肛循环码，那么a = 肛 例4 2 1 在例3 1 1 d p ，c 1 ，c 2 分别有生成多项式夕1 ( z ) = 2 x 2 + x + 1 ， 仍( z ) = x 6 + 2 x 5 + 4 x 4 + 3 x 3 + z 2 + 2 x + 4 定理4 2 2 设c 是瑶上一个码长为n 的入一循环码，生成多项式为9 ( z ) ，其 c d e g g ( x ) = 几一k ，另瞄么 7 r a ( c ) = n ( z ) 夕( z ) ：a ( x ) 日 z 】，d e g a ( x ) 七) ，d i m ( c ) = k 例4 2 2 由定理4 2 2 可知，例4 2 1 中，d i m ( a ) = 2 ，d i m ( c 2 ) = 1 由于叽是向量空间曰到日 x l ( x n 一入) 的一个同构映射，那么我们就可以把 向量 u = ( 蛐，0 ) 1 ，0 9 n 一1 ) 曰 和对应的多项式 u ( z ) = 蛐+ u 1 x + + 一1 x n 一1 看成是相同的这样仿照非零循环码从生成多项式构造生成矩阵的方法，利用前 面这个等置变换，关于a 一循环码可以得到类似的结果 定理4 2 3设c 是e 上一个码长为几的a 一循环码，生成多项式为 夕( z ) = g o + g l x + + 鲰一知z n 一七 其中d e g g ( x ) = 他一k ，那么这个矩阵 仕嵫卜 夕o9 1 夕n k 00 0 0 g og l 吼一七00 0 0 0 g og l g n 一七 1 3 关于a 一循环码的a 一周期分布和广义人周期分布 证明很显然g 的行是线性无关的，因为g 的每一行都是c 的一个码字， 又r a n k ( g ) = k = d i m i c ) ，所以g 是c 的一个生成矩阵 我们已经知道循环码的对偶码仍然是循环码，对于a 循环码这个结论也是成 立的 定理4 2 4设c 是层上一个码长为扎的a 一循环码，生成多项式为9 ( z ) ，其 d p d e g g ( x ) = n 一忍，那么c 上就是日上码长为佗的a - l _ 循环码，生成多项式 是九i l h r ( z ) ，其中 h ( x ) = ( z n 一入) 夕( z ) o 是h ( x ) 中的常数项，血i x ) = x d e g f ( z ) ，( z - 1 ) 是厂( z ) 的互反多项式 定义4 2 2设c 是局上一个码长为n 的a 一循环码，生成多项式为夕( z ) ，设h ( x ) = ( x n - - a ) 9 ( z ) ，h o 是h ( x ) 中的常数项，用血( z ) 定义， ) 的互反多项式x d e g f ( 。) ，( z - 1 ) ， 那么首一多项式h 0 1 h r ( z ) 被称为c 的奇偶校验多项式 由定理4 2 3 和定理4 ，2 4 可以得到下面的推论4 2 1 推论4 2 1设c 四是日上一个码长为他的a 一循环码，生成多项式为9 ( z ) ， 其中d e g g ( x ) = n k ，记 h ( x ) = ( z 竹一入) 9 ( z ) = h o + h l x + + h k x 七 日：f ，l h r ( ? x ) x n - k - 1 h r ( x ) 1 惫一1 0 h k 一1 是c 的一个奇偶校验矩阵 0o 0 h o 00 0 0h k h k 一1 o 4 3 入循环码的入周期分布 引理4 3 1 【1 9 】 在日上给定多项式u ( z ) ( 钆( z ) o ) 后，则日 z 】中存在g k - d e 9 u ( 。) 个 阶数不超过k 一1 的多项式y ( z ) 使得u ( z ) i y ( z ) ，记 t ( k ，乱( z ) ) = q k - d e 夕u ( z ) 1 4 关于入一循环码的a 一周期分布和广义a 一周期分布 证明 在b m 中，u ( z ) l y ( z ) 也就是说，存在r ( z ) b i x ，使篌4 v ( x ) = r ( z ) u ( z ) ，其中 d e g r ( x ) = d e g v ( x ) 一d e g u ( x ) k 一1 一d e g u ( x ) ， 而这样的7 0 ) 共有q 七一咖u ( 2 ) 个，所以y ( z ) 个数为矿一如9 u ( 引 下面设c 是日 z 】( z n 一入) 上一个码长为n ( ( 礼，q ) = 1 ) 的入一循环码，生成多项 式为9 ( z ) ，d e g g ( x ) = n k ，记h ( x ) = ( z n 一入) 9 ( z ) 七一1 定理4 3 1 在片循环码c 中与信息多项式a ( x ) = a i x 对应的码字c 具 i = o 有入一周期的充要条件是：存在正整数t ( 1 t m ) ，使 口( z ) ( z r a 2 ) m o d h ( x ) = 0 ，1 t m n - - 1 证明码字多项式c ( x ) = q ，有前面的生成多项式的讨论可知， i = 0 c ( x ) = n ( z ) 9 ( z ) 那么 c ( x ) x * m o d ( x 1 一a ) = n ( z ) 夕( z ) z 7 m o d ( x n 一入) = a ( x ) x r g ( x ) l m o d g ( x ) h ( x ) 】 = 陋( z ) z r m o d h ( x ) g ( x ) 因为码字多项式和信息多项式相互唯一确定，根据码字c 具有a 周期的定义： t ( 1 t m ) ，必c = a r c ，码字c 具有入一周期就等价于存在正整数t ( 1 t m ) ， 又等价于 也就是 a 。n ( z ) 夕( z ) 兰 o ( z ) z r m o d h ( x ) g ( x ) 入t a ( x ) 三 a ( x ) x r m o d h ( x ) o ( z ) ( z r 一入。) m o d h ( x ) = 0 定理4 3 2 由9 ( z ) ( 9 ( z ) ( z ) = 扩一a ) 生成的码长为佗( ( n ，q ) = 1 ) 的入一循环 码c 的a 一周期分布 h i ，1 i 佗) 和最小a 一周期分布 只，1 i n ) 分别为 珥：俨m 州a x e “ 咖删z 一卅，1 r n ， 只= 肛( s 7 ) 研，1 s 钆 r ：r i