Minimizing N-Detect Tests for Combinational Circuits

Abstract

An N-detect test set detects each stuck-at fault by at least N different vectors. N-detect tests are of practical interest because of their ability to improve the defect coverage. The main problem that limits their use is their size. Researchers have proposed various methods to generate N-detect tests, but not much work is done on minimizing them. Also, there is no clear minimum size estimate of an N-detect test set. We provide a theoretical lower bound on the size of an N-detect test set. We show that the lower bound on the size of an N-detect test set is N times the size of the largest Independent Fault Set (IFS).

Given any N-detect vector set, Integer linear programming (ILP) is used to derive a minimal N-detect vector set from it. Faults are simulated without fault dropping and that result is used to formulate the ILP model. The model consists of a single N-detection constraint for each fault and an objective function to be minimized, which is the sum of all integer variables. The problem is then solvable by any ILP solver and ILP always achieves the smallest possible test set. The ILP method, when applied to the ISCAS85 benchmark circuits, produced better results compared to an earlier N-detect test minimization method.

The ILP method is limited in its application to much larger circuits because of its exponential complexity. A new relaxed linear programming (LP) algorithm, which we call recursive rounding, addresses this complexity issue. It is shown to be an improvement over the existing relaxed LP methods like randomized rounding. The new algorithm has a polynomial time complexity, even in the worst case. The results indicate an almost linear increase in CPU time with respect to the circuit size. The recursive rounding method can be applicable in various fields where ILP is conventionally used.

The benchmark circuit c6288, a 16-bit multiplier, is a challenging example due to the huge difference between its theoretical minimum test set of size of six and the practically achieved minimum test set of size 12. Small size multipliers are designed based on c6288 and integer linear programming method is applied to their exhaustive test sets. For the first time, it is veritably confirmed through a 5-bit multiplier that for some circuits, the theoretical lower bound cannot be achieved practically. The minimum test sets from smaller multipliers are replicated in various combinations for the 16 bit multiplier (c6288) and are processed using ILP, which produced a minimum test set of size 10. The recursive LP method gave a test set of 12 vectors in 301 seconds. We believe that the 10 vector set is the smallest test set ever achieved for c6288.