On the size and generation of minimal N-detection tests

The main result of this paper, proved as a theorem, is that a lower bound on the number of test vectors that detect each fault at least N times is N times the minimal test set size for N = 1. Tests with N > 1 have been reported to have a higher defect coverage and hence are of practical interest. We give an integer linear programming (ILP) algorithm for optimally minimizing a given test set for any given N; in general, the value of N can be separately specified for each fault. Results on benchmark circuits show that optimal N-detection tests are easier to find for circuits that are deep and the input cones of primary outputs have large overlap. However, for small depth circuits, where the primary input overlap between output cones is small or nonexistent, the minimization of the N-detection tests requires further investigation.