ON ACHIEVING COMPLETE FAULT COVERAGE FOR SEQUENTIAL-MACHINES

A method for generating tests for gate-level stuck-at faults in sequen tial machines is given, which is applicable when a state-table descrip tion of the machine under test is either given or extractable from the given description. A test generation procedure for faults in the stat e table is first described. The test generation procedure is polynomia l in the size of the state table, and is complete and accurate in the following sense. For every given state-table fault, the procedure prov ides either a minimum-length test, or a proof that the fault is undete ctable. This test generation procedure is used for generating complete test sets for stuck-at faults in a gate level implementation of the m achine, by translating stuck-at faults in the gate-level implementatio n into faults in the state table. The translation includes modeling an d extraction. Modeling consists of a simple method to select a small s ubset of state-table faults such that a test set for these faults yiel ds very high coverage of stuck-at faults in the actual implementation. Extraction consists of accurate translation of stuck-at faults in the implementation into equivalent state-table faults, and can be used to derive tests for stuck-at faults which are not detected by the test s et for the modeled faults. Based on the test generation algorithm deve loped and the modeling and extraction of stuck-at faults to translate them into state-table faults, a method to achieve 100% fault-efficienc y for stuck-at faults is proposed, and experimental results for stuck- at faults are presented. Short test sequences are shown to be obtained .