## Efficient VLSI fault simulation

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.

### Duke Scholars

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- 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

*Computers and Mathematics with Applications*,

*25*(2), 15–32. https://doi.org/10.1016/0898-1221(93)90219-L

*Computers and Mathematics with Applications*25, no. 2 (January 1, 1993): 15–32. https://doi.org/10.1016/0898-1221(93)90219-L.

*Computers and Mathematics with Applications*, vol. 25, no. 2, Jan. 1993, pp. 15–32.

*Scopus*, doi:10.1016/0898-1221(93)90219-L.

## Published In

## DOI

## ISSN

## Publication Date

## Volume

## Issue

## Start / End Page

## Related Subject Headings

- 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