## Efficient VLSI fault simulation

Publication ,  Journal Article
Reif, JH
Published in: Computers and Mathematics with Applications
January 1, 1993

Let C be an acyclic 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 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 + 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. © 1992.

## Published In

Computers and Mathematics with Applications

0898-1221

January 1, 1993

25

2

## Start / End Page

15 / 32

• Numerical & Computational Mathematics
• 49 Mathematical sciences
• 46 Information and computing sciences
• 35 Commerce, management, tourism and services
• 15 Commerce, Management, Tourism and Services
• 08 Information and Computing Sciences
• 01 Mathematical Sciences

### Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1993). Efficient VLSI fault simulation. Computers and Mathematics with Applications, 25(2), 15–32. https://doi.org/10.1016/0898-1221(93)90219-L
Reif, J. H. “Efficient VLSI fault simulation.” Computers and Mathematics with Applications 25, no. 2 (January 1, 1993): 15–32. https://doi.org/10.1016/0898-1221(93)90219-L.
Reif JH. Efficient VLSI fault simulation. Computers and Mathematics with Applications. 1993 Jan 1;25(2):15–32.
Reif, J. H. “Efficient VLSI fault simulation.” Computers and Mathematics with Applications, vol. 25, no. 2, Jan. 1993, pp. 15–32. Scopus, doi:10.1016/0898-1221(93)90219-L.
Reif JH. Efficient VLSI fault simulation. Computers and Mathematics with Applications. 1993 Jan 1;25(2):15–32.

## Published In

Computers and Mathematics with Applications

0898-1221

January 1, 1993

25

2

15 / 32