（应用数学专业论文）强度为4至8的覆盖阵列的构造.pdf

t ，”l、i 苏州大学学位论文使用授权声明 i i rflliiiiiiiiiiij y 17 316 2 9 。 本人完全了解苏州大学关于收集、保存和使用学位论文的规定， 即：学位论文著作权归属苏州大学。本学位论文电子文档的内容和纸 质论文的内容相一致。苏州大学有权向国家图书馆、中国社科院文献 信息情报中心、中国科学技术信息研究所( 含万方数据电子出版社) 、 中国学术期刊( 光盘版) 电子杂志社送交本学位论文的复印件和电子 文档，允许论文被查阅和借阅，可以采用影印、缩印或其他复制手段 保存和汇编学位论文，可以将学位论文的全部或部分内容编入有关数 据库进行检索。 涉密论文口 本学位论文属 在年一月解密后适用本规定。 非涉密论文豳 论文作者签名：皇酗 导师签名：壅查i 塑 日期： 趔! = 啦墨二 强度为4 至8 的覆盖阵列的构造 摘要 摘要 令x 是一个口元集，a 为x 上的n k 阵列若a 满足：对a 的任 意一个n t 子阵列均包含x 的所有t 一元组至少一次，则称a 为x 上的 覆盖阵列，记作c a ( n ；t ，k ，钉) 其中t 称为阵列a 的强度，k 称为因子数，钐 是每个因子的代表元的个数若将至少”改为”恰好”，则称a 为正交阵 列对给定的t ，k ，口，使得覆盖阵列c a ( t ，k ，移) 存在的最小行数称为覆盖阵列 数，记作c a n ( t ，k ，口) 覆盖阵列在实验设计中有许多应用，例如软件测试、数据压缩和药物筛 选等当t = 2 时，覆盖阵列数的上界尤其是正交阵列已经被广泛研究相 比之下，t 3 的覆盖阵列数的研究结果较少，现在越来越受到了关注 本文利用差覆盖阵列构作覆盖阵列的方法，通过对差覆盖阵列添加一 些特殊的性质构作了强度为4 至8 的覆盖阵列，同时也给出了一些满足特殊 性质的差覆盖阵列的理论构作另外，通过直接构作，构作了一些满足特殊 性质的差覆盖阵列，利用由差覆盖阵列到强度为4 至8 的覆盖阵列的构作可 以大大改进相应参数的覆盖阵列数的上界文章最后，通过对带洞差矩阵添 加必要的性质，获得了由带洞差矩阵到t = 4 的覆盖阵列的构作 关键词；覆盖阵列；差覆盖阵列；带洞差矩阵 作者；许凤娟 指导教师：季利均 a b s t r a c t c o n s t r u c t i o n so fc o v e r i n ga r r a y sw i t hs t r e n g t hf r o mf o u r t oe i g h t _ 一一 c o n s t r u c t i o n so fc o v e r i n ga r r a y sw i t h s t r e n g t hf r o mf o u rt oe i g h t a b s t r a c t ac o v e r i n ga r r a yc a ( n ；t ，k ，口) i sa nn ka r r a yw i t he n t r i e sf r o m as e t 叉o fu s 、r h l b o l ss u c ht h a te v e r ynx ts u b - a r r a yc o n t a i n sa l lt - t u p l e so v e rx a tl e a s to n c e t h e n 亡i 8t h es t r e n g t ho ft h ec o v e r a g eo fi n t e r a c t i o n s ，ki st h en u m b e ro fc o m p o n e n t s , a n d 口 i st h e 肌n l b e ro fs y m b o l sf o re a c hc o m p o n e n t w h e n a tl e a s t i sr e p l a c e db y e x a c t l y t h i 8 出舭a no r t h o g o n a la r r a y t h ei n i n i m u i ns i z en f o rw h i c hac a ( n ；t ，k ，秽) e 】d s t s i sc a l l e dt h ec o v e r i n ga r r a yn u m b e ra n dw r i t t e na sc a n ( t ，凫，御) c o v e r i n ga r r a y sh a v ea n u m b e ro fa p p l i c a t i o n si ne x p e r i m e n t a ld e s i g n , f o re x a m p l e i ns o 矗删et e s t i n g ，i nd a t ac o m p r e s s i n ga n di nd r u gs c r e e n i n g c o v e r i n ga r r a y sf o r s t r e n g t ht ：2 i np a r t i c u l a ro r t h o g o n a la r r a y s ，h a v e b e e ne x t e n s i v e l ys t u d i e d h o w e v e r ， v e r yl i t t l ei sk n o w na b o u tc o v e r i n ga r r a y sf o rs t r e n g t ht 3 i nt h i sp a p e r ，w ep r e s e n ts o m ec o n s t r u c t i o n so fc o v e r i n ga r r a y so fs t r e n g t h sf r o m f o u rt oe i g h tv i ad i f f e r e n c ec o v e r i n ga r r a y sw i t hp r e s c r i b e dp r o p e r t i e s s o m ed i f f e r e n c e c o v e r i n ga r r a y so ft h e o r e t i c a lc o n s t r u c t i o n sa n dd i r e c tc o n s t r u c t i o n sa r ep r e s e n t e da s w e l li nt h i sp a p e r o u rc o n s t r u c t i o n so fc o v e r i n ga r r a y si m p r o v e dt h eu p p e rb o u n d s o f i i n ec o v e r i n ga r r a yn u m b e r ss i g n i f i c a n t l y a tl a s t ，w ep r e s e n tac o n s t r u c t i o no f c o v e r i n ga r r a y so fs t r e n g t hf o u r v i ah o l e yd i f f e r e n c em a t r i c e sw i t hp r e s c r i b e dp r o p e r t i e s k e y w o r d s ：c o v e r i n ga r r a y , d i f f e r e n c ec o v e r i n ga r r a y , h o l e y d i f f e r e n c em a t r i x i i w r i t t e nb yx uf e n g j u a n s u p e r v i s e db yj il i j u n 目录 一引言1 1 1 研究背景1 1 2 主要结果2 二由d c a ( 4 ，佗； ) 到c a ( n v 纠；t ，亡+ 2 ， ) 的构作4 三由d c a ( 4 ，n ；v ) 到c a ( n v t 一1 ；t ，t + 3 ，口) 的构作9 四由h d m 到c a ( 4 ，7 ， ) 的构作1 6 参考文献。2 3 致谢_ 2 6 ，r ， 强度为4 至8 的覆盖阵列的构造一引言 1 1 研究背景 引言 令x 是一个u 元集，4 为x 上的n xk 阵列若a 满足：对a 的任 意一个n t 子阵列均包含x 的所有t 一元组至少一次，则称a 为x 上的 覆盖阵列，记作c a ( n ；t ，k ，秽) 其中t 称为阵列a 的强度，k 称为因子数，口 是每个因子的代表元的个数若将至少”改为”恰好”，则称a 为正交阵 列，记作o a ( n ；t ，k ，u ) 或者o a ( t ，k ，移) 对给定的t ，k ，u ，使得覆盖阵列c a ( t ，k ，口) 存在的最小行数称为覆盖阵列 数，记作c a n ( t ，k ，钉) 易知c a n ( t ，k ，口) 可知 覆盖阵列在实验设计中有许多应用【3 2 】，例如软件测试f 6 ，7 ，1 5 】和药物 筛选【3 4 】在这些应用中，最主要的是t 个参数的所有组合的相互作用都要 进行测试，所以所有这些选择都要被阵列的列覆盖到因为最优的覆盖阵列 可以大大降低实验设计的成本，所以对覆盖阵列的研究越来越受到关注和 重视 对覆盖阵列的最早的研究隐含在m a r c z e w s k i 的文章【2 3 】中它也曾经作 为其它等价对象被深入研究，例如t 一满射阵列【2 1 1 、集合的性质不同的t 独立划分【2 9 】、横截覆盖【3 3 】等 现在，对覆盖阵列的研究主要有两个方面：一方面是覆盖阵列的渐近存 在性，另一方面是对给定的t ，k ，u ，使尽可能地小，或者等价地，对给定的 t ，u ，n ，使k 尽可能地大 对覆盖阵列的渐近存在性的研究，g o d b o l e ，s k i p p e r 和s u n l e y 1 4 】通过在 u 元集上随机选择阵列发现：对给定的t ，k ，u ，当足够大时，这个随机选择 一引吉 强度为4 至8 的覆盖阵列的构造 的阵列是c a ( n ；t ，k ，钉) 的概率非零他们得到了结论：c a n ( t ，尼， ) 掣( 1 + d ( 1 ) ) 在文章【2 ，2 6 ，2 7 】中，有c a n ( t ，k ，2 ) 2 t t o ( 1 0 9 们l o gk 文献【1 3 】证明了结 论：丝等等的渐近值是；仇 对覆盖阵列界的研究，到目前为止已有多种方法用来改进覆盖阵列数 的上界例如将研究正交阵列的方法推广来研究覆盖阵列【17 】，积构作 9 】， r o u x 一型构作 5 ，1 0 ，群构作【2 5 】，利用置换向量构作【3 1 】，利用算法构作【8 ，1 6 1 等等 对于t = 2 ，覆盖阵列数的上界的研究尤其是正交阵列的研究比较广泛 例如：l 毪n y i 3 0 】确定了当k 是偶数，t = 口= 2 时的覆盖阵列数当t = 移= 2 时，对所有的k ，文章 2 0 】和【2 1 】的作者们各自独立地确定了其覆盖阵列数 关于正交阵列的丰富结果可参阅文献【1 】对于强度t = 2 的覆盖阵列数的上 界的研究还可以参见文献f 1 1 ，1 3 ，3 3 】相比之下，t 3 的覆盖阵列数的研究 结果较少，现在越来越受到了关注对于强度t = 3 的情形的一些结果可以 在文章 4 ，5 ，1 0 ，1 8 ，2 2 ，3 2 】中找到对于强度t 3 的情形的结果可以参见文 章 1 0 ，1 9 ，2 2 ，2 4 】最近，文献【1 8 ，1 9 ，2 2 】中利用特殊的差覆盖阵列构作了一 些强度为3 ，4 的覆盖阵列本文将进一步推广这个方法，获得新的覆盖阵 列的组合构作 1 2 主要结果 本文主要通过对差覆盖阵列添加特殊性质来构作强度为4 至8 的覆盖 阵列 设g 为u 阶交换群，d = ( 奶) ( 1 i k ，1 j 佗) 是g 上的k n 阵列，若d 的任意不同的两行f 和h ( 1 2 h 冬k ) 满足。差序列m = 【奶一：1 歹n ) 包含g 的每个元素至少一次，则称d 为g 上的差覆盖 阵列( d i f f e r e n c ec o v e r i n ga x r a y ) ，记作d c a ( k ，竹；t ，) 本文推广文献【1 8 ，1 9 ，2 2 】中的构作方法，通过对差覆盖阵列添加特殊性 2 强度为4 至8 的覆盖阵列的构造一引言 质，得到了由差覆盖阵列到强度为4 至8 的覆盖阵列的构作同时我们也给 出了一些满足特殊性质的差覆盖阵列的理论构作，从而得到了以下结果： 推论2 1 设 3 为奇数，则c a n ( t ，t + 2 ，u ) ( 2 v 一1 ) 口，t 6 ，7 ，8 ) 推论3 1 设u 为奇数，则c a ( t ，t + 3 ，u ) ( 2 v 一1 ) v 扣1 ，t 4 ，5 ) 推论3 2 设u 为偶数，则c a ( t ，t + 3 ，口) 2 v ，t 4 ，5 ) 另外，我们也通过直接构作，构作了一些满足特殊性质的差覆盖阵列， 其列数大大小于理论构作的差覆盖阵列列数于是，利用由差覆盖阵列到 强度为4 至8 的覆盖阵列的构作可以大大改进相应参数的覆盖阵列数的上 界这些改进的上界也已在c o l b o u r n 覆盖阵列表中列出【1 2 】 在文章最后，通过对带洞差矩阵添加必要的性质，获得了由带洞差矩阵 到亡= 4 的覆盖阵列的构作，从而有以下结论： 定理4 1 若存在c a ( b ；4 ，7 ，伽) 和满足所需性质的( 4 ，钐；伽) h d m ，则c a n ( 4 ，7 ，口) 4 一, 0 3 w + 6 ( 老) 3 3 二 由d c a ( 4 ，铊；t j ) 到c a ( n v 。一1 ；t ，t + 2 ，口) 的构作 强度为4 至8 自寺覆盖阵列的构造 二 由d c a ( 4 ，佗；u ) 到c a ( n v “；亡，t + 2 ，v ) 的构作 这一章，我们将利用给定性质的d c a ( 4 ，佗； ) 构作强度为t ( 6 ，7 ，8 ) 的 c a ( n v “；t ，t + 2 ，”) 首先我们给出以下的定义 设d = ( 奶) 为群g 上的d c a ( 4 ，n ；t ，) ，定义1 8 个差序列如下： 丕1 = d l j + 一奶一嘞：1 歹亿 ； 2 = d 巧+ 一d l 歹一d 彰：1 js 扎) ； a 3 = d 3 j + d 幻一d 1 ，一d 易：1 歹n ) ； a 4 = d a j + 屯一2 d 1 j ：1 歹礼】； 5 = d 4 j + 嘞一2 d 1 j ：1 j 礼) ； 6 = ( d a j + 2 d 2 j 一2 d l j d a j ：1 歹扎 ； a 7 = d 4 j + 2 奶一2 d l j 一奶：1 j 佗) ； 态8 = 【如+ d 1 j 一2 d 2 j ：1 歹礼 ； 9 = 屯+ d z j 一2 d 2 j ：1 j n ) ； a l o = d 4 j 十2 d 1 j 一2 d 易一奶：1 j 佗 ； 1 l = d 句+ 2 d z j 一2 d 2 , ，一d u ：1 歹佗) - ； a 1 2 = d 4 j + 3 d 3 j 一2 d 2 j 一2 d l j ：1 j n ) a 1 3 = d 4 j + d 巧一2 d z j ：1 j n 】； 态1 4 = d 4 j + d 1 j 一2 d 3 ，：1 歹佗) ； 1 5 = d 4 j + 2 d 2 j 一2 d 劭一d l j ：1 歹佗 ； 1 6 = d 易+ 2 d a j 一2 嘞一锄：1 歹佗】； a 1 7 = d 句+ 3 d 巧一2 d 1 j 一2 d 却：1 j n ) 1 8 = d 句+ 3 d l j 一2 d 易一2 奶：1 j n ) 如果差序列_ 1 包含g 中每个元素至少一次，则将这样的d c a ( 4 ，礼； ) 记为 d c a + ( 4 ，礼；u ) 如果前三个差序列满足每个差序列都包含g 中每个元素至少 一次，则在【1 9 】中这样的d c a ( 4 ，n ；v ) 记为d c a ( 4 ，扎；移) 如果前七个差序列 满足每个差序列包含g 中每个元素至少一次，则将这个性质记为( p 1 ) 如果 前十二个差序列满足每个差序列包含g 中每个元素至少一次，则将这个性 质记为( p 2 ) 如果上述十八个差序列满足每个差序列包含g 中每个元素至 少一次，则将这个性质记为( p 3 ) 引理2 士设 3 为奇数，则在磊上存在具有性质( p 3 ) 的d c a ( 4 ，2 v 一1 ；口) 4 强度为4 至8 的覆盖阵列的构造 二 由d c a ( 4 ，竹；u ) 到c a ( n v 。一1 ；t ，t + 2 ，钞) 的构作 证明：设b 1 是一个4xu 阵列，它的列向量是( o ，i ，2 i ，o ) t ，i 磊，b 2 是一个 4x ( u 一1 ) 阵列，它的列向量是( o ，0 ，0 ，i ) r ，i 磊 o ) 令a = ( b 1 ，b 2 ) 易证 a 是玩上具有性质( p 3 ) 的d c a ( 4 ，2 v 一1 ；u ) 口 定理2 1 设u 为奇数，如果存在具有性质( p 1 ) 的d c a ( 4 ，n ；钐) ，则c a n ( 6 ，8 ，t ，) n 5 证明；设d = ( 奶) 为群g 上具有性质( p 1 ) 的d c a ( 4 ，佗；口) 只需要在群g 上 构造c a ( n v 5 ；6 ，8 ，口) 即可 对d c a 的每一列( d - 歹，奶，嘞，奶) r ，构造如下这些行： c ( j ，u ，e ， 9 ，w ) = ( d l j + u + e + w ，奶+ t 正+ ，嘞+ 让+ 9 ，d 0 + 钍+ e + ，+ 9 + 2 叫，e ，g ，叫) ， 其中钆，e ，正g ，w g 下面验证由上述佗u s 行构成的矩阵m 是群g 上的c a ( 6 ，8 ，u ) 任取m 的 y 1 ，y 2 ，y s ，y a ，y 5 ，y 6 列，其中1 y l y 2 y a y 4 蜘 y 6 8 只需证明由m 的这六列构成的n 6 子阵列覆盖任意6 一元组b = ( z 2 ，z 4 ，z 5 ，z 6 ) 至少 一次 假设蜘= 8 对1 i 5 ，如果鼽= 1 ，则令z ：= 兢一z 6 ，如果y i = 4 ， 则令= 兢一2 x 6 ，否则令= 兢由 1 9 】的定理2 2 证明可以知道，删 除最后一列之后，c ( j ，u ，e ，9 ，0 ) 的所有列形成c a ( n v 4 ；5 ，7 ，口) 因此，在由 y 1 ，2 ，y 3 ，y a ，y 5 列构成的n 5 子阵列中至少有一行c ( j 7 ，u 7 ，e 7 ，7 ，9 7 ，0 ) 包含5 一 元组( z 0 ，。：，兢) 由此可知，在由m 的y t , 沈，可3 ，可4 ，可5 ，y 6 构成的nx6 子 阵列中b 出现在c 0 7 ，u 7 ，e 7 ，7 ，9 7 ，z 6 ) 行 假设( ! ，1 ，抛，y 3 ，玑，蜘，y 6 ) = ( 1 ，2 ，3 ，4 ，5 ，6 ) 因为差序列_ 6 包含g 中每个元 素至少一次，所以存在整数j 厶= 1 ，2 ，他) ，使得4 - 2 奶一2 d u 一奶= x 4 一x 5 一x 6 + 2 ( x 2 一x 6 ) 二2 ( x l x 5 ) 一x 3 从而在由m 的y l ，y 2 ，协，y 4 ，y 5 ，姚列构 5 二 由d c a ( 4 ，佗；钉) 到c a ( n v 一1 ；亡，t + 2 ， ) 的构作 强度为4 至8 的覆盖阵列的构造 成的n 6 子阵列中b 出现在c o ，x 2 一x 6 - - 奶，x 5 ，z 6 ，x 3 + z 6 + 奶一奶一z 2 ，z 1 + x 6 + 奶一x 5 一d l j x 2 ) 行 假设( y l ，y 2 ，y s ，y 4 ，y 5 ，y 6 ) = ( 1 ，2 ，3 ，4 ，5 ，7 ) 因为差序列压包含g 中每个元 素至少一次，所以存在整数j 厶，使得+ 2 d 3 j 一2 d l j d v = x 4 + 铂+ 2 x 3 2 x l z 2 3 x 6 从而在由m 的y l ，珈，y s ，y 4 ，y s ，蜘列构成的n 6 子阵列中b 出 现在c ( j ，x 3 一x 6 一嘞，x 5 ，x 2 一x 3 + 一奶+ 嘞，z 6 ，2 7 1 一x 5 一屯一x 3 + 如+ 2 6 ) 行 假设( y l ，y 2 ，y 3 ，y 4 ，y 5 ，珈) = ( 1 ，2 ，3 ，4 ，6 ，7 ) 因为d 是一个差覆盖阵列，所 以存在整数歹厶，使得翰一奶= x 2 一x 5 一( z 3 一x 6 ) 从而在由m 的 y ly 2 ，蜘，y 4 ，y 5 ，y 8 列构成的nx6 子阵列中b 出现在c ( 歹，z 2 一z 5 一奶，2 x 1 2 d z j + 2 x 5 一x 2 一x 4 + 2 7 6 + 奶+ ，x 5 ，x 6 ，x 4 一x 5 一x 6 一如一x l + d l j ) 行 类似地，可以验证其他情形d 定理2 2 设t ，为奇数，如果存在具有性质( p 2 ) 的d c a ( 4 ，佗；u ) ，则似( 7 ，9 ，u ) t , u 6 证明：设d = ( 奶) 为群g 上具有性质( 尸2 ) 的d c a ( 4 ，礼；口) 只需要在群g 上 构造c a ( n v 6 ；7 ，9 ，u ) 即可 对d c a 的每一列( d t ，奶，电，) t ，构造如下这些行t c ( j ，乱，e ，g ，叫，九) = ( d l j + u + e + w ，奶+ t 十，+ ，d s j + t + g ，d 4 j 十牡+ e + ，+ 9 + 2 叫+ 2 ，l ，e ， g ，叫，危) ， 其中让，e ，g ，w ，h g 下面验证由上述删6 行构成的矩阵m 是群g 上的c a ( 7 ，9 ，钉) 任取m 的y 1 ，y 2 ，y s ，纵，蜘，y 6 ，掣7 列，其中1s 暑f l 沈 驰 y 4 铂 y 6 狮 9 只需证明由m 的这七列构成的n 7 子阵列覆盖任意7 一元组b = ( z l ，z 3 ，z 4 ，z 5 ，z 6 ，z 7 ) 至少一次 假设y r = 9 对1 i 6 ，如果y i = 2 ，则令= 戤一z 7 ，如果瓠= 4 ，则令 茹：= 筑一2 x 7 ，否则令= 由定理2 1 的证明可以知道，删除掉最后一列之 6 强度为4 至8 的覆盖阵列的构造 二 由d c a ( 4 ，佗；钞) 到c a ( n v 。一1 ；t ，t + 2 ，移) 的构作 后，c g ，t ，e ，g ，伽，0 ) 的所有列形成c a ( n v 5 ；6 ，8 ，秽) 因此，在由秒l ，y 2 ，y 3 ，y 4 ，蜘，珈 列构成的n 6 子阵列中至少有一行c 9 7 ，牡7 ，e ，f t9 7 ，w 7 ，0 ) 的元素是6 一元组 ( 吐，。：，呓，硝，z ；，z 3 ) 由此可知，在由m 的y l ，y 2 ，y a ，驰，蜘，舶，y 7 列构成的n 7 子阵列中b 出现在c ( 歹，让，e ，7 ，9 7 ，w ，z 7 ) 行类似地，可以证明当y 7 = 8 时， 在由m 的3 1 ，y 2 ，y a ，驰，y 5 ，y 6 ，y 7 列构成的n 7 子阵列中至少有一行元素是b 假设y 7 = 7 因为差序列五。2 包含g 中每个元素至少一次，所以存在整 数j 厶，使得如+ 3 如一2 d 2 j 一2 d u = x 4 + z 5 + 一4 x 7 + 3 x 3 2 x 1 2 x 2 从 而在由m 的y l ，y 2 ，y a ，y a ，y 5 ，y 6 ，y 7 列构成的n 7 子阵列中b 出现在c g ，。3 一 z 7 一屯，x 5 ，铂，。7 ，x l x 5 一d u 一勖+ x 7 + 奶，x 2 一z 6 一奶一z 3 + x 7 + 嘞) 行 因此，m 是群g 上的c a ( n v 6 ；7 ，9 ，口) o 定理2 3 设u 为奇数，如果存在具有性质( 尸3 ) 的d c a ( 4 ，佗；u ) ，则c a n ( 8 ，1 0 ，u ) 佗钞7 证明：设d = ( 奶) 为群g 上具有性质( p 3 ) 的d c a ( 4 ，住；u ) 只需要在群g 上 构造c a ( n v 7 ；8 ，1 0 ， ) 即可 对d c a 的每一列( 屯，奶，如，) 丁，构造如下这些行： c g ，u ，e ，9 ，伽， ，r ) = ( d l j + t 正+ e + 伽，d 2 j + t + ，+ h ，d 妨+ t + g + r + u + e + ，+ g + 2 w + 2 h + 2 r ，e ，9 ，叫，九，r ) ， 其中让，e ，g ，w ，h ，r g 下面验证由上述佗t ，7 行构成的矩阵m 是群g 上的c a ( 8 ，1 0 ，钳) 任取m 的y 1 ，y 2 ，y a ，y 4 ，y 5 ，y 8 ，y 7 ，y s 列，其中1 y 1 y 2 y s 弧 y 5 珈 y 7 引理2 2 存在具有性质( p 1 ) 的d c a ( 4 ，8 ；5 ) 证明：在群磊上得到所需要的d c a ( 4 ，8 ；5 ) 如下： 0000 0000 、 a = i 吕吕呈呈3 1 呈主4 2l 02 414 3 34 凸 利用定理2 1 和引理2 2 ，可以得到c a n ( 6 ，8 ，5 ) 2 5 0 0 0 ，这比 2 8 】中给出 的c a n ( 6 ，8 ，5 ) 2 7 7 1 7 要低 8 强度为4 至8 的覆盖阵列的构造 三 由d c a ( 4 ，他；口) 到c a ( n v 。一1 ；t ，t + 3 ， ) 的构作 三由d c a ( 4 ，n ；v ) 到c a ( n v “；亡，t + 3 ，v ) 的构作 这一章，我们将利用给定性质的d c a ( 4 ，n ；t ，) 构作强度为t 4 ，5 ) 的 c a ( n v t 。；亡，t + 3 ，口) 首先我们给出下述相关定义 令d = ( 奶) 为交换群g 上的d c a ( 4 ，n ； ) 如果群g 上的伽元组s = ( s 。，8 2 ，s n ) 满足下列性质：( 1 ) 在多重集 s ，8 2 ，s n ) 中群g 中的每个元 素至少出现1 次，( 2 ) 矩阵d 8 = ( 磁f ) 是一个d c a ( 4 ，n ；u ) ，其中当i 1 ，2 ) 时 = 奶，当i 3 ，4 ) 时= 奶+ 彤那么称s 为差覆盖阵列d 的a d d e r 带有 a d d e r 性质的d c a ( 4 ，n ；钞) 可以用于构造c a ( n v 2 ；3 ，6 ，口) 【18 】定义如下9 个差序 列l 瓦= d 3 j + 奶一d 1 j 一鸡：1 j 扎) ； 2 = d a j + 奶一2 d l j ：1 歹佗 ； 3 = d a j + 如一2 4 ：1 j n ) ； a 4 = d l j + 彤一d 勿：1 歹死) ； a 5 = d 跗+ 2 彤一d 巧：1sj 佗) - ； 6 = d z j + 勺一奶：1 歹竹) ； a 7 = d a j + d 1 j 一2 d 巧+ 勘：1 j 礼) ； a s = d 句+ d l j 一2 d a j 一勺：1sj 冬礼) ； a 9 = d l j + 彤一d 町：1 歹竹 如果前六个差序列满足每个差序列包含g 中每个元素至少一次，则记这个 性质为( p p l ) 如果上述九个差序列满足每个差序列包含g 中每个元素至少 一次，则记这个性质为( p p 2 ) 引理3 1 设t ，3 为奇数，则在磊上存在具有a d d e r 性质的d c a ( 4 ，2 v 一1 ；v ) 并且该差覆盖阵列满足性质( p p 2 ) 证明：设b 1 是一个4 t ，阵列，它的列向量是( o ，i ，0 ，2 i ) r ，i 玩，玩是一个 9 三 由d c a ( 4 ，佗； ) 到c a ( n v 一1 ；t ，t + 3 ， ) 的构作 强度为4 至8 的覆盖阵列的构造 4 一1 ) 阵列，它的列向量是( 0 ，o ，i ，o ) r ，i 磊| o ) 易证a 是磊上的 d c a ( 4 ，2 v l ；秒) 取( 2 v 一1 ) 一元组8 = ( 0 ，0 ，0 ，0 ，1 ，2 ，口一1 ) 可以验证8 是a 的a d d e r ， 而且这样的阵列a 与8 满足性质( p p 2 ) 口 引理3 2 设u 2 为偶数，则在z 2 z 2 上存在具有a d d e r 性质的d c a ( 4 ，2 v ； ) 并且该差覆盖阵列满足性质( p p 2 ) 证明：设b z 是一个4 , e 阵列，它的列向量是( ( o ，o ) ，( 0 ，i ) ，( 0 ，o ) ，( 0 ，o ) ) t ，t 磊2 ，岛是一个4 u 2 阵列，它的列向量是( ( o ，o ) ，( 1 ，i ) ，( 0 ，o ) ，( 0 ，i ) ) t ，i 磊2 ， 马是一个4 勘2 阵列，它的列向量是( ( o ，o ) ，( 0 ，o ) ，( o ， ) ，( 1 ，o ) ) t ，i 磊2 ，b 4 是一个4 口2 阵列，它的列向量是( ( o ，o ) ，( 0 ，o ) ，( 1 ，t ) ，( 1 ，z ) ) t ，i 邑2 易证a 是磊上的d c a ( a ，2 v ；口) 取四个( 2 ) 一元组8 1 = ( ( 1 ，o ) ，( 1 ，1 ) ，( 1 ，v 2 一1 ) ) ，8 2 = ( ( o ，o ) ，( 0 ，o ) ) ， 8 3 = ( ( o ，o ) ，( 0 ，1 ) ，( 0 ，v 2 1 ) ) ，8 4 = ( ( 1 ，o ) ，( 1 ，o ) ) 令8 = ( 8 1l8 2i8 3is 4 ) 可以验证8 是a 的a d d e r ，而且这样的阵列a 与s 满足性质( p p 2 ) 口 定理3 1 如果存在具有a d d e r 性质并且满足性质( p p l ) 的o v a ( 4 ，n ；t j ) ，则 c a g ( 4 ，7 ，钞) 竹口3 一 证明：设d = ( 奶) 为群g 上具有a d d e r 性质且满足性质( p p l ) 的d c a ( 4 ，n ；口) 只需要在群g 上构造c a ( n v 3 ；4 ，7 ，u ) 即可 对d c a 的每一列( d l j , 奶，如，如) t ，构造如下这些行s c g ，铭，e ，) = ( d 1 j + 牡，奶+ t 正+ ，嘞+ t 正+ e + 彤，如+ 札+ e + ，+ ，e ，e + ，+ s j ，) ， 其中牡，e ，g 1 0 强度为4 至8 的覆盖阵列的构造 三 由r ) c a ( 4 ，礼； ) 到c a ( n v 一1 ；t ，t + 3 ，u ) 的构作 下面验证由上述n 3 行构成的矩阵m 是群g 上的c a ( 4 ，7 ， ) 任取m 的 y 1 ，1 2 ，珧，y 4 列，其中1 玑 耽 y a 驭7 只需证明由m 的这四列构成的 nx4 子阵列覆盖任意4 一元组b = ( z 。，z 2 ，z 3 ，x 4 ) 至少一次 假设驰= 7 对1 i 3 ，如果玑 2 ，4 ，6 ) ，则令= 戤一x 4 ；否则令 = 露由【1 8 】的定理2 2 证明可以知道，删除最后一列之后，c ( j ，钍，e ，0 ) 的 所有列形成c a ( n v ：；3 ，6 ，口) 因此，在由y 1 ，y 2 ，撕列构成的n x 3 子阵列中至少 有一行c ( j 7 ，e ，0 ) 包含3 一元组( 硝，呓，) 由此可知，在由m 的y ，y 2 ，y 3 ，讥 列构成的n 4 子阵列中b 出现在c ( j ，t 7 ，e ，。4 ) 行 假设( y l , y 2 ，y 3 ，y 4 ) = ( 1 ，2 ，3 ，4 ) 因为差序列五l 包含g 中每个元素至少一 次，所以存在整数j 厶，使得奶+ 奶一屯一= x 3 + x 2 一z ，一x 4 从而在 由m 的y 1 ，耽，珈，玑列构成的nx4 子阵列中b 出现在c ( j ，z 1 一d l j 如一如一 野一z 1 + d l j ，x 2 一奶一z 1 + d l j ) 行 假设( 可1 ，y 2 ，珈，弧) = ( 1 ，2 ，3 ，5 ) 因为眇是一个差覆盖阵列，所以存在整 数歹厶，使得嘞+ 一奶= z 3 一$ 4 一z 1 从而在由m 的y l ，y 2 ，钠，驰列构成 的n 4 子阵列中b 出现在c ( j ，z 1 一d l j ，x 4 ，x 2 一z 1 一奶+ d l j ) 行 假设( y ，y 2 ，珈，y 4 ) = ( 1 ，2 ，3 ，6 ) 因为差序列瓦包含g 中每个元素至少一 次，所以存在整数j 厶，使得如+ 奶一2 d 玎= z 3 + 。2 一z 4 2 x 1 从而在由 m 的y 1 ，沈，蜘，驰列构成的nx4 子阵列中b 出现在c ( j ，z 1 一d l j ，z 3 一z 1 一彤一 嘞+ d 1 j ，x 2 一z l 一奶+ d 巧) 行 假设( y l ，y 2 ，y a ，y 4 ) = ( 1 ，2 ，5 ，6 ) 因为差序列_ 4 包含g 中每个元素至少一 次，所以存在整数j 厶，使得屯+ 彤一奶= 。- + x 4 一z 2 一幻从而在由m 的y 1 ，沈，舶，玑列构成的n 4 子阵列中b 出现在c ( j ，z 1 一d u ，z 3 ，。4 一z 3 一劝 行 假设( y ，轨，y a ，讥) = ( 2 ，3 ，4 ，6 ) 因为差序列瓦包含g 中每个元素至少一 次，所以存在整数j 厶，使得奶+ 奶一2 奶= z 1 + z 2 + z 4 2 2 3 从而在由m 的y 1 ，伽，y 3 ，驰列构成的n 4 子阵列中b 出现在c ( j ，z 3 一x 4 一如，z 2 一z 3 + x 4 三 由d c a ( 4 ，佗；秽) 到c a ( n v 一1 ；t ，t + 3 ，u ) 的构作 强度为4 至8 的覆盖阵列的构造 一彤一奶+ ，z l 一2 7 3 + z 4 一d 巧+ d q ) 行 假设( y l , y 2 ，y s ，y 4 ) = ( 2 ，3 ，5 ，6 ) 因为差序列瓦包含g 中每个元素至少一 次，所以存在整数j 厶，使得奶+ 2 8 j 一奶= x 2 + z 4 一z 1 2 x 3 从而在由m 的 y l ，y 2 ，珈，驰列构成的n x 4 子阵列中b 出现在c ( 歹，z 2 一z 3 一一，x 3 ，x 4 - - x 3 一s j ) 行 假设( l ，y 2 ，y 3 ，弧) = ( 3 ，4 ，5 ，6 ) 因为差序列瓦包含g 中每个元素至少一 次，所以存在整数j 厶，使得如+ s i 一奶= x l + 瓤一z 2 一x 3 从而在由m 的 y l ，y 2 ，y a ，y a 列构成的n 4 子阵列中b 出现在c ( j ，x 2 - - x 4 一，z 4 一z 3 一s j ) 行 类似地，可以验证其他情形口 定理3 2 如果存在具有a d d e r 性质并且满足性质( p p 2 ) 的d c a ( 4 ，扎；口) ，则 c a n ( 5 ，8 ， ) n ”4 证明：设d = ( 奶) 为群g 上具有a d d e r 性质且满足性质( p p 2 ) 的d c a ( 4 ，他；口) 只需要在群g 上构造c a ( n v 4 ；5 ，8 ，u ) 即可 对d c a 的每一列( d t j ，如，) t ，构造如下这些行， c 0 ，t 正，e ，9 ) = ( d l j + u + g ，奶+ u + ，嘞+ u + e + 9 + 勺，奶+ + e + ，+ 彤，e + g ，e + ，+ 勺，夕) ， 其中t ，e ，g g 下面验证由上述舢4 行构成的矩阵m 是群g 上的c a ( 5 ，8 ，u ) 任取m 的y 1 ，耽，y 3 ，y 4 ，y 5 列，其中1 y 1 y 2 y 3 y 4 y 5 8 只需证明由m 的这 五列构成的n 5 子阵列覆盖任意5 一元组b = ( z 。，z 。，z 。，z 4 ，。) 至少一次 假设y 5 = 8 对1 i 4 ，如果玑【1 ，3 ，5 ) ，则令= 甄一x s ；否则令 = 因为d 具有性质( p p l ) ，所以由定理3 1 的证明可以知道，删除最后一 列之后，c ( j ，让，e ，0 ) 的所有列形成c a ( n v 3 ；4 ，7 ，t ，) 因此，在由y 1 ，抛，y a ，y 4 列 构成的n 4 子阵列中至少有一行c ( j 7 ，缸7 ，e ，7 ，0 ) 包含4 一元组( ，z ：，z ：) 12 强度为4 至8 的覆盖阵列的构造 三 由r ) c a ( 4 ，n ；口) 到c a ( n v 一1 ；亡，t + 3 ， ) 的构作 由此可知，在由m 的1 t l ，驰，1 t 3 ，弧，班列构成的nx5 子阵列中b 出现在 c ( j 7 ，u ，e ，x 5 ) 行 假设( y t ，抛，蜘，玑，蜘) = ( 1 ，2 ，3 ，4 ，5 ) 因为差序列五1 包含g 中每个元素至 少一次，所以存在整数j 厶，使得d 萄+ 奶一屯一d 4 j = z 3 + z 2 一z 1 一z 4 。从而 在由m 的秒1 ，耽，! ，3 ，y 4 ，y 5 列构成的nx5 子阵列中b 出现在c ( j ，茁3 一d 巧一8 j x 5 ，d l j 一屯一s j z l + x 3 ，z 2 一奶一( 茹3 一d 3 j 一町一z 5 ) ，z l d l j 一( z 3 一嘞一彤一x s ) ) 行 假设( y l ，耽，蜘，玑，可5 ) = ( 1 ，2 ，3 ，5 ，7 ) 因为是一个差覆盖阵列，所以存 在整数j 厶，使得+ 彤一d 2 j = x a + x 5 - - x 2 - - a 7 4 从而在由m 的可1 ，仇，y a ，y 4 ，讹 列构成的nx5 子阵列中b 出现在c ( j ，x 2 一z 5 一奶，x 4 + x 2 一写l x 5 一奶+ d l j ，2 7 5 ，z 1 一x 2 + z 5 一d l j + 奶) 行 假设( y l ，耽，蜘，弧，佻) = ( 1 ，2 ，4 ，5 ，7 ) 因为差序列一7 包含g 中每个元素至 少一次，所以存在整数j 厶，使得毗+ d 1 j 一2 锄+ s j = x l + x 3 + z 5 一x 4 2 x 2 从而在由m 的掣l ，抛，蜘，y 4 ，y 5 列构成的nx5 子阵列中b 出现在c ( j ，z 2 一奶一 d 2 j ，x 3 一z 2 + 奶一如一s j ，z 5 ，z l d x j 一( x 2 一f 1 7 5 一奶) ) 行 假设( 可1 ，管2 ，讹，弧，佻) = ( 1 ，3 ，4 ，5 ，7 ) 因为差序列瓦包含g 中每个元素至 少一次，所以存在整数j 厶，使得+ d l j 一2 d 3 j s j = x l + z 3 + x 4 一x 5 2 2 2 从而在由m 的y l ，耽，y 3 ，y 4 ，y 5 列构成的nx5 子阵列中b 出现在c ( j ，x 2 一x 4 一 d 3 j s j ，2 ：