Behavior and testability preservation under the retiming transformation

Recently, it has been shown that retiming has a very strong impact on the run time required for sequential, structural automatic test pattern generators (ATPG's), as well as the levels of fault coverage and fault efficiency attained. In this paper, we show that, for circuits with no hardware reset or a global reset state, retiming preserves testability with respect to a single stuckat fault test set by adding a prefix sequence of a predetermined number of arbitrary input vectors. We show that this result holds for test sets derived based on structural and functional methods, and based on the conventional and multiple observation time testing strategies. Furthermore, we derive the conditions under which synchronizing sequences are preserved under retiming. We show that a structural synchronizing sequence for a circuit drives any of its corresponding retimed circuits to an equivalent state. In addition, we show that functional synchronizing sequences are preserved under retiming by adding a prefix sequence of a predetermined number of arbitrary input vectors. The impact of retiming on ATPG complexity and test-set preservation under retiming suggest a new approach for enhancing the performance of structural, sequential ATPG's. Experimental results show that high fault coverages can be achieved on high-performance circuits optimized by retiming with much less CPU time (a reduction of two orders of magnitude in several instances) than if ATPG is attempted directly on those circuits.