Synchronizing sequences and symbolic traversal techniques in test generation

Asynchronizing sequence drives a circuit from an arbitrary power-up state into a unique state. Test generation on a circuit without a reset state can be much simplified if the circuit has a synchronizing sequence. In this article, a framework and algorithms for test generation based on themultiple observation time strategy are developed by taking advantage of synchronizing sequences. Though it has been shown that the multiple observation time strategy can provide a higher fault coverage than the conventional single observation time strategy, until now the multiple observation time strategy has required a very complex tester operation model (referred asMultiple Observation time-Multiple Reference strategy (MOMR) in the sequel) over the conventional tester operation model. The overhead of MOMR, exponential in the worst case, has prevented widespread use of the method. However, when a circuit is synchronizable, test generation can employ the multiple observation time strategy and provide better fault coverages, without resorting to MOMR. This testing strategy is referred asMultiple Observation time-Single Reference strategy (MOSR). We prove in this article that the same fault coverage, that could be achieved in MOMR, can be obtained in MOSR, if the circuit under test generation is synchronizable. We investigate how a synchronizing sequences simplifies test generation and allows to use MOSR under multiple observation time strategy. The experimental results show that higher fault coverages and large savings in CPU time can be achieved by the proposed framework and algorithms over both existing single observation time strategy methods as well as other multiple observation time strategy methods.