Critical Path Tracing-An Algorithm for Test Generation and Fault Simulation

Presently,almost all the algorithmic test generation methods for digital circuits, such as the D-algorithm,the PODEM-algorithm and the F AN-algorithm,etc., are designed in such a situation where a test is generated first for a given fault and then all faults that can be detected by this test are found out by fault simulation. In this way, test generation and fault simulation are separated iato two different st eps. This paper presents the critical path tracing racthod, a new algorithm for both test generation and fault simulation. The so called "critical path tracing" is perfor med from primary outputs to primary iaputs in the circuit. The generation of a test and the determination of the faults that can be detected by this test are accomplis hed simultaneously, i.e,,test generation is combined with fault simulation closely. Like the PODEM-algorithm and the FAN-algorithm, the discussion in this paper is limited to the single s-a-0 and s-a-1 faults in combinational circuits.The strategy of critical path tracing is described in detail and it is ensured that all testable faults in the circuit can be detected by the tests generated in this manner. The total number of tests will not exceed the sum of the number of tests for every single ga te.