Automatic Test Pattern Generation (ATPG) based on Boolean Satisfiability (SAT) has been proposed as an alternative to classical search algorithms. SAT-based ATPG turned out to be more robust and more effective by formulating the problem as a set of equations. In this paper we present an efficient ATPG algorithm that makes use of powerful SAT-solving techniques. Problem specific heuristics are applied to guide the search. In contrast to previous SAT-based algorithms, the new approach can also cope with tri-states. The algorithm has been implemented as the tool PASSAT. Experimental results on large industrial circuits are given to demonstrate the quality and efficiency of the algorithm.
展开▼
