After producing a chip, the functional correctness of the integrated circuit
has to be checked. Otherwise, products with malfunctions would be delivered
to customers, which is not acceptable for any company. During this
post-production test, input stimuli are applied and the correctness of the
output response is monitored. These input stimuli are called test patterns.
Many algorithms for Automatic Test Pattern Generation (ATPG) have been
proposed in the last 30 years. However, due to the ever increasing design
complexity, new techniques have to be developed that can cope with today’s
circuits.
Classical approaches are based on backtracking over the circuit structure.
They have been continuously improved by using dedicated data structures
and adding more sophisticated techniques like simplification and learning.
Approaches based on Boolean Satisfiability (SAT) have been proposed since
the early 1980s. Comparisons to other “classical” approaches based on FAN,
PODEM and the D-algorithm have shown the robustness and effectiveness
of SAT-based techniques.