Generating all test patterns for a given stuck-at fault of a logical circuit and its ROBDD implementation

Test generation for stuck-at faults at the gate poles of a combinational circuit is reduced to finding one test pattern for each stuck-at fault. This problem is intensively investigated in Russia and abroad. Some effective methods for its solving have been developed. If we would like to get a minimal test for such faults, we need to find all test patterns for each fault and then to cover all faults with minimal subset of these test patterns. Unfortunately, this approach is very time consuming. Moreover, the number of test patterns for one fault may be very large that is why in practice, a test engineer finds any test pattern for each fault and minimize the test length using obtained subset of test patterns. The problem of finding all test patterns for the given fault is used in many applications. It is known that the subcircuit behavior (a frame of a given circuit C) may be described with a partially specified Boolean function. This fact is used for minimizing the overall circuit as a whole and except for changing subcircuits consisting of gates with the proper CLBs during design of partially-programmable circuits and can be used for minimizing programmable arrays? Partially specified functions of subcircuits may be represented by all test patterns for corresponding stuck-at faults of the circuit. Thus, it is very important to represent all test patterns in a compact way. This paper is devoted to solving the problem of finding all test patterns for a given stuck-at fault and compact presentation of such test patterns. The method that has been suggested by our scientific group, for finding one (any) test pattern, is modified in this paper. The modification is based on the following. We consider a stuck-at pole as the input of a subcircuit which output coincides with the output of the given circuit C. For that subcircuit the ROBDD R is built and the first variable of the Shannon decomposition during the ROBDD construction is the variable corresponding to the stuck-at pole. The order of other variables may be arbitrary. From this ROBDD R we select ROBDDs R , R which roots are high and low nodes of the ROBDD R root. The subcircuit of C which output is the same stuck-at pole and inputs are inputs of the circuit C is represented as ROBDD R . The order of variables is the same for all constructed ROBDDs. The ROBDD representing all test patterns for the given stuck-at fault is derived by multiplying and summarizing some of above mentioned ROBDDs. First, we briefly describe a method for finding one test pattern for a given stuck-at fault based on solving the proper Boolean equations and the representation of subcircuits as the SoPs (sum of products). Then a proposed algorithm for deriving all test patterns for a given stuck-at fault is described. The method can be extended to combinational equivalent of a sequential circuit. The example illustrating the algorithm is given.

Keywords

Authors

References