Efficient VLSI (Very Large Scale Integration) Fault Simulation.
A practical algorithm for fault simulation which simultaneously determines all detectable S-A faults for every gate in the circuit tree C, which requires only the evaluation of a circuit FS(C) which has equal to or less than 3(d+1), when d is the depth of C.
Abstract
Abstract : Let C be an acyclic boolean circuit with n gates and equal to or less than n inputs. A circuit manufacture error may result in a Stuck-at (S-A) fault is a circuit identical to C except a gate v only outputs a fixed boolean value. The (S-A) fault simulation problem for C is to determine all possible S-A faults which can be detected (i.e., faults for which a faulty circuit and C would give distinct outputs) by a given test pattern input. We consider the case where C is a tree (i.e., has fan-out 1). We give practical algorithm for fault simulation which simultaneously determines all detectable S-A faults for every gate in the circuit tree C. Our algorithm requires only the evaluation of a circuit FS(C) which has equal to or less than 3(d+1), when d is the depth of C. Thus the sequential time of our algorithm is equal to or less than 7n, and the parallel time is equal to or less than 3(d+1). Furthermore FS(C) requires only a small constant factor more VLSI area than does the original circuit C. We also extend our results to get efficient methods for fault simulation of oblivious VLSI circuits with feedback lines. Originator supplied keywords include: VLSI; fault simulation; stuck-at faults; reliable computation; boolean functions; partial derivations; and boolean circuits.