（应用数学专业论文）（αβ）几何及相关编码问题的研究.pdf

上海交通大学博士学位论文 ( d ，p ) - 几何及相关编码闻题的研究 摘要 有限几何是组合数学中一个霆要的分支，它为图论、组合设计积编码理论等方向 提供了丰富的源泉对于有限几何的研究，有着重要的理论意义和实际应用背景有限 几何的理论与方法在数理统计、运筹学、信息论帮计算祝科学中都有着重要的地位 ( a ，) 几何魁满足特定条件的关联结构，对它的研究可以追溯到1 9 6 3 年1 9 6 3 年， b o s e 在研究强正虽l 图与p b d 一设计的关系时，提毒了偏几何( 偏几何是，声) 几何的 一种特殊情形) 的概念目前关于偏几何的理论已经非常丰富，但关于一般的( o l ，p ) 一 几何的结果却步得多对( a ，p ) 一几何的另一种特殊情形一半镳几何的研究，是近l o 年活跃在几何界的重要课题在对( q ，p ) 一几何的研究中，不仅发现了一些具有良好性 质的关联结构，揭示了这类关联结构的本质特征，也不断创立与弓 入了许多新的理论 与方法，而这些新的理论与方法也给其他学科方向的研究注入了活力用有限几何研 究线性码是一种行之有效的方法在讨论线性码的最小长度界方面，有限几何是一种 强有力的工具人们也尝试着用几何结构构造好码近年来，数学家和计算机学专家 用几何结构构造了一攒l d p c 码试验显暴，用偏几何构造的l d p c 码在最小距离， 圈长，误码率等方面都有不错的表现我们希望了解更一般的( a ，p ) 几何的性质，能 够构造出薪的凡何结构，并探讨其在信息科学中的应用本文苁( a ，声) 一几何的嵌入、 构造、应用等几个方面进行了研究 本文的王作共分成六郝分。 第一部分是概述，主要讲述丁问题发展的历史和现状、采用的主要方法、面临的 豳雅，并介绍了本文的主要工作 第二部分讨论了( 1 ，卢) - 几何在a g ( 3 ，q ) 中的全嵌入诳明了当q 2 时，一个 ( 1 ，g ) 一几何麓够全嵌入在a g ( 3 ，q ) 中当且仅当它是一个线性表示，并进一步讨论了强 i i i 孛文摘要 正则的情形。另外。还给出了巍2 2 ，a ( 1 ，g ) 一g e o m e t r yc a nb ef u l l ye m b e d d e d i na g ( 3 ，垡) i fa n do n l yi fi ti sa l i n e a rr e p r e s e n t a t i o n 。i nf u r t h e r 。、 ，et a i ka b o 疆毛毛h e c a s eo fs t r o n g l yr e g u l a r ( 1 ，f 1 ) - g e o m e t r i e s 。w ea l s o g i v et h en e c e s s a r ya n ds u f f i c i e n t c o n d i t i o n sf o raf a m i l yo f ( 1 f 1 ) - g e o m e t r i e sf u l l ye m b e d d e di na g ( 3 ，q ) b e i n gl i n e a r r e p r e s e n t a t i o n sw h e n2 1 ) ，一个有限仿射 平面是一个2 一( q 2 ，q ，1 ) 设计 若疋为p g ( k 一1 ，q ) 中一个含有珏个点的集合，满足v c ( k 1 ，q ) 审的任意一个 3 第一鬻绪论 超平面与疋的交点个数最多为r 个并且至少存在一个与足交于r 个点的超平面，则 称赶为一个( 礼，7 ) 一弧( a r c ) 在p g ( 2 ，q ) 中，如果咒是一个非空点集，p g ( 2 ，q ) 中 的每一条线与足交于0 个或者d 个点，则称瓦为度为d 的极大弧度为2 的极大 弧被称为超卵形线 我们所研究的关联结构中有许多是点和线都属于某个射影空间或某个仿射空间的 情形 定义l 。1 9 设s ；沪，i ) 是一个关联结构。如果矽是某个射影空间p g ( d ，d 的点集的子集，是p g ( d ，q ) 的线集的子集，矽是中所有点的并，i 是p g ( d ，口) 申的包含关系，那么称s 被全嵌入在p g ( d ，q ) 中。类似地，可定义艿在仿射空间中 的全嵌入 设a f ( q ) ”是有限域g f ( q ) 上的一个钆维向擞空间g f ( q ) 上的一个( n ，m ) 码c 指的是o f ( q ) “中一个大小为m 的非空子集通常用a l a 2 a 。来表示a f ( q ) n 中的 向量，并称c 中的向量为码字码字v 中非零坐标分量的个数称为它的( h a m m i n g ) 霞量两个码字1 1 1 和v 中不同坐标分鬣的个数称为它们之间的( h a m m i n g ) 距离 定义1 1 1 0 若c 是g f ( q ) “的一个k 一维予空间，则称c 为融，翻一线性码( 或 融，昝码) 迸一步，设d 是c 的最小距离，则称c 为b ，k ，砰码 对于线性码，最小距离和最小重量相等又豳于线性码是一个向量空间，所以可 以用基来加以描述从矩阵的角度，可以将基向量看作一个矩阵的行向量 定义1 1 1 1 设c 是一个i n ，件码。若g 是一个k 髓阶矩阵，它的行向量组构 成e 的一组基，则称g 为c 的一个生成矩阵 如果c 是个b ，嘲一码，g 是c 的生成矩阵，那么c 中的码字是g 的行向量的 线性组合或者说， c = x o l z v f ( q ) “) 由于对个矩阵施行初等行变换( 交换任意两行，在菜一行上乘以一个菲零常数， 把某行的常数倍加到另外一行上去) 不改变这个矩阵生成的向量空间，所以任何行等 4 上海交通大学博士学位论文 价予g 的矩阵也是0 的一个生成矩阵。 称具有形式g = ( i k l a ) 的生成矩阵为标准型，这里厶是阶为k 的单位矩阵由 上瓤的讨论可知，每个线性码都有一个标准型生成矩阵。 考虑g f ( q ) n 中的内积运算设u u l u 2 n 和v v l v 2 是g f ( q ) n 的 两个甸量，它们的内积是1 1 ，v e 坠。u i v i 定义1 1 1 2 设c 是一个【n ，叫一码，令c 上= v a f ( q ) n j u v 一0 ，对任意的 1 1 e 那么称e 上为e 的对偶码。 c 上的生成矩阵被称为c 的奇偶校验矩阵从而有 = x c v ( q ) 羁l h x t 一0 。 王2 礤究鹜最 有限几何是组合数学中一个重要的分支，它为图论、组合设计和编码理论等方向 提供了丰富的源泉对( o t ，圆一几何的研究可以追溯到1 9 6 3 年几十年来，几何学家 从( a ，卢) 一几何的构造、( n ，卢) 一几何在射影空间和仿射空间中的嵌入、( n ，p ) 几何在 其它研究方向的应用等方面进行了研究 设5 是一个阶为( 8 ，t ) 的( o t ，卢) 一几何当理一p 时，称s 为偏几何( p a r t i a l g e o m e t r i e s ) 1 9 6 3 年，b o s e ( 【1 】) 在研究强正则图与p b d 一设计的关系时，提出 了偏几何的概念s ，t ，a 被称为s 的参数，用p g ( s ，t ，o t ) 表示偏几何s 容易计算s 的点图是 s r g ( ( s + 1 ) 延譬盟，8 ( t + 1 ) ，s 一1 + t ( n 一1 ) ，a ( + 1 ) ) 偏几何可以分成以下四种情形： ( 1 ) 口= 1 ，称其为广义四边形关于广义四边形的内容，请参考【2 】 ( 2 ) 8 一s + l 或者对偶地a = t + l ，即2 一扣，5 + 1 ，1 ) 设计和它们的对髑。在 任何关于组合设计的书巾，都可以了解到更多的细节 ( 3 ) 8 一s 或者对偶地口一t 8 一t 时的编几何( 篝pp g ( s ，t ，t ) ) 被称为阶为 5 第一掌鹫 论 8 十1 ，度数为t + 1 的b r u c k 网( f 3 】) 。 ( 4 ) 1 a l ，并 鼠满足下列条件： ( 1 ) 对任意的e t ，马冗，如果t 马，那么tn 马= 西。 ( 2 ) 如果一个m + 1 维子空阐包含莱个e i 冗，那么它和6 个冗i 中的m 维 子空间有6 个公共点，称它为冗的6 - 割，这里6 = o l 或者p ( 3 ) 如果一个p g ( n ，q ) 的点包含在诧的某个元素中，那么它包含在p ( p 是 常数) 个晓一割中 ( 4 ) 如果一个p g ( n ，q ) 的点不包含在冗的任何一个元索中，那么它包含在r ( r 是常数) 个q 一割中。 6 上海交通大学博士学位论文 当= 0 时，强菱剃( a ，) 一线汇是一个s p g 一线汇。 设t 1 ， 咒= 2 ，但是不能被全嵌入在一个p g ( n 7 ，8 ) 中，n 7 n ，那么佗是一 个奇数且s = 面面习。 对于一般的( n ，p ) 一几何在射影空间中的全嵌入，有下述结果 定理1 2 4 ( c a u s h i e 【2 9 】一f 3 0 】)设s = ( p ，i ) 是一个全嵌入在p g ( n ，s ) 中 的( q ，卢) 一几何，8 是一个奇数并且n i 如果p g ( n ，s ) 包含至少一个口一平面或 一个p 一平面，那么s 必定是下列情形之一： ( 1 ) s 是一个( s ，s + 1 ) 一几何，点集是p c ( n ，8 ) p g ( m ，s ) ，1 鬟m n 一2 ，线 集是由p g ( n ，8 ) 中所有与p g ( m ，s ) 不交的线组成的集合 ( 2 ) s 是一个( s ，8 + 1 ) - 几何，点集是p g ( n ， 8 ) p g ( m ，s ) ，1 冬m 1 。如果s 被全嵌入在a g ( n ，q ) 中，那么s 必定是下列情形之一t ( 1 ) s 是o o 上一个集合j 屯的线性表示，瑶。张成h o o 并且型足 o ，1 ，3 ) ； ( 2 ) 2s z ( n ，q ，e ) ； ( 3 ) 嚣一2 并且s 的线和h o o 组成了个对偶的超卵形线； ( 4 ) 7 2 3 并且s = a ( o 。) ； ( 5 ) n 一4 并且s = t q ( 4 ，q ) 用有限几何研究线性码是一种行之有效的方法。在讨论线性码的最小长度界和2 - 重码方面，有限几何是一种强有力的工具设e 是g f ( q ) 上的一个hk ，d 一码，g 为生成矩阵，且没有一个坐标位满足所有码字在这个位置的分量力0 。g 的列可以被 看作是p g ( k 一1 ，q ) 中住个点的多重集如果g 中任意两列都线性无关，则称c 为一 个射影码。记g 的行向量分别为v l ，v 2 ，v 患；列向量分别为u l ，u 2 。，u 拈那么 ( ) j = ( ) i ，i = 1 ，2 ，钆，歹= 1 ，2 。，惫对任意的8 霹，码字1a j v j 最多有礼一d 个坐标向量为零，从而对i = 1 ，2 。，珏，可知肇l 哟( q ) i = 0 最多有 似一d 个解即箍1 ( u t ) j 一0 最多有礼一d 个解也就是说在8 所对应的超平面上 最多有他一d 个啦通过上面的分析可以知道，在p g ( k l ，q ) 中，一个( 扎，一d ) 一 弧等价子一个射影i n ，k ，田码这样，在线性码和关联几何之间建立了联系几何 学家运用有限几何的知识，讨论关于线性码的最小长度界问题，取得了丰富的结果。 关于这方面的内容，请参考【3 7 】一译6 】相关结果请参考h t t p ：w w w a p p m a t h o s a k a - w u 。a c j p m a r u t a g r i e s m e r h t m 和h t t p ：w w w w i n 。t u e n l a e b v o o r l i n c o d h t m l 。 如果一个码中码字的重量只有两个取值，那么称这个码为2 一重码( t w o - w e i g h t c o d e s ) 2 重码的对偶屉一类非常重要盼码一均匀填充码( u n i f o r m l yp a c k e dc o d e s ) 在射影2 。重码和强正则图之间有着很密切的联系设p 是p g ( r ，g ) 中的一个点集， 将p g ( r ，q ) 作为一个超平面嵌入到p g ( r + 1 ，q ) 中定义一个图r ( p ) ，顶点集是 p o ( r + 1 ，q ) p a ( r ，q ) ，两个顶点相邻接当且仅连接它们的p g ( r + 1 ，q ) 申的线与 p g ( r ，q ) 棚交的点在p 中r ( p ) 是一个正则图，可= q 什1 ，价k = ( q i ) i p l i o 上海交通大学博士学位论文 d e t s a r t e ( 1 9 7 2 年，【4 曩) 蒌骥了这个强是强正嬲的当显仅当p g ( r , q ) 的超平褥与 p 的点相交数只有两种可能取值c a l d e r b a n k 和k a n t o r ( 1 9 8 6 年， 4 8 】) 讨论了强 王受l 图秘线性2 一重码鲸关系。1 9 9 7 年，b r o u w e r 秘v a n e u p e n ( 攀9 】) 在线性谷重 码和射影码之间建立了一一对应关系d ec l e r c k 和d e l a n o t e ( 2 0 0 0 年，【5 0 ) 构造 一些毅的线性2 一重码2 0 0 5 年，b o u y u k l i e v 【5 1 】) 等入研究了射影2 一重码，并 给出了小参数下的等价分类由一个强正则( q ，p ) 一线汇可以构造一个强正则图，从而 可以产生一个线性2 - 重码。 近年来，人们也尝试着用几何结构构造好码可以进行叠代译码的区组码，也叫 低密度码( l d p c 码) ，首先由g a l l a g e r 1 9 6 2 年，【5 2 】) 提出。低密度奇偶校验码 中稀疏的奇偶校验矩阵对于译码来说是关键的最近几年，对l d p c 码的研究引起了 极大的关注，这是由予人们对t u r b o 码的整薪认识，发现它菲常接近s h a n n o n 弄。对 于l d p c 码，和一积算法有关于区组长度的线性译码复杂度，这使得对非常长的码进 行译码是可行的2 0 0 1 年，y ，k o u ，s 。l i n 积m 。pc 。f o s s o r i e r 【5 3 】) 开始月 几何结构构造l d p c 码同年，v o n t o b e l 和t a n n e r ( 【5 4 】) 用广义四边形构造了一 批l d p c 码2 0 0 4 年，j o h n s o n 和w e l l e r 5 5 1 ) 用偏几何构造了一揽l d p c 码。 试验显示，用偏几何构造的l d p c 码在最小距离，圈长，误码率等方面都有不错的表 现。关于这方面的知识，请参考【5 3 一 6 0 】。 王3 本文圭要工佟 本文首先讨论了( 1 ，卢) 一几何在a g ( 3 ，q ) 中的全嵌入。证明了当譬 2 时，一个 ( 1 ，g ) 一几何能够全嵌入在a g ( 3 ，q ) 中当噩仅当它是一个线性表示并给出了当2 2 ) 的概念刻画了一类极大可诱导网的强正 则( 1 ，p ) - 几何的特性本文还用群论的方法构造了一类( q ，) 一几何证明了当g 是 a b e l 群时，这一理论几乎等价予对( o l ，多) 一线汇的研究在( 穗，声) 一几何的应用方面。 1 1 第一搴绪论 我们用半偏几何构造了一批l d p c 码试验显示，这类l d p c 码性能良好本文的 最后用有限几何的方法刻画了一类线性码的最小长度界 一) ( 1 ，p ) 一几何在a g ( 3 ，q ) 中的全嵌入 在对全嵌入在a g ( 3 ，q ) 中的( 1 ，p ) 一几何( p 2 ) 的研究中，我们首先对a g ( 3 ，q ) 中的仿射平面进行了分类设s = 护，i ) 是全嵌入在a g ( 3 ，q ) 中的一个阶为( q - 1 ，t ) 的( 1 ，卢卜几何( 2 ) ，7 r 是a g ( 3 ，q ) 中的一个平面令r = pn7 f ，岛= l t l ，lc 霄 定义子空间几何岛为关联结构( ，丌，i 。) ，这里薹坩是诱导出的关联 关系作为讨论的基础，我们有下面的命题 霉l 理1 3 1 。设s 是一个金嵌入在a g ( 3 ，q ) 中的一个阶为( q l ，t ) 的( 1 ，p ) 一几 何( p 2 ) ，7 r 是a g ( 3 ，g ) 中的一个平面，那么7 r 必为下列情形之一 ( 1 ) ，r 不包含s 的任何反旗； ( 2 ) s 在7 r 上的限制是一个b r u c k 网，即p g ( q 一1 ，t ，t ) ； ( 3 ) q 一2 矗，岛是一个p g ( 2 矗一1 ，1 ，2 ) ，h 0 ； ( 4 ) 7 r 为退化平面，即s 是s 中若干条共点的线； ( 5 ) 不潺于上面任一情形此时称霄为混合平面 在上述分类中，只有混合平面的性质不清楚我们首先讨论了混合平面的特征 充分裂蔫穰= 1 的特性，得到了下面的孳 理 引理1 3 2 设s 是一个全嵌入在a g ( n ，q ) 中的( 1 ，p ) 一几何，p 2 ，他 2 如果7 r 是a g ( n ，q ) 中的一个混合平面，鄢么过最中酶任一点有1 条或多条中的 线，并且这两种情形