Objectives.
Orthogonal Arrays play an
important role in combinatorics.
This Tutorial will give a
quick introduction to what Orthogonal Arrays are and why they are
useful.
Goals:
1. Understand
what an Orthogonal Array is
2. Determine the
important factors of an Orthogonal Array by looking at its
denotation
1
The definition of an
orthogonal array is as follows.
An N x k array A
with entries from some set S with s levels, strength t within
the range 0 ≤ t ≤ kand index
λ where every
N x t
subarray of A contains each t-tuple based on S exactly λ
times as a row.
This information can be found within the standard notation of an Orthogonal Array which is OA(N,k,s,t)
To make it easier to understand let's run through a quick example
2
An OA(8,4,2,3)
N is equal to 8 and represents
the number of rows. |
|
3
An OA(8,4,2,3)
k is equal to 4 and represents
the number columns. |
|
4
An OA(8,4,2,3)
s is equal to 2 and represents
the number of possible variable values. |
|
5
An OA(8,4,2,3)
Note that in this example because
s is equal to 2 we are dealing with the set of possible values
S={0,1} |
|
6
An OA(8,4,2,3)
t is equal to 3 and represents
the number of variables in each N x t subarray. |
|
7
An OA(8,4,2,3)
There are 4 different subarrays
each containing every combination of 3 parameters excactly one time
|
|
8
An OA(8,4,2,3)
The final parameter of an
Orthogonal array is the index λ which can be calculated by the
formula λ =N/st |
|
9
An OA(8,4,2,3)
λ =8/23=1 so this
Orthogonal array has index unity because the index is equal to
one. |
|
10
The Orthogonal array
testing system or OATS uses the concept of orthogonal arrays to
design tests for software systems
By setting up an Orthogonal Array with testing
parameters and approprite values you can easily create a series
of tests that can cover all pairwise or greater combinations.
The paper "Robust Testing of AT&T PMX/StarMAIL using OATS" showed that by using OATS they had a higher level of confidence for the finished product when released on time then originaly anticipated.
Next let's see how orthogonal arrays can be adjusted for more complex systems.
11
An Orthogonal Array can be
limited by its definition, so what if a problem requires more flexability? One possible option is
using a Mixed Orthogonal Array.
What makes them so useful is that different
variables are not restricted by the same set of possible values.
A Mixed Orthogonal Array is denoted by OA(N,sk,t). N and t stay the same, but now there are k variables with s values.
Let's look at a simple example.
12
An OA(8,24,41,2)
Here there are 4
columns with 2 possible values, and 1 column with 4 possible
values. |
|
13
An OA(8,24,41,2)
Note that the possible
combinations now depends on which columns are chosen to look at. |
|
14
An OA(8,24,41,2)
One 2 value and one 4 value
variable combined create 8 possibilites (0,0) (1,0) (1,1) (0,1) (1,2) (0,2) (0,3)
(1,3) which each occur 1 time in this mixed orthogonal array. |
|
15
What is the correct denotation of This Mixed Orthogonal Array? |
|
16
One of the problems with
using Orthogonal Arrays is that they can be too strict with
their index values. By relaxing the index you can create a
covering array.
Covering arrays are desired for their ability to
cover all the imporant combinations while reducing the size of
the array as much as possible.
A Covering array can be denoted by CA(t,k,v) with t and k the same as t and k for an orthogonal array and v the same as s for an othogonal array .
Covering arrays will be covered further in a later tutorial.
17
Recap.
One of the key underlining
concepts in combinatorics is Orthogonal Arrays.
Having at least some basic knowledge in what they can help make sense of the more complicated concepts.
18