（计算数学专业论文）剩余类环上的循环码与负循环码及其距离分布.pdf

中文摘要 线性码在编码，纠错码理论中有着重要的地位本文主要研究了在剩余类 环上的线性码的一些性质，得到了下面的一些主要结果 1 利用环直和分解的性质研究了( m 6 ) 上的循环码( 负，准循环码) 与其直和项上循环码( 负，准循环码) 之间的关系；进一步通过定义了与环 的直和项有相同特征的剩余类环之间的同构映射妒，得到了在映射矽作用下 环z 赢上的码与其外直和项上码的关系；应用g r a y 映射d ：红+ _ 乙，得到 了一般化的中的足循环码与其外直和项中的准循环码之间的关系；同时 得到了z 赢上存在自对偶码的充分必要条件 2 利用g r a y 映射移的定义，给出了乃+ 。上的( 1 一p k ) - 循环码与露上 指标为p 1 长度为p k n 的准循环码的关系；同时定义了乃一霹n 新的映 射矽，并且研究了在它的作用下准循环码和循环码的关系 3 首先引入了双链环的概念，研究了哆+ u 昂t 上长度为矿的循环码与负 循环码的关系，得到长度为p 8 的负循环码是双链环( 硌+ u 砟t ) k 】( + 1 ) 的 理想；利用链环的性质我们研究了双链上的负循环码的h a m m i n g 距离分布；证 明了当且仅当p = 2 时，0 t + u 0 - 上存在自对偶码；同时，也得n t0 t + u 纬- 上长度为p s 的双链上的循环码的h a m m i n g 距离分布 关键词 负循环码，* 循环码，直和分解，双链环，h a m m i n g 距离分布，自对偶码 a b s t r a c t ( 英文摘要) l i n e a rc o d e sp l a ya l li m p o r t a n tr o l ei nb o t hc o d i n gt h e o r ya n dd e c o d et h e - o r y i nt h i sd i s s e r t a t i o n ，w ei n v e s t i g a t et h ep r o p e r t i e so fl i n e a rc o d e so v e rd i f f e r - e n tr e s i d u ec l a s sr i n g ，t h em a i nr e s u l t sa r ea sf o l l o w s ： 1 t h er e l a t i o nb e t w e e nc y c l i cc o d e s ( n e g a c y c l i c ，q u a s i c y c l i cc o d e s ) o v e r z m ( m 6 ) a n dc y c h cc o d e s ( n e g a c y c l i c ，q u a s p c y c l i cc o d e s ) o v e rt h e k sd i r e c t s u m m a n di ss t u d i e db ym a k i n gu s eo ft h er i n gd i r e c ts u m m a n dd e c o m p o s i t i o n m o r e o v e r ，t h er e l a t i o nb e t w e e nc o d e so v e r a n dt h er i n g sw h i c hh a v et h e s a m ec h a r a c t e r i s t i c so fz m sd i r e c ts u m m a n di sm s oi n v e s t i g a t e db yd e f i n i n gt h e i s o m o r p h i s mm a p p i n g 妒o f t ot h er i n g sw h i c hh a v et h es a m ec h a r a c t e r i s t i c so f z m sd i r e c ts u m m a n d m e a n w h i l e ，a p p l y i n gt h ed e f i n i t i o no ft h eg r a ym a p p i n g 口：z 1 _ 磊，t h eg e n e r a l l yr e l a t i o nb e t w e e n ) , - c y c l i cc o d e so v e rz 赢a n dt h e q u a s i c y c l i cc o d e so v e rr i n g sw h i c hh a v et h es a m ec h a r a c t e r i s t i c so fz 毒sd i r e c t s u m m a n di sg i v e n a tt h es a m et i m e ，n 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 sf o rt h e e x i s t e n c eo fs e l f - d u a lc o d e so v e rz ma r eo b t a i n e d 2 a p p l y i n gt h ec o n c e p t 彩o fg r a ym a p ，t h er e l a t i o nb e t w e e nc y c l i cc o d e s o v e r 绉+ la n dt h eq u a s i c y c l i cc o d e so fi n d e x 矿a n dl e n g t hp k no v e r 嚯 i sg a v i n a tt h es a j i i l et i m e ，w ei n t r o d u c em a p 妒o n 琴_ 霹na n ds t u d yt h e r e l a t i o nb e t w e e nn e g a c y c l i cc o d e sa n dc y c l i cc o d e s 3 t h ec o n c e p to fd o u b l ec h a i nr i n g si sg i v e na tf i r s t w ei n v e s t i g a t e n e g a c y c l i cc o d e sa n dc y c l i cc o d e so fl e n g t hp 8o v e rt h er i n g 昂+ u 昂k ，p r o v e t h a tn e g a c y c l i cc o d e so fl e n g t h 矿a r ep r e c i s e l yt h ei d e a l so ft h ed o u b l ec h a i n r i n g ( 0 k + u o k ) 【z 】( 矿。+ 1 ) ，a n dg i v et h e i rh a m m i n gd i s t a n c ed i s t r i b u t i o n s o nt h ed o u b l ec h m n sb yt h ec h a r a c t r i c so fc h a i nr i n g s w ef i n dt h a tt h e r ee x i s t s e l f - d u a lc o d e si fa n do n l yi fp = 2 a tt h es a m et i m e ，w eo b t a i nt h eh a m m i n g d i s t a n c ed i s t r i b u t i o n so fc y c l i cc o d e so nt h ed o u b l ec h a i n sw i t hl e n g t hp 8 k e y w o r d s n e g a c y c l i cc o d e s ，d i r e c ts u m m a n d s ，d o u b l ec h a i nt i n g s ，h a m m i n gd i s t a n c e d i s t r i b u t i o n s ，s e l f - d u a lc o d e s 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学 交有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人 龟许论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或 帮分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存和汇编本学位论文。同时授权中国科学技术信息研究所等机构 每本学位论文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：茹羞送指导教师签名：主! 塑 7 1 年月阻日弦o c | 年6 月j - 日 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢 的地方外，本论文不包含其他人已经发表或撰写过的研究成果，也 不包含为获得西北大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示谢意。 学位论文作者签名：1 著名l 夯 沪7 年月，p 日 两北大学硕士学位论文 1 1 引言 第一章绪论 1 9 4 8 年s h a n n o n 在他的开创性论文“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 ”中提出了信道编码定理，为纠错码的发展奠定了理论基础从此以 后，h a m m i n g ，b o s e ，m a c w i l l i a m s 等编码专家先后创造性地提出了一系列设计 好码和有效的译码方法，使编码理论取得了长足的发展，也使编码理论越来越 受到通信和数学工作者，特别是代数学家的青睐。在很长一段时期内，编码学家 们主要围绕b e r l e k a m p 列举的编码理论的三大主要问题而展开讨论f 1 】 这三大 问题是： 1 最佳码的性能如何? 2 怎样才能设计出好码? 3 如何对这些好的码进行译码? 在编码理论的发展过程中人们最早提出的一个问题是如何寻找完备码 我们可以将有限域昂上一个码长为礼的码看做矢量空间y n ( f p ) 的一个子 集_ 【言1 ，言2 ，7 m ) ，对于某个正整数e ，如果环绕这m 个码字的半径为e 的汉明球体，无交叠地填满y n ( f p ) 空间，就称这个码是完备的( 或者密合填充 的) 到1 9 5 0 年为止，科学家们已经发现了几种完备码【2 】，到2 0 世纪7 0 年代 编码学家们发现除了已发现的完备码以外不存在其他的完备码【3 】，同时编码专 家也得到了一些值得注意的好码，如：j e 7 c 日码，r m 码，卷积码【4 】由于信息 的传输不可能在无噪信道中传播，所以怎样对这些好码进行译码又成为了一个 重要的课题当然对于较少的码我们可以通过伴随式进行译码，但是对于较大 的码这种译码方法却不适用于是人们耗费了大量的精力去寻找大型码的有效 译码算法，不管那种译码算法都是集中于码的结构和码字之间距离的研究，所 以，本文主要对剩余类环上码的结构和码字的h a m m i n g 距离进行研究，进一步 完善有限环上的编码理论，对纠错码的发展也有一定的意义首先介绍一下有 】 第一章绪论 限环上编码理论已取得的一些的成果 h a i o d i n h 等利用有限链环的特点研究了有限域艮上长为矿的循环 码和负循环码 5 - s , l v , 2 0 , e l , 3 0 ，并且给出了码的h a m m m i n g 重量分布多项式； p r a m o d ，k a m v a r 和s e r g i o 利用不可约多项式的性质研究了磊m 上循环码与 负循环码，利用g r a y 映射研究了知+ - 上的线性循环码与磊上指标为p 肛1 长度为p 屉几的准循环码之间的关系【8 】；j a c q u e sw o l f m a n n 利用g r a y 映射研究 了刃_ 砖n 上的循环码负循环码之间的关系【纠；y o u n g j uc h o i e 和s t e v e n t d o u g h e r t y 研究了环汤m + 口易m + 汤m4 - ，y 忍m 上的白对偶码与四元数 幺模格的关系【2 3 】，同时得到了2 仇上的码的重量分布；a b o n n e c a z a 等研究 了乃+ u f 2 上的第二、五类型码与对偶码在文献 1 2 - - 1 4 , 3 0 , 3 7 ；b s u n d a rr a j a n 和m u s i d d i q u i 利用中国剩余定理与离散傅立叶变换对上的循环码和对 偶码进行了研究，给出了上的循环码的直和分解，并且讨论了它上不存在 自对偶码的充分必要条件【15 】；j f q i a n ，l n z h a n g ，s x z h u 定义了马+ u f 2 的g r a y 映射，证明了尼+ u f 2 上长度为奇数的( 1 + u ) 一循环码在g r a y 映 射作用下是尼上长度为2 几的循环码【1 6 】；m c v a m a r r a ，f r n e m e n z o 定义 了硌+ 乱哆上的g r a y 映射，证明了哆+ u 硌上长度为佗的( 1 一钍) 一循 环码在g r a y 映射作用下是珞上长度为p k 礼指标为p 砖一1 的准循环码【1 7 i 本文的主要结构为：在第二章利用环直和分解的性质研究了( m 6 ) 上的循环码( 负，准循环码) 与其直和项上循环码( 负，准循环码) 之间的关系， 同时给出了( m 6 ) 上存在自对偶码的一个充分必要条件引入了与 环的直和项有相同特征的剩余类环之间的同构映射矽，得到了在映射妒作用 下环与其外直和项之间码的关系；同时应用了g r a y 映射移：磊t + - _ 磊的 概念，得到了一般化的中的a 一循环码与环的外直和项中的准循环码之 间的关系第三章主要是利用了g r a y 映射的定义并给出了召+ ，一嚯上 的1 一p 惫循环码与玖的关系方框图，定义了乃_ 劈付上的一种新映射妒， 并且讨论了在它的作用下准循环码和循环码的关系第四章首先引入了双链环 的概念，进一步研究了哆+ 钍硌上长度为p 3 的循环码与负循环码，得到长 2 西北大学硕士学位论文 度为p 8 的负循环码是双链环的理想，利用链环的性质我们研究了这类负循环 码的h a m m i n g 距离分布，当且仅当p = 2 时，昂t + 乱0 * 上存在唯一的自对偶 码；同时，我们也得到了长度为p 5 的循环码的h a m m i n g 距离分布第五章主要 总结一下本文，给出进一步值得研究的几个问题 1 2 预备知识 表示模m ( m 6 ) 的剩余类环盔上的玖变换为： v a ( a l ，a 2 ，a n - 1 ) = ( a a ，l 一1 ，a l ，a n - 2 ) 当a = 1 时，1 7 1 即为编上的 循环变换；当a = m 一1 时，1 r n 一1 即为上的负循环变换如果码c 编， 玖( c ) = c 时，则称c 为z m 上的长为礼的入一循环码对于任意的整数n ，s ，定 义盯圆8 ：獬一獬，即口0 8 ：( 豕1 ) f 糸2 ) i l 糸8 ) ) h ( 口( 承1 ) ) i 口( 糸2 ) ) l l 盯( 万( 8 ) ) ) ， 其中糸) 编，扩是砺一编的循环变换若码c 编，口o8 ( c ) = c ，则称c 是指标为8 长为s n 的准循环码，下面我们给出环的直和的概念和环的直和的 一些性质 定义1 1 1 1 4 0 l 设r 1 ，r 2 ，r 是环r 的1 1 个理想如果 a ) r = r 1 + r 2 + + ； 2 ) r 中每个元素表为r 1 ，r 2 ，r 中元素相加时，表示法唯一， 则称r 是子环兄1 ，尼，的内直和，简称直和，并记为r = r lor 2o 。或r = 。尼 i = 1 例1 1 1 模6 剩余类环磊是其理想r 1 = 石，5 ) 与r 2 = 西，夏，石) 的内直 和，即z 6 = r xor 2 引理1 1 1 f 柏】设r i ( i = 1 ，2 ，佗) 是环r 的理想，且r = of 尼，则此 和是直和的充分必要条件是，零元素只能表示成0 = 0 + 0 + + 0 引理1 1 2 1 4 0 l 如引理1 1 1 所设，则和r = o f 尼是直和的充分必要条 石 件是：忍n ( r 1 + + 昆一1 + 尼+ 1 + + 心) = 0 ，i = 1 ，2 ，佗 定义1 1 2 1 4 0 1 设是环r 的一个理想如果存在环r 中的理想7 3 第一章绪论 使r = n + n 7 ，则称是环r 的一个直和项 引理1 1 3 1 4 0 如果环r 的理想是环r 的一个直和项，则的理想也 是环r 的理想 引理1 1 4 【加l 设r = 。r ，若m 里r ，i = 1 ，2 ，m ，则m 塑r i = l i = 1 反之，设n 里r ，若r 中有单位元时存在她笪见使n = f 眦 i = 1 引理1 1 5 1 4 0 设r 是一个特征为几的环，如果n = 亿1 n 2 ，且1 ，他2 ) = 1 ，则 存在r 的理想冗1 和r 2 使r = r 1 0 r 2 ，而且其中c h a r r l = n l ，c h a r r 2 = 佗2 引理1 1 6 4 0 】设环r 的特征是n ，且n = p ：1 p ；。p ：e ，p i 是互异素数，k i 1 ，i = 1 ，2 ，e 则存在环r 的理想见，其特征为p k , ，并且r = 。危 定义1 1 3 【2 】如果c 是一个循环码，那么c 中一个最低次非零多项式被称 为它的一个生成多项式，通常用9 ( z ) 表示生成多项式 定理1 1 1 1 2 】1 ) 如果c 是有限域f 上一个( 扎，k ) 循环码，则它的生成多项 式是z n 一1 的一个因式而矢量才= ( c o ，c 1 ，a n 一1 ) c 当且仅当它对应的 生成函数c ( x ) = c o + c l x + + c m 一1 z 俨1 能够被c 的生成多项式整除如果 用k 表示c 的维数，则k = 扎一d e g ( g ( x ) ) 2 ) 反之，如果9 ( z ) 是x 几一1 的一个因式，则存在一个以夕( 正) 为生成多项 式，且k = n d e g ( 夕( z ) ) 的( 佗，k ) 循环码，该码中的所有矢量( c o ，e l ，a n 一1 ) 的生成函数都能被g ( z ) 整除我们容易将定义1 1 3 与定理1 1 1 推广到有限 环上，这个推广过程是平凡的，在下面的行文中我们将直接引用 4 两北大学硕士学位论文 第二章上的线性码 2 1z m 上的循环码和负循环码 设表示模m ( m = p ：1 p 耋2 砖，其中p i 是互异素数，觑1 ，i = 1 ，2 ，e ) 的剩余类环首先，对一些符号进行约定：r 竹= ( c o ，c l ，一1 ) ，其 中q z m ，i1 1 _ 0 ，1 ，n 一1 ，r 旧= m ( 护- 1 ) ，尼是环的理想，碍= ( a o ，a l ，a n _ 1 ) ，其中a i 忌，i = 0 ，1 ，n 一1 ，昆m = 尼( 扩一1 ) ，i = 1 ，2 ，e ，下文为叙述方便记r 中的单位元为1 i 设p ：r x ( 扩一1 ) _ 酽 的自然映射p ：( c o + c l x + + 一1 x n 一1 ) h ( c o ，c l ，一1 ) ，则显然p 是的 同构映射 例2 1 1 模6 剩余类环磊是理想r 1 = 【_ ，研与r 2 = 币，乏趸) 不难发现磊中的单位元就是“l ”，r 1 中的单位元是j ，r 2 中的单位元 是虿由前面的约定，则有下面的结论 命题2 1 1 若尼塑z 击，则忍m 里r m ，其中i = 1 ，2 ，e 证明：对于任意的g ( x ) = g o + g l x + + g n 一1 x n 一1 r 几，任意的r i ( x ) = r i o + r i l x + + r i 礼一1 x n 一1 r 7 ，有夕( z ) 7 ) = c o + c l x + + c n 一1 x “一1 ，其 n 一1 中q = j ，k = 0 j + k = i ( m o dn ) 1 ，2 ，e g j r k ，因为忍璺，缈，r k 尼，所以尼m 塑r m ，i = 例2 1 2 由例2 1 1 的条件容易发现尼f z j 塑r m ，i = 1 ，2 定理2 1 2 若码c 是舻中的循环码，则存在研中的循环码已，其 中i = 1 ，2 ，e ，使得c = of 岛 证明：因为码c 是冗n 中的循环码，即码c 是有r z 】中的多项式夕( z ) ，( 其 中夕( z ) lx n 一1 ) ) 生成的理想，即c = ( 9 ( z ) ) ，关键是证明白( z ) ) = 。( n ( z ) ) ， = 1 e r i ( x ) 冗 成立，其中n ( z ) l ( 1 i z n 一1 t ) ，现在就来证明白( z ) ) = 。( 亿( z ) ) 是成立的首先证明对任意的g ( x ) r n 都可以表示成n ( z ) 研的 5 第二章赢卜的线性码 直和，由引理1 1 3 与命题2 1 1 很容易得到夕 ) = 。n 扛) ，下面考 i = i r 虑r i ( x ) l ( 1 t 扩一l t ) 是否也成立，这个回答是肯定的设扩一1 = 毋 ) ， i = 1 1 ，那么夕( z ) = 彭( z ) ，0 磁冬，只要证明9 ( z ) = 夕1 ( z ) 9 2 ( z ) 的情形成 i = 1 e ee 立即可g i ( x ) = 。( z ) ，i = 1 ，2 ，则夕( z ) = ( 。7 1 j ( z ) ) ( 。r 巧( z ) ) ， 假设r i j ( x ) t ( 1 歹z n 一1 j ) ，则有1 j 扩一l j = q a x ) r i a x ) + 吃( z ) ，r 0 ( z ) 0 ，d e g ( r ：j ( z ) | ) d e g ( r i j ( x ) ) ，即 z n 一1 = 。l j x n 一1 j = 。劬( z ) ) + r 0 ( z )z o - j 。 o j = l j = l ee e = ( 。劬( z ) ) ( 。( z ) ) + 。r 易( z ) j = lj - - 1 j = l ee = 。劬( z ) 仇( z ) + 。屹( z ) e 显然。r 易( z ) 0 ，这与g ( z ) l ( 扩一1 ) 相矛盾，所以r i ( z ) l ( 1 i x 7 1 1 i ) 成立，反 之容易验证对任意的n ( z ) i ( 1 t 扩一l i ) ，由引理1 1 4 可以得到。 ) i ( 扩一 j = l e 1 ) ，故码c = 。g 例2 1 3 霞老：6 ，礼：3 ，c ：( z 2 + z + 1 ) r 【z 】，r 【z 】：b 】( z 3 1 ) ， 则码c = c 1 0 q ，其中c 1 = ( 5 x 2 + 孙+ 5 ) 是r 1 上的循环码，已= ( 如2 + b + 虿) 是r 2 上的循环码这是容易验证的 定理2 1 3 若码c 是舻的负( 准) 循环码，则存在毋中的负( 准) 循环 码已，其中i = l ，2 ，e ，使得c = 。已 例2 1 4 设m = 6 ，n = 3 ，负循环码c = ( 2 + 5 x + 1 ) r ，r ，= 磊l z j ( z 3 + 1 ) ，则码c = c 1oc 2 ，其中c 1 = ( k 2 + k - i - 5 ) 是r i 上的负循环 码，岛= ( k 2 + b + 趸) 是冗2 上的负循环码 注：并且若限定一定的顺序表示方法也是唯一的由引理1 1 4 ，引理1 1 6 与命题2 1 1 容易得到下面的结论 6 两北大学硕士学位论文 定理2 1 4z 南是模m 的剩余类环且m = 硝1 砖2 p 争，p i 是互异素数， k i 1 ( i = 1 ，2 ，e ) ，则舻中的循环码( 负，准循环码) 可以唯一的分解 为砬中的循环码( 负，准循环码) 的直和 不难发现环的直和分解与它的特征有密切的关系由例2 1 1 我们很容 易得到磊的理想r 1 = 石，习，r 2 = - 乏弓与它们有相同特征的整环历， z 3 之间有同构映射也：r a _ 磊+ 1 = l ，2 ) ，即妒1 ( 虿) = l ，妒1 ( 石) = o ；妒2 ( 五) = 1 ，矽2 ( 石) = 0 ，矽2 ( 互) = 2 ，容易验证也是也：r 1 _ 历+ 1 ( i = l ，2 ) 的同构映射( 注 意上面的历，磊是分别是模2 ，3 运算，而r 1 与忌则是模6 运算) 由此就可 以定义妒：z 6 = ( 妒1 ，矽2 ) 即对于 c a z 6 ，a = a loa 2 ，a l r 1 ，a 2 r 2 ，妒( o ) = 渺1 ( n 1 ) ，妒2 ( 口2 ) ) ，为了下文叙述方便我们记：渺1 1 ) ，t b 2 ( a 2 ) ) = 妒i ( a 1 ) o 妒2 ( 0 2 ) ， 并称其为外直和容易验证砂就是我们满足条件的同构映射 下面给出剩余类环m 6 ) 与其直和项有相同特征的环之间的同构映 射矽同时可以发现定义矽的关键是找到环的直和项中的单位元，首先，要证 明环的直和项中是否有单位元，我们有下面定理 定理2 1 5 设环r 的特征是m 且m = p ：1 p 争谚( e l 是互异素数， 1 ，i = 1 ，2 ，e ) ，忍是环r 的理想，其特征为毋，并且r = o 忌，则忍 i = 1 中存在唯一的单位元 ee 证明：存在性，由环的理想的性质可知昆= ( 孝) = 似i i 孝，k j ij i ee 锄；) ，因为 ，孝) = 1 ，存在s ，z ( o ) r ，满足谚+ 孝三1 ( j j i e e eee m 。dm ) ，即印毋+ n 孝穆兰孝( r o o d m ) ，所以t ( 孝) 2 三 j tj j # ij tj i ee i i 考( r o o dm ) ，两边同时乘以k | 【o ，l ，p 争一1 ) 得舰( 孝) 2 兰 j # ij t 七穆( 1 1 1 0 dm ) ，故l i = t 孝，i = 1 ，2 ， e j # ij i ee 唯一性，假设不唯一，则存在t i 孝是忍的单位元，则亡7 孝= 7 第二章z m 上的线性码 ( t 孝) ( 毋) = 孝所以，r 中有唯一的单位元 j tj ij i 下而给出寻找忍中单位元的算法 算法2 1 1 ，k z t 。) r t & ：计算( 南孝) 2 三后孝( r o o dm ) ，k z 毒；并对其进行标号记为： j ij t a l ，l z + ，1 l p 昆：计算a i a j 兰a i ( r o o dm ) 其中i ，j 为上面不同的2 的值，对任意的j 都有a i a j 兰a i ( m o dm ) 成立，则输出a i 定义2 1 1 设的特征是m 的剩余类环，m = p ：1 p ；2 建e ，忍是 环的理想，其特征为毋，并且= 。忍，一o 。( m 产孝) i = 1i = 1 e 的映射妒满足：妒= ( 妒1 ，妒2 ，c e ) ，其中p i 是互异素数，也 i i 孝) = 1 ， j t ee 讹( 脘孝( m 。d i n ) ) = k 容易验证矽是_ 。nz 矗( 盹= 硝) n n n n j 判 i = l 射 例2 1 5z 1 2 的理想r 1 = ( 3 ) ，r 2 = ( 2 2 ) 与它们有相同特征的整环易。， 历之间有同构映射矽1 ：r 1 _ 易：，即l d l ( 9 ) = 1 ，矽1 ( 石) = 0 ，妒1 ( 石) = 2 ，妒1 ( j ) = 3 ；矽2 ：r 2 ，磊，妒2 ( 西) = 1 ，妒2 ( 西) = 0 ，妒2 ( 趸) = 2 妒满h i ：矽= ( 妒1 ，妒2 ) ，我f i 、 容易验证砂是z 1 2 一汤。qz 3 的同构映射 由定义2 1 1 进一步将妒推广到形_ 。瑶。上，对任意- - o - 4 , = ( a o ，a l ，a n - 1 ) r n ，存在- - o - l + = ( a i o ，a l l ，a i 凡一1 ) 毋，i = 1 ，2 ，e ， 满足_ a = 。_ a i ，矽( 言) = ( 妒1 ( 赢) ；妒2 ( 。- - - - 2 4 ) ；矽。( 瓦) ) ，他( 面) = ( 如( 口i o ) ，如( a i l ) ，识( n i m 一1 ) ) 定理2 1 6 若码c 是纭的循环码，m = p ：1 p 5 2 p ：c ，则码矽够) = 。已， 其中岛是纭中的循环码( i = 1 ，2 ，e ，m i = 毋，i = 1 ，2 ，e ，k i 1 ) 证明：由定理2 1 2 与引理1 1 6 可知码c 可以表示为兄( z = 1 ，2 ，e ) 8 旁 e 傅 七 e = 旁 。彬 = e 磁 算计& 两北大学硕士学位论文 的循环码的直和且表示方法是唯一的，又因为妒是r n _ q 碾的同构映 射，所以码c 在妒的作用下可表示成。的循环码的外直和；假设表示方法不 唯一，不妨设码c 在妒作用下可以表示成c = 。c 盹和c = 。，由 i = li = 1 引理1 1 2 与移是同构的可知这是不可能的，结论得证 定理2 1 7 若码c 是中的负( 准) 循环码且m = 硝1 p 争缱。， 则码矽够) = o 已，其中已是罨中的负( 准) 循环码( m i = 既k i ，i = i = 1 1 ，2 ，e ，k i 1 ) 一 定理2 1 8 设表示模m 的剩余类环( m = p ：1 p 争p ：c ，鼽是互异 素数，k i 2 ，i = 1 ，2 ，e ) 若码c 是中的x 循环码( 入= 。( 1 i p 争一1 1 t ) ) 则矽够) 是弦。中的i t p 争。1 t 循环码的外直和 证明：由定理2 1 2 与引理1 1 6 知码c 可以表示为冗 ( i = 1 ，2 ，e ) 的a ，- 循环码( x = 1 i 一毋_ 1 1 ) ，( i = 1 ，2 ，e ) 的直和，关键是验证a = 。x 是否成立，而a = 。x 成立是显然的，又因为妒是舻一。nz 巍 的同构映射，所以，码c 在妒的作用下可表示成碾中的入t 一循环码( 九= 1 一孝- 1 ) 的外直和 推论2 1 8 若k i = 2 ，i = 1 ，2 ，e 码c 是中的a 一循环码( a = 。( 1 i - - p i l i ) ) 则矽够) 是；中的1 一慨) 一循环码的外直和 i = 1 由定理2 1 8 可以直接得到此结论 在研究在映射妒作用下环与其外直和之间的码的关系时，需要回答的 是既然z 篡上的码与编；上的码之间有以上的结论，那么上的码的纠错能 力与缳上的码的纠错能力有什么样的关系呢? 有下面的定理 定理2 1 9 码c ，若已碾是码c 在妒作用下的外直和项， 则d ( c ，日) 5l m i n e d ( c i ，何) ) - 证明：因为码c 璺r n ，有( 定理2 1 6 ) 容易得到c t 塑瑶。，又因为妒 是同构映射，所以在妒的逆映射作用下已就与孵里r 唯一的理想相 对应，由引理1 1 3 可以得到叼塑c 从而就有d ( c ，日) 1 m 心i n 。 d ( c m t ，日) 】l 9 第二章z 。上的线性码 也就是存在一个码子c c 使得h ( c 7 ) = r a i n ， d ( ，日) ) 我们仅须取 出g 中重量最小的码子记为：，而在g ，0 i ) 中取出育码子就可以得 到c = 妒i - 1 ( 育) o o 蝎( 育) o 蜉1 ( ) o 蝴( 方) o o 蜉1 ( 育) 下面证明这个码子就是c 中h a m m i n g 重量最小的码子，假设不是c 中h a m m i n g 重量最小的码子，则存在码子c 是c 中h a m m i n g 重量最小的 码子，那么c 的非零分量的数目礼 h ( c ，) 有中零元素的分解的唯一性 知道必存在码子掣c t ，满足n ( c 1 7 ) 日( q ) 这显然是不可能的所以c 7 就 是c 中h a m m i n g 重量最小的码子 故d ( c ，日) 2 1 m i n e d ( c m i ，日) ) 由定理2 1 9 可以知道编中的码的纠错能力完全被它的外直和项的纠错 能力所决定，当然，由定理2 1 6 ，定理2 1 7 ，定理2 1 8 我们完全可以用熟悉的 码来构造编中的码，也可以用所熟悉的译码方法来对编中的码进行译码 下面我们进一步来研究兹中的对偶码与自对偶码 2 2 上的循环码和自对偶码 定义2 2 1 1 4 0 向量空间昂中的两个向量7 = 1 ，x 2 ，z n ) ，_ y = ( y l ，y 2 ，y n ) 的内积定义为( 7 才) = x l y l + z 2 秒1 + + x n y l 昂如 果( 7 寸) = 0 ，称叠，可正交 定义2 2 2 1 4 0 设c 是参数为h ，k 】的q 元线性码，即c 是昭的一个k 维 线性子空间，则c 上= 才叼对每个7 c ，( 刁彳) = o ) 叫做正交码；如 果c c 上称码c 为自正交码；如果c = c 上称码c 为自对偶码由上面的定 义容易给出上的正交码，自正交码，自对偶码的定义 定义2 2 3 1 4 0 1 设c 是罨中的m 元线性码，即c 是的一个线性子空 间，则c 上= 言z 嚣对每个言c ，( 刁7 ) = o ) 叫做正交码；如果c c 上 称码c 为自正交码；如果c = c 上称码c 为自对偶码 命题2 2 1 m 设r 式有限交换环，并且a ( x ) = a o + a l x + + 1 0 西北大学硕士学位论文 a n 一1 z n 一1 ，b ( x ) = b o + b l x + + b n - l x n 一1 r z 】 贝uo ( z ) 6 ( z ) 三0 ( m 。d ( z n + 1 ) ) 当且仅当言：( 口0 ，口1 ，口礼一1 ) 与言：( b o ，b 1 ，b n 一1 ) 和_ b 的所有负循环燹抉郡正燹 引理2 2 2 【3 7 】设，中非零线性码c 的码字个数为p 七，那么对偶码c 上 的个数为p l ，其中k + l = m 7 佗 引理2 2 3 1 3 7 设p t n ，p 是素数，并且c = ( 豆，p 扇，一一1 露，) 其 中f 0 日f m ， = 扩一1 ，磊= 生茅，i = 1 ，2 ，m 7 ，则c 上= ( 昂，p 不，7 一，矿。元) 其 中最= z d e g ( 或) 曩( 三) 证明：假定r 1 ，1si m 7 如果对于某些i ，r = 1 则结论是显然 的设c 1 = ( 元，p 露，p 2 岛一1 ，p m 一1 霸一1 ) 0 i ，j m 一1 ，当i + 1 m 7 - j + l 时，( z n 一1 ) i 或+ 1 ) 汐己，。+ 1 ) 7 ，当i + 1 = m 一j + l 时，p m 。ip i 却， 所以，( 磊+ 1 ) 己，一件1 ) 三o ( 1 1 2 。dz “一1 ) ，因此，c 1 至c 上孓因为，i c l l = 矿d e g f o p ( m - i ) d e g ，p d e g f ! = p t ，其中，t = i d e g r + 1 ，+ 1 = f o 由 。 t = 1 m 7 1 引理2 2 2 容易得到i c 上i = p 。，其中，z + k = m 7 佗容易得到k = ( m 7 一 i = 0 m ， i ) d e g f l + 1 因此，l = i d e g 只+ 1 = t 所以，c 1 = c 上 引理2 2 4 i a v l 设c = ( 再，p 曩，p m ，一1 露，) ，其中f o f l f 仇，= 扩一l ， 并且p t 扎，p 是素数则c 是自对偶码当且仅当i + j 兰1 ( m o dm 7 + 1 ) ，其 中( o i ，j m ，) 定理2 2 5 设c 是编中的m 元线性码，码c 为自对偶码，当且仅当矽( c ) 是觋中的自对偶码的外直和( 其中m i = p ，p i 互异为素数i = 1 ，2 ，e ) 证明：因为c 是编中的m 元线性码，所以c 鱼由定义2 2 3 与引 理2 2 4 ，知c = 妒f 1 ( c 1 ) o 矽i 1 ( 已) o o 蜉1 ( 巳) ，故妒够) = c 1 0 c 2 0 p c e ， 其中已里瑶；，i = 1 川2 一，e y nn 矽是编_ 。瑶；n n 构n n ，所以 对任意的言，_ b c ，( 言言) ：0 铮( 矽( 言) 妒( 言) ) = 0 ，故矽) 是编。中的 1 1 第二章z 。上的线性码 自正交码的外直和必要性得证由于砂是的同构映射，再由引理2 2 2 ，充分 性也容易得到 由定理2 2 5 与引理2 2 3 容易得到下面的结论 定理2 2 6 设码c z m ，m = p 铷5 p ：，g = ( 豆1 ，p i 置 i 2 ，露一1 曩七) ，其 中i = 1 ，2 ，e ，只o r l 尼七= 扩一1 i ，并且p 十n ，p 是素数则码c 是自对 偶码的充分必要条件为i + j 三1 ( r o o dk + 1 ) ，( 0 i ，j 七) 证明：步骤与引理2 2 2 类似，略去 对于一般的m = 前1 莲z 缱c ，其中k i 幻，i j ，z m 中的自对偶码存在 的充分必要条件有待于进一步的研究 1 2 西北大学硕士学位论文 第三章g r a y 映射在的应用 3 1g r a y 映射 设p 2 ( p 为素数) 七1 ，七z + ，我们先假定用“+ ”，“- ”表示务+ - 上 的加法，减法运算；用“o ”，“e 表示昂上的加法，减法运算；对于任意的n 乙* + ，则：口= r o ( n ) + 1 ( o ) + 却七( 口) ，其中r i ( a ) 0 ，1 ，p 一1 ) ，0 i 忌， 那么，对于任意的口，b 冷+ ，b = t o ( b ) + p r l ( b ) + + p k r k ( b ) ，o + b = r o ( a + b ) + 1 ( o + b ) + + p 七( o + 6 ) 相应的r i ( a + b ) = r i ( a ) o n ( 6 ) o 已( o ，b ) 其中： f ，1 ， & ( n ，b ) = 【0 ， n l ( a ) + r i l ( b ) p ，( 1 i 七) 7 i 一1 ( a ) + 心一1 ( 6 ) p ，( 1 i 七) 给出g r a y 映射：琴+ ，_ 墨n 对于弓= ( c o ，c l ，一1 ) z + t 矽( 刁= ( 晶，i ， ，* n 一。) 其中对所有的0 i p 七一1 ，0 j p 一1 ，0 m 佗一l f ( ) o ( 口：f ( ) ) o j r o ( c m ) ， c ( 缸州o ) 礼+ m21 l 讯( c m ) o 歹r o ( c m ) ， 尼2 ， = 1 其中