PASSAT: efficient SAT-based test pattern generation for industrial circuits

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 A...

Full description

Saved in:
Bibliographic Details
Main Authors: Junhao Shi, Fey, G., Drechsler, R., Glowatz, A., Hapke, F., Schloffel, J.
Format: Conference Proceeding
Language:eng ; jpn
Subjects:
Algorithm design and analysis
Automatic test pattern generation
Circuit testing
Computer science
Engines
Equations
Input variables
Logic programming
Robustness
Test pattern generators
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2159-3469
2159-3477
DOI:10.1109/ISVLSI.2005.55