Test pattern generation using Boolean satisfiability
- 1 January 1992
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 11 (1) , 4-15
- https://doi.org/10.1109/43.108614
Abstract
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 benchmarksKeywords
This publication has 11 references indexed in Scilit:
- Search strategy switching: an alternative to increased backtrackingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A framework for evaluating test pattern generation strategiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- SOCRATES: a highly efficient automatic test pattern generation systemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988
- On the Acceleration of Test Generation AlgorithmsIEEE Transactions on Computers, 1983
- An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic CircuitsIEEE Transactions on Computers, 1981
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Diagnosis of Automata Failures: A Calculus and a MethodIBM Journal of Research and Development, 1966
- A Computing Procedure for Quantification TheoryJournal of the ACM, 1960
- On a Theory of Boolean FunctionsJournal of the Society for Industrial and Applied Mathematics, 1959