Delay-Fault Test Generation and Synthesis for Testability Under a Standard Scan Design Methodology

We address the problems of test generation and synthesis aimed at producing VLSI sequential circuits that are delay-fault testable under a standard scan design methodology. We begin with theoretical results regarding the standard-scan delay testability of finite state machines (FSM’s) described at the state transition graph (STG) level. We show that a one-hot coded and optimized FSM whose STG satisfies a certain property is guaranteed to be fully gate-delay-fault testable under standard scan. We extend this result to arbitrary-length encodings and develop a heuristic state assignment algorithm that results in highly gate-delay-fault testable sequential FSMs, which are also area-efficient, as evinced by results obtained on benchmark FSM circuits. We switch focus to the problem of delay test generation for large sequential circuits and modify a PODEM-based combinational test pattern generator for our purpose. The modifications involve a two time-frame expansion of the combinational logic of the circuit, and the use of backtracking heuristics tailored for our problem. We also employ a version of the scan shifting technique in our test pattern generator. We give an algorithm to determine an efficient ordering of the flip-flops in the scan-chain using the information derived from running a delay test generator on the circuit. Given an ordering of the flip-flops, we give an optimization algorithm that attempts to minimize the number of flip-flops to be made enhanced-scan so as to obtain a required level of delay-fault coverage. We show how the test vector sets derived using our test generator can be compacted by solving a clique covering problem. We present test generation, flip-flop ordering, flip-flop selection and test set compaction results on large benchmark circuits.