โ Scribed by John H. Reif
No coin nor oath required. For personal study only.
Let C be an acycfic Boolean circuit with n gates and _< n inputs. A circuit manufacture error may result in a "Stuck-at" (S-A) fault in 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 a practical algorithm for fault simulation which simultaneously determines all detectable S-A faults for every gate in the circuit tree C. Our algorithm required only the evaluation of a circuit FS(C) which has < 7n gates and has depth _< 3(d -{-1), when d is the depth of C. Thus the sequential time of our algorithm is _< 7n, and the parallel time is < 3(d 4-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.
๐ SIMILAR VOLUMES
State-of-the-art technologies for VLSI circuits give rise to various defect mechanisms that may cause a circuit to fail when operated at its designated speed of operation. Such defects are conventionally modeled by delay faults. In this paper, we review delay fault models used for circuits described
Recent advances in VLSI and communications technology have made the use of multiprocessors m circuit simulation cost-effective\_ However, for achieving maximum speedup in concurrent circuit simulation, the problem of mapping the tasks of a concurrent program onto the processors of a muitiprocessor m
This article emphasizes simulation-based sampling techniques for estimating fault coverage that use small fault samples. Although random testing is considered to be the primary area of application of the technique it is also suitable for estimating the fault coverage of nonrandom tests based on spec