Accelerating the compaction of test sequences in sequential circuits through problem size reduction

The problem of compacting a set of test sequences for sequential circuits is modeled here with the help of a covering matrix, where the test sequences are modeled as columns with variable cost to reflect the cost (number of vectors) of covering selected subsets of circuit faults. From this formulation, reduction rules are extracted, particular to this type of problem which, iteratively applied, result in a significant reduction of the size of the initial compaction problem. A characteristic of the reduction rules is that their application will not compromise the optimum solution of the problem. The remaining reduced problem is then solved by a combination of a heuristic and an exact branch and bound algorithm. Experimental results using the above reduction rules show that the sizes of the given sets of test sequences are often significantly reduced and many times these rules directly produce the absolute minimum of the solution. The final results, compared with others from the literature and also with the absolute minima of the examples, computed separately, support the potential of the proposed approach.