State Variable Extraction to Reduce Problem Complexity for ATPG and Design Validation

We present a new algorithm to extract characteristic flip-flops, which form a characteristic state set, using state correlation information. The extracted characteristic state set allows us to focus on a significantly smaller set of flip-flops while ignoring other flip-flops, thereby simplifying the target problem and reducing state explosion in very large sequential circuits. Next, partitioning is applied only on the characteristic state variables, and partial state transition graphs (STGs) are built. During test generation, test vectors are generated using a two-fold criteria: (1) whether the vector will expand the overall STGs, and (2) whether this vector will break the relationship among flip-flops within the correlated sets. Experiments showed that our extraction algorithm can reduce the original complete state set by up to 97%. In addition, with the reduced state variables, we achieve not only equal or better coverages for both stuck-at faults and design errors, the execution time is also significantly reduced due to the much smaller set of flip-flops. For some large sequential circuits, highest coverages have been obtained.