Automatic Test Pattern Generation:A Complete Test Set

A Complete Test Set

Any one of the presented algorithms can be used repeatedly to generate a set of patterns for all the faults. This section focuses on methods to accelerate the process and result to a smaller set of test patterns. It describes three commonly used techniques: fault collapsing, elimination of randomly testable faults, and fault simulation. More sophisticated methods to reduce the total number of required test patterns (test set compaction) can be found in the literature but such methods do not necessarily accelerate the ATPG process and are typically applied after a set of test patterns that detect all the faults has been generated. The first two techniques, fault collapsing and elimination of randomly testable faults, are typically applied prior to generating any test pattern. The latter is applied whenever a test pattern is generated. The objective in all three described atechniques is to quickly reduce the number of faults on which the algorithms of the previous subsection apply. It is assumed that the CUT is combinational.

For a circuit with n lines in total, there are 2n possible stuck-at faults to consider. Fault collapsing reduces this initial number by taking advantage of equivalence and dominance relations among faults. Two faults are said to be functionally equivalent if all patterns that detect the one detect also the other. Given a set of functionally equivalent faults, only one fault from that set has to be considered for test generation. A fault j is said to dominate a fault h if all patterns that detect h detect also j, and there is at least one pattern that detects j but not h. Then only h needs to be considered for test generation. It can be shown that the fault s-a-(c XOR i ) on the output of a gate is functionally equivalent with the fault s-a-c on any of the gate inputs and that the fault s-a-(c XOR i ) on the output of a gate dominates the fault s-a-c on any of the gate inputs, where c is the controlling value of the gate and i is 1 (0) if the gate is inverting (noninverting). As an example, using these relations on the circuit of Figure 69.1, we obtain that (F-s-0, A-s-0, B-s-0), (G-s-1, C-s-1, D-s-1), (J-s-1, G-s-0, I-s-0), (M-s-0, H-s-1, K-s-1), (N-s-0, E-s-0, 1-s-0) are functionally equivalent sets of faults, and that F-s-1 dominates A-s-l and B-s-1, G-s-0 dominates C-s-0 and D-s-0, J-s-0 dominates G-s-l and I-s-1, M-s-1 dominates H-s-0 and K-s-0, and N-s-1 dominates E-s-1 and L-s-1. Given these relations, only the set of faults {A-s-1, B-s-1, C-s-0, D-s-0, G-s-1, I-s-1 H-s-0, K-s-0, E-s-1, 1-s-1, F-s-0, M-s-0, N-s-0} need be considered and the number of target stuck-at faults is reduced from 28 to 13. In general, more faults can be eliminated if fault equivalence and fault dominance are examined using the test function for the stuck-at faults. However, such an approach is time consuming and may be useful only for test set compaction.

A very simple way of eliminating faults from a target fault list is to generate test patterns at random and verify, by fault simulation, which target faults (if any) each generated pattern detects. Techniques for fault simulation are reviewed later. First we focus on the random pattern generation process. Such patterns are generated by a pseudorandom method, that is, an algorithmic method whose behavior under specific statistical criteria seems close to random. Eliminating all faults by pseudorandom test pattern generation generally requires a very large number of patterns but the ATPG is accelerated because fault simulation process is very fast compared to ATPG for one SSF. Under the assumption of uniform input distribution and independent test pattern generation, the smallest number of patterns to detect with probability P, a fault whose detection probability is d is N = ln(P)/ln(1 – d). In general, faults with small detection probability are referred to as randomly untestable or hard-to-detect faults, whereas faults with high detection probability are referred to as randomly testable or easy-to-detect faults. For example, in a circuit consisting of a single k-input AND gate with output line I, the fault I s-a-0 is a hard-to-detect fault as only one out of 2k patterns can detect it, whereas the fault I s-a-1 is an easy-to-detect fault as 2k–1 out of 2k patterns can detect it. In practice, an acceptable number of pseudorandom test patterns are generated and simulated to drop many easy-to-detect faults from the target fault list, with all remaining faults given over to a deterministic (as opposed to pseudorandom) TPG tool [2,3].

The remaining of the section reviews algorithms for fault simulation which is applied whenever a test pattern has been generated. The goal is to determine quickly all the faults that the test pattern detects and remove them for the list of not-yet-targeted faults. The fault simulation process is composed of one or more topological circuit traversals, and requires polynomial time in contrast to the ATPG process which requires (in the worst-case) exponential time per fault.

The simplest form of simulation is called single-fault propagation. After a test pattern is simulated, the stuck-at faults are inserted one after the other. The values of every faulty circuitry are compared with the error-free values. A faulty value needs to be propagated from the line where the fault occurs. The propagation process continues line-by-line, in a topological search manner, until there is no faulty value that differs from the respective good one. If the latter condition is not satisfied, the fault is detected.

In an alternative approach, called parallel-fault propagation, the goal is to simulate n test patterns in parallel using n-bit memory. Gates are evaluated using Boolean instructions operating on n-bit operands. The problem with this type of simulation is that events may occur only in a subset of the n patterns while at a gate. If on average a fraction B of gates have events on their inputs in one test pattern, the parallel simulator will simulate 1/B more gates than an event-driven simulator. Since n patterns are simulated in parallel, the approach is more efficient when n is not less than 1/B, and the speed-up is nB. Single and parallel fault propagation can also be combined efficiently.

In deductive fault simulation only one topological circuit traversal is required. The idea is to maintain for each line l a list Ll of SSFs that have been propagated by the test patterns up to that line. While examining a gate g with inputs a, b and output c, list Lc is constructed by manipulating the contents of La and Lb. Assume that g is an AND gate and that the test pattern brings values a = 0, b = 1. Lc contains c-s-1 since c = 0. Additional faults in Lc include faults in La because b has a noncontrolling value. However, only those faults in La that are not part of Lb can propagate to line c ; faults in La that also propagate to line b essentially change its value to controlling and cannot propagate. Such logical arguments can be used to generate the list Lc at the output of gate g, under any assignment of binary values to its inputs. This simulation method is faster than the single fault simulation method when the contents of the fault lists are small on many lines in the CUT.

An approach to further accelerate the fault simulation process is to report many but not all the SSFs that the test pattern detects. The most popular representative of approximate fault simulation is the critical path tracing approach. For every test pattern, the approach first simulates the fault-free circuit and then determines the detected faults by determining which lines have critical values. Such lines are called critical. A line has critical value 0 (1) in pattern t if and only if test pattern t detects the fault stuck-at 0 (1) at the line. Therefore, finding the critical lines in pattern t amounts to finding the stuck-at faults that are detected by t. Critical lines are found by backtracking from the primary outputs. Such a backtracking process determines paths of critical lines that are called critical paths. The process of generating critical paths uses the concept of sensitive inputs of a gate with two or more inputs (for a test pattern t). This is determined as follows: If only input l has the controlling value of a gate, then it is sensitive. On the other hand, if all the inputs of a gate have noncontrolling value, then they are all sensitive. There is no other condition for labeling some input line of a gate as sensitive. Thus, the sensitive inputs of a gate can be identified during the fault-free simulation of the circuit.

The operation of the critical path tracing algorithm is based on the observation that when a gate output is critical, then all its sensitive inputs are critical. On fan-out free circuits, critical path tracing is a simple traversal that applies recursively to the above observation. The situation is more complicated when there exist re-convergent fan-outs. This is illustrated in Figure 69.4. In Figure 69.4(a), starting from g, we determine critical lines g, e, b, and cl as critical, in that order. To determine whether c is critical, we need additional analysis. The effects of the fault stuck-at 0 on line c propagate on re-convergent

paths with different parities which cancel each other when they re-converge at gate g. This is called self-masking. Self-masking does not occur in Figure 69.4(b) because the fault propagation from c2 does not reach the re-convergent point. In Figure 69.4(b), c is critical.

Therefore, the problem is to determine whether self-masking occurs or not at the stem of the circuit. Let 0 (1) be the value of a stem l under test pattern t. A solution is to explicitly simulate the SSF c-s-1 (c-s-0), and if t detects this fault, then l is marked as critical. Instead, the approach uses bottlenecks in the propagation of faults that are called capture lines. Let a be a line sensitized to SSF fault f with a pattern t. If every path sensitized to f either goes through a or does not reach any other line with a greater topological level, then a is a capture line of f under pattern t. Such a line is common to all paths on which the effects of f can propagate to the primary output under pattern t. The capture lines of a fault form a transitive chain. Therefore, a test t detects fault f if and only if all the capture lines of f under test pattern t are critical. Thus, to determine whether a stem is critical, the algorithm does not propagate the effects of the fault step up to the primary output; it only propagates the fault effects up to the capture line that is closest to the stem.