（应用数学专业论文）强度为3的混合覆盖阵.pdf

强度为3 的混合覆盖阵摘要 摘要 设n ，t ，k ，g i ( i = 1 ，2 ，k ) 为正整数，其中2 t k g i 是一个大小为g 的 集合一个混合覆盖阵，m c a ( n ；t ，k ，9 1 9 2 班) ，定义为一个n k 阵列，第 列上的所有元素取自集合g ；且对任意有序序组( t 。，i 2 ，i 。) ，由列i ，i 2 ，乱 标定的子阵列n t 含g ；，g i ，g i 中每一个作为行向量的t 元序组至 少一次混合覆盖阵m c a ( n ；t ，k ，9 1 9 2 g k ) 存在的最小长度称为混合覆 盖阵数，记作m c a n ( t ，k ，g 1 9 2 鲰) 若等于m c a n ( t ，七，g 1 9 2 肌) ，则称其 为最优的当9 l = 9 2 = = 9 k 时，混合覆盖阵m c a ( n ；t ，k ，9 1 9 2 9 k ) 恰好 就是覆盖阵c a ( n ；t ，k ，9 1 ) 混合覆盖阵在软件测试、网络、电路等系统测试 中有着许多重要的应用 有关混合覆盖阵研究的基本问题之一是确定函数m c a n ( t ，k ，g x 9 2 弧) 的值当t = 3 时，有m c a n ( 3 ，k ，夕l 仍g k ) m ，其中m = m a x g i g l g , , ，1 i 歹 竹有关函数值m c a n ( t ，k ，g t 9 2 g k ) 的上界主要是通过构作相应的 混合覆盖阵得到，这是有关混合覆盖阵研究中的一个重点，也是一个难点 本文对强度为3 的混合覆盖阵展开了深入研究，利用8 - f a nm c a 、组拉长、 因子分解等递推构作方法完全确定了k = 3 ，4 时的混合覆盖阵数，基本确定 了k = 5 和k = 6 时的混合覆盖阵数当k 7 时，本文还给出了若干个达到 下界最优混合覆盖阵的无穷类 关键词：混合覆盖阵，覆盖阵，构作，存在性，最优性 作者：史册 导师：殷剑兴( 教授) m i x e dc o v e r i n ga r r a y so fs t r e n g t ht h r e ea b s t r a c t m i x e dc o v e r i n go fs t r e n g t hthreqixec o v ea r r a y ss t r e nr e e a b s t r a c t l e tn ，t ，七，9 ( i = 1 ，2 ，匙) b ep o s i t i v ei n t e g e r s ，w h e r e2 ts 匙g ii sas e t o fs i z eg i am i x e dc o v e r i n ga r r a y , m c a ( n ；t ，k ，g i 9 2 g k ) ，i sa l ln ka r r a yw i t h e n t r i e so ft h ei t hc o l u m nf r o mas e tg ；f o ra n yo r d e r e dt u p l e ( i l ，i 2 ，n ) ，t h en t s u b a r r a yi n d e x e db yc o l u m n si l ，i 2 ，i tc o n t a i n se a c ht - t u p l ef r o mg l g i 2 g i , 鹊ar o wa tl e a s to n c e t h em i n i m u ms i z enf o rw h i c ha l lm c a ( n ，t ，k ，g i 9 2 夕彪) e x i s t si sc a l l e dm i x e dc o v e r i n ga r r a yn u m b e r ，a n dw r i t t e n 鹪m c a n ( t ，七，g i 9 2 9 k ) t h ec o r r e s p o n d i n gm c ao fs i z en = m c a n ( t ，k ，g i 9 2 夕七) i sc a l l e do p t i m a l w h e n g l = 9 2 = = g k ，a nm c a ( n ，t ，七，g i 9 2 9 七) i s j u s tac a ( n ，t ，9 1 ) m i x e dc o v e r i n g a r r a y sh a v em a n yi m p o r t a n ta p p l i c a t i o n si nt h et e s t i n go fs y s t e m ss u c ha ss o f t w a r e t e s t i n g ，n e t w o r k sa n dc i r c u i t s ，a n ds oo n o n eo ft h eb a s i cp r o b l e m so nm i x e dc o v e r i n ga r r a y si st od e t e r m i n et h ev a l u e so f t h ef u n c t i o nm c a n ( t ，七，g 1 9 2 g k ) w h e nt = 3 ，w eh a v em c a n ( t ，k ，g i 9 2 g k ) m ， w h e r em = m 玑毋乳，1 i 歹 2 研究 很少，本文主要考虑t = 3 时的情形，即强度为3 的混合覆盖阵 1 2 研究问题和结果 有关混合覆盖阵研究的基本问题之一是确定整变量函数m c a n ( t ，k ，9 1 仍 鲰) 的值显然，函数m c a n ( t ，k ，g x 9 2 g k ) 有个平凡的下界，即m c a n ( t ，k ， g 1 9 2 g k ) m ，其中仇= m a x i 叫g i ，i ，l _ t ， 1 ，2 ，七) ) 对于t = 3 ，有 m e a n ( 3 ，k ，g i 9 2 g k ) 仇，其中仇= m a x g i g j g , , ，1 i 歹 3 ，则正交表o a ( 3 ，8 + 2 ，s ) 存在 横截设计和正交表是相互等价的组合研究对象，t d a ( t ，k ，口) 存在当且 仅当o a a ( t ，七，t ，) 存在从而研究正交表可以归结为对横截设计的研究，对于 横截设计的研究也可以从正交表的观点去拓展b u s h 构作只是考虑素数幂 的情形，对于非素数幂的情形，通过t - g d d 的加权构作，得到下面的结果： 定理2 3 【8 】8 设t ，= 衍1 谬妒，其中p i ( 1si r ) 两两不同，且p t ( 1 i ，) ，则存在正交表o a ( t ，k + 1 ， ) 和t d ( t ，k + 1 ，口) ，其中= m i n ( p ：1 i r ) 如果o a ( 3 ，七，g ) 存在，其就是最优的覆盖阵，从而有c a n ( 3 ，七，g ) = g a 正 交表o a ( k ，夕) ，等价于七一2 个两两正交的拉丁方，也等价于横截设计t d ( k ，g ) 【8 1 2 2 构作方法 本小节将给出若干基本和递推构作强度为3 的混合覆盖阵的方法 定理2 4假设混合覆盖阵m c a ( n ；t ，忌，g 1 9 2 鲰) 存在，设i l i 2 i ， t - ，i 2 ，谐) 1 ，2 ，”则对任意s t ，s 七，存在混合覆盖阵 m c a ( n ；s ，7 ，9 i 1 9 i 2 飒) 6 强度为3 的混合覆盖阵 二 混合覆盖阵的构作方法 证明：对任意8 t ，混合覆盖阵m c a ( n ；t ，9 1 9 2 g k ) 显然是m c a ( n ；8 ，k ， g i 9 2 g k ) ，删除集合 l ，2 ，忌 l 。，t 2 ，i f 所标定的列就得到了m c a ( n ；s ， k ，g i l 飒) 口 对给定的混合覆盖阵m c a ( n ；t ，七，g 1 9 2 鲰) ，其中g l 9 2 g k 为 了覆盖任意t 列所标定的那些集合上的所有t 元序组至少一次，则最小 应为所有分支中任意t 个分支阶乘积的最大值对t = 3 的情形，有下述引 理 弓i 理2 5设g l 9 2 鲰，贝0m o a n ( 3 ，k ，g 1 9 2 g k ) g k 一2 9 k l 鲰 证明：显然集合玩一。苏一。瓦上的三元序组个数为g k 一2 9 k l g k ，故m c a n ( 3 ，k ， 下面给出了一个最优的m c a ( 1 2 ，3 ，4 ，2 s 3 1 ) ，长度大小恰好等于其平凡的 000 01 1l00l1 1 、。 10 01 l0100101l i 1 0l0l0010110l i 0l 1010 0 22 221 最优的m c a ( 1 2 ，3 ，4 ，2 3 3 1 ) t 表示转置 坍缩是构作混合正交表的一种常用方法，在【1 1 】中，所谓坍缩即是将某 列上的m 个水平数划分为n 个两两所含元素个数相等的集合，然后用n 个 不同的元素分别去替换每个集合中的所有元素，从而将m 个水平数坍缩为 佗个水平数显然，这里的扎要求整除m ，对混合覆盖阵，由定义知所有t 元序组至少出现一次，从而在坍缩时，仅仅需要将m 个水平划分为死个集 合，并不要求n 整除m 下面引理正是这种方法的推广 弓l 理2 6 设勉g i ，l i k ，贝i jm c a n ( 3 ，七，h l h 2 h k ) m c a n ( 3 ，七，9 1 9 2 g k ) 定理2 7 若g l 9 2 g k ，且m c a n ( 3 ，k ，g i 9 2 矶) = g k 一2 9 k l g k ，对任意 1 i k 一3 有俄成立，贝0m c a n ( 3 ，七，h i h 2 h k 一3 9 k 一2 9 k l g k ) = g k - 2 9 k 一1 9 k 强度为3 的混合覆盖阵 二 混合覆盖阵的构作方法 证明： 由引理2 5 知m c a n ( 3 ，k ，h l h 2 k 一3 9 k 一2 9 k 一1 玑) g k 一2 9 k 一1 9 k 由引理 2 6 得m c a n ( 3 ，k ， l h 2 h k a g 一2 9 k 一1 玑) m c a n ( 3 ，七，g 1 9 2 g k 一2 9 k l g k ) = 孤一2 g k 一1 9 七古女m c a n ( 3 ，k ，h l h 2 h k - 3 9 k 一2 9 k l g k ) = g k 一2 夕七一l g k 口 做为简单的推论，有下面的结果 推论2 8 若正交表o a ( 3 ，k ，移) 存在，则对任意g i 秒，其中1 isk 一3 ，有 m c a n ( 3 ，是，g i 9 2 g k 一3 j 3 ) = u 3 类似于f 2 0 】的定理5 2 ，有下面的基本g d d 构作方法 定理2 9 如果g d d ( 3 ，k ，g 1 9 2 g k ) 的区组个数为b ，其中k = h ，h 忌，h ) ，则混合覆盖阵数m c a n ( 3 ，k ，g i 9 2 g k ) b 下面定理是【2 6 】中并置方法的变着 定理2 1 0 若混合覆盖阵m c a ( n 1 ，3 ，k + l ，u 9 1 9 2 鲰) 和m c a ( n 2 ，3 ，k + l ，v 9 1 9 2 鲰) 均存在，则胍4 ( l + 2 ，3 ，k + l ，( t + t j ) 9 1 9 2 鲰) 也存在，进而有m e a n ( 3 ， 七+ 1 ，( u + v ) g 1 9 2 g k ) m c a n ( 3 ，克+ l ，u g l 9 2 g k ) + m c a n ( 3 ，奄+ l ，v g l 9 2 9 k ) 定理2 1 1 若混合覆盖阵m c a ( n ；3 ，g 1 9 2 弧) 和m c a ( m ；3 ，”i v 2 v k ) 均 存在，贝m e a n ( 3 ，七，( g l 口1 ) 0 2 v 2 ) ( 珊喙) ) m n 推论2 1 2 若混合覆盖阵m c a ( n ；3 ，七，9 1 9 2 g k ) 存在，则对任意正整数序列 8 1 ，s 2 ，s 七，有m c a n ( 3 ，七，( s 1 9 1 ) ( s 2 仍) ( 5 七班) ) 8 1 s 2 s 七 证明：显然长度为m = 8 1 8 2 s b 的混合覆盖阵m c a ( m ；，七 s l s 2 s 七) 存 在由引理2 4 得到m c a ( m ；3 ，惫，s l s 2 s 知) 由题设，m c a ( n ；3 ，七，9 1 9 2 鲰) 存在，应用定理2 1 1 得m c a n ( 3 ，尼，( s 1 9 1 ) ( s 2 9 2 ) ( s 七班) ) m n = 8 1 8 2 s 七 凸 8 强度为3 的混合覆盖阵 二 混合覆盖阵的构作方法 下面的定理是对已知的混合覆盖阵增加列数比较有效的方法 定理2 1 3设9 l 9 2 9 k 对某个i ( 1 i 忌) ，9 i = t x t 2 如 则m c a n ( 3 ，k l + s ，9 1 9 2 9 i l t l t 2 t 8 9 1 + l g k ) m c a n ( 3 ，七，9 1 9 2 9 i 一1 9 i 9 i + l 9 七) 此外，若i 七一3 且m e a n ( 3 ，七，9 1 9 2 9 i 一1 9 i 9 i + 1 9 k ) = 9 k 一2 9 k l 夕七， 则导出的混合覆盖阵m c a ( 3 ，七一1 + s ，9 1 9 2 g i l t l 2 t s y i + l 9 k ) 也是最优 的 证明：记混合覆盖阵m c a ( 3 ，七，9 1 9 2 g i 一1 9 i g i + 1 鲰) 为m 由题设g i = t l t 2 t 。，知存在一个双射玩叫五l 况z t , ，n 叫( a l ，a 2 ，) 用( a 。，a ：，a 。) 去替代m 的第i 列上的相应的a ，继续这个过程，则从m 得 到了一个n ( 七一1 + s ) 阵列，用表示剩下的就是验证矩阵竹7 就是所 求的混合覆盖阵 为了证明这个断言，只需要证明任意3 元序组( z ，y ，z ) 在由i l ，i 。，i 。列标 定的子阵列m ，3 中出现至少一次，其中z ，可，z 各自跑遍列i x , i 2 ，i 3 所对应 的集合，1 i l i 2 i 3 七一1 + 8 情形1 ：假设i l , i 2 ，i s 譬 i ，i + 1 ，i + s 一1 在这种情形下，列i l ，i 2 , i 3 同 时也是m 所对应的列从而3 元序组( z ，y ，z ) 在这三列中出现至少一次 情形2 ：假设i l ，i 2 ，i 3 中的两个不属于集合 i ，i + 1 ，i + s 一1 ) 不失一般 性，设i l i ，i + 1 ，i + s - 1 ) ，i 2 ，i s 1 ，2 ，3 ，七一l + s ) i ，i + 1 ，i + s - 1 ) 考虑任意3 元序组( z ，y ，名) 由上面所定义的双射知，至少存在一个元素口， 口z g , - - - - - - - 4 ( 口l ，o a ，) 邑，z t 2 况使得z = 口m 因为m 是混合 覆盖阵，则( 口，y ，z ) 在m 中出现至少一次确保了( z ，y ，z ) 出现至少一次 情形3 ：假设i 1 ，t 2 ，i 3 中的一个不属于集合 i ，t + 1 ，i + s 一1 ) 不失一般 性，设i l ，i 2 t ，i + 1 ，i + 8 - 1 ) ，i 3 1 ，2 ，3 ，k - 1 + 8 i ，i + 1 ，i + s 1 ) 考 虑任意3 元序组( z ，耖，z ) 由上面所定义的双射，至少存在一个元素口，a 玩 一( a l ，a 2 ，a | ) 邑l 五2 乙使得z = a i 。一i + l 和y = a i 2 一i + 1 对任意 z z g i 3 ，( 吼z ) 在 z 的i s 和i 列中至少出现一次故( 茁，y ，名) 在m 7 的i l ，i 2 ，i 3 q 强度为3 的混合覆盖阵 二 混合覆盖阵的构作方法 列中至少出现一次 情形4 ：假设t 1 ，i 2 ，i 3 0 ，i + l ，i + s l 显然，由前面所定义的双 射，( z ，y ，z ) 瓦，磊，在 f 的i l ，i 2 ，i s 列中出现至少一次 综上所有情形，就证明了定理的第一个结论 由题设及第一个结论知，m c a n ( 3 ，k ，g l 仍g i lh t 2 t s g i + 1 - g k ) g k 一2 g k l g k 。若t k 一3 ，则m c a n ( 3 ，七一1 + 8 ，g i 9 2 绋一t t l 亡2 t s g i + l g k ) g k - 2 9 k l 鲰故m c a n ( 3 ，七，夕1 9 z g i l g i g i + l g k ) = g k 一2 9 k 一1 9 k ，即导出的混合覆 盖阵是最优的口 下面的定理是对已知的m c a 增加某分支的阶，即组拉长构作，同时也 是一个构作强度为3 的混合覆盖阵的有效的递推方法 定理2 1 4 设p 0 ，q 0 和1 i j k ，如果混合覆盖阵m u a ( m 1 ；3 ，k ，g i 9 2 g i i g i g i + 1 9 1 1 易毋+ 1 肌) ，m c a ( m 2 ；2 ，k - 1 ，g 1 9 2 吼一l g i + l g k ) 和m u a ( m s ； 2 ，k - 1 ，g 1 9 2 缈一l 缈+ l g k ) 存在，贝4m c a n ( 3 ，k ，g i 9 2 g i l ( 9 + p ) 夕+ 1 毋一l ( 缈+ q ) g j + 1 g k ，3 ) m 1 + p m 2 + q m 3 + p q t ，其中t = m a x g 缸i1 u 七，1 工ia n d u 歹) 证明： 设混合覆盖阵m c a ( m l ；3 ，七，g i 9 2 g i l 夕t 夕t + l 缈一1 g j g j + l g k ) 为a ， 取集合1 和协，满足i 风i = p ，1 1 t 2 l = g ，h lng i = 0 和日2n q = 仍 设混合覆盖阵m c a ( m 2 ；2 ，七一1 ，g x g z g i 一1 9 i + l g k ) 为b ，对b 的每一行 向量( a ，a ：，a i - 1 ia i + l ，a k ) ，将日。中的每个点z 加入其中得到k 元序 组( a l ，a 2 ，a i 1 z ，a i + l ，佩) ，继续这个过程，则从矩阵b 得到一个p 尥七 矩阵，用b 7 表示；类似地，由m c a ( m 3 ；2 ，庇一1 ，9 1 9 2 仍一1 彩+ 1 鲰) ，得到了 一个a m 3 k 矩阵，用表示对每一对元素( z ，y ) h i xh 2 ，构作t 个k 元 序组( a l ，a 2 ，口i - 1 ，z ，毗+ 1 i ，_ 1 箩，a l + l ，鲰) ，其中a 。取自集合g 。，且g 。 中每个元素被选取至少一次显然t = m a x g ui1 七，t ia n d 钍j ) 能 够保证这种选取对所有( z ，y ) 胁凰，继续这个过程，得到了一个p q t x 七 矩阵，用d 表示； 1 0 强度为3 的混合覆盖阵 二 混合覆盖阵的构作方法 记g iu 研= g ：，qu 飓= q 和 f = 我们断言f ，一个( 舰+ p + g 慨+ p g 丁) k 矩阵，是混合覆盖阵m c a ( n ；3 ，七， 9 1 9 2 优一l ( 9 i + p ) 9 i + 1 毋一l ( 毋+ g ) 缈+ 1 - 矶) ，其每列元素分别取自集合g 1 ， g 一1 ，g ，g i + l ，g j 一1 ，g 0 岛+ l ，g 七 为了证明这个断言，只需要证明任意3 元序组( z ，y ，名) g n g i ，g i 3 在p 的列i 1 ，i 2 ，i 3 标定的子矩阵中出现至少一次，其中1 i 1 0 ，存在一个数e o = e o ( 3 ，k ) 使得对任意u 和 任意质数幂口，对所有的e e o ，存在最优的混合覆盖阵m c a ( 3 ，七，( v q 。) ( q 8 ) ( u 口。) 切) 上面的结果均是由素数幂的情形得来的，对于非素数幂的情形，可以利 用算术基本定理将其分解为素数幂的乘积，从而有下面的结果 定理3 1 7设u = 衍1 p 。妒，其中p i ( 1 i ，) 两两不同，且 6 ( 1 i ，) ，则存在最优混合覆盖阵m c a ( v d e ；3 ，七+ l ，9 1 9 2 g k - 2 u 如) ，其中 g i u ( 1 i 七一2 ) ，d t ，e u 和七= m i n p ：1 i ，_ ) 1 9 强度为3 的混合覆盖阵四进一步的研究问题 四进一步的研究问题 本文完全确定了t = 3 ，k = 3 ，4 时的混合覆盖阵数，基本确定了k = 5 ，6 时的混合覆盖阵数；同时还给出了若干最优的混合覆盖阵无穷类但是对没 有解决的一些例外，还需要进行讨论和研究 问题1能否找到新的构作方法，完全确定k = 5 ，6 时的混合覆盖阵数或者 解决剩下的一些类? 如果能够完全解决这个问题，不仅会充实混合覆盖阵的构作方法，而且 会扩大实际中的应用 问题2 能否给出新的直接和递推构作，解决更加一般的混合覆盖阵数存在 性结果，即确定m c a n ( 3 ，k ，9 1 9 2 ，9 k ) 的上界和非平凡的下界? 本文给出了具有特殊结构的混合覆盖阵：s - f a nm c a 的定义，这种m c a 在构作最优的混合覆盖阵中发挥了重要作用，文中却没有讨论其存在性结 果 问题3能否从组合设计的角度去研究这种特殊结构的m c a ，解决其存在 性问题? 强度为3 的混合覆盖阵 参考文献 参考文献 1 k a b u s h ，o r t h o g o n a la r r a yo fi n d e xu n i t y , a n n m a t h s t a t 2 3 ( 1 9 5 2 ) ，4 2 6 4 3 4 【2 】m c h a t e a u n e u f , c j c o l b o u r na n dd l k r e h e r ，c o v e r i n ga r r a y so fs t r e n g t h t h r e e ，d e s c o d e sc r y p t o g r 1 6 ( 1 9 9 9 ) ，2 3 5 - 2 4 2 【3 】3 m c h a t e a u n e u fa n dd l k r e h e r ，o nt h es t a t eo fs t r e n g t h t h r e ec o v e r i n ga r r a y s ， zc o m b i n d e s 1 0 ( 2 0 0 2 ) ，2 1 7 - 2 3 8 【4 1m b c o h e n ，c j c o l b o u r na n da c h l i n g ，c o n s t r u c t i n gs t r e n g t ht h r e e c o v e t i n ga r r a y sw i t ha u g m e n t e da n n e a l i n g ，d i s c r e t em a t h 3 0 8 ( 2 0 0 8 ) ，2 7 0 9 2 7 2 2 【5 】d m c o h e n ，s r d a l a i ，m l f r e d m a na n dg c p a t t o n ，t h ea e t gs y s t e m ： a na p p r o a c ht ot e s t i n gb a s e do nc o m b i n a t o r i a ld e s i g n ，i e e et r a n s s o f t w a r ee n 9 2 3 ( 1 9 9 7 ) ，4 3 7 - 4 4 4 【6 】d m 。c o h e n ，s r d a i m ，j p a r e l i u sa n dg c p a t t o n ，t h ec o m b i n a t o r i a ld e s i g n a p p r o a c ht oa u t o m a t i ct e s tg e n e r a t i o n ，i e e es o f t w a r e 1 3 ( 5 ) ( 1 9 9 6 ) ，8 3 - 8 8 【7 】7c j c o l b o u r n ，s t r e n g t ht w oc o v e r i n ga r r a y s ：e x i s t e n c et a b l e sa n dp r o j e c t i o n ， d i s c r e t em a t h 3 0 8 ( 2 0 0 8 ) ，7 7 2 - 7 8 6 【8 】c j c o l b o u r na n dj h d i n i t z ，t h ec r ch a n d b o o ko fc o m b i n a t o r i a ld e s i g n s ， c r cp r e s s ，b o c ar a t o n ，f l ，2 0 0 7 【9 】c j c o l b o u r n ，s s m a r t i r o s y a n ，g l m u l l e n ，d e s h a s h a ，g b s h e r w o o d a n dj l y u c a s ，p r o d u c t so fm i x e dc o v e r i n ga r r a y so fs t r e n g t ht w o ，zc o m b i n d e s 1 4 ( 2 0 0 6 ) ，1 2 4 - 1 3 8 【1 0 】c j c o l b o u r n ，s s m a r t i r o s y a n ，t v t r u n ga n dr a w a l k e ri i ，r o u x - t y p e 强度为3 的混合覆盖阵参考文献 c o n s t r u c t i o n sf o rc o v e r i n ga r r a y so fs t r e n g t h st h r e ea n df o u r ，d e s c o d e sc r y p t o g r 4 1 ( 2 0 0 6 ) ，3 3 - 5 7 【1 1 】a d e ya n dr m u k e r j e e ，f r a c t i o n a lf a c t o r i a lp l a n s ，j o h nw i l e y & s o n s ，i n c ， n e wy o r k ，1 9 9 9 【1 2 】a h a r t m a na n dl r a s k i n ，p r o b l e m sa n da l g o r i t h m sf o rc o v e r i n ga r r a y s ，d i s c r e t e m a t h 2 8 4 ( 2 0 0 4 ) ，1 4 9 1 5 6 【1 3 la s h e d a y a t ，n j a s l o n ea n dj s t u f k e n ，o r t h o g o n a la r r a y s ，s p r i n g e r ，n e w y o r k ，1 9 9 9 【1 4 】l j ia n dj y i n ，c o n s t r u c t i o n so fn e wo r t h o g o n a la r r a y sa n dc o v e r i n ga r r a y so f s t r e n g t ht h r e e ，p r e p r i n t 【1 5 】j k s r n e ra n dm l u c e r t i n i ，c o m p r e s s i n gi n c o n s i s t e n td a t a ，i e e et r a n s i n f o r - m a r i o nt h e o r y4 0 ( 1 9 9 4 ) ，7 0 6 - 7 1 5 【1 6 】y l i ，l j ia n dj y i n ，c o v e t i n ga r r a y so fs t r e n g t h3a n d4f r o mh o l e yd i f f e r e n c e m a t r i c e s ，d e s c o d e sc r y p t o g r 5 0 ( 2 0 0 9 ) ，3 3 9 - 3 5 0 【1 7 】s m a r t i r o s y a na n dt v d u n g ，o nt - c o v e r i n ga r r a y s ，d e s c o d e s c r y p t o g r 3 2 ( 2 0 0 4 ) ，3 2 3 - 3 3 9 【1 8 】k m e a g h e r ，l m o u r aa n dl z e k a o u i ，m i x e dc o v e r i n ga r r a y so ng r a p h s ，z c o m b i n d e s 1 5 ( 2 0 0 7 ) ，3 9 3 - 4 0 4 【1 9 】k m e a g h e ra n db s t e v e n s ，g r o u pc o n s t r u t i o no fc o v e r i n ga r r a y s ，zc o m b m d e s 1 3 ( 2 0 0 5 ) ，7 0 - 7 7 【2 0 】l m o u r a ，j s t a r d o m ，b s t e v e n sa n da w i l l i a m s ，c o v e r i n ga r r a y sw i t hm i x e d a l p h a b e ts i z e s ，zc o m b i n d e s 11 ( 2 0 0 3 ) ，4 1 3 - 4 3 2 【2 1 】k j n u r m e l a ，u p p e rb o u n d sf o rc o v e r i n ga r r a y sb yt a b us e a r c h ，d i s c a p p l m a t h 1 3 8 ( 2 0 0 4 ) ，1 4 3 - 1 5 2 2 2 强度为3 的混合覆盖阵参考文献 【2 2 】g b s h e r w o o