（基础数学专业论文）四元reedmuller码的研究.pdf

四元r e e d - m u l l e r 码的研究 中文摘要 四元线性码是经典的纠错码理论在近十年间发展起来的个重要研究方向，它与 二元非线性码的构造及研究有着紧密的联系本文主要讨论两个z 4 线性码z t c m ( r , m ) 和z 冗m + m ) 以及它们在g r a y 映射下的二元像z r m ( r , m ) 和z r m ( r ，m ) 的一些 性质 本文的主要结果为； 1 ，讨论了z t c , 4 ( r , m ) 和z 兄m ( r ，m ) 的类型，得到当2sr m + l 时，z 冗m ( r m ) 的类型为驴- 2 b 矗t ，其中k i = l + ( t ) + + ( r m l ) ，如= 1 + i f ) + + ( ，t = m z n 2 r 一2 ，m ；z 见m ( 7 17 7 1 ) 的类型为4 k l 2 一一h 。其中k 1 7 = l + ( m ) + + ( r m l ) ，= 1 + ( ? ) + + ( m ) 2 ，证明了z t 洲( r ，m ) 的二元像z r m ( r ，m ) 是线性码，丽z 冗m 4 ( r m ) 的二元像 z r m ( r ，m ) 是二元非线性码并且由z r m ( r m ) 张成的线性码就是z r m ( r ，m ) ， 得到z r m ( r m ) 的秩为k l + 最后讨论了z r m * ( r f i t , ) 的核及核的维数，得到 出mk e r z r m ( r m ) ；1 + ( t ) + + ( m ) + ( m + 1 ) 3 ，当3 r m 一2 时，对r m ( r , m ) 的z 4 非线性给出了一个新的证明，并且证 明了z t c m ( r , m 一1 ) 是最小的z 4 一线性码，满足妒( z 亿m ( r m 一1 ) ) r m ( r , m ) 关键词二元r e e d m u l l e r 码四元r e e d - m u l l e r 码z n m ( r ，m ) 码 z r m ( r 1m ) 码 作者： 指导老师： 王海华 崔杰 s t u d yo nq u a t e r n a r yr e e d - m u l l e rc o d e s a b s t r a c t t h et h e o r yo fq u a t e n a , a r yl i n e a rc o d e si 8o i l eo ft h ei m p o r t a n ts l l b j e e t 8o fd 搬i c a le l t l x ) l - c o r r e c t i n gc o d i n gt h e o r yi nr e c e l t t e ny e a r s ，w h i c hi s c l o s e l yr e l a t e dw i t ht h eb t t t d y0 1 1 e o n s t r u e t i o r 蝤a n dp r o p e r t i e so fb i i u a r ya o n l i n e a rc o d e s i nt h i sp a p e r 。w ed i s e u 船z t 孙4 ( r , m ) c o d e sa n dz 冗 矿n m ) c o d e 8 ，a n dt h 咖b i n a r yi m a g e f lz 兄m ( r ，m ) c o d e sa 丑dz r m ( r ，m ) c o d e sv i n g r a y m a p 8 0 l u t i o mp r e s e n t e di nt h i 8p a p e rc a nb es t t m m a r i z e d 釉f o l l o w s ： 1 i ) i s e t 埘t h et y p e so fz 7 己m ( nm ) c o d e 8a n dz 冗州。( r ，m ) c o d e 8 w h e n2 兰r s m + 1 ，t h et y p eo fz 冗朋( r ，m ) i s 矿l 鲈2 一氩，w h e t e 1 = l + ( t ) + + ( 0 1 ) ，= 1 + ( m ) + + ( t 3 ，t = m i n 2 r 一2 ，m ；t h e 咖eo f2 删【n r n ) i s 驴1 2 b 一“，w h e r e 詹i = 1 + ( p + + ( r 三) ，七2 一l + ( m ) + + ( 2 p r o v e t 呲t h e b l n a r y l m a g 船a r e l l n e a rc o d e 目i t h ec 撇o f 名冗m ( r m ) ，b u t t h e y 缸e n o ti nt h ec a 的o fz 冗m ( n m ) m o r e d v 留，s i u e et h el 纽l e 篮c o d e 88 p 删b yz r m + n m ) a r ez 兄m ( r t m ) ，w ec a ne o n c l u d et h a tt h er 勰ko fz p a ( r m ) i sk l + a tl a s t ，w ed i c l l 8 s t h ek e r n e lo f z r m ( n m ) a n dg e tt l 砖& m e m i o no f k e r n e lo f z 冗且f ( r ，竹i ) i s1 + ( t ) + + + ( m + 1 ) 3 g i v ean e wm e t l m dt op r o v et h a tj 乏m ( r ，呐i saz 哇_ n i 瑚l i 岭a rc o d ef o r3 r m 一2 耻t h e 眦o r e ，p r o v et h tz 冗朋( r m 一1 ) i st i l em i u i m l l mq u a t e r n a r yc o d e 鲫d lt h a t 西f z 兄m ( r ，m 1 ) ) 矗m ( r ，m ) k e y w o r d s ：b i n a r yr e e d - m u l l e rc o d e ，q u a t e n a a r yr e e d m u l l e rc o d e ，2 记m ( r ，m ) c o d e z 冗m ( r m ) c o d e 1 1 w n t t e nb yw a n gt t a g a u a s u p e 墒e db y c l l ij i e 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不舍为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：二逡华日期：塑鱼坐! 革 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复带4 手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办9 趣。 期：竺! ! ! ! ， 第一章绪论 1 1 经典纠错码理论简介 早在1 8 世纪后期，就有关于某个特定码的结构及解码算法的论文，如b c h 码 但是直到1 9 4 8 年s h a u n o n 的论文 2 1 1 的发表才标志着编码理论的真正建立s h a n n o n 在论文中引入了信道容量的概念，并给出了信道容量的计算方法同时，他证明只要 传输率小于信道容量，就可以通过使用适当的编码方法，使得误码率任意小 s h a n n o n 的工作给人们提出了个问题：如何构造传输率充分接近于信道容量的 编码? 尽管这个问题至今尚未得到完全解央，但事实证明寻求答案的过程更为重要， 因为在这个过程中产生了许多非常重要的编码技巧 有很多因素影响着信息传送中的可靠性，例如；噪音，同步化，干扰，等等经典 的编码理论主要考虑的是噪音的影响它主要分为纠错码理论及g a u s s i a n 信遭中信息 的传送这里主要介绍的是纠错码理论的发展 经典的纠错码理论通常研究的是有限域上的编码，特别是在二元域上令玛是 含有g 个元素的有限域，四是n 元向量空间卫翟中的任子集g 就是个编码， 其中g 的元素称为码元，而卫翟中的向量称为字在皿穿中引入h a m m i n g 重量的概 念，对于任意的x = ( $ l ，z 2 ，) 四，定义 w n ( x ) = i 1 盈o ) i ， 称为x 的h a m m i n g 重量这个重量函数就决定了叼中的一个度量定义 d u ( x ，y ) = t i t l ( x y ) ，v x i y 丑翟 称为x 与y 的h a m m i n g 距离令 d = m i r t d r ( x ，y ) ix ，y qx y l 四元p 0 3 e d - m u l e r 码的研究 第一章绪论 称为码g 的极小h a m m i n g 距离这样，一个纠错码g 就包含了3 个重要参数：码长 n ，码元个数吲及极小h a m m i n g 距离d ，通常记作( n ，l g l ，d ) 码 为了在应用上的实现，一个好的纠错码还必须易于编码及解码通常情况下，我 们会要求码具有一定的代数结构，例如要求码g 是砑的线性子空间，即所谓的线性 码此时码的势就由它的维数决定，我们通常用【n ，田表示个长度为n ，维数为 k ，极小h a m m i n g 距离为d 的线性码对于线性码的编码，我们只需找到一组基就可 以很容易地实现而对于解码，一般地我们也可以利用校验子的分类，绘制译码表得 以实现对于某些特殊的线性码，例如循环码，还有著名的b e r l e k a m p - m a s s e y 算法 线性码一直是经典的纠错码理论研究的重点在s h a n n o n 的论文【2 l 】发表不久， g o h y 与h a m m i n g 分别构造了g 0 l a y 码与h a m m i n e 码，它们是两类非常重要的线性 码后来，v a nl i n t 2 5 j z i n o v i e v 及l e o n t i e v 3 0 1 研究了完备码，证明了完备码只有 h a m m m g 码，g o l a y 码及二元重复码三类s l e p i a n 的工作【2 2 】，【2 3 】， 2 4 】更是给线性 码的研究打下了坚实的基础继于b c h 码的研究，p e t e r s o n 1 9 第一次证明了b c h 码实际上就是循环码一一这是一类非常重要的线性码对于线性码的解码，也有着大 量的工作 s l e p - a n 【2 3 】聍一般的线性码，利用校验子及陪集分类，给出了译码表的构 造方法利用译码表解码，这种方法虽然简单，但对于码元较多的线性码却不是很实 用p e t e r s o n 1 9 ，g o e r e n s t e i n 与z i e r l e r 8 】及b e r l e k a m p 2 】相继研究了b c h 码的解码 m a s s e y 在文献【1 6 】及【1 7 】中，对b e r l e k a m p 提出的算法加以改进，最终形成了著名的 b e r l e k a m l p m a s s e y 算法 然而，在线性码易于编码及解码的同时，其信息量及纠错能力上的要求势必会降 低我们知道，一个线性码的维数及极小h a m m i n g 距离必须满足s i n g l e t o n 界【2 5 】， 即k n d + 1 在经典理论的基础上，纠错码理论在近三十年间取得了很大发展其中一个尤为 突出的方向是d e l s a r t e 提出的结合方案理论，它使得纠错码理论与设计及组合学紧密 地结合起来利用结合方案理论，在1 9 7 0 年左右，几个非线性码被构造出来，包括二 元n o r d s t r o m - r o b i n s o n ，k e r d o c k ，p r e p a r a t a , g o e t h a l s 以及d e l s a r r e - g o e t h a l s 码( 见文献 【6 】，吲，【1 4 】，【2 0 】， 2 5 1 ) 与相同长度及极小h a m m i n g 距离的线性码相比，它们往往具有更 多的码元，有时甚至达到两倍以上这样，在具有相同的纠错能力下，我们可以很大地 2 四元r e e d - m u l l e r 码的研究 第一章绪论 提高码的信息量然而，由于非线性码的构造往往比较复杂，从而很难象线性码一样 找到较为简单的编码及解码算法，这在很大程度上阻碍了非线性码在实际中的应用 1 2四元线性码的发展 在对二元非线性码的研究过程中，人们发现尽管k e r d o c k 与p r e p a r a t a 码作为非 线性码来说，不存在通常意义下的对偶关系，但它们却具有对偶码所满足的性质，即 它们的h a m m i n g 重量分布满足m a c w i l l i a m s 恒等式于是，人们猜测两者之间是否存 在着某种代数意义上的对偶关系? 人们还发现存在着许多非线性码，它们与上述的非 线性码( 除n o r d s t r o m - r o b i n s o n 码外) 具有相同的h a m m i n g 重量分布，但彼此并不等 价( 【l 】，f 1 2 】，【1 3 】) 它们之间又有什么关系呢? k a n t o r 在文献 1 3 】中认为，这仅仅是一 种巧合但是，以后的研究工作却证明事实并非如此 人们一直在试图寻找更为简单的方法来描述这些非线性码 n e c h a e vf 1 8 】首先研 究了四元序列，他通过四元序列的2 - a d i c 展开式构造了一个二元非线性码，并证明它 与二元k e r d o c k 码的两次删减码等价相继地，b o z t a s ，e t a l 【5 】与k u m a r ，e t 州1 4 】也研 究了四元序列，发现其中某些序列的2 - a d i c 展开式与k e r d o c k 码有着惊人的相似在上 述工作的基础上，h a m m o n s ，e t ，a 1 【9 】在非线性码的研究中取得了突破性的进展，他们 构造了一系列的四元线性码，包括四元k e r d o c k ，p r e p a r a t a , g o e t h a l s ，d e l s a r t e - g o e t h a l s 及g o e t h a l s - d e l s a r t e 码，并证明了这些四元线性码在g r a y 映射下二元像恰恰就是上述 的几个二元非线性码( 除四元p r e p a r a t a 及g o e t h a l s 码) 在h a m m o n s 等人的理论中，由于四元k e r d o c k 码与四元p r e p a r a t a 码作为z 4 线 性码是对偶的，故它们的二元像的h a j n m m g 重量分布满足m a c w l l h a m s 恒等式尽管 四元p r e p a r a t a 码在g r a y 映射下的二元像并不是二元p r e p a r a t a 码( 前者所张成线陛 码的极小h a m r m n g 重量为2 ，而后者是h a m m i n g 码的个子码) ，但二者却具有相同 的h a m m i n g 重量分布这就可以解释为什么二元k e r d o c k 码与p r e p a r a t a 码的重量分 布会满足m a c w i l l i a r a s 恒等式 h a m m o 瑚等人的工作给二元非线性码的研究工作提供了一个新的思路我们可 以通过四元线性码来描述某些二元非线性码，从而给出了这些二元非线性码的个较 3 四元r e e d - m u l l e t 码的研究第一章绪论 为简单的构造，使得编码工作易于实现并且，对这些二元非线性码的性质的研究也 可以转化为对四元线性码性质的研究，从而简化了研究工作另外，g r a y 映射是由 ( 砑，l e e 距离) 到( z 争，h a m m i n g 距离) 的保距映射，故这些二元非线性码的解码也可 以通过四元线性码的解码得以实现 在此之后，环上的编码问题引起了人们越来越为广泛的兴趣w a = f 2 9 j 与h a m m o n s e t ，a l 【9 】通过讨论校验子，分别对四元p r e p a r a t a 码给出了个解码算法利用相同的方 法，h e u e s e t h 与x l l m a r t 4 1 给出了四元g o e t h a l s 码的解码算法很多有限域上编码的 概念也被引入到四元线性码中p l e s s 与q i a n 讨论了四元循环码及二次剩余码，并证 明z 4 n ( = “一1 ) 也是主理想环w a n 2 9 】在z 4 的有限次扩张环一一伽罗华环上讨论了 循环码的结构a s h i k h m i n 将广义h a m m i n g 重量的概念引入到四元线性码中，并表明 广义h a m m i n g 重量谱同有限域上的情形一样，可以成功地刻划w i r e - t a p 信道y a n g 等人【2 6 1 对四元k e t d o c k 码计算了前五阶的广义h a m m i n g 重量，并给出了任意阶广 义h a m m i n g 重量的下界y a n g 与h e l l e s e t h 在文献 2 7 1 中对四元p r e p a r a t a 码计算了 前六阶的广义h a m m i n g 重量，在文献【2 8 】中对四元g o e t h a l s 码计算了前六阶的广义 h a m m i n g 重量同时，人们也试图四元线性码在其它方面的应用，例如，b o n n e c a z e 【3 】 就指出，四元自对偶码可以用于格上单模的构造 第二章四元r e e d m u l l e r 码 2 1 ：元r e e d - m u l l e r 码 在这一节中，我们简单介绍一下二元r 舶d - m u l l e r 码的定义及基本性质由于二元 r e e d - m u l l e r 码的解码较为简单，这是一类很重要的线性码 令a g ( r a ，2 ) 是现上的m 维空间，即 a g ( m ，2 ) = f ( a o ，a i ，a m 1 ) io l 现) ) k 维线性子空间的陪集称为维仿射空闻或k 维面特别地，当= m 一1 时，称为超 平面 令u o ，u i ，u m 一1 是仿射空间a g ( m ，2 ) 的标准基对于任意的j ，0 s j 2 m ， 设j = m 量- t 岛2 ，其中如= o 或1 令x ，：曹岛l l i 。则x o ，x l ，劬一l a g ( m , 2 ) l = u s = o 中的所有点 令凹为m x n 矩阵，列依次为x o ，x l ，x 弘一l ，其中n = 2 m 一1 用0 ，1 ，2 m 一1 表示列指标，也可以用x o ，x l ，x 2 m l ，即a g ( m ，2 ) 中的点作为列指标令 a = 苟a g ( m ，2 ) i 岛= lh 则a ，i = 0 ，1 ，m l ，是仿射空间a g ( m ，2 ) 中的m 一1 维超平面令v i 叼是矩 阵e 的第t 行，则v ，是a 的特征函数显然，a g ( m ，2 ) 的特征函数为1 = ( 1 ，l ，1 ) 对于任意的a = ( a o ，o l ，a n - - 1 ) ，b = 怖，b t ，6 n 1 ) 砑，定义 则我们有 a b = ( a o b o ，m 6 i ，n n t b n 一1 ) 命题2 1 ( 2 5 】) 令0 l l ，1 2 ，i ，m l 为不同正整数，则 ( 1 ) v i 。7 旷v 1 是m s 维仿射平面的特征函数； ( 2 ) v i l 7 1 2 v h 的h a m m i n g 重量为t o ( v , t v s , l v i ) = 2 m 一； 5 四元r e e d - m u l l e r 码的研究 第二章四元r e e d - m u l l e r 码 ( 3 ) v i 。v i 。v s e ，0 s m 是皿蛩的组基，其中当8 = 0 时，约定v - ，v | 。v 。 为1 = ( 1 ，1 ，1 ) 口 令0 r m ，由所有乘积v l 。v 。v i ，其中8 r ，张成的线性码称为r 阶 r e e d - m u l l e r 码，记为r m ( r , m ) 命题2 2 ( 【2 5 1 ) 设r m 是正整数，满足0 蔓r m ，r m ( t - ，m ) 是r 阶r d m 1 】1 1 e r 码，则 ( 1 ) d t r a ( r m ( r ，m ) ) = l + ( m ) + + ( m ) ，其中为组合数； ( 2 ) 兄w ( r m ) 的极小距离为d - - - 2 r n _ r ； ( 3 ) j m ( r ，m ) 上= l t m ( m r 一1 ，m ) ，其中g m ( r , 神上表示r m ( r , m ) 的对偶码 令g ( r ，m ) 是r 阶r e e d - m u l l e r 码的生成矩阵，约定r m ( 一1 ，m ) = 兄m ( m + l ，m ) = o ，a ( - 1 ，m ) = a ( m + 1 ，f t l ) = ( 0 ) ，则 命题2 3 设r ，竹l 是正整数满足0 r s m ，则 g c r + - ，m + - ，= ( g p ：1 仇) g 芝主：m ) ) 即r m ( r + l ，m + 1 ) = ( u ，1 1 1 + v ) lu e a m ( r + 1 ，m ) ，v r m ( r ，m ) 口 令丌岛是 o ，1 ，n 1 ) 的一个置换，定义 _ 砑 + ( f ( o ) ，o f ( 1 ) ，一，o 州一1 ) ) 则”是砑上的一一对应，相当于叼中的向量交换分量的位置令砑为线性 码，若”( d ) c ，则称”是c 的个自同构所有e 的自同构按照映射的复合构成 一个群，称为0 的自同构群，记为a u t ( q 例如，a u t ( r m ( o ，m ) ) = 岛 令a g l ( m ，2 ) 为仿射变换群，即 a g l ( m ，2 ) = t m m a x t n ( 毋) l m 可逆) 6 一n b 叨 ， dn 丌 四元r e e d - m u l l e r 码的研究第二章四元r e e d - m u l l e r 码 考虑a o l ( m ，2 ) 在仿射空间a a ( r a ，2 ) 上的作用 a g l ( m ，2 ) a g ( m ，2 ) - - 4a g ( m ，2 ) ( m ，x ) _ _ m x 由于a g ( m ，2 ) 中的点可以作为砑中向量的n 个位置，故m a g l ( m ，2 ) 在a g ( r n ，2 ) 上的作用诱导出忭个位置上的置换 命题2 4 ( 1 2 5 ) 令a 是a g ( m ，2 ) 的f 维仿射平面，v 是a 的特征函数，则v r m ( m i ，m ) 口 由于a g l ( m ，2 ) 中的元素将a g ( m ，2 ) 的l 维平面映到z 维平面。由命题2 4 得 a g l ( m ，2 ) a u t ( r m ( r m ) ) ，并且 命题2 5 ( 1 5 1 ) 当3 r 墨m 一2 时。a u t ( r m ( r , m ) ) = a g l ( m ，2 ) 口 2 2四元线性码及其g r a y 映射 令z 4 是整数环模4 的剩余类环，n 是个正整数，留是z 4 上所有n 元向量的 集合，即 z 譬= ( z l ，却，霉。) i 茁。z 4 ， = 1 ，2 ，n ) 刃中任加法子群称为四元线性码，或简称为z r 线性码，其中子群中的元素称为码 元，n 称为码长令c 是个z 4 线性码，如果它作为加法群的类型为驴- 2 b ，则我们 称码c 的类型为驴t 2 b 显然，蚓= 2 2 t + b 对于任意的x = ( z l ，沈，孙) ，y = ( f l ，抛，撕) z 2 ，定义 xy = l 掣l + 。c 2 y 2 + + + x n y ， 称为x 与y 的内积若x y = 0 ，则称x 与y 是正交的令c 是任意一个长度为n ， 类型为4 k t 2 k 2 的z 4 - 线性码，定义 c 上= x z 2x y = 0 ，v y c 则c 上也是一个线性码，称为c 的对偶码由【2 9 】命题1 2 知，对偶码萨的类型为 4 “一虹女t 擎2 7 四元r e e d - m u l l e r 码的研究第二章四元r e e d - m u l l e r 码 与域上编码中的h a m m j 曲_ g 重量及h 柚m i n g 距离相对应地，我们在四元线性码中 引入了l e e 重量及l e e 距离对于z 4 中的元素0 , 1 ，2 ，3 ，其l e e 重量分别定义为0 , 1 ，2 ，1 对于任意的向量a = ( o t ，o , 2 ，a n ) 趁，定义 w l ( a ) = t o l ( a 1 ) + t v l ( a 2 ) + + t l ，l ( ) ， 称为向量a 的l e e 重量对于任意的向量x ，y z n ，定义d l ( x ，y ) = w z ( x - y ) ，称为向 量x 与y 的l e e 距离定义 d = r a i n d l ( x ，y ) ix ，y c ，x y 称为码c 的极小l e e 距离同样地，我们对于四元线性码的解码依据的依然是极大似 然译码理论，则极小l e e 距离d 就完全决定了四元线性码c 的纠错能力 定义三个由z 4 到z 2 的映射，分别为 a ：0 q 1 h 1 ，2 h 0 ，3 t - - + l ； 卢：0 h 0 ，1 t - - - + 0 ，2 h l ，3 h 1 ； ，y ：0 h 0 ，lh1 ，2h1 ，3 h 0 注意到a 为环同态，丽p ，7 不是很自然地，我们可以把上述三个映射推广为由蜀 到z 2 的映射，为简单计，分别也记为口，卢，丁定义 毋：z 4 一 趁“ c + ( c ) ，7 ( c ) ) ， 庐称为g r a y 映射令c 是个z 4 - 线性码，它在g r a y 映射下的像妒( c ) 称为它的二元 像我们通常用大写的花写体字母表示四元码，丽用相应的大写拉丁字母表示其二元 像显然，g r a y 映射建立了一个由刃到z 2 “的一一对应，更为重要的是，它是一个 保距映射 命题26 ( 2 9 】) 妒是由( 功，l e e 重量) 到( 趁”，h a m m i n 9 重量) 的保重映射，即 w l ( x ) = h ( ( x ) ) ，v x z 2 并且，咖是由( 刃，l e e 距离) 到( z 争，h a m m i n 9 距离) 的保距映射，即 d l ( x ，y ) = = d 盯( 咖( x ) ，咖( y ) ) ，v x ，y z 2 8 四元r e e 出m i l l l e r 码的研究 第二章四元r e , d - m u l l e r 码 令c 是类型为矿- 2 t 的z 4 - 线性码，自然地有两个二元线性码与之联系令 q = a ( c ) ic c 则q 为协，1 1 码令 f = c ci2 c = 0 ) 则彳中码元的分量均为0 或2 ，且于是类型为2 t t 舳，的z 4 线性码定义 妒： c_ 刁 ( 2 c 0 ，2 c i ，2 一1 ) p _ ( a ( 印) ，a ( c d ，a ( c n 1 ) ) 令锡= 母( 西，则岛为唧，1 + 2 】码 令口是个= 元码( 线性或菲线性的) ，若存在z 4 一线性码c ，使得g 与毋( c ) 置换等价，则称g 是z 4 线性的自然的两个问题：一、什么样的二元码是z 4 线性 的? 二，什么样的z 4 - 线性码，其在g r 氆y 映射下的二元像是线性的2h a 瑚硒o m 等人 【9 】对这两个问题给出了判别条件这里，我们只叙述主要结果 命题2 7 对于任意的x y 硪，则 咖( x + y ) = 毋( x ) + ( y ) + 庐( 2 口( x ) a ( y ) ) 口 命题28 长度为2 n 的二元码c 是z 4 一线性的当且仅当适当交换分量的位置后， 满足 u ，v c = 争( u + 盯( u ) ) ( v - 4 - 口( v ) ) i z 其中盯= ( 1 ，n + 1 ) ( 2 ，住+ 2 ) ( n ，2 n ) 岛。 口 命题2 9 c 是z 4 - 线性码，则c = 咖( c ) 是线陛的当且仅当 x ，y c 辛2 a ( x ) 口( y ) c 9 口 四元r e e d - m u l l e r 码的研究 第二章四元r e e d - m u l l e r 码 2 3四元r e e d - m u l l e r 码 为了讨论二元r e e d - m u l l e r 码的z 4 - 线性，先考虑两个四元r e e d - m u l l e r 码1 9 0 4 年，h a m m o n s 等人【9 】定义了一类z 4 线性码，以下记作z 冗，m ( nm ) 1 9 9 7 年，万哲 先【2 9 】给出了个类似的定义，以下记作z 冗m + ( r m ) 他们分别证明：对某些特定 的r z 冗m ( r 1m ) 与z 冗朋nm ) 的二元像为r e e d - m u l l e r 码 觑朋( r m ) 是由n m ( r 一1 ，m ) 与2 r m ( r , m ) 张成的长度为2 m 的z 4 线性码，即 z 冗a 4 ( r , m ) = t 令g ( r ，m ) 是r e e d - m u l l e r 码m f ( r ，哟的生成矩阵，则z 亿m ( r m ) 是长度为2 m 的z 4 一线性码，其生成矩阵为 ( g 。( 吼r - 1 7 , r n ) 令z r m = 妒( z 亿m ( r ，m ) ) ，z r j l 扩= ( z 冗m ( r ，m ) ) ，分别为z t z m r , 仃磅与 z 兄m ( r m ) 在g r a y 映射下的二元像显然，它们均是长度为2 f ，h 。1 的二元码由 【9 】和 2 9 1 知 命题2 1 0 令r = 0 ，1 ，2 ，m 及m + 1 ，则 ( 1 ) z r m ( r ，m ) = r m ( r , m + 1 ) ( 2 ) z r m + ( r j m ) = 兄m ( r m + 1 ) 口 由命题2 1 0 知，当r = 仉1 ，2 ，m 及m + 1 时，三7 z m ( r l m ) 与z t l m n m ) 的定义 是一致的，并且二元r e e d - m u l l e r 码r m ( r , m + 1 ) 是z 4 线睦的 对于任意的x ，y z ，为了不致引起混淆，它们在霹中的和记为x lh x 2 ，而将 x l ，x 2 看成是砑中的向量，它们在殁中的和记为x 1 + x 2 显然，z r m ( r ，m ) z 冗3 4 ( r ，m ) ，并且对于某些特定的r 值，等号成立很自然 的问题足对于其它的r 值，等号是否成立呢? 1 0 四元r e e d - m u l l e r 码的研究 第二章四元r e e d - m u l l e r 码 g = ( ：) 四元r e e d - m u l l e r 码的研究 第二章四元r e e d - m u l l e r 码 引理2 1 2 况朋( o ，m ) 的类型为2 1 ，且z 7 训( 1 ，m ) 的类型为4 1 扩 口 命题2 1 3 当2 r m + 1 时，z 刚d ( r , m ) 的类型为驴t 2 t “t ，其中l = 1 + ( n + + ( 0 1 ) ，= 1 + ( m ) + + ( m ) ，t = r n _ ；n 2 r 一2 ，m ) 证明：考虑与z 冗m m ) 相关的两个z 2 - 线性码 q = a ( e ) ic z t z m ( r ，竹1 ) ； 与 岛= 妒( c ) lc 彳 其中f = c z t 已m ( r , m ) l2 c = o ) ，且1 ；f ，由2 2 节给出显然，q m u ( r 一1 ，m ) ， 故d n a = 1 + ( m ) + + ( r m l ) = 后卜下面，我们考虑q 的维数 对于任意的， 1 ，2 ，m ，满足川m t n 2 r 一2 ，m ) ，存在n - t - 子集五，而。 使得 u 屯= ，且m l r l ，i 屯i r l ，则由引理2 1 1 得 v 。+ 6i iv 。= i iv 。+ i iv s + 2 v 。 t j li b l f ii e b i j 由于l i t i sr l ，且l 2 i r 一1 ，故兀v 。，nv s r m ( r l ，m ) ，贝0 丌v 。+ 6nv 。 i e ，ll bi i b r m ( r l ，m ) 由于nv 。+ 6 兀v ；，nv i ，nv l 4 ，故 i nl 2 i 1t j 2 2 v 。= ( v 。h h ) 一v | 一 4 矾m ( r m ) 1 jl ，l l 如 i i 如 由孑的定义知，21 1v 石则nv q 令t = m l n 2 r 一2 ，m ，由于v l ，i j l t 是r e e d m u l l e r 码m u ( t ，m ) 的一组基，故r m ( t ，m ) q 另一方面，令d = 妒一1 ( 冗m ( t ，m ) ) = 2 r m ( t ，m ) ，对于任意的x 彳，设x = x 1 + x 2 其中x l 4n 互x 2 4 ，显然， x 2 d 设 x l = l y l + a 2 y 2 + + 入，y 5 其中k z 4 ，y l r m ( r 一1 ，m ) 对于4 = 1 ，2 ，5 ，设 ( 21 ) yl=玎v l + 6nv + 6 + 6n 姒l5 厶4眠 ( 2 2 ) =nv l + 1 iv l + + nv i + 2 i i v l l l ll l 2l ，f l ：9 k 兰kl 如u - 1 2 四元r e e d - m l l l l e r 码的研究 第二章四元r e e d - m u l l e r 码 其中i r 一1 ，故对于任意的1 墨j k k ，i 岛u i m m ( 2 r 一2 ，m = t ，则 2 n ，v l d 因此，由( 2 1 ) 与( 2 2 ) ，我们可设 l s ， 自三m 1 0 u 1 “ x l = a l v l + a 2 e i + + a 。v l + c ， l 副1l b 埯l 其中k ，e z 4 ，c d ，l 五l 曼r l ，且i t ，屯，互不相同由于2 x t = 0 故 2 入l v l 十2 入2 ，v l + i ：2 v l = o l f li e ，2 ， 由于1 iv l ，1 1 ，r i ，v l 是z 4 自由的，故2 k ，- 0 ，则a 。= 2 u ”对某个饥z 4 l l 如 l l = l ，2 ，8 ，故 x l = 2 u l v l + 2 u 2 十+ 2 u ，+ c d i 培五 l l 兰毫一h ，i 三；s m + 。 四元r e e d - m u l l e r 码的研究 第二章四元r e e d - m u l l e r 码 其中口= c 42 c = 0 显然，d t 一肼( r 一1 ，仇) ，故d ：m d l = l + ( t ) + + ( r m l ) = k 1 由命题2 1 3 的证明知，对于任意的l ， l ，2 ，m ) ，满足 i j i r a m 2 r 一2 ，m ) 2r i ，v t 4 ，故n v i d 2 ，贝0 r m ( t ，m ) s d 2 ， 故d l m d 2 l + ( ? ) + + ( m ) = b 因此 4 的类型为4 b t 2 d * m d 。一b ，而 z 冗m ( r m ) 的类型为 t 2 k 2 - h l ，故d z m d 2 = 如，且 4 = z 冗朋( r ，竹1 ) 用类似的方法，我们可以讨论z t z m ( r ，m ) 的类型 凸 命题2 1 6 2 巩m ( n m ) 的类型为4 t 1 2 k 2 一1 。，其中l = l + ( t ) + + ( r m t ) 如= l + ( t ) + + 口) 证明： 由定义知z 冗m ( r 仇) 的生成矩阵为 fg p l ，m ) i2 g ( r i 。) j 考虑与z 冗m ( r m ) 相关的两个z 2