Independence Fault Collapsing and Concurrent Test Generation

Abstract

The objective of this work is to find suitable targets for Automatic Test Pattern Generation (ATPG) such that a minimal test set is obtained for a combinational circuit. Original concepts of independence fault collapsing and concurrent test generation are developed and a novel test generation strategy based on these is devised.

Independence fault collapsing groups faults into independent fault subsets such that each subset includes some faults that cannot be covered by the tests derived for any other subset. Using these fault subsets, optimally compact tests can be found. For an equivalence or dominance collapsed fault set an independence graph is generated using structural and functional independences. Each fault is represented as a node and an undirected edge between two nodes indicates independence of the corresponding faults; two independent faults cannot be detected by the same test vector. A ""similarity-based"" collapsing procedure reduces the graph to a fully-connected graph, whose nodes specify concurrently-testable fault targets for the ATPG.

Given a set of target faults, a concurrent test is an input vector that detects all (or most) faults in the set. These sets are obtained from the independence fault collapsing procedure. A new algorithm called the concurrent D algebra is presented for concurrent test generation.

The independence fault collapsing algorithm and the concurrent D algebra together produced the minimal set of 12 tests for the 4-bit ALU (74181) circuit. But due to the complexity involved in generating the independence graph, this technique was not applied to the ISCAS85 benchmark circuits. A simulation based method was devised for generating the independence graph and for deriving concurrent tests using single-fault ATPG.

The simulation based method was applied to the ISCAS85 combinational benchmark circuits. The results show that minimal test sets were generated for some benchmark circuits in CPU times that were almost half of what were required for an alternative dynamic compaction technique presented in the literature.