MUST: Multiple-stem analysis for identifying sequentially untestable faults

In this paper we present MUST - a multiple-stem analysis algorithm for identifying untestable faults in sequential circuits. In general, processing untestable faults is the most time-consuming part of a sequential ATPG. MUST extends the scope of the single-stem analysis done in the FIRES algorithm by identifying additional untestable faults that cannot be found by single-stem analysis. While its computational requirements are greater than those of FIRES, the run-time of MUST remains significantly lower than that used by sequential ATPG. We show that the faults identified by MUST are difficult targets for conventional ATPG programs, that can benefit by using MUST as a preprocessor and excluding the untestable faults identified by multiple stem analysis from the target faults processed by ATPG. We report experimental results obtained by our prototype implementation of MUST on ISCAS benchmarks and other circuits.