A global test generation system for sequential circuits

With the rapid progress of VLSI technology, integrated circuit complexity increases greatly. The reliability of a chip is very important to VLSI engineering and even our daily life. Due to the increase in size and complexity of circuits placed on a chip, it is very difficult to test a chip at an affordable cost.; Automatic Test Pattern Generation (ATPG) plays an important role in VLSI technology. Reduction in test application time and test set size is highly desirable for the reduction of the overall cost in integrated circuit fabrication and testing. Testing of digital circuits involves the generation of a set of test vectors and their application to detect faults in the circuits. An important part of testing is the creation of effective test vectors. The test generation problem for sequential circuits is known to be a difficult task. It is difficult to achieve a significant breakthrough in realizing efficient ATPG algorithms to test large sequential circuits.; A global test generation approach for sequential circuits, called GLOBALTEST, is presented in this dissertation. Global test generation is formulated as the problem of tracing different sensitive paths from the primary inputs and present state lines to the primary outputs and next state lines in a circuit. It consists of two parts: a fault-independent test generation algorithm and a fault-oriented test generation algorithm. At first, a new backward assignment method is presented to extract the ON/OFF sets of the primary outputs and next state lines by partitioning circuits. The combinational test vectors can be extracted at the same time. State justification and state differentiation are efficiently performed using the ON/OFF sets of the primary outputs and next state lines. To enhance the efficiency of state differentiation in the existing three-phase ATPG, a backward deterministic method for state differentiation is proposed and the order of next state lines in state differentiation is presented. The fault-independent test generation algorithm can detect most of the testable faults in the sequential circuits. A disadvantage of the method is that it can not determine the redundant faults.; The fault-oriented test generation algorithm is developed to detect the remaining faults and determine the redundant faults. The recent advances in combinational test generation based on Boolean satisfiability and transitive closure provide a powerful method for test generation. We extend Boolean satisfiability and transitive closure to sequential circuit test generation.; Test compaction is an important part in test generation. We formulate the test compaction problem as the set covering problem. An efficient set covering algorithm (HICOMPACT) is proposed to compact test vectors. It attempts to select the necessary test vectors for the faults detected and eliminate other redundant test vectors so the original fault coverage is not compromised. This method generates a compact testing sequence for a given fault.; The global test generation algorithm for sequential circuits is tested using the IS-CAS'89 sequential benchmark circuits. The proposed algorithm has yielded a high fault coverage and provided time efficient procedures to generate tests for large sequential circuits. The experimental results are compared with other existing test generation systems.