SAT-Based Test Generation For Path Delay Faults

With the growing size and increasing complexity of VLSI circuits, the test generation for integrated circuit(IC) has been the bottleneck of IC industry of our country for years. The requirement of reliability can not be satisfied only by tests for stuck-at faults today, resulting in that Automatic test pattern generation (ATPG) for delay faults is becoming more and more significant.In this paper, ATPG problems for path delay faults are researched based on Boolean satisfiability (SAT), including non-robust tests, robust tests and transition path delay fault model. Meanwhile, the corresponding algorithms are presented and implemented. The contents of this paper are outlined as follow.1. Algorithms for test generation for path delay fault model are presented first. We discuss how to convert an ATPG problem to a SAT formula where both non-robust and robust test are considered. Based on the formulation of a circuit, constrains for sensitization of the circuit according to non-robust or robust tests are added, and the structured CNF formula is solved by a SAT-solver. Compare to the traditional algorithms, this approach is more convenient and efficient.2. A new fault model:transition path delay fault model presented by I. Promeranz in 2008, which is used for the detection of the faulty behavior caused by cumulated effects of small extra delays along a sub path, is analyzed in detail and compared with the path delay fault model in this paper. A test for a transition path delay fault satisfies the additional requirement that it detects all the transition faults along the path.3. An SAT-based algorithm for the test generation for transition path delay faults is proposed and compared with the path delay faults. Compared to an arbitrary non-robust test, a test for a transition path delay fault satisfies the additional requirement that it detects all the transition faults along the path. As a result, both the path delay fault and all the transition faults on the path are detected when an expected transition does not occur at the path output. The effectiveness of the algorithm is demonstrated on a set of ISCAS'85 benchmarks.