Information Technology Reference
In-Depth Information
2.2.3.1 Strength-2 Covering Arrays
In [
2
], Colbourn showed that CAs of strength 2 can be easily constructed with DCAs.
v
k
Theorem 2.9
If there exists a
DCA
(
k
,
n
;
v
)
, then there exists a
CA
(
nv
,
,
2
)
.
Given a DCA
(
k
,
n
;
v
)(
d
ij
)
over the Abelian group
G
of order
v
. For each row vector
d
i
1
,
d
i
2
,...,
d
ik
(
1
≤
i
≤
n
)
and each element
u
∈
G
, we construct a row vector
(
d
i
1
+
u
), (
d
i
2
+
u
), . . . , (
d
ik
+
u
)
.
v
k
These
n
×
v
row vectors form a CA
(
nv
,
,
2
)
.
2
4
Example 2.6
From the DCA
in
Fig.
2.9
using this method. Since the DCA is over
Z
2
, each row vector in the DCA
would produce two row vectors in the CA by adding '0' and '1' respectively.
(
4
,
3
;
2
)
in Fig.
2.8
, we can construct a CA
(
6
,
,
2
)
2.2.3.2 Strength-3 Covering Arrays
In [
6
], Ji and Yin proposed two constructive methods to build covering arrays of
strength 3 based on DCAs. For simplicity we only introduce the first one.
nv
2
v
5
Theorem 2.10
If there exists a
DCA
(
4
,
n
;
v
)
, then there exists a
CA
(
,
,
3
)
.
Given a DCA
(
4
,
n
;
v
)(
d
ij
)
over the Abelian group
G
of order
v
. For each row vector
d
i
1
,
d
i
2
,
d
i
3
,
d
i
4
(
1
≤
i
≤
n
),
we construct a series of row vectors
Fig. 2.8
DCA
(
4
,
3
;
2
)
0000
0101
0011
Fig. 2.9
Construct a
0 0 0 0
0101
0011
1111
1 0 1 0
1100
2
4
CA
(
6
,
,
2
)
from a
DCA
(
4
,
3
;
2
)
Search WWH ::
Custom Search