REDUNDANCY IDENTIFICATION REMOVAL AND TEST-GENERATION FOR SEQUENTIAL-CIRCUITS USING IMPLICIT STATE ENUMERATION

The recent advances in finite state machine (FSM) verification based o n implicit state enumeration provide a powerful method for FSM verific ation. This method can be extended to test generation and redundancy i dentification. The extended method constructs the product machine of t wo FSM's to be compared, and reachability analysis is performed by tra versing the product machine to find any difference in I/O behavior. Wh en an output difference is detected, the information obtained by reach ability analysis is used to generate a test sequence. This method is c omplete and it generates one of the shortest possible test sequences f or a given fault. However, applying this method indiscriminately for a ll faults may result in unnecessary waste of computer resources. In th is paper, we present an efficient method based on reachability analysi s of the fault-free machine (three-phase ATPG) in addition to the powe rful but more resource-demanding product machine traversal. We report on the application of these algorithms to the problems of generating t est sequences, identifying redundancies, and removing redundancies.