Covering arrays of higher strength from permutation vectors

A covering array CA(N;t,k,v) is an N × k array such that every N × t sub‐array contains all t‐tuples from v symbols at least once, where t is the strength of the array. Covering arrays are used to generate software test suites to cover all t‐sets of component interactions. We introduce a combinatorial technique for their construction, focussing on covering arrays of strength 3 and 4. With a computer search, covering arrays with improved parameters have been found. © 2005 Wiley Periodicals, Inc. J Combin Designs 14: 202–213, 2006     

Covering arrays of strength three from extended permutation vectors

A covering array \(\text{ CA }(N;t,k,v)\) is an \(N\times k\) array such that in every \(N\times t\) subarray each possible t-tuple over a v-set appears as a row of the subarray at least once. The integers t and v are respectively the strength and the order of the covering array. Let v be a prime power and let \({\mathbb {F}}_v\) denote the finite field with v elements. In this work the original concept of permutation vectors generated by a \((t-1)\)-tuple over \({\mathbb {F}}_v\) is extended to vectors generated by a t-tuple over \({\mathbb {F}}_v\). We call these last vectors extended permutation vectors (EPVs). For every prime power v, a covering perfect hash family \(\text{ CPHF }(2;v^2-v+3,v^3,3)\) is constructed from EPVs given by subintervals of a linear feedback shift register sequence over \({\mathbb {F}}_v\). When \(v\in \{7,9,11,13,16,17,19,23,25\}\) the covering array \(\text{ CA }(2v^3-v;3,v^2-v+3,v)\) generated by \(\text{ CPHF }(2;v^2-v+3,v^3,3)\) has less rows than the best-known covering array with strength three, \(v^2-v+3\) columns, and order v. CPHFs formed by EPVs are also constructed using simulated annealing; in this case the results improve the size of eighteen covering arrays of strength three.     

Covering arrays from cyclotomy

For a prime power ${q \equiv 1 (mod{v})}$ , the q × q cyclotomic matrix, whose entries are the discrete logarithms modulo v of the entries in the addition table of ${\mathbb{F}_q}$ , has been shown using character theoretic arguments to produce an ${\varepsilon}$ -biased array, provided that q is large enough as a function of v and ${\varepsilon}$ . A suitable choice of ${\varepsilon}$ ensures that the array is a covering array of strength t when ${q > t^2 v^{4t}}$ . On the other hand, when v = 2, using a different character-theoretic argument the matrix has been shown to be a covering array of strength t when ${q > t^2 2^{2t-2}}$ . The restrictions on ${\varepsilon}$ -biased arrays are more severe than on covering arrays. This is exploited to prove that for all v ≥ 2, the matrix is a covering array of strength t whenever ${q > t^2 v^{2t}}$ , again using character theory. A number of constructions of covering arrays arise by developing and extending the cyclotomic matrix. For each construction, extensive computations for various choices of t and v are reported that determine the precise set of small primes for which the construction produces a covering array. As a consequence, many covering arrays are found when q is smaller than the bound ${t^2 v^{2t}}$ , and consequences for the existence of covering arrays reported.     

Orthogonal arrays obtained by repeating-column difference matrices

In this paper, by using the repeating-column difference matrices and orthogonal decompositions of projection matrices, we propose a new general approach to construct asymmetrical orthogonal arrays. As an application of the method, some new orthogonal arrays with run sizes 72 and 96 are constructed.     

Covering arrays from m-sequences and character sums

A covering array of strength t on v symbols is an array with the property that, for every t-set of column vectors, every one of the \(v^t\) possible t-tuples of symbols appears as a row at least once in the sub-array defined by these column vectors. Arrays constructed using m-sequences over a finite field possess many combinatorial properties and have been used to construct various combinatorial objects; see the recent survey Moura et al. (Des Codes Cryptogr 78(1):197–219, 2016). In this paper we construct covering arrays whose elements are the remainder of the division by some integer of the discrete logarithm applied to selected m-sequence elements. Inspired by the work of Colbourn (Des Codes Cryptogr 55(2–3):201–219, 2010), we prove our results by connecting the covering array property to a character sum, and we evaluate this sum by taking advantage of the balanced way in which the m-sequence elements are distributed. Our results include new infinite families of covering arrays of arbitrary strength.     

Orthogonal arrays obtained by generalized difference matrices with g levels

Nowadays orthogonal arrays play important roles in statistics, computer science, coding theory and cryptography. The usual difference matrices are essential for the construction for many mixed orthogonal arrays. But there are also orthogonal arrays which cannot be obtained by the usual difference matrices, such as mixed orthogonal arrays of run size 60. In order to construct these mixed orthogonal arrays, a class of special so-called generalized difference matrices were discovered by Zhang (1989,1990,1993,2...     

Covering arrays and intersecting codes

A t-covering array is a set of k binary vectors of length n with the property that, in any t coordinate positions, all 2^t possibilities occur at least once. Such arrays are used for example in circuit testing, and one wishes to minimize k for given values of n and t. The case t = 2 was solved by Rényi, Katona, and Kleitman and Spencer. The present article is concerned with the case t = 3, where important (but unpublished) contributions were made by Busschbach and Roux in the 1980s. One of the principal constructions makes use of intersecting codes (linear codes with the property that any two nonzero codewords meet). This article studies the properties of 3-covering arrays and intersecting codes, and gives a table of the best 3-covering arrays presently known. For large n the minimal k satisfies 3.21256 < k/log n < 7.56444. © 1993 John Wiley & Sons, Inc.     

Triple arrays from difference sets

This paper addresses the question of whether triple arrays can be constructed from Youden squares developed from difference sets. We prove that if the difference set is abelian, then having ?1 as multiplier is both a necessary and sufficient condition for the construction to work. Using this, we are able to give a new infinite family of triple arrays. We use an alternative version of the construction to analyze the case of non‐abelian difference sets, for which we prove a sufficient condition for giving triple arrays. We do a computer search for such non‐abelian difference sets, but have not found any examples satisfying the given condition.     

Optimal grid holey packings with block size 3 and 4

The notion of a grid holey packing (GHP) was first proposed for the construction of constant composite codes. For a GHP (k, 1; n ×  g) of type [w ₁, . . . , w _g ], where , the fundamental problem is to determine the packing number N([w ₁, . . . , w _g ], 1; n ×  g), that is, the maximum number of blocks in such a GHP. In this paper we determine completely the values of N([w ₁, . . . , w _g ], 1; n ×  g) in the case of block size .      

Covering and radius-covering arrays: Constructions and classification

The minimum number of rows in covering arrays (equivalently, surjective codes) and radius-covering arrays (equivalently, surjective codes with a radius) has been determined precisely only in special cases. In this paper, explicit constructions for numerous best known covering arrays (upper bounds) are found by a combination of combinatorial and computational methods. For radius-covering arrays, explicit constructions from covering codes are developed. Lower bounds are improved upon using connections to orthogonal arrays, partition matrices, and covering codes, and in specific cases by computation. Consequently for some parameter sets the minimum size of a covering array is determined precisely. For some of these, a complete classification of all inequivalent covering arrays is determined, again using computational techniques. Existence tables for up to 10 columns, up to 8 symbols, and all possible strengths are presented to report the best current lower and upper bounds, and classifications of inequivalent arrays.     

Divisible difference families from Galois rings GR(4,n) and Hadamard matrices

We give a new construction of difference families generalizing Szekeres’s difference families Szekeres (Enseignment Math 15:269–278, 1969). As an immediate consequence, we obtain some new examples of difference families with several blocks in multiplicative subgroups of finite fields. We also prove that there exists an infinite family of divisible difference families with two blocks in a unit subgroup of the Galois ring \(GR(4,n)\) . Furthermore, we obtain a new construction method of symmetric Hadamard matrices by using divisible difference families and a new array.     

Hadamard matrices and difference families

Translated from Matematicheskie Zametki, Vol. 47, No. 3, pp. 11–16, March, 1990.     

Balanced arrays of strength two from block designs

Some constructions of balanced arrays of strength two are provided by use of rectangular designs, group divisible designs, and nested balanced incomplete block designs. Some series of such arrays are also presented as well as orthogonal arrays, with illustrations. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 303–312, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10016     

Covering arrays for some equivalence classes of words

Covering arrays for words of length over a ‐letter alphabet are arrays with entries from the alphabet so that for each choice of columns, each of the ‐letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case known as partitioning hash families, words are equivalent if they induce the same partition of a element set. In the second case, words of the same weight are equivalent. In both cases, we produce logarithmic upper bounds on the minimum size of a covering array. Definitive results for , as well as general results, are provided.     

Recursive constructions for difference matrices and relative difference families

We present a new recursive construction for difference matrices whose application allows us to improve some results by D. Jungnickel. For instance, we prove that for any Abelian p-group G of type (n₁, n₂, …, n_t) there exists a (G, p^e, 1) difference matrix with e = Also, we prove that for any group G there exists a (G, p, 1) difference matrix where p is the smallest prime dividing |G|. Difference matrices are then used for constructing, recursively, relative difference families. We revisit some constructions by M. J. Colbourn, C. J. Colbourn, D. Jungnickel, K. T. Phelps, and R. M. Wilson. Combining them we get, in particular, the existence of a multiplier (G, k, λ)-DF for any Abelian group G of nonsquare-free order, whenever there exists a (p, k, λ)-DF for each prime p dividing |G|. Then we focus our attention on a recent construction by M. Jimbo. We improve this construction and prove, as a corollary, the existence of a (G, k, λ)-DF for any group G under the same conditions as above. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 165–182, 1998     

On orthogonal arrays of strength 3 and 5 achieving Rao's bound

It is shown that ifA is an orthogonal array (N, n, q, 3) achieving Rao's bound, thenA is either

1. an orthogonal array (2n, n, 2, 3) withn ≡ 0 (mod 4), or
2. an orthogonal array (q ³,q + 2,q, 3) withq even.

This result should be compared with a theorem of P.J. Cameron on extendable symmetric designs. It is also shown that ifA is an orthogonal array (N, n, q, 5) achieving Rao's bound, thenA is either the orthogonal array (32, 6, 2, 5) or the orthogonal array (3⁶, 12, 3, 5).