（基础数学专业论文）环zpk1上的（1pk）循环码与gray映射.pdf

摘要 上世纪7 0 年代起，b l a k e 【1 】和s p e i g e l 【2 】等学者开始将纠错码的研究从有限域 上转移到整数剩余类环z 。上9 0 年代初，f o m e y 等学者在【3 】，h a m m o r l s 等学者 在f 4 j 中证明了k e r d o d 【码，p r e p a r a 乇a 码，d e l s a r 乇e - g o e t h a l s 码比同样长度，同样 距离的线性码有更多的码字，这些非线性码实际上就是一些z 4 上的线性码在g r a y 映射下的像1 9 9 8 年， c a r l e t 在文献【6 1 中，通过b 0 0 l e a n 函数在z 2 t 上定义了 g r a y 映射，通过g r a y 映射将z 垆上的线性码映射成z 2 上的非线性码，得到了广 义的k e r d o c l 【码和广义的g o e t h a l s 码l i n g 在文献 9 】中进一步将g r a y 映射推广 到环瓦州上，给出了( 1 一矿) 循环码的g r a y 像是珞上的准循环码，且通过建 立( 1 一矿) 一循环码与一般循环码的一一对应，得到了环z p 川上的循环码的g r a y 像等价于准循环码，且给出了它们的像为线性的充分条件 本文继续对环州上的码展开研究，得到了以下主要结果 在第二章，通过利用环z p 中的元素可以唯一写成p 进制的形式，以及从z 孕+ 。 到霹上的g r a y 映射，我们给出了环z 矿+ t 上的( 1 十p ) 一循环码的g r a y 像和一 般循环码的g r a y 像以及负循环码的g r a y 像 在第三章，我们给出了环z 矿+ ，上长为n ，( 死，p ) = 1 的常循环码的生成元通过 建立瓦上的循环码与( 1 + p 七) 一循环码的一一对应给出了( 1 + 矿) 一循环码的生 成元 在第四章，我们考虑环z 矿上的码由于本文所说的循环码，常循环码，准循环 码不一定是线性的最后本文给出了环z 上( 1 + p ) 一循环码和循环码的g r a y 像 是线性的充分条件 关键词：g r a y 映射；循环码；常循环码；准循环码；次准循环码；准负循环码；线 性码；理想 a b s t r a c t s i n c e1 9 7 0 8 ，s o m er e s e a r c l l e r s ，s u c h 罄b l a k e f l 】a n ds p e i g e l 2 】，b e g a nt od 溥 c u s se r r o r - c o r r e c t i n gc o d e s ，e rt h er i n g sz mo fi n t e g e r sm o d u l omi n s t e a d0 fs t u d y i i l gc o d e sa v e r 丘n i t e6 e l d 8 1 1 1t h eb e g i n n i n go f1 9 9 0 s ，f 0 m e ye t c 【3 】a n dh a m m o u s e t c 【4 】p r o v e dt h a ts o m en o n l i n e a rc o d e s ，s u c ha sk e r d o 出c o d e ，p r 印a r a t ac o d ea n d d e l s a r t e g o e t h a l sc o d ea r et h ei m a g e so fs o m e1 i n e a rc o d e so v e rz 4 ，w h e r et h em 印 i st h eg r a ym a p s i n c et h e s en o n l i n e a rc o d e sh a 、r em o r ec o d ( 强r o r d bt h a nt h o s el i n e a r c o d e sw i t ht h es 锄el e n 酵ha n dt h es a m eh 锄m i n gd i s t a n c e ，t h er e s e a rc ：hi n t e r e s ti n c o d e sa v e rf i n i t er i g sh a sg r l r 印i d l y i n1 9 9 8 ，c 盯l e t 【6 】d e 矗n e dg r a ym a po v e rz 2 女 b yu s i n gb o o l e a nf i m c t i o n ，t h e nm 印p e dt h el i n e a rc o d e so 、他rz 2 七t on o n l i n e 越c o d e s o v e rz 2b yt h eg r a ym 印i nt h i sp 印e r ，a n d 丘n a l l yo b t a l i n e dg e n e r a l l i z e dk e r d o 出 c o d ea n dg e n e r a l i z e dg o e t h 以sc o d e l i n g 9 e 斌e n d e dt h ed e 丘n i t i o no fg r a ym a pt o z 矿+ 1a n dp r o v e dt h a tt h eg r a yi m a g eo f ( 1 一矿) 一c y c l i cc o d e s 盯eq u a s i c y e l i cc o d e s d v e r 珞i n 9 ，t h e va l s op r o v e dt h a tc y c l i cc o d e so v e rt h er i n g sz 矿十】a r ee q u i v 出e n t t oq u a s i - c y c l i cc o d e sb yf o r m u l a t i n gao n e - t m o n ec o r r e s p o n d e n c eb e 伽e e n ( 1 一矿) 一 c y c l i c d e sa n dg e n e r a l lc y c l i cc o d e s ，t h e ya l s op r 硎d e das u 行c i e n tc o n d i t i o nf o rt h e i m a g e so fc o d e so v 竹z 七十lt ob el i n e a r i nt h i j st h e s i s ，es h a uc o n t i n u et h es t u d yo nc o d e so v e rz 口k + 1 w 色o b t a i l lt h e f o l l o 丽n gr e s u l t s i i l 出印t e r2 ，b yu s i n gt h eg r a ym 印( s e e 【9 ) 厅o mz 1t o 缉“，a n dt h eu n i q u e p a d i ce 冲r e s s i o no fe a c he l e m e n ti nz 口，t h eg r a yi m a g e so f ( 1 + 矿) 一c y c l i cc o d e so f l e n 酌hn o 、伦rt h en n g sz 口七十l ，g e n e r a l lc y c l i cc o d e sa n dn e g a c y c l i cc o d e sa r eo b t a i n e d ， w h e r e ( 行，p ) = 1 hc h 印t e r3 ，w h e n ( 礼，p ) = 1 ，t h eg e n e r a t o ro fc o n s t a u c y c l i cc o d e s 研t hl e n 酗h no m e rz 口上+ 1a r eo b t a j n e d b y 璐i n gt h eo n e - t o 卜o n ec o r r e s p o n d e n c eb e 饥矿e e nq r c l i c c o d e sa v e rz p 州a n d ( 1 + p 七) 一c y c l i cc o d 铭o v e rz p ，t h eg e n e r a t o ro f ( 1 + 矿) 一 c y d i cc o d e sa r eo b t 越n e d i n 出印t e r4 ，w ef o c u so nc o d e so v e rz 知f i r s tw en o t et h a tt h et h e ec l a 鼹o f c o d e s l 了c l i cc o d e s ，c o n s t 嘲7 c l i cc o d 皤a n dq u a s i c y c u cc o d e s ，w h i d ha r ed i s c u s s e di t h i st h e s i s ，m a yb en o n l i n e a r i nt h i s 出印t e r ，t h es u 伍c i e n tc o n d i t i o i l sf b rt h eg r a y i m a g eo f ( 1 + p ) 一c y c l i cc o d e sa n dt h ec y c l i cc o d e s0 v | e rz 矿t ob el i n e a ra r ea 1 8 0 西m i i 硕士学位论文 m a s t e r st h e s i s i ( e y w o r d s ：g r a ym 印；c y c cc o d e s ；c o n s t a 呵c l i cc o d e s ；q u a s i - c y c l i cc o d e s ； m i n o 卜q u a s i c y c l i cc o d e s ；q u 够i n e g a u c y c l i cc o d e s ；h n e a rc o d e s ；i d e a l i i i 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：兄墙依日期：2 缈s 年s 月2 口日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名：霭债镌 日期：2 妒g 年s 月2 口日 狮弘钡乏飞“7 日期：年兮月9 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程中的 规定享受相关权益。回童诠塞握銮卮溢卮；旦主生i 旦二生i 旦三生筮查! 作者签名：店镐盾 日期：丑妒子年9 月2 夕日 导师签名： 厂门 够p 弓【- 夕 日期：乙砺年f 月2 目 第一章引言 编码理论最初开始于对二元域上的码的研究，进而扩展到研究一般有限域上的 码结构在上世纪7 0 年代，b l a k e 【1 】和s p e i g e l 【2 等学者开始将纠错码的研究从有 限域上转移到整数剩余类环上利用中国剩余定理，对剩余类环z 。上的码的研究 归结为对。上的码的研究，这里p 是一个素数对任意口致，元素口可以唯一表 示为o = 口o + 2 q 1 ，这里0 知，0 1 1 利用z 4 上的元素的这种唯一表示，f o m e y 等【3 】，h a m m o n s 等【4 】学者在上世纪9 0 年代初在环z 4 上定义g r a y 映射如下 妒：z 4 _ 砰，口( n 1 ，0 1on 0 ) ， 这里。表示域马上的加法g r a y 映射可以自然地扩展到从砑到露”： z 2 露，z = r ( z ) + 2 q ( z ) ，( 名) = ( q ( z ) ，g ( z ) o r ( z ) ) 在文献f 3 ，f 4 j 中，作者证明了k e r d o c k 码，p r e p a r a t a 码，d e l s a r t 争g o e t h 甜s 码等实 际上就是一些z 4 上的线性码在g r a y 映射下的像由于这些非线性码比同样长度， 同样h 洳m i n g 距离的线性码具有更多的码字，因此在信息传输中可以承载比同样 长度，同样距离的线性码更多的信息，因此具有较高的效率通过g r a y 映射，人们 可以更加清楚地理解这些非线性码的性质进而对非线性码的结构有更进一步的了 解这些重要的发现重新激起了编码理论界对有限环上的码的研究兴趣特别是对 整数剩余环z 矿上的线性分组码及其g r a y 像的研究 设冗是任意有限交换含单位元的环环r 上的码c 称为循环码，如果对任意 的c = ( c 0 ，c 1 ，一】) c ，有( 一1 ，c ；d ，一2 ) c 循环码理论在编码理论 的研究中占有非常重要的地位，已有很多研究成果在1 9 9 9 年，w | o a n n 5 】研 究了环z 4 上的线性循环码( 长为奇数) 的g r a y 像与线性负循环码的像，得出了 此环上的线性负循环码的像为二元的循环码，长为n ( 礼为奇数) 的线性循环码的 像等价于一个循环码并且指出线性循环码与负循环码的像不一定是线性的进一 步，设护一1 = ( z 一1 ) 五( z ) b ( z ) ，其中z 一1 ，五( z ) ，6 ( z ) 两两互素令0 1 ( z ) ，6 1 ( z ) 为五( z ) ，6 ( z ) 的h e n s e l 提升在该文中作者证明了：如果z 4 上的线性循环码的生成 元为口1 ( z ) ( 6 10 ) + 2 ) ，则其g r a y 像为线性的若z 4 上的线性负循环码的生成元为 o ( z ) ( 6 ( z ) + 2 ) 其中口( z ) = 凸1 ( z ) ，6 ( z ) = 6 z ( 一z ) ，则其g r a y 像是线性的循环码 c 缸l e t 在文献 6 】中，通过b o o l e a n 函数将g r a y 映射的定义推广到z 2 - 上，在z 2 - 上定义了g r a y 映射，并且给出了z 2 t 线性码上的一些重要结果7 工i a p i a - r e c i a s 在 文献( 7 1 ，【8 】中研究了z 2 - 上的循环码与常循环码的g r a y 像，及其g r a y 像的线性 性l i n g 在文献 9 】中进一步将g r a y 映射的定义推广到环z p 川上，并将已有结果 1 推广到了z p m 上在该文中作者还给出了( 1 一矿) 一循环码的g r a y 像是z p 上的准 循环码，并且通过建立( 1 一矿) 一循环码与一般循环码的一一对应，得到了环z p 上的循环码的g r a y 像等价于准循环码，而且给出了它们的像为线性的充分条件 本文在上述研究工作的基础上进一步展开对剩余类环z 扩+ - 上的线性码的研究 本文得到了以下几个主要结果t 第一，利用环硌+ - 中的任意元素口可以唯一写成口= 咖+ 0 1 p + + o 砖p 七，这 里o p 一1 ，j = o ，1 ，七，以及在文献【9 】中给出的z x - 到缉上的g r a y 映射，当( 扎，p ) = 1 时，给出了z p 州上的长为n 的码c 为一个( 1 + 矿) 一循环码当 且仅当其g r a y 像咖( c ) 是z p 上的指数为矿，长度为矿n 的次准循环码环z p 州上 长度为礼的码为循环码的充分必要条件是它的g r a y 像是z 口上长度为n 矿指数为 矿的准循环码环z 一+ ，上长度为n 的码为负循环码的充分必要条件为它的g r a y 像为z p 上的长度为礼矿指数为矿的准负循环码 第二，给出环z 矿+ t 上长为n ，( n ，p ) = 1 的常循环码的生成元c 是z 矿+ ，上 的长为n 的a 一循环码，a z 二则存在多项式昂，r ，最+ 1 彼此互素( 可以 为1 ) ，使得z “一a = 蜀日晟+ 1 ，且 这里 c = ( 矗，p 岛，矿或+ 。) ， icl = 一， 若忍= z p t + ，m ( 矿一a ) 为主理想环，c 为心的理想，则c = ( g ) ，其中 g = 矗+ p 皮+ 十矿鼠+ 1 通过建立z 。川上的循环码与( 1 + 矿) 一循环码的一一对应给出了( 1 十矿) 一循 环码的生成元的情况 第三，当七= 1 时，给出了环z 萨上( 1 + p ) 一循环码和循环码的g r a y 像 是线性的充分条件即若c 为z 扫一线性码( 长为n ) ，则咖( c ) 是z p 上线性 码当且仅当对，b c ，有p ，( 咱( a ) ，伯( b ) ) c ( 其中，见第四章中定义的函 数) 特别地，如果a ，p b c ，p ( a 幸b ) c ，其中木指分量乘法，则( c ) 是 上的线性码若g = ( a ( z ) ( b ( z ) + p ) ) 是长为扎的循环码，则( g ) 是线性 如果( o ( z ) 6 ( z ) ) 牛( 口( z ) ) ( o ( z ) ) ，在这种情况下，z p 2 上线性码( 1 + p ) 一循环码 = 似7 ( z ) ( b 7 ( z ) + p ) ) 的g r a y 像( c 7 ) 也是线性的( 其中a ( z ) ，b ( z ) ，a 7 ) ，b 7 ( z ) 为定理3 2 4 与3 2 5 中所指 口( z ) 加( z ) 为其关于模p 的约化) 2 + 咒 g ed 磅 一l + 七御 l i 硕士学位论文 m a s t e r st h e s i s 2 1 基本概念 第二章 环+ - 上的g r a y 映射 设p 2 且为素数，奄是1 的正整数，为避免混淆，环瓦州( 老1 ) 内的加 法与减法记作+ ，一，环z p 内的加法与减法记作o ，e ，同样的记号还用于其对应环上 的向量与多项式的加法和减法 z 纛+ 。表示z 矿+ - 中的所有可逆元的集合2 0 + t 【瑚 表示以环瓦内元素为系数的多项式的集合 定义2 1 1 设n 是任意正整数令z + 。= ( 口o ，0 1 ，一1 ) l 啦瓦) 则 z 象+ 。是一个z p 一模z 纛+ 。的任意的非空子集c 称为z p - + - 上的一个长为n 的 码进一步，如果c 是z 飘，的子模，则称c 是z 口上的长n 的线性码 定义2 1 2 设c 为环z 矿+ - 上长为n 的码，令 盯：弓+ l _ 碜+ 1 ，( 凸o ，n 1 ，一1 ) h ( a 。一1 ，伽，o l ，o 。一2 ) 若仃( g ) = c ，则称c 为环上的循环码 定义2 ，1 3 设c 为环川上长为咒的码，令 p ：碜+ - _ 珞+ ，( 知，口1 ，一1 ) h ( 一一1 ，n o ，0 1 ，一2 ) 若p ( g ) = c ，则称c 为环z p m 上的负循环码 定义2 1 4 设c 为环z p 上长为n 的码，入z 每+ ，令 坝：碜+ l _ z + ，( n o ，0 1 ，一1 ) h ( 入d n l ，知，0 1 ，一2 ) 若叭( c ) = c 则称c 为环z p 州上的常循环码，或入一循环码 定义2 1 5 设c 为环z p 上长为n 的码，m ，s 为正整数， a ( ，q ( ，口 z ，盯：矽一z 指循环置换( 仃( 咖，口1 ，口。一1 ) = ( 一1 ，知，0 1 ，n 。一2 ) ) 令 口。8 ：矽叶矽，( 口( 1 io ( 2 i i 口( 8 ) h ( 仃( o ( 1 ) i 盯( o ( 2 ) i l 口( 口( 8 ) ) 若矿8 5 ( c ) = c 则称c 为环殇上的准循环码，s 称为准循环码的指数特别地， 仃圆l = 盯 定义2 1 6 设c 为环z p 上长为的码，仍，s 为正整数，口( ，q ( 2 ) ，o ( 5 z 罗，p ：z 孑一z 罗指负循环置换( p ( 咖，口1 ，一1 ) = ( 一一1 ，0 0 ，q 1 ，o 。一2 ) ) 令 卢。8 ：z 尹_ z 尹，( 口( 1 ln ( 刁i fd 。) h ( p ( 口( 1 ) lp ( 口( 2 ) i lp ( 口5 ) 3 硕士学位论文 & a s t e r st h e s i s 若p 舯( c ) = g 则称c 为环瓦上的准负循环码，特别地，p 刚= p 1 一循环码即为循环码，指数为1 的准循环码即为循环码， 一1 一循环码即为负 循环码 需要强调的是这里的循环码，常循环码，准循环码，准负循环码不一定是线性 的，环兄上的线性码是一个冗一模 设，( z ) = d o + o l z + + 护z 矿+ ，m ，记，( z ) 是将，( z ) 的系数约化到z p 中得到的瓦f z l 的多项式，即 珏：z 矿+ ，嘲_ 缉嘲，0 ) h 嚣，( z ) = ，( 2 ) ， 其中页万= 而+ 西z + + 酝矿z p 定义2 1 7 设厂( z ) 耳州m 为首一多项式，( z ) 称为基本不可约多项式，如 果厂( z ) 在中不可约 以下为方便，有时简记，扛) 为厂 定义2 1 8 任意口硌，可唯一写成 口= r o ( o ) + 1 ( 凸) + + p 七( o ) ， 其中 n ( n ) o ，l ，p 一1 ，( osi 惫) 以下映射称为g r a y 映射： ：硌+ t 一缉l ， a = ( a o ，a 1 ，a 一1 ) h ( 印，0 1 ，七。一1 ) 。“m + f ：2 强( a ) 。( 舌n l ( i ) n ( 4 ) ) 。e r o ( 如) ，老2 ；( 2 1 ) o ( i 什c ) f l + j2 气 l = 1 l z 1 ) i “( 4 ) o 珊( 4 ) ， 七= 1 o i 矿一1 1 ，o p 一1 ，o j 死一1 是单射，且当p = 2 ，七= 1 ，驴是我们通常所说的磁到2 窖上的g r a y 映射规定 若a = ( 山，a 1 7 一，a 一1 ) z 则 n ( a ) = ( n ( 也) ，n ( a 1 ) ，n ( a 一1 ) ) z ；( o i 七) 定义2 1 9 设c 为环z p 上长为死的码，是g r a y 映射 碜+ 鱼 。纬k!，砟k ， ( 山，a 1 ，厶一1 ) = ( c l 0 ，一1 i ，口2 n 一1 l ，i 口铲一1 ) 。，。一1 ) ，y ( 口o ，口n 一1 l o 。，0 2 。一1 i ，l 口( p 一1 ) 。，k 。一1 ) = ( n 2 n 一1 ，知，一2 l 口3 n 一1 ，口2 n 2 i ，i 凸西t + 1 ) n 一1 ，口( p 七一1 ) n ，o p 七n 一2 ) 其中令 口( p - + 1 ) 。一l = “( a 1 ) + 一1 ) 【r 1 ( 厶一1 ) + 7 2 ( 厶一1 ) + r 3 ( a “一1 ) + + “一1 ( 厶一1 ) 】， 环殇上的码c 称为指数为矿，长度为 地，当忍= 1 时， o 加。+ 1 ) 。一1 = 一1 2 2 几类循环码的g r a y 像 p 的次准循环码，如果，y ( c ) = c 特别 关于g r a y 映射，有下列命题； 命题2 2 1 9 若a ，b z & 则 ( 矿a ) = ( 伯( a ) ，7 o ( a ) ，：r o ( a ) ) 驴( a + p 七b ) = ( a ) o ( p 2 b ) z 扩十，上的齐次重量叫t ，l 帆定义为： f 矿，z p 七弓十， o ) ； 叫t ，l 。( z ) = 矿1 ( p 一1 ) ，zg 矿硌“ 【 o z = o 几一l 若a = ( a o ，a 1 ，a 。一1 ) 乃+ 。，定义叫 o m ( a ) = 叫 。( 4 ) ，：= u 齐次距离定义为； d h 一( a ，b ) = 伽t b m ( a b ) ，a ，b 碜+ - 命题2 2 2 9 】上面定义的g r a y 映射是( 2 咎+ ，d ，l 一) 到( 虿“，妇) 的保距同 构，其中妇指瑶h 中的h 衄1 m i n g 距离 下面研究几类循环码的g r a y 像 命题2 2 3 设a = 1 + 矿硌+ 1 则矽口a = ，y ( 其中坝，庐，y 见2 1 中的基本概 念) 证明任意的a = ( 凡，a 1 ，厶一1 ) z 十。， 坝( 山，a l 一，厶一1 ) ( ( 1 + 矿) a 乩凡，a l 一，a 。一2 ) = ( b o ，b 1 ，既一1 ) 5 设 设 加a = ( b 0 ，岛，风一1 ) = ( 6 0 ，6 1 ) 一，峪。一1 ) ( ，a 1 ，a 一1 ) =( 口o ，q 1 ， ，t 。一1 ) ， ，y ( 山，a l ，厶一1 ) = ，y ( 知，0 1 ，一。一1 ) = ( c 0 ，c 1 ，勺t 。一1 ) 风=( 1 + 矿) 厶一l ( 1 + 矿) ( 翔( a 1 ) + 1 ( a 1 ) + + 矿( a 一1 ) ) = 伯( a 。一1 ) + p r l ( 厶一1 ) + + 矿p 七( a 。一1 ) ) o ( a 一1 ) 】 b 1 = a o = 铂( 山) + l ( 山) + + 矿住( 山) ， 岛一1 = a 。一2 = r 0 ( a n 一2 ) + p r l ( a 。一2 ) + + p 七“( a 一2 ) 则由g r a y 映射定义( 2 1 ) ，可验证， = ( 岛) = ( a 一1 ) o ( a 。1 ) ， 0 2 n 一1 = o ( o p + 1 ) 竹+ ( n 一1 ) ：= 7 七( a 。一1 ) o ( 7 o ( 0 ) 7 _ 1 ( a 。一1 ) or 1 ( o ) 7 2 ( a 。一1 ) o ) o7 o ( 4 。一1 ) = 张( 厶一1 ) o 绚( a 1 ) ， 6 j d = 口加一1 而c 0 = 口2 。1 故6 ；0 = c 0 6 l = 弦( 岛) = “( a ) ，锄= ( 山) ，而 c 1 = 口o ，6 1 = 知，故b l = c 1 故c n 一1 = k 一1 故6 n = 一1 = a 一2 = 8 ( 叻+ o ) n + ( 。一2 ) = 弦( a n 一2 ) ， k 一1 = 6 ( o ，片o ) n + ( n 1 )= 飞( 上k 1 ) = 强( a n 一2 ) ， ( = 0 鼽一l = 口( o 舛2 ) n + ( t l 一1 )= “( a 一1 ) o2 r 0 ( 厶一1 ) ， k = 6 ( o 什1 ) n + o = 取( b 0 ) or 0 ( 玩) = 他( a 一1 ) o 伯( a 1 ) o 翔( a n 一1 ) = 7 七( k 1 ) o2 伯( k 一1 ) ， 6 硕士学位论文 m a s t e r st h e s i s 故k + 1 = c ，l + 1 c r 汁12c k2o ( o 1 ) n + o k + 1 = 6 ( 吻+ 1 ) ，l + 1 = 仉( 山) or 0 ( a o ) = “( b 1 ) 0 珊( b 1 ) = ( 凡) o 约( a o ) ， 6 ( p 七一1 ) n = 6 l ( ，丘一l 一1 ) p + ( p 一1 ) 】n + o = ( b o ) o 【r o ( p b l 1 ) 7 1 ( 风) o7 1 ( ( 矿一1 ) r 2 ( b 0 ) 0 7 2 ( 矿一一1 ) r 3 ( 岛) o o “一2 ( 矿一1 ) n 一1 ( 岛) 】 o p 一1 ) 绚( 疡) = 仉( b o ) o ( p 一1 ) r 1 ( 岛) o ( p 一1 ) r 2 ( 岛) o o ( p 一1 ) 7 - 七一1 ( b o ) o ( p 一1 ) r o ( b o ) = ( a n 一1 ) or o ( a 。一1 ) 0 1 ) n ( a 。一】) op 一1 ) 7 2 ( a 一】) o 一1 ) 一1 ( a 。一1 ) o 一1 ) r o ( 4 。一1 ) = 如( a 。一】) o 一1 ) f q ( a 。一】) or 2 ( 4 。一】) g + r 七一】( 4 ，。1 ) 其中矿“= o ，且 而 矿一1 1 = ( p 一1 ) + ( p 一1 ) p + + ( p 一1 ) p 七一1 + ( 一1 ) 矿+ p 七一1 = p 一1 ) 十0 一1 ) p + ( p 一1 ) p 2 + + 一1 ) p 七 c ( p k 1 ) n = o ( p 七+ 1 ) n 1 = ( a 1 ) o 一1 ) 【7 1 ( a 一1 ) o7 2 ( 如一1 ) o o 巩一l ( a 一1 ) 】 故七一1 ) n = 6 铲一1 ) 。 h 一228 f 白一l 1 h 件函一i ) 加+ m 一2 j = “( a 一2 ) o 瞰矿一1 ) 7 1 ( 九一2 ) o7 1 ( ( 矿- 一1 ) 7 2 ( a 一2 ) o r 2 ( 矿一1 ) 您( a 一2 ) o o 弦一2 p 七一1 ) “一1 ( a 。一2 ) j o 一1 ) r o ( a 一2 ) = ( a 俨2 ) o0 1 ) r 1 ( a 一2 ) o 一1 ) r 2 ( a n 一2 ) o o 扣一1 ) “一1 ( a 一2 ) $ 妇一1 ) ( a 。一2 ) = 7 七( 月n 一2 ) o ( p 一1 ) p 0 ( k 一2 ) o7 - 1 ( a 。一2 ) o7 2 ( a 。一2 ) 0 7 七一1 ( 4 。一2 ) 】 7 而 峪。一1 = ( 鼠一1 ) o ( p 一1 ) r 0 ( 铱一1 ) or 1 ( 风一1 ) o7 2 ( 风一1 ) o o n 一1 ( 岛一1 ) 】 = ( a 。一2 ) o ( p 一1 ) 【r o ( a 。一2 ) or 1 ( a 。一2 ) or 2 ( a 一2 ) o o n 一1 ( a 。一2 ) j 故勺t 。1 = t 。一2 = i 。一1 通过验证，可得 6 t = q ( i = o ，1 ，p 七n 一1 ) ， 故口a ( a ) = 7 ( a ) ，u = 7 咖得证 定理2 2 4z p 上的长为礼的码c 为一个( 1 + p 七) 一循环码当且仅当其g r a y 像痧( c ) 是z p 上的指数为矿，长度为矿n 的次准循环码 证明若c 为( 1 + 矿) 一循环码，则由咖叭= 7 咖，( 其中a = 1 + 矿) ，则 7 ( 妒( g ) ) = 咖叭( g ) = 咖( c ) 故( c ) 为次准循环码 反之，若9 ( g ) 为次准循环码，( 叭( c ) ) = 叭( c ) = 7 ( 妒( c ) ) = 砂( c ) ，又因为 驴是单射，故叭( c ) = c ，g 为( 1 + p 南) 一循环码 关于一般循环码的g r a y 像，我们有下列命题： 命题2 2 5 设口是z 斗- 到z + ，上的循环置换，则有枷= 盯印。( 其中，仃印。 见2 1 1 证明设任意 a = ( ，a 1 ，a 一1 ) z + t ， 则 ( a o ，a 1 ，a 一1 ) = ( a l ，山，a 1 ，a 。一2 ) ， 设 ( a 。“a o ，a 1 一，如一2 ) = ( 岛，岛，鼠一1 ) = ( 6 0 ，b 1 ，k 一l k ，k + 1 ，6 2 。一l 幻。，k + 1 ，b 。一1 l ，1 6 白一1 ) 。，6 ( p 一1 ) 。+ 1 ， n 一1 ) 咖( 山，a 1 ，a 。一1 ) = ( 口0 ，口1 ，一1 l ，+ 1 ， 口2 n 一1 1 0 2 n ，口2 n + 1 ，口鼽一1 i ，l 口。上一1 ) n ，口( p 七一1 ) ，i + 1 ，e 矿n 一1 ) ， 由g r a y 映射的定义，可验证 玩n = n “+ 1 ) n 一1 ，6 ( t 卅j ) n + j = d o p + 占) n + j 一1 8 硕士学位论文 m a s t e r st h e s i s 其中 0 歹几一1 ，o s p 一1 ，0si p 七一1 1 ， 即西u = 盯劬西 定理2 2 6 环z 。上长度为n 的码为循环码的充分必要条件是它的g r a y 像 是z p 上长度为礼矿指数为p 七的准循环码 证明若c 为z p 上长为礼的循环码，则仃( c ) = c ，由命题2 2 5 ，盯印( c ) = 加( c ) = 咖( c ) ，故咖( c ) 为长度为礼矿指数为矿上的准循环码 反之，若c 的g r a y 像( c ) 是长度为矿指数为矿的准循环码，则盯却( c ) = ( c ) ，由上命题口。p 砂( c ) = 加( c ) = 砂( ( c ) ) ，又因为为单射，故u ( g ) = c ，即 c 为循环码 关于负循环码的g r a y 像，我们有下列命题： 命题2 2 7 设 为z 蚤+ ，到z + 。上的负循环置换，则有加= p p 。咖( 其中 ，声却见2 1 ) 证明设 a = ( 山，a l ，一，a 。一1 ) z + ， u 。( ，a 1 ，a 。1 ) = ( 一a 吨凡，a ，a 一2 ) = ( b 0 ，b 1 ，- ，风一1 ) ， ( 一a 。一1 ，山，a 1 ，厶一2 ) = 妒( b o ，b 1 ，既一1 ) = ( 6 0 ，6 1 ，一，k 一1 1 6 n ，6 n + 1 ，6 2 。一，1 6 2 。，6 2 。+ 1 ，b 3 。一1 i ， 1 6 一1 h ，6 0 一1 ) 。+ 1 ，6 矿。一1 ) ( 凡，a ，a 1 ) = ( o o ，d 1 ，o n 一1 i ，o n + 1 ，口2 n 一1 i n 2 n ，0 2 n + 1 ，口轨一1 l ， ，f n ( p 七一1 ) ，l ，o ( p 七一1 ) n + l ，口p 七n 1 ) 注意到 风= 一厶一1 = 一( r 0 ( a 一1 ) + p r l ( a 一1 ) + 十矿7 詹( a 一1 ) = 一r 0 ( 厶一1 ) 一1 ( 厶一1 ) 一一p 七7 七( a 。一1 ) ， 由g r a y 映射的定义，可得 i6 ( 咖+ ) n + j = 口( i 升e ) t l + d 一1 ) ， j o ； 6 ( 旬卜卜) n 卅= 一o ( 甸叶1 ) n l ， 歹= o ，= o l6 ( 咖托) n + j = 一o ( p + ) n + ( 。一1 ) ，歹= o ，o ； 得证 9 硕士学位论文 m a s t e r st h e s j s 定理2 2 8 环z p 上长度为礼的码为负循环码的充分必要条件为它的g r a y 像为z p 上的长度为印七指数为矿的准负循环码 证明若c 为硌t + - 上长为死的负循环码，则口( c ) = g ，由命题2 2 7 ，p 印咖( c ) = 加。( c ) = ( c ) ，故( c ) 为长度为唧k ，指数为矿上的准负循环码 反之，若c 的g r a y 像咖( g ) 是长度印七为指数为p 七的准负循环码，即p 矿咖( g ) = ( c ) ，由命题2 2 7 ，p 却。( c ) = 加( c ) = ( t j ( c ) ) ，因西为单射，故口( g ) = c ，即 c 为负循环码 1 0 硕士学位论文 【a s t e r st h e s i s 第三章 环弛z 上常循环码与( 1 + p 七) 一循环码的生成元 3 1 环z p 上常循环码的生成元 引理3 1 1 ( h e n s e l sl e 衄a ) 【1 0 】设r 是一个有限交换链环，9 兄吲是首一多 项式f 是r 的剩余域，假设存在 ，厶， f h 是首一，两两互素的多项 式使得耍= ，2 那么存在9 1 ，夕2 ，吼z p 【z 】是首一的两两互素的多项 式使得夕= 夕l 夕2 吼，并且盈= 五 由引理3 1 1 ，我们有如下定理： 定理3 1 2 记号如上，设z 口t + - 表示模矿+ 1 剩余环，并且g c d ( 礼，p ) = 1 a 琢”则存在9 1 ，9 2 ，吼z p m 是首一的两两互素的基本不可约多项式使得 z n a = 9 1 9 2 吼，并且磊= 五 证明由于入可逆，故可设a = 盘+ p p ，这里，芦由于扩一( a + p 卢) = z ”一a ，而且由于g c d ( 礼，p ) = 1 ，我们有( z “一a ) 7 = n 扩。o ，因此有 ( 一一1 ) ( z “一a ) + ( n 一1 及一1 z ) ( n z “一1 ) = 1 所以多项式扩一口在f 上没有重根，从而有限域f 上的多项式z “一a 可以分解可 以分解成两两互素的首一不可约多项式的乘积，设 孑两= 孑_ 二_ 币i i 丽= z “一q = ( z ) 尼( z ) ( z ) 由引理3 1 1 ，存在r 上的两两互素的多项式夕1 ) ，夕2 ( z ) ，仉( z ) 使得 z “一a = 夕1 ( z ) ，夕2 ( z ) ，9 。( z ) ， 并且；丽= 五( z ) 由于五( z ) 是f 上的不可约多项式，故吼( z ) 是r 上的不可约多 项式，即吼( z ) 是基本不可约多项式 对于任意交换环r 与整数1 ，通常可建立j 与其多项式环r 旧上的 对应 一1 ( 山，a 1 ，瓜一，) h a = o 当冗= z 。，= n ，可诱导出下列映射 p ：珞+ - 一硌州吲( 矿一1 ) ， n 1 p ( 山，a 1 ，厶一1 ) = 1 1 a + ( 矿一1 ) = o p ，：硌+ - 一孙+ ，( 矿一a ) ， p ( 山，a 1 ，a 1 ) = n 一1 a + ( 扩一入) ，( a 哆+ t ) = 0 下面我们讨论上的长为扎为奇数，p 为素数) 的常循环码的生成元 引理3 1 3 【1 1 】若，( z ) z p 州 叫是一个基本不可约多项式，则z p 【卅( ，( z ) ) 的理想为( o ) ，( 1 + ( ，( z ) ) ) ，( p + ( ，( z ) ) ) ，佃七十( ，( z ) ) ) 定理3 1 4 【1 2 】设c 是瓦t + ，上的长为n 的线性