Information Technology Reference
In-Depth Information
Fig. 1.1
Orthogonal latin
squares
1230
3012
2103
0321
3210
2301
0123
1032
13 22 31 00
32 03 10 21
20 11 02 33
01 30 23 12
LS
1
LS
2
Mj
Definition 1.1
A
Latin square
of order
n
is an
n
n
array in which each cell is an
element of a set
D
(whose size is
n
), such that each element occurs exactly once in
each row and column.
×
Definition 1.2
A pair of Latin squares of order
n
is said to be
orthogonal
if the
n
2
ordered pairs of elements formed by juxtaposing the two squares are all distinct.
Formally, two latin squares
L
1
and
L
2
aresaidtobe
orthogonal
if for any row
x
,
y
,
and any column
z
,
w
,
(
L
1
(
x
,
z
)
=
L
1
(
y
,
w
)
&
L
2
(
x
,
z
)
=
L
2
(
y
,
w
))
→
(
x
=
y
&
z
=
w
).
Here & denotes conjunction (AND),
→
denotes implication (IMPLIES).
Example 1.1
The matrices
LS
1
and
LS
2
in Fig.
1.1
are two Latin squares. When they
are juxtaposed, as shown by the matrix
Mj
, we can see that all ordered pairs of cells
are distinct. So
LS
1
and
LS
2
are orthogonal Latin squares.
A set of mutually orthogonal Latin squares (MOLS) has the property that every
pair of Latin squares in the set is orthogonal.
1.3.2 Orthogonal Arrays
In the 1980s,
Orthogonal Arrays
(OAs) [
3
,
20
,
33
] were also used in software testing.
For example, in the late 1980s, Phadke and his colleagues at AT&T developed the
tool Orthogonal Array Testing System (OATS), and used it to test PMX/StarMAIL,
an electronic mail product of AT&T, which is based on local area networks [
4
]. The
product should work with several types and versions of LAN software, operating
systems, and personal computers. OAs have also been used by Smith et al. [
37
], to
generate test suites for validating the RAX of the DS1 mission.
Definition 1.3
An
orthogonal array
(OA) of
run size N
,
factor number k
,
strength
t
is an
N
×
k
matrix having the following properties:
(1) There are exactly
s
i
symbols in each column
i
,1
≤
i
≤
k
.
(2) In every
N
t
subarray, each ordered combination of symbols from the
t
columns
appears equally often in the rows.
×
The OA defined above can be denoted by OA
(
N
,
s
1
·
s
2
···
s
k
,
t
)
. We call
s
i
the
level
of factor
i
.
Search WWH ::
Custom Search