An alternate formulation is given for index one orthogonal arrays based on computer searches. Orthogonal arrays in diagonal form, and their elements' products, powers, and orders, are derived from first column vectors which result from the searches. Mapping operators relating the first column vectors for each number of levels (m) are described. A scheme for factoring the mapping operators is suggested also. Results are given for values of m which are primes, prime powers, and prime power products. An association between first column vectors and irreducible monic polynomials is made for selected prime power values of m.
Permutation vectors which extend the formulation to groups with orders of powers of m are defined for values of m which are primes and prime powers. Properties of the permutation vectors are described. A formulation is given for strength two covering arrays based on the permutation vectors. These arrays have wm2-(w-1)m rows and (mw+1-1)/(m-1) columns for values of w which are positive integers. A sliding levels technique is suggested to include values of m which are prime power products.
Zero sum arrays are constructed using the permutation vectors. A recursive construction for strength three covering arrays is given for m equal to two. Alternatively, the cats program is used to find strength three and four covering arrays by removing redundant rows from covering arrays of permutation vectors.
For values of m which are primes and prime powers, another formulation describes sets of permutation vectors which do not cover. The formulation is used to find covering arrays of strength greater than two, by forming arrays of permutation vectors in which each combination of columns contains a combination of permutation vectors which is not noncovering. Resulting covering arrays of strengths l=3 and l=4 have zml-(z-1)m rows for values of z which are positive integers. The numbers of columns found are consistent with the conjecture that arrays of this form can have m+1 columns for z=1 and mz columns for z>1.
For values of m which are primes and prime powers, and for strengths greater than two, a narrower, recursive search is described for index one orthogonal arrays of permutation vectors. The search results suggest a formula for orthogonal arrays with m+1 columns, and strengths up to m+1. Selected results are given for strengths up to four.
Four years ago I started a mathematical journey. These are my travel notes. They document my search for ways to construct covering arrays using various computer search techniques. The computer search has been a heuristic tool for me, with results leading to improved searches, as well as to the mathematical patterns described here.
I suppose the reader who is interested in orthogonal arrays and covering arrays may desire a rigorous mathematical deduction of results. That is not the purpose of these notes. I have included some informal logical illustrations, but the emphasis here is on pattern recognition and description, rather than formal proof. The reader will not find a clear boundary drawn between derivation and conjecture. Instead, I invite the reader who travels these paths to join in the logical development of the ideas, to add the rigor where it fits.
AT&T Labs provided computer facilities supporting this work. (A Sun Microsystems Ultra 5 workstation executed the searches described here.) Also, I would like to acknowledge the interest and support of several people in my earlier work on the Constrained Array Test System (which was one of the motivators of the present work). These colleagues include:
Otto Sgro | David Gelperin | |
Jim Prowse | Bob Stahl | |
Alex Gillon | Willa Ehrlich | |
Merle Poller | Colin Mallows | |
Bob Brownlie | Neil Sloane | |
Madhav Phadke |
In particular, Colin and Neil showed me there was new ground to explore here. Finally I want to thank my family Ann, Jeffrey, Andrew, and Daniel for their patience and understanding during my travels.
Have a good trip!
George Sherwood
March 2002
This section defines Dot Vectors and Dot Operators.
For each of the m levels h=0, 1, ..., m-1,
define the vector h. given by repeating the value of h m times.
For example, for m=3, the dot vectors are:
The unary dot operator acts on an array to replace each element with its corresponding dot vector.
The result is an array with m times the number of rows compared to the original array.
Thus,
Similarly, the raised dot operator replaces each element of an array with its corresponding dot vector transposed.
The result is an array with m times the number of columns compared to the original array:
The number of levels m for a dot vector or operator usually is taken from its context.
If the number of levels is not clear, the value is indicated in braces after the dot (e.g. h.{3}).
When the number of columns c<m, the dot vectors may be truncated to c elements.
This case is indicated by {c/m} or just {c/} after the dot (e.g. h·{2/6} when m=6).
This section defines Plus Vectors and Plus Operators for three cases:
In all cases the zero plus vector 0+{m} is defined to contain all m levels in ascending order:
Note that the definitions given in this section are not the only choice leading to the formulations given here.
Later sections will illustrate two cases in which alternate plus vector definitions can affect results.
However, a systematic study of all choices of plus vectors is beyond the current scope.
Construct the modulo m=p addition table (p=prime) for the m order cyclic group.
Each table element in row j=0, 1, ..., m-1 and column k=0, 1, ..., m-1 has the value j+k (mod m).
For example, for m=3, the table is
Now define the m vectors k+ given by the table columns. In this example, they are
The unary plus operator acts on an array to replace each element with its corresponding plus vector.
The result is an array with m times the number of rows compared to the original array.
Thus,
Similarly, the raised plus operator replaces each element of an array with its corresponding plus vector transposed.
The result is an array with m times the number of columns compared to the original array:
The number of levels m for a plus vector or operator usually is taken from its context.
If the number of levels is not clear, the value is indicated in braces after the plus (e.g. h+{3}).
When c<m, the plus vectors may be truncated to c elements.
This case is indicated by {c/m} or just {c/} after the plus (e.g. h+{2/6} when m=6).
For m=pa, in which p=prime and a>1, the plus vectors are defined in terms of the pa-1 plus vectors.
Thus, plus vectors for m=pa can be found recursively from those of p.
An R function associates
each of the m levels
with a row in an m-by-a level representation array.
The R function is given by
Here R(0+{p}) is defined to be 0+{p}.
So for m=9, p=3, and a=2,
and
The addition table for m=pa is constructed by modulo p addition of elements from the level representation array.
For each table element in the jth row, there is a corresponding row J in the level representation array,
with values J0, ..., Ja-1.
For each table element in the kth column, there is a corresponding row K in the level representation array,
with values K0, ..., Ka-1.
The j,k table element is found by vector addition of the two level representation rows (mod p), and then finding the position of the row
with the resulting sum J0+K0, ... , Ja-1+Ka-1.
The j,k table element is
Here R(j) gives the jth row of the level representation array, and
R-1 is defined as the function which gives the position
of each row of the level representation array.
For example, for m=9, j=4, and k=5, the rows to add are 1 2 and 2 0. The resulting row is 0 2 which is represented
by the level 6. So the 4+5 element in the addition table is 6.
The complete addition table for this example is
Now define the m vectors k+ given by the table columns.
In this example, they are
Similarly, for m=27, p=3, and a=3,
R(0+{27})=(0.{9} R(0+{9}))+{3} and
The k+ vectors for m=27 are
As before the unary plus operator acts on an array to replace each element with its corresponding plus vector.
When m>1, and is divisible by b>1 distinct primes,
m can be expressed as a product of b primaries,
which contain the prime factors of m raised to the appropriate powers:
m=p0a0
p1a1 ...
pb-1ab-1.
In this case, the plus vectors are defined in terms of the plus vectors of the b primaries.
An R function associates
each of the m levels
with a row in an m-by-b level representation array.
The R function is given by
Each column of the level representation array consists of repetitions of the zero plus vectors of one of the primaries.
The number of repetitions is chosen to form a total of m rows.
So for m=12, b=2, p0=2, a0=2, p1=3, and a1=1.
The addition table for m is constructed by addition of elements from the level representation array using the addition tables
as defined above for the corresponding primaries.
For each table element in the jth row, there is a corresponding row J in the level representation array,
with values J0, ..., Jb-1.
For each table element in the kth column, there is a corresponding row K in the level representation array,
with values K0, ..., Kb-1.
The j,k table element is found by addition of the corresponding level representation row elements,
using the addition table for the primary of each column,
and then finding the position of the row
with the resulting sum J0+K0, ... , Jb-1+Kb-1.
The j,k table element is
R-1(J+Kaddition tables).
For example, for m=12, j=4, and k=5, the rows to add are 0 1 and 1 2,
using the addition tables for p0a0 = 22 = 4
and p1a1 = 31 = 3
respectively.
The resulting row is 1 0 which is represented
by the level 9. So the 4+5 element in the addition table is 9.
The complete addition table for this example is
Now define the m vectors k+ given by the table columns.
In this example, they are
As before the unary plus operator acts on an array to replace each element with its corresponding plus vector.
Each of the addition tables of the previous section defines the addition
operation for a group of order m.
The sum of j+k is given by the table element in the jth row
and the kth column.
0 is the identity element, and inverses are identified by row-column pairs
whose sum is 0.
The plus vectors associated with each table,
and their composite vector operation, also form a group of order m.
Each of these vector groups is isomorphic to the corresponding
integer addition group of order m.
In the following definition
vectors are described as functions of their positions or subscripts.
That is, for a vector A of order m,
the element in the jth row is given by
Similarly, all the elements of A can be expressed as
The composite vector operation is the binary operation
of one vector on another.
It is defined1 by
The elements of the A * B vector are those of the B vector arranged according to the values of the A vector elements.
The jth element of A * B is found by using the jth element of A as the position of B.
The resulting value is the jth element of A * B.
For example, if A = 4+{12} and B = 5+{12}, then A * B = 9+{12}, as follows.
The plus vectors form abelian groups in that
However generally vectors will not commute in the composite vector operation:
A more general definition of the composite vector operation will be needed below.
Consider two arrays of vectors A and B with r rows and c columns.
That is, the element of A in the ith row and the kth column
Aik is a vector.
Similarly the element of B in the ith row and the kth column
Bik is a vector.
For such arrays
the composite vector operation A * B is defined to be the r-by-c array of vectors C
whose elements are given by
for all rows i and columns k.
The composite vector operation is also called the vector product here.
Consider an m-by-c array of vectors A which forms an orthogonal array of strength1 l=2
and index one2.
That is, each pair of distinct columns k and k' contains each pair of levels h and h' once.
(Here, h and h' may be equal; k and k' cannot be.)
Suppose each vector Aik is of order m and contains each of the m levels once.
Thus, each vector can be expressed as a bijective function of its position
and there is an inverse function which gives the position for each of the levels
Consider a pair of distinct columns k and k'.
Each is composed of m vectors of order m.
The vector elements with position j in the ith row of vectors are Aik(j) = h and
Aik'(j) = h'.
The pair of levels h and h' can appear only once, in this ith row of vectors.
Consider also a pair of vectors in the same columns k and k', but in a different row of vectors i'.
The vectors are Ai'k and Ai'k'
as illustrated below.
Select the position j' such that
Since the pair of levels h and h' occur in k and k' in the ith row of vectors
and that pair of levels cannot occur more than once,
the corresponding elements in column k must be different:
And since
substitution yields
Application of Ai'k-1 gives
and the definition of the composite vector operation yields
This is the criterion to be used to find orthogonal arrays of vectors,
for all distinct i and i', and all distinct k and k'.
For a given set of vectors, say h+, h=0, ... , m-1,
a table of m2 products
h+ * h'+-1 can be computed
for reference.
Then the search can be done over an m-by-c array of vectors, which is faster
than a more general search over an m2-by-c array of levels.
To narrow its scope and thus improve its speed,
the orthogonal array search will require found arrays to be in standard form.
A strength l=2 array of plus vectors is in standard form when
Requiring these conditions poses no loss of generality due to well known properties of orthogonal arrays1.
To illustrate this point consider an orthogonal array of plus vectors Aik in some other, arbitrary form.
The following four transformations can be applied to the array to produce an orthogonal array in standard form.
Conversely, an orthogonal array in standard form can lead to many other forms by similar transformations in reverse.
(Here the ·{c/m} notation means the Ai0-1 vector is to be repeated over c columns,
because c may be less than m.)
By definition, the effect of applying Ai0-1 to form the vector product is the rearrangement of the rows of levels
within the ith row of vectors.
This transformation is a permutation of rows, which results in an orthogonal array with the same parameters -- l, m, c, and r.
For an array with 0.+ as its 0th column,
so
Thus the m vectors in the 1st column are all different and must include all plus vectors from the set under consideration.
Now it is possible to rearrange of the rows of vectors so that the 1st column contains the i+ vectors in ascending order.
This transformation is a permutation of rows, which results in an orthogonal array with the same parameters.
By definition, the effect of taking the vector product of each plus vector in the column with A0k-1 is a remapping of levels
within the kth column.
Specifically, the level h of each column vector element is mapped to the level of the element of A0k-1 with position h.
Consequently, this transformation is a permutation of levels of a column, which results in an orthogonal array with the same parameters.
For an array with 0·+ as its 0th row of vectors,
so
Thus the c vectors in the 1st row are all different.
Now it is possible to rearrange the columns so that the 1st row of vectors contains the plus vectors in ascending order.
This transformation is a permutation of columns, which results in an orthogonal array with the same parameters.
When c=m, the orthogonal array of plus vectors can be expressed as an m-by-m array to which the plus operator is applied.
If the orthogonal array is in standard form,
the m-by-m array can be interpreted as a multiplication table.
Its 0th row and 0th column consist of the element 0,
indicating all multiplication products of 0 equal 0.
Its 1st row and 1st column consist of the m elements in ascending order,
indicating 1 is the multiplicative identity element.
For example, when l=2 and c=m=5, the orthogonal array of plus vectors is
The corresponding multiplication table is contained in the parentheses.
In this example, the table represents multiplication modulo 5.
When m=p is a prime, or
m=pa is a prime power, then c=m.
In these cases corresponding addition and multiplication tables
may define rings or fields for the elements h=0, 1, ..., m-1.
Similarly the tables may define isomorphic rings or fields for the plus vectors
h+=0+, 1+, ..., (m-1)+ .
Here the addition operation is the composite vector operation,
and the multiplication operation is given by the multiplication table.
List of Updates - Current browser versions, Netscape 6 or IE 5.50,
or later are recommended. Earlier versions
(Netscape 4.7, IE 5.00) don't always get the
formatting just right. May 17, 2002 - The total number of noncovering sets
wel,m is expressed as a product of a power of m and a
Gaussian binomial coefficient. November 10, 2002 -
The covering array search algorithm for strength l>2 and rows of vectors z>1
is improved for better efficiency.
A new section describes the search algorithm. November 10, 2002 -
The improved search algorithm yields the following
results for strength l=3.
The covering arrays have zm3-(z-1)m rows for positive integers z.
For z=2 rows of vectors, n=9 columns are found
for number of levels m=3;
16 columns are found for m=4;
24 columns for m=5;
31 columns for m=7;
40 columns for m=8.
For z=3 rows of vectors, n=20 columns are found
for number of levels m=3;
28 columns are found for m=4.
The numbers of columns found are consistent with the conjecture
that arrays of this form can have mz columns. November 10, 2002 - Additional arrays of permutation vectors,
for m=7,
m=8, and
m=9, are included in an appendix. November 10, 2002 - The pound sign
#
in a section heading indicates the material is not required to understand
later sections,
and may be skipped on a first reading.
The pound sign provides a link to the next section not so marked. January 4, 2003 -
Additional strength l=3
results are included.
For z=2 rows of vectors, n=39 columns are found
for number of levels m=9. March 22, 2003 -
Additional strength l=3
results are included.
For z=1 row of vectors, n=10 columns are found
for number of levels m=8;
10 columns are found for m=9;
12 columns are found for m=11;
14 columns are found for m=13.
For z=2 rows of vectors, n=44 columns are found
for number of levels m=11;
39 columns are found for m=13. March 22, 2003 -
Numbers of covering arrays found for l=3 and for selected values of m and z are
tabulated and described in a revised
section.
(For z=1 these results are for orthogonal arrays of index one.) June 8, 2003 -
The improved search algorithm described earlier is used to find strength l=4 arrays with w=3.
For z=2 rows of vectors, n=8 columns are found
for number of levels m=2;
9 columns are found for m=3. August 15, 2003 -
Additional strength l=4
results are included.
For z=1 row of vectors, n=6 columns are found
for number of levels m=5.
For z=2 rows of vectors, n=10 columns are found
for number of levels m=3;
9 columns are found for m=4;
11 columns are found for m=5.
For z=3 rows of vectors, n=8 columns are found
for number of levels m=2;
16 columns are found for m=3.
For z=4 rows of vectors, n=11 columns are found
for number of levels m=2.
A new section
gives numbers of wFwP arrays found for l=4. August 15, 2003 -
Two new sections summarize results for m=2 levels with strengths
l=3 and
l=4.
Another new section
gives numbers of w,zFwP(') arrays found for m=2. August 15, 2003 -
The section mark notation §
is introduced to represent the operation of removing redundant rows via the cats program.
This use (typically for m=2) is to distinguish clearly from the removal of the (z-1)m
duplicate rows indicated by the apostrophe in w,zFwP'.
For example, for m=2 and l=4, the operation of the cats program on the lowest covering array
3,3F3P§ yields the same array
as the lowest
3,2F3P' array
(which illustrates the high redundancy in the
3,3F3P' array).
June 8, 2004 - Highlights of this site have been collected in a paper
submitted to the
Journal of Combinatorial Designs. June 8, 2004 - Some of the construction methods described here
are used in a covering test case generator service available from
Testcover.com. June 8, 2004 - Question for Site Visitors:
The
coveringarray.org domain has been reserved as a possible site for a
public domain covering array database.
The idea is to collect "interesting" arrays, e.g. which represent various construction methods,
or which may be of particularly small size, etc.
To gauge whether there is sufficient interest to justify the project,
would you please
respond by email as to whether and how such a data base would be of use to you?
And if you are a researcher, would you be willing to contribute arrays to the database? Table of Contents
Table of Symbols
Table of Covering Arrays
Definitions
Dot Vectors
h. :
0. 1. 2.
0
0
0
1
1
1
2
2
2
(0 1 2). =
0
0
0
1
1
1
2
2
2
(0 1 2)· = 0 0 0 1 1 1 2 2 2 Plus Vectors
0
1
:
m-1
Plus Vectors for m=prime
k: 0
1 2 j:
0
1
2
0
1
2
1
2
0
2
0
1
k+:
0+ 1+ 2+
0
1
2
1
2
0
2
0
1
(0 1 2)+ =
0
1
2
1
2
0
2
0
1
(0 1 2)+ = 0 1 2 1 2 0 2 0 1 Plus Vectors for m=prime power
R(
0
1
2
3
4
5
6
7
8
) =
0
1
2
0
1
2
0
1
2
0
1
2
1
2
0
2
0
1
k: 0
1 2
3 4 5
6 7 8 j:
0
1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
8
1
2
0
4
5
3
7
8
6
2
0
1
5
3
4
8
6
7
3
4
5
6
7
8
0
1
2
4
5
3
7
8
6
1
2
0
5
3
4
8
6
7
2
0
1
6
7
8
0
1
2
3
4
5
7
8
6
1
2
0
4
5
3
8
6
7
2
0
1
5
3
4
k+:
0+ 1+ 2+
3+ 4+ 5+
6+ 7+ 8+
0
1
2
3
4
5
6
7
8
1
2
0
4
5
3
7
8
6
2
0
1
5
3
4
8
6
7
3
4
5
6
7
8
0
1
2
4
5
3
7
8
6
1
2
0
5
3
4
8
6
7
2
0
1
6
7
8
0
1
2
3
4
5
7
8
6
1
2
0
4
5
3
8
6
7
2
0
1
5
3
4
R(
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
) =
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
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
0
1
2
1
2
0
2
0
1
1
2
0
2
0
1
0
1
2
2
0
1
0
1
2
1
2
0
k+:
0+ 1+ 2+
3+ 4+ 5+
6+ 7+ 8+
9+ 10+ 11+
12+ 13+ 14+
15+ 16+ 17+
18+ 19+ 20+
21+ 22+ 23+
24+ 25+ 26+
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
1
2
0
4
5
3
7
8
6
10
11
9
13
14
12
16
17
15
19
20
18
22
23
21
25
26
24
2
0
1
5
3
4
8
6
7
11
9
10
14
12
13
17
15
16
20
18
19
23
21
22
26
24
25
3
4
5
6
7
8
0
1
2
12
13
14
15
16
17
9
10
11
21
22
23
24
25
26
18
19
20
4
5
3
7
8
6
1
2
0
13
14
12
16
17
15
10
11
9
22
23
21
25
26
24
19
20
18
5
3
4
8
6
7
2
0
1
14
12
13
17
15
16
11
9
10
23
21
22
26
24
25
20
18
19
6
7
8
0
1
2
3
4
5
15
16
17
9
10
11
12
13
14
24
25
26
18
19
20
21
22
23
7
8
6
1
2
0
4
5
3
16
17
15
10
11
9
13
14
12
25
26
24
19
20
18
22
23
21
8
6
7
2
0
1
5
3
4
17
15
16
11
9
10
14
12
13
26
24
25
20
18
19
23
21
22
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
0
1
2
3
4
5
6
7
8
10
11
9
13
14
12
16
17
15
19
20
18
22
23
21
25
26
24
1
2
0
4
5
3
7
8
6
11
9
10
14
12
13
17
15
16
20
18
19
23
21
22
26
24
25
2
0
1
5
3
4
8
6
7
12
13
14
15
16
17
9
10
11
21
22
23
24
25
26
18
19
20
3
4
5
6
7
8
0
1
2
13
14
12
16
17
15
10
11
9
22
23
21
25
26
24
19
20
18
4
5
3
7
8
6
1
2
0
14
12
13
17
15
16
11
9
10
23
21
22
26
24
25
20
18
19
5
3
4
8
6
7
2
0
1
15
16
17
9
10
11
12
13
14
24
25
26
18
19
20
21
22
23
6
7
8
0
1
2
3
4
5
16
17
15
10
11
9
13
14
12
25
26
24
19
20
18
22
23
21
7
8
6
1
2
0
4
5
3
17
15
16
11
9
10
14
12
13
26
24
25
20
18
19
23
21
22
8
6
7
2
0
1
5
3
4
18
19
20
21
22
23
24
25
26
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
19
20
18
22
23
21
25
26
24
1
2
0
4
5
3
7
8
6
10
11
9
13
14
12
16
17
15
20
18
19
23
21
22
26
24
25
2
0
1
5
3
4
8
6
7
11
9
10
14
12
13
17
15
16
21
22
23
24
25
26
18
19
20
3
4
5
6
7
8
0
1
2
12
13
14
15
16
17
9
10
11
22
23
21
25
26
24
19
20
18
4
5
3
7
8
6
1
2
0
13
14
12
16
17
15
10
11
9
23
21
22
26
24
25
20
18
19
5
3
4
8
6
7
2
0
1
14
12
13
17
15
16
11
9
10
24
25
26
18
19
20
21
22
23
6
7
8
0
1
2
3
4
5
15
16
17
9
10
11
12
13
14
25
26
24
19
20
18
22
23
21
7
8
6
1
2
0
4
5
3
16
17
15
10
11
9
13
14
12
26
24
25
20
18
19
23
21
22
8
6
7
2
0
1
5
3
4
17
15
16
11
9
10
14
12
13
Plus Vectors for m=prime power product
R(
0
1
2
3
4
5
6
7
8
9
10
11
) =
R(0+{12}) = 0.{3}+{4} 0.{4}+{3} =
0+{4}
0+{4}
0+{4}
0+{3}
0+{3}
0+{3}
0+{3}
=
0
1
2
3
0
1
2
3
0
1
2
3
0
1
2
0
1
2
0
1
2
0
1
2
k0: 0
1 2
3 j0:
0
1
2
3
0
1
2
3
1
0
3
2
2
3
0
1
3
2
1
0
k1: 0
1 2 j1:
0
1
2
0
1
2
1
2
0
2
0
1
k: 0
1 2
3 4 5
6 7 8
9 10 11 j:
0
1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10
11
1
8
3
10
5
0
7
2
9
4
11
6
2
3
4
5
6
7
8
9
10
11
0
1
3
10
5
0
7
2
9
4
11
6
1
8
4
5
6
7
8
9
10
11
0
1
2
3
5
0
7
2
9
4
11
6
1
8
3
10
6
7
8
9
10
11
0
1
2
3
4
5
7
2
9
4
11
6
1
8
3
10
5
0
8
9
10
11
0
1
2
3
4
5
6
7
9
4
11
6
1
8
3
10
5
0
7
2
10
11
0
1
2
3
4
5
6
7
8
9
11
6
1
8
3
10
5
0
7
2
9
4
k+:
0+ 1+ 2+
3+ 4+ 5+
6+ 7+ 8+
9+ 10+ 11+
0
1
2
3
4
5
6
7
8
9
10
11
1
8
3
10
5
0
7
2
9
4
11
6
2
3
4
5
6
7
8
9
10
11
0
1
3
10
5
0
7
2
9
4
11
6
1
8
4
5
6
7
8
9
10
11
0
1
2
3
5
0
7
2
9
4
11
6
1
8
3
10
6
7
8
9
10
11
0
1
2
3
4
5
7
2
9
4
11
6
1
8
3
10
5
0
8
9
10
11
0
1
2
3
4
5
6
7
9
4
11
6
1
8
3
10
5
0
7
2
10
11
0
1
2
3
4
5
6
7
8
9
11
6
1
8
3
10
5
0
7
2
9
4
Composite Vector Operators
A = A(0+) =
A(
0
1
:
m-1
) =
A(0)
A(1)
:
A(m-1)
=
A0
A1
:
Am-1
A * B = (4+ * 5+)(0+) = 5+(4+(
0
1
2
3
4
5
6
7
8
9
10
11
)) =
5+(
4
5
6
7
8
9
10
11
0
1
2
3
) =
9
4
11
6
1
8
3
10
5
0
7
2
= 9+
Preparation
Orthogonal Array Search Criterion
: : ... Aik(j) ... Aik'(j) ... : : ... Ai'k(j') ... Ai'k'(j') ... : :
Standard Form
Ai0-1 ·{c/m} * (Ai0 Ai1 ... Ai c-1) =
Ai0-1*Ai0 Ai0-1*Ai1 ... Ai0-1*Ai c-1
A1k * A0k-1
:
Am-1 k * A0k-1
A = (
0
0
0
0
0
0
1
2
3
4
0
2
4
1
3
0
3
1
4
2
0
4
3
2
1
)+
To narrow its scope and improve its speed further, the orthogonal array search will look for arrays in diagonal form. A strength l=2 orthogonal array of plus vectors B is in diagonal form when it can be written as a vector product of a template array T and a first column vector fuv as follows.
in which T is an m-by-c array, and fuv is a vector with m rows. (The u and v vectors are used to label the first column vectors as described in a later section.) For m>1, the template array elements are defined as follows.
Tik = 0 | if i=0 or k=0, and if m>1. |
T11 = 1 | if i=1 and k=1, and if m=2. |
(Tik-1)mod m = (i-1 + k-1)mod m-1 | if i>0 and k>0, and if m>2. |
The fuv vector contains a permutation of the m levels with 0 and 1 in the 0th and 1st positions respectively. For example, for m=5 and c=5, the template array is
T = |
0 0 0 0 0 |
0 1 2 3 4 |
0 2 3 4 1 |
0 3 4 1 2 |
0 4 1 2 3 |
f00 = |
0 1 2 4 3 |
Their product is
T * f00· = |
0 0 0 0 0 |
0 1 2 4 3 |
0 2 4 3 1 |
0 4 3 1 2 |
0 3 1 2 4 |
(Note the first column of this array is f00, which leads to the name first column vector for an orthogonal array in diagonal form.) Finally, the application of the plus operator gives the full array:
B = |
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 |
0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 4 0 1 2 3 3 4 0 1 2 |
0 1 2 3 4 2 3 4 0 1 4 0 1 2 3 3 4 0 1 2 1 2 3 4 0 |
0 1 2 3 4 4 0 1 2 3 3 4 0 1 2 1 2 3 4 0 2 3 4 0 1 |
0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 2 3 4 0 1 4 0 1 2 3 |
Because an orthogonal array in diagonal form has 0+ vectors in its 0th row of vectors and in its 0th column, it already satisfies conditions 1 and 3 for standard form (above). Thus, only transformations of type 2 and 4 are needed to change the orthogonal array from diagonal form to standard form. It is convenient to express the array in standard form in terms of the first column vector, as follows.
Aik = 0+ | if i=0 or k=0, and if m>1. |
A11 = 1+ | if i=1 and k=1, and if m=2. |
Aik = fuv({fuv-1(i) - 1 + fuv-1(k) - 1}mod m-1 + 1mod m)+ | if i>0 and k>0, and if m>2. |
In this example
A24 | = f00({f00-1(2) - 1 + f00-1(4) - 1}mod 4 + 1mod 5)+ |
= f00({2-1 + 3-1}mod 4 + 1mod 5)+ | |
= f00(3+1mod 5)+ | |
= f00(4)+ | |
= 3+ |
The entire orthogonal array in standard form is
A = ( |
0 0 0 0 0 |
0 1 2 3 4 |
0 2 4 1 3 |
0 3 1 4 2 |
0 4 3 2 1 | )+ = |
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 |
0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 |
0 1 2 3 4 2 3 4 0 1 4 0 1 2 3 1 2 3 4 0 3 4 0 1 2 |
0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1 |
0 1 2 3 4 4 0 1 2 3 3 4 0 1 2 2 3 4 0 1 1 2 3 4 0 |
In general the mapping from orthogonal arrays of plus vectors in diagonal form to those in standard form is not injective. This is because there can be multiple diagonal form arrays mapped to the same standard form array. In particular, for m=5 and c=5, the first column vector
f10 = |
0 1 3 4 2 |
maps to the same standard form array as f00 does.
Generally the mapping from an orthogonal array of plus vectors in diagonal form to one in standard form is not surjective either, because there are orthogonal arrays of vectors in standard form1 which do not have corresponding diagonal forms. (They are not found in a search for arrays in diagonal form.)
Requiring the orthogonal array search to find arrays of plus vectors in diagonal form is neither necessary nor sufficient. It is not a necessary condition because there are other orthogonal arrays which are not found by the search for arrays in diagonal form. Search results include orthogonal arrays based on Galois fields however. Finding an array in diagonal form is not sufficient because there are diagonal arrays of plus vectors which do not satisfy the orthogonal array search criterion. For example, for m=5 and c=5, the identity vector
0+ = |
0 1 2 3 4 |
yields a nonorthogonal array, though its product with the template array is diagonal. Thus 0+ is not a first column vector in this example.
The advantage of searching for orthogonal arrays in diagonal form is the reduction in the scope of the search, leading to shorter execution times for large m. The search is reduced to finding first column vectors, for which there may be (m-2)! permutations of levels. In practice, the number of cases to test is less than (m-2)! because the first column vector can be built incrementally. After level 0 is assigned to the 0th row and column, and after 1 is assigned to the first diagonal position, each candidate level can be checked in a partial array to see if it meets the orthogonal array search criterion. If it does, a candidate level is chosen for the next diagonal. If it does not, the search considers the next candidate level for the current diagonal, without consideration of additional diagonals containing this nonorthogonal, partial permutation.
0 | 0 0 0 0 | 0 0 0 0 | 0 | 0 | ||||
T = |
0 0 0 0 |
1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 |
5 8 7 6 6 5 8 7 7 6 5 8 8 7 6 5 | with f = |
1 3 2 6 | or |
1 3 2 6 |
|
0 0 0 0 |
5 8 7 6 6 5 8 7 7 6 5 8 8 7 6 5 |
3 4 1 2 4 1 2 3 1 2 3 4 2 3 4 1 |
4 7 8 5 |
8 7 4 5 |
The remaining 12 orthogonal arrays from the search yield multiplication tables which are not associative.
The interpretation of the standard form orthogonal array of plus vectors as a multiplication table, and its expression in terms of the first column vector, lead to formulas for products of the levels. The multiplication products expressed in terms of the first column vectors are as follows:
h x h' = 0 | if h=0 or h'=0, and if m>1. |
h x h' = 1 | if h=1 and h'=1, and if m=2. |
h x h' = fuv({fuv-1(h) - 1 + fuv-1(h') - 1}mod m-1 + 1mod m) | if h>0 and h'>0, and if m>2. |
In particular, for m>1 the powers of h are given by
ha = 0 | if h=0. |
ha = 1 | if h=1. |
ha = fuv(a{fuv-1(h) - 1}mod m-1 + 1mod m) | if h>1. |
In the m=5 example,
43 = f00(3{f00-1(4) - 1}mod 4 + 1mod 5) = f00(3{3 - 1}mod 4 + 1mod 5) = f00(2 + 1mod 5) = f00(3) = 4 |
The powers of h formula for h>1 implies which positions in a first column vector can contain primitive elements. (The powers of a primitive element generate all m-1 nonzero levels.) If q is a totitive of m-1, then fuv(q+1) is a primitive element. (q is a totitive of m-1 if it is a relative prime of m-1 and less than m-1.)
When h=fuv(q+1),
If q equals a totitive of m-1,
To see this, divide aq by m-1 as follows,
in which y and z are integers. aqmod m-1 = z, the remainder. A similar expression for a different power is:
Now consider when z'=z.
so
Since the right side of the equation is a multiple of m-1, and since q and m-1 are relative primes, a'-a must be a multiple of m-1. Since the values of a=1, 2, ..., m-1 differ by less than m-1, aqmod m-1 = z takes on all m-1 values 0, 1, ..., m-2 without repeating. Now in
the argument of fuv must take on all values 1, 2, ..., m-1, so ha generates all nonzero levels.
In the m=5 example, q=1 or 3 (relative primes of 4), so the first column vectors can have primitive elements only with positions 2 or 4. The primitive elements are 2 and 3.
Note that for any m>2, q may be 1 or m-2. Therefore the first column vector positions 2 and m-1 must contain primitive elements.
Generally the powers of h formula implies which positions in a first column vector contain elements of a particular order. For an element h>1 with order a,
Application of fuv-1 and subtraction yield
so
for some integer y. Solving for h yields
in which 0<y<a, so the position of fuv is greater than 1 and less than m. Also, a must divide y(m-1) so that the position of fuv is an integer. Now y must be a totitive of a (i.e. y/a must be irreducible). To see this, suppose there is a reduced fraction
in which y'<y and a'<a. Replacement of y/a with y'/a' gives
Then the powers of h formula indicates a' is the order of h:
which contradicts the statement that a is the order of h. Thus, since y is a totitive of a, a cannot divide y, and a must divide m-1.
The order of the first column vector element in each position greater than 1 is determined as follows.
For example, for m=16, the orders and corresponding positions are as follows.
order | totitive | position |
---|---|---|
a | y | y(m-1)/a + 1 |
3 | 1 | 6 |
2 | 11 | |
5 | 1 | 4 |
2 | 7 | |
3 | 10 | |
4 | 13 | |
15 | 1 | 2 |
2 | 3 | |
4 | 5 | |
7 | 8 | |
8 | 9 | |
11 | 12 | |
13 | 14 | |
14 | 15 |
The elements of order a=m-1=15 are the primitive elements in this example.
The association of an element's order with its position in the first column vector implies which positions are allowed for the element when there are more than one first column vectors with the same multiplication table. Consider a multiplication table when m=16. The orders of all the nonzero elements are determined by the table, so the orders cannot vary among the first column vectors associated with the table. Thus, the element occurring in position 6 has order 3, and can occur only in position 6 or position 11 of any first column vector associated with this table. Similarly, elements in positions 4, 7, 10, and 13 have order 5 and can occur only in those positions, etc.
A further consequence of the association of an element's order with its position is that there is only one position for order a=2 elements, (m-1)/2+1. When m is odd, m-1 is even, so a can be 2. y must be 1 in this case, so the position for the only order 2 element is (m-1)/2+1. In the cases with m=p a prime, m>2 is odd, and the multiplication table gives modulo m multiplication. In these cases, the element in the (m-1)/2+1 position is m-1, and (m-1)x(m-1)=1.
The m cross vectors kx are defined to be the columns of the multiplication table derived from a first column vector. The vectors are defined for all columns k=0, 1, ..., m-1, disregarding the possibility that only c<m columns may form an orthogonal array. Thus,
for i=0, 1, ..., m-1, in which
Aik = 0 | if i=0 or k=0, and if m>1. |
A11 = 1 | if i=1 and k=1, and if m=2. |
Aik = fuv({fuv-1(i) - 1 + fuv-1(k) - 1}mod m-1 + 1mod m) | if i>0 and k>0, and if m>2. |
In the example c=m=3, the cross vectors are
kx: | 0x | 1x | 2x |
0 0 0 |
0 1 2 |
0 2 1 |
The unary cross operator acts on an array to replace each element with its corresponding cross vector. The result is an array with m times the number of rows compared to the original array. Thus,
(0 1 2)x | = |
0 0 0 |
0 1 2 |
0 2 1 |
Similarly, the raised cross operator replaces each element of an array with its corresponding cross vector transposed. The result is an array with m times the number of columns compared to the original array:
(0 1 2)x = 0 0 0 0 1 2 0 2 1 |
The number of levels m for a cross vector or operator usually is taken from its context. If the number of levels is not clear, the value is indicated in braces after the cross (e.g. hx{3} when m=3). When c<m, the cross vectors may be truncated to c elements. This case is indicated by {c/m} or just {c/} after the cross (e.g. hx{2/6} when m=6).
Note that the addition and multiplication tables given here specify abelian groups for the indicated elements. The addition group is of order m (elements h=0, 1, ..., m-1); the multiplication group is of order m-1 (elements h=1, ..., m-1). When m is a prime or a prime power, the tables define finite (Galois) fields of order m. Other values of m do not yield fields because their multiplication operations are not distributive over addition.
Also note that the plus vectors form isomorphic groups for addition and multiplication. Thus
h+ + h'+ = (h + h')+ = h+ * h'+ and |
h+ x h'+ = (h x h')+ |
If m is a prime or a prime power, the plus vectors form an isomorphic field of order m.
The cross vectors also form isomorphic groups for addition and multiplication. Thus
hx + h'x = (h + h')x and | |
hx x h'x = (h x h')x = hx * h'x |
If m is a prime or a prime power, the cross vectors form an isomorphic field of order m. Moreover, if m is a prime or a prime power, the cross vector addition operation is vector addition according to the addition table. That is, the cross vector components are added as follows
for j=0, 1, ..., m-1.
The isomorphisms of the plus and cross vectors to the multiplication groups imply the vectors have the multiplication properties of the multiplication tables. Thus the multiplication properties described in the Products, Powers, and Primitive Elements section apply to the plus vectors and cross vectors as well as to the elements that comprise them. (And these properties do not depend on m being a prime or on m being a prime power.)
The orthogonal array of plus vectors of strength l=2 and index one now can be expressed as
in terms of the plus and cross operators, when c=2 or c=m. Inclusion of the solutions at infinity1 yields an additional column
expressed in terms of the plus and dot operators.
For c=m=3, the expression is evaluated as follows.
0+. 0+x{c/}+ = ( |
0 1 2 |
). ( |
0 1 2 |
)x+ = ( |
0 1 2 |
). ( |
0 0 0 |
0 1 2 |
0 2 1 |
)+ = |
0 0 0 1 1 1 2 2 2 |
0 1 2 0 1 2 0 1 2 |
0 1 2 1 2 0 2 0 1 |
0 1 2 2 0 1 1 2 0 |
When c=2 or c=m, the standard form orthogonal array expressions above can be used, because each vector in the first row is k+, k=0, 1, ..., c-1, with no gaps in the sequence. When 2<c<m, some values of k<c may not follow from the first column vector. For example, when m=12 and c=4, there is a first column vector
fuv = |
0 1 2 4 10 9 8 11 3 6 7 5 | labeled by the vectors u = 0 and v = |
0 1 |
fuv yields the orthogonal array
( |
0 0 0 0 0 0 0 0 0 0 0 0 |
0 1 2 4 10 9 8 11 3 6 7 5 |
0 2 4 10 9 8 11 3 6 7 5 1 |
0 4 10 9 8 11 3 6 7 5 1 2 | )+ | in diagonal form, and | ( |
0 0 0 0 0 0 0 0 0 0 0 0 |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 2 4 6 10 1 7 5 11 8 9 3 |
0 4 10 7 9 2 5 1 3 11 8 6 | )+ | in standard form. |
In this case the vectors in the first row are k+, k=0, 1, 2, 4.
Generally each orthogonal array of plus vectors of strength l=2 and index one can be expressed as
in terms of a first row vector
which is a first column vector transposed, truncated to c columns, and sorted in ascending order. In this example guv = 0 1 2 4 .
Examples of first column vectors and first row vectors for the values of m between 2 and 23 are given below.
It is also possible to remove the gaps in the k+ sequence k=0, 1, ..., c-1 with alternate definitions of the plus vectors. An appropriate selection of level representations yields a first row vector
so the earlier l=2 orthogonal array expressions
can be used.
In the m=12 example from the previous section, consider the alternate level representation array R' which has the levels 3 and 4 interchanged compared to the original definition of R.
R'(0+) = R( |
0 1 2 4 3 5 6 7 8 9 10 11 | ) = |
0 1 2 0 3 1 2 3 0 1 2 3 |
0 1 2 1 0 2 0 1 2 0 1 2 |
The alternate level representation array R' leads to an alternate addition table and alternate plus vectors and plus operators, as follows.
0+ | 1+ | 2+ | 3+ | 4+ | 5+ | 6+ | 7+ | 8+ | 9+ | 10+ | 11+ | ||
+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7 8 9 10 11 |
0 1 2 3 4 5 6 7 8 9 10 11 |
1 8 4 5 10 0 7 2 9 3 11 6 |
2 4 3 6 5 7 8 9 10 11 0 1 |
3 5 6 8 7 9 10 11 0 1 2 4 |
4 10 5 7 0 2 9 3 11 6 1 8 |
5 0 7 9 2 3 11 6 1 8 4 10 |
6 7 8 10 9 11 0 1 2 4 3 5 |
7 2 9 11 3 6 1 8 4 10 5 0 |
8 9 10 0 11 1 2 4 3 5 6 7 |
9 3 11 1 6 8 4 10 5 0 7 2 |
10 11 0 2 1 4 3 5 6 7 8 9 |
11 6 1 4 8 10 5 0 7 2 9 3 |
The corresponding first column vector f'uv becomes
f'uv = |
0 1 2 3 10 9 8 11 4 6 7 5 | and f'uv yields the orthogonal array |
( |
0 0 0 0 0 0 0 0 0 0 0 0 |
0 1 2 3 10 9 8 11 4 6 7 5 |
0 2 3 10 9 8 11 4 6 7 5 1 |
0 3 10 9 8 11 4 6 7 5 1 2 | )+ | in diagonal form, and | ( |
0 0 0 0 0 0 0 0 0 0 0 0 |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 2 3 10 6 1 7 5 11 8 9 4 |
0 3 10 9 7 2 5 1 4 11 8 6 | )+ | in standard form. |
Thus the vectors in the first row are k+, k=0, 1, 2, 3, and the gap is eliminated.
The numbers of first column vectors and standard form arrays for values of m up to 23 are tabulated below.
m | c | Number of First Column Vectors | Number of Standard Form Arrays |
---|---|---|---|
2 | 2 | 1 | 1 |
3 | 3 | 1 | 1 |
4 | 4 | 2 | 1 |
5 | 5 | 2 | 1 |
6 | 2 | 24 | 1 |
7 | 7 | 2 | 1 |
8 | 8 | 48 | 8 |
9 | 9 | 12 | 3 |
10 | 2 | 8! | 1 |
11 | 11 | 4 | 1 |
12 | 4 | 24 | 24 |
13 | 13 | 4 | 1 |
14 | 2 | 12! | 1 |
15 | 4 | 64 | 64 |
16 | 16 | 2688 | 336 |
17 | 17 | 8 | 1 |
18 | 2 | 16! | 1 |
19 | 19 | 6 | 1 |
20 | 4 | 3744 | 3744 |
21 | 4 | 12372 | 12372 |
22 | 2 | 20! | 1 |
23 | 23 | 10 | 1 |
It is apparent from the table that the number of first column vectors can increase rapidly with m. It is convenient to express the first column vectors for m in terms of one particular first column vector because typically there are mapping operators which can be factored and tabulated concisely. The mapping operators also highlight the relationships among the first column vectors.
For a given value of m, the first column vectors are ordered by assigning decreasing significance to elements with increasing positions. Thus, the element with position 0 has the most significance, and the element with position m-1 has the least. For example, 0. = 0x is the lowest possible vector, and the identity vector 0+ = 1x is the lowest candidate for a first column vector. (Lowest first column vectors and lowest first row vectors for the values of m between 2 and 23 are given below.) Each first column vector for m is expressed in terms of the lowest first column vector, which is f00. Specifically,
in which the first column vector mapping operator
The effect of Muv (operating on the right) is to map the levels of f00 to those of fuv .
For example, for m=9 the two lowest first column vectors are
f00 = |
0 1 3 4 7 2 6 8 5 | and fuv = |
0 1 3 7 8 2 6 5 4 | in which the vectors u = | 1 1 | and v = | 1 |
label the second lowest first column vector. The mapping operator is
Muv = |
0 1 2 3 7 4 6 8 5 | and fuv = f00 * Muv = |
0 1 3 4 7 2 6 8 5 | * |
0 1 2 3 7 4 6 8 5 |
Here each position h of Muv(h) equals a level of f00 and is mapped to a corresponding level of fuv:
The mapping can be tabulated as follows.
Level of f00 h | Level of fuv Muv(h) | |
---|---|---|
0 | => | 0 |
1 | => | 1 |
2 | => | 2 |
3 | => | 3 |
4 | => | 7 |
5 | => | 4 |
6 | => | 6 |
7 | => | 8 |
8 | => | 5 |
Thus Muv is called a level mapping operator because it maps the levels of the vector on its left to a new set of levels.
In the cases considered here, Muv can be factored into two level mapping operators Su and Dv, so that
in which Su maps f00 to first column vectors yielding the same multiplication table, and Dv maps f00 to first column vectors yielding different multiplication tables. In the m=9 example
Su * Dv = |
0 1 2 5 8 3 7 6 4 |
* |
0 1 2 4 5 3 8 6 7 |
= |
0 1 2 3 7 4 6 8 5 |
= Muv |
Here,
yields the same multiplication table as that of f00, and
yields a different multiplication table (since v is not 0, the zero vector).
Generally the first column vectors for m=9 can be expressed in terms of level mapping operators associated with the components of the u and v vectors:
and
so
with the level mapping operators tabulated as follows.
u0: | 0 | 1 | u1: | 0 | 1 | v0: | 0 | 1 | 2 | ||
---|---|---|---|---|---|---|---|---|---|---|---|
Su0: |
0 1 2 3 4 5 6 7 8 |
0 1 2 7 8 6 5 3 4 |
Su1: |
0 1 2 3 4 5 6 7 8 |
0 1 2 6 4 7 3 5 8 |
Dv0: |
0 1 2 3 4 5 6 7 8 |
0 1 2 4 5 3 8 6 7 |
0 1 2 5 3 4 7 8 6 |
The twelve first column vectors are given by evaluating f00 * Muv for all combinations of values for u0, u1 and v0. The first column vectors for m=9 are tabulated in a later section.
The cap operator ^ acts on a vector of order m to yield its vector product with f00 on the left and f00-1 on the right.
The cap operator transforms a level mapping operator (acting on the right) to a position mapping operator which acts on the left:
In the m=9 example with the two lowest first column vectors,
f00 = |
0 1 3 4 7 2 6 8 5 | and fuv = |
0 1 3 7 8 2 6 5 4 | in which the vectors u = | 1 1 | and v = | 1 |
label the second lowest first column vector. The position mapping operator is
^Muv = |
0 1 2 4 7 5 6 8 3 | and fuv = ^Muv * f00 = |
0 1 2 4 7 5 6 8 3 | * |
0 1 3 4 7 2 6 8 5 |
Here the value of ^Muv(i) equals a position of f00 and is mapped to the corresponding position i of fuv(i):
The mapping can be tabulated as follows.
Position of fuv i | Position of f00 ^Muv(i) | |
---|---|---|
0 | <= | 0 |
1 | <= | 1 |
2 | <= | 2 |
3 | <= | 4 |
4 | <= | 7 |
5 | <= | 5 |
6 | <= | 6 |
7 | <= | 8 |
8 | <= | 3 |
Thus ^Muv is called a position mapping operator because it maps the positions of the vector on its right to a new set of positions.
Now when Muv is factored into Su and Dv, ^Muv can be factored also:
In the m=9 example
^Su * ^Dv = |
0 1 8 7 6 5 4 3 2 |
* |
0 1 3 8 6 5 7 4 2 |
= |
0 1 2 4 7 5 6 8 3 |
= ^Muv |
Generally the first column vectors for m=9 can be expressed in terms of position mapping operators associated with the components of the u and v vectors:
with the position mapping operators tabulated as follows.
u0: | 0 | 1 | u1: | 0 | 1 | v0: | 0 | 1 | 2 | ||
---|---|---|---|---|---|---|---|---|---|---|---|
^Su0: |
0 1 2 3 4 5 6 7 8 |
0 1 4 7 2 5 8 3 6 |
^Su1: |
0 1 2 3 4 5 6 7 8 |
0 1 6 3 8 5 2 7 4 |
^Dv0: |
0 1 2 3 4 5 6 7 8 |
0 1 3 8 6 5 7 4 2 |
0 1 8 2 7 5 4 6 3 |
The twelve first column vectors are given by evaluating ^Muv * f00 for all combinations of values for u0, u1 and v0.
In the cases considered here, when m is a prime or a prime power, each of the position mapping operators ^Su, which maps to the same multiplication table, is equal to a difference vector dq:
in which
dq(i) = 0 | if i=0, and if m>1. |
dq(i) = 1 | if i=1, and if m=2. |
dq(i) = (i-1)qmod m-1 + 1mod m | if i>0, and if m>2. |
Here q is a totitive of m-1.
In the m=9 example, q=1, 3, 5, or 7.
Regardless of whether m is a prime or a prime power, the difference vectors form a group with the vector product operator. This group is isomorphic to the group of totitives of m-1 with multiplication modulo m-1.
For m>2 and i>0,
(dq * dq')(i) | = dq'(dq(i)) |
= dq'((i-1)qmod m-1 + 1mod m) | |
= (i-1)qq'mod m-1 + 1mod m | |
= dqq'(i) |
And for i=0,
so
Thus, for example, when m=6, the difference vectors are
d1 | d2 | d3 | d4 |
---|---|---|---|
0 1 2 3 4 5 |
0 1 3 5 2 4 |
0 1 4 2 5 3 |
0 1 5 4 3 2 |
and the table of their vector products is
* | d1 | d2 | d3 | d4 | |
---|---|---|---|---|---|
d1 | d1 | d2 | d3 | d4 | |
d2 | d2 | d4 | d1 | d3 | |
d3 | d3 | d1 | d4 | d2 | |
d4 | d4 | d3 | d2 | d1 |
while for m=9, the difference vectors are
d1 | d3 | d5 | d7 |
---|---|---|---|
0 1 2 3 4 5 6 7 8 |
0 1 4 7 2 5 8 3 6 |
0 1 6 3 8 5 2 7 4 |
0 1 8 7 6 5 4 3 2 |
and the table of their vector products is
* | d1 | d3 | d5 | d7 | |
---|---|---|---|---|---|
d1 | d1 | d3 | d5 | d7 | |
d3 | d3 | d1 | d7 | d5 | |
d5 | d5 | d7 | d1 | d3 | |
d7 | d7 | d5 | d3 | d1 |
In both cases examination of the q subscripts in the table indicates the structure of modulo m-1 multiplication.
When m is a prime or a prime power, ^Su=dq, so the ^Su position mapping vectors also form an isomorphic group with the vector product. And since
^Su * ^Su' | = f00 * Su * f00-1 * f00 * Su' * f00-1 |
---|---|
= f00 * Su * Su' * f00-1 | |
= ^(Su * Su') |
the Su level mapping vectors form an isomorphic group with the vector product as well.
Note that the number of Su or ^Su mapping vectors is the number of totitives of m-1 (the totient of m-1).
Listed below are the first column vectors fuv for prime values of m up to 23. When multiple first column vectors are possible, they are listed in ascending order. The u and v vectors label the first column vectors according to the mapping operators given in the following sections. The lowest first column vector f00 is listed first. Each column in a table below lists
Note that the primitive elements are contained in positions 2 and m-1 (and sometimes other positions). Also note that for m>2, position (m-1)/2+1 always contains the level m-1.
The first column vector tables for m=prime are as follows.
m: | 2 | m: | 3 | m: | 5 | m: | 7 | m: | 11 | m: | 13 | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 | u: | 0 | u: | 0 | 1 | u: | 0 | 1 | u: | 0 0 | 0 1 | 1 1 | 1 0 | u: | 0 0 | 1 0 | 1 1 | 0 1 | ||||||
v: | 0 | v: | 0 | v: | 0 | 0 | v: | 0 | 0 | v: | 0 | 0 | 0 | 0 | v: | 0 | 0 | 0 | 0 | ||||||
fuv: |
0 1 | fuv: |
0 1 2 | fuv: |
0 1 2 4 3 |
0 1 3 4 2 | fuv: |
0 1 3 2 6 4 5 |
0 1 5 4 6 2 3 | fuv: |
0 1 2 4 8 5 10 9 7 3 6 |
0 1 6 3 7 9 10 5 8 4 2 |
0 1 7 5 2 3 10 4 6 9 8 |
0 1 8 9 6 4 10 3 2 5 7 | fuv: |
0 1 2 4 8 3 6 12 11 9 5 10 7 |
0 1 6 10 8 9 2 12 7 3 5 4 11 |
0 1 7 10 5 9 11 12 6 3 8 4 2 |
0 1 11 4 5 3 7 12 2 9 8 10 6 |
m: | 17 | m: | 19 | m: | 23 | ||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 0 0 | 1 0 1 | 0 1 1 | 1 1 0 | 1 0 0 | 0 0 1 | 1 1 1 | 0 1 0 | u: | 0 0 | 0 2 | 1 1 | 1 0 | 0 1 | 1 2 | u: | 0 0 | 1 4 | 0 2 | 0 4 | 1 2 | 1 3 | 1 0 | 0 3 | 0 1 | 1 1 | |||
v: | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | v: | 0 | 0 | 0 | 0 | 0 | 0 | v: | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
fuv: |
0 1 3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 |
0 1 5 8 6 13 14 2 10 16 12 9 11 4 3 15 7 |
0 1 6 2 12 4 7 8 14 16 11 15 5 13 10 9 3 |
0 1 7 15 3 4 11 9 12 16 10 2 14 13 6 8 5 |
0 1 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12 |
0 1 11 2 5 4 10 8 3 16 6 15 12 13 7 9 14 |
0 1 12 8 11 13 3 2 7 16 5 9 6 4 14 15 10 |
0 1 14 9 7 13 12 15 6 16 3 8 10 4 5 2 11 | fuv: |
0 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 |
0 1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 |
0 1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2 |
0 1 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3 |
0 1 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15 |
0 1 15 16 12 9 2 11 13 5 18 4 3 7 10 17 8 6 14 | fuv: |
0 1 5 2 10 4 20 8 17 16 11 9 22 18 21 13 19 3 15 6 7 12 14 |
0 1 7 3 21 9 17 4 5 12 15 13 22 16 20 2 14 6 19 18 11 8 10 |
0 1 10 8 11 18 19 6 14 2 20 16 22 13 15 12 5 4 17 9 21 3 7 |
0 1 11 6 20 13 5 9 7 8 19 2 22 12 17 3 10 18 14 16 15 4 21 |
0 1 14 12 7 6 15 3 19 13 21 18 22 9 11 16 17 8 20 4 10 2 5 |
0 1 15 18 17 2 7 13 11 4 14 3 22 8 5 6 21 16 10 12 19 9 20 |
0 1 17 13 14 8 21 12 20 18 7 4 22 6 10 9 15 2 11 3 5 16 19 |
0 1 19 16 5 3 11 2 15 9 10 6 22 4 7 18 20 12 21 8 14 13 17 |
0 1 20 9 19 12 10 16 21 6 5 8 22 3 14 4 11 13 7 2 17 18 15 |
0 1 21 4 15 16 14 18 10 3 17 12 22 2 19 8 7 9 5 13 20 6 11 |
Listed below are the level mapping operators Su and Dv associated with the first column vectors fuv for prime values of m up to 23. These operators give the mapping
in which f00 is the lowest first column vector. Each column in a table below lists the u vector and corresponding Su operator, or the v vector and corresponding Dv operator. When multiple level mapping operators Su are possible, they are listed in the same order as the position mapping operators ^Su in a following section.
Note that for prime values of m, v=0 and Dv=0+ the identity operator. This means that there is only one multiplication table for each prime m, and all the first column vectors yield that table. (This is the modulo m multiplication table.)
Also note that Su(h) gives the allowed levels fu0(i) mapped from f00(i) according to the fu0=Su(f00) level mapping. Consider, for example, when m=11 and i=3. Then f00(3)=4=h. The allowed levels for fu0(3) are given in the h=4 "position" of Su(h). In this case the allowed levels are 4, 9, 5, and 3. In particular, for
u = | 1 1 |
, fu0(3) = Su(f00(3)) = Su(4) = 5 |
Finally, note that for m=prime, level m-1 maps to itself. Thus for m=11,
The level mapping operator tables for m=prime are as follows.
m: | 2 | m: | 3 | m: | 5 | m: | 7 | m: | 11 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 | v: | 0 | u: | 0 | v: | 0 | u: | 0 | 1 | v: | 0 | u: | 0 | 1 | v: | 0 | u: | 0 0 | 1 0 | 1 1 | 0 1 | v: | 0 | |||||
Su: |
0 1 | Dv: |
0 1 | Su: |
0 1 2 | Dv: |
0 1 2 | Su: |
0 1 2 3 4 |
0 1 3 2 4 | Dv: |
0 1 2 3 4 | Su: |
0 1 2 3 4 5 6 |
0 1 4 5 2 3 6 | Dv: |
0 1 2 3 4 5 6 | Su: |
0 1 2 3 4 5 6 7 8 9 10 |
0 1 8 5 9 4 7 2 6 3 10 |
0 1 7 9 5 3 8 6 2 4 10 |
0 1 6 4 3 9 2 8 7 5 10 | Dv: |
0 1 2 3 4 5 6 7 8 9 10 |
m: | 13 | m: | 17 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 0 | 1 0 | 0 1 | 1 1 | v: | 0 | u: | 0 0 0 | 1 0 0 | 1 0 1 | 0 0 1 |
0 1 0 | 1 1 0 | 1 1 1 | 0 1 1 | v: | 0 | ||
Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 |
0 1 6 9 10 5 2 11 8 3 4 7 12 |
0 1 11 3 4 8 7 6 5 9 10 2 12 |
0 1 7 9 10 8 11 2 5 3 4 6 12 | Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 | Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
0 1 8 10 13 6 12 3 2 15 14 5 11 4 7 9 16 |
0 1 15 5 4 14 7 11 9 8 6 10 3 13 12 2 16 |
0 1 9 11 13 10 14 12 15 2 5 3 7 4 6 8 16 |
0 1 2 14 4 12 11 10 8 9 7 6 5 13 3 15 16 |
0 1 8 7 13 11 5 14 2 15 3 12 6 4 10 9 16 |
0 1 15 12 4 3 10 6 9 8 11 7 14 13 5 2 16 |
0 1 9 6 13 7 3 5 15 2 12 14 10 4 11 8 16 | Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
m: | 19 | m: | 23 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 0 | 1 0 | 0 1 | 1 2 | 0 2 | 1 1 | v: | 0 | u: | 0 0 | 0 2 | 0 1 | 1 0 | 0 4 | 1 1 | 0 3 | 1 3 | 1 4 | 1 2 | v: | 0 | ||
Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
0 1 13 15 17 9 5 11 12 16 3 7 8 14 10 2 4 6 18 |
0 1 14 2 6 16 9 7 8 4 15 11 12 10 3 13 17 5 18 |
0 1 15 10 16 6 17 11 12 5 14 7 8 2 13 3 9 4 18 |
0 1 3 14 9 17 4 7 8 6 13 11 12 15 2 10 5 16 18 |
0 1 10 13 5 4 16 11 12 17 2 7 8 3 15 14 6 9 18 | Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
0 1 8 4 18 10 9 21 6 16 11 20 3 12 7 17 2 14 13 5 19 15 22 |
0 1 9 13 12 20 2 17 16 8 19 5 18 4 15 7 6 21 3 11 10 14 22 |
0 1 13 2 8 17 3 5 12 4 14 7 16 9 19 11 18 20 6 15 21 10 22 |
0 1 6 18 13 11 16 15 9 2 20 19 4 3 21 14 8 7 12 10 5 17 22 |
0 1 4 9 16 21 13 20 18 12 15 17 6 8 11 5 3 10 2 7 14 19 22 |
0 1 16 12 3 19 8 14 2 6 5 10 13 18 17 21 9 15 4 20 11 7 22 |
0 1 18 16 2 15 12 19 13 3 17 14 9 6 20 10 4 11 8 21 7 5 22 |
0 1 3 6 9 7 18 11 4 13 21 15 8 2 10 19 12 5 16 14 17 20 22 |
0 1 12 8 6 14 4 10 3 18 7 21 2 16 5 20 13 19 9 17 15 11 22 | Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Listed below are the level mapping operator factors for prime values of m up to 23. These operators give the mapping
in which f00 is the lowest first column vector, and the level mapping operators Su and Dv are factored by components of the u and v vectors.
The level mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.
Consider, for example, m=11, with u0=1, u1=1, and v0=0. The element in position 3 of this first column vector is
fuv(3) | = (f00 * Su0=1 * Su1=1 * Dv0=0)(3) |
= Dv0=0(Su1=1(Su0=1(f00(3)))) | |
= Dv0=0(Su1=1(Su0=1(4))) | |
= Dv0=0(Su1=1(9)) | |
= Dv0=0(5) | |
= 5 |
This level agrees with the one listed for the third position of this first column vector.
Note that other factoring schemes are possible.
The level mapping operator factor tables for m=prime are as follows.
m: | 2 | m: | 3 | m: | 5 | m: | 7 | m: | 11 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | v0: | 0 | u0: | 0 | v0: | 0 | u0: | 0 | 1 | v0: | 0 | u0: | 0 | 1 | v0: | 0 | u0: | 0 | 1 | u1: | 0 | 1 | v0: | 0 | |||||
Su0: |
0 1 | Dv0: |
0 1 | Su0: |
0 1 2 | Dv0: |
0 1 2 | Su0: |
0 1 2 3 4 |
0 1 3 2 4 | Dv0: |
0 1 2 3 4 | Su0: |
0 1 2 3 4 5 6 |
0 1 4 5 2 3 6 | Dv0: |
0 1 2 3 4 5 6 | Su0: |
0 1 2 3 4 5 6 7 8 9 10 |
0 1 8 5 9 4 7 2 6 3 10 |
Su1: |
0 1 2 3 4 5 6 7 8 9 10 |
0 1 6 4 3 9 2 8 7 5 10 | Dv0: |
0 1 2 3 4 5 6 7 8 9 10 |
m: | 13 | m: | 17 | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | u1: | 0 | 1 | v0: | 0 | u0: | 0 | 1 | u1: | 0 | 1 | u2: | 0 | 1 | v0: | 0 | ||
Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 |
0 1 6 9 10 5 2 11 8 3 4 7 12 | Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 |
0 1 11 3 4 8 7 6 5 9 10 2 12 | Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 | Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
0 1 8 10 13 6 12 3 2 15 14 5 11 4 7 9 16 | Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
0 1 2 14 4 12 11 10 8 9 7 6 5 13 3 15 16 | Su2: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
0 1 9 11 13 10 14 12 15 2 5 3 7 4 6 8 16 | Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
m: | 19 | m: | 23 | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | u1: | 0 | 1 | 2 | v0: | 0 | u0: | 0 | 1 | u1: | 0 | 1 | 2 | 3 | 4 | v0: | 0 | ||
Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
0 1 13 15 17 9 5 11 12 16 3 7 8 14 10 2 4 6 18 | Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
0 1 14 2 6 16 9 7 8 4 15 11 12 10 3 13 17 5 18 |
0 1 3 14 9 17 4 7 8 6 13 11 12 15 2 10 5 16 18 | Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
0 1 13 2 8 17 3 5 12 4 14 7 16 9 19 11 18 20 6 15 21 10 22 | Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
0 1 9 13 12 20 2 17 16 8 19 5 18 4 15 7 6 21 3 11 10 14 22 |
0 1 8 4 18 10 9 21 6 16 11 20 3 12 7 17 2 14 13 5 19 15 22 |
0 1 16 12 3 19 8 14 2 6 5 10 13 18 17 21 9 15 4 20 11 7 22 |
0 1 6 18 13 11 16 15 9 2 20 19 4 3 21 14 8 7 12 10 5 17 22 | Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Listed below are the position mapping operators ^Su and ^Dv associated with the first column vectors fuv for prime values of m up to 23. These operators give the mapping
in which f00 is the lowest first column vector. Each column in a table below lists the u vector and corresponding ^Su operator, or the v vector and corresponding ^Dv operator. The values of q for which ^Su=dq also are listed in the ^Su columns. When multiple position mapping operators ^Su are possible, they are listed in the same order as the level mapping operators Su in a previous section. This order is that of ascending q.
Note that for prime values of m, v=0 and ^Dv=0+ the identity operator. This means that there is only one multiplication table for each prime m, and all the first column vectors yield that table. (This is the modulo m multiplication table.)
Also note that ^Su(i) gives the allowed positions of f00 which map to fu0(i) according to the fu0=f00(^Su) position mapping. Consider, for example, when m=11 and i=3. Then ^Su(3)=3, 7, 5, or 9. In particular, for
u = | 1 1 |
, fu0(3) = f00(^Su(3)) = f00(5) = 5 |
Finally, note that for prime m>2, position (m-1)/2+1 maps to itself. Thus for m=11,
The position mapping operator tables for m=prime are as follows.
m: | 2 | m: | 3 | m: | 5 | m: | 7 | m: | 11 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 | v: | 0 | u: | 0 | v: | 0 | u: | 0 | 1 | v: | 0 | u: | 0 | 1 | v: | 0 | u: | 0 0 | 1 0 | 1 1 | 0 1 | v: | 0 | |||||
q: | 1 | q: | 1 | q: | 1 | 3 | q: | 1 | 5 | q: | 1 | 3 | 7 | 9 | |||||||||||||||
^Su: |
0 1 | ^Dv: |
0 1 | ^Su: |
0 1 2 | ^Dv: |
0 1 2 | ^Su: |
0 1 2 3 4 |
0 1 4 3 2 | ^Dv: |
0 1 2 3 4 | ^Su: |
0 1 2 3 4 5 6 |
0 1 6 5 4 3 2 | ^Dv: |
0 1 2 3 4 5 6 | ^Su: |
0 1 2 3 4 5 6 7 8 9 10 |
0 1 4 7 10 3 6 9 2 5 8 |
0 1 8 5 2 9 6 3 10 7 4 |
0 1 10 9 8 7 6 5 4 3 2 | ^Dv: |
0 1 2 3 4 5 6 7 8 9 10 |
m: | 13 | m: | 17 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 0 | 1 0 | 0 1 | 1 1 | v: | 0 | u: | 0 0 0 | 1 0 0 | 1 0 1 | 0 0 1 |
0 1 0 | 1 1 0 | 1 1 1 | 0 1 1 | v: | 0 | ||
q: | 1 | 5 | 7 | 11 | q: | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | ||||||
^Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 |
0 1 6 11 4 9 2 7 12 5 10 3 8 |
0 1 8 3 10 5 12 7 2 9 4 11 6 |
0 1 12 11 10 9 8 7 6 5 4 3 2 | ^Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 | ^Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
0 1 4 7 10 13 16 3 6 9 12 15 2 5 8 11 14 |
0 1 6 11 16 5 10 15 4 9 14 3 8 13 2 7 12 |
0 1 8 15 6 13 4 11 2 9 16 7 14 5 12 3 10 |
0 1 10 3 12 5 14 7 16 9 2 11 4 13 6 15 8 |
0 1 12 7 2 13 8 3 14 9 4 15 10 5 16 11 6 |
0 1 14 11 8 5 2 15 12 9 6 3 16 13 10 7 4 |
0 1 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 | ^Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
m: | 19 | m: | 23 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 0 | 1 0 | 0 1 | 1 2 | 0 2 | 1 1 | v: | 0 | u: | 0 0 | 0 2 | 0 1 | 1 0 | 0 4 | 1 1 | 0 3 | 1 3 | 1 4 | 1 2 | v: | 0 | ||
q: | 1 | 5 | 7 | 11 | 13 | 17 | q: | 1 | 3 | 5 | 7 | 9 | 13 | 15 | 17 | 19 | 21 | ||||||
^Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
0 1 6 11 16 3 8 13 18 5 10 15 2 7 12 17 4 9 14 |
0 1 8 15 4 11 18 7 14 3 10 17 6 13 2 9 16 5 12 |
0 1 12 5 16 9 2 13 6 17 10 3 14 7 18 11 4 15 8 |
0 1 14 9 4 17 12 7 2 15 10 5 18 13 8 3 16 11 6 |
0 1 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 | ^Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | ^Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
0 1 4 7 10 13 16 19 22 3 6 9 12 15 18 21 2 5 8 11 14 17 20 |
0 1 6 11 16 21 4 9 14 19 2 7 12 17 22 5 10 15 20 3 8 13 18 |
0 1 8 15 22 7 14 21 6 13 20 5 12 19 4 11 18 3 10 17 2 9 16 |
0 1 10 19 6 15 2 11 20 7 16 3 12 21 8 17 4 13 22 9 18 5 14 |
0 1 14 5 18 9 22 13 4 17 8 21 12 3 16 7 20 11 2 15 6 19 10 |
0 1 16 9 2 17 10 3 18 11 4 19 12 5 20 13 6 21 14 7 22 15 8 |
0 1 18 13 8 3 20 15 10 5 22 17 12 7 2 19 14 9 4 21 16 11 6 |
0 1 20 17 14 11 8 5 2 21 18 15 12 9 6 3 22 19 16 13 10 7 4 |
0 1 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 | ^Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Listed below are the position mapping operator factors for prime values of m up to 23. These operators give the mapping
in which f00 is the lowest first column vector, and the position mapping operators ^Su and ^Dv are factored by components of the u and v vectors.
The position mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.
Consider, for example, m=11, with u0=1, u1=1, and v0=0. The element in position 3 of this first column vector is
fuv(3) | = (^Su0=1 * ^Su1=1 * ^Dv0=0 * f00)(3) |
= f00(^Dv0=0(^Su1=1(^Su0=1(3)))) | |
= f00(^Dv0=0(^Su1=1(7))) | |
= f00(^Dv0=0(5)) | |
= f00(5) | |
= 5 |
This level agrees with the one listed for the third position of this first column vector.
Note that other factoring schemes are possible.
The position mapping operator factor tables for m=prime are as follows.
m: | 2 | m: | 3 | m: | 5 | m: | 7 | m: | 11 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | v0: | 0 | u0: | 0 | v0: | 0 | u0: | 0 | 1 | v0: | 0 | u0: | 0 | 1 | v0: | 0 | u0: | 0 | 1 | u1: | 0 | 1 | v0: | 0 | |||||
q: | 1 | q: | 1 | q: | 1 | 3 | q: | 1 | 5 | q: | 1 | 3 | q: | 1 | 9 | |||||||||||||||
^Su0: |
0 1 | ^Dv0: |
0 1 | ^Su0: |
0 1 2 | ^Dv0: |
0 1 2 | ^Su0: |
0 1 2 3 4 |
0 1 4 3 2 | ^Dv0: |
0 1 2 3 4 | ^Su0: |
0 1 2 3 4 5 6 |
0 1 6 5 4 3 2 | ^Dv0: |
0 1 2 3 4 5 6 | ^Su0: |
0 1 2 3 4 5 6 7 8 9 10 |
0 1 4 7 10 3 6 9 2 5 8 |
^Su1: |
0 1 2 3 4 5 6 7 8 9 10 |
0 1 10 9 8 7 6 5 4 3 2 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 |
m: | 13 | m: | 17 | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | u1: | 0 | 1 | v0: | 0 | u0: | 0 | 1 | u1: | 0 | 1 | u2: | 0 | 1 | v0: | 0 | ||
q: | 1 | 5 | q: | 1 | 7 | q: | 1 | 3 | q: | 1 | 9 | q: | 1 | 7 | ||||||
^Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 |
0 1 6 11 4 9 2 7 12 5 10 3 8 | ^Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 |
0 1 8 3 10 5 12 7 2 9 4 11 6 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 | ^Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
0 1 4 7 10 13 16 3 6 9 12 15 2 5 8 11 14 | ^Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
0 1 10 3 12 5 14 7 16 9 2 11 4 13 6 15 8 | ^Su2: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
0 1 8 15 6 13 4 11 2 9 16 7 14 5 12 3 10 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
m: | 19 | m: | 23 | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | u1: | 0 | 1 | 2 | v0: | 0 | u0: | 0 | 1 | u1: | 0 | 1 | 2 | 3 | 4 | v0: | 0 | ||
q: | 1 | 5 | q: | 1 | 7 | 13 | q: | 1 | 7 | q: | 1 | 5 | 3 | 15 | 9 | ||||||
^Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
0 1 6 11 16 3 8 13 18 5 10 15 2 7 12 17 4 9 14 | ^Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
0 1 8 15 4 11 18 7 14 3 10 17 6 13 2 9 16 5 12 |
0 1 14 9 4 17 12 7 2 15 10 5 18 13 8 3 16 11 6 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | ^Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
0 1 8 15 22 7 14 21 6 13 20 5 12 19 4 11 18 3 10 17 2 9 16 | ^Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
0 1 6 11 16 21 4 9 14 19 2 7 12 17 22 5 10 15 20 3 8 13 18 |
0 1 4 7 10 13 16 19 22 3 6 9 12 15 18 21 2 5 8 11 14 17 20 |
0 1 16 9 2 17 10 3 18 11 4 19 12 5 20 13 6 21 14 7 22 15 8 |
0 1 10 19 6 15 2 11 20 7 16 3 12 21 8 17 4 13 22 9 18 5 14 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Listed below are selected first column vectors fuv for values of m which are prime powers. First column vectors are given for m=4, 8, 9, and 16. The first column vectors are listed starting with the lowest first column vector f00, in ascending order. The number of first column vectors listed for each value of m is as follows.
m | Number of First Column Vectors Listed |
---|---|
4 | 2 of 2 |
8 | 10 of 48 |
9 | 12 of 12 |
16 | 10 of 2688 |
The u and v vectors label the first column vectors according to the mapping operators given in the following sections. Each column in a table below lists
Note that the primitive elements are contained in positions 2 and m-1 (and sometimes other positions). Also note that for m=9 which is odd, position (m-1)/2+1=5 always contains the level 2.
The first column vector tables for m=prime power are as follows.
m: | 4 | m: | 8 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 | 1 | u: | 0 0 | 0 0 |
0 0 | 0 0 | 0 0 |
0 0 | 0 0 | 0 0 |
1 2 | 1 0 | ||
v: | 0 | 0 | v: | 0 0 0 | 1 0 0 |
0 1 1 | 1 1 1 | 0 1 0 |
1 1 0 | 0 0 1 | 1 0 1 |
1 1 1 | 0 1 1 | ||
fuv: |
0 1 2 3 |
0 1 3 2 | fuv: |
0 1 2 4 3 6 7 5 |
0 1 2 4 5 7 3 6 |
0 1 2 5 3 7 6 4 |
0 1 2 5 4 6 3 7 |
0 1 2 6 3 4 5 7 |
0 1 2 6 7 5 3 4 |
0 1 2 7 3 5 4 6 |
0 1 2 7 6 4 3 5 |
0 1 3 4 2 7 6 5 |
0 1 3 4 5 6 2 7 |
m: | 9 | m: | 16 | ||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 0 | 1 1 | 0 0 | 1 1 | 0 0 | 1 1 | 0 1 | 1 0 | 0 1 | 1 0 | 0 1 | 1 0 | u: | 0 0 0 | 0 0 0 |
0 0 0 | 0 0 0 | 0 0 0 |
0 0 0 | 0 0 0 | 0 0 0 |
0 0 0 | 0 0 0 | ||
v: | 0 | 1 | 1 | 2 | 2 | 0 | 0 | 1 | 2 | 0 | 1 | 2 | v: | 0 0 0 0 0 0 | 2 0 0 0 0 0 |
0 1 0 0 0 0 | 2 1 0 0 0 0 |
1 0 0 0 0 0 | 4 0 0 0 0 0 |
1 1 0 0 0 0 | 4 1 0 0 0 0 |
0 0 1 0 0 0 | 2 0 1 0 0 0 | ||
fuv: |
0 1 3 4 7 2 6 8 5 |
0 1 3 7 8 2 6 5 4 |
0 1 4 5 6 2 8 7 3 |
0 1 4 6 7 2 8 3 5 |
0 1 5 3 8 2 7 6 4 |
0 1 5 8 6 2 7 4 3 |
0 1 6 4 5 2 3 8 7 |
0 1 6 7 4 2 3 5 8 |
0 1 7 3 4 2 5 6 8 |
0 1 7 8 3 2 5 4 6 |
0 1 8 5 3 2 4 7 6 |
0 1 8 6 5 2 4 3 7 | fuv: |
0 1 2 4 8 3 6 12 11 5 10 7 14 15 13 9 |
0 1 2 4 8 9 11 15 7 14 5 10 13 3 6 12 |
0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 |
0 1 2 4 9 8 10 14 7 15 5 11 12 3 6 13 |
0 1 2 4 10 3 6 14 9 5 8 7 12 13 15 11 |
0 1 2 4 10 11 9 13 7 12 5 8 15 3 6 14 |
0 1 2 4 11 3 6 15 8 5 9 7 13 12 14 10 |
0 1 2 4 11 10 8 12 7 13 5 9 14 3 6 15 |
0 1 2 4 12 3 6 8 15 5 14 7 10 11 9 13 |
0 1 2 4 12 13 15 11 7 10 5 14 9 3 6 8 |
Listed below are selected level mapping operators Su and Dv associated with the first column vectors fuv for values of m which are prime powers. Level mapping operators are given for m=4, 8, 9, and 16. These operators give the mapping
in which f00 is the lowest first column vector. The number of level mapping operators listed for each value of m is as follows.
m | Number of Su Level Mapping Operators Listed | Number of Dv Level Mapping Operators Listed | ||
---|---|---|---|---|
4 | 2 of 2 | 1 of 1 | ||
8 | 6 of 6 | 8 of 8 | ||
9 | 4 of 4 | 3 of 3 | ||
16 | 8 of 8 | 10 of 336 |
Each column in a table below lists the u vector and corresponding Su operator, or the v vector and corresponding Dv operator. There are multiple level mapping operators Su for m=prime power. They are listed in the same order as the corresponding position mapping operators ^Su in a following section.
Note that for values of m which are prime powers, there can be more than one Dv level mapping operator. This means that there can be more than one multiplication table for each value of m. Each level mapping operator product
maps f00 to a first column vector fuv which yields the multiplication table of
Also note that Muv(h) gives the allowed levels fuv(i) mapped from f00(i) according to the fuv=Muv(f00)=Dv(Su(f00)) level mapping. Consider, for example, when m=9 and i=3. Then f00(3)=4=h. The h=4 position of the Su operators gives the allowed levels 4 and 8, which map to positions 4 and 8 of the Dv operators. The allowed levels of Dv are 4, 5, 3 and 8, 7, 6 for positions 4 and 8 respectively. Thus, the allowed levels for fuv(3) are 3, 4, 5, 6, 7, and 8. In particular, for
u = | 1 1 |
and v = 1, fuv(3) = Dv(Su(f00(3))) = Dv(Su(4)) = Dv(8) = 7 |
The level mapping operator tables for m=prime power are as follows.
m: | 4 | m: | 8 | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 | 1 | v: | 0 | u: | 0 0 | 0 1 |
1 0 | 0 2 |
1 2 | 1 1 |
v: | 0 0 0 | 0 0 1 |
0 1 0 | 0 1 1 |
1 0 0 | 1 0 1 |
1 1 0 | 1 1 1 | ||
Su: |
0 1 2 3 |
0 1 3 2 | Dv: |
0 1 2 3 | Su: |
0 1 2 3 4 5 6 7 |
0 1 4 5 6 7 2 3 |
0 1 3 4 5 6 7 2 |
0 1 6 7 2 3 4 5 |
0 1 7 2 3 4 5 6 |
0 1 5 6 7 2 3 4 | Dv: |
0 1 2 3 4 5 6 7 |
0 1 2 3 7 6 5 4 |
0 1 2 3 6 7 4 5 |
0 1 2 3 5 4 7 6 |
0 1 2 5 4 6 7 3 |
0 1 2 6 7 5 4 3 |
0 1 2 7 6 4 5 3 |
0 1 2 4 5 7 6 3 |
m: | 9 | ||||||||
---|---|---|---|---|---|---|---|---|---|
u: | 0 0 | 1 0 | 0 1 | 1 1 |
v: | 0 | 1 | 2 | |
Su: |
0 1 2 3 4 5 6 7 8 |
0 1 2 7 8 6 5 3 4 |
0 1 2 6 4 7 3 5 8 |
0 1 2 5 8 3 7 6 4 | Dv: |
0 1 2 3 4 5 6 7 8 |
0 1 2 4 5 3 8 6 7 |
0 1 2 5 3 4 7 8 6 |
m: | 16 | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 0 0 | 1 0 0 |
0 1 0 | 0 0 1 | 1 1 0 |
1 1 1 | 0 1 1 | 1 0 1 |
v: | 0 0 0 0 0 0 | 0 0 1 0 0 0 |
0 1 0 0 0 0 | 1 0 0 0 0 0 |
1 1 0 0 0 0 | 2 0 0 0 0 0 |
2 0 1 0 0 0 | 2 1 0 0 0 0 |
4 0 0 0 0 0 | 4 1 0 0 0 0 | |
Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 4 5 3 2 7 6 12 13 8 9 15 14 11 10 |
0 1 3 2 5 4 6 7 15 14 12 13 10 11 9 8 |
0 1 11 13 9 14 6 7 12 5 8 3 15 2 4 10 |
0 1 5 4 2 3 7 6 10 11 15 14 8 9 13 12 |
0 1 14 9 11 13 7 6 8 3 10 4 12 5 2 15 |
0 1 13 11 14 9 6 7 10 4 15 2 8 3 5 12 |
0 1 9 14 13 11 7 6 15 2 12 5 10 4 3 8 | Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 4 5 6 7 12 13 14 15 8 9 10 11 |
0 1 2 3 4 5 6 7 9 8 11 10 13 12 15 14 |
0 1 2 3 4 5 6 7 10 11 8 9 14 15 12 13 |
0 1 2 3 4 5 6 7 11 10 9 8 15 14 13 12 |
0 1 2 9 4 14 11 10 8 12 5 7 15 6 13 3 |
0 1 2 13 4 10 15 14 12 8 5 7 11 6 9 3 |
0 1 2 8 4 15 10 11 9 13 5 7 14 6 12 3 |
0 1 2 11 4 12 9 8 10 14 5 7 13 6 15 3 |
0 1 2 10 4 13 8 9 11 15 5 7 12 6 14 3 |
Listed below are the level mapping operator factors for values of m which are prime powers. Level mapping operator factors are given for m=4, 8, 9, and 16. These operators give the mapping
in which f00 is the lowest first column vector, and the level mapping operators Su and Dv are factored by components of the u and v vectors.
The level mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.
Consider, for example, m=9, with u0=1, u1=1, and v0=1. The element in position 3 of this first column vector is
fuv(3) | = (f00 * Su0=1 * Su1=1 * Dv0=1)(3) |
= Dv0=1(Su1=1(Su0=1(f00(3)))) | |
= Dv0=1(Su1=1(Su0=1(4))) | |
= Dv0=1(Su1=1(8)) | |
= Dv0=1(8) | |
= 7 |
This level agrees with the one listed for the third position of this first column vector.
The level mapping operator factor tables for m=prime power are as follows.
m: | 4 | m: | 8 | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | v0: | 0 | u0: | 0 | 1 | u1: | 0 | 1 | 2 | v0: | 0 | 1 | v1: | 0 | 1 | v2: | 0 | 1 | ||
Su0: |
0 1 2 3 |
0 1 3 2 | Dv0: |
0 1 2 3 | Su0: |
0 1 2 3 4 5 6 7 |
0 1 3 4 5 6 7 2 |
Su1: |
0 1 2 3 4 5 6 7 |
0 1 4 5 6 7 2 3 |
0 1 6 7 2 3 4 5 | Dv0: |
0 1 2 3 4 5 6 7 |
0 1 2 5 4 6 7 3 | Dv1: |
0 1 2 3 4 5 6 7 |
0 1 2 3 6 7 4 5 | Dv2: |
0 1 2 3 4 5 6 7 |
0 1 2 3 7 6 5 4 |
m: | 9 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | u1: | 0 | 1 | v0: | 0 | 1 | 2 | |
Su0: |
0 1 2 3 4 5 6 7 8 |
0 1 2 7 8 6 5 3 4 | Su1: |
0 1 2 3 4 5 6 7 8 |
0 1 2 6 4 7 3 5 8 | Dv0: |
0 1 2 3 4 5 6 7 8 |
0 1 2 4 5 3 8 6 7 |
0 1 2 5 3 4 7 8 6 |
m: | 16 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | u1: | 0 | 1 | u2: | 0 | 1 | v0: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 4 5 3 2 7 6 12 13 8 9 15 14 11 10 | Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 3 2 5 4 6 7 15 14 12 13 10 11 9 8 | Su2: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 11 13 9 14 6 7 12 5 8 3 15 2 4 10 | Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 4 5 6 7 10 11 8 9 14 15 12 13 |
0 1 2 9 4 14 11 10 8 12 5 7 15 6 13 3 |
0 1 3 9 4 15 10 11 8 12 5 6 14 7 13 2 |
0 1 2 11 4 12 9 8 10 14 5 7 13 6 15 3 |
0 1 3 11 4 13 8 9 10 14 5 6 12 7 15 2 |
0 1 4 5 6 7 2 3 8 9 12 13 14 15 10 11 |
m: | 16 | (continued) | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
v1: | 0 | 1 | v2: | 0 | 1 | v3: | 0 | 1 | v4: | 0 | 1 | v5: | 0 | 1 | 2 | |
Dv1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 4 5 6 7 9 8 11 10 13 12 15 14 | Dv2: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 4 5 6 7 12 13 14 15 8 9 10 11 | Dv3: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 5 4 7 6 8 9 10 11 13 12 15 14 | Dv4: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 6 7 4 5 8 9 10 11 14 15 12 13 | Dv5: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 8 9 10 11 4 5 6 7 12 13 14 15 |
0 1 2 3 12 13 14 15 4 5 6 7 8 9 10 11 |
Listed below are selected position mapping operators ^Su and ^Dv associated with the first column vectors fuv for values of m which are prime powers. Position mapping operators are given for m=4, 8, 9, and 16. These operators give the mapping
in which f00 is the lowest first column vector. The number of position mapping operators listed for each value of m is as follows.
m | Number of ^Su Position Mapping Operators Listed | Number of ^Dv Position Mapping Operators Listed | ||
---|---|---|---|---|
4 | 2 of 2 | 1 of 1 | ||
8 | 6 of 6 | 8 of 8 | ||
9 | 4 of 4 | 3 of 3 | ||
16 | 8 of 8 | 10 of 336 |
Each column in a table below lists the u vector and corresponding ^Su operator, or the v vector and corresponding ^Dv operator. The values of q for which ^Su=dq also are listed in the ^Su columns. There are multiple position mapping operators ^Su for m=prime power. They are listed in the same order as the level mapping operators Su in a previous section. This order is that of ascending q.
Note that for values of m which are prime powers, there can be more than one ^Dv position mapping operator. This means that there can be more than one multiplication table for each value of m. Each position mapping operator product
maps f00 to a first column vector fuv which yields the multiplication table of
Also note that ^Muv(i) gives the allowed positions of f00 which map to fuv(i) according to the fuv=f00(^Muv)=f00(^Dv(^Su)) position mapping. Consider, for example, when m=9 and i=3. The i=3 position of the ^Su operators gives the allowed levels 3 and 7, which map to positions 3 and 7 of the ^Dv operators. The allowed levels of ^Dv are 3, 8, 2 and 7, 4, 6 for positions 3 and 7 respectively. Thus, the allowed positions of f00 which map to fuv(3) are 2, 3, 4, 6, 7, and 8. In particular, for
u = | 1 1 |
and v = 1, fuv(3) = f00(^Dv(^Su(3))) = f00(^Dv(7)) = f00(4) = 7 |
The position mapping operator tables for m=prime power are as follows.
m: | 4 | m: | 8 | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 | 1 | v: | 0 | u: | 0 0 | 0 1 |
1 0 | 0 2 |
1 2 | 1 1 |
v: | 0 0 0 | 0 0 1 |
0 1 0 | 0 1 1 |
1 0 0 | 1 0 1 |
1 1 0 | 1 1 1 | ||
q: | 1 | 2 | q: | 1 | 2 | 3 | 4 | 5 | 6 | |||||||||||||
^Su: |
0 1 2 3 |
0 1 3 2 | ^Dv: |
0 1 2 3 | ^Su: |
0 1 2 3 4 5 6 7 |
0 1 3 5 7 2 4 6 |
0 1 4 7 3 6 2 5 |
0 1 5 2 6 3 7 4 |
0 1 6 4 2 7 5 3 |
0 1 7 6 5 4 3 2 | ^Dv: |
0 1 2 3 4 5 6 7 |
0 1 2 6 4 7 3 5 |
0 1 2 5 4 3 7 6 |
0 1 2 7 4 6 5 3 |
0 1 2 3 7 6 4 5 |
0 1 2 6 5 3 4 7 |
0 1 2 5 6 7 4 3 |
0 1 2 7 3 5 4 6 |
m: | 9 | ||||||||
---|---|---|---|---|---|---|---|---|---|
u: | 0 0 | 1 0 | 0 1 | 1 1 |
v: | 0 | 1 | 2 | |
q: | 1 | 3 | 5 | 7 | |||||
^Su: |
0 1 2 3 4 5 6 7 8 |
0 1 4 7 2 5 8 3 6 |
0 1 6 3 8 5 2 7 4 |
0 1 8 7 6 5 4 3 2 | ^Dv: |
0 1 2 3 4 5 6 7 8 |
0 1 3 8 6 5 7 4 2 |
0 1 8 2 7 5 4 6 3 |
m: | 16 | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 0 0 | 1 0 0 |
0 1 0 | 0 0 1 | 1 1 0 |
1 1 1 | 0 1 1 | 1 0 1 |
v: | 0 0 0 0 0 0 | 0 0 1 0 0 0 |
0 1 0 0 0 0 | 1 0 0 0 0 0 |
1 1 0 0 0 0 | 2 0 0 0 0 0 |
2 0 1 0 0 0 | 2 1 0 0 0 0 |
4 0 0 0 0 0 | 4 1 0 0 0 0 | |
q: | 1 | 2 | 4 | 7 | 8 | 11 | 13 | 14 | ||||||||||||
^Su: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 |
0 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 |
0 1 8 15 7 14 6 13 5 12 4 11 3 10 2 9 |
0 1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 |
0 1 12 8 4 15 11 7 3 14 10 6 2 13 9 5 |
0 1 14 12 10 8 6 4 2 15 13 11 9 7 5 3 |
0 1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 | ^Dv: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 7 5 6 4 13 9 12 11 10 8 15 14 |
0 1 2 3 15 5 6 14 10 9 8 11 13 12 7 4 |
0 1 2 3 10 5 6 12 15 9 4 11 7 14 13 8 |
0 1 2 3 8 5 6 13 4 9 15 11 14 7 12 10 |
0 1 2 3 4 15 8 13 11 12 9 10 14 5 6 7 |
0 1 2 3 7 14 13 8 11 10 9 12 15 5 6 4 |
0 1 2 3 15 4 10 12 11 13 9 8 7 5 6 14 |
0 1 2 3 10 8 15 14 11 7 9 4 13 5 6 12 |
0 1 2 3 8 10 4 7 11 14 9 15 12 5 6 13 |
Listed below are the position mapping operator factors for values of m which are prime powers. Position mapping operator factors are given for m=4, 8, 9, and 16. These operators give the mapping
in which f00 is the lowest first column vector, and the position mapping operators ^Su and ^Dv are factored by components of the u and v vectors.
The position mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.
Consider, for example, m=9, with u0=1, u1=1, and v0=1. The element in position 3 of this first column vector is
fuv(3) | = (^Su0=1 * ^Su1=1 * ^Dv0=1 * f00)(3) |
= f00(^Dv0=1(^Su1=1(^Su0=1(3)))) | |
= f00(^Dv0=1(^Su1=1(7))) | |
= f00(^Dv0=1(7)) | |
= f00(4) | |
= 7 |
This level agrees with the one listed for the third position of this first column vector.
The position mapping operator factor tables for m=prime power are as follows.
m: | 4 | m: | 8 | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | v0: | 0 | u0: | 0 | 1 | u1: | 0 | 1 | 2 | v0: | 0 | 1 | v1: | 0 | 1 | v2: | 0 | 1 | ||
q: | 1 | 2 | q: | 1 | 3 | q: | 1 | 2 | 4 | |||||||||||||
^Su0: |
0 1 2 3 |
0 1 3 2 | ^Dv0: |
0 1 2 3 | ^Su0: |
0 1 2 3 4 5 6 7 |
0 1 4 7 3 6 2 5 |
^Su1: |
0 1 2 3 4 5 6 7 |
0 1 3 5 7 2 4 6 |
0 1 5 2 6 3 7 4 | ^Dv0: |
0 1 2 3 4 5 6 7 |
0 1 2 3 7 6 4 5 | ^Dv1: |
0 1 2 3 4 5 6 7 |
0 1 2 5 4 3 7 6 | ^Dv2: |
0 1 2 3 4 5 6 7 |
0 1 2 6 4 7 3 5 |
m: | 9 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | u1: | 0 | 1 | v0: | 0 | 1 | 2 | |
q: | 1 | 3 | q: | 1 | 5 | |||||
^Su0: |
0 1 2 3 4 5 6 7 8 |
0 1 4 7 2 5 8 3 6 | ^Su1: |
0 1 2 3 4 5 6 7 8 |
0 1 6 3 8 5 2 7 4 | ^Dv0: |
0 1 2 3 4 5 6 7 8 |
0 1 3 8 6 5 7 4 2 |
0 1 8 2 7 5 4 6 3 |
m: | 16 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | u1: | 0 | 1 | u2: | 0 | 1 | v0: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
q: | 1 | 2 | q: | 1 | 4 | q: | 1 | 7 | |||||||||
^Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 | ^Su1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 | ^Su2: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 8 15 7 14 6 13 5 12 4 11 3 10 2 9 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 10 5 6 12 15 9 4 11 7 14 13 8 |
0 1 2 3 4 15 8 13 11 12 9 10 14 5 6 7 |
0 1 5 3 4 15 10 12 6 13 9 8 14 2 11 7 |
0 1 2 3 10 8 15 14 11 7 9 4 13 5 6 12 |
0 1 5 3 10 8 4 7 6 14 9 15 13 2 11 12 |
0 1 3 6 4 9 2 12 14 11 7 5 10 8 13 15 |
m: | 16 | (continued) | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
v1: | 0 | 1 | v2: | 0 | 1 | v3: | 0 | 1 | v4: | 0 | 1 | v5: | 0 | 1 | 2 | |
^Dv1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 15 5 6 14 10 9 8 11 13 12 7 4 | ^Dv2: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 3 7 5 6 4 13 9 12 11 10 8 15 14 | ^Dv3: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 9 4 5 11 14 8 3 10 6 13 12 7 15 | ^Dv4: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 6 4 5 3 12 8 11 10 9 7 14 13 15 | ^Dv5: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
0 1 2 4 3 5 10 7 11 15 6 8 12 13 14 9 |
0 1 2 7 3 5 12 4 11 14 6 13 10 8 15 9 |
The first column vectors for values of m which are prime powers can be associated with the irreducible monic polynomials used to construct Galois fields. The association is made by comparing the addition and multiplication tables given here with the Galois field tables. (See Appendix A of Orthogonal Arrays Theory and Applications1 for an introduction to the theory of Galois fields.)
The Galois field tables are given in terms of the variable x of an irreducible monic polynomial f(x). The association with the first column vectors is made by substituting the levels greater than p-1 for the powers of the variable x and then comparing the tables with those of the first column vectors. In this comparison the value of the u vector does not matter, because all first column vectors fuv with a particular v vector have the same addition and multiplication tables.
For example, Tables A.9 and A.10 of Appendix A1 give the addition and multiplication tables for m=9 using the irreducible monic polynomial
Substitution of a level for x (say, x=5), and requiring the addition table A.9 be the same as the m=9 addition table here determines the levels for all the elements. In this case
0 | = 0 |
1 | = 1 |
2 | = 2 |
x | = 5 |
x+1 | = 3 |
x+2 | = 4 |
2x | = 7 |
2x+1 | = 8 |
2x+2 | = 6 |
Substitution of these levels into the multiplication table A.10 yields the same table as that for the lowest first column vector f00. Similar associations can be made for other values of x with this polynomial. Associations can be made with the two other irreducible monic polynomials for m=9 as well. For example the lowest first column vector f00 gives the powers of x in Table A.111 for f3(x=5), f5(x=4) and f6(x=3).
Listed below are the combinations of levels for the powers of x which associate the irreducible monic polynomials f(x) with the v vectors for m=4, 8, and 9. For m=4 and 9 (squares of primes), (x) levels are listed. For m=8=23, (x, x2) level pairs are listed.
m: | 4 | v: | 0 | |||||||
---|---|---|---|---|---|---|---|---|---|---|
f(x): | x2+x+1 | (x): | (2) (3) | |||||||
m: | 8 | v: | 0 0 0 | 0 0 1 |
0 1 0 | 0 1 1 |
1 0 0 | 1 0 1 |
1 1 0 | 1 1 1 |
f(x): | x3+x+1 | (x, x2): | (2, 4) (4, 6) (6, 2) | (2, 7) (5, 2) (7, 5) |
(2, 6) (4, 2) (6, 4) | (2, 5) (5, 7) (7, 2) |
(3, 5) (5, 6) (6, 3) | (3, 6) (5, 3) (6, 5) |
(3, 7) (4, 3) (7, 4) | (3, 4) (4, 7) (7, 3) |
x3+x2+1 | (x, x2): | (3, 5) (5, 7) (7, 3) | (3, 6) (4, 3) (6, 4) |
(3, 7) (5, 3) (7, 5) | (3, 4) (4, 6) (6, 3) |
(2, 4) (4, 7) (7, 2) | (2, 7) (4, 2) (7, 4) |
(2, 6) (5, 2) (6, 5) | (2, 5) (5, 6) (6, 2) | |
m: | 9 | v: | 0 | 1 | 2 | |||||
f(x): | x2+2x+2 | (x): | (3) (7) | (4) (6) | (5) (8) | |||||
x2+1 | (x): | (4) (8) | (5) (7) | (3) (6) | ||||||
x2+x+2 | (x): | (5) (6) | (3) (8) | (4) (7) |
Any value of m>1 has a set of trivial first column vectors for c=2. These vectors contain the levels 0 and 1 in the zeroth and first positions respectively, and any permutation of the remaining levels in the remaining positions. There are (m-2)! first column vectors for c=2. In these cases the lowest first column vector f00=0+ the identity operator, so Su=^Su, Dv=^Dv, Muv=^Muv, etc.
Searches for first column vectors with c=3 were executed for values of m=6, 10, 14, and 18. In all cases the searches completed without finding a first column vector for c=3. A similar search for m=22 and c=3 was abandoned prior to completion, without finding a first column vector. Thus, for these values of m, the maximum value of c given here is 2.
Listed below are the position mapping operator factors for m=6. In this case there are 4!=24 first column vectors leading to 6 different multiplication tables.
m: | 6 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | u1: | 0 | 1 | v0: | 0 | 1 | v1: | 0 | 1 | 2 | |
q: | 1 | 4 | q: | 1 | 3 | ||||||||
^Su0: |
0 1 2 3 4 5 |
0 1 5 4 3 2 |
^Su1: |
0 1 2 3 4 5 |
0 1 4 2 5 3 | ^Dv0: |
0 1 2 3 4 5 |
0 1 3 2 5 4 | ^Dv1: |
0 1 2 3 4 5 |
0 1 2 4 5 3 |
0 1 2 5 3 4 |
Listed below are selected first column vectors fuv for values of m which are prime power products, and for values of c>2. First column vectors are given for m=12, 15, 20, and 21. In these cases first column vectors were found for c=4, but searches with c=5 completed without finding a first column vector. The first column vectors are listed starting with the lowest first column vector f00, in ascending order. The number of first column vectors listed for each value of m is as follows.
m | Number of First Column Vectors Listed |
---|---|
12 | 10 of 24 |
15 | 10 of 64 |
20 | 10 of 3744 |
21 | 10 of 12372 |
Where listed, the u and v vectors label the first column vectors according to the mapping operators given in the following section. A column in a table below lists
The first column vector tables for m=prime power product and c>2 are as follows.
m: | 12 | m: | 15 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u: | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | u: | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||
v: | 0 0 | 1 0 |
2 0 | 3 0 | 4 0 |
2 0 | 5 0 | 4 0 |
4 1 | 5 1 | v: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
fuv: |
0 1 2 3 6 10 4 9 11 8 7 5 |
0 1 2 4 10 9 8 11 3 6 7 5 |
0 1 2 10 11 4 7 6 8 5 9 3 |
0 1 2 10 11 9 3 7 4 6 5 8 |
0 1 3 8 2 6 9 10 11 7 5 4 |
0 1 3 9 5 8 6 7 4 11 10 2 |
0 1 4 3 2 8 10 11 7 5 6 9 |
0 1 4 5 7 11 10 9 6 2 8 3 |
0 1 4 5 10 2 7 9 3 11 8 6 |
0 1 4 6 11 8 7 2 10 5 3 9 | fuv: |
0 1 2 6 3 14 9 12 11 4 10 8 13 5 7 |
0 1 2 11 4 10 8 13 5 7 6 3 14 9 12 |
0 1 2 13 4 11 10 3 6 8 5 9 14 12 7 |
0 1 3 8 14 13 2 11 4 5 12 9 7 10 6 |
0 1 3 9 2 12 6 13 11 8 7 10 14 4 5 |
0 1 3 9 7 12 6 13 2 5 4 14 10 11 8 |
0 1 4 3 7 9 14 5 13 10 2 11 12 8 6 |
0 1 4 9 2 3 14 8 10 7 5 11 6 13 12 |
0 1 5 3 6 13 10 9 4 12 2 11 7 8 14 |
0 1 5 4 7 14 12 6 8 3 9 2 13 10 11 |
m: | 20 | m: | 21 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
fuv: |
0 1 2 3 7 6 13 18 17 15 11 5 8 16 19 14 4 10 12 9 |
0 1 2 3 10 6 5 18 16 9 15 19 11 13 8 17 14 4 12 7 |
0 1 2 3 11 6 19 12 4 8 14 9 18 16 5 15 17 13 10 7 |
0 1 2 3 16 13 19 8 4 9 12 10 18 7 11 5 15 17 14 6 |
0 1 2 3 16 15 9 4 14 7 11 8 10 6 18 13 19 17 5 12 |
0 1 2 3 19 7 5 4 14 9 6 12 16 15 17 11 18 10 13 8 |
0 1 2 3 19 12 5 4 18 17 9 7 13 15 10 14 11 8 16 6 |
0 1 2 4 5 3 15 11 14 18 12 19 7 13 8 17 10 9 16 6 |
0 1 2 4 5 12 15 13 7 11 14 10 19 16 8 18 3 9 17 6 |
0 1 2 4 5 15 13 17 10 3 9 18 7 19 14 11 8 16 12 6 | fuv: |
0 1 2 4 3 9 17 11 6 19 10 7 5 14 18 8 15 20 13 16 12 |
0 1 2 4 7 12 16 10 17 14 9 8 20 18 11 3 13 19 6 15 5 |
0 1 2 4 7 12 20 9 8 3 18 14 11 15 13 6 19 10 17 5 16 |
0 1 2 4 7 13 11 20 10 17 6 18 12 16 3 8 5 19 15 14 9 |
0 1 2 4 7 15 9 19 16 11 17 10 14 6 5 12 3 20 18 8 13 |
0 1 2 4 7 16 13 20 11 10 8 18 3 17 12 6 14 19 15 5 9 |
0 1 2 4 8 17 13 10 20 5 16 15 6 19 3 18 11 9 12 7 14 |
0 1 2 4 8 19 5 18 6 11 17 16 9 12 7 3 15 13 10 20 14 |
0 1 2 4 9 12 3 11 17 15 19 5 16 10 7 20 8 18 14 13 6 |
0 1 2 4 9 18 3 14 7 5 20 11 10 6 19 8 16 13 17 12 15 |
Listed below are the position mapping operator factors for values of m which are prime power products, and for values of c>2. Position mapping operator factors are given for m=12 and 15. These operators give the mapping
in which f00 is the lowest first column vector, and the position mapping operators ^Su and ^Dv are factored by components of the u and v vectors.
The position mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.
Note that for both m=12 and m=15,
so there are two first column vectors for each distinct multiplication table. For m=12 there are 12 multiplication tables and 24 first column vectors; for m=15 there are 32 multiplication tables and 64 first column vectors. However, each of first column vectors leads to a different standard form orthogonal array, because pairs of arrays from the same multiplication table include different sets of columns. (The columns are given by guv the first row vector.) Thus there are 24 and 64 standard form orthogonal arrays for m=12 and m=15 respectively.
The position mapping operator factor tables for m=prime power product and c>2 are as follows.
m: | 12 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | v0: | 0 | 1 | 2 | 3 | 4 | 5 | v1: | 0 | 1 | |
q: | 1 | 10 | |||||||||||
^Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 1 11 10 9 8 7 6 5 4 3 2 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 1 2 6 5 7 9 8 3 4 10 11 |
0 1 2 5 8 6 10 4 9 11 7 3 |
0 1 2 5 8 7 3 10 6 4 11 9 |
0 1 3 9 2 4 7 5 8 10 11 6 |
0 1 6 3 2 9 5 8 10 11 4 7 | ^Dv1: |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 1 8 4 3 10 6 7 2 9 5 11 |
m: | 15 | |||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | v0: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | |
q: | 1 | 13 | ||||||||||||||||||
^Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
0 1 14 13 12 11 10 9 8 7 6 5 4 3 2 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
0 1 2 8 9 10 11 12 13 14 3 4 5 6 7 |
0 1 2 12 9 8 10 4 3 11 13 6 5 7 14 |
0 1 4 11 5 12 2 8 9 13 7 6 14 10 3 |
0 1 4 6 2 7 3 12 8 11 14 10 5 9 13 |
0 1 4 6 14 7 3 12 2 13 9 5 10 8 11 |
0 1 9 4 14 6 5 13 12 10 2 8 7 11 3 |
0 1 9 6 2 4 5 11 10 14 13 8 3 12 7 |
0 1 13 4 3 12 10 6 9 7 2 8 14 11 5 |
0 1 13 9 14 5 7 3 11 4 6 2 12 10 8 |
0 1 13 9 7 3 11 4 6 14 5 2 12 10 8 |
0 1 13 9 5 10 14 11 3 7 2 6 4 8 12 |
0 1 13 11 4 9 3 12 14 7 8 6 2 5 10 |
0 1 13 11 14 9 2 6 4 12 3 7 5 10 8 |
0 1 13 11 14 6 4 12 3 7 9 2 5 10 8 |
0 1 13 5 10 14 7 8 6 2 11 4 9 3 12 | |
m: | 15 | (continued) | ||||||||||||||||||
v0: | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | ||||
^Dv0: |
0 1 3 2 7 13 5 4 6 10 11 14 9 8 12 |
0 1 3 4 9 8 13 14 2 10 11 5 12 6 7 |
0 1 3 4 5 12 9 8 13 14 2 10 11 6 7 |
0 1 3 11 7 8 5 6 14 4 9 12 13 2 10 |
0 1 14 13 11 10 9 6 2 4 5 8 3 12 7 |
0 1 14 11 9 12 4 8 3 13 2 6 7 10 5 |
0 1 14 8 7 6 9 4 3 2 10 11 12 13 5 |
0 1 11 3 7 14 6 4 8 10 5 9 13 2 12 |
0 1 11 8 3 14 7 10 9 4 6 13 12 2 5 |
0 1 6 14 9 13 8 10 12 4 5 3 11 2 7 |
0 1 6 14 12 4 5 3 11 8 10 9 13 2 7 |
0 1 10 2 14 13 12 9 11 6 7 8 3 4 5 |
0 1 10 2 14 13 12 6 7 8 3 4 9 11 5 |
0 1 10 4 12 6 5 2 9 8 11 14 13 3 7 |
0 1 7 6 9 4 3 14 8 2 10 11 12 13 5 |
0 1 12 2 10 3 7 8 13 4 11 6 9 14 5 |
This section illustrates that the selection of the plus vectors can affect the structure of the mapping operator factors when m is a prime power product and c>2.
Consider two alternate level representation arrays R'', for m=12 and m=15. Their values are listed below in comparison to their original definitions of R.
R''(0+) = R( |
0 6 3 9 4 10 7 1 8 2 11 5 | ) = |
0 2 3 1 0 2 3 1 0 2 3 1 |
0 0 0 0 1 1 1 1 2 2 2 2 | for m=12, | and R''(0+) = R( |
0 10 5 6 1 11 12 7 2 3 13 8 9 4 14 | ) = |
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 |
0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 | for m=15. |
The alternate level representation arrays R'' lead to alternate addition tables and alternate plus vectors and plus operators, as follows for m=12
0+ | 1+ | 2+ | 3+ | 4+ | 5+ | 6+ | 7+ | 8+ | 9+ | 10+ | 11+ | ||
+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7 8 9 10 11 |
0 1 2 3 4 5 6 7 8 9 10 11 |
1 0 3 2 5 4 7 6 9 8 11 10 |
2 3 0 1 6 7 4 5 10 11 8 9 |
3 2 1 0 7 6 5 4 11 10 9 8 |
4 5 6 7 8 9 10 11 0 1 2 3 |
5 4 7 6 9 8 11 10 1 0 3 2 |
6 7 4 5 10 11 8 9 2 3 0 1 |
7 6 5 4 11 10 9 8 3 2 1 0 |
8 9 10 11 0 1 2 3 4 5 6 7 |
9 8 11 10 1 0 3 2 5 4 7 6 |
10 11 8 9 2 3 0 1 6 7 4 5 |
11 10 9 8 3 2 1 0 7 6 5 4 |
and for m=15
0+ | 1+ | 2+ | 3+ | 4+ | 5+ | 6+ | 7+ | 8+ | 9+ | 10+ | 11+ | 12+ | 13+ | 14+ | ||
+ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
1 2 0 4 5 3 7 8 6 10 11 9 13 14 12 |
2 0 1 5 3 4 8 6 7 11 9 10 14 12 13 |
3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 |
4 5 3 7 8 6 10 11 9 13 14 12 1 2 0 |
5 3 4 8 6 7 11 9 10 14 12 13 2 0 1 |
6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 |
7 8 6 10 11 9 13 14 12 1 2 0 4 5 3 |
8 6 7 11 9 10 14 12 13 2 0 1 5 3 4 |
9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 |
10 11 9 13 14 12 1 2 0 4 5 3 7 8 6 |
11 9 10 14 12 13 2 0 1 5 3 4 8 6 7 |
12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 |
13 14 12 1 2 0 4 5 3 7 8 6 10 11 9 |
14 12 13 2 0 1 5 3 4 8 6 7 11 9 10 |
Searches with c=4 again yielded 24 first column vectors for m=12 and 64 first column vectors for m=15. The lowest first column vectors are
f''00 = |
0 1 2 5 11 7 10 4 6 3 8 9 | for m=12, and f''00 = |
0 1 3 4 9 11 14 10 8 5 13 2 6 12 7 | for m=15 |
They lead to the following multiplication tables for m=12
0x | 1x | 2x | 3x | 4x | 5x | 6x | 7x | 8x | 9x | 10x | 11x | ||
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7 8 9 10 11 |
0 0 0 0 0 0 0 0 0 0 0 0 |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 2 5 8 6 11 3 10 9 1 4 7 |
0 3 8 10 11 9 7 2 4 6 5 1 |
0 4 6 11 2 3 5 9 7 10 1 8 |
0 5 11 9 3 7 8 4 1 2 6 10 |
0 6 3 7 5 8 11 1 10 4 2 9 |
0 7 10 2 9 4 1 3 5 11 8 6 |
0 8 9 4 7 1 10 5 6 3 11 2 |
0 9 1 6 10 2 4 11 3 8 7 5 |
0 10 4 5 1 6 2 8 11 7 9 3 |
0 11 7 1 8 10 9 6 2 5 3 4 |
and for m=15
0x | 1x | 2x | 3x | 4x | 5x | 6x | 7x | 8x | 9x | 10x | 11x | 12x | 13x | 14x | ||
x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
0 2 10 6 12 11 8 13 9 7 4 1 5 14 3 |
0 3 6 4 9 13 12 1 5 11 8 14 7 2 10 |
0 4 12 9 11 2 7 3 13 14 5 10 1 6 8 |
0 5 11 13 2 4 14 8 3 6 1 12 10 9 7 |
0 6 8 12 7 14 5 2 11 1 9 3 13 10 4 |
0 7 13 1 3 8 2 12 10 4 14 9 6 5 11 |
0 8 9 5 13 3 11 10 1 2 7 6 14 4 12 |
0 9 7 11 14 6 1 4 2 10 13 8 3 12 5 |
0 10 4 8 5 1 9 14 7 13 12 2 11 3 6 |
0 11 1 14 10 12 3 9 6 8 2 5 4 7 13 |
0 12 5 7 1 10 13 6 14 3 11 4 2 8 9 |
0 13 14 2 6 9 10 5 4 12 3 7 8 11 1 |
0 14 3 10 8 7 4 11 12 5 6 13 9 1 2 |
Once again the position mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.
Note that for both m=12 and m=15,
so there are two first column vectors for each distinct multiplication table again.1 For m=12 there are 12 multiplication tables and 24 first column vectors; for m=15 there are 32 multiplication tables and 64 first column vectors. Again, each of first column vectors leads to a different standard form orthogonal array, because pairs of arrays from the same multiplication table include different sets of columns. And again there are 24 and 64 standard form orthogonal arrays for m=12 and m=15 respectively.
Although the ^Su operators are the same for the alternate choices of plus vectors, the structures of the ^Dv operators are different. As illustrated below, the ^Dv operators have more v components (factors) with fewer values, compared to those from the original plus vector definitions.
The alternate position mapping operator factor tables for m=prime power product and c>2 are as follows.
m: | 12 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | v0: | 0 | 1 | 2 | v1: | 0 | 1 | v2: | 0 | 1 | |
q: | 1 | 10 | |||||||||||
^Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 1 11 10 9 8 7 6 5 4 3 2 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 1 2 8 7 9 11 10 3 4 5 6 |
0 1 4 10 5 11 3 6 9 2 8 7 | ^Dv1: |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 1 2 11 5 4 8 10 6 9 7 3 | ^Dv2: |
0 1 2 3 4 5 6 7 8 9 10 11 |
0 1 9 3 6 8 4 7 5 2 10 11 |
m: | 15 | ||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
u0: | 0 | 1 | v0: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | v1: | 0 | 1 | 2 | 3 | |
q: | 1 | 13 | |||||||||||||||
^Su0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
0 1 14 13 12 11 10 9 8 7 6 5 4 3 2 | ^Dv0: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
0 1 2 12 9 11 4 5 13 10 14 6 3 7 8 |
0 1 3 11 5 4 10 2 7 14 12 9 13 8 6 |
0 1 3 2 5 12 9 6 13 14 4 10 7 11 8 |
0 1 3 6 4 2 9 12 13 5 10 7 11 14 8 |
0 1 3 6 5 10 4 2 9 12 13 7 11 14 8 |
0 1 9 3 11 5 14 13 4 7 2 12 10 8 6 |
0 1 9 3 11 5 14 10 8 13 4 7 2 12 6 | ^Dv1: |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
0 1 12 14 2 9 5 3 6 8 7 11 13 4 10 |
0 1 4 7 13 6 8 10 9 5 14 11 2 12 3 |
0 1 13 10 12 8 9 14 5 6 3 11 4 2 7 |
When m is a prime or a prime power, consider the mw levels h=0, 1, ..., mw-1, in which w=1, 2, ... As before, these levels form a group of order mw with the addition operation defined by the mw addition table. Here w is the log-order of the group because it is the base m logarithm of the order of the group:
Each of the levels h can be expressed uniquely in base m notation:
h | = sumt=0w-1(ht x mw-t-1) |
= h0 x mw-1 + h1 x mw-2 + ... + hw-1 |
in which ht can take any of the values 0, 1, ..., m-1, and the + and x operations are given by the mw addition and multiplication tables.
This level (from the set of mw levels) also may be expressed as the vector h whose components are ht for t=0, 1, ..., w-1.
The log-order w permutation vector of h is defined to be the vector product
in which the dot operator exponent (w-t-1 or t) indicates the number of times the dot operator is applied. There are w-1 dot operators, one cross operator, and one plus operator applied to each ht level. Thus,
1Ph | = h0 x+ |
---|---|
2Ph | = h0 .x+ * h1 x.+ |
3Ph | = h0 ..x+ * h1 .x.+ * h2 x..+ |
and so forth.
The log-order 2 permutation vectors for m=3 are listed below, for example. Each column lists an h level in base m notation above the corresponding permutation vector. Here the permutation vectors are expressed as vectors of plus vectors.
h: | 00 | 01 | 02 | 10 | 11 | 12 | 20 | 21 | 22 |
---|---|---|---|---|---|---|---|---|---|
2Ph: | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ |
0+ | 0+ | 0+ | 1+ | 1+ | 1+ | 2+ | 2+ | 2+ | |
0+ | 0+ | 0+ | 2+ | 2+ | 2+ | 1+ | 1+ | 1+ | |
0+ | 1+ | 2+ | 0+ | 1+ | 2+ | 0+ | 1+ | 2+ | |
0+ | 1+ | 2+ | 1+ | 2+ | 0+ | 2+ | 0+ | 1+ | |
0+ | 1+ | 2+ | 2+ | 0+ | 1+ | 1+ | 2+ | 0+ | |
0+ | 2+ | 1+ | 0+ | 2+ | 1+ | 0+ | 2+ | 1+ | |
0+ | 2+ | 1+ | 1+ | 0+ | 2+ | 2+ | 1+ | 0+ | |
0+ | 2+ | 1+ | 2+ | 1+ | 0+ | 1+ | 0+ | 2+ |
For each w, the mw permutation vectors form a group with the vector product operator. Each of these groups is isomorphic to the mw addition group. In the m=3, w=2 example, the vector product table is as follows.
* | 2P00 | 2P01 | 2P02 | 2P10 | 2P11 | 2P12 | 2P20 | 2P21 | 2P22 | |
---|---|---|---|---|---|---|---|---|---|---|
2P00 | 2P00 | 2P01 | 2P02 | 2P10 | 2P11 | 2P12 | 2P20 | 2P21 | 2P22 | |
2P01 | 2P01 | 2P02 | 2P00 | 2P11 | 2P12 | 2P10 | 2P21 | 2P22 | 2P20 | |
2P02 | 2P02 | 2P00 | 2P01 | 2P12 | 2P10 | 2P11 | 2P22 | 2P20 | 2P21 | |
2P10 | 2P10 | 2P11 | 2P12 | 2P20 | 2P21 | 2P22 | 2P00 | 2P01 | 2P02 | |
2P11 | 2P11 | 2P12 | 2P10 | 2P21 | 2P22 | 2P20 | 2P01 | 2P02 | 2P00 | |
2P12 | 2P12 | 2P10 | 2P11 | 2P22 | 2P20 | 2P21 | 2P02 | 2P00 | 2P01 | |
2P20 | 2P20 | 2P21 | 2P22 | 2P00 | 2P01 | 2P02 | 2P10 | 2P11 | 2P12 | |
2P21 | 2P21 | 2P22 | 2P20 | 2P01 | 2P02 | 2P00 | 2P11 | 2P12 | 2P10 | |
2P22 | 2P22 | 2P20 | 2P21 | 2P02 | 2P00 | 2P01 | 2P12 | 2P10 | 2P11 |
Comparison with the m2=9 addition table yields the same structure.
For arbitrary values of m, the isomorphism can be shown for w=2 as follows.
2Ph * 2Ph' | = | (h0 .x+ | * h1 x.+) | * (h'0 .x+ | * h'1 x.+) | by definition |
---|---|---|---|---|---|---|
= | h0 x0+ | * h1 x0+ | * h'0 x0+ | * h'1 x0+ | by expansion of the dot and cross vectors into their components | |
h0 x1+ | * h1 x0+ | * h'0 x1+ | * h'1 x0+ | |||
: | : | : | : | |||
h0 xm-1+ | * h1 x0+ | * h'0 xm-1+ | * h'1 x0+ | |||
h0 x0+ | * h1 x1+ | * h'0 x0+ | * h'1 x1+ | |||
h0 x1+ | * h1 x1+ | * h'0 x1+ | * h'1 x1+ | |||
: | : | : | : | |||
h0 xm-1+ | * h1 x1+ | * h'0 xm-1+ | * h'1 x1+ | |||
: | : | : | : | |||
h0 x0+ | * h1 xm-1+ | * h'0 x0+ | * h'1 xm-1+ | |||
h0 x1+ | * h1 xm-1+ | * h'0 x1+ | * h'1 xm-1+ | |||
: | : | : | : | |||
h0 xm-1+ | * h1 xm-1+ | * h'0 xm-1+ | * h'1 xm-1+ | |||
= | (h0 x0 | + h'0 x0)+ | * (h1 x0 | + h'1 x0)+ | by commuting the middle two factors (vector products of plus vectors are abelian) and by the plus vectors' isomorphism with addition | |
(h0 x1 | + h'0 x1)+ | * (h1 x0 | + h'1 x0)+ | |||
: | : | : | : | |||
(h0 xm-1 | + h'0 xm-1)+ | * (h1 x0 | + h'1 x0)+ | |||
(h0 x0 | + h'0 x0)+ | * (h1 x1 | + h'1 x1)+ | |||
(h0 x1 | + h'0 x1)+ | * (h1 x1 | + h'1 x1)+ | |||
: | : | : | : | |||
(h0 xm-1 | + h'0 xm-1)+ | * (h1 x1 | + h'1 x1)+ | |||
: | : | : | : | |||
(h0 x0 | + h'0 x0)+ | * (h1 xm-1 | + h'1 xm-1)+ | |||
(h0 x1 | + h'0 x1)+ | * (h1 xm-1 | + h'1 xm-1)+ | |||
: | : | : | : | |||
(h0 xm-1 | + h'0 xm-1)+ | * (h1 xm-1 | + h'1 xm-1)+ | |||
= | (h0 + h'0)x+ | * (h1 x0 + h'1 x0).+ | by addition of the cross vectors and collection of their components on the left, and by collection of the dot vector components on the right | |||
(h0 + h'0)x+ | * (h1 x1 + h'1 x1).+ | |||||
: | : | |||||
(h0 + h'0)x+ | * (h1 xm-1 + h'1 xm-1).+ | |||||
= | (h0 + h'0).x+ | * (h1 + h'1)x.+ | by collection of the dot vector components on the left, and by addition of the cross vectors and collection of their components on the right | |||
= | 2Ph+h' |
Each of the permutation vectors is a vector of plus vectors, so a set of mw reduced permutation vectors wPh can be defined. Here the minus operator is the inverse of the plus operator: It replaces each plus vector h+ with the corresponding level h=0, ..., m-1. In the m=3, w=2 example, the reduced permutation vectors are as follows. Each column lists an h level in base m notation above the corresponding reduced permutation vector.
h: | 00 | 01 | 02 | 10 | 11 | 12 | 20 | 21 | 22 |
---|---|---|---|---|---|---|---|---|---|
2Ph: | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | |
0 | 0 | 0 | 2 | 2 | 2 | 1 | 1 | 1 | |
0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | |
0 | 1 | 2 | 1 | 2 | 0 | 2 | 0 | 1 | |
0 | 1 | 2 | 2 | 0 | 1 | 1 | 2 | 0 | |
0 | 2 | 1 | 0 | 2 | 1 | 0 | 2 | 1 | |
0 | 2 | 1 | 1 | 0 | 2 | 2 | 1 | 0 | |
0 | 2 | 1 | 2 | 1 | 0 | 1 | 0 | 2 |
Selected permutation vectors are tabulated in an appendix as plus vectors. So the corresponding reduced permutation vectors are apparent from the same tables, by ignoring the plus operators.
A later section will use vector products of reduced permutation vectors. The products can be tabulated according to the vector product definition, and observation of the product tables suggests the identity
in which
h0 | = h'0 x h''0 | and |
ht | = h't x h''0 + h''t | if t>0 |
The vector product table for the m=3, w=2 reduced permutation vectors is as follows.
* | 2P00 | 2P01 | 2P02 | 2P10 | 2P11 | 2P12 | 2P20 | 2P21 | 2P22 | |
---|---|---|---|---|---|---|---|---|---|---|
2P00 | 2P00 | 2P01 | 2P02 | 2P00 | 2P01 | 2P02 | 2P00 | 2P01 | 2P02 | |
2P01 | 2P00 | 2P01 | 2P02 | 2P01 | 2P02 | 2P00 | 2P02 | 2P00 | 2P01 | |
2P02 | 2P00 | 2P01 | 2P02 | 2P02 | 2P00 | 2P01 | 2P01 | 2P02 | 2P00 | |
2P10 | 2P00 | 2P01 | 2P02 | 2P10 | 2P11 | 2P12 | 2P20 | 2P21 | 2P22 | |
2P11 | 2P00 | 2P01 | 2P02 | 2P11 | 2P12 | 2P10 | 2P22 | 2P20 | 2P21 | |
2P12 | 2P00 | 2P01 | 2P02 | 2P12 | 2P10 | 2P11 | 2P21 | 2P22 | 2P20 | |
2P20 | 2P00 | 2P01 | 2P02 | 2P20 | 2P21 | 2P22 | 2P10 | 2P11 | 2P12 | |
2P21 | 2P00 | 2P01 | 2P02 | 2P21 | 2P22 | 2P20 | 2P12 | 2P10 | 2P11 | |
2P22 | 2P00 | 2P01 | 2P02 | 2P22 | 2P20 | 2P21 | 2P11 | 2P12 | 2P10 |
Note that the identity element for the vector product is
(The dot operator exponent w-1 indicates the number of times the dot operator is applied. The 0 in the last expression wP10 is the w-1 order 0 vector, so the identity element is given in base m notation.) Elements with levels h greater than or equal to mw-1 form a group with the vector product.
Also note the following recursion relations for level h and its associated base m, w order vector h. (The expressions on the right are in base m notation. The last expression contains the w order 0 vector.)
wPh. | = | w+1Ph | = | w+1P0h |
---|---|---|---|---|
wPh | = | w+1P(mw + h) | = | w+1P1h |
h0.wx | = | w+1P(h0 x mw) | = | w+1Ph00 |
Examination of the mw permutation vectors leads to the observation that they form an mw+1-by-mw orthogonal array1 of strength l=2 and index mw-1. The orthogonal array is given by
in which ascending permutation vectors form the array columns. In the m=3, w=2 example, expansion of the permutation vectors yields the following orthogonal array.
h: | 00 | 01 | 02 | 10 | 11 | 12 | 20 | 21 | 22 |
---|---|---|---|---|---|---|---|---|---|
2Ph: |
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 1 2 0 1 2 0 1 2 1 2 0 1 2 0 1 2 0 2 0 1 2 0 1 2 0 1 |
0 1 2 0 1 2 0 1 2 2 0 1 2 0 1 2 0 1 1 2 0 1 2 0 1 2 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 |
0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 2 0 |
0 1 2 1 2 0 2 0 1 2 0 1 0 1 2 1 2 0 1 2 0 2 0 1 0 1 2 |
0 1 2 2 0 1 1 2 0 0 1 2 2 0 1 1 2 0 0 1 2 2 0 1 1 2 0 |
0 1 2 2 0 1 1 2 0 1 2 0 0 1 2 2 0 1 2 0 1 1 2 0 0 1 2 |
0 1 2 2 0 1 1 2 0 2 0 1 1 2 0 0 1 2 1 2 0 0 1 2 2 0 1 |
In this example, each pair of columns contains each pair of levels exactly 3 times.
The mw+1-by-mw orthogonal arrays resulting from the permutation vectors can be used to find r-by-mw covering arrays1, in which r<mw+1. The formula given here for strength l=2 covering arrays is the result of using the cats program from the Constrained Array Test System2 to remove redundant rows from the orthogonal arrays of permutation vectors. I.e. a logical derivation of the formula from the permutation vectors is not given here. The formula is instead a description of search results which fit the formula's pattern. The covering properties of the resulting arrays are illustrated below however.
The covering array wG is a w order vector of subarrays. The components wGs (s=1, ..., w) are
Thus, wG is an m2+m(m-1)(w-1)-by-mw covering array:
wG1 | m2-by-mw subarray | |||
---|---|---|---|---|
wG | = | wG2 | m(m-1)-by-mw subarray | |
: | : | |||
wGw | m(m-1)-by-mw subarray |
The component subarrays are
wGs | = | 0(')+·s-1 x ·w-s+ |
---|
in which
0(')+ | = | 0+ | if s=1, and |
---|---|---|---|
0(')+ | = | 0'+ | if s>1. |
The apostrophe after the 0 indicates the initial 0 level is omitted from the plus vector (because it leads to redundant rows). Thus,
0'+ | = |
1 : m-1 |
---|
Again, the dot operator exponent (s-1 or w-s) indicates the number of times the dot operator is applied. There are w-1 raised dot operators and one raised cross operator applied to each plus vector level. Finally the plus operator is applied to each of the resulting array elements.
In the m=3, w=2 example the formula is evaluated as follows.
2G | = | 2G1 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
2G2 | ||||||||||
= | 0+x·+ | |||||||||
0'+·x+ | ||||||||||
= | 0x·+ | |||||||||
1x·+ | ||||||||||
2x·+ | ||||||||||
1·x+ | ||||||||||
2·x+ | ||||||||||
= | 0·+ | 0·+ | 0·+ | |||||||
0·+ | 1·+ | 2·+ | ||||||||
0·+ | 2·+ | 1·+ | ||||||||
1x+ | 1x+ | 1x+ | ||||||||
2x+ | 2x+ | 2x+ | ||||||||
= | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | |
0+ | 0+ | 0+ | 1+ | 1+ | 1+ | 2+ | 2+ | 2+ | ||
0+ | 0+ | 0+ | 2+ | 2+ | 2+ | 1+ | 1+ | 1+ | ||
0+ | 1+ | 2+ | 0+ | 1+ | 2+ | 0+ | 1+ | 2+ | ||
0+ | 2+ | 1+ | 0+ | 2+ | 1+ | 0+ | 2+ | 1+ | ||
= |
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 |
0 1 2 0 1 2 0 1 2 1 2 0 2 0 1 |
0 1 2 0 1 2 0 1 2 2 0 1 1 2 0 |
0 1 2 1 2 0 2 0 1 0 1 2 0 1 2 |
0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 |
0 1 2 1 2 0 2 0 1 2 0 1 1 2 0 |
0 1 2 2 0 1 1 2 0 0 1 2 0 1 2 |
0 1 2 2 0 1 1 2 0 1 2 0 2 0 1 |
0 1 2 2 0 1 1 2 0 2 0 1 1 2 0 |
The covering of the wG array is illustrated as follows. Consider the mw-1 subarrays formed from each set of m contiguous columns of wG. Each of these m-column subarrays covers the m2 level pairs because its first m rows from the wG1 subarray together with the last m(m-1) rows from the wGw subarray form an m2-by-m orthogonal array with index one.
Now consider the mw-2 m2-column subarrays formed from each set of m contiguous m-column subarrays. Each of the m2-column subarrays covers the m2 level pairs because
This process is repeated with fewer but wider subarrays until all mw columns are included. That is, for each of the mw-s ms-column subarrays (s=1, ..., w), pairs of columns from the m different ms-1-column subarrays cover the m2 level pairs using the first m rows from the wG1 subarray together with the last m(m-1) rows from the wGw-s+1 subarray.
It is possible to increase the number of wG covering array columns from mw to
without increasing the number of rows from
by including the solution at infinity (t=0) with solutions for tG, t=1, ..., w.1
The covering array wH is a w-by-w+1 array of subarrays wHs,t in which the row position is s=1, ..., w, and the column position is t=0, ..., w. The subarrays are given by
wHs,t = | 0(').·t. | if s<w-t. |
---|---|---|
wHs,t = | 0(')+·t. | if s=w-t. |
wHs,t = | 0(')+·s+t-w-1 x ·w-s+ | if s>w-t. |
Here
0('). | = | 0. | if s=1. |
---|---|---|---|
0('). | = | 0'. | if s>1. |
0(')+ | = | 0+ | if s=1. |
0(')+ | = | 0'+ | if s>1. |
The apostrophe after the 0 indicates the initial 0 level is omitted from the dot vector and from the plus vector (because it leads to redundant rows). Thus,
0'. | = | 0.{m-1/} | and | 0'+ | = |
1 : m-1 |
---|
Again, the dot operator exponent (t, s+t-w-1, or w-s) indicates the number of times the dot operator is applied.
In the m=3, w=2 example the formula is evaluated as follows.
2H | = | 2H1,0 | 2H1,1 | 2H1,2 | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
2H2,0 | 2H2,1 | 2H2,2 | |||||||||||||
= | 0.. | 0+·. | 0+x·+ | ||||||||||||
0'+. | 0'+x+ | 0'+·x+ | |||||||||||||
= | 0. | 0·. | 0x·+ | ||||||||||||
0. | 1·. | 1x·+ | |||||||||||||
0. | 2·. | 2x·+ | |||||||||||||
1. | 1x+ | 1·x+ | |||||||||||||
2. | 2x+ | 2·x+ | |||||||||||||
= | 0. | 0. | 0. | 0. | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | ||
0. | 1. | 1. | 1. | 0+ | 0+ | 0+ | 1+ | 1+ | 1+ | 2+ | 2+ | 2+ | |||
0. | 2. | 2. | 2. | 0+ | 0+ | 0+ | 2+ | 2+ | 2+ | 1+ | 1+ | 1+ | |||
1. | 0+ | 1+ | 2+ | 0+ | 1+ | 2+ | 0+ | 1+ | 2+ | 0+ | 1+ | 2+ | |||
2. | 0+ | 2+ | 1+ | 0+ | 2+ | 1+ | 0+ | 2+ | 1+ | 0+ | 2+ | 1+ | |||
= |
0 0 0 0 0 0 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 0 0 1 1 1 2 2 2 1 2 0 2 0 1 |
0 0 0 1 1 1 2 2 2 2 0 1 1 2 0 |
0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 |
0 1 2 0 1 2 0 1 2 1 2 0 2 0 1 |
0 1 2 0 1 2 0 1 2 2 0 1 1 2 0 |
0 1 2 1 2 0 2 0 1 0 1 2 0 1 2 |
0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 |
0 1 2 1 2 0 2 0 1 2 0 1 1 2 0 |
0 1 2 2 0 1 1 2 0 0 1 2 0 1 2 |
0 1 2 2 0 1 1 2 0 1 2 0 2 0 1 |
0 1 2 2 0 1 1 2 0 2 0 1 1 2 0 |
For larger values of w, the wHs,t subarrays are arranged as follows.
t: | 0 | 1 | ... | w-2 | w-1 | w | |
---|---|---|---|---|---|---|---|
s: | 1 | 0.. | 0.·. | ... | 0.·w-2. | 0+·w-1. | 0+x ·w-1+ |
2 | 0'.. | 0'.·. | ... | 0'+·w-2. | 0'+x ·w-2+ | 0'+· x ·w-2+ | |
3 | 0'.. | 0'.·. | ... | 0'+x ·w-3+ | 0'+· x ·w-3+ | 0'+·· x ·w-3+ | |
: | : | : | : | : | : | ||
w-1 | 0'.. | 0'+·. | ... | 0'+·w-4 x ·+ | 0'+·w-3 x ·+ | 0'+·w-2 x ·+ | |
w | 0'+. | 0'+x+ | ... | 0'+·w-3 x+ | 0'+·w-2 x+ | 0'+·w-1 x+ |
Subarrays with s=w-t are shown on the shaded diagonal. Subarrays with s<w-t are above and to the left of the shaded diagonal; subarrays with s>w-t are below and to the right.
The covering of the wH array is illustrated as follows.
wH1,t | |
---|---|
wHt = | wH2,t |
: | |
wHw,t |
for t=1, ..., w. (t=0 is not considered because it has only one column.) Each of these mt-column subarrays covers the m2 level pairs because it contains all the rows of the tG covering array.
and since only integer values of t<w are under consideration, the minimum value of w-t=1. Thus s>w-t implies s>1, and
Now
tGs+t-w | = | 0(')+·s+t-w-1 x ·w-s+ | |
---|---|---|---|
= | 0+·s+t-w-1 x ·w-s+ | if s+t-w=1 or s=w-t+1 | |
0'+·s+t-w-1 x ·w-s+ | if s+t-w>1 or s>w-t+1 |
For values of s>w-t+1 (greater than the lowest value)
and wHs,t contains all the rows of the subarray tGs+t-w from the tG covering array. But for the lowest value of s=w-t+1, wHs,t contains all the rows of tGs+t-w except for those resulting from the initial 0 level of the plus vector in the
expression. The missing rows are given by the
expressions. There are m missing rows consisting of mt columns. All the elements of each row are one of the m levels 0, 1, ..., m-1. Examination of the expressions in the wHs,t definition indicates:
Thus for t<w, wHt contains all the rows of the tG covering array.
wHs,t | = | 0(')+·s+t-w-1 x ·w-s+ |
---|---|---|
= | 0(')+·s-1 x ·w-s+ | |
= | wGs |
Since each of the w subarrays wHt (t=1, ..., w) contains the rows of the covering array tG, each wHt subarray is a covering array itself.
contains an m-by-mt subarray of each of the nonzero levels. Each column of a particular level is paired with a plus vector in the subarrays to the right:
(t'>t). Since the plus vectors contain all m levels, each nonzero level from any wHs=w-t,t column is paired with each of the levels in any column of the wHs>w-t',t' subarray.
contains an m-by-mt subarray of the zero level. Each column of the subarray is paired with a plus vector in the subarray to the right (t'=w). Since the plus vectors contain all m levels, a zero level from any column of wH1,t=w-1 is paired with each of the nonzero levels in any column of the wH1,t'=w subarray.
whose last m(m-1) rows pair zero levels with each of the nonzero levels in any wHs=w-t-1,t' subarray as follows.
contains rows of all the nonzero levels in its last m(m-1) rows. Thus any pair of columns from wHs=w-t-1,t and wHs=w-t',t'=t+1 will cover the zero-nonzero level pairs.
the subarray
which consists of plus vectors. Thus, the zero levels from any column of wHs=w-t-1,t are paired with each of the m levels of any column of the wHs=w-t-1,t'>t+1 subarray.
Since all nonzero levels and zero levels from the wHt columns are paired with all levels from wHt' columns, all m2 level pairs are covered by columns from different wHt subarrays.
Because all pairs of columns within and between the wHt subarrays cover the m2 level pairs, wH is a covering array.
The earlier formulation for orthogonal arrays of strength l=2 and index one can be extended to w=1 covering arrays as follows.
is an m2-by-c covering array. As before,
and
so
is an m2-by-c+1 covering array. These formulas are general in that they apply to values of m which are prime power products.
For n>c+1, covering arrays for values of m which are not primes or prime powers can be constructed from covering arrays with more levels (m'>m) using a sliding levels technique described here.
Consider an m'>m order vector A. The m'-to-m sliding level operator is defined to be the level mapping operator which leaves levels less than m unchanged and which maps greater levels to m-1. The operator applied to A is
Am/m' = A * ( |
0 1 : m-1 : m-1 | ) |
---|
The operator applied to an array of vectors Aik yields an array of vector products:
Aik m/m' = Aik * ( |
0 1 : m-1 : m-1 | ) |
---|
When applied to a covering array (e.g. wG or wH), the sliding level operator also implies the omission of rows m to m'-1 from the top row of vectors, because these rows are the same as row m-1, and are therefore redundant. (Note the top row of vectors consists of 0. and 0+ vectors in the formulas given here.) The omission of rows m to m'-1 is explicitly noted with an apostrophe, using
in the top row of vectors, as appropriate.
For a given value of m and an associated maximum number of columns n, consider a larger value m'>m for which there is a covering array with a number of columns n'>n. If wH is the covering array for m', wHm/m' is a covering array for m. Compared to wH, wHm/m' has m'-m fewer rows and the same number of columns.
Consider for example m=6. There is a 36-by-3 covering array 1H as follows.
1H = 0+. g00 x+ = 0+. 0+{2/}x+ = 0+. 0+x{2/}+ = | 0. | 0+ | 0+ | = |
0 0 0 0 0 0 |
0 1 2 3 4 5 |
0 1 2 3 4 5 |
---|---|---|---|---|---|---|---|
1. | 0+ | 1+ |
1 1 1 1 1 1 |
0 1 2 3 4 5 |
1 2 3 4 5 0 | ||
2. | 0+ | 2+ |
2 2 2 2 2 2 |
0 1 2 3 4 5 |
2 3 4 5 0 1 | ||
3. | 0+ | 3+ |
3 3 3 3 3 3 |
0 1 2 3 4 5 |
3 4 5 0 1 2 | ||
4. | 0+ | 4+ |
4 4 4 4 4 4 |
0 1 2 3 4 5 |
4 5 0 1 2 3 | ||
5. | 0+ | 5+ |
5 5 5 5 5 5 |
0 1 2 3 4 5 |
5 0 1 2 3 4 |
Additional factors can be covered with a 48-by-8 covering array 1H6/7 as follows.
1H6/7 = | 0+. 6/7 | 0+x+ 6/7 | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
= | 0.' 6/7 | 0+' 6/7 | 0+' 6/7 | 0+' 6/7 | 0+' 6/7 | 0+' 6/7 | 0+' 6/7 | 0+' 6/7 | = |
0 0 0 0 0 0 |
0 1 2 3 4 5 |
0 1 2 3 4 5 |
0 1 2 3 4 5 |
0 1 2 3 4 5 |
0 1 2 3 4 5 |
0 1 2 3 4 5 |
0 1 2 3 4 5 |
1. 6/7 | 0+ 6/7 | 1+ 6/7 | 2+ 6/7 | 3+ 6/7 | 4+ 6/7 | 5+ 6/7 | 6+ 6/7 |
1 1 1 1 1 1 1 |
0 1 2 3 4 5 5 |
1 2 3 4 5 5 0 |
2 3 4 5 5 0 1 |
3 4 5 5 0 1 2 |
4 5 5 0 1 2 3 |
5 5 0 1 2 3 4 |
5 0 1 2 3 4 5 | ||
2. 6/7 | 0+ 6/7 | 2+ 6/7 | 4+ 6/7 | 6+ 6/7 | 1+ 6/7 | 3+ 6/7 | 5+ 6/7 |
2 2 2 2 2 2 2 |
0 1 2 3 4 5 5 |
2 3 4 5 5 0 1 |
4 5 5 0 1 2 3 |
5 0 1 2 3 4 5 |
1 2 3 4 5 5 0 |
3 4 5 5 0 1 2 |
5 5 0 1 2 3 4 | ||
3. 6/7 | 0+ 6/7 | 3+ 6/7 | 6+ 6/7 | 2+ 6/7 | 5+ 6/7 | 1+ 6/7 | 4+ 6/7 |
3 3 3 3 3 3 3 |
0 1 2 3 4 5 5 |
3 4 5 5 0 1 2 |
5 0 1 2 3 4 5 |
2 3 4 5 5 0 1 |
5 5 0 1 2 3 4 |
1 2 3 4 5 5 0 |
4 5 5 0 1 2 3 | ||
4. 6/7 | 0+ 6/7 | 4+ 6/7 | 1+ 6/7 | 5+ 6/7 | 2+ 6/7 | 6+ 6/7 | 3+ 6/7 |
4 4 4 4 4 4 4 |
0 1 2 3 4 5 5 |
4 5 5 0 1 2 3 |
1 2 3 4 5 5 0 |
5 5 0 1 2 3 4 |
2 3 4 5 5 0 1 |
5 0 1 2 3 4 5 |
3 4 5 5 0 1 2 | ||
5. 6/7 | 0+ 6/7 | 5+ 6/7 | 3+ 6/7 | 1+ 6/7 | 6+ 6/7 | 4+ 6/7 | 2+ 6/7 |
5 5 5 5 5 5 5 |
0 1 2 3 4 5 5 |
5 5 0 1 2 3 4 |
3 4 5 5 0 1 2 |
1 2 3 4 5 5 0 |
5 0 1 2 3 4 5 |
4 5 5 0 1 2 3 |
2 3 4 5 5 0 1 | ||
6. 6/7 | 0+ 6/7 | 6+ 6/7 | 5+ 6/7 | 4+ 6/7 | 3+ 6/7 | 2+ 6/7 | 1+ 6/7 |
5 5 5 5 5 5 5 |
0 1 2 3 4 5 5 |
5 0 1 2 3 4 5 |
5 5 0 1 2 3 4 |
4 5 5 0 1 2 3 |
3 4 5 5 0 1 2 |
2 3 4 5 5 0 1 |
1 2 3 4 5 5 0 |
To cover more factors the process can be continued similarly. For m=6 a few of the arrays are as follows.
1H | 36-by-3 |
---|---|
1H6/7 | 48-by-8 |
1H6/8 | 62-by-9 |
1H6/9 | 78-by-10 |
2H6/7 | 90-by-57 |
2H6/8 | 118-by-73 |
Note that this sliding levels technique is general in that it depends on m being less than m', but there is no requirement for either m or m' to be a prime or a prime power. For example, there is a 24-by-6 covering array 1H4/5 for m=4; there is a 224-by-5 covering array 1H14/15 for m=14, etc.
A zero sum array is an ml-by-l+1 orthogonal array of index one and strength l, in which l and m can be any positive integers. The array can be constructed from an ml-by-l subarray of the ml rows of distinct l-tuples of levels, with an additional column whose elements are chosen so each row sums to zero.
Zero sum arrays can be constructed from the permutation vectors as follows. First generalize the permutation vector definition to include any positive integer m, and let
so that w=0, 1, ... Next define the mw+1-by-w+2 array wE in terms of its elements wEjk for j=0, ..., mw+1-1 and k=0, ..., w+1:
wEjk = | wP0 j | if k=0. |
wPmk j | if 0<k<w+1. | |
0 - sumk'=0w(wEjk')addition table | if k=w+1. |
wE is a zero sum array for strength l=w+1.
In the m=3, w=2 example, with base 3 notation,
2E | = | 2P00 | 2P01 | 2P10 | 0. 2. 1. 2. 1. 0. 1. 0. 2. |
---|---|---|---|---|---|
0+ | 0+ | 0+ | 0. | ||
0+ | 0+ | 1+ | 2. | ||
0+ | 0+ | 2+ | 1. | ||
0+ | 1+ | 0+ | 2. | ||
= | 0+ | 1+ | 1+ | 1. | |
0+ | 1+ | 2+ | 0. | ||
0+ | 2+ | 0+ | 1. | ||
0+ | 2+ | 1+ | 0. | ||
0+ | 2+ | 2+ | 2. |
Generally wE can be expressed in terms of its column vectors wEk as described below. First, for each of the m levels h=0, 1, ..., m-1, define the zero sum vector h[w] by the vector sum
Note that the vector components are added according to the addition table, so
h[w]j | = h.j - sumk=0w(0+j)addition table |
= h - sumk=0w(j)addition table |
for j=0, 1, ..., m-1. Also, when w>m-1, the sum can stop at wmod m because all the elements in the addition table have orders dividing m. This means that for each level h, there are at most m zero sum vectors. And if m is a prime power (pa), the sum can stop at wmod p. In this case there are up to p zero sum vectors for each level h.
In the m=3 example, the zero sum vectors are:
h[0]: | 0[0] | 1[0] | 2[0] | h[1]: | 0[1] | 1[1] | 2[1] | h[2]: | 0[2] | 1[2] | 2[2] | ||
0 2 1 |
1 0 2 |
2 1 0 |
0 1 2 |
1 2 0 |
2 0 1 |
0 0 0 |
1 1 1 |
2 2 2 |
The zero sum operator acts on an array to replace each element with its corresponding zero sum vector. The result is an array with m times the number of rows compared to the original array. Thus,
0[0][0] = | 0[0] 2[0] 1[0] |
= |
0 2 1 2 1 0 1 0 2 |
Now the zero sum array wE is expressed in terms of its column vectors as follows.
wEk = | 0.w + | if k=0. |
---|---|---|
0.k-1 + .w-k + | if 0<k<w+1. | |
0[0]w[w] | if k=w+1. |
Examples of zero sum arrays are given in the following table. The reference tables in an appendix give the associated formulas, vectors, and levels for these arrays.
Zero Sum Covering Arrays | |||||||
---|---|---|---|---|---|---|---|
Strength | Number of Levels | Number of Rows | Number of Columns | Array | Reference Tables | ||
l | m | r | n | ||||
2 | 2 | 4 | 3 | 1E | formula | vectors | levels |
2 | 3 | 9 | 3 | 1E | formula | vectors | levels |
2 | 4 | 16 | 3 | 1E | formula | vectors | levels |
3 | 2 | 8 | 4 | 2E | formula | vectors | levels |
3 | 3 | 27 | 4 | 2E | formula | vectors | levels |
3 | 4 | 64 | 4 | 2E | formula | vectors | levels |
3 | 6 | 216 | 4 | 2E | formula | vectors | levels |
4 | 2 | 16 | 5 | 3E | formula | vectors | levels |
4 | 3 | 81 | 5 | 3E | formula | vectors | levels |
4 | 4 | 256 | 5 | 3E | formula | vectors | levels |
Note that when m is a prime (p) or a prime power (pa), the addition table sum in the zero sum vector expression can be replaced with a product from the multiplication table:
h[w]j | = h - sumk=0w(j)addition table |
= h - (w+1)mod p x j |
Moreover, the zero sum vectors h[w] are the columns in the array
0+[w] = ( -(w+1)mod p )x+ |
---|
This section describes a recursive covering array construction for strength l=3 and number of levels m=2.
Consider the array wI for w=0, 1, ... Define
0I = 2P | and | 0I' = 2G |
---|
w+1I and w+1I' are both 2-by-2 arrays of arrays given by
w+1I = | wI | wI | and | w+1I' = | wI' | wI' |
---|---|---|---|---|---|---|
wI' | wI' | 0·(w+1)+ | 1·(w+1)+ |
Here the underline in wI' indicates that all the order 2 vectors in wI' are replaced by their vector products with the 1+ vector. The effect is a transposition of levels 0 and 1 because wI' is comprised of vectors 0+ and 1+ only.
The following examples illustrate the construction of wI for w=0, 1, and 2.
When w=0,
0I | = | 2P | |||
---|---|---|---|---|---|
= | 0+ | 0+ | 0+ | 0+ | |
0+ | 0+ | 1+ | 1+ | ||
0+ | 1+ | 0+ | 1+ | ||
0+ | 1+ | 1+ | 0+ |
0I is a covering array for strength l=3 because in this case 2P=2E, a zero sum array.
When w=1,
1I | = | 0I | 0I | ||||||
---|---|---|---|---|---|---|---|---|---|
0I' | 0I' | ||||||||
= | 2P | 2P | |||||||
2G | 2G | ||||||||
= | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | |
0+ | 0+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | ||
0+ | 1+ | 0+ | 1+ | 0+ | 1+ | 0+ | 1+ | ||
0+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | 0+ | ||
0+ | 0+ | 0+ | 0+ | 1+ | 1+ | 1+ | 1+ | ||
0+ | 0+ | 1+ | 1+ | 1+ | 1+ | 0+ | 0+ | ||
0+ | 1+ | 0+ | 1+ | 1+ | 0+ | 1+ | 0+ |
1I contains two subarrays consisting of the left four columns and the right four columns. Each of the subarrays
2P | and | 2P |
---|---|---|
2G | 2G |
covers its four columns with strength l=3 because it contains 2P. Now the top three rows of vectors in 2P are the same as 2G, so they cover the subarrays with strength l=2 also. In each of the top three rows of vectors, each of the element pairs in 2G is associated with a level, 0 or 1, to form 3-tuples in the same row of the other subarray. To cover all the 3-tuples spanning the subarrays, each of the 2G pairs is combined with the other level of the other subarray in the bottom three rows of vectors. This is accomplished by applying 1+ mapping operators to the plus vectors of 2G to form 2G in the right subarray. The result is six rows of vectors in 1I are the same as those of
1G = | 0+ 0+ | 0+ 1+ |
---|
with 0+ replaced by 2G and 1+ replaced by 2G:
2G | 2G |
---|---|
2G | 2G |
This construction covers the 3-tuples spanning the left and right subarrays. Since all the 3-tuples within and spanning the subarrays are covered, 1I covers all eight columns with strength l=3.
When w=2,
2I | = | 1I | 1I | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1I' | 1I' | ||||||||||||||||
= | 2P | 2P | 2P | 2P | |||||||||||||
2G | 2G | 2G | 2G | ||||||||||||||
2G | 2G | 2G | 2G | ||||||||||||||
0··+ | 1··+ | 1··+ | 0··+ | ||||||||||||||
= | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | |
0+ | 0+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | ||
0+ | 1+ | 0+ | 1+ | 0+ | 1+ | 0+ | 1+ | 0+ | 1+ | 0+ | 1+ | 0+ | 1+ | 0+ | 1+ | ||
0+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | 0+ | ||
0+ | 0+ | 0+ | 0+ | 1+ | 1+ | 1+ | 1+ | 0+ | 0+ | 0+ | 0+ | 1+ | 1+ | 1+ | 1+ | ||
0+ | 0+ | 1+ | 1+ | 1+ | 1+ | 0+ | 0+ | 0+ | 0+ | 1+ | 1+ | 1+ | 1+ | 0+ | 0+ | ||
0+ | 1+ | 0+ | 1+ | 1+ | 0+ | 1+ | 0+ | 0+ | 1+ | 0+ | 1+ | 1+ | 0+ | 1+ | 0+ | ||
0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 0+ | 1+ | 1+ | 1+ | 1+ | 1+ | 1+ | 1+ | 1+ | ||
0+ | 0+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | 1+ | 1+ | 0+ | 0+ | 1+ | 1+ | 0+ | 0+ | ||
0+ | 1+ | 0+ | 1+ | 0+ | 1+ | 0+ | 1+ | 1+ | 0+ | 1+ | 0+ | 1+ | 0+ | 1+ | 0+ | ||
0+ | 0+ | 0+ | 0+ | 1+ | 1+ | 1+ | 1+ | 1+ | 1+ | 1+ | 1+ | 0+ | 0+ | 0+ | 0+ |
2I contains four subarrays, each consisting of four contiguous columns. Each of the subarrays covers its four columns with strength l=3 because it contains 2P. Next note that 2I contains nine rows of vectors that are the same as those of
2G = | 0+ 0+ 0+ |
0+ 0+ 1+ |
0+ 1+ 0+ |
0+ 1+ 1+ |
---|
with 0+ and 1+ replaced by 2G and 2G respectively:
2G | 2G | 2G | 2G |
---|---|---|---|
2G | 2G | 2G | 2G |
2G | 2G | 2G | 2G |
This construction covers the 3-tuples spanning pairs of subarrays because all pairs of subarrays contain 2G paired with 2G and with 2G.
Now consider the four rows of vectors in 2I from the first rows of the 2P, 2G, and 2G subarrays, and from the last row of vectors in 2I. These rows are
0··+ | 0··+ | 0··+ | 0··+ |
---|---|---|---|
0··+ | 1··+ | 0··+ | 1··+ |
0··+ | 0··+ | 1··+ | 1··+ |
0··+ | 1··+ | 1··+ | 0··+ |
which (with rearrangement) are the same rows of vectors as those of 0I with 0+ and 1+ replaced by 0··+ and 1··+ respectively. This construction covers the 3-tuples spanning three subarrays because 0I covers four columns with strength three. Since all the 3-tuples spanning one, two, or three subarrays are covered, 2I covers all 16 columns with strength three.
Constructions for w=3 and w=4 are given in an appendix.
The typical efficiency of a wI array compares favorably with that of a covering array generated by the Constrained Array Test System. The following table shows cases in which the number of rows of the wI array is less than or equal to that of the array from the expand command with the -t option.
Number of Rows for l=3 and m=2 | |||
---|---|---|---|
Number of Columns | expand -t | wI | |
n | r | w | r |
4 | 8 | 0 | 8 |
8 | 14 | 1 | 14 |
16 | 26 | 2 | 22 |
32 | 38 | 3 | 32 |
64 | 4 | 44 |
This section describes a similar covering array for strength l=4, number of levels m=2, and number of columns n=8.
The array consists of two subarrays of four columns each. The top eight rows of plus vectors in each subarray are columns from 3P. They are the left four columns from 3E, so they cover each of the subarrays with strength four.
The next four rows of plus vectors in the left subarray are the columns from 2P; in the right subarray they are the columns from 2P. Now each row of plus vectors from 2P (on the left) is the same as a row of plus vectors from the 3P columns above. Since each subarray contains 2P in the top eight rows of plus vectors, each subarray covers its 3-tuples in combination with individual levels (0 or 1) from the other subarray. And since the subarrays pair 2P with 2P in the next four rows of plus vectors, each covers its 3-tuples with the other level from the other subarray also. Thus, the 4-tuples consisting of 3-tuples from one subarray and one level from the other are covered.
The last eight rows of plus vectors are as given below. Their inclusion allows the array to cover the remaining 4-tuples.
3P000 | 3P001 | 3P010 | 3P100 | 3P000 | 3P001 | 3P010 | 3P100 |
---|---|---|---|---|---|---|---|
2P00 | 2P01 | 2P10 | 2P11 | 2P00 | 2P01 | 2P10 | 2P11 |
0.··+ | 0++·+ | ||||||
0.+·+ | 0+··+ | ||||||
0.··+ | 0+·++ | ||||||
0.·++ | 0+··+ |
A formula, vectors, and levels are given for this array in an appendix. Note that rows of vectors are rearranged in the appendix, to allow a more concise formulation than the one given here.
The efficiency of this array does not compare favorably with a corresponding array from the Constrained Array Test System: This construction has 40 rows; the expand program with the -Q option yields an array with 33 rows, and other CATS runs have yielded as few as 31 rows in this case.
Another way to find covering arrays for strength l=3 and number of levels m=2 depends on the arrays of permutation vectors wP covering with strength 3 when w>1. Here, the cats program from the Constrained Array Test System is used to remove redundant rows from wP. The resulting covering array wP§ typically has the same number or fewer rows than the corresponding w-2I array. (The section mark in wP§ denotes the removal of redundant rows by cats.) Note that different wP§ arrays can be found depending on the order of the rows of wP in the cats program input.
An appendix gives the wP§ arrays for w=2, w=3, w=4, w=5, and w=6. The table below summarizes the numbers of rows for the different arrays for l=3 and m=2.
Number of Rows for l=3 and m=2 | ||||
---|---|---|---|---|
Number of Columns | expand -t | w-2I | wP§ | |
n | r | w | r | r |
4 | 8 | 2 | 8 | 8 |
8 | 14 | 3 | 14 | 14 |
16 | 26 | 4 | 22 | 20 |
32 | 38 | 5 | 32 | 28 |
64 | 6 | 44 | 34 |
The approach described in the previous section works because wP covers with strength l=3 when w>1. Generally this is not the case. The 2w columns of wP do not cover with strength 4 when w>1. However when w>2, there are combinations of 3<n<2w columns from wP which cover with strength 4. For example, a search of the 8 3P vectors yields 56 combinations of 4 which cover and 14 combinations which do not. The lowest such covering array is
3P000 | 3P001 | 3P010 | 3P100 |
---|
in which elements have decreasing significance from left to right. This array also is expressed as 3F3P in which
is an array of levels in base 2 notation, and the 3P operator acts on each element to replace it with its corresponding permutation vector. The 16-by-4 arrays derived from the 3P columns do not compare favorably with the 16-by-5 zero sum array 3E, which is given in an appendix.
Two other examples, for w=4 and w=5 respectively, are the 32-by-6 array 4F4P and the 64-by-7 array 5F5P in which
and
As in the previous section, the cats program can be used to remove redundant rows. The results in these cases are the 30-by-6 array 4F4P§ and the 32-by-7 array 5F5P§ given in an appendix. The table below compares the numbers of rows for these arrays with those from the expand program with the -q option.
Number of Rows for l=4 and m=2 | |||
---|---|---|---|
Number of Columns | expand -q | wFwP§ | |
n | r | w | r |
4 | 16 | 3 | 16 |
6 | 28 | 4 | 30 |
7 | 30 | 5 | 32 |
A later section describes the use of permutation vectors which do not cover to construct covering arrays which may have more than one row of permutation vectors. For example, an array with z=2 rows of 2F2P arrays (with the same number of columns) may be found to cover for l=3. The notation w,zFwP is used to label such an array. Because the top plus vector in every permutation vector is 0+, (z-1)m rows are redundant in each w,zFwP array. These rows are removed, as indicated by the apostrophe in w,zFwP', without losing the covering property of w,zFwP.
These arrays, introduced later for m>2, can be found for m=2 as well. However, like the m=2 arrays already described, they typically are not as efficient as other known binary covering arrays. This observation is illustrated in the table below which summarizes the numbers of rows for the different arrays for l=3 and m=2.
Number of Rows for l=3 and m=2 | |||||||||
---|---|---|---|---|---|---|---|---|---|
Number of Columns | expand -t | 2E | w-2I | wP§ | 2,zF2P(') | 2,zF2P§ | Sloane1 | ||
n | r | r | w | r | r | z | r | r | r |
4 | 8 | 8 | 2 | 8 | 8 | 1 | 8 | 8 | 8 |
4 | 2 | 14 | 8 | ||||||
8 | 14 | 3 | 14 | 14 | 3 | 20 | 14 | 12 | |
16 | 26 | 4 | 22 | 20 | 4 | 26 | 26 | 17 | |
32 | 38 | 5 | 32 | 28 | 25 | ||||
64 | 6 | 44 | 34 | 32 |
The rightmost column in the table puts all of these results in the perspective of the best known results (in 1993) for l=3 and m=2. The results given here offer no improvement.
The techniques described in the previous section to construct strength l=3 2,zF2P' arrays also can be used to find strength l=4 3,zFzP' arrays. The table below summarizes the numbers of rows for the different arrays for l=4 and m=2.
Number of Rows for l=4 and m=2 | ||||||||
---|---|---|---|---|---|---|---|---|
Number of Columns | expand -q | 3E | w,1FwP | w,1FwP§ | 3,zF3P(') | 3,zF3P§ | ||
n | r | r | w | r | r | z | r | r |
4 | 16 | 3 | 16 | 16 | 1 | 16 | 16 | |
5 | 241 | 16 | ||||||
6 | 28 | 4 | 32 | 30 | ||||
7 | 30 | 5 | 64 | 32 | ||||
8 | 401 | 2 | 30 | 30 | ||||
8 | 3 | 44 | 30 | |||||
11 | 40 | 4 | 58 | 58 |
Number of w,zFwP(') Covering Arrays for m=2 | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Number of Columns | ||||||||||||||
l | w | z | n | |||||||||||
3 | 4 | 5 | 8 | 9 | 11 | 16 | 17 | |||||||
3 | 2 | 1 | 4 | 1 | 0 | |||||||||
3 | 2 | 2 | 24 | 0 | ||||||||||
3 | 2 | 3 | 13824 | 0 | ||||||||||
3 | 2 | 4 | 2156544 | 0 | ||||||||||
4 | 3 | 1 | 56 | 0 | ||||||||||
4 | 3 | 2 | 10752 | 0 | ||||||||||
4 | 3 | 3 | 433520640 | or more | 0 | |||||||||
4 | 3 | 4 | 10 or more |
For n=9 columns a similar search was completed, with a fixed zeroth row of vectors and with the zeroth column of the first row fixed as 03P. (A later section gives more detail on the search scope and method.) No covering arrays were found. This result for 03P in the eighth column of the zeroth row and for 03P in the zeroth column of the first row suggests that there are no covering arrays for any other permutation vectors in these positions either. If there were some other choice for the eighth column of the zeroth row, the inverse of that vector could be applied as a position mapping operator to the zeroth row, to yield a covering array with 03P in the eighth column. The other eight columns could be rearranged to increase with column number, to yield a covering array with a zeroth row which is the same as the fixed row in the search. And if this transformed array were to have a nonidentity vector in the zeroth column of the first row, the inverse of that vector could be applied as a position mapping operator to the first row, to yield a covering array with 03P in the zeroth column. Such an array would have been found in the completed search. Thus, there are no covering arrays of this form, with z=3 rows of vectors, n=9 columns, and one permutation vector repeated in each row.
Earlier sections illustrate the use of permutation vectors to form covering arrays with strength l>2. These sections describe the combinations of permutation vectors which do not cover. The tabulation of these noncovering vector combinations then can be used to find covering arrays (which may have z>1 rows of permutation vectors). The idea is to construct an array w,zF from the mw levels 0, ..., mw-1 such that each of the (nl) combinations of columns contains at least one covering combination of permutation vectors.
Consider, for example, the permutation vectors for w=2 and m=3. For strength l=3, the covering array uses combinations of the mw=9 permutation vectors taken l=3 at a time. There are 84 such combinations. 72 of them cover, and 12 do not. The noncovering combinations are given in the following rows (in base 3 notation).
2P00 | 2P01 | 2P02 |
---|---|---|
2P10 | 2P11 | 2P12 |
2P20 | 2P21 | 2P22 |
2P00 | 2P10 | 2P20 |
2P01 | 2P11 | 2P21 |
2P02 | 2P12 | 2P22 |
2P00 | 2P11 | 2P22 |
2P01 | 2P12 | 2P20 |
2P02 | 2P10 | 2P21 |
2P00 | 2P12 | 2P21 |
2P01 | 2P10 | 2P22 |
2P02 | 2P11 | 2P20 |
Once the noncovering combinations are tabulated, the covering arrays are found by systematically testing combinations of l columns for including permutation vector combinations which are not noncovering. This type of search is faster than testing each combination of columns for coverage directly.
In this case the lowest covering array with one row of vectors and n=4 columns is
2P00 | 2P01 | 2P10 | 2P11 |
---|
The formula, vectors, and levels for this 27-by-4 array are given in an appendix.
For m=prime or m=prime power, and w>0, consider the mw+1-by-n arrays which can be formed from columns of wP. Also consider the strengths l=1, 2, ..., w+2. There is no need to consider larger values of l because the wP permutation vectors can cover with at most strength w+1: The permutation vectors have mw+1 rows, and ml are needed to cover. The wP permutation vectors cannot cover with strength l>w+1.
The strength also cannot exceed the number of wP permutation vectors. Since there are mw vectors to form l-tuples, l cannot exceed mw without repeated use of one or more permutation vectors. And such repetition does not improve coverage.
Now for n=l, the arrays which do not cover define the noncovering combinations of permutation vectors. These are the combinations of l columns selected to form the noncovering arrays. In the cases considered here, these combinations can be described in terms of a set of noncovering permutation vectors. Each set contains ml-2 of the mw elements 0, 1, ..., mw-1. The elements are selected such that any combination of l elements labels a combination of permutation vectors which does not cover. Thus each noncovering set is associated with
( | ml-2 l | ) |
noncovering combinations.
In the w=2, l=3, m=3 example, there are 3 elements in each noncovering set, and 1 noncovering combination results. When l=4 and m=3, all 9 elements are in a noncovering set, and 126 noncovering combinations result.
The sets of noncovering permutation vectors can be organized into collections of noncovering sets. Each collection is a set of a power of m (ma) noncovering sets. (Specific formulations for the collections are given below.) For l less than or equal to w+2, there are
( | w l-2 | ) |
collections. In particular, for l=1,
( | w -1 | ) = 0 |
so there are no collections and no noncovering sets. All wP permutation vectors cover with strength l=1.
In the cases considered here, the total number of noncovering sets is given by wel,m whose values are computed recursively in a manner similar to that of Pascal's triangle.
1e2,m = m |
1e3,m = 1 |
w+1el+1,m = mw-l+2 wel,m + m wel+1,m |
In the triangle, rows are labeled by w, and shaded diagonals are labeled by l. Each element, corresponding to wel,m, is the sum of each of the two elements above multiplied by an appropriate power of m. Thus for w=2 and l=3, for example,
And for m=3, m2+m=12. I.e. there are 2 collections, one with 9 sets of noncovering vectors, and one with 3.
l=2 | l=3 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
w=1 | m | 1 | l=4 | |||||||
w=2 | m2 | m2+m | 1 | l=5 | ||||||
w=3 | m3 | m4+m3 +m2 | m3+m2 +m | 1 | l=6 | |||||
w=4 | m4 | m6+m5 +m4+m3 | m6+m5 +2m4 +m3+m2 | m4+m3 +m2+m | 1 |
Note that the total number of noncovering sets can be expressed
as a product of a power of m and a Gaussian binomial coefficient:
Tables of Gaussian binomial coefficients can be found in the
On-Line Encyclopedia of Integer Sequences.
Sequence
A022167 gives the table for the m=3 example.
Finally the total number of noncovering combinations of permutation vectors is the product of the number of noncovering combinations per set
and the number of noncovering sets:
It is important to note that the noncovering combinations of permutation vectors included in the total may not be unique.
While each set of noncovering permutation vectors contains distinct vectors
so the combinations for each set are unique
it is possible for a combination of l vectors to appear in more than one set.
In the strength l=3 cases described here (with w=2),
the noncovering combinations are unique,
so the total represents distinct noncovering arrays.
However for the l=4 cases (with w=3),
the noncovering combinations are not unique when the number of levels m is greater than or equal to the strength l.
A later section shows that for l=4 with m=4 or m=5,
the number of distinct noncovering arrays is less than the total formulated here.
The expression for the total number of noncovering combinations of permutation vectors
leads to the following special cases:
All permutation vector combinations cover for l=2.
All permutation vector combinations cover for l=3 and m=2.
When l=w+2 all permutation vectors are contained in a single noncovering set.
The noncovering permutation vectors are described in terms of the mw elements 0, 1, ..., mw-1 in base m notation.
The wel,m-by-wml-2 array w,lQ~ describes these elements with each row corresponding
to a set of noncovering permutation vectors.
w,lQ~ contains w subarrays consisting of ml-2 contiguous columns.
Each subarray contains the values for a particular base m component (h0, h1, etc.) of the elements.
For example, when w=2, l=3, and m=3,
The top row of vectors
describes a collection of 3 noncovering sets.
The bottom row of vectors
describes a collection of 9 noncovering sets.
The left subarray
contains the values for the h0 component (3's place), and the right subarray
contains the values for the h1 component (1's place).
Expansion of the formula gives
It is convenient to use the notation w,lQ (without the tilde) to mean the array of noncovering elements expressed in base m
(or h vectors).
This requires a simple rearrangement of w,lQ~ columns to yield the
wel,m-by-ml-2 array w,lQ.
In the example,
When the elements of this array are replaced with their corresponding permutation vectors,
the array of noncovering combinations 2,3Q2P results.
This array was given in a previous section.
Descriptions of w,lQ~ for selected values of w and l are listed below.
Thus,
and so forth.
w,w+2Q~ contains one set of all mw permutation vectors (which do not cover with strength l=w+2).
There are m elements in each set.
There are 2 collections:
One with m sets and one with m2 sets.
There are m elements in each set.
There are 3 collections with a total of m2+m3+m4 sets.
There are m2 elements in each set.
There are 3 collections with a total of m+m2+m3 sets.
This section describes results of searches for covering arrays
using the technique described in the previous sections.
The arrays consist of z rows of permutation vectors.
Each search is to find arrays such that every combination of l columns contains at least one row of permutation vectors which is not noncovering.
The notation w,zF is used to describe covering arrays which may have z>1 rows of permutation vectors.
The results for w=2, l=3, and m>2 are summarized in the following table.
The reference tables in an appendix give the lowest arrays in terms of their permutation vector formulas, plus vectors, and levels.
(Rows of permutation vectors have decreasing significance from top to bottom.)
Because the top plus vector in every permutation vector is 0+, (z-1)m rows are redundant in each array.
These rows are removed, as indicated by the apostrophe in 2,zF2P'.
Thus the number of rows is
Note that the sliding levels technique described for strength l=2 arrays can
be applied for higher strength arrays as well.
Thus an array for m=prime power product can be formulated in terms of an
array for a larger value m'=prime power.
Two examples for l=3, m=6, and m'=7, with z=1
and z=2,
are given in an appendix.
When the values of z and m are low,
the searches can run to completion,
so all the covering arrays 2,zF2P can be found.
Also the maximum number of columns n can be found by executing searches with increasing n until one completes without finding a covering array.
Tables in the following sections list the numbers of arrays
(based on the lowest first column vectors)
in these cases.
The results given here for higher values of z and m, i.e. for
are from searches which yielded one or more covering arrays
but which were abandoned prior to completion.
Note that where a maximum n is found, its value is greater than or equal to
mz.
In the cases listed with n<mz,
searches with larger values of n were abandoned
without finding an array and without completion.
These results are consistent with the conjecture that there are covering arrays of this form
When z=1 row of permutation vectors,
the search is to find combinations of n vectors which cover.
For each such array any permutation of the n vector columns also covers.
So to narrow the search, candidate arrays are constrained to have vectors
in ascending order with increasing column number.
That is, the lowest permutation of each covering combination of vectors is found and counted.
Each number of arrays is the number of covering combinations
resulting from a completed search which spans the
total combinations.
For the cases considered here
the number of covering arrays can be described for selected values of n columns as follows.
(Note that for z=1 the covering arrays are orthogonal arrays of index one.)
Often the number of covering arrays is a multiple of mw.
This property can be explained by associating each covering array with a set
of mw arrays which differ only by a permutation of rows.
For each covering array
select one permutation vector from the set of mw.
The permutation vector is applied to the row of permutation vectors
in the array, from the left, as a position mapping operator.
This operation has the effect of permuting the rows of all the permutation
vectors, so the transformed array also covers.
And the transformed array consists of a row of permutation vectors
because they form a group with the vector product operator.
Thus the transformed arrays can be found in the search,
and the number of arrays can be a multiple of mw.
In the table above there are two exceptions to this observation:
for m=2 with n=4, and for m=4 with n=4.
Note that in the case of m=2, the transformation described here
results in 4 permutations of the single combination of vectors,
and not 4 different combinations.
When z=2 rows of permutation vectors,
the array is partitioned into subarrays of up to mw contiguous columns.
Each row of vectors in each subarray consists of permutation vectors which are not repeated.
That is, a permutation of the mw levels identifies the vectors in each row
of the subarray.
In addition, the zeroth row of vectors is fixed, so that
in each subarray the permutation vectors are taken from the corresponding subarray columns
0, 1, ..., mw-1.
In this section two cases are considered for the number of columns n:
For z=2 rows of vectors,
the search is to find permutation vectors for the first (lower) row of vectors
which together with the zeroth (upper), fixed row of vectors will cover.
In this case, different
permutations of the vectors in the lower row of each subarray
are counted separately.
So for n=m2, the scope of the search is up to m2! arrays.
And for m2+1, the scope is up to m2!m2 arrays.
The numbers of covering arrays
resulting from completed searches are given in the following table.
Note that the number of covering arrays is a multiple of mw=m2.
This property can be explained by associating each covering array with a set
of mw arrays which differ only by a permutation of rows.
For each covering array consisting of 2 rows of permutation vectors,
select one permutation vector from the set of mw.
This vector is applied to the lower row of permutation vectors
in the array, from the left, as a position mapping operator.
This operation has the effect of permuting the rows of this row of permutation
vectors, so the transformed array also covers.
And the transformed array consists of 2 rows of permutation vectors
(with the upper row fixed)
because the permutation vectors form a group with the vector product operator.
Thus the transformed arrays are found in the search,
and the number of arrays is a multiple of mw.
Of course a permutation vector could be applied to the upper row (as above for z=1),
possibly leading to the number of arrays being a multiple of mwz.
But there is no assurance that the transformed array would be unique
within the search and counting rules given here.
It turns out that for m=3 and m=4 with n=m2 the number of arrays actually is a multiple of m4:
For each of the mw permutation vectors in the zeroth column of the lower row, the number of covering arrays
is observed to be a multiple of m2. (m=2 is an exception to this pattern.)
This section describes results of searches for strength l=4 covering arrays
using the technique described in the previous sections.
The results for w=3, l=4, and m>2 are summarized in the following table.
The reference tables in an appendix give the lowest arrays in terms of their permutation vector formulas, plus vectors, and levels.
The 3F3P array described earlier for m=2
has only four columns compared to the 3E zero sum array which has five.
The 3F3P arrays in this table for m=3 and m=4 have the same numbers of rows and columns
compared to the corresponding 3E zero sum arrays.
For m=5 the 3F3P array has m+1=6 columns.
Arrays with additional columns are found when z>1.
These results are consistent with the conjecture that there are covering arrays of this form
When z=1 row of permutation vectors,
the search is to find combinations of n vectors which cover.
For each such array any permutation of the n vector columns also covers.
So to narrow the search, candidate arrays are constrained to have vectors
in ascending order with increasing column number.
That is, the lowest permutation of each covering combination of vectors is found and counted.
Each number of arrays is the number of covering combinations
resulting from a completed search which spans the
total combinations.
For the n=4 cases described here,
the number of covering arrays is the total number of l=4 combinations
minus the number of unique noncovering combinations:
wel,m = mw-l+2 ( w
l-2)m
( ml-2
l) wel,m
= mw-l+2 ( ml-2
l) ( w
l-2)m Special Cases of Noncovering Permutation Vector Combinations
( m2-2
2) we2,m = ( 1
2) we2,m = 0
( 23-2
3) we3,2 = ( 2
3) we3,2 = 0
( mw
l) wew+2,m = ( mw
l) Formulas for Collections of Noncovering Permutation Vector Sets
2,3Q~ =
0·+
0+..0+.
0+x+
0·+ 0+.
0+.. 0+x+
2,3Q~0 = 0·+
0+..
2,3Q~1 = 0+.
0+x+
2,3Q~ = 0·+
0+..0+.
0+x+= 0+
0..0+
1..0+
2..0.
0x+1.
1x+2.
2x+
2,3Q = 0+0.
0..0x+0+1.
1..1x+0+2.
2..2x+= 00
10
2001
11
2102
12
2200
01
0210
11
1220
21
2200
01
0211
12
1022
20
2100
01
0212
10
1121
22
20
1,3Q~ = 0+ 2,4Q~ = 0+· 0·+ 3,5Q~ = 0+·· 0·+· 0··+
2,3Q~ =
0·+
0+..0+.
0+x+
3,3Q~ =
0·+.
0·+..
0+....0·.+
0+...
0+x+..0+..
0+.x+
0+..x+
3,4Q~ =
0··+
0+·..
0+·...0+·.
0+·x+
0·+...0·+.
0·+..
0+·.x+*0·+x.+Covering Arrays for l>2 and m>2
Covering Arrays for l=3 and m>2
Covering Arrays for w=2, l=3, and m>2 Number
of Rows
of VectorsNumber
of LevelsNumber
of RowsNumber
of ColumnsArray Reference Tables z m r n 1 3 27 4 2,1F2P
formula vectors levels 1 4 64 6 2,1F2P
formula vectors levels 1 5 125 6 2,1F2P
formula vectors levels 1 7 343 8 2,1F2P
formula vectors levels 1 8 512 10 2,1F2P
formula vectors 1 9 729 10 2,1F2P
formula vectors 1 11 1331 12 2,1F2P
formula vectors 1 13 2197 14 2,1F2P
formula vectors 2 3 51 9 2,2F2P'
formula vectors levels 2 4 124 16 2,2F2P'
formula vectors levels 2 5 245 24 2,2F2P'
formula vectors 2 7 679 31 2,2F2P'
formula vectors 2 8 1016 40 2,2F2P'
formula vectors 2 9 1449 39 2,2F2P'
formula vectors 2 11 2651 44 2,2F2P'
formula vectors 2 13 4381 39 2,2F2P'
formula vectors 3 3 75 20 2,3F2P'
formula vectors 3 4 184 28 2,3F2P'
formula vectors Numbers of Arrays for l=3
z=1 and m>9, z=2 and m>4, and z>2,
z=1 Row of Permutation Vectors
( mw
n)
Number of 2,1F2P Covering Arrays for w=2, l=3, and z=1 Number
of LevelsNumber of Columns m n 3 4 5 6
7 8 9 10 11 2 4 1 0 3 72 54 0 4 480 840 288 48
0 5 2000 6500 6600 1000
0 7 16464 127596 444528 460992
51744 6174 0 8 37632 404544 2145024 4158336
1666560 584640 125440 12544 0 9 77760 1108080 8328096 26290656
23794560 3411720 239760 23328 0
( mw
n) - (
ml-2
l) wel,m =
( m2
3) - (
m
3) (m+1)m
1
3{( m-1
2) + 1
2}( m
2)( m2
2)
2m( m
2)2
z=2 Rows of Permutation Vectors
Number of 2,2F2P' Covering Arrays for w=2, l=3, and z=2 Number
of LevelsNumber of Columns m n 4 5 9
10 16 17 2 24 0 3 82944 0 4 234213120 0
Covering Arrays for l=4 and m>2
Covering Arrays for w=3, l=4, and m>2 Number
of Rows
of VectorsNumber
of LevelsNumber
of RowsNumber
of ColumnsArray Reference Tables z m r n 1 3 81 5 3F3P
formula vectors levels 1 4 256 5 3F3P
formula vectors levels 1 5 625 6 3F3P
formula vectors 2 3 159 10 3,2F3P'
formula vectors levels 2 4 508 9 3,2F3P'
formula vectors 2 5 1245 11 3,2F3P'
formula 3 3 237 16 3,3F3P'
formula vectors
Numbers of Arrays for l=4
( mw
n)
Number of 3,1F3P Covering Arrays for w=3, l=4, and z=1 Number
of LevelsNumber of Columns m n 4 5 6
7 2 56 0 3 12636 12636 0 4 483840 1935360 0 5 7750000 79050000 62000000 0
( mw
n) - {(
ml-2
l) - ( m
l)m2} wel,m =
( m3
4) - {(
m2
4) - ( m
4)m2} (m2+m+1)m
( | ml-2 l | ) wel,m = ( | m2 4 | ) (m2+m+1)m |
because the combinations in the total are not unique.
This section describes in some detail the search technique for arrays with multiple rows of permutation vectors. An example with strength l=3, number of levels m=3, number of columns n=20, log-order w=2, and number of rows of vectors z=3 illustrates the search technique.
Throughout this discussion, candidate covering arrays are described in terms of the mw levels which label the permutation vectors, and to which the wP operator is applied. In the search itself there is no need to compute the permutation vectors explicitly. The application of the wP operator to compute the covering array is the last step, after the search is complete.
There is no need for base m to label the permutation vectors in the search program, so decimal integers are used. In this example, the mw permutation vectors are indicated by the integers 0, 1, ..., 8. The sets of noncovering permutation vectors are computed from the w,lQ~ formula, and each set is stored in ascending order. In this example, the noncovering sets are indicated by
0 | 1 | 2 |
---|---|---|
3 | 4 | 5 |
6 | 7 | 8 |
0 | 3 | 6 |
1 | 4 | 7 |
2 | 5 | 8 |
0 | 4 | 8 |
1 | 5 | 6 |
2 | 3 | 7 |
0 | 5 | 7 |
1 | 3 | 8 |
2 | 4 | 6 |
The permutation vectors wP can be computed from their definition also.
To reduce the scope of the search and thus reduce execution times, search constraints are imposed:
( | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | )2P |
---|
Within these constraints the lowest array in the example, from which the search is started, is given by
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 |
(The 2P operator is implied.) The search progresses to higher candidate arrays, in which increasing rows (top to bottom) have decreasing significance, and increasing columns (left to right) have decreasing significance.
Each candidate array is checked for coverage by consideration of each combination of l columns, which must contain at least one l-tuple of permutation vectors which is not noncovering. Column combinations are enumerated by an l-order vector
in which the column numbers are placed in ascending order:
In the example the first column combination to check is 0 1 2. If it covers, the highest column k2 is incremented to 3, so the next three combinations,
0 1 3, | 0 2 3, | and 1 2 3, |
can be checked. If these combinations cover, k2 is incremented again, and
0 1 4, | 0 2 4, | 1 2 4, | 0 3 4, | 1 3 4, | and 2 3 4, |
are checked.
It is important to note that for each highest column kl-1, all the associated
( | kl-1 l-1 | ) |
combinations are checked together. Thus, as the candidate array changes, and kl-1 varies, it is easy to find which column combinations need to be rechecked.
A score array stores coverage results during the computation. This array contains z elements (one for each row of vectors) for each l order column combination. I.e. the score array has z(nl) elements, and in the example there are 3420 elements.
The value of each score array element is set according to the coverage of the corresponding row of vectors for this column combination. Three values are used:
Value | Meaning |
---|---|
0 | Coverage not checked yet |
1 | Column combination covers for this row of vectors |
-1 | Column combination does not cover for this row of vectors |
Initially all the elements of the score array are set to zero. As coverage is checked, the results are recorded. This cache is used to reduce the need to recheck as the candidate covering array is varied. Thus, when a permutation vector in a particular row is changed, the score array elements for this row with the combinations including this column are reset to zero. But the other score array elements remain valid for the rest of the candidate array.
Each column combination is checked for coverage as follows. First a loop over the rows of vectors is started.
If the row of vectors loop completes without finding coverage (if all rows have scores of -1), then this column combination does not cover, and a different candidate array is selected.
When a candidate array does not cover with a particular highest column kl-1, the next candidate covering array is found by incrementing the least significant element. This element is in the bottom row of vectors and column kl-1. The next permutation vector for this element is found by incrementing the level by one until it is different from the levels of the lower columns in this row and partition. (I.e. it must lead to a permutation in this row and partition.) Any remaining columns (above kl-1) in this row and partition are given the remaining levels in ascending order, so the partition contains the lowest of the remaining permutations in this row.
If the mw levels are exhausted for the given row and column kl-1, then the program selects the lowest level unused in this row in the lower columns of this partition. In this case, the next row up (the next more significant row) is incremented similarly. If the levels are exhausted in the first row, then the bottom row in the next more significant column (kl-1-1) is incremented (because the zeroth row is fixed). The process of selecting more significant rows and columns continues until the next higher candidate array is found. The score array elements corresponding to the incremented rows and columns are reset to zero. And the highest column kl-1 is set to the lowest column with incremented elements. There is no need to recheck combinations of unchanged columns.
When a covering array with the required number of columns is found, the same process is used to find the next candidate. The least significant element in the bottom row and the highest column kl-1 is incremented.
In the example, the search starts with the lowest array:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 |
Column combination 0 1 2 is checked first. It is found to be noncovering for all rows 0, 1, and 2 because each contains the levels 0, 1, and 2, which are found in a noncovering set. The candidate array is incremented to be
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
0 | 1 | 3 | 2 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 |
Now column combination 0 1 2 covers because row of vectors 2 contains the levels 0, 1, and 3, which are not noncovering. (They are not found in any noncovering vector set.)
Next k2 is incremented to 3. All three associated column combinations are covered by the zeroth row. And similarly, for k2=4, all six column combinations are covered by the zeroth row. When k2=5 however, the column combination 3 4 5 is not covered by row 0 or 1, because the levels 3, 4, and 5 are noncovering. But row 2 contains the levels 2, 4, and 5, which cover, so k2 can be incremented to 6.
When k2=6 the column combinations are covered up to combination 1 5 6. Here each row of vectors contains the levels 1, 5, and 6 which are noncovering. Row 2 is incremented as below, and then all 15 column combinations for k2=6 are covered.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
0 | 1 | 3 | 2 | 4 | 5 | 7 | 6 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 |
When k2=7, all 21 column combinations are found to be covered. However for k2=8, column combination 0 4 8 contains levels 0, 4, and 8, which are noncovering, in all rows. The candidate array must be incremented, but the level 8 in row 2 and column 8 is the highest level and cannot be increased. Moreover it cannot be changed to a lower level without changing a level of one of the lower columns. This is because a permutation of levels is required in the partition, and column 8 is the last column in the partition. Similarly, the level 8 in row 1 and column 8 cannot be changed, and the level 8 in row 0 is fixed. Thus the level 6 in row 2 and column 7 is increased to 8, and the following candidate array results.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
0 | 1 | 3 | 2 | 4 | 5 | 7 | 8 | 6 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 |
Now k2 is decremented to 7, and all 21 associated column combinations are found to be covered. When k2 is incremented to 8 this time, all column combinations are covered except for the last one 6 7 8. This combination contains the levels 6, 7, and 8, which are noncovering, in all rows. k2 must be decremented again to find the next candidate array. The search process continues similarly to find covering arrays of the required form. The lowest such covering array is
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 0 | 1 | ||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 8 | 6 | 7 | 5 | 8 | 6 | 7 | 5 | 3 | 1 | 2 | 0 | 4 | 6 | 0 | ||||
0 | 1 | 3 | 2 | 4 | 7 | 8 | 5 | 6 | 3 | 4 | 1 | 0 | 5 | 6 | 2 | 8 | 7 | 6 | 7 |
The formula (in base 3) and the vectors for this array are given in an appendix.
To find arrays with larger values of l or m, a narrower search can be used. The search described here is to find orthogonal arrays of index one, beginning with strength l=2 and working up to higher strengths recursively.
For m=prime or m=prime power, consider the vectors
1Nh = hx+ | for h=0, ..., m-1. |
---|
The array
1N = 0+. 1N0 ... 1Nm-1 |
---|
is an orthogonal array of index one and strength l=2. (1N is the same as 1H.)
In terms of the permutation vectors,
1N = 2P1 1P0 ... 1Pm-1 |
---|
because
2P1 | = 1P1. | by a reduced permutation vector recurrence relation |
---|---|---|
= 1x+. | ||
= 1x. | ||
= 0+. |
and
1Nh | = 1Ph | for h=0, 1, ..., m-1 |
---|
For l=3 the search is to find orthogonal arrays containing the vectors
2Nk | = (1Nh * k.x)+ |
---|
I.e. the search is to find a level h(k) for each column k>1 such that the vectors 2Nk cover for k=0, 1, ..., m-1.
Note that the vector for k=0 is independent of h:
2N0 | = (1Nh * 0.x)+ = 0.x+ = 2P00 |
---|
for h=0, ..., m-1. Also, to limit the scope of the search, the vector for k=1 is constrained to be
2N1 | = (1N0 * 1.x)+ = 1.x+ = 2P10 |
---|
The 2Nk vectors can be expressed in terms of the permutation vectors as follows (using base m notation).
2Nk | = (1Ph * k.x)+ | by the definition of 1Nh |
---|---|---|
= (2P1h * 2Pk0)+ | by the reduced permutation vector recurrence relations | |
= (2Pk hxk )+ | by the reduced permutation vector product identity | |
= 2Pk hxk |
This result can be expressed as 2Pk x (m+h) also.
The strength l cannot exceed the number of columns m in the search, so the minimum value of m is l. Thus the search is constrained by the relation
With the reduced permutation vector 3P001 inserted as the leftmost column, the array becomes
2N = 3P001 2N0 ... 2Nm-1 |
---|
an orthogonal array of index one and strength l=3. The total number of columns n is m+1, so
For the l=3 cases considered here, the search results include at least m-1 arrays, one of which is given by
2Nk = 2Ph |
---|
in which
h0 | = k and |
h1 | = k x (k-1) |
or | |
h | = k x (m+k-1) |
Thus, for example, for m=9, k-1 = k+2, so that
h1(k=2) = 2 x (2+2) = 2 x 1 = 2 |
h1(k=3) = 3 x (3+2) = 3 x 5 = 1, etc. |
and
2N = 3P001 2P00 2P10 2P22 2P31 2P47 2P53 2P67 2P71 2P83 |
---|
Moreover m-1 arrays are given by 2Ph in which
h0 | = k and |
h1 | = k x (k-1) x h', with |
h' | = any nonzero level = 1, ..., m-1 |
The search results are summarized in the following table.
Orthogonal Arrays for w=2, l=3, and m>2 | |||||||
---|---|---|---|---|---|---|---|
Number of Levels | Number of Rows | Number of Columns | Number of Arrays | Array | Reference Tables | ||
m | r | n | |||||
3 | 27 | 4 | 2 | 2N | formula | vectors | levels |
4 | 64 | 5 | 3 | 2N | formula | vectors | levels |
5 | 125 | 6 | 4 | 2N | formula | vectors | levels |
7 | 343 | 8 | 6 | 2N | formula | vectors | levels |
8 | 512 | 9 | 70 | 2N | formula | vectors | |
9 | 729 | 10 | 8 | 2N | formula | vectors | |
11 | 1331 | 12 | 10 | 2N | formula | vectors |
Note that for m=8, the search results in 70 arrays, including the 7 described above.
The reference tables in an appendix give the arrays for h'=1 in terms of their permutation vector formulas, plus vectors, and levels.
For successively larger values of l, the search is to find orthogonal arrays containing the vectors
w+1Nk | = (wNh * k.w x)+ |
---|
in which l=w+2, wNh is one of the m column vectors from an orthogonal array for l=w+1, and the dot operator exponent w indicates the operator is applied w times. Again the search is to find a level h(k) for each column k>1 such that the vectors w+1Nk cover for k=0, ..., m-1. Of the mw possible levels h, the search considers only the m levels which yield orthogonal array column vectors for the previous value of l=w+1. Also note that
wN0 | = wP0 |
---|
and
wN1 | = wPmw-1 |
---|
as before.
When w=1 and w=2, the orthogonal array column vectors wNh are permutation vectors, so for each of the m levels h, there is a level h'' such that
wNh | = wPh'' |
---|
If this is true for some value of w, then it is true for w+1 also:
w+1Nk | = (wPh'' * k.w x)+ |
---|---|
= (w+1P1h'' * w+1Pk0)+ | |
= (w+1Pk x (mw+h'') )+ | |
= w+1Pk x (mw+h'') |
Thus the column vectors w+1Nk are permutation vectors.
The resulting orthogonal array is
w+1N = w+2P1 w+1N0 ... w+1Nm-1 |
---|
which has index one and strength l=w+2. Again, the total number of columns n is m+1, so
Searches for l=4 orthogonal arrays were performed using 2Nk columns from selected l=3 arrays found in previous searches. Arrays were found for values of m=4, 5, and 7. Each of the selected l=3 arrays yielded 6, 20, and 18 l=4 arrays for m=4, 5, and 7 respectively.
Moreover for l=5 and m=5, 24 orthogonal arrays were found using an l=4 array from a previous search.
Some of the search results described in the previous sections suggest an orthogonal array formula as follows. For columns k=0, 1, ..., m-1, let
wLk = wPh |
---|
in which
ht | = products=0t(k-s), t=0, 1, ..., w-1 |
Then the index one orthogonal array is given by
wL = w+1P1 wL0 ... wLm-1 |
---|
The strength l cannot exceed the number of columns n in the formula, so the minimum value of n is l.
The formula gives n=m+1 columns, so the relation
results.
For a given value of m, the ht products are easily computed by starting with w=1 and working up to the desired strength l=w+1. Examples are given in the following table.
Orthogonal Array Formulas for l=w+1 and l<m+2 | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Strength | Number of Levels | Formulas | |||||||||||
l | m | wL | |||||||||||
2 | 2 | 2P01 | 1P0 | 1P1 | |||||||||
3 | 2 | 3P001 | 2P00 | 2P10 | |||||||||
2 | 3 | 2P01 | 1P0 | 1P1 | 1P2 | ||||||||
3 | 3 | 3P001 | 2P00 | 2P10 | 2P22 | ||||||||
4 | 3 | 4P0001 | 3P000 | 3P100 | 3P220 | ||||||||
2 | 4 | 2P01 | 1P0 | 1P1 | 1P2 | 1P3 | |||||||
3 | 4 | 3P001 | 2P00 | 2P10 | 2P21 | 2P31 | |||||||
4 | 4 | 4P0001 | 3P000 | 3P100 | 3P210 | 3P311 | |||||||
2 | 5 | 2P01 | 1P0 | 1P1 | 1P2 | 1P3 | 1P4 | ||||||
3 | 5 | 3P001 | 2P00 | 2P10 | 2P22 | 2P31 | 2P42 | ||||||
4 | 5 | 4P0001 | 3P000 | 3P100 | 3P220 | 3P311 | 3P424 | ||||||
2 | 7 | 2P01 | 1P0 | 1P1 | 1P2 | 1P3 | 1P4 | 1P5 | 1P6 | ||||
3 | 7 | 3P001 | 2P00 | 2P10 | 2P22 | 2P36 | 2P45 | 2P56 | 2P62 | ||||
4 | 7 | 4P0001 | 3P000 | 3P100 | 3P220 | 3P366 | 3P453 | 3P564 | 3P621 | ||||
2 | 8 | 2P01 | 1P0 | 1P1 | 1P2 | 1P3 | 1P4 | 1P5 | 1P6 | 1P7 | |||
3 | 8 | 3P001 | 2P00 | 2P10 | 2P26 | 2P36 | 2P42 | 2P52 | 2P64 | 2P74 | |||
2 | 9 | 2P01 | 1P0 | 1P1 | 1P2 | 1P3 | 1P4 | 1P5 | 1P6 | 1P7 | 1P8 | ||
3 | 9 | 3P001 | 2P00 | 2P10 | 2P22 | 2P31 | 2P47 | 2P53 | 2P67 | 2P71 | 2P83 | ||
2 | 11 | 2P01 | 1P0 | 1P1 | 1P2 | 1P3 | 1P4 | 1P5 | 1P6 | 1P7 | 1P8 | 1P9 | 1PA |
3 | 11 | 3P001 | 2P00 | 2P10 | 2P22 | 2P36 | 2P41 | 2P59 | 2P68 | 2P79 | 2P81 | 2P96 | 2PA2 |
(The symbol A represents 10 in base 11 notation.)
Selected orthogonal arrays following this formula are described in the table below.
Selected Orthogonal Arrays Following Formula for l=3 and l=4 | |||||||
---|---|---|---|---|---|---|---|
Strength | Number of Levels | Number of Rows | Number of Columns | Array | Reference Tables | ||
l | m | r | n | ||||
3 | 2 | 8 | 3 | 2L | formula | vectors | levels |
3 | 3 | 27 | 4 | 2L | formula | vectors | levels |
3 | 4 | 64 | 5 | 2L | formula | vectors | levels |
3 | 5 | 125 | 6 | 2L | formula | vectors | levels |
3 | 7 | 343 | 8 | 2L | formula | vectors | levels |
3 | 8 | 512 | 9 | 2L | formula | vectors | |
3 | 9 | 729 | 10 | 2L | formula | vectors | |
3 | 11 | 1331 | 12 | 2L | formula | vectors | |
4 | 3 | 81 | 4 | 3L | formula | vectors | levels |
4 | 4 | 256 | 5 | 3L | formula | vectors | levels |
4 | 5 | 625 | 6 | 3L | formula | vectors | |
4 | 7 | 2401 | 8 | 3L | formula |
The reference tables in an appendix give these arrays in terms of their permutation vector formulas, plus vectors, and levels.
Note that the 2L arrays for m>2 given here are the same as the 2N arrays given in a previous section.