Test set compaction using relaxed subsequence removal

Recent work observed that a subset of states are frequently visited during the simulation of a test set for a sequential circuit. Re-visiting a state implies that a cycle has been traversed in the state diagram. Removal of su bsequence responsible for the cycle can lead to static compaction. The size of a cycle is the number of vectors in its subsequence. In this work, we e xtend the subsequence removal technique to provide significantly higher sta tic compaction for sequential circuits. We show that state relaxation techn iques can be used to identify more or larger cycles in a test set. State re laxation creates more opportunities for subsequence removal and hence, resu lts in better compaction. Relaxation of a state is possible since not all m emory elements in a finite state machine have to be specified for a state t ransition. The proposed technique has several advantages: (1) test sets tha t could not be compacted by existing subsequence removal techniques can now be compacted, (2) the size of cycles in a test set can be significantly in creased by state relaxation and removal of the larger sized cycles leads to better compaction, (3) only two fault simulation passes are required as co mpared to trial and re-trial methods that require multiple fault simulation passes, and (4) significantly higher compaction is achieved in short execu tion times as compared to known subsequence removal methods. Experiments on ISCAS89 sequential benchmark circuits and several synthesized circuits sho w that the proposed technique consistently results in significantly higher compaction in short execution times.