Orthogonal array

In mathematics, in the area of combinatorial designs, an orthogonal array is a "table" (array) whose entries come from a fixed finite set of symbols (typically, {1,2,...,n}), arranged in such a way that there is an integer t so that for every selection of t columns of the table, all ordered t-tuples of the symbols, formed by taking the entries in each row restricted to these columns, appear the same number of times. The number t is called the strength of the orthogonal array. Here is a simple example of an orthogonal array with symbol set {1,2}:

1 1 1
2 2 1
1 2 2
2 1 2

Notice that the four ordered pairs (2-tuples) formed by the rows restricted to the first and third columns, namely (1,1), (2,1), (1,2) and (2,2) are all the possible ordered pairs of the two element set and each appears exactly once. The second and third columns would give, (1,1), (2,1), (2,2) and (1,2); again, all possible ordered pairs each appearing once. The same statement would hold had the first and second columns been used. This is thus an orthogonal array of strength two.

Orthogonal arrays generalize the idea of mutually orthogonal latin squares in a tabular form. These arrays have many connections to other combinatorial designs and have applications in the statistical design of experiments, coding theory, cryptography and various types of software testing.

Definition

A t-(v,k,λ) orthogonal array (t ≤ k) is a λvt × k array whose entries are chosen from a set X with v points such that in every subset of t columns of the array, every t-tuple of points of X appears in exactly λ rows.

In this formal definition, provision is made for repetition of the t-tuples (λ is the number of repeats) and the number of rows is determined by the other parameters.

In many applications these parameters are given the following names:

v is the number of levels,
k is the number of factors,
λvt is the number of experimental runs,
t is the strength, and
λ is the index.

An orthogonal array is simple if it does not contain any repeated rows.

An orthogonal array is linear if X is a finite field of order q, Fq (q a prime power) and the rows of the array form a subspace of the vector space (Fq)k.[1]

Every linear orthogonal array is simple.

Examples

An example of a 2-(4, 5, 1) orthogonal array; a strength 2, 4 level design of index 1 with 16 runs.

1 1 1 1 1
1 2 2 2 2
1 3 3 3 3
1 4 4 4 4
2 1 4 2 3
2 2 3 1 4
2 3 2 4 1
2 4 1 3 2
3 1 2 3 4
3 2 1 4 3
3 3 4 1 2
3 4 3 2 1
4 1 3 4 2
4 2 4 3 1
4 3 1 2 4
4 4 2 1 3

An example of a 2-(3,5,3) orthogonal array (written as its transpose for ease of viewing):[2]

0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2 0 0 0 1 1 1 2 2 2
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2
0 0 0 1 1 1 2 2 2 2 2 2 0 0 0 1 1 1 1 1 1 2 2 2 0 0 0
0 1 2 1 2 0 2 0 1 0 1 2 1 2 0 2 0 1 0 1 2 1 2 0 2 0 1

Trivial examples

Any t-(v, t, λ) orthogonal array would be considered trivial since they are easily constructed by simply listing all the t-tuples of the v-set λ times.

Mutually orthogonal latin squares

A 2-(v,k,1) orthogonal array is equivalent to a set of k − 2 mutually orthogonal latin squares of order v.

Index one, strength 2 orthogonal arrays are also known as Hyper-Graeco-Latin square designs in the statistical literature.

Let A be a strength 2, index 1 orthogonal array on a v-set of elements, identified with the set of natural numbers {1,...,v}. Chose and fix, in order, two columns of A, called the indexing columns. All ordered pairs (i, j) with 1 ≤ i, j ≤ v appear exactly once in the rows of the indexing columns. Take any other column of A and create a square array whose entry in position (i,j) is the entry of A in this column in the row that contains (i, j) in the indexing columns of A. The resulting square is a latin square of order v. For example, consider the 2-(3,4,1) orthogonal array:

1 1 1 1
1 2 2 2
1 3 3 3
2 1 2 3
2 2 3 1
2 3 1 2
3 1 3 2
3 2 1 3
3 3 2 1

By choosing columns 3 and 4 (in that order) as the indexing columns, the first column produces the latin square,

1 2 3
3 1 2
2 3 1

while the second column produces the latin square,

1 3 2
3 2 1
2 1 3

The latin squares produced in this way from an orthogonal array will be orthogonal latin squares, so the k − 2 columns other than the indexing columns will produce a set of k − 2 mutually orthogonal latin squares.

This construction is completely reversible and so strength 2, index 1 orthogonal arrays can be constructed from sets of mutually orthogonal latin squares.[3]

Latin squares, latin cubes and latin hypercubes

Orthogonal arrays provide a uniform way to describe these diverse objects which are of interest in the statistical design of experiments.

Latin squares

As mentioned in the previous section a latin square of order n can be thought of as a 2-(n, 3, 1) orthogonal array. Actually, the orthogonal array can lead to six latin squares since any ordered pair of distinct columns can be used as the indexing columns. However, these are all isotopic and are considered equivalent. For concreteness we shall always assume that the first two columns in their natural order are used as the indexing columns.

Latin cubes

In the statistics literature, a latin cube is an n × n × n three-dimensional matrix consisting of n layers, each having n rows and n columns such that the n distinct elements which appear are repeated n2 times and arranged so that in each layer parallel to each of the three pairs of opposite faces of the cube all the n distinct elements appear and each is repeated exactly n times in that layer.[4]

Note that with this definition a layer of a latin cube need not be a latin square. In fact, no row, column or file (the cells of a particular position in the different layers) need be a permutation of the n symbols.[5]

A latin cube of order n is equivalent to a 2-(n, 4, n) orthogonal array.[2]

Two latin cubes of order n are orthogonal if, among the n3 pairs of elements chosen from corresponding cells of the two cubes, each distinct ordered pair of the elements occurs exactly n times.

A set of k − 3 mutually orthogonal latin cubes of order n is equivalent to a 2-(n, k, n) orthogonal array.[2]

An example of a pair of mutually orthogonal latin cubes of order three was given as the 2-(3,5,3) orthogonal array in the Examples section above.

Unlike the case with latin squares, in which there are no constraints, the indexing columns of the orthogonal array representation of a latin cube must be selected so as to form a 3-(n,3,1) orthogonal array.

Latin hypercubes

An m-dimensional latin hypercube of order n of the rth class is an n × n × ... ×n m-dimensional matrix having nr distinct elements, each repeated nm − r times, and such that each element occurs exactly n m − r − 1 times in each of its m sets of n parallel (m − 1)-dimensional linear subspaces (or "layers"). Two such latin hypercubes of the same order n and class r with the property that, when one is superimposed on the other, every element of the one occurs exactly nm − 2r times with every element of the other, are said to be orthogonal.[6]

A set of k − m mutually orthogonal m-dimensional latin hypercubes of order n is equivalent to a 2-(n, k, nm − 2) orthogonal array, where the indexing columns form an m-(n, m, 1) orthogonal array.

History

The concepts of latin squares and mutually orthogonal latin squares were generalized to latin cubes and hypercubes, and orthogonal latin cubes and hypercubes by Kishen (1942).[7] Rao (1946) generalized these results to strength t. The present notion of orthogonal array as a generalization of these ideas, due to C. R. Rao, appears in Rao (1947).[8]

Other constructions

Hadamard matrices

If there exists an Hadamard matrix of order 4m, then there exists a 2-(2, 4m − 1, m) orthogonal array.

Let H be an Hadamard matrix of order 4m in standardized form (first row and column entries are all +1). Delete the first row and take the transpose to obtain the desired orthogonal array.[9]

The order 8 standardized Hadamard matrix below (±1 entries indicated only by sign),

+ + + + + + + +
+ + + + − − − −
+ + − − + + − −
+ + − − − − + +
+ − + − + − + −
+ − + − − + − +
+ − − + + − − +
+ − − + − + + −

produces the 2-(2,7,2) orthogonal array:[10]

+ + + + + + +
+ + + − − − −
+ − − + + − −
+ − − − − + +
− + − + − + −
− + − − + − +
− − + + − − +
− − + − + + −

Using columns 1, 2 and 4 as indexing columns, the remaining columns produce four mutually orthogonal latin cubes of order 2.

Codes

Let C ⊆ (Fq)n, be a linear code of dimension m with minimum distance d. Then C⊥ (the orthogonal complement of the vector subspace C) is a (linear) (d − 1)-(n, q, λ) orthogonal array where
λ = qn − m − d + 1.[11]

Applications

Threshold schemes

Main article: Secret sharing

Secret sharing (also called secret splitting) consists of methods for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares, of possibly different types, are combined together; individual shares are of no use on their own. A secret sharing scheme is perfect if every collection of participants that does not meet the criteria for obtaining the secret, has no additional knowledge of what the secret is than does an individual with no share.

In one type of secret sharing scheme there is one dealer and n players. The dealer gives shares of a secret to the players, but only when specific conditions are fulfilled will the players be able to reconstruct the secret. The dealer accomplishes this by giving each player a share in such a way that any group of t (for threshold) or more players can together reconstruct the secret but no group of fewer than t players can. Such a system is called a (t, n)-threshold scheme.

A t-(v, n + 1, 1) orthogonal array may be used to construct a perfect (t, n)-threshold scheme.[12]

Let A be the orthogonal array. The first n columns will be used to provide shares to the players, while the last column represents the secret to be shared. If the dealer wishes to share a secret S, only the rows of A whose last entry is S are used in the scheme. The dealer randomly selects one of these rows, and hands out to player i the entry in this row in column i as shares.

Factorial designs

Main article: Factorial experiment

A factorial experiment is a statistically structured experiment in which several factors (watering levels, antibiotics, fertilizers, etc.) are applied to each experimental unit at varying (but integral) levels (high, low, or various intermediate levels).[13] In a full factorial experiment all combinations of levels of the factors need to be tested, but to minimize confounding influences the levels should be varied within any experimental run.

An orthogonal array of strength 2 can be used to design a factorial experiment. The columns represent the various factors and the entries are the levels that the factors can be applied at (assuming that all factors can be applied at the same number of levels). An experimental run is a row of the orthogonal array, that is, apply the corresponding factors at the levels which appear in the row. When using one of these designs, the treatment units and trial order should be randomized as much as the design allows. For example, one recommendation is that an appropriately sized orthogonal array be randomly selected from those available, then randomize the run order.

Quality control

Orthogonal arrays played a central role in the development of Taguchi methods by Genichi Taguchi, which took place during his visit to Indian Statistical Institute in early 1950s. His methods were successfully applied and adopted by Japanese and Indian industries and subsequently were also embraced by US industry albeit with some reservations.

Testing

Orthogonal array testing is a black box testing technique which is a systematic, statistical way of software testing.[14][15] It is used when the number of inputs to the system is relatively small, but too large to allow for exhaustive testing of every possible input to the systems.[14] It is particularly effective in finding errors associated with faulty logic within computer software systems.[14] Orthogonal arrays can be applied in user interface testing, system testing, regression testing and performance testing. The permutations of factor levels comprising a single treatment are so chosen that their responses are uncorrelated and hence each treatment gives a unique piece of information. The net effect of organizing the experiment in such treatments is that the same piece of information is gathered in the minimum number of experiments.

See also

Notes

  1. ↑ Stinson 2003, pg. 225
  2. 1 2 3 Dénes & Keedwell 1974, pg. 191
  3. ↑ Stinson 2003, pp. 140–141, Section 6.5.1
  4. ↑ Dénes & Keedwell 1974, pg. 187 credit the definition to Kishen (1950, pg. 21)
  5. ↑ In the combinatorialist's preferred definition, each row, column and file would contain a permutation of the symbols, but this is only a special type of latin cube called a permutation cube.
  6. ↑ Dénes & Keedwell 1974, pg. 189
  7. ↑ Raghavarao 1988, pg. 9
  8. ↑ Raghavarao 1988, pg. 10
  9. ↑ Stinson 2003, pg. 225, Theorem 10.2
  10. ↑ Stinson 2003, pg. 226, Example 10.3
  11. ↑ Stinson 2003, pg. 231, Theorem 10.17
  12. ↑ Stinson 2003, pg. 262, Theorem 11.5
  13. ↑ Street & Street 1987, pg. 194, Section 9.2
  14. 1 2 3 Pressman, Roger S (2005). Software Engineering: A Practitioner's Approach (6th ed.). McGraw–Hill. ISBN 0-07-285318-2.
  15. ↑ Phadke, Madhav S. "Planning Efficient Software Tests". Phadke Associates, Inc. Numerous articles on utilizing Orthogonal Arrays for Software and System Testing.

References

External links

 This article incorporates public domain material from websites or documents of the National Institute of Standards and Technology.

This article is issued from Wikipedia - version of the Tuesday, March 15, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.