In mathematics, anorthogonal array (more specifically, afixed-level orthogonal array) is a table ("array") whose entries come from a fixed finite set of symbols (for example, {1,2,...,v}), arranged in such a way that there is an integert so that for every selection oft columns of the table, all orderedt-tuples of the symbols, formed by taking the entries in each row restricted to these columns, appear the same number of times. The numbert is called thestrength of the orthogonal array. Here are two examples:
| 1 | 1 | 1 |
| 2 | 2 | 1 |
| 1 | 2 | 2 |
| 2 | 1 | 2 |
| 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 example at left is that of an orthogonal array with symbol set {1,2} and strength 2. Notice that the fourordered 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.
In the example on the right,[1] the rows restricted to the first three columns contain the 8 possibleordered triples consisting of 0's and 1's, each appearing once. The same holds for any other choice of three columns. Thus this is an orthogonal array of strength 3.
Amixed-level orthogonal array is one in which each column may have a different number of symbols. An example is given below.
Orthogonal arrays generalize, in a tabular form, the idea ofmutually orthogonal Latin squares. These arrays have many connections to other combinatorial designs and have applications in the statisticaldesign of experiments,coding theory,cryptography and various types ofsoftware testing.
.svg)
Fort ≤k, anorthogonal array of type (N, k, v, t) – anOA(N, k, v, t) for short – is anN ×k array whose entries are chosen from a setX withv points (av-set) such that in every subset oft columns of the array, everyt-tuple of points ofX is repeated the same number of times. The number of repeats is usually denoted λ.
In many applications these parameters are given the following names:
The definition of strength leads to the parameter relation
An orthogonal array issimple if it does not contain any repeated rows. (Subarrays oft columns may have repeated rows, as in the OA(18, 7, 3, 2) example pictured in this section.)
An orthogonal array islinear ifX is afinite fieldFq of orderq (q a prime power) and the rows of the array form a subspace of thevector space (Fq)k.[2] The right-hand example in the introduction is linear over the fieldF2. Every linear orthogonal array is simple.
In a mixed-level orthogonal array, the symbols in the columns may be chosen from different sets having different numbers of points, as in the following example:[3]
| 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 |
This array has strength 2:
It may thus be denoted may be denoted OA(8, 5, 2441, 2), as is discussed below. The expression 2441 indicates that four factors have 2 levels and one has 4 levels.
As in this example, there is no single ``index" or repetition number λ in a mixed-level orthogonal array of strengtht: Each subarray oft columns can have a different λ.
The termssymmetric andasymmetric are sometimes used forfixed-level andmixed-level. Here symmetry refers to the property that all factors have the same number of levels, not to the "shape" of the array: a symmetric orthogonal array is almost never asymmetric matrix.
The notation OA(N, k, v, t) is sometimes contracted so that one may, for example, write simply OA(k, v),[4] as long as the text makes clear the unstated parameter values. In the other direction, it may be expanded for mixed-level arrays. Here one would write OA(N, k, v1···vk, t), where columni hasvi levels. This notation is usually shortened when valuesv are repeated, so that one writes OA(8, 5, 2441, 2) for the example at the end of the last section, rather than OA(8, 5, 2·2·2·2·4, 2). In similar fashion, one may shorten OA(N, k, v, t) to OA(N, vk, t) for fixed-level arrays.
This OA notation does not explicitly include the index λ, but λ can be recovered from the other parameters via the relationN = λvt. This is effective when the parameters all have specific numerical values, but less so when aclass of orthogonal arrays is intended. For example, when indicating the class of arrays having strengtht = 2 and index λ=1, the notation OA(N, k, v, 2) is insufficient to determine λ by itself. This is typically remedied by writing OA(v2, k, v, 2) instead. While notations that explicitly include the parameter λ do not have this problem, they cannot easily be extended to denote mixed-level arrays.
Some authors define an OA(N, k, v, t) as beingk ×N rather thanN ×k. In such cases the strength of the array is defined in terms of a subset oftrows rather than columns.
Except for the prefix OA, the notation OA(N, k, v, t) is the same as that introduced by Rao.[5] While this notation is very common, it not universal. Hedayat, Sloane and Stufken[6] recommend it as standard, but list eight alternatives found in the literature, and there are others.[8]
An example of an OA(16, 5, 4, 2); 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 an OA(27, 5, 3, 2) (written as itstranspose for ease of viewing):[9]
| 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 |
This example has index λ = 3.
An array consisting of allk-tuples of av-set, arranged so that thek-tuples are rows, automatically ("trivially") has strengthk, and so is an OA(vk, k, v, k).Any OA(N, k, v, k) would be consideredtrivial since such arrays are easily constructed by simply listing all thek-tuples of thev-set λ times.
An OA(n2, 3, n, 2) is equivalent to aLatin square of ordern. Fork ≤n+1, an OA(n2, k, n, 2) is equivalent to a set ofk − 2mutually orthogonal Latin squares of ordern. Such index one, strength 2 orthogonal arrays are also known asHyper-Graeco-Latin square designs in the statistical literature.
LetA be a strength 2, index 1 orthogonal array on ann-set of elements, identified with the set of natural numbers {1,...,n}. Choose and fix, in order, two columns ofA, called theindexing columns. Because the strength is 2 and the index is 1, all ordered pairs (i,j) with 1 ≤i,j ≤n appear exactly once in the rows of the indexing columns. Herei andj will in turn index the rows and columns of an×n square. Take any other column ofA and fill the (i,j) cell of this square with the entry that is in this column ofA and in the row ofA whose indexing columns contain (i,j). The resulting square is aLatin square of ordern. For example, consider this OA(9, 4, 3, 2):
| 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 |
These two squares, moreover, are mutually orthogonal. In general, the Latin squares produced in this way from an orthogonal array will be orthogonal Latin squares, so thek − 2 columns other than the indexing columns will produce a set ofk − 2mutually 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.[10]
Orthogonal arrays provide a uniform way to describe these diverse objects which are of interest in the statisticaldesign of experiments.
As mentioned in the previous section, a Latin square of ordern can be thought of as an OA(n2, 3, n, 2). 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 allisotopic 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.
In the statistics literature, aLatin cube is a three-dimensionaln ×n ×n matrix consisting ofn layers, each havingn rows andn columns such that then distinct elements which appear are repeatedn2 times and arranged so that in each layer parallel to each of the three pairs of opposite faces of the cube all then distinct elements appear and each is repeated exactlyn times in that layer.[11]
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 apermutation of then symbols.[12]
A Latin cube of ordern is equivalent to an OA(n3, 4 ,n, 2).[9]
Two Latin cubes of ordern areorthogonal if, among then3 pairs of elements chosen from corresponding cells of the two cubes, each distinct ordered pair of the elements occurs exactlyn times. A set ofk − 3 mutually orthogonal Latin cubes of ordern is equivalent to an OA(n3, k, n, 2).[9] An example of a pair of mutually orthogonal Latin cubes of order three was given as the OA(27, 5, 3, 2) in theExamples 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 an OA(n3, 3, n, 3).
Anm-dimensionalLatin hypercube of ordern of therth class is ann ×n × ... ×nm-dimensional matrix havingnr distinct elements, each repeatednm − r times, and such that each element occurs exactlynm − r − 1 times in each of itsm sets ofn parallel (m − 1)-dimensional linear subspaces (or "layers"). Two such Latin hypercubes of the same ordern and classr with the property that, when one is superimposed on the other, every element of the one occurs exactlynm − 2r times with every element of the other, are said to beorthogonal.[13]
A set ofk − m mutually orthogonalm-dimensional Latin hypercubes of ordern is equivalent to an OA(nm, k, n, 2), where the indexing columns form an OA(nm, m, n, m).
The concepts ofLatin squares andmutually orthogonal Latin squares were generalized to Latin cubes and hypercubes, and orthogonal Latin cubes and hypercubes byKishen (1942).[14]Rao (1946) generalized these results to arrays of strengtht. The present notion of orthogonal array as a generalization of these ideas, due to legendary scientistC. R. Rao, appears inRao (1947),[15] with his generalization to mixed-level arrays appearing in 1973.[16]
Rao initially used the term "array" with no modifier, and defined it to mean simply a subset of all treatment combinations – asimple array. The possibility of non-simple arrays arose naturally when making treatment combinations the rows of a matrix. Hedayat, Sloane and Stufken[17] credit K. Bush[18] with the term "orthogonal array".
There exists an OA(4λ, 4λ − 1, 2, 2) if and only if there exists aHadamard matrix of order 4λ.[19] To proceed in one direction, letH be a Hadamard matrix of order 4m in standardized form (first row and column entries are all +1). Delete the first row and take thetranspose to obtain the desired orthogonal array.[20] The following example illustrates this. (The reverse construction is similar.)
The order 8 standardized Hadamard matrix below (±1 entries indicated only by sign),
| + | + | + | + | + | + | + | + |
| + | + | + | + | − | − | − | − |
| + | + | − | − | + | + | − | − |
| + | + | − | − | − | − | + | + |
| + | − | + | − | + | − | + | − |
| + | − | + | − | − | + | − | + |
| + | − | − | + | + | − | − | + |
| + | − | − | + | − | + | + | − |
produces the OA(8, 7, 2, 2):[21]
| + | + | + | + | + | + | + |
| + | + | + | − | − | − | − |
| + | − | − | + | + | − | − |
| + | − | − | − | − | + | + |
| − | + | − | + | − | + | − |
| − | + | − | − | + | − | + |
| − | − | + | + | − | − | + |
| − | − | + | − | + | + | − |
Using columns 1, 2 and 4 as indexing columns, the remaining columns produce four mutually orthogonal Latin cubes of order 2.
LetC ⊆ (Fq)n, be alinear code of dimensionm with minimum distanced. ThenC⊥ (the orthogonal complement of the vector subspaceC) is a (linear) OA(qn-m, n, q, d − 1)where
λ = qn − m − d + 1.[22]
Secret sharing (also calledsecret splitting) consists of methods for distributing asecret amongst a group of participants, each of whom is allocated ashare of the secret. The secret can be reconstructed only when a sufficient number of shares, of possibly different types, are combined; individual shares are of no use on their own. A secret sharing scheme isperfect 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 onedealer andnplayers. 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 oft (forthreshold) or more players can together reconstruct the secret but no group of fewer thant players can. Such a system is called a (t, n)-threshold scheme.
An OA(vt, n+1, v, t) may be used to construct a perfect (t,n)-threshold scheme.[23]
Afactorial experiment is a statistically structured experiment in which severalfactors (watering levels, antibiotics, fertilizers, etc.) are applied to each experimental unit at finitely manylevels, which may be quantitative or qualitative.[24] In afull factorial experiment all combinations of levels of the factors need to be tested. In afractional factorial design only a subset of treatment combinations are used.
An orthogonal array can be used to design a fractional factorial experiment. The columns represent the various factors and the entries are the levels at which the factors are observed. An experimental run is a row of the orthogonal array, that is, a specific combination of factor levels. The strength of the array determines the resolution of the fractional design. 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, and that the run order then be randomized.
Mixed-level designs occur naturally in the statistical setting.
Orthogonal arrays played a central role in the development ofTaguchi methods byGenichi Taguchi, which took place during his visit toIndian Statistical Institute in the 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[citation needed]. Taguchi's catalog[25] contains both fixed- and mixed-level arrays.
Orthogonal array testing is ablack box testing technique which is a systematic,statistical way ofsoftware testing.[26][27] 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 thesystems.[26] It is particularly effective in finding errors associated with faultylogic withincomputersoftware systems.[26] Orthogonal arrays can be applied inuser interface testing,system testing,regression testing andperformance testing.Thepermutations of factor levels comprising a single treatment are so chosen that their responses are uncorrelated and hence each treatment gives a unique piece ofinformation. The net effect of organizing the experiment in such treatments is that the same piece of information is gathered in the minimum number ofexperiments.
Numerous articles on utilizing Orthogonal Arrays for Software and System Testing.
{{cite book}}: CS1 maint: multiple names: authors list (link)| Scientific method | |
|---|---|
| Treatment andblocking | |
| Models andinference | |
| Designs Completely randomized | |
This article incorporatespublic domain material from the National Institute of Standards and Technology
