覆盖阵列的群构造外文翻译资料

英语原文共 18 页，剩余内容已隐藏，支付完成后下载完整资料

---

覆盖阵列的群构造

Karen Meagher

摘要：本文探讨的是Chateauneuf, Colburn和Kreher研究出的强度为3的覆盖阵列的构造问题。这个构造使用的是覆盖阵列的一个子阵列和作用在这个子阵列上的一个群操作。

1. 介绍和定义

覆盖阵列是一个非常有趣和有用的设计，现已经被广泛研究。它们与正交阵列密切相关，还与有趣的数学结构有关，如集合系统和交叉代码，在软件测试和交换网络中也有许多应用。因此对这些阵列可以探讨许多有趣的问题。例如，哪些参数确实覆盖了阵列，如何找到最小阵列以及如何将这些设计有效地应用于测试系统。

本文讨论的问题是如何构造覆盖阵列。很快就会明白，这些阵列具有大量的结构性和重复性，这个属性通过用群操作来构造覆盖阵列。首先，我们需要对覆盖阵列有一个很好的理解。

定义1.(正交阵列)定义正交阵列是一个ktimes;n²阵列，其所有元素取自Z_n，使得在任何行对中，取自Z_n的任意有序对恰好出现在一列中。

此时正交阵列记为OA(k,n)。

例2.一个正交阵列OA(3,3)

固定正交阵列的大小(它是ktimes;n²)，因此通常问题是正交阵列是否存在。我们知道，对于n为一个素数幂，那么存在一个正交阵列OA(n 1,n)。

覆盖阵列是正交阵列的推广。取自Z_n的每个有序对不是恰好出现一次在一列中，而是覆盖阵列仅要求每个有序对至少出现一次在一列中。所以每一对将被一些列覆盖，因此称其为覆盖。

此外，我们可以通过引入强度的概念来扩展这些阵列。不是要求取自Z_g的每一对发生在每一对行之间，而是可以要求取自Z_g的每一t元子集出现在每一t元组的行的一些列中。由此我们这样定义了强度为t的覆盖阵列。

定义3.(覆盖阵列)用字母g来表示大小(阶数)、k因子(阶数)和大小n，这样的一个t强度覆盖阵列由长度为k的n个向量构成，其每一元素均取自Z_g。这些向量具有给定任何t个不同索引1le;i₁lt; i₂lt;hellip;lt;i_tle;k和任何有序t元组，其元素(g₁,g₂,hellip;,g_t) Z，至少存在一个向量v，使得对于所有1le;jle;t，v_ij = g_j。这等效于将阵列投影到包含所有g^t个可能性的任何t坐标上。

t强度的覆盖阵列记为t-CA(n,k,g)，它可能是非最优大小。最小覆盖阵列的大小将由这样得到：

t-CAN(k,g)= {l:存在t-CA(k,g)，其大小为l}.

称为覆盖阵列数。

首先很清楚，如果一个覆盖阵列t-CA (n,k,g)存在，则nge;g^t。此外当且仅当正交阵列OA(k,g)存在时，2-CA(g²,k,g)存在。当g是素数幂时，正交阵列OA (g 1,g)存在等价于覆盖阵列2-CA (g²,g 1,g)存在。

1. CA(n,k,2)的存在性问题是显而易见的。事实上，每个n有一个最大可能k的公式：

{k:CAN(k,2)le;n}=.

从这些稀疏结果中可以清楚地看出，关于覆盖阵列的许多问题需要研究，比如知道特定影响因素大小后覆盖阵列的存在性问题，以及对于t-CAN ( k,g)的最小值研究问题。

幸运的是，我们确实取得了许多有益的成果。首先，强度为t的覆盖阵列的许多结果可用于强度为t -1的覆盖阵列的上界，很容易看出其不等式如下:

(t-1)-CA(k-1,g)le;(t-CA(k,g)).

简单地取一个覆盖阵列t-CA(k,g)并选择行r_i和取自字母表x的字母。然后移除行r_i并仅保留阵列中在行i中具有x的列。由此生成正确大小的(t-1)-CA(k-1,g)。

本文的重点是探索一些有趣的强度为3的覆盖阵列的新构造，并试图将这些方法推广到强度为2的覆盖阵列。

2.强度为3的覆盖阵列的构造

本文的研究重点是Chateauneuf, Colburn和Kreher共同探讨出的构造设计。这种构造使用覆盖阵列的结构和覆盖阵列中的重复性，其思想是从一个小阵列、“一个starter阵列”和一个群来构造一个覆盖数组，这种构造通过考虑作用在起始数组列上的群逐列构造覆盖阵列。在某些情况下，将附加小阵列以完成覆盖阵列的构造，举个例子可以更清楚地说明这一点。第一个例子直接来自Chateauneuf, Colburn和Kreher的论文。

例4.starter例子

这个例子是3-CA(27,4,3)的覆盖阵列，这是最小的可能，因为3³ = 27。因为这个例子没有解释所选群和starter阵列，稍后将探讨可能的选择。

使用的群是S₃，即3个元素上的对称群。

G={{0},{01},{02},{12},{123},{132}}.

使用的starter阵列为：

M=

我们考虑群中每个元素作用于给定阵列。首先，我们有不改变阵列的群，接下来我们有元素01，交换所有0和1，而不改变任何2。因此我们得到了阵列:

M_{01}=

类似地，我们得到阵列：

M_{02} M_{12} M_{012} M_{021}

它们是:

显而易见，在这一点上，我们没有任何三重形式的{aaa}。所以我们需要如下所示的4times;3矩阵C。

C=

然后，为了构造覆盖阵列，我们串联所有阵列。这给出了大小为4times;6 3=27的覆盖阵列。这个例子实际上只是为了说明这种构造是如何操作的，因为一个大小为27的覆盖阵列3-CA(4,3) 的存在性不会引起太多数学家的兴趣。

例5.一个更好的例子

利用群G = S₃和下面的starter阵列，可以构建大小为33的覆盖阵列3-CA(6,3)，这是一个让数学家兴奋的结果。

M=

此阵列见附录2第8节。因此，如果他们选择，可以检查阵列中任何三行之间的所有可能三元组。这是一个有趣的过程，但不会向读者阐明这种方法是如何具体操作的。

对于强度为3的阵列，我们关注行之间的三元组，我们将查看在群作用下三元组的轨道。设X是取自Z_g的所有三元组的集合。

X={(a,b,c)|a,b,cZ₃}

那么一个x=(a,b,c)X的轨道是以X为单位设置的

orbit(x)={(g(a)),g(b),g(c))|所有的gG}.

本文所考虑的群是g元素上置换群的子群。每一个gGS_g是一个置换，符号g_a是在置换g下的一个简单置换。

在上述阵列中，前三行中的首个三元组是(012)。S₃组下的三重轨道是:

排列	{0}	{01}	{02}	{12}	{012}	{021}
三元组	{012}	{102}	{210}	{021}	{120}	{201}

在这种构造中，组中的每个元素作用于起始starter阵列来创建新阵列。在本例中，我们将构建6个子矩阵，上述6个三元组将是这些矩阵的每一个的第一列的前3个元素。当我们构造覆盖阵列时，我们保证上述三个三元组将在前三行中出现，因此我们得到27个需要的三元组中的6个，如果我们在起始starter阵列中有一个三重轨道，我们将使整个轨道出现在最终覆盖阵列中，这将整齐地覆盖许多三元组。

在群S₃作用下，很容易列出Z₃的所有三重轨道。它们是:

轨道:

1 {012} {102} {210} {021} {120} {201}

2 {001} {110} {221} {002} {112} {220}

3 {010} {101} {212} {020} {121} {202}

4 {011} {100} {211} {022} {122} {200}

5 {000} {111} {222}

请注意，所有轨道都划分了三元组，并且每个三元组都在一个唯一的轨道中，在最终的覆盖阵列中，我们需要出现每个三元组。

这5条轨道可表示为{aaa},{aab},{aba},{abb},{abc},且abcZ₃。

为了做到这一点，对于starter阵列中的任意三行，我们将使前四个轨道中的每一个轨道中的至少一个元素出现在某一列中。从检查中可以看出，我们的starter阵列具有这个属性，这意味着，当我们对starter阵列进行群操作时，所有三元组(除了最后3个，第5个轨道中的三元组)都将出现。

最后，另外的矩阵C负责最终轨道。

C=

这种构造生成强度为3的覆盖阵列，其大小为5times;6 3。6是群的大小，5是起始starter阵列中的列数，3来自另外的数组C (它是字母表大小)。因此我们有3-CAN(6,3)le;33和2-CAN(5,3)le;11，事实上已知2-CAN(5,3)ge;11，所以我们实际上得到2-CAN(5,3)=11。

这种结构很有趣，但仍有一些重要问题没有得到解答。首先是如何找到这样的starter阵列，这将在第4节中讨论，二是构造覆盖阵列时应采用哪一个群，这将在第5节进行讨论。但是在这个例子中，使用了一种特殊类型的starter阵列和群，它可以在大量情况中使用，这就引出了我们的第一个大定理，也是唯一的。

3.定理

这种构造引出以下定理。

定理6.[12]设v是一个大于2的正整数，q为一个素数幂且满足qge;v-1，那么存在一个覆盖阵列3-CA(n,2v,q 1)，n=(2v-1)(q³-q) q 1。

证明7.证明分为两部分。证明将使用群构造。我们需要一个起始starter阵列M和群G，先从起始starter阵列开始，快速参考附录，有一个图的一因式分解的定义。我们的starter阵列将由2v顶点上的完全图的一次分解来建立，每一行对应于图中的一个顶点，每一列将是一个因子分解中的一个因子，对于每个因子，我们可以用{0,1,hellip;,v-1}集合对因子中的边缘进行编号，在每一列中，我们将行设置为给定因子的顶点所在边的编号。在附录中将再次给出一个示例，给出一个2vtimes;2v-1阵列M，其所有项均取自{0,1,hellip;,v-1}。

证明的第二部分是寻找一个群，它的群操作能够生成一个覆盖阵列。这就是我们要使用的q，是一个素数幂。我们要使用的群就是G=PGL(q)，它是一个变换群。组在变换群GF(q)cup;{infin;}上是3元递归的，这意味着组在集合{aaa},{aab},{aba},{abb},{abc}上是可传递的，a,b,c都取自Z_{q 1}。这意味着我们的轨道将再次形成：

{aaa},{aab},{aba},{abb},{abc}

3元递归组保证了如果我们每个轨道代表starter阵列各3行，当我们用这个组来构造阵列时，我们得到的最终阵列甚至是一个三元组阵列。标记|G|= |PGL(q)| = q³-q

这意味着我们最后需要表明的事是，每一个轨道都在starter阵列的每3行中表示。唯一我们不需要担心的轨道是{aaa}，因为最后我们会添加一个阵列C在末端，来覆盖这些元组，阵列C将是 2vtimes;q 1阵列的第i列，沿着列重复i-1。

我们需要除了第一个轨道的每个轨道，在starter阵列中的每三行显示。首先我们将展示这个轨道{aab}出现在M的xyz行，这个很容易，因为我们从完全图的边E={x,y}外汇一分解建立M，必须出现在一个因素中，记为F_i，在这里因素z不能连接到任何的x或y，（我们使用一个因式分解！），这意味着在列i中，对于x和y，我们有相同的条目，z的条目也不同，同理可以用来表明轨道{aba}和{abb}都到处出现在相同入口。

最后，我们只需要表明，轨道{abc}会发生在矩阵M的某三列{xyz}。在分解中有

剩余内容已隐藏，支付完成后下载完整资料

---

资料编号：[23652]，资料为PDF文档或Word文档，PDF文档可免费转换为Word