IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1992 · 702 citations · 11 references
EngineeringComputer EngineeringComputer ScienceAlgorithmsCircuit TheoryFormal MethodsDesign For TestabilityDigital Logic DesignLogic SynthesisPattern GenerationAutomated Test GenerationAutomatic Test Pattern GenerationBoolean DifferenceBoolean SatisfiabilityBoolean Satisfiability ProblemCombinational Logic SynthesisSatisfiabilityTest Generation
The author describes the Boolean satisfiability method for generating test patterns for single stuck-at faults in combinational circuits. This new method generates test patterns in two steps: first, it constructs a formula expressing the Boolean difference between the unfaulted and faulted circuits, and second, it applies a Boolean satisfiability algorithm to the resulting formula. This approach differs from previous methods now in use, which search the circuit structure directly instead of constructing a formula from it. The new method is general and effective. It allows for the addition of heuristics used by structural search methods, and it has produced excellent results on popular test pattern generation benchmarks.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
11
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
A Computing Procedure for Quantification Theory
Martin Davis, Hilary Putnam · Journal of the ACM · 1960 · 2.6K citations · Full text