DIMACS TR: 93-48
Covering Arrays and Intersecting Codes
Author: N. J. A. Sloane
ABSTRACT
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 sup 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 Renyi, Katona, and Kleitman and Spencer.
The present paper is concerned with the case t=3 ,
where important (but unpublished) contributions were made by
Busschbach and Roux in the 1980's.
One of the principal constructions makes use of intersecting
codes (linear codes with the property that any two nonzero
codewords meet). This paper 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
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-48.ps
DIMACS Home Page