On the Over-Specification Problem in Sequential ATPG Algorithms

Most sequential ATPG (Automatic Test Pattern Generation) programs employ the time-frame expansion technique. Within a time-frame, combinational test generation algorithms that are variations of D-algorithm or PODEM are used. In this paper, we show that some ATPG programs may err in identifying untestable faults. In other words, these test generators may not be able to find the test sequence for a testable fault, even allowed infinite run time, and furthermore may mistakenly claim it as untestable. The main problem of these programs is that the underlying combinational test generation algorithm may overspecify the requirements at the present state lines. We show a necessary condition that the underlying combinational test generation algorithm must satisfy to ensure a correct sequential ATPG program. It is shown that the simple D-algorithm satisfies this condition while PODEM and the enhanced D-algorithm do not. We also study the impact of over-specification on the length of the generated test sequence. Overspecification causes a longer test sequence. Experimental results are presented.