Combinational test generation using satisfiability
Paul R. Stephan, Robert K. Brayton, Alberto Luigi Sangiovanni-Vincentelli · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1996
We present a robust, efficient algorithm for combinational test generation using a reduction to satisfiability (SAT). The algorithm, Test Generation Using Satisfiability (TEGUS), solves a simplified test set characteristic equation using straightforward but powerful greedy heuristics, ordering the variables using depth-first search and selecting a variable from the next unsatisfied clause at each branching point. For difficult faults, the computation of global implications is iterated, which finds more implications than previous approaches and subsumes structural heuristics such as unique sensitization. Without random tests or fault simulation, TEGUS completes on every fault in the ISCAS networks, demonstrating its robustness, and is ten times faster for those networks which have been completed by previous algorithms. Our implementation of TEGUS can be used as a base line for comparing test generation algorithms; we present comparisons with 45 recently published algorithms. TEGUS combines the advantages of the elegant organization of SAT-based algorithms with the efficiency of structural algorithms.
Cited by 326 works. doi:10.1109/43.536723
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The complexity of theorem-proving procedures
- Computer Architecture: A Quantitative Approach
- Diagnosis of Automata Failures: A Calculus and a Method
- An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits
- Combinational profiles of sequential benchmark circuits
- A neutral netlist of 10 combinational benchmark circuits and a target translator in FORTRAN
- Random number generators: good ones are hard to find
- SOCRATES: a highly efficient automatic test pattern generation system
- Sequential circuit design using synthesis and optimization