（基础数学专业论文）二元常重码及数字（tms）网的构造与界.pdf

摘要 通过建立长度为n 的二元常重码和n 元集合的一组子集的对 应关系，我们得到了二元常重码的一个繁衍规则。我们把这种思想 推广，给出了二元常重码的三种构造方法。最后的例子表明，我们 的构造方法能够产生出具有较好参数的二元常重码。 利用编码理论中的思想，我们把关于码的结果推广到o o a 上，得到了一些关于o o a 的构造和界。再通过o o a 和数字 ( t ，m ，s ) 一网的对应关系，我们得到了一些数字( t ，m ，s ) 一网的构造 和界。 关键词：常重码，( t ，m ，8 ) - n ，有序正交阵列。 1 1 1 a b s t r a c t f r o mt h e c o r r e s p o n d e n c e b e t w e e nab i n a r yc o n s t a n t w e i g h tc o d eo f l e n g t h 礼a n d af a m i l yo fs u b s e t so fa l 扎e l e m e n t ss e t ，w eg e tas i m p l ep r o p a - g a t i o nr u l ef o rc o n s t a n t w e i g h tc o d e s b yg e n e r a l i z i n gt h ep r o p a g a t i o nr u l e ， w e p r e s e n tt h r e ec o n s t r u c t i o n so fb i n a r yc o n s t a n t w e i g h tc o d e s ，i t u r n so u t t h a to u rc o n s t r u c t i o n sc a np r o d u c eb i n a r yc o n s t a n t w e i g h tc o d e sw i t hg o o d p a r a m e t e r s a p p l y i n gi d e a si nc o d i n gt h e o r y ，w eg e n e r a l i z es o m er e s u l t so nc o d e st o t h o s eo n0 0 a s ，a n d g e ts o m e c o n s t r u c t i o n so fa n db o u n d so no o a st h e n f r o mt h ec l o s ec o n n e c t i o n so fo o a sa n dd i g i t a l ( t ，m ，s ) - n e t s ，w eo b t a i n s o m ec o n s t r u c t i o n so fa n db o u n d so nd i g i t a l ( t ，m ，s ) 一n e t s k e y w o r d s ：c o n s t a n t w e i g h tc o d e s ，( t ，m ，s ) - - n e t s ，o r d e r e do r t h o g o n a l a r r a y s 1 v 致谢 本文完成之际，在科大的学习生活也即将结束了在科大的七 年里，我的成长得到了许多老师和同学的关心和帮助，在此对他们 表示深深的感谢我相信，在科大学到的知识和做人的道理将是我 以后人生的一笔宝贵财富。 我还要衷心感谢我的导师邢朝平教授的悉心指导在我的研究 生学习期间，邢老师一直给予我极大的帮助、鼓励和关怀在本文 从选题到定稿的过程中，邢老师付出了大量的心血，多次和我讨论 并提出修改意见。邢老师渊博的知识，严谨的治学态度令我受益匪 浅，终身难忘。 我也要感谢代数编码讨论班的帮助。在三年研究生学习期间， 我向讨论班上的同学学习了很多新知识，获得了很多帮助。在此感 谢各位同学，他们是胡万宝、龙寿伦、孙广人、李鸿利、于飞、凌杰 、任涤新和方杨。 最后，我要特别感谢我的父母和家人，他们是我坚强的后盾， 无论在什么时候都支持着我感谢他们多年来对我细致入微的关怀 和教育，他们为我的成长付出了极大的心血，没有他们就没有我的 今天。 第一章引言 编码理论是主要研究在有嗓信道中传输数据和恢复受损数据的一门学 科。1 9 4 8 年，c l a u d es h a n n o n 发表了开创性的论文am a t h e m a t i c a lt h e o r y 计c o m m u n i c a t i o n ，以此为标志编码理论正式诞生。在短短的5 0 多年中， 编码理论蓬勃发展，取得了一系列的重要成果，并在实际生活中得到了广泛 的应用，为i n t e r n e t 的兴起以及其它许多数据存储和传输技术的进步奠定了 坚实的理论基础。 如何构造好的码一直是编码理论中的一个非常重要的问题。在编码理论 的发展过程中人们使用了各种各样不同的方法来构造出不同的码，所用到的 知识几乎涉及到了数学的各个分支，包括分析、代数、组合数学、几何等等。为 了检验构造出来的码是不是好的，人们计算出了许多码的界，即在一定条件 下码的参数可能达到的最优值。通过码的参数与这些界的比较，人们可以判 断一种码是否有意义。常重码在编码理论中是一类重要的码。历史上，因其 码字都具有相同的重量常重码一直有着重要的理论意义( 参见 3 】，f z o ) 。 近年来，常重码在现实生活中也得到了大量的应用【1 】，被用于c d m a 系 统，并行异步通讯，自动纠错系统等许多领域。因为在理论研究和实际应用 中的双重意义，常重码引起了人们广泛的研究兴趣。在接下来的一章中，我 们将给出一类新的常重码的构造方法，并由此得到常重码的一些新的界。 本文中要讨论的第二个问题来源于科学计算领域。拟m o n t ec a r l o 方法 是一种计算高维数值积分的有效方法，它通过在s 维半开单位立方体，5 = 0 ，1 ) 5 ( s 2 ) 中选取一组点x o ，x ”，x 一。来计算数值积分 厶m 灿专篓，( x a 为了控制上述数值积分的误差，点集x o ，x z ，x n 一) 应该在p 中分布的 尽量“均匀”，也即所谓的低偏差点集( 具体定义见 1 8 】) 人们提出了多种 构造低偏差点集的方法，例如元h a m m e r s l e y 点集，h a l t o n 序列的前 项等等但现今最有效的构造低偏差点集的方法还是基于n i e d e r r e i t e r 【1 2 l 提出的( t ，m ，s ) 垌( 具体定义见第三章) 。数字( t ，m ，s ) 嗣是指在有限环兄上 构造的( t ，m ，s ) 一网。到目前为止，在拟m o n t ec a r l o 方法中得到实际应用的 ( t ，m ，s ) 一网都是在特定的有限环上构造的数字( t ，m ，s ) 一网。为了得到更多的 数字( t ，m ，8 ) 一网，l a w r e n c e ，m u l l e n 和s c h m i d 1 8 1 提出了有序正交阵列 2 0 0 4 年中国科学技术大学硕士学位论文第2 页 第一章引言 ( o o a ) 的概念，并建立了( t ，m ，s ) j 碉和一类o o a 的等价关系。和( t ，m ，s ) 一 网相比，o o a 具有更明确的代数和组合性质，因而我们可以更容易的利用 各种方法来构造出新的o o a 。在第三章中，我们将主要利用编码理论中的 方法来构造新的o o a ，同样利用编码理论中求码界的思想得到了一些关于 o o a 的界。 本文余下内容安排如下：第二章介绍常重码的概念以及三种新的构造方 法，由此导出了一些关于常重码的新的界，并给出了一些具体的例子；第三 章先介绍数字( t ，m ，s ) - g 和o o a 的概念，再利用编码理论中的常用方法得 到新的o o a 及一些关于o o a 的界，接着通过建立数字( t ，m ，s ) 网和o o a 的联系，进一步得到新的数字( t ，m ，s ) 一网的构造和界；第四章总结全文。 第二章二元常重码的构造与界 在本章中，我们将给出二元常重码的三种构造。首先我们给出一个二元 常重码的简单繁衍规则，然后把这种思想推广到有限域上的线性空间和z m 一 模上，构造出了具有较好参数的二元常重码。在给出具体构造之前，我们先 介绍一些编码理论以及二元常重码的基本概念。 2 1 码和h a m m i n g 距离 定义2 1 1 设f 口为q 元有限域，记“竺，称”中的 任一非空子集c 为一个长度为n 的p 元码特别地，当p = 2 时称c 为 一个二元码。c 中的每个元素称为一个码字，c 中的元素个数1 c l 称为 c 的尺度。 定义2 1 2 设霉= ( 。1 ，。2 ，z 。) 和y = ( y l ，y 2 ，f 。) 为二元码c 昭 中的两个码字，定义z 和y 间的h a m m i n g 距离d ( x ，掣) 为z ，y 取值不同的 分量的个数，即 d ( 而掣) = d ( 而，轨) ， ( 2 1 1 ) 其中d ( 最，挑) 2 ：薹三薹如果c 中含有至少两个码字，则c 的距 离d ( c ) 定义为c 中两个不同码字间距离的最小值，即d ( c ) = m i n ( d ( x , y ) ： 墨y c ，z g ， 容易验证，h a m m i n g 距离具有和欧氏距离类似的性质： 命题2 1 3 设c 是一个长度为n 的二元码，为弘石c ，则 ( 1 ) 正定性；0sd ( 霉，们s 扎，并且d ( z ，们= 0 # 导z = y ； ( 2 ) 对称性；d ( 2 ，们= d ( 弘动； ( 3 ) 三角不等式：d ( 为奶d ( 毛功+ d ( 。，y ) 。 在本章的以下部分中，我们将只讨论c 为二元码的情况，并把h a m m i n g 距离简称为距离。 定义2 1 4 设。= ( z l ，勉，z 。) 为二元码c 中任一码字，称 勋，岱2 ，z n ) 3 2 0 0 4 年中国科学技术大学硕士学位论文第4 页 第二章二元常重码的构造与界5 2 2 = 无常重码的构适 中非零元素的个数为z 的h a m m i n g 重量，记为叫f ( 动。 易见，w t ( x ) = d ( x ，o ) ，其中0 = ( o ，o ，0 ) 为赡中的零向量。关于 h a m m i n g 重量和距离的关系，我们还有一个非常有用的公式： 命题2 1 5 ( 1 6 】，l e m m a4 3 4 ) 对叼中任意两个码字z = ( z 1 ，z 2 ，z 。) 和暑，= ( y l ，y 2 ，) ，令z 十三= ( z l y l ，x 2 y 2 ，z 。y 。) ，贝0 d ( 为们= w t ( x + 扪= ( 动+ 埘t ( 们一2 w t ( x 们。( 2 1 ，2 ) 同样的，以下我们把h a m m i n g 重量简称为重量。有了重量的概念，我 们就可以定义二元常重码了 定义2 1 6 设c 是一个长度为n 的二元码，如果存在常数叫使得c 中的 任一码字刃都有 ( 动= w ，则称c 是一个二元常重码。进一步，若还 有d ( c ) 2d ，蚓= m ，则称c 是一个( 孔，m ，d ；叫) 二元常重码，给定 n ，d ，留，记( 扎，m ，或 ) 二元常重码的最大可能尺度为a ( 咒，d ， ) 。 2 2 二元常重码的构造 下面我们开始介绍这一章的主要结果。在第一节中，我们建立了长度为 n 的二元常重码和一个n 元集合的一组子集的对应关系，由此我们得到了二 元常重码的一个繁衍规则。在第二、第三节中，我们把这种思想分别推广到 线性空间和模上，也分别得到了二元常重码的新的构造方法， 2 2 1集合 设a = a 1 ，a 。) 是一个含有n 个元素的集合，记2l 4 l = s ：sc a ) 为a 的所有子集组成的集合，则我们可以定义一个映射妒：砸2 1 a i ， 妒( ( z 1 ，。2 ，x n ) ) = o ；：x i = 1 ) 。 容易验证妒是双射，对任意的( n ，m ，d ；划) 二元常重码ec 叼，妒( c ) = 4 1 ，a 2 ，a m c2 f a f 均满足 a i f = w n ，i = 1 ，2 ，m ；( 2 2 1 ) 2 0 0 4 生 第二章 中国科学技术大学硕士学位论文第5 页 二元常重码的构造与界2 2 ：元常重码的构造 以及 i 1 + i a ， 一2 l a i n a j i = 2 w 一2 1 a , na j l2 d ， 1s2 jsm 。 f 2 2 2 ) 于是，给定一个( 扎，m ，d ；w ) 二元常重码c ，我们就可以找到一组a 的子集 满足( 2 2 1 ) 和( 2 2 2 ) 。 另一方面，如果存在一组a 的子集f a - ，a 2 ，a m 满足上述条件 ( 2 2 1 ) 和( 2 2 2 ) ，我们也可以构造一组二元常重码。 对于任一取定的s ( 1 ssw ) ，设b l ，b 2 ，b m 是a 的所有含s 个元素的子集。我们构造二元常重码c 7 = c l ，c 2 ，c m ) cz ；如下： c t = c q ，& ：，。，c ，其中，= ( ：) ，c 。= 1 。：马b ic 鐾a a i i 。 显然w t ( c i ) = ( ：) ，且对所有的1 i j 茎m ，我们有 d ( c i ，q ) = w t ( c i ) + w t ( c i ) 一2 w t ( c l 。j ) = z ( ；) 一z ( 陋i ：矧) z ( ：) 一z ( 等) 钮 ( 2 2 、3 ) 所以，c 7 是一个( n ，m ，d ，；w ) 常重码，其中n 7 = ( ：) ，d r = 2 ( ：) 一2 ( 2 f ) ， w 7 = ( w 。) 。 由上述论证可知，我们可以从一个已知的( n ，m ，面w ) 二元常重码c 构 造出一组( n 7 ，m ，d ；q _ t 3 ) 二元常重码e 给定a ( n ，d ，谢) 的一个下界，则 存在至少一个( n ，d ；w ) 常重码，于是我们可以按上述方法构造一组新的 二元常重码。总结起来，我们有如下定理： 定理2 2 1 给定a ( n ，d ，山) 的一个下界j v ，则对于所有的1 s w 都存 在一个( ，n ，d r ；叫) 二元常重码，其中礼，= ( ：) ，d ，= 2 ( 善) 一2 ( 2 f ) ， w 7 = ( ：) 。因此，a ( n ，d ，w 7 ) n 。 2 0 0 4 年中国科学技术大学硕士学位论文第6 页 第= 章= 元常重码砖构造与界2 2 = 元常重码的构造 2 2 2线性空间 首先我们介绍一下g a u s s 系数的概念。 定义2 2 2 给定一个素数幂q 和两个正整数七，r 且满足k r ，称 为g 。“8 s 系数。为了以后使用的方便，当k r 时我们补充定义 ； 。= 0 。 命题2 2 3 ( 【1 6 】，t h e o r e m5 1 1 2 ) 设为q 元有限域，v 是上的r 维线性空间，则v 的( r ) 维子空间的个数为 ” ( ，一q 2 1 ) ( q 。一q 1 ) 接下来我们给出基于线性空间的构造方法设v 是有限域上的r 维 线性空间，1s ss 2 r 为正整数再设，k ，：l 为y 的所有s 维 子空间。那么，给定一些v 的t 维子空间w 1 ，w m ( m 豳。) ，我 们可以类似地构造一个二元常重码c = c - ，e 2 ，c m ： c z = c q 。，岛。，g 。，其中扎= 习。，c 。= 1 ：甏薹滚。 ( 2 2 4 ) 按上述方法构造的二元常重码c 的参数也很容易确定。首先，对任意的 i 有w t ( c d = 明日。记0 垒m a x d i m ( w i n w j ) ：1si j 茎m ) 一1 ， 则对任意1si j m 有 d ( c i ，c j ) = w t ( c i ) + w t ( c j ) 一2 w t ( c c j ) 一t j ，_ 2 p 鼍喁 。 猢t ，- - 2 m zs ， 从而c 是一个( 朗q ，m ，2 嘲。一2 朗。；豳口) 二元常重码。至此我们已经证明 了如下定理： 2 0 0 4 年中国科学技术大学硕士学位论文第7 页 第二章二元常重码的构造与界2 2 二元常重码的构造 定理2 2 4 设y 是有限域n 上的r 维线性空间，若存在一个由y 的子空 间组成的集合q ( r ，m ，t ，满足： ( 1 ) 吲= m ； ( 2 ) d t m ( w ) = t ，vw n ； ( 3 ) d i m ( w v l w 7 ) 目，vw w 7 q ， 则对任意1 s t 均存在一个( ； 。，m ，2 嘲。一2 朗。；嘲。) 二元常重 码。 现在，为了构造好的常重码，我们只需找到合适的q ( r ，m ，t ，鳓使得m 足够大。我们采用从秩距离码构造q ( r ，m ，t ，口) 的方法来解决这个问题。为 此，我们先回顾一下g a b i d u l i n 在 4 中研究的秩距离码。 设a = a ) 是一个上t m 矩阵的集合。a 中任意两个矩阵 a ，b 之间的距离d ( a ，b ) 定义为d ( a ，b ) = r a n k ( a b ) 。记d ( a ) = m i n d ( a ，b ) ：a b a ) 。设d = d ( a ) ，m = l a l ，则我们称a 是一个 ( t w t , ，m ，d ) 秩距离码。对于一个( txm ，m ，d ) 秩距离码，s i n g l e t o n 界依 然成立，即 d ( a ) t f + 1 ，( 2 2 6 ) 其中j = l o g 。m 。使得上式中等号成立的秩距离码称为最大秩距离码( m a x i m u m r a n k d i s t a n c ec o d e ) ，简记为m r d 码 在【6 】中，j o h a n s s o n 提出了一种从线性化多项式构造m r d 码的方 法。设1 f s t s m 为正整数，形如 f ( z ) = z 旷，f 嵋m i = 0 的多项式被称为线性化多项式，记所有的次数不高于q 卜1 的线性化多项式 为 t 最 。= f ( z ) = 五z 旷 = 0 五m ，d e g ( f ( x ) ) q 卜1 。 取定取m 中玛钱性无关的t 个元素g l ，9 2 ，g t ，对每一个f ( z ) 最 。 令 a f = ( f ( 9 1 ) ，f ( 9 2 ) ，f ( g t ) ) t 。 2 0 0 4 年中国科学技术大学硕士学位论文第8 页 第二章二元常重码的构造与界2 2 二元常重码的构造 再取定m 在碥上的一组基，并把每个f ) 在这组基下表示成行向量的 形式y ( g ：) = ( a i l ，a i 2 ，o i 。) ，其中每个分量a i j f 口。因此，每个a f 均 可以看成一个f 口上的txm 矩阵( o 坩) ，a = a f ：y ( x ) 只，t ，。) 可以看 成一个秩距离码。进一步，j o h a n s s o n 证明了如下定理： 定理2 2 5 ( 6 】，l e m m a3 ) a = a f ：f 0 ) 日 。 是一个m r d 码，也 即，a 是一个( t m ，q “，t f + 1 ) 秩距离码。 1 7 】中定理1 和定理3 给出了秩距离码和q ( r ，m ，t ，口) 的关系。 定理2 2 6 ( 1 7 1 ) 若存在一个虬上的( t m ，m ，t 一日) 秩距离码，则必有 一个f 口上的a ( m + t ，m ，t ，0 ) 。 结合上述两个定理，我们可以从秩距离码a = a f ：f ( x ) 日 。) 构造 出一个n 0 + m ，q “，t ，f 一1 ) ，进而得到一组( ”产。 口，q “，2 嘲。一2 n 1 。；豳。) 常重码。总结起来，我们有 命题2 2 7 设f 。是q 元有限域，1 f 茎t 茎m 为正整数，则对所有的 1 s 曼t ， a ( n ，d ，伽) q “，( 2 2 7 ) 其中礼= 7 7 。 。，d = 2 嘲。一2 f ：1 。，w = 圈。 我们断言，当q 趋向无穷大时这一组a ( t + m ，q “，t ，f 一1 ) 也逐渐趋向 其大小的上界，因此这一组q ( t + m ，q ，t ，2 1 ) 是“最优”的。为了证明这 一点，我们先给出l f 2 ( r ，m ，t ，口) l 的一个上界，再把a ( t + m ，q ，t ，f 一1 ) 的 参数与它的上界进行比较。 定理2 2 8 ( i q ( r ，m ，t ，8 ) i 的上界) 给定r ，t 和口，设m ( r ，t ，目) 为i q ( r ，m ，t 目) j 的最大值，则 m ( n t ，8 ) 墨鲁半。 ( 2 2 8 ) 【口十1 j 口 证明：设y 是上的r 维线性空间，q ( r ，m ，t ，目) = - n ，w 2 ，w ，h ) 是矿的一组线性子空间，其中m = m ( r ，t ，鳓。再设u 是y 的一个自+ 1 维子空间。若v 被包含在某个中，那么u 不可能被其他仰j 0 i ) 所包 含。否则，d i m ( n w j ) d i m u = 8 + 1 ，这与q ( r ，m ，t ，口) 的定义矛盾。 v 中的口+ 1 维子空间个数为 日；， 。，且每个姒中包含 8 + t ， 。个口+ 1 2 0 0 4 年 中国科学技术大学硕士学位论文第9 页 至三兰皇童兰翌篁竺兰童至 塑兰三垄兰塞竺竺竺兰 维子空间，所以 口 取定r 和七，当q1 + 。时我们有 r 1 ：熊；二避：二坠：鲑竺二! ! k j 。( q 一1 ) ( 矿一- 一1 ) _ _ ( 再可一 扩扯。 ( 2 舢) 从而，当9 + 。时 m ( r ，t ，目) 。 乩 。 o ( r p 1 ) 徊+ 1 ) d ( 一日一1 ) 汨+ 1 ) 扩一棚+ 。 ( 2 2 1 0 ) 显然，当q 趋于无穷时q ( t + m ，q “，t ，一1 ) 也将趋于此t ，目) 的上界，即 s2 ( 抖m ，g “，f ，l - 1 ) 是“最优”的于是，我们有理由相信由n ( f + m ，g m l ，t ，l - 1 ) 构造碍到的常重码也应该有比较好的参数。为了证明这一点，我们把由命题 2 2 7 得到的a ( 札，d ，叫) 的下界与i l l 中的一个上界进行比较。 命题2 2 9 ( 1 ，t h e o r e m1 2 ) 令让= 叫d 2 + 1 ，则 4 m ，d ，w ) ( ：) ( ：) 。 继续使用命题2 2 7 和2 , 2 9 中的记号，当g - + o 。时，我们有 儿= 一1 。矿“_ 卸= 习。a ( 1 1 扣； 甜= 叫一彤。+ z = 。：1 。+ z z a c 卜l 一5 扣 应用s t i r l i n g 公式： 州厮( ：一_ 十。) ，有 ( 22 i 1 ) ( 2 2 1 2 ) ( 2 2 1 3 ) ( 2 2 1 4 ) ，b 、如 二量蕊 1 是正整数，z 。是整数模m 剩余类环，z 麓兰z 。z 。z 。 、。- - - _ _ _ _ _ 、，- - - - _ - - - 一一 r 是z 。上的秩为r 的自由模。记z 麓中的秩为( r ) 的自由z 。- 7 模的个 数为f m ，( ) 。再设1 s 茎tsr ， a 1 ，a 2 ，) 为z 裔中的所有秩 为s 的自由z 。一子模组成的集合，其中礼= ，( s ) 。类似地，给定一些 z 中的秩为t 的自由z 。一子模b 1 ，b 2 ，b m ( m f m ，( t ) ) 使得对任意 的1si j 曼m 有r a n k ( b in b ，) 茎0 t 一1 ，我们可以构造二元常重码 c = c 1 ，c 2 ，c m 如下： c ；= c c m c t 。，其中= 。1 ：山a j c 垡局b i 。c z 2 ，s ， 容易验证，c 是一个( 扎，m ，2 ，t ( s ) 一2 。( s ) ；f m ，t ( s ) ) 二元常重码。于是 2 0 0 4 年中国科学技术大学硕士学位论文第1 1 页 第二章= 元常重码的构造与界2 2 二元常重码的构造 为了确定c 的参数，我们只需计算f m ，( 七) 即可。接下来，我们分几步来得 出计算、，( ) 的公式。首先，我们证明一个很有用的引理。 引理2 2 1 0 把m 分解为素因子的乘积m = p e l p ；2 砖，其中e 。 0 ， p ，为互不相同的素数，则 f m ，r ( ) = - ，( ) 0 知( ) 瑶o ( ) 。 ( 2 , 21 7 ) 证明：由中国剩余定理z 。竺z p ；t 。z 谬。z p ；t ，令r 垒z p ：- 。 z p ；z 。z p ；。，则r 7 垒g 兰墨兰：墨掣z ，且蹋，( 女) 等于r ”中的 秩为k 的自由r 彳模的个数。 对任意的x = ( 互l ，z 2 ，x r ) t r t ，我们把x 写成 x = z l 2 x 2 2 - x r 2甜 其中x j = ( x j l ，x j 2 ，) r 是x 的第j 行( j = 1 ，2 ，r ) 。再记x 的 第i 列为c 。l ( x ) t = ( z z 2 一，x r i ) r ( i = 1 ，2 ，t ) ，则c 。1 ( x ) z l ，且 对任意a = ( a 1 ，a 2 ，a t ) r ， a x = ( a 1 c o l ( x ) 1 ，a 2 c o l ( x ) 2 ，九c o l ( x ) ) 。 设a 是r r 中的秩为21 的自由r 一子模a 记ac z 7 p e l 。为a 中所有 元素的第i 列组成的集合，即 我们断言a 是z 的秩为的自由z p 寻模。事实上，取a 的一组r 一 基( x ( ，x ( 扪，x ( ) ，容易验证 c o l ( x ( 1 ) i ，c o l ( x ( 2 ) ”，c o l ( x ( ) f ) 也是 a 的一组z p ：t 基。 设m = a c r ：r a n k a = 女) 为形中所有秩为女的自由r 子模组成 的集合，n2 ( b 1 ，b 2 ，鼠) ：b ic 珲：。，r a n k b i 。七) ，则我们可以定义 8l22 ，【 2l 一二= r z rc4 、j r z 2 zz ，【 = x r p z 、j x ，【 l oc ，【 | | a 2 0 0 4 年中国科学技术大学硕士学位论文 第1 2 页 董三兰三垄兰兰丝竺竺兰皇墨 ! ! 兰三垄童兰兰竺竺兰 一个映射 妒：m ， a h ( 4 h a 2 ，a t ) 。 接下来我们只要证明妒是双射即司。 先证妒是单射设存在4 ，b m 满足妒) = 妒( b ) = ( a 1 ，a 2 ，a ) 。 取a 的一组冗堪 x ( ，x ( 2 1 ，x ( ) ) 和b 的一组r 罐 y ( ，y ( 孙，y ( 。 那么， c o l ( x ( n ) ：n = 1 ，2 ，自) 和 c o l ( y ( ”) ) ；：扎= 1 ，2 ，。，k ) 是a i 的 两组z p ；。基。所以对任意的i = 1 ，2 ，t 均存在a m a i 2 ，a 抽z p ；t 使 得 k c o l ( y ( 1 ) 。= a 讯c o l ( x ( ”) 。 那么 y ( 1 ) = ( c o l ( y ( 1 ) 1 ，c o l ( y ( 1 ) 2 ，c o l ( y 0 ) ) ) k = h x ”a ， n = 1 其中a 。= ( a 1 。，a 2 。，凡。) r ( 扎= 1 ，2 ，k ) 。类似的，我们可以证明 y ( 2 1 ，y ( ea ，从而有b ca 同理可证acb ，所以必有a = b 。 另一方面，对任意的1 ，a 2 ，a t ) n ，我们要找到一个a m 使 得妒( a ) = l ，a 2 ，a ) 。设 o m q ，a 让) 是a 的一组z p ：t 堪。对 任意的礼= 1 ，2 ，k 陋l n ，n 2 。，n m ) r 7 若存在 a 。= ( a a 1 2 】 取。m z 作为x “的第i 个坐标构成x ”= 则f x ( ，x ( ”，x 佧) 是r 钱性无关的。否则， ，a n ) r ：i = 1 ，2 ，) 使得 a l x ( 1 ) + a 2 x ( 2 ) + + a x ( ) ：0 则 a 1 i 口i 1 + 2 l 口i 2 + + a k i a i k = 0 z p ：。，1 is t 因为 啦l ，啦2 ，o f 让) 是z p ：- 兹性无关的，所以入l ，入2 一，入觚必定全为 0 ，从而a l = a 2 = = 九= 0 ，即 x ( ”，x ( 2 1 ，x ( 。) ) 为r 一线性无关 的令a = 为由 x ( ，x ( 扪，x ( 七) 张成的r 模， 则a 是r r 中秩为k 的自由r 一子模且妒( a ) = ( a l ，a 2 ，a t ) 。 口 罂0 4 量 中国科学技术大学硕士学位论文 第1 3 页 兰三兰三量竺兰兰墼竺兰皇墨 竖! 量垄童兰塞竺垫堇 = = = = = = = = 旨= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = - ! 二_ 二二二= 三兰二! ：。7 = - 引理2 2 - 1 1 设p 为素数，e 1 为正整数，m = p e 。若f d l l ，d 2 】，d ) 为z 毫守一组z m 一线性无关的元素，则它们可以扩充成z 毛的一组z 。毒 ( z ( ，d2 1 ，z ( “，d 七+ 1 1 ，z ( r ) l 。 证明：我f i x ck 使用归纳法。 ( i ) 当k = 1 时 h 、设x 1 = ( z z ，。 1 ) t ，则对任意a o z 。有( a 石 a z 5 l j ， a z l j ) o ，因此p g c d ( 。”z ，z 1 ) 。不妨设p fz ”，即在 取z 麓的标准z m 甚 e ：= ( 0 ，0 ，1 ，0 ，o ) ? ：z ：1 ，2 中e i 只在第i 个分量上有一个非零元l 。显然 x ( 1 ) = 。h l + 。乳2 + 1 0 p e 2 + + p ) e ，x ( 1 ) 。 从而，e 1 ，e 2 ，e r ) 可以被 x ，e 2 ，e ，) z 。线性表出，所以( x ( u ，e 2 e r 也是z 毛的一组z 。一基。 ( 2 ) 设命题对k 一1 成立 因为 x ，x “，x 一1 ) 也是z 。线性无关的，由归纳假设它们可_ 以 扩充为z 岛的一组z m 堪 x ”，x ”，x ( 一，y ( 舢，y ) 。于是x ( ”可 以被这组基线性表出 x ( ) = a l x ( 1 j + a 2 x ( 2 ) + + a k l x ( k 一1 ) + a 女y ( ) + 则至少存在一个k ( 南礼sr ) 在z 。可逆。否则，p i g 矗d ( 丸，扎+ 我们有 k - i n 矿一x = 矿一1 a 。x n ) + 矿一1 。y 这与 x ”，x ( 2 1 一，x ( 。) z 。_ 线性无关矛盾。 + a ，y ( ) 1 ，a ，) (， z 一 = e 0n n x n a 瞄旧 p | | 2 0 0 4 年中国科学技术大学硕士学位论文 第1 4 页 苎三兰三垄兰兰竺竺竺兰皇垦 ! ! 兰三查童童竺! 竺! 兰 不妨设p fk ，则 于是 x ( 1 1 ，x ( 2 1 ，x ( 2 ) ) 可以被扩充为z 幺的一组z 。遵 x ( ，x ( 2 y ( 十，y ( ) 推论2 2 1 2 在引理2 2 1 1 的条件下，a = 是秩的 证明：a = o ：1 z 。x ( “) 皇z 基显然是秩的自由z m 模，由引理2 2 ，1 1 x ( 1 1 ，x ( 2 1 ，x ( 2 ) 可以扩充为z 乏的一组z 。堪 x ，x ( ，x ( 姚，x 8 + “， ，x 7 从而 一 z 二似型0z 。x ”皇z i 。 n = k + l 口 现在我们开始计算乃v ( ) 。 引理2 2 1 3 设p 为素数，e 1 为正整数，m = p 。，则对任意的1 妒叫卜u m r ( 2 ，2 ，2 0 ) 证明：记z 二中含七个元素的z m - 线性无关集的个数为n m ，( 七) ，则 ，( 女) = 心，( 忌) m ，( ) 。我们继续对女使用归纳法。 ( 1 ) 当= 1 时 z 二中的元素x = ( 。l ，勋，研) r 可以张成秩1 的自由z m 一模当且仅 当a x 0 对任意的a 0 z 。成立，即p f g c d ( z 1 ，。2 ，斯) 。于是z 麓 中共有p r e 一矿( e 一1 ) 个元素可以张成秩1 的自由z m 模。 另一方面，任一秩1 的自由z 。摸中有毋( m ) = p 2 一p ”1 个元素可以 作为一组z 。一基，所以 ( 1 ) = 筹 一1 ) ( e 一1 ) ( 矿一1 ) x n yn 天 ，= i fn + 8 x n h 脚 一 一 0 ，p i 为互不相同的素数，则对任意的1sk r f m 州= 鹫p “h “。 b il j a 证明：由引理2 2 1 3 和引理2 2 1 0 立即可得。 至此，我们已经确定了c 的参数。但不幸的是，对于给定的d t 并没有找到合适的方法来找到z 毛的一组秩t 自由子模：b l ，_ 8 2 ， ， u q o 3 磅 加 戒k 唧 k 坷 2 0 0 4 年中国科学技术大学硕士学位论文第1 6 页 第二章二元常重码的构造与界2 3 一些例子 表2 1 1 5 】中的下界 新的下界 a ( 8 ，4 ，6 ) 4a ( 2 8 ，1 8 ，1 5 ) 4 a ( 9 ，4 ，6 ) 芝1 2a ( 3 6 ，1 8 ，1 5 ) 1 2 a ( 1 0 ，4 ，6 ) 3 0a ( 4 5 ，1 8 ，1 5 ) 3 0 a ( 1 1 ，4 ，6 ) 6 6a ( 5 5 ，1 8 ，1 5 ) 6 6 a ( 1 2 ，4 ，6 ) 1 3 2a ( 6 6 ，1 8 ，1 5 ) 1 3 2 使得m 尽量大且r a n k ( b i n b j ) 0 ( 1 i jsm ) 。我们仅有关于 0 = t 一1 的一个特殊结果： 定理2 2 1 5 设m 为正整数，则对所有的15s t 茎r a ( f m ，( s ) ，2 取，t ( s ) 一2 ，t ( s ) ) 之f m ，( ) 。( 2 2 2 2 ) 2 3 一些例子 在本节中，我们给出几个应用上节构造方法的具体例子。这些例子改进 了已知的二元常重码的下界f 1 5 ，这说明了我们的构造方法是有意义的 例2 3 1 应用定理2 2 ，由a ( n ，d ，w ) n 可以得到a ( ( ；) ，2 ( 苫) 一2 ( 2 f ) ， ( ：) ) n 。我们从口珂中选择了一些a ( n ，d ，w ) 的下界，并由此计算出一 些新的下界，这些结果( 见表2 ) 改进了卢可中的已知结果。 例2 3 2 设1 茎fst 曼m 是正整数。选取和f 很接近的8 ，我们根据命 题2 2 7 和命题2 2 9 计算了一些a ( n ，d ，w ) 的上界和下界，并把它们列在 表2 2 和表3 1 中。表2 2 和表3 1 中的上下界非常接近，可见22 2 中的 构造方法可以产生出具有较好参数的二元常重码。 例2 3 3 设z 。= z 6 ，令r = 4 ，t = 3 ，s = 1 ，我们得到f 6 4 ( 1 ) = f 6 ，4 ( 3 ) = 6 0 0 ，r ，3 ( 1 ) = 9 1 以及r ，2 ( 1 ) = 1 2 。根据2 2 3 中的构造方法 可知存在( 6 0 0 ，6 0 0 ，1 5 6 ，9 1 ) 常重码，故a ( 6 0 0 ，1 5 6 ，9 1 ) 6 0 0 。 2 0 0 4 年中国科学技术大学硕士学位论文 第= 章= 元常重码的构造与界 第1 7 页 2 3 一些例子 表2 2 口 m = t = 2 1 = s = 1 8 6 4 a ( 5 1 2 ，1 6 ，8 ) 6 5 1 1 1 2 1 a ( 1 3 3 1 ，2 2 ，1 1 ) 1 2 2 1 31 6 9s a ( 2 1 9 7 ，2 6 ，1 3 ) s1 7 0 1 7 2 8 9 茎a ( 4 9 1 3 ，3 4 ，1 7 ) 2 9 0 1 9 3 6 1 a ( 6 8 5 9 ，3 8 ，1 9 ) 3 6 2 g m = t = f = 2 5 = 1 84 0 9 6s a ( 5 1 2 ，1 4 ，8 ) 4 7 4 5 1 l 1 4 6 4 1 a ( 1 3 3 1 ，2 0 ，1 1 ) 1 6 2 2 6 1 32 8 5 6 1s a ( 2 1 9 7 ，2 4 ，1 3 ) 曼3 1 1 1 0 1 7 8 3 5 2 1 a ( 4 9 1 3 ，3 2 ，1 7 ) 8 9 0 3 0 1 9 1 3 0 3 2 1 墨a ( 6 s 5 9 ，3 6 ，1 9 ) 1 3 7 9 2 2 第三章数字( t ，m ，s ) - 网的构造与界 在本章中，我们首先介绍关于( t ，m ，s ) 一网，数字( t ，m ，s ) 一网和有序正交 阵列( o o a ) 的一些概念，然后利用编码理论中繁衍规则的思想来构造新的 0 0 a ，再通过数字( t ，巩s ) 嗣和o o a 的对应关系得到数字( t ，