DIMACS TR: 93-48

Covering Arrays and Intersecting Codes

Author: N. J. A. Sloane


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