Sequential circuit test generation using genetic techniques

The majority of the time spent by automatic test generators for sequential circuits is used to find test sequences for hard-to-detect faults. These faults are either hard to excite, hard to propagate, or both. Although simulation-based test generators avoid the complexity of backtracking by processing in the forward direction only, they often fall short when targeting the hard faults. The problem faced by the genetic algorithm (GA)-based approaches is mainly the lack of knowledge of the sequences necessary to activate the hard faults or propagate the fault effects.; Several new approaches have been developed to address these shortcomings. A hybrid approach using GA-based and deterministic test generators is presented first. Hard-to-detect faults are identified by the GA-based test generator, and they are given to the deterministic test generator in an attempt to find test sequences. The sequences provided by the deterministic test generator are likely to expand the search space and explore the previously unvisited regions of the state space.; Next, a simulation-based test generation algorithm is presented that targets faults individually in two phases: fault activation and fault propagation. Genetically-engineered finite-state machine sequences are used to aid both the fault activation and fault-propagation phases. These finite-state machine sequences provide important information about state justification, as well as propagation of fault effects. Further refinements on state justification using dynamic state traversal are performed to improve the activation of the hard-to-activate faults.; The size of a test set directly impacts the cost of testing. Long test sequences usually result when the hard faults are targeted. Thus, compaction of test sets is necessary to reduce the testing cost. Test set compaction, however, is an NP-complete problem in itself. Instead of an exhaustive search of the most compact test set, two fast algorithms for test set compaction are developed that reduce the test set sizes significantly at very low computational cost.; Finally, synchronizing sequences can greatly benefit test generation. Finding these sequences, however, is nontrivial. The GA is applied to find short synchronizing sequences, and applications of these sequences are also discussed.