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.