A Reduced Complexity Algorithm for Minimizing N-Detect Tests

We give a new recursive rounding linear programming (LP) solution to the problem of N-detect test minimization. This is a polynomial-time solution that closely approximates the exact but NP-hard integer linear programming (ILP) solution. In ILP, a test is represented by a [0,1] integer variable and the sum of those variables is minimized. Constraints ensure that each fault has at least N tests with non-zero variables. Traditionally, the problem has been transformed to less complex LP by treating the variables as real numbers, regarded as probabilities with which they can be rounded off to 0 or 1. This is known as the randomized rounding method. In the new method, the LP is recursively used, each time rounding the largest variable to 1 and reducing the size of the LP. The method is found to converge to a solution in just a few LP runs and the result is usually better than that of randomized rounding. Experimental results include ISCAS85 benchmarks and a set of multiplier circuits. N-detect tests for N = 1, 5 and 15 are considered. Also, a 10-vector single-detect sequence for c6288 is given