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

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

An OA(8,4,2,3)

N is equal to 8 and represents the number of rows.

In combinatorics the rows represent different tests to be run.

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

An OA(8,4,2,3)

k is equal to 4 and represents the number columns.

In combinatorics the each column represents a different parameter.


0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

An OA(8,4,2,3)

s is equal to 2 and represents the number of possible variable values.

In combinatorics the values represent the different levels or states for the parameters being tested.

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

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}

In combinatorics this could represent something like an off or on switch.

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

An OA(8,4,2,3)

t is equal to 3 and represents the number of variables in each N x t subarray.

In combinatorics a larger strength means more combinations.

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

An OA(8,4,2,3)

There are 4 different subarrays each containing every combination of 3 parameters excactly one time

3 columns are highlighted with yellow, 3 are outlined in red, 3 are in italics and 3 are colored blue.

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

An OA(8,4,2,3)

The final parameter of an Orthogonal array is the index λ which can be calculated by the formula λ =N/s^t

The index represents the number of times each combination of values appears in each subarray.

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

An OA(8,4,2,3)

λ =8/2³=1 so this Orthogonal array has index unity because the index is equal to one.

Within combinatorics the index can play a large role in testing, this concept will be explored further in an application tutorial.

0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

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.

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,s^k,t). N and t stay the same, but now there are k variables with s values.

Let's look at a simple example.

An OA(8,2⁴,4¹,2)

Here there are 4 columns with 2 possible values, and 1 column with 4 possible values.

This can be adjusted in countless ways, and is essential when testing complicated systems.


0	0	0	0	0
1	1	1	1	0
0	0	1	1	1
1	1	0	0	1
0	1	0	1	2
1	0	1	0	2
0	1	1	0	3
1	0	0	1	3

An OA(8,2⁴,4¹,2)

Note that the possible combinations now depends on which columns are chosen to look at.

2 values combined creates 4 possibilities (0,0) (0,1) (1,0) (1,1) which each occur 2 times in this mixed orthogonal array.


0	0	0	0	0
1	1	1	1	0
0	0	1	1	1
1	1	0	0	1
0	1	0	1	2
1	0	1	0	2
0	1	1	0	3
1	0	0	1	3

An OA(8,2⁴,4¹,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.

In general N must be a multiple of all the different numbers of possibilities, in this case 4 and 8.


0	0	0	0	0
1	1	1	1	0
0	0	1	1	1
1	1	0	0	1
0	1	0	1	2
1	0	1	0	2
0	1	1	0	3
1	0	0	1	3

What is the correct denotation of This Mixed Orthogonal Array?

OA(18,4⁶,2³,2)

OA(16,4⁶,2³,3)

OA(16,2⁹,4³,2)

OA(16,2⁶,4³,2)

OA(16,2⁶,4³,3)

0	0	0	0	0	0	0	0	0
1	1	0	1	0	1	0	2	2
0	1	1	1	1	0	2	0	2
1	0	1	0	1	1	2	2	0
0	0	1	1	1	1	0	3	3
1	1	1	0	1	0	0	1	1
0	1	0	0	0	1	2	3	1
1	0	0	1	0	0	2	1	3
1	1	0	0	1	1	3	0	3
0	0	0	1	1	0	3	2	1
1	0	1	1	0	1	1	0	1
0	1	1	0	0	0	1	2	3
1	1	1	1	0	0	3	3	0
0	0	1	0	0	1	3	1	2
1	0	0	0	1	0	1	3	2
0	1	0	1	1	1	1	1	0

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.

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.

Back to Main Tutorial

Tutorial on construction of Orthogonal Arrays

Orthogonal Array Tutorial

Previous

Next