DELTEST: Deterministic test generation for gate delay faults

This paper presents an efficient approach to generate tests for gate delay faults. Unlike other known algorithms which try to generate a “good” delay test the presented algorithm is complete in the sense that if a delay test exists it will generate an optimal delay test. An optimal delay test for a gate delay fault is a test that sensitizes the longest functional path through the fault site. Especially the cone-oriented test generation - each output cone is processed separately - and the delay graph - a new method to keep track of all possible paths in a given situation - contribute to the efficiency of the algorithm. Although it is an NP-hard problem to generate optimal delay tests, experimental results show that it is tractable for a wide class of circuits. Close to optimal delay test sets could be generated for most ISCAS benchmark circuits containing up to 38,000 nodes