Static compaction using overlapped restoration and segment pruning

We propose a new technique for static compaction of test sequences. Our method is based on two key ideas: (1) overlapped vector restoration, and (2) identification, pruning, and re-ordering of segments. Overlapped restoration provides a significant computational advantage for large circuits. Segments partition the compaction problem into sub-problems. Segments are identified, dynamically pruned and re-ordered to achieve further compaction and speed up. When compared to the fastest method proposed by I. Pomeranz and S.M. Reddy (1997), our method was 5 to 30 times faster on ISCAS circuits and 20 to 50 times faster on large, industrial designs. The new algorithm was able to successfully process large industrial designs that could not be handled by earlier techniques in 2 CPU days.