SAT-Based Test Pattern Generation with Improved Dynamic Compaction

During the last years, SAT-based ATPG has been proved to be a powerful complement of traditional structural approaches. It outperforms structural methods when applied to hard-to-detect faults, and it can be combined with advanced SAT solving techniques in order to compute provably optimal solutions to complex test generation problems with optimisation goals. However, one weakness of SAT-based ATPG methods is their relatively high pattern count, which results largely from the over specification of the generated patterns. In order to overcome this weakness, we present a dynamic compaction technique specifically designed to work with SAT-based ATPG. We systematically investigate the impact of a conflict limit parameter and of several fault list sorting strategies on both test compactness and run-time. Using the best parameter combination, our SAT-based algorithm was able to generate with feasible computational effort more compact test sets for ISCAS circuits than a commercial structural tool, and the pattern counts for industrial circuits were reduced significantly.