（应用数学专业论文）广义双可分解填充和有关的码.pdf

广义双可分解填充和有关的码摘要 摘要 常重复合码( c c c ) 是二元常重码的推广由于常重复合码在跳频序列、 电力线通信技术中有广泛应用，近年来国际上有关常重复合码的研究比较 活跃d i n g 等人证明了与最优c c c 对等的组合结构是最优广义双可分解填 充( g d r p ) 本文对最优g d r p 的结构，构作方法以及存在性进行了研究， 借助于最优g d r p ，建立了系列构作最优c c c 的组合方法和新的码类 2 0 0 3 年，l u o 等人建立了c c c 的一个上界( 简称为l f v c 界) ，此界成 为许多研究者判定c c c 最优性的准则第二章首先给出了这个界的组合证 明，然后揭示了达到这个界的最优g d r p 的结构，最后建立了一些g d r p 新 的上界，这些界是我们下文中g d r p 最优性的判别准则 第三章讨论了达到l f v c 界的最优g d r p 的构作方法及存在性首先， 我们引入了一些新的辅助设计，建立了若干构作最优g d r p 的有效方法 接着，我们完全解决了满足3 a = 2 p 的最优g d r p 的存在性问题；基本解决 了满足4 a = 3 p 的最优g d r p 的存在性问题( 仅留下两个可能的例外) ，其中 a ，p 为任意正整数另外我们还得到了满足5 a = 4 肛的最优g d r p 的渐近存 在性结果由此得到了最优c c c 的码类与此同时，我们还改进了l a m k e n 关于互补f r a m e 和n g b t d 的存在性结果 第四章讨论了达到推广的l f v c 界的最优g d r p 的结构和构作方法 我们引入了一类具有指定性质的差族，称为可分解差族，并通过可分解差族 建立了最优g d r p 的构作方法和存在性结果第五章给出了最优g d r p 的 一些其它构作方法最后一章我们提出了若干进一步的研究问题 关键词：广义双可分解填充；常重复合码；f r a m e 广义双可分解填充；可分 解差族 作者：严洁 导师：殷剑兴( 教授) 广义双可分解填充和有关的码英文摘要 g e n e r a l i z e dd o u b l yr e s o l v a b l ep a c k i n ga n d t h ec o r r e s p o n d i n gc o d e s a b s tr a c t c o n s t a n tc o m p o s i t i o nc o d e ( c c c ) i sag e n e r a l i z a t i o no fb i n a r yc o n s t a n tw e i g h t c o d e t h ec o n s t a n tc o m p o s i t i o nc o d e sh a v ea r i s e nr e c e n ti n t e r e s td u et ot h e i rn u m e r o u sa p p l i c a t i o n si nf r e q u e n c yh o p p i n gs e q u e n c e s ，p o w e r l i n ec o m m u n i c a t i o n sa n d s oo n d i n ge t c p r o v e dt h a ta no p t i m a lc c ci se q u a lt oa no p t i m a lg e n e r a l i z e d d o u b l yr e s o l v a b l ep a c k i n g ( g d r p ) t h i sd e s s e r t a t i o ni n v e s t i g a t e st h es t r u c t u r e ，t h e c o n s t r u c t i o na n dt h ee x i s t e n c eo fo p t i m a lg d r p s m a k i n gu s eo fg d r p s ，w ee s t a b l i s h as e r i e so fc o m b i n a t o r i a lm e t h o d so fc o n s t r u c t i n go p t i m a lc c c sa n ds o m en e wf a m i l i e s o fo p t i m a lc c c s i n2 0 0 3 ，l u oe t c e s t a b l i s h e da l lu p p e rb o u n do fc c c ( a nl f v cb o u n di ns h o r t ) ， w h i c hh a sb e c o m eab e n c h m a r ko fm a n yr e s e a r c h e r sm e a s u r i n gt h eo p t i m a l i t yo fc c c c h a p t e r2f i r s tg i v e sac o m b i n a t o r i a lp r o o fo ft h el f v cb o u n d ，t h e ni m p o s e st h e s t r u c t u r eo fo p t i m a lg d r p s m e e t i n gt h el f v cb o u n d ，f i n a l l yb u i l d ss o m en e wu p p e r b o u n d so fg d r p s ，w h i c ha r eo u rb e n c h m a r k st om e a s u r et h eo p t i m a l i t yo fg d r p s c h a p t e r3d i s c u s s e st h ec o n s t r u c t i o na n dt h ee x i s t e n c eo fo p t i m a lg d r p sm e e t i n g t h el f v cb o u n d f i r s t l y , w ei n t r o d u c es e v e r a ln e wa u x i l i a r l yd e s i g n sa n dp r e s e n ts o m e v a l i dm e t h o d so fc o n s t r u c t i n go p t i m a lg d r p s s e c o n d l y ，w ec o m p l e t e l ys o l v et h e e x i s t e n c ep r o b l e mo fo p t i m a lg d r p ss a t i s f y i n g3 a = 2 肛，a l m o s ts o l v et h ee x i s t e n c e p r o b l e mo fo p t i m a lg d r p ss a t i s f y i n g4 a = 3 p w i t ho n l yt w op o s s i b l ee x c e p t i o n s ， a n do b t a i na na s y m p t o t i cr e s u l tf o ro p t i m a lg d r p ss a t i s f y i n g5 a = 4 弘，w h e r ea a n dpa r ea n yp o s i t i v ei n t e g e r s t h ec o r r e s p o n d i n go p t i m a lc c c sa r et h e no b t a i n e d i i 广义双可分解填充和有关的码英文摘要 m e a n w h i l e ，w ei m p r o v et h ee x i s t e n c er e s u l t so fc o m p l e m e n t a r yf r a m e sa n dn g b t d s g i v e nb yl a m k e n i nc h a p t e r4 ，w ed i s c u s st h es t r u c t u r ea n dt h ec o n s t r u c t i o no fo p t i m a lg d r p s m e e t i n gt h eg e n e r a l i z e dl f v cb o u n d ad i f f e r e n c ef a m i l yw i t ht h ep r e s c r i b e dp r o p - e r t i e s ，c a l l e dr e s o l v a b l ed f ，i si n t r o d u c e da n du s e dt oe s t a b l i s hc o n s t r u c t i o n sa n d e x i s t e n c er e s u l t so fo p t i m a lg d r p s s o m eo t h e rc o n s t r u c t i o n so fo p t i m a lg d r p sa r e p r o v i d e di nc h a p t e r5 i nt h ef i n a lc h a p t e r ，w ep r e s e n ts o m eo p e np r o b l e m sf o rf u r t h e r s t u d y k e y w o r d s ：g e n e r a l i z e dd o u b l yr e s o l v a b l ep a c k i n g ；c o n s t a n tc o m p o s i t i o nc o d e ；f r a m e g e n e r a l i z e dd o u b l yr e s o l v a b l ep a c k i n g ；r e s o l v a b l ed i f f e r e n c ef a m i l y i i i w r i t t e nb yy a nj i e s u p e r v i s e db yp r o f y i nj i a n x i n g 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立 进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文 不含其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏 州大学或其它教育机构的学位证书而使用过的材料。对本文的研究作 出重要贡献的个人和集体，均已在文中以明确方式标明。本人承担本 声明的法律责任。 研究生签名：至三圭 日期：兰盟垒垒日。日 研究生签名： 21 里 日 期：竺竺士竺月 目 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论 文合作部、中国社科院文献信息情报中心有权保留本人所送交学位论 文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论 文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的 保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的 全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名： 导师签名：级多乡 。 7 日 期：趔生垒身7 日 日 期：呵日 第一章绪论研究背景 第一章绪论 1 1 研究背景 当我们把二元常重码推广为多元时，就产生了常重复合码的概念早 在上世纪六十年代，文 4 3 】和文【4 4 】就对非二元常重复合码进行过研究，但 是关于常重复合码的系统研究从上世纪九十年代才刚刚开始( 见s v a n s t r s m 4 9 】) 本文研究常重复合码的组合结构，并且应用各种组合构作方法得到一 些最优的码类我们首先介绍有关常重复合码的定义和记号 ( 一) 常重复合码 下面我们采用码论中的标准记号令磊表示集合 o ，1 ，m 一1 ) ( 字 母表) ，编为上的所有n 维向量( 字) 的集合，此处m 是一个正整数 一个长为n 的m 元码是一个集合cc 霸两个码字u ， c 的汉明距离 记为妇( 钍，u ) 如果对于所有的让，t ，c ，d h ( u ， ) d ，那么称一个码c 具有距离d 一个码字u c 的重量是牡的非零分量的个数若c 中的每 个码字都有重量w ，则称c 具有常重量伽一个长为礼，大小为m ，距离 为d ，具有常重量w 的m 元码记为一个( 仃，m ，d ，) mc w c 一个码字t c 的复合是一个向量页= 【a 。，入l k 一。】，使得牡包含i 乙恰好九次如 果c 中的每个码字都有复合天，那么一个m 元码c 具有常复合页一个长 为n ，大小为m ，距离为d ，具有常复合【h ，a h 一。】的m 元码记为一 个( n ，m ，d ，a ”k 一】) mc c c 大小达到最大的( n ，m ，d ， a o ，a ”a m 一1 d m c c c 称为是最优的 显然，常重复合码是常重码的一个子类，而置换码( 【4 】_ 6 】， 1 8 】， 1 9 】， 2 5 】， 【2 6 】， 4 6 】) 和二元常重码( 【2 】【8 】 2 7 ， 4 1 】， 5 2 】) 又是特殊的常重复合码近年 来，由于常重复合码在电力通信技术( 【1 1 ，1 5 】) ，跳频序列( 1 3 】) 等方面有着 广泛的应用，引发了研究者极大的兴趣如今确定一个常重复合码大小的 第一章绪论研究背景 最大值成为诸多文献研究的一个中心问题( 【1 2 】， 2 0 1 - 2 3 1 ， 4 0 i ，【5 0 ， 5 1 】) ( 二) 广义双可分解填充 一个阶为可的设计是一个对子( x ，4 ) ，其中x 是秽个元素的集合( 称 为点) ，4 是x 的子集族( 称为区组) 一个设计的一个a 一平行类是4 中一 些区组的集合，使得x 中的每个点恰出现在o t 个区组中当a - - - - 1 时，简 单称之为平行类如果每个相异点对至多出现在a 个区组中，并且每个点 恰好出现在竹个区组中，那么该设计( x ，4 ) 称为是( 佗，a ) 一填充当我们提 及( n ，a ) 一填充，就蕴涵着确实有两个不同的点出现在a 个区组中在文献 中，如果每个相异点对恰出现在入个区组中，那么此时的填充通常被称为一 个成对平衡设计( p b d ) 为了一致起见，“填充”被认为包括了这种恰当的 情形这里一个( n ，a ) 一填充的区组大小是没有约束条件的，允许区组大小 为一 如果一个阶为t ，的( 礼，a ) 一填充，它的区组可以安排成个仇佗阵冗， 满足下列性质： 1 冗的每一个位置要么是空的，要么包含一个区组； 2 对于任意0 i m 一1 ，冗的第i 行的区组构成一个九一平行类； 3 冗的每一列的区组构成一个平行类 那么我们称之为一个广义双可分解填充，记作g d r p ( n ，a ；口) 重集t = a o ，a 。， ，a , - i ) 称为是该g d r p 的型由定义易知n = 7 2 0 1 九通常情况下用指 数符号来记g d r p 的型当指数符号夕? 1 镀2 夕 被使用时，意味着有n = a 1 9 1 + a 2 9 2 + + a s 9 5 并且m = a l + a 2 + + a 3 如果a o = a 1 = = h 一1 = 1 且m = n ，那么一个g d r p 就是通常意义下的双可分解填充( 见 1 8 】) 常重复合码( c c c ) 的编码问题推动了对广义双可分解填充( g d r p ) 的 研究我们可以利用广义双可分解填充和常重复合码的等价关系，通过构作 广义双可分解填充来得到最优的常重复合码 2 第一章绪论 主要结果 1 2主要结果 本文对与最优常重复合码( c c c ) 对等的组合结构广义双可分解填充 ( g d r p ) 进行了探讨，借助于g d r p ，我们建立了一系列构作最优c c c 的组 合方法和新的码类 在第二章中，我们推广了l f v c 界，得到如下定理 定理2 4 1 假定存在一个型为 a o ，a 1 一，a m 一。) 的g d r p ( n ，a ； ) 对任意的 0 i m 一1 ，令 = 引且南刊听 则有 ( 2 屯 + n ( 斤一五) ) a ( 口一1 ) 另外，我们还建立了g d r p 其它一些新的上界可以说明这些界都是紧 的 定理2 4 4 对于任意的正整数m 和入， 上 m ( n ，a ， a ，a ，入】) m ( n 一1 ) 定理2 4 5 对于任意的整数仇2 ， b m ( 2 m ，3 ，【2 ，2 ，2 】) 2 m ( m 一2 ) ( 2 m 一1 ) 定理2 4 6 对于任意整数入， b m ( n ，a + 1 【入+ 1 ，等( a m - 1 ) m 在第三章中，我们讨论了达到l f v c 界的最优g d r p 首先，我们揭示 了型为入1 矿一1 ( a p ) 的最优g d r p ( n ，a ；u ) 的特性，并由此简化了相应的 g d r p 的构作接下来，我们推广了经典的s t a r t e r a d d e r 方法，给出了最优 第一章绪论主要结果 g d r p 的一种直接构作方法然后，我们引入了若干新的辅助设计，并由此 导出了一些构作最优g d r p 的有效方法作为这些方法的应用，我们完全 解决了满足3 a = 2 p 的最优g d r p 的存在性问题，基本解决了满足4 a = 3 肛 的最优g d r p 的存在性问题( 仅留下两个可能的例外) ，另外还得到了满足 5 a = 4 p 的最优g d r p 的渐近存在性结果，其中入，弘为任意正整数 定理3 6 9 设a ，p 和m 为任意正整数，其中3 a = 2 p 且m 2 ，则一个型 为a 1 矿一1 的最优g d r p ( n ，a ；u ) 存在 定理3 6 2 2 设a ，p 和m 为任意正整数，其中4 a 亍3 p 且仇隹 4 2 ，4 5 ，则 一个型为a 1 p 一1 的最优g d r p ( n ，a ；u ) 存在 定理3 6 2 6 设a ，p 和m 为任意正整数，其中4 a = 3 p 且m 5 3 0 ，则一个 型为a 1 p 一1 的最优g d r p ( n ，a ；t ，) 存在 在第四章中，我们研究达到推广的l f v c 界的最优g d r p 我们定义了 一类具有指定性质的差族，称为可分解差族，并通过可分解差族建立了最优 g d r p 的构作方法和如下存在性结果 定理4 2 5 设，和仇为正整数，满足，为奇数且m 4 如果m ，+ 1 是一个 奇素数幂，那么存在一个型为( m f 2 ) 号( m f 2 + 1 ) 詈的最优g d r p ( n ，止2 业+ 1 ；m f + 1 ) ，等价地，存在一个最优的( n ，m + 1 ，m ( m 2 - + 2 ) - ， 孚，巫2 ，孚，孚+ 1 ，警+ 1 ，警+ 1 】) mc c c ，其中n = r e ( m 2 r - l - 1 ) ，巫2 出现虿e r g 次 定理4 2 6 设，和m 为正整数，满足m 3 如果m f + l 是一个素数幂，那么 存在一个型为( m y + i ) m 的最优g d r p ( m ( m f + i ) ，( ，一1 ) 仇+ 2 ；m f + 1 ) ，等价地， 存在一个最优的( r e ( m r + 1 ) ，m f + l ，m ( m ，一f + 2 ) - 2 ， m f + l ，m f + l ，m ，+ 1 】) m c c c 在第五章中，我们给出了最优g d r p 的一些其它构作方法和存在性结 果，其中包括用w e i l 定理构作，通过有限域上的离散对数表构作以及用频 率长方构作 4 第二章关于g d r p 的界g d r p 与常重复合码的等价性 第二章关于g d r p 的界 本章主要介绍g d r p 的界由于g d r p 与常重复合码具有等价关系， 所以常重复合码的界就等价于g d r p 的界在此基础上我们首先介绍了一 些码论中已知的界；接着，我们给出了l f v c 界的组合证明；然后，我们建 立了一些新的界；最后，我们介绍了达到l f v c 界的最优g d r p 的结构 2 1 g d r p 与常重复合码的等价性 下面的定理来自于文 2 2 】 定理2 1 1 一个型为 a o ，a 1 ，k 1 ) 的g d r p ( n ，a ； ) 的存在性等价于一个 ( 礼，m ，d ，a ”a 一1 】) mc c c 的存在性，其中m = 口，n = 扛t n - - 0 1 凡并且 d = n a 我们用下面的简单例子来说明定理2 1 1 中g d r p 与c c c 之间的密切联 例2 1 2 下面的阵冗表示了一个型为4 1 2 3 的g d r p ( 1 0 ，2 ；1 0 ) ： 1 ，2 ，3 ，6 】( 2 , 3 ，4 ，7 】- 3 ，4 ，5 ，8 ) 4 ，5 ，6 ，9 ) o ，5 ，6 ，7 )( 1 ，6 ，7 ，8 ) 2 ，7 ，8 ，9 ) 0 ，3 ，8 ，9 】 o ，l ，4 ，9 ) 0 ，1 ，2 ，5 】- 4 ，7 】- 5 ，8 ) 6 ，9 ) o ，7 】 1 ，8 ) 2 ，9 ) 0 ，3 ) 1 ，4 2 ，5 ) 3 ，6 】 5 ，9 】 o ，6 ) 1 ，7 ) 2 ，8 ) 3 ，9 ) o ，4 ) 1 ，5 ) 2 ，6 】 3 ，7 ) 4 ，8 ) 0 ，几( n a ) 三0 ( m o dn ) 且n 一入0 ( r o o d 丙) ，那么 b m ( 礼，a ， a 。，a l ，一，a m - 1 】) 坐- 1 文 3 3 】中的j o h n s o n 界是常重码一个经典的上界这种定界的方法在 5 1 】 中应用于三元c c c 这里我们将这个方法进一步推广得到下面的引理 引理2 2 4 对于任意满足0 r m 一1 的整数r ，我们有 b m ( n ，a ，a 1 一，h 一1 】) 罟( 扎一1 ，a 一1 ，际，焉，c 。】) ， 其中 趸= 协i1 臻i ： 证明：设( x ，4 ) 是一个型为 知，a ，k 一 的g d r p ( n ，a ； ) ，它的区 组能表示成一个m 礼的阵冗= ( b i j ) 对于任意给定的r ( 0 r m 一1 ) ，我 们固定第r 行的一个区组，记为耳。我们从冗中删去耳。所在的第c 列， 然后用b n 耳。替代导出的子阵中的所有区组b 这产生一个定义在耳。上 的m ( n 一1 ) 的区组阵m 由于对任意的i ( 0 i m 一1 ) ，冗中第i 行的 区组构成一个入；一平行类，而冗的每一列的区组构成一个平行类，我们能看 出阵m 给出一个b r 。上的型为【焉，石，c 1 ) 的g d r p ( n 一1 ，入一1 ；i b r 。1 ) 因此，l 研。l b m ( 佗一1 ，入一1 ，【焉，石，c 。】) 这个不等式与c 的选择无关 计算所有的点在冗的第r 行中出现的总次数，给出 入，b m ( n ，a ，队o ，a 1 ，a m 一。】) n b m ( 扎一1 ，a 一1 ，【焉，焉，兀= = 二。】) 于是结论成立 2 3 l f v c 界的组合证明 文 4 0 】给出了引理2 2 2 中l f v c 界的一种证明本节我们从组合设计 的角度给出l f v c 界一个新的证明 7 第二章关于g d r p 的界 一些新的界 风( 训h 小 一) 雨币冬 证明：设( x ，a ) 是一个型为 a o ，a 1 ，h 一。) 的g d r p ( n ，a ；u ) ，如上一 章所述，其区组可表示成一个矾嚣阵冗对于任意的0 i m 一1 和 1 歹死，设南为冗中( ，歹) 位置的区组大小，也就是说，这个g d r p 中 久；一平行类和第j 个平行类的公共区组的大小于是有危0 且 向= n t ， 计算包含在4 的区组中不同点对的数目，我们有 m - 1 疗 m - 1 刀| ) t v ( v 一1 ) 南( 向一1 ) = l 局l n ， ( 1 ) i = 0j = 1 i = 0j = l 由c a u c h y - s c h w a r t z 不等式，我们得到 羚掣：譬 对任意的i ( 0 i m 一1 ) 成立 结合( 1 ) 和( 2 ) 可以导出 知( u 一1 ) 圣墨鲨芝一舭 入口( u 一1 ) 刍竿一n u 若有( ”证t - g w 0 1 埒) 一a 仃 0 成立，则我们可化简得到 口甚禹 2 4 一些新的界 在这一节中我们将建立如( 死，a ，盼o ，a 一，k 一。】) 的一些新的界首先， 我们推广了引理2 2 2 中的l f v c 界，建立了下面的定理 8 第二章关于g d r p 的界一些新的界 定理2 4 1 假定存在一个型为 a o ，a 1 ，a m - 1 ) 的g d r p ( n ，a ；u ) 对任意的 0 i 仇一1 ，令 = 引v a i j it i = v a i - n f i 则有 ( 2 屯 + n ( 斤一 ) ) a v ( v 一1 ) ( 3 ) 证明：如引理2 2 2 证明中那样定义南，我们同样有向0 ， 厶= 舢 和( 1 ) 成立众所周知( 例如见【7 】) ，当任意对子8 ，t ) ( 1 s ，t 礼) 满足 k zs i 1 时，n 个非负整数的平方和达到最小值因此 局( n 一血) 芹+ 屯( + 1 ) 2 ( 4 ) j 2 1 。 对任意的i ( 0 i m 一1 ) 成立 结合( 1 ) 和( 4 ) 产生 ) t v ( v 一1 ) ( 芝渤吨) 斤- 4 - “ 4 - i - - - - 01 ) 2 ) ) ， 一) i ( ( n 一屯) 斤屯( 1 ) 2 ) ) 一n 口， 即 a v ( v 一1 ) e ( 2 t i l l4 - 礼( 骨一五) ) 注：对于定理2 4 1 的特殊情形仇= 3 ，s v a n s t r s m 等【5 1 】中可见另外，文 【7 】中有与定理2 4 1 类似的关于c w c 的描述 定理2 4 1 给出的界比l f v c 界更紧，而它又是l f v c 界的推广，故称之 为推广的l f v c 界这个定理是说，如果是满足不等式( 3 ) 的所有口的最 大值，那么( 佗，a ，a ，h 一。】) 更进一步，若伽使得( 3 ) 中等号成 立，则我们称咖对应的g d r p 达到推广的l f v c 界通过这个定理我们还 得到下面的两个结果 9 第二章关于g d r p 的界 一些新的界 定理2 4 2 设存在一个常数k ，使得对任意的i ( o i 仇一1 ) ，有【譬j = k 如果有 笺掣1会 塑等篙1 塑， ( 5 ) ( 口一) 一佗 u ( u + ) 。 、7 男墨么三m ( n ，a ， a o ，a l ，a m 一1 】) u 证明：对于任意的i ( o i m 一1 ) ，如果有【譬j = k ，那么定理2 4 1 中 的不等式( 3 ) 可以简化为 2 v k n m ( n k 2 + n k ) v ( v 一1 ) a ， 且 a 、2 k v m ( k 2 + k ) 元可矿矿。 n u i 口一上j 更进一步，我们有k 【丛竽j k + 1 因此，我们可以假设当i t 时，【丛竽j = k ，其中t o ，1 ，m 一1 ) 为某个子集合，且当i 于= o ，1 ，m 一1 ) t 时，【丛竽j = k + 1 于是定理2 4 1 中不等式( 3 ) 的左端 就能表示成 礼( 2 后( + 1 ) 一m ( 七2 + 七) ) + 2e t 。， 5 予 其中t 。= ( 口+ 1 ) a 。一n ( 七+ 1 ) 0 ( s 于) 由假设，我们有 a ( + 1 ) 0 且n d n 2 + ( 硝+ a ；+ + 磕一。) i 钆d 成立为了方便起见，我们采用下面的记号： d ：= n a ， 一n ：- - n d n 2 + o i m 一1a ( = 0 5 i m 一1a ；】一a 礼) ， 生 9 c d 一；i ：i = 0 ，l ，m 一1 ) ， n ：- - n a ， 瓦：- - - 礼天 因为n = 嘣 0 这同时表明n 一a ) 能被( a 3 + a + + a 象一1 ) 一加整除最近，文【2 3 】给 出了具有相同频率的最优g d r p 的一个有力的构作方法这里，我们主要关 心的是型为a 1 旷_ 1 ( a p ) 的最优g d r p ( n ，入； ) 首先，我们给出以下事实 定理3 1 1 设a ，p 为两个正整数，满足a p 如果一个型为a 矿一的最优 g d r p ( n ，入； ) 存在，那么p ai 入且 f 扎= ( p a ) ( m 一1 ) ( 支+ 1 ) + 】， ja = ( p a ) 天， 1p = ( p a ) ( 爻+ 1 ) ， i i 钞= 忐， 其中天= 上t - , k 证明：我们注意到对于一个型为入1 p 一1 的g d r p ( n ，a ； ) ，l f v c 界 成为忐，其中n = ( m 一1 ) 肛+ a 因为给出的g d r p 是最优的，我们有 钉= 忐由引理2 5 1 可知，在任何一个最优g d r p ( n ，a ；u ) 中( 达到l f v c 界) ，对任意的i ( 0 i 仇一1 ) ，九平行类的区组有相同的大小因此， 在任意一个型为a 旷- 1 的最优g d r p ( n ，a ； ) 中，我们能够假设唯一的p 一平 行类的区组大小为丘，a 一平行类的区组大小为 于是 = 警= 击且 14 第三章最优g d r p 的f g d r p 构作 s t a r t e r a d d e r 方法 丘= 警= 忐因此# - a la ，同时我们有a = ( p a ) j i ，p = ( p a ) ( 天+ 1 ) 从而 佗= ( 价一1 ) p + 入= ( m 一1 ) ( p a ) ( 天+ 1 ) + ( 肛一a ) 天= ( p a ) ( m 一1 ) ( 爻+ 1 ) + 天】 口 我们注意到一个型为爻1 ( 天+ 1 ) m 一1 的最优g d r p ( 壳，爻；台) 的阶台和一个型 为a ，矿一- 的最优g d r p ( n ，a ； ) 的阶相等，其中a = ( p a ) 天从定理3 1 1 的 证明中我们可以看出，后面的g d r p 可以由前面的g d r p 复制肛一a 次得 到我们在下面的定理中记录这个事实 定理3 1 2 设1 a p 为两个整数，满足p aia 且天= 志如果一个 型为天，( 爻+ 1 ) m 一1 的最优g d r p ( f i ，爻； ) 存在，那么一个型为a 1 矿一1 的最优 g d r p ( n ，入；u ) 存在 由定理3 1 2 ，我们只需要对型为a 1 ( a + 1 ) 一1 的g d r p ( n ，a ； ) 描述构作 方法就行了在这种情况下，l f v c 界( a + 1 ) m 一1 = n 因此，t ，= n 记 k = 入+ 1 于是一个型为a 1 ( a + 1 ) m 一1 的最优g d r p ( n ，a ；口) 的参数能被唯一的 表示成 f 口 = n ， m = 警， ( 6 ) i - a = k 一1 更进一步，从定理3 1 1 的证明中我们知道它的m 一1 个k 一平行类中的区组 大小均为k ，而唯一的( 七一1 ) 平行类的区组大小均为七一1 为了记号方便， 我们记一个型为a 1 ( a + 1 ) 一1 的最优g d r p ( n ，入；钉) 为g d r p ( k ，竹) 当这个记 号被使用时，参数仇，a 和口由( 6 ) 式确定 3 2 s t a r t e r - a d d e r 方法 本章我们考虑的最优g d r p 都是型为a 1 矿- 1 的最优g d r p 根据定理 3 1 2 ，我们只需要考虑型为天1 ( 支+ 1 ) m 一1 的最优g d r p ，简记为g d r p ( k ，n ) 在本节中，我们给出了一种新的直接构作方法，称为s t a r t e r - a d d e r 方法 s t a r t e r a d d e r 方法曾在【4 7 】中被用于构作r o o m 方，在l a m k e n 3 8 】中被用于 1 5 第三章最优g d r p 的f g d r p 构作 s t a r t e r - a d d e r 方法 构作推广的平衡竞赛设计现在我们把已知的s t a r t e r a d d e r 方法( 例如见文 【1 6 ，3 8 ，5 6 1 ) 通过变着，用于构作我们所需要的g d r p ( k ，n ) 设k ，w 和n 为正整数，满足kin ， kl ( w + 1 ) 和叫n 七记 u = n k 设g 是阶为u 后的阿贝尔群，含有一个阶为k 的子群g o 我们固 定g o 在g 中的一个陪集代表系，记为( h o = 0 ，h 1 ，一，九u 一1 ) 写g fh i + g o ( 0 i 牡一1 ) 为g o 在g 中的陪集然后我们取一个g d r p ( k ，礼+ w ) 的点集 为x = g u o o l ，o 。2 ，。叫) 定义在点集x 上的g d r p ( k ，孢+ 叫) 的一个可迁 s t a r t e rs 是一个具有下面结构的三元集( s ，r ，c ) 1 s 由u 个k 长向量( 基区组) 马( j = 1 ，2 ，u ) 组成，其中恰有w 个基 区组包含一个取自 。，z ，o 。叫) 的无穷大点 2 r 由半一1 个g 上的k 长向量和唯一一个g 上的七一1 长向量( 基区 组) 组成，记为r 1 ，疡，兄毕 3 c 由半一1 个g 上的后长向量( 基区组) a ，q ，哗_ 组成对 于任意的j ( 1 j w 七+ l 1 ) ，7 r ( g ) = g o 此处7 r ：g _ g o 是一个满 射，满足如果有z = h i + ! ，g i ( 0 i 让一1 ) ，那么丌( z ) = y ，其中 ( h o = 0 ，h 1 一，h u 一。) 为固定的代表系 ( s ，r ，c ) 满足下面的性质： 1 sur 形成x 的一个划分； 2 s t jr uc 中基区组的差列表包含a a o 中每个元素恰好k 一1 次，不包 含g o 中的任意元素 ( s ，r ，c ) 的性质暗示了每个基区组最多包含一个无穷大点，且每个无穷 大点恰好出现在一个基区组中 与s 对应的一个a d d e r 是取自札个代表元h o = 0 ，h 1 i 一，h u 一。的一个置 换，记为a ( s ) = ( a 。，a 2 ，n u ) a ( s ) 满足重集合 ( u u i ( b i + a i ) ) u ( ( 加f 刁 第三章最优g d r p 的f g d r p 构作 s t a r t e r a d d e r 方法 恰包含某k 一1 个陪集( 不妨记为g 即g ，吼) 每一个陪集的k 一1 个 元素( 不一定不同) ，剩下的每个陪集中的k 个元素( 不一定不同) 在这里， 对任意的1 i u ，1 j w 有a i + 。o ，= 。o j 定理3 2 1 如果存在一个定义在x 上的g d r p ( k ，n + w ) 的可迁s t a r t e r ( s ，r ，c ) 和一个与s 对应的a d d e ra ，那么存在一个空缺g d r p ( k ，w ) 作为子设计 的g d r p ( k ，n + 叫) 更进一步，如果一个c d r p ( k ，w ) 存在，那么就存在一 个g d r p ( k ，n + 伽) 证明：记让= 几后我们先用s t a r t e rs 和对应的a ( s ) 构作阶为牡的方 阵硒，其行和列用玩中的元素标号对于任意的r 乙，我们把区组b 放 于位置( 一r ，0 ) 当且仅当这个基区组对应的a d d e r 是h ，由于a ( s ) 是代表 元h o = 0 ，h 1 一，k 一。的一个置换，这样的操作是可行的对于剩下的列c ( c = 1 ，2 ，t 一1 ) ，我们把b + h 。放于位置( r ，c ) ，其中b 是放置在( r c ，0 ) 的区组，这里的r c 在况中计算 接着用r 生成下w + l 让阶阵k ( r ) ，不妨设k ( r ) 的最后一行均为k 一1 长区组k ( r ) 有下面的形式： k ( r ) = r 1 + h or 1 + h ir 1 + h 一1 r 2 + h or 2 + h i r 2 + h u 一1 r 业+ o r 业+ lr 业+ h t 一1 然后用c 生成让w + 广l - k 阶阵k ( c ) 它有下面的形式： k ( c ) = c 1 + h oc 2 + h o c 竺土! = + o 量 研+ 九1q + h i c 型! = ! + 1 k a + h u 一1g - 2 + h 。1c 型! = + t 一1 接下来我们还需要用上文提到的k 一1 个陪集g g ，g 址。生成一 个t ix ( k 一1 ) 阶阵k ( p ) 它具有下面的形式： k ( p ) = g z l + og z 2 + h o g z 一1 + o g z l + 1g z 2 + lg z i l + 1 瓯1 + h t i 一1g 正2 + h - 1g z + k 一1 1 7 第三章最优g d r p 的f g d r p 构作f r a m e 型构作 最后，设g o = ( g o = 0 ，9 1 ) 一，鲰一。) 我们形成一个吐芦( 礼+ w )