Premium
Covering arrays and intersecting codes
Author(s) -
Sloane N. J. A.
Publication year - 1993
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.3180010106
Subject(s) - combinatorics , mathematics , property (philosophy) , set (abstract data type) , discrete mathematics , binary number , arithmetic , computer science , philosophy , epistemology , programming language
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.