Automatic Test Pattern Generation:Logical Faults

Automatic test pattern generation (ATPG) is the process of obtaining a set of input stimuli, called test patterns that detect possible faulty behavior of a circuit after its fabrication. This may be due to fabrication defects, fabrication errors, or physical failures. Such physical defects in a circuit are detected using fault models that are related to the modeling of the circuit so that we detect the impact of these faults in the operation of the circuit. Only permanent defects that are always present after their occurrence are examined. Sections 69.1 and 69.2 present ATPG techniques for defects in random logic at the gate level or register transfer level. Defects during fabrication can affect the state of logic signals in the circuit independent of its operating frequency. These defects are modeled by logical faults and are discussed in Section 69.1. Some manufacturing defects may impact the functionality of the circuit only under high operating frequency and are modeled by delay faults. Delay faults are examined in Section 69.2. The challenge in random logic ATPG is due to the difficulty in controlling and observing logic values at the fault site. The ATPG problem is intractable [1]. Section 69.3 considers memory testing and reviews fault models and ATPG methods. In memory testing the logic values are directly controllable and observable at the fault site. The ATPG process is complicated due to the complex fault models used and the very large number of memory cells.

Logical Faults

Defects in a circuit that are modeled by logical faults include breaks on wires, open transistors, shorted transistors, and technology-specific faults. The most common fault model used in practice is the stuck- at mode where lines in a gate- or register-transfer-level description of a circuit are assumed to be set permanently to a “1” or “0” value in the presence of a fault. An additional restriction is that the modeled faults cause only one line in the circuit to have a stuck-at value. The fault model is called the single stuck- at fault (SSF) model. Patterns generated under the SSF model have been shown in practice to cover many faults under more complex fault models, such as the multiple-stuck-at fault model where more than one line may be permanently set to value 0 or 1 [2,3].

Given a list of faults, the primary goal of ATPG is to generate a test pattern for each of these faults, and additionally to keep the overall number of test patterns generated as small as possible. The latter is required for reducing the time/cost of applying the test patterns to the circuit. This section presents some algorithms for finding a test pattern for a single fault. Aspects for accelerating the ATPG process for all the faults and reducing the number of generated test patterns are also described. The methods are described assuming the SSF model.

ATPG Algorithms

Let l s-a-v denote the target fault of line l being stuck at value v in a combinational circuit. The fault function of l s-a-v is the function that contains all possible test patterns for this fault. One method for generating a pattern is to form the test function and then identify a cube (product term) in the function. Recent advances in function representations and manipulations have sparked interest in this direction. Compact graph-based data structures, such as reduced order binary decision diagrams (ROBDDs), store functions in a canonical form, in which case a cube can be selected very fast [3]. Alternatively, efficient methods have been proposed for identifying a cube of a function that is expressed as a product of sums [4].

The fault function can be generated in many ways, and it has been also shown how to convert it into a compact product-of-sums form if desirable. One approach is via a virtual circuit construction. First, the faulty circuit is formed, a simplification of the circuit under test (CUT) by fixing value v on line l. Then the CUT and the faulty circuit are merged so that they are driven by a common set of inputs. In addition, the outputs of the two circuits are pair-wise-connected to two-input exclusive-OR (XOR) gates. The fault function is then formed by applying a Boolean OR operation on the functions at the XOR gates.

The process can be accelerated by generating a test pattern without generating the test function since ATPG typically requires that only one cube of the test function be returned. Such ATPG algorithms manipulate the structure of the CUT and may revisit any circuit line several times in an attempt to generate a pattern such that (1) the pattern brings l to have a value v (fault activation) and (2) the same pattern carries over the effect of the fault to a primary output (fault propagation). A path from line l to a primary output along each line of which the effect of the fault is carried over is called a sensitized path. The case of a line l having a value of 1 in the correct circuit and a value of 0 in the circuit under the fault l s-a-v is denoted by the symbol D and, similarly, the opposite case is denoted by D′. Given the symbols D and D′, the basic Boolean operations AND, OR, and NOT can be extended in a straightforward manner. For example, AND(1, D) = D, AND(l, D) = D, AND(O, D) = 0, AND(O, D) = 0, AND(x, D) = x, AND(x, D) = x (where x denotes the don’t-care case), etc.

A basic TPG algorithm for combinational circuits is the D-algorithm [5]. This algorithm works as follows: all values are initially assigned a value of x, except line l which is assigned a value of D if the fault is l s-a-0, and a value of D′ if the fault is l s-a-l. Let G be the gate whose output line is l. The algorithm first selects an assignment for the inputs of G out of all possible assignments that produce the appropriate D-value (i.e., a D or D′) at the output of G. This step is known as fault activation. All possible assignments are fixed for each gate type and are referred to as the primitive d-cubes for the fault (pdcfs) of the gate. For example, the pdcfs of a two-input AND gate are 0xD′, x0D′, and 11D, and the pdcfs of a two-input OR gate are lxD, x1D, and 00D′ (using the notation abc for a gate with input values a and b and output value c).

Subsequently, the algorithm repeatedly selects a gate from the set of gates whose output is currently x but has at least one input with a D-value. This set of gates is known as the D-frontier. Then it selects an assignment for the inputs of that gate out of all possible assignments that set the output to a D-value. All possible assignments are fixed for each gate type and are referred to as the propagation d-′cubes (pdcs) of the gate. For example, the pdcs of a two-input AND gate are 1DD, D1D, 1D′D′, D′1D′, DDD, and D′D′D′. By repeated application of this step, a D-value is eventually propagated to a primary output. This step is known as fault propagation.

In a third step, the algorithm finds an assignment of values for the primary inputs that establishes the candidate values required in steps (1) and (2). This step is known as line justification. For each value that is not currently accounted for, the line justification process tries to establish (“justify”) the value by (a) assigning binary values (and no D-values) on the inputs of the corresponding gate, working its way back to the primary inputs (this process is referred to as backtracing; and (b) determining all values that are imposed by all candidate assignments thus far (implication) and checking for any inconsistencies (consistency check).

If an inconsistency is found during the line justification step, then the computation is restored to its state at the last decision point. This process is known as backtracking. A decision point can be (a) the decision in step (1) of which pdcf to select; (b) the decisions in step (2) of which gate to select from the D-frontier and which pdc to select for that gate; or (c) the decision in step (3) of which binary combination to select for each value that has to be justified.

If line justification is eventually successful after zero or more backtrackings, then the existing values on the primary inputs (some of which may well be x) constitute a test pattern for the fault. Otherwise, no pattern can be found to test the given fault and that fault is thus shown to be redundant.

The order of the fault propagation and line justification steps may be interchanged, or even the two steps may be interspersed, in an attempt to reduce the running time, but the discovery or not of a pattern is not affected by such changes.

Consider the circuit in Figure 69.1 and G s-a-1. To establish G = D, the pdcf CD = 00 is chosen and the D-frontier becomes {J} (gates are named by their output line). Then, gate J is considered and the pdc setting I = 1 is selected with result J = D and new D-frontier {M, N}. Assume gate M is selected. Then, the pdc setting H = 0 is selected with result M = D′. The justification of current values H = 0 and I = 1 results in conflict, so the algorithm backtracks and tries the next pdc for gate M which sets H = D. This cannot be justified, the algorithm backtracks once more and selects gate N from the D-frontier. The assignment E = 1 is made, which results in N = D. The values E = 1 and I = 1 can be justified without conflict. The algorithm terminates successfully and generates test pattern ABCDE = 11001.

Sometimes the algorithm must sensitize two paths simultaneously from the fault site to a PO to detect the fault. This is referred to as multipath sensitization. Consider the circuit in Figure 69.2 and the fault B s-a-l. The assignment B = 0 is made and the D-frontier becomes {F, G}. Assume that gate F is selected. The pdc A = 1 and G = 0 are selected to propagate fault D to line H. This results in conflict, as B (and E) are required to be 0. The algorithm backtracks and tries the next available pdc of gate H which sets G = D. This value is justified by setting C = 1. The resulting test pattern is ABC = 101.

Another basic TPG algorithm is called PODEM, and also uses the five-valued logic (0, 1, x, D, D) [6]. In PODEM, all lines are initialized to value x except line l, which is assigned a value of D if the fault is l s-a-O, and a value of D′ if the fault is l s-a-l. The algorithm at each step tries to satisfy an objective (v, l ), defined as a desired value v at a line l by making assignments only to primary inputs (PIs), one PI at a time. The mapping of an objective to a single PI value is done heuristically. The initial objective is (v ′, l ). All implications of the current pattern of values assigned to PIs are computed, and the algorithm terminates when the effect of the fault is propagated to a primary output (PO). If a conflict occurs and the fault cannot be activated or cannot be propagated to a PO, then the algorithm backtracks to the previous decision point, which is the last assignment to a PI. If no conflict occurs but the fault has not been activated or not been propagated to a PO because the currently implied values on the lines involved are x, then the algorithm continues with the same objective (v, l ) if the fault is still not activated, or with an objective (c ′, k) if the fault has been activated but not propagated, where k is an input line of a gate from the D-frontier that has currently assigned a value of x on it, and c the controlling value of that gate.

The determination of which single PI to be selected and which value to assign to it given an objective (v, l ) is done heuristically. A simple heuristic is to select a path from line l to a PI, and assign to that PI the value v (v ′) if the total number of inverting gates (such as NOT, NAND, and NOR) along that path is even (odd). Concerning the selection of a gate from the D-frontier, a simple heuristic is to select the gate that is closest to a PO. As an example of the application of PODEM, consider the circuit of Figure 69.1 and the fault G s-a-l. The initial objective is (0, G). The chosen PI assignment is C = 1 for which there are no implications. The objective remains the same, the PI assignment becomes D = 0, and this implies G = D. The D-frontier becomes {J}, and the next objective is (1, I). This eventually results in PI assignments A = 1 and B = 1 with implications F = l, H = 1, I = 1, M = 0, J = D, K = D, L = D, and new D-frontier {N}. The next objective is (1, E), which is immediately satisfied and has implication N = D. So, the algorithm returns successfully with test pattern ABCDE = 11001.

In the example of Figure 69.2, PODEM works as follows. The original objective is (0, B). With PI assignment B = 0, the D-frontier becomes {F, G}. Assuming gate F is selected, the next objective is (1, A), which is immediately satisfied with resulting implication F = D and new D-frontier {G, H}. Given that gate H is selected as closer to the output, the next objective is (0, G) which leads to the PI assignment C = 1 with implications G = D and H = D. The resulting test pattern is ABC = 101. The implied value for G was D while the objective generated was (1, G), but this is not considered a conflict since the goal of any objective is to assign a value to a PI that activates and propagates the fault to a PO. Figure 69.3 illustrates backtracking in PODEM. Consider fault J s-a-l. Starting with objective (0, J), the PI assignment A = 0 is made (using path HFEA) with no implication, and then the PI assignment B = 0 is made (using path HFEB) with implications E = 0, F = 0, G = 0, H = 0, I = 1, J = 1. The last assignment results to a conflict, and the algorithm backtracks trying PI assignment A = 1. The impli- cations of this assignment are E = 1, F = 1, G = 1. The fault at J is still not activated and objective

(1, B) is generated (using path HFEB), which is satisfied immediately but has no new implications. Then the objective (0, C) is generated (using path HCJ), which is satisfied immediately and has implication H = 0. Finally, the objective (1, D) is generated (using path ID), which is satisfied imme- diately and has implications I = 0 and J = 0. Since the fault is now activated and (trivially) propagated, the algorithm terminates successfully with test pattern ABCD = 1101.

Several extensions to PODEM have been proposed, such as working with more than one objective each time and stopping backtracking before reaching PIs. The FAN algorithm maintains a list of multiple objectives and stops backtracking at headlines rather than just PI lines [7]. A headline is a line that is driven by a subcircuit containing no line that is reachable from some fan-out stem, and, therefore, can be justified at the end with no conflicts. The fault in Figure 69.3 is activated when H and I are 0. The objectives (H, 0) and (I, 0) are now both taken into consideration. To achieve objective (H, 0), the assignment E = 0 can be selected because line E is a headline. But to achieve objective (I, 0), the assignment E = 1 is required. PODEM assigns C = 0 on PI C for objective (0, H), and then selects the assignment E = 1 on headline E and D = 1 on PI D for objective (0, I), which results in success. The justification of results to either ABCD = lx00 or ABCD = x100.

There are many ATPG algorithms based on various strategies (see, e.g., Ref. [5] for more information). It is noted that in the worst case, all ATPG algorithms may take exponential time. In fact, the test pattern generation problem has been shown to be NP-complete.

So far it was assumed that the CUT is combinational. Generating a pattern to detect a fault in sequential circuits is much more difficult than for combinational circuits. Testing of synchronous ASICs is typically reduced to combinational testing using the previously described methods, and the combinational core is tested using full-scan design [3], a Design for Testability (DFT ) technique that was described in the previous chapter. If full scan is not available, a sequence of patterns is generally required for each fault. ATPG techniques for combinational circuits can still be applied to sequential circuits by considering the iterative logic array model of the sequential circuits. This model applies to both synchronous and asynchronous sequential circuits, although it is more complex for the latter.

Given a current state vector Q and a current input vector X, the function of a sequential circuit is specified as a mapping from (X, Q) to (Q+, Z), where Q+ is the next state vector and Z the resulting output. In the iterative logic array representation, the sequential circuit is modeled as a series of combi- national circuits C0, C1,…, CN, where N is the length of the current input pattern sequence applied to the sequential circuit [2,3]. Each circuit Ci, referred to as a time frame, is an identical copy of the sequential circuit but with all feedback removed, and has inputs Xi and Qi , and outputs Q+ and Zi. Inputs Xi are driven by the ith pattern applied to the sequential circuit and inputs Qi are driven by the outputs Q i −1 , of the previous time frame for i > 0, with Q0 being set to the original initial state of the sequential circuit.

All outputs Zi are ignored except for the outputs ZN of the last time frame, which constitute the output of the sequential circuit resulting from the specific input sequence and initial state.

Given a stuck-at fault, the fundamental idea in sequential TPG is to create an iterative logic array of appropriate length N and justify all the values necessary for the fault to be activated and propagated to the outputs ZN of the last time frame. If this can be achieved with the values of the Q0 inputs of the first time frame being set to ‘x’s, then a self-initializing test sequence is produced. Otherwise, the specific values required for the Q0 inputs (preferably, all 0) are assumed to be easily established through a reset capability. In principle, one can start from one time frame Ci , (with the index i to be appropriately adjusted later) and try to propagate the effect of the fault to either some of the Zi lines or some of the Q+ lines. In case of propagation to the Z lines, C becomes tentatively the last frame in the iterative logic array and line justification by assignments to the Xi and Qi lines is repeatedly done in additional time frames Ci–1, Ci–2,…, Ci–m, up to some number m, until all lines are justified with either Qi–m, being set to all ‘x’s or to an initial state that can be reset. In case of propagation to the Qi lines, additional time frames Ci+1, Ci+2,…, Ci+k, for some number k, are considered until the effect of the fault, is propagated to the Zk lines. Notice that because each time frame contains the same fault, the propagation can be done from any of the Ci−1, Ci−2,…, Ci−m time frames to the Zk lines. Then, line justification is again attempted as above. In case of conflict during the justification process, backtracking is attempted to the last decision point, and this backtracking can reach as far as the Ci−m frame.

To reduce the storage required for the computation status as well as the time requirements of this process, algorithms that consider only backward justification and no forward fault propagation have been proposed. For example, the extended backtrace (EBT) algorithm selects a path from the fault site to a primary output which may involve several time frames and then tries to justify all values for the sensitization of this path (along with the requirements for the initial state) by working with time frames Ci−1, Ci−2,…, Ci−m [8]. It has also been shown by Muth [9] that four additional logic values are required besides the five values 0, 1, D, D′, and x, especially where state initialization may be affected by the fault. A differing signal may be 0 at the fault-free circuit and x in the faulty circuit. In the nine-valued algebra this is denoted by a new value 0/x whereas the five-valued algebra used in combinational ATPG cannot denote it as a differing signal and simply denotes it by x. Similarly, 1/x, x/1 and x/0 are defined. Using this nine-valued algebra test patterns may be detected for faults that cannot be detected using the five-valued algebra.

A fault for which no test pattern exists is referred to as redundant if the circuit is combinational and untestable if the circuit is sequential. If a sequential circuit is tested using full scan, then the set of redundant faults is only a subset of the untestable faults in the CUT.