Complexity analysis of sequential ATPG

The problem of automatic test pattern generation (ATPG) for sequential circuits has long been recognized as a very difficult task. An analysis is conducted of the sequential complexity of the benchmarks proposed for ISCAS'89 looking for a correlation between attainable coverage and ATPG approach. To pursue this goal, the authors have performed a topological analysis of the circuits, identifying peculiar structures and extracting numerical quantities useful in summarizing some design characteristics. In order to correlate these measures with the intrinsic testing difficulty, they have implemented an experimental sequential ATPG. The experiments run on the benchmarks enabled the authors to identify some important parameters to estimate circuit resistance to ATPG. The results show that the overall performance is dominated by the structure of the circuit's loops and the number of state-controlling inputs.