Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
On Computing Signal Probability and Detection Probability of Stuck-At Faults
Chakravarty S., Hunt H. IEEE Transactions on Computers39 (11):1369-1377,1990.Type:Article
Date Reviewed: Jun 1 1991

A key problem for random and pseudorandom testing and the testability analysis of combinatorial circuits is to determine the quality of certain test patterns. For this it is important to know with what probability a stuck-at fault at an internal node can be detected (the computing detection probability, CDP), and with what probability a primary output can be forced to one (the computing signal probability, CSP). Algorithms that compute or estimate these probabilities have been published. This paper briefly reviews some of them. They either are unable to compute the CDP exactly or can do so only for single stuck-at faults.

The authors present their new algorithm, which can compute the CDP exactly even for multiple stuck-at faults. The algorithm starts by transforming the original network by introducing pseudo-gates that model the fault under investigation. The transformed circuit is then decomposed into a tree of supergates. Each supergate is a completely self-contained subnetwork of the original circuit. Supergates do not share any inputs, and each has only one output. The detection probability of a fault is then computed recursively by evaluating the CDP for the supergates forming the circuit. The authors give an algorithm that evaluates the CDP for supergates. They prove that their algorithm has the same worst-case complexity as an algorithm that enumerates all input vectors to the circuit. Their algorithm usually enumerates fewer input vectors, however.

The algorithm presented for the CDP can be modified to solve the CSP problem. Again the authors show that their algorithm has a better average complexity than algorithms that enumerate all input vectors.

The paper addresses an important problem in generating test patterns and evaluating the testability of circuits. This makes it interesting for people involved in designing such systems. Unfortunately the authors do not report an implementation of their algorithm, so it is difficult to judge how it actually compares to existing algorithms.

The paper is well structured and sufficiently readable. Some effort is needed to completely understand the given proofs and algorithms, however.

Reviewer:  Bengt-Olaf Schneider Review #: CR114960
Bookmark and Share
 
Reliability And Testing (B.6.2 )
 
 
Combinational Logic (B.6.1 ... )
 
 
Gate Arrays (B.7.1 ... )
 
 
Signal Processing Systems (C.3 ... )
 
 
Design Styles (B.6.1 )
 
 
Types And Design Styles (B.7.1 )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Reliability And Testing": Date
Sequential logic testing and verification
Ghosh A., Devadas S., Newton A., Kluwer Academic Publishers, Norwell, MA, 1992. Type: Book (9780792391883)
Jul 1 1994
Fault tolerant and fault testable hardware design
Lala P. (ed), Prentice-Hall, Inc., Upper Saddle River, NJ, 1985. Type: Book (9789780133082487)
Nov 1 1985
Hardware fault tolerance
Carter W., John Wiley & Sons, Inc., New York, NY, 1986. Type: Book (9789780471845188)
Feb 1 1989
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy