View article

Automatic test pattern generation (ATPG) is one of the first applications that motivated the development of modern Boolean satisfiability (SAT). It is now widely accepted that ATPG is easy for current state-of-the-art SAT solvers. Nevertheless, as with any NP-hard problem, for large complex industrial circuits, some faults may be difficult to detect or prove undetectable. Recent work on SAT-based ATPG has been motivated by industrial designs with ever increasing size, for which more efficient ATPG models are essential. Moreover, ATPG models and algorithms find applications in a number of other settings, which further motivate the development of more efficient SAT-based ATPG solutions. Interestingly, despite the interest in more efficient ATPG approaches, the core SAT-based ATPG model has remained essentially unchanged since it was first proposed in the 1980s. This paper describes an alternative model for …