Exact and approximate membership testers
Larry Carter, Robert Floyd, et al.
STOC 1978
In [1] and [2] Savir developed many facets of syndrome-testing (checking the number of minterms realized by a circuit against the number realized by a fault-free version of that circuit) and presented evidence showing that syndrome-testing can be used in many practical circuits to detect all single faults. In some cases, where syndrome-testing did not detect all single stuck-at-faults, Savir showed that by the addition of a small number of additional “control” inputs and gates one would get a function which is syndrome-testable for all single stuck-at faults, and yet which realizes the original function when the “control” inputs are fed appropriate values. However, he left open the question of whether one could always modify a circuit to achieve syndrome-testability. In this correspondence we show that a combinatorial circuit can always be modified to produce a single-fault, syndrome-testable circuit. Copyright © 1981 by The Institute of Electrical and Electronics Engineers, Inc.
Larry Carter, Robert Floyd, et al.
STOC 1978
George Markowsky, Andrew Wohlgemuth
Discrete Applied Mathematics
Alfredo DeSantis, George Markowsky, et al.
FOCS 1988
Andrew Wohlgemuth, George Markowsky
Mathematical Biosciences