Simulation and Generation of I_{ddq} Tests for Bridging and

Leakage Faults in Combinational Circuits ^{1}

( Draft, March 7, 1995)

Sreejit Chakravarty and Paul J. Thadikaran 226 Bell Hall Department of Computer Science State University of New York Buffalo, NY 14260.

Abstract

In the absence of information about the layout and for better defect coverage test generation and fault simulation systems must target all bridging faults. The usefulness of targeting a subset of such faults, viz. all two line bridging faults, is based on the fact that an I_{ddq} Test Set that detects all two line bridging faults also detects all multiple line, single cluster bridging faults.

A novel algorithm for simulating I_{ddq} Tests for all two-line bridging faults in combinational circuits is presented. The algorithm uses an implicit representation of the fault list thereby resulting in a time and space efficient algorithm.

We show that the problem of computing I_{ddq} Tests for a two line bridging fault as well as for a leakage fault, in some restricted classes of circuits, is intractable. Next, experimental results on using randomly generated I_{ddq} Test Sets for detecting bridging faults are presented. These results point to the computational feasibility of targeting all two line bridging faults in combinational circuits.

1 Introduction

Studies have shown that bridging and leakage faults, defined below, are highly probable

in static CMOS circuits[8]. As discussed below, these faults can be detected using Current Sensors. The tests used in conjunction with Current Sensors are known as I_{ddq} Tests.

1Research supported by NSF Grant Number MIP-9102509. Some of the results discussed here has been presented in [7]

Recent studies have also shown that single stuck-at test sets are inadequate to detect bridging and Leakage faults[20,21]. This motivates the study of the problem of simulating and generating I_{ddq} Tests, for the above two classes of faults.

1.1 Fault Model and Testing Strategy

For every FET there are four nodes: gate (G), drain(D), source(S) and bulk(B). Accordingly, there are six Leakage faults for every FET. GS is the gate to source leakage fault in which there is a permanent conducting path between the gate and source. Faults GD, GB, DS, DB and SB are similarly defined[17, 18].

A bridging fault ( BF ) occurs when two or more distinct lines are shorted. In general, assume that only the lines in the set S are involved in a BF where S = ⋃_{i=1}^{t} S_{i}, such that lines in S_{i} are shorted. Moreover, if a line belongs to S_{i} and another line belongs to S_{j} s.t. i ≠ j then these two lines are not shorted. We refer to the S_{i}’s as clusters of the fault. If a BF is such that it consists of only one cluster then it is a single bridging fault ( SBF ). Else, it is a multiple bridging fault. Also, if for all 1 ≤ i ≤ t, ∥S_{i}∥ ≤ K then the fault is a K-line BF. There are other BFs viz. those between the internal nodes of a gate[15, 21]. In this paper we do not consider such faults.

Current sensors monitor the power supply current ( I_{ddq} ). In a fault free static CMOS circuit I_{ddq} is small. However, if there is a BF or a Leakage fault in the circuit then, on application of certain input vectors, I_{ddq} is large. Thus, the presence of large I_{ddq} indicates the presence of a fault in the circuit. This test methodology is known as I_{ddq} Testing or quiescent current testing[16, 18, 19]. The corresponding tests are known as I_{ddq}Tests. Conditions that must be satisfied by input vectors to be I_{ddq} Tests are summarized in Section 2.

In the rest of the paper we assume that: the fault can be either a single two-line BF or a single Leakage fault; and that such faults are detected using I_{ddq} Tests and Current Sensors. The circuits are assumed to be combinational. However, the algorithms we present can also be used for sequential circuits which are such that either: (i) it has a full scan structure embedded in it[1]; or (ii) the system registers can be configured as ALFSRs to be used as a test generator[1]. In these cases we restrict the fault list to single two-line bridging faults between lines in the same combinational component of the circuit. Henceforth, we use the abbreviation TSBF to refer to two-line bridging faults.

1.2 Motivation for the Fault Model

The number of SBFs equal 2^{m} − 2, where m is the number of lines in the circuit. Simulating such a large number of faults presents a problem. In Section 3 we show that if an I_{ddq} Test Set covers all TSBFs then it also covers all SBFs. In [18] a similar result was claimed. However, as we will see in Section 2, we impose a much stronger condition for an input vector to be an I_{ddq} Test for a TSBF than was used in [18]. Consequently, we have to show that the result is also valid under the stricter conditions we impose on the I_{ddq} tests.

The above result is significant in that it shows that targeting TSBFs rather than SBFs is a useful alternative because it reduces the number of faults that we consider to O(m^{2}). This is the motivation behind our fault model.

Even if we restrict ourselves to TSBFs the size of the fault list, shown as Total in Table 1, is still very large. Because of the large number of such faults existing study of test generation and fault simulation of bridging faults[5, 20, 21] has attempted to reduce the set of bridging faults to be considered. Such a reduction process requires detailed analysis of the circuit layout. There are two shortcomings of this approach.

1. The layout information is often not available. Even if it is available, for larger circuits the fault list extraction process has to manipulate larger and larger layouts which is itself going to be time consuming. In fact, as we will see later, the performance of systems like Carafe[20] points to this.

2. The fault list extraction process used in systems like Carafe[20] etc. assumes “point defects”. Although such “failure modes” may be dominant in certain fab lines they are by no means the only “failure modes”. Therefore, bridging faults extracted under the “point defect” assumption may not include other probable

bridging faults.

In order to avoid the above two shortcomings we assume all TSBFs. But this leaves us with the problem of having to consider a large number of faults. An important point of the work presented here is to show that test generation and fault simulation for TSBFs, in combinational circuits, is a computationally feasible alternative to the existing approach, especially if no information about the layout is available. This can be achieved by developing “good” test generation and fault simulation techniques. We present techniques that, we believe, is a step in that direction.

1.3 Fault Simulation

Simulating the large number of faults that we are targeting, using either fault dictionaries or by explicitly enumerating them, leads to a very time consuming algorithm. In order to cope with that we use a novel technique for simulating the TSBFs. As discussed later, our algorithm uses an implicit representation of the fault list. This representation leads to an efficient simulation algorithm.

The set of TSBFs are classified into two classes, NFTSBFs and FTSBFs, which are defined in Section 2. Our algorithm works in two phases. In the first phase it uses an extremely fast algorithm to simulate the NFTSBFs. In the second phase it simulates the FTSBFs. Table 1 shows the percentages of the two classes of faults in each of the benchmark circuits. From this it should be clear that an overwhelming percentage of the TSBFs are NFTSBFs. The main speedup of the algorithm is obtained in the first phase. In Section 4 we present the algorithm for NFTSBFs and in Section 5 we present the algorithm for FTSBFs. The experimental results are presented in Section 6.

1.4 Test Generation.

In Section 7 we address the problem of computing I_{ddq} Tests for TSBFs and Leakage faults. The theoretical results of Section 7.2 characterizes the complexity of computing I_{ddq} Tests for TSBFs and Leakage faults. We show that these problems are NP-Hard for: restricted classes of circuits consisting only of AND, OR gates; and for circuits consisting of only one “very restrictive” complex CMOS gate. Thus, like the Controllability and Observability Problems[10, 11], as well as the problem of computing tests for stuck-open faults[6], computing I_{ddq} Test is an intractable problem; and nonmonotonicity and the degree of fanout are not the only causes of the intractability of these problems.

The conventional method of testing circuits ( IO-Testing ) consists of exciting the primary inputs and monitoring the logic level at the primary output. Tests for IO-Testing has to be a solution of both the Controllability and Observability Problems. However, I_{ddq} Tests have to be a solution of the Controllability Problem only. This raises an interesting philosophical question: Is computing I_{ddq} Tests any easier than computing tests for IO-Testing ? Our theoretical results show that this is indeed the case!

When Current Sensors are used, processing each test vector takes a considerable amount of time. Therefore, I_{ddq} Testing will be feasible for production testing only if the targeted set of faults can be tested with a small test set. This motivates the need for a test generation strategy that will generate an I_{ddq} Test Set quickly, is of small size, and has high coverage of TSBFs and Leakage faults. As discussed below, there are reasons to believe that this can be achieved and works presented in [7, 18] points to this. ( Note that this does not contradict the results of Section 7.2. The results of Section 7.2 imply that computing I_{ddq} Test Sets with 100% fault coverage is difficult. However, it does not imply that computing test sets with very high, but not 100%, fault coverage is computationally intractable ).

I_{ddq} Testing provides good observability. Therefore, for every fault f the number of test vectors for f will be rather high. In [18] it was shown that 15 test vectors were enough to detect all the Leakage faults in an ALU. In [9] it was shown that a test set for IO-Testing of stuck-at faults can be reduced drastically to derive an I_{ddq} Test set for stuck-at faults. In [17] it was shown that a functional test set can be reduced drastically to derive an I_{ddq} Test Set for the Leakage faults in the circuit.

We investigated methods for Computing I_{ddq} Test Sets for TSBFs. Our approach differs from the approaches proposed in [9, 17] for computing I_{ddq} tests. The approaches proposed in [9, 17] are for stuck-at or Leakage faults and require that a test set for some other fault model be available. We experimented with more direct method. In [7] we presented experimental results on the use of some universal test sets for detecting TSBFs and Leakage Faults. Here ( Section 7.4 ) we present experimental results on the use of randomly generated I_{ddq} Test Sets for testing TSBFs. The size of such test sets are computed using incremental simulation, which is discussed in Section 7.3. We conclude that our method works for a fairly large class of circuits. We present a characterization that identifies a subclass of such circuits. This subclass includes all two-level circuits.

Test generation for bridging faults has been discussed in [2, 3, 5, 20, 21]. In [2, 3], unlike our work, the test strategy assumed was IO-Testing; and, unlike our work, only a small subset of TSBFs were considered. The main emphasis of the work presented in [2, 3] was to use the knowledge of stuck-at test generation to compute tests for bridging faults. In [5, 20, 21], like our work, I_{ddq} testing is assumed. However, unlike our work, only a small subset of the two line bridging faults is considered. In Section 7 a comparison of our experimental results with those in [5,20] are presented. From this comparison we hope to convince our readers that, computationally, it is feasible to target all two line brindging faults.

2 I_{ddq} Tests

In Figure 1, let: L1(L2) be the output of gate G_{1}(G_{2}); F be the fault s.t. L1, L2 are bridged; v(l) be the value at l on application of the input vector v to the good circuit; and v′(l) be the value at l on application of v to the faulty circuit. Let v be an input vector s. t. v(L1) = 1 and v(L2) = 0. In the good circuit, on application of v, there exists a conducting path p_{1} in G_{1} from V_{dd} to L1 and a conducting path p_{2} in G_{2} from L2 to Gnd. Depending on v, the two paths p_{1}, p_{2} may still be activated in the faulty circuit and there will be a conducting path from V_{dd} to Gnd. This will result in a large I_{ddq}, which can be detected by current sensors.

Let H be an SBF s.t. S = {f_{1}, …, f_{p}} is the set of lines of the circuit C that are shorted. Then H is a non-feedback single bridging fault ( NFSBF ) iff ∀f_{i}, f_{j} ∈ S there does not exist a path in C either from f_{i} to f_{j} or from f_{j} to f_{i}. If an SBF is not an NFSBF then it is a feedback single bridging fault ( FSBF ). Since we restrcit ourselvs to TSBFs rather we often use the abbrev. FTSBF ( NFTSBF ) instead of FSBF ( NFSBF ). In Figure 2, (21,31) is an FTSBF whereas (21,28) is an NFTSBF.

Let f_{1}, f_{2} be two lines and v an input vector s.t. v(f_{1}) ≠ v(f_{2}). If the TSBF is such that f_{1}, f_{2} are shorted then v′(f_{1}), v′(f_{2}) are ambiguous ( i.e. can be either 0 or 1 or be at an intermediate level depending on the relative strengths of the pullup and pulldown transistors involved).

Consider the NFTSBF (21,28) and the input vector v1 =< X11 = 1, X12 = 1, X8 = 0 >. This creates a conducting path p1 in the pulldown of 28 and a path p2 in the pullup of 21. Although the values at 21, 28 are ambiguous they do not affect the values at the inputs of 21, 28. Therefore, even in the faulty circuit, the paths p1, p2 are active. Therefore, v1 is a test for the TSBF (21, 28). In general, if (f_{1}, f_{2}) is an NFTSBF then v is a test for this TSBF iff v(f_{1}) ≠ v(f_{2}).

Next consider the FTSBF (21,31). Let v2 =< X9 = 0, X8 = 0, X11 = 0, X13 = 0 >. Then v2(21) = 1 ≠ v2(31) = 0. Therefore, in the fault free circuit v2 activates a path p1 in the pullup of 21 and a path p2 in the pulldown of 31. However, in the faulty circuit v2′(21), v2′(31) are ambiguous. This implies that v2′(22) is also ambiguous. Therefore, v2 may or may not activate a path in the pulldown of 31. Therefore, v2 may or may not detect the TSBF (21,31). Because of this uncertainty we reject v2 as a test of the TSBF (21, 31). On the other hand, if v3 =< X9 = 1, X10 = 1, X8 = 0, X11 = 0, X13 = 0 > then v3(21) = 1 ≠ v3(31) = 0, v3′(21) is ambiguous and, independent of the value of v3′(21), v3′(31) = 0. Therefore, v3 is a test for this FTSBF.

For FTSBF we use the following criteria to ascertain whether an input vector detects the fault or not. Assume that there exists a path from L_{1} to L_{2}. For any input vector v assign u ( don’t care ) to L1. Next use three valued simulation and breath-first traversal to determine if L2 can be assigned the value 0 or 1 or if it remains unknown. Let the value so assigned to L2 be denoted by V al(L2, v). Then v is a test for the FTSBF < L1, L2 > if and only if: (i) v(L1) ≠ v(L2); and (ii) V al(L2, v) ∈ {0, 1}. Because of the stricter conditions on tests for FTSBFs when compared with NFTSBFs it is more difficult to simulate FTSBFs when compared with NFTSBFs.

In [18] it was stated that v is an I_{ddq} Test for detecting any TSBF < L1, L2 > iff v(L1) ≠ v(L2). We are using a stricter condition for an input vector to be a test for FTSBFs than the condition used in [18]. According to [18] both v2, v3, defined above, are I_{ddq} Tests for (21, 31). But, according to our criteria v2 is not a test but v3 is a test for (21, 31).

The distinction between NFTSBFs and FTSBFs is based on a pessimistic assumption. This makes our simulation results a bit pessimistic since it rules out the detection of certain faults viz. those between the input and output of a NOT gate.

Next consider the Leakage Fault between the gate and drain of the nFET N2 of Figure 3. Consider the input vector T 1 that sets both A and B to 1. This sets node b to 0. If the fault under consideration exists then there will be a conducting path between V_{dd} and Gnd, on application of T 1, that passes through nodes b and B. Thus, T 1 is a test for our example Leakage Fault. Tests for other Leakage Faults can be similarly identified[17].

3 Coverage of SBFs by Tests for TSBFs

Let F be an SBF in the circuit C s.t. S = {f_{1}, …, f_{k}} are the set of lines that are shorted and g_{i} the gate with output f_{i}. The cluster graph of F is a directed graph G_{F} = (V, E) where: V = S; and ∀f_{i}, f_{j} ∈ V < f_{i}, f_{j} >∈ E iff there exists a path, in C, from f_{i} to f_{j}. G_{F} for the SBFs involving the following set of lines, of the circuit of Figure 2, are shown in Figure 4: {8, 9, 19, 21}, {18, 21, 28}, {6, 22, 31}.

If the fault F is such that there exists an edge in G_{F} from f_{i} to f_{j} then an ambiguous value at f_{i} could deactivate a path in gate g_{i} which would have been activated in the fault free circuit. A node a in a cluster graph is said to be lowest iff the indegree of a is 0. In Figure 4, nodes 6,19, 9 are example of lowest nodes.

Fact 1. If f_{i} is a lowest node of the cluster graph of an SBF F among lines in {f_{1}, …, f_{k}} then ambiguous values at f_{j}, j ≠ i cannot deactivate paths in gate g_{i}, corresponding to the lowest node, that are activated in the absence of the fault.

The definition of NFSBF implies that for any NFSBF F, all nodes of the cluster graph G_{F} are lowest. Fact 1 implies that for any i, j ambiguous values at the lines involved in the fault cannot deactivate any path in g_{i}, g_{j} that are activated in the fault free circuit. Therefore, any test for the NFTSBF between lines f_{i}, f_{j} will detect F. Thus, for the fault F of the example of Figure 4(b) any test for the NFTSBFs (18, 21), (21, 22), (18, 22) will also detect F.

FSBFs are divided into two classes: Type 1, Type 2. An FSBF F is a Type 1 FSBF iff its cluster graph contains exactly one lowest node. Figure 4(a) illustrates this case. An FSBF F is a Type 2 FSBF iff its cluster graph contains at least two lowest nodes. Figure 4(c) illustrates this case. Since we are considering acyclic combinational circuits any FSBF must be either Type 1 or Type 2.

Let F be a Type 2 FSBF and, without loss of generality, assume that f_{1}, f_{2} are two lowest nodes in its cluster graph. Fact 1 implies that for i = 1, 2 the ambiguous value at f_{j}, i ≠ j cannot deactivate any path in gate g_{i} that is activated in the fault free circuit. Therefore, any test for the NFTSBF (f_{1}, f_{2}) will also detect F.

Next, let F be a Type 1 FSBF s.t. f_{1} is the lowest node in G_{F}. Let F′ be another fault among the lines in S −{f_{1}}. In G_{F′}, because the circuit is acyclic, there exists at least one lowest node say f_{2}. Fact 1 implies that ambiguous values at f_{i}, i ≥ 3 cannot deactivate any path in gate g_{1} or gate g_{2} which is activated in the fault free circuit. Let T be a test for the FTSBF (f_{1}, f_{2}). Therefore, on application of T, and even in the presence of an ambiguous value at f_{1}, f_{3}, … f_{k} in the faulty circuit, appropriate paths are still activated in gates g_{1}, g_{2}. Therefore, T will also be a test for F. Thus, any test for the TSBF among lines 6, 22 is also a test for the FSBF of Figure 4(a). The above argument leads to the following result.

Theorem 3.1. Any I_{ddq} Test Set that detects all TSBFs detects all SBFs.

Note that a similar result was claimed in [18]. But, our result is stronger than the claim in [18] in that we have shown it to be valid under stricter conditions on the I_{ddq} Test Sets.

We observe that if m is the size of the circuit then the number of SBFs equals 2^{m} − m − 1 and the number of TSBFs equals \frac{m(m−1)}{2}. Thus, Theorem 3.1 states that, by targeting only a quadratic number of faults we can cover an exponential number of faults.

4 A Simulation Algorithm for NFTSBFs

Notations :

C is the given circuit. m is the size of C. N is the size of the given test set. T = {T_{1}, …, T_{N}} is the given test set. f is the number of fanout points. {F_{1}, …, F_{f}} is the set of fanout points. m_{i} is the number of lines in C reachable from F_{i}. m_{av} = \frac{1}{f} ∑_{i=1}^{f} m_{i} = average number of lines reachable from a fanout point. n is the number of primary inputs. T_{i}(q) is the value of line q of C on application of T_{i}.

Let q_{1}, q_{2} be any two lines in C. Line q_{1} is said to be equivalent to line q_{2} w.r.t. T iff ∀1 ≤ i ≤ N, T_{i}(q_{1}) = T_{i}(q_{2}). This is denoted by q_{1} ≡_{T} q_{2}. Note that ≡_{T} is an equivalence relation and therefore partitions the set of lines into equivalence classes.

Fact 2. A test set T does not detect the NFTSBF (q_{1}, q_{2}) of C iff they belong to the same equivalence class E of C w.r.t. T.

Fact 2 forms the basis of our algorithm for computing coverage of NFTSBFs. For example, let T = {T 1, T 2, T 3, T 4, T 5} be as defined in Table 2. The value at each line in the circuit of Figure 2, on application of these vectors, is tabulated in Table 3. The set of equivalence classes is as follows: {{1, 21, 22},{2}, {3},{4, 26}, {5},{6}, {7}, {8}, {9, 32, 33}, {10}, {11}, {12}, {13}, {14}, {15}, {16}, {17, 18, 23, 25}, {19, 24}, {20}, {27, 31, 34}, {28, 29, 30}, {35, 37, 38}, {36}}. From this we deduce that T does not detect the NFTSBF (4, 26) and detects the NFTSBF (16, 17).

Equivalence classes with only one entry can be eliminated because all NFTSBF between the line in that set and any other line is detected by T. Eliminating those sets we have L_{5} = {{1, 21, 22}, {4, 26}, {9, 32, 33}, {17, 18, 23, 25}, {19, 24} {27, 31, 34}, {28, 29, 30}, {35, 37, 38}}. Consider the equivalence class {1, 21, 22}. Out of the three bridging fault that it represents (21, 22) is an FTSBF. Therefore, this equivalence class corresponds to 2 undetectable NFTSBF. We compute this value for each of the equivalence classes and sum them up to get the total number of undetected NFTSBFs. For our example this is given by 2 + 1 + 1 + 0 + 1 + 1 + 1 + 0 = 7. The reader can verify that there are a total of 525 NFTSBFs in the circuit. Therefore, the test set of Table 2 detects 100 − \frac{7}{525} × 100 = 98.67% of all the NFTSBFs.

Algorithm SimNFTSBF

Step 1. Compute T ot = the total number of NFTSBFs in C. ( COUNT1, Section

4.1. ). Step 2. Compute the equivalence classes of C w.r.t. T. ( EquivClass, Section 4.2.

). Step 3. Using the equivalence classes computed in Step 2 compute UnDet, the num-

ber of undetected NFTSBFs. ( COUNT2, Section 4.3 ). From that compute Coverage = 1 − \frac{UnDet}{T ot}.

Steps 1 , 2 and 3 are discussed in more details in the next three subsections. An analysis of the algorithm is given in Section 4.4.

4.1 Counting Number of NFTSBFs

NumF B(q) is the number of nodes in C that are reachable from q. NumF B(q) can be used to count the number of faults as follows.

The total number of FTSBFs is ∑_{q∈C} NumF B(q) and the total number of NFTS-BFs is \frac{m(m−1)}{2} − ∑_{q∈C} NumF B(q). NumF B(q) for each line in the example of Figure 2 is shown in Table 4. From that we deduce the number of FTSBFs to be 178, the number of NFTSBFs to be 525, and the total number of TSBFs to be 703.

Using breadth-first traversal of C, starting from q, NumF B(q) can be computed. If this is done for every line in C then the complexity of the resulting algorithm will be O(m^{2}). We next present an algorithm that is an improvement on this algorithm.

Algorithm COUNT1

/* Counts the number of NFTSBFs. It is assumed that while reading in the circuit description a list of fanout points and a list of primary outputs has been created. */

Step 1. For each primary output q, NumF B(q) = 0. Step 2. For each fanout point q, initialize NumF B(q) to 0 and perform the following

computation. Starting from q and using breadth-first traversal of C, visit the lines of C. Each time a new node is visited NumF B(q) is incremented by 1.

Step 3. Starting with the primary outputs and traversing C breadth-first, towards the primary inputs, compute NumF B(q) for each gate and primary input q as follows. If q is a fanout point or a primary output then NumF B(q) has already been computed. Else, let p be the successor of q in C. Then, NumF B(q) = NumF B(p) + 1.

4.2 Computing the Equivalence Classes

The equivalence classes can be computed as follows. Compute, for each line in C, the value assigned to it by each of the input vectors of T. From that deduce the pattern of values assigned by T to each of the lines in C. Compute the equivalence classes by grouping lines with identical patterns in the same class. This algorithm has: space complexity O(mN); and time complexity O(m^{2}). Algorithm EquivClass, discussed next, is an algorithm for computing the equivalence classes, that is an improvement on this.

The basic idea used in Algorithm EquivClass is to start by assuming that all the lines form one equivalence class. After simulating an input vector, split some of the equivalence classes to form a new set of equivalence classes. Such an iterative algorithm has the advantage of being used as an “incremental simulator” as discussed in Section 7.

To understand the algorithm we need to understand the data structure (Figure 5) that it uses. NodeList is a list having an entry ( Node(i) ) for all i, where i is a gate or a primary input of the circuit. Each Node(i) contains a Value field, denoted by Value(i). EquivClassList is the list of equivalence classes and contains one entry ( EquivClass(P) ) for each equivalence class P computed by the algorithm. Each EquivClass(P) contains, among others, a pointer ( LineList(P) ) to a list that represents the lines in the equivalence class P. LineList(P) contains an entry Line(j) if and only if Line(j) is in the equivalence class P. Line(j) contains a pointer ( NodePtr(j) ) to Node(j).

Algorithm EquivClass

/* Given the test set T, this algorithm computes the equivalence classes of C w.r.t. T. It is assumed that the structure NodeList has been initialized to represent the

given circuit C. */ Step 1. Initialize EquivClassList to contain one entry representing the equivalence

class consisting of all lines in the circuit. For each line j in C, compute the value assigned to it by T_{1} and store it in V alue(j).

Step 2. Traverse EquivClassList. For each EquivClass P that is visited create two new equivalence classes P_{0}, P_{1} as described in Step 3. Delete and free the space used by P and insert P_{0}, P_{1}, if they are nonempty, into EquivClassList.

Step 3. Traverse LineList(P). For each Line(j) visited determine, using NodePtr(j), if Value(j) is 1 or 0. If Value(j) is 1(0) then delete Line(j) from LineList(P) and insert it into LineList(P_{1}) ( LineList(P_{0}) ).

Step 4. If all input vectors have been processed exit. Else, for each line j, compute the value assigned by the next input vector T_{i} to j and store it in Value(j). Go to Step 2.

We next present an example to illustrate this algorithm. The test set is defined in

Table 2 and the circuit is shown in Figure 2. Let L_{i} be the list of equivalence classes

after processing T_{i}. The L′_{i}s computed after each iteration through the algorithm is

shown below.

L_{1} = {1, 3, 4, 5, 7, 9, 10, 12, 14, 15, 20, 21, 22, 26, 32, 33, 35, 37, 38}

{2, 6, 8, 11, 13, 16, 17, 18, 19, 23, 24, 25, 27, 28, 29, 30, 31, 34, 36}

L_{2} = {4, 5, 9, 10, 15, 20, 26, 32, 33}, {1, 3, 7, 12, 14, 21, 22, 35, 37, 38}

{6, 8, 16, 17, 18, 23, 25, 28, 29, 30}, {2, 11, 13, 19, 24, 27, 31, 34, 36}

L_{3} = {4, 9, 20, 26, 32, 33}, {5, 10, 15}, {1, 12, 14, 21, 22, 35, 37, 38}

{3, 7}, {6, 17, 18, 23, 25}, {8, 16, 28, 29, 30}, {11, 13, 36}, {2, 19, 24, 27, 31, 34}

L_{4} = {4, 20, 26}, {9, 32, 33}, {10, 15}, {5}, {12, 35, 37, 38}

{1, 14, 21, 22}, {3, 7}, {6, 17, 18, 23, 25}, {8, 16}, {28, 29, 30}, {13},

{11, 36}, {27, 31, 34}, {2, 19, 24}

L_{5} = {4, 26}, {20}, {9, 32, 33}, {10}, {15}, {5}, {35, 37, 38}, {12}

{14}{1, 21, 22}, {3}, {7}, {6}, {17, 18, 23, 25}, {8}, {16},

{28, 29, 30}, {13}, {11}, {36}, {27, 31, 34}, {2}, {19, 24}

4.3 Counting the Number of Undetected NFTSBFs

Algorithm COUNT2, described below, counts the number of undetected NFTS-

BFs. The data structure used by this algorithm is depicted in Figure 6. In addition

to the pointers defined in Figure 5, we assume that Node(q), in NodeList, has a

pointer ( EquivClassPtr(q) ) that points to the equivalence class containing q. Each

Node(q) has a field NumFB(q). Each EquivClass(P) in EquivClassList has a field

FanNumFB(P) .

A circuit in which only the primary inputs fanout are known as Tree Circuits.

Let F be a fanout point or a primary output. Then MT S_{F} is the maximal tree

subcircuit with output F. In Figure 2, MT S_{31} = {31, 30}.

Algorithm COUNT2

/* It is assumed that Algorithm EquivClass has computed the equivalence classes of C w.r.t. T.*/

Step 1. Traverse EquivClassList. For each EquivClass(P) traverse LineList(P). For each Line(j), assign a value to EquivClassPtr(j), accessed using NodePtr(j), so that it points to EquivClass(P).

Step 2. For each line q in the circuit, where q belongs to the equivalence class P, compute, as follows, the number of lines of C in P that are reachable from q.

Step 2.1. For each fanout point F do Steps 2.2, 2.3.

Step 2.2. Traverse EquivClassList. For each EquivClass(P) set FanNumFB(P) to 0. Starting from F, traverse C breadth-first towards the primary outputs. Let q be the line being visited and P the equivalence class containing q ( determined using EquivClassPtr(q) ). Increment FanNumFB(P). This step terminates when all lines reachable from F has been visited. /* At the end of this step, for each equivalence class P, FanNumFB(P) is the number of lines reachable from F and in the equivalence class P. */

Step 2.3. For each line q in MT S_{F} perform the following computation. Let P be the equivalence class containing q. NumF B(q) = F anNumF B(P). Visit the lines of MT S_{F}. Let r be the line being visited. If Equiv-ClassPtr(r) points to P then increment NumFB(q).

Step 2.4. Traverse EquivClassList. For each EquivClass(P) set FanNumFB(P) to 0. For each primary output F do step 2.3.

Step 3. For each equivalence class P let Size(P) be the cardinality of P and Total(P) the number of undetected NFTSBFs between lines in P. Then,

T otal(P) = Size(P)(Size(P) − 1)/2 − ∑_{q∈P} NumF B(q).

Let L_{N} be the set of equivalence classes. Then, the number of undetected NFTSBFs equals ∑_{P ∈L_{N}} T otal(P). This can be readily computed by traversing EquivClassList.

Continuing with our example, consider L_{5} computed in Section 4.2. FanNumFB(P), for each equivalence class P, after each iteration of Step 2.2 is shown in Table 5. Note that only one row of Table 5 need be stored at any one time. NumFB(q), for all lines in one of the equivalence classes of Table 5, is shown in Table 6. From this we compute the last column of Table 5 as stated in Step 3 of the algorithm. The total number of undetected NFTSBFs equals 7, as was computed earlier.

4.4 Analysis of the Algorithm

Consider Algorithm COUNT1. The time complexity of Step 2 is O(fm_{av}) and the time complexity of Step 3 is O(m). From this the following lemma follows.

Lemma 4.1. The time complexity of COUNT1 is O(max(fm_{av}, m)) and its space complexity is O(m).

Next consider Algorithm EquivClass. Step 1 takes time O(m). Every pass through Steps 2, 3 and 4 takes time O(m). Steps 2, 3 and 4 are executed N times. The space complexity required to store the EquivClassList is O(m). This implies the following lemma.

Lemma 4.2. The time complexity of Algorithm EquivClass is O(mN) and its space complexity is O(m).

Next, consider Algorithm COUNT2. Step 1 takes time O(m). If F_{i} is the fanout point then Step 2.2 takes time O(m_{i}). Let M_{i} be the size of MT S_{F_{i}}. Then, Steps 2.3 takes time O(M_{i}^{2}). For each primary output Y_{j}, 1 ≤ j ≤ t, let Q_{j} be the size of MT S_{Y_{j}}. Then, for the output Y_{j}, Step 2.3 takes time O(Q_{j}^{2}). Therefore, Step 2 takes time

∑_{i=1}^{f}(O(m_{i}) + O(M_{i}^{2})) + ∑_{j=1}^{t} O(Q_{j}^{2}) = ∑_{i=1}^{f} O(m_{i}) + (∑_{i=1}^{f} O(M_{i}^{2}) + ∑_{j=1}^{t} O(Q_{j}^{2})
= O(max(fm_{av}, M_{av}^{2}), where
M_{av}^{2} = M_{1}^{2} + … + M_{f}^{2} + Q_{1}^{2} + … + Q_{t}^{2}

Step 3 takes time O(m). This leads to Lemma 4.3. Theorem 4.4 follows from Lemmas 4.1, 4.2 and 4.3 and the description of Algorithm SimNFTSBF.

Lemma 4.3. The time complexity of Algorithm COUNT2 is O(max(m, fm_{av}, M_{av}^{2})) and its space complexity is O(m).

Theorem 4.4. The time complexity of Algorithm SimNFTSBF is O(max(mN, fm_{av}, M_{av}^{2})).

Note that for any circuit this is a considerable improvement over an O(Nm^{2}) algorithm that we had alluded to earlier. Experimental evaluation of this algorithm will be presented in Section 6.

5 A Simulation Algorithm for FTSBFs

For every line q in C define Region(q) to be the subcircuit of C consisting of all lines p in C s.t. ∃ a line r in C and r is reachable from both p and q. In Figure 2, Region(29) = {X5, X6, X7, X8 X9, X10, X11, X12, X13, X14, X15 19, 20, 21, 22, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38}. Recall the definition of Node(p), Value(p) and NodeList from Section 3.

Algorithm SimFTSBF

Step 1. UnDetect = 0; For each line q ∈ C do Steps 2, 3, 4 and 5. Step 2. Compute Region(q). Step 3. Initialize L to be the set of lines reachable from q.

Step 4. For each T_{i} in T delete elements from L as described below. If L is empty or T has been exhausted go to Step 5.

Step 4.1. Starting from the primary inputs visit Region(q), breadth-first. Let p be the node being visited. If p is a primary input Value(p) = T_{i}(p). Else, compute Value(p) as follows. If p is an AND( OR, NAND, NOR ) gate and one of its inputs is 0 ( 1,0,1) then Value(p) = 0(1,1,0); Else, if p is an AND( OR, NAND, NOR ) gate and all its inputs are 1( 0,1,0 ) then Value(p) = 1(0,0,1); Else, Value(p) = u. If ( p equals q ) then VALUE = Value(p). After that set Value(p) to u. /* Note that VALUE ∈ {0, 1}. */

Stem 4.2. Visit lines in L. Let p be the line being visited. If V alue(p) = \overline{V ALUE} then delete p from L.

Step 5. UnDetect = UnDetecet + ∥L∥.

Algorithm SimFTSBF is illustrated with the help of an example. Table 7 shows,

for each line q of Region(29), the value assigned to q for each of the input vectors of

Table 2. Let L_{0} denote the value of L after Step 3 and L_{i} denote the value of L after

Step 4 has processed T_{i}. The value of L_{0}, …, L_{5} is shown below.

L_{0} = {30, 31, 32, 33, 34, 35, 37, 38}
L_{1} = {30, 31, 34, 35, 37, 38}
L_{2} = L_{3} = L_{4} = L_{5} = {30, 37}

Therefore, the test set does not detect, among others, the two FTSBFs (29, 30) and

(29, 37) which involves line 29. Let q be the line being processed and Z_{q} the size of

Region(q). Steps 2, 3 take time O(Z_{q}) and Steps 4.1, 4.2 takes time O(Z_{q}N). From

this we have the following theorem.

Theorem 5.1. The time complexity of Algorithm SimFTSBF is O(∑_{q∈C} Z_{q}) = O(NmZ_{av}),

where Z_{av} = \frac{1}{m} ∑_{q∈C} Z_{q} and its space complexity is O(m).

6 Experimental Results.

For each ISCAS circuit a number of test sets ( given by N.S. in Table 8 ) were used.

Note that the smallest test set that will cover all TSBFs must have M = Log(m) vectors, where m is the number of nodes in the circuit. The test set {T_{1}, …, T_{M}} is generated using a random number generator and simulation is done to compute the coverage of NFTSBFs. The same test set is used to compute the coverage of FTSBFs. Table 8 tabulates the time taken to perform the simulation. Ave. is the average time taken and S.D. is the standard deviation. Table 9 tabulates the coverage results.

Several points are worth noting. A small number of I_{ddq} tests do cover a very large percentage of TSBFs. All TSBFs can be simulated using such a test set in a small amount of time. The amount of time taken to simulate the NFTSBFs is a tiny fraction of the total simulation time even though the percentage of NFTSBFs is very large. Note that the Standard Deviation in all cases is very small making the average a good predictor of the actual running time and coverage.

The second phase of the algorithm that simulates the FTSBFs requires logic simulation. We used a very crude logic simulator to implement this phase. A better logic simulator will reduce the simulation time considerably.

7 Test Generation

First, complexity results that characterizes the complexity of computing tests for bridging and leakage faults and the relative hardness of some of these problems are presented. Next, an approach to generate I_{ddq} Tests for TSBFs is presented. Our test generation strategy uses “incremental simulation” which is discussed in Section 7.3.

7.1 Definitions

Monotone Circuits. Circuits consisting only of AND, OR gates. Fanout Free Circuits. Circuits not containing any fanout points. Two Bounded Circuits. Circuits in which all its fanout points have no more than

two fanout branches. C(v) denotes the value of the output of a Boolean circuit C on application of the

input vector v. C_{1} covers C_{2} if and only if for all input vectors v, C_{2}(v) = 1 implies C_{1}(v) = 1. IOSA. Given a stuck-at fault f, in a circuit C, compute a test t for f s.t. t can be

used to detect f when IO-Testing is used.

I_{ddq}-SA. Given a stuck-at fault f in a circuit C, compute an I_{ddq} Test t for f. BC-COVER. Given two Boolean circuits C_{1}, C_{2} over the same set of variables de-

termine if C_{1} covers C_{2}. NOT-BC-COVER. Given two Boolean circuits C_{1}, C_{2} determine if C_{1} does not

cover C_{2}. LEAK. Given a CMOS circuit C and a Leakage fault f in C compute an I_{ddq} Test

for f.

CMOS circuits may consist of complex CMOS gates where the complex gates can implement arbitrary Boolean functions. A static CMOS gate G can be represented by two labeled graphs P_{G}, N_{G} with one source and one sink node. The labeled graph P_{G}, N_{G} of the gate G of Figure¡ 7(a) is shown in Figure 7(b), (c). The correspondence between the pullup ( pulldown ) network of G and P_{G}(N_{G}) is straight forward.

An input literal a occurs in a labeled graph G if and only if there exists an edge in G labeled by a. An input literal a occurs in a path p if there exists an edge in p labeled by a. A labeled graph G is said to be unate if and only if for every input variable X_{i} either only X_{i} occurs in G or only \overline{X_{i}} occurs in G. An input variable X_{i} is said to occur k times along a path p if there are k edges in p labeled by either X_{i} or \overline{X_{i}}. A labeled graph G is said to be repetition free if for every input variable X_{i} there does not exist any path p in G such that X_{i} occurs more than once in p. A labeled graph G is said to be k-bounded if and only if for every input variable X_{i} there exist at most k edges that are labeled by X_{i} or \overline{X_{i}}. A labeled graph G is said to be simple if and only if G is unate, repetition free and 2-bounded. A complex CMOS gate G is said to be a simple gate if and only if either P_{G} or N_{G} is a simple labeled graph.

7.2 Complexity Results

We assume that the reader is familiar with the terms NP-Hard etc. as defined in [12]. The model of comparison for comparing two NP-Hard problems that we use is as follows. The problems that we are interested in are defined over the set of all Boolean circuits. Let A, B be two such problems; U be the set of all Boolean circuits; and S_{A} ( S_{B} ) be the set of Boolean circuits for which A(B) can be solved in polynomial time. Then, we say that A is easier than B ( or B is harder than A ) if and only if S_{A} ⊄ S_{B} and S_{B} ⊂ S_{A}. In other words, whenever B can be solved in polynomial time then A can also be solved in polynomial time but not vice-versa.

Lemma 7.2.1. If C is a monotone circuit I_{ddq}-SA can be solved in polynomial time.

Proof. Let f be a s-a-0 ( s-a-1) fault. Then the all 0 ( all 1 ) input vector detects f. □

Theorem 7.2.2. I_{ddq}-SA is easier than IOSA.

Proof. Note that any solution to IOSA is also a solution to I_{ddq}-SA. Therefore, S_{IOSA} ⊂ S_{I_{ddq}−SA}. IOSA for monotone circuits is NP-Hard[11]. Therefore, S_{IOSA} ⊄ S_{I_{ddq}−SA}. From this and our proposed model of comparison it follows that I_{ddq}-SA is easier than IOSA. □

Lemma 7.2.3. NOT-BC-COVER for fanout free monotone circuits is NP-Hard.

Proof. In [14] it is shown that BC-COVER for fanout free monotone circuits is CoNP-Hard from which this lemma follows. □

Theorem 7.2.4. LEAK for two bounded monotone circuits is NP-Hard.

Proof. The problem is clearly in NP. We next show that NOT-BC-COVER for fanout free monotone circuits is embedded in LEAK. Let C_{1}, C_{2} be two fanout free monotone circuits. Construct the two bounded Boolean circuit C shown in Figure 8(a). We assume that a CMOS AND gate G is constructed as shown in Figure 8(b). In order to test for the leakage fault between nodes a and b of N1 we need to set A to 0 and B to 1. Clearly, C_{1} does not cover C_{2} if and only if there exists an input vector v s.t. C_{1}(v) = 0 and C_{2}(v) = 1. Also, the leakage fault between nodes a and b is detectable if and only if there exists an input vector v s.t. v sets A to 0 and B to 1. Therefore, the leakage fault between nodes a, b of gate G is detectable if and only if C_{1} does not cover C_{2}. □

Theorem 7.2.5. LEAK is harder than I_{ddq}-SA.

Proof. Consider any complete test set T for all leakage faults in a circuit C. For every line l in C there exists input vectors t_{0}, t_{1} in T s.t. t_{0}, t_{1} sets l to 0,1 respectively. Therefore, T is a complete I_{ddq} test set for stuck-at faults. Therefore, S_{LEAK} ⊂ S_{I_{ddq}−SA}. From Lemma 7.2.1 and Theorem 7.2.4 we know that S_{I_{ddq}−SA} ⊄ S_{LEAK}. From this and our model of comparison the result follows. □

Lemma 7.2.6. Given a fanout free monotone circuit C_{1}, representing the Boolean function f, labeled graphs P_{1}, N_{1} can be computed in polynomial time such that: P_{1}, N_{1} are repetition free; every edge in P_{1} is labeled by the complement of an input variable; every edge in N_{1} is labeled by an input variable; and P_{1}(N_{1}) represents the Boolean function f(\overline{f})[6].

Theorem 7.2.7. LEAK for simple CMOS gates is NP-Hard.

Proof. The problem is clearly in NP. We show that NOT-BC-COVER is embedded in this problem. Let C_{1}, C_{2} be two monotone, fanout free circuits representing the Boolean functions f_{1}, f_{2}. Construct the repetition free labeled graphs P_{1}, N_{1}, P_{2}, N_{2} representing respectively the Boolean functions f_{1}, \overline{f_{1}}, f_{2}, \overline{f_{2}} ( Lemma 7.2.6 ). Let X be an input variable that is distinct from the input variables of C_{1}, C_{2}. Construct the two labeled graphs N_{G}, P_{G} shown in Figure 8. From these two graphs a gate G can be constructed in an obvious way. Note that the node in G corresponding to n_{4} is V_{dd}, n_{1} is the output and n_{3} is the ground. From Lemma 7.2.6 we know that N_{G}, P_{G} can be computed in polynomial time and G is a simple gate. If f_{2} = 0 ( f_{1} = 0 ) then there exists a path from node n_{2}(n_{1}) to Gnd. Any test for the leakage fault between nodes n_{1}, n_{2} must set X to 0. If X = 0 and the input v is such that: (i) f_{2}(v) = 0, f_{1}(v) = 0 then n_{1} = n_{2} = 0 and the input vector cannot test the leakage fault between nodes n_{1}, n_{2}; (ii) f_{2}(v) = 0, f_{1}(v) = 1 then n_{1} = 1 and n_{2} = 0 then the input vector is a test vector for the leakage fault between nodes n_{1}, n_{2}; and (iii) f_{2}(v) = 1, f_{1}(v) = 1 or 0 then v cannot be a test vector for the leakage fault between nodes n_{1}, n_{2}. Therefore, there exists a leakage fault between nodes n_{1}, n_{2} if and only if C_{1} does not cover C_{2}. □

Theorem 7.2.8. Computing tests for bridging faults in two bounded, monotone circuits is NP-Hard.

Proof. Once again we show that NOT-BC-COVER for fanout free monotone circuits is embedded in the problem of computing a test for bridging faults. Let C_{1}, C_{2} be the two fanout free monotone circuits. Construct the circuit C shown in Figure 3(a) and consider the bridging fault that shorts lines L_{1}, L_{2}. According to the conditions stated above any input vector that detects this fault must, in the fault free circuit, set A to 1 and L_{1} to 0. Therefore, the bridging fault L_{1}, L_{2} is testable if and only if C_{1} does not cover C_{2}. □

To summarize, we see that non-monotonicity and degree of fanout are not the only causes of the difficulty of computing I_{ddq} tests for bridging and leakage faults. Moreover, because the covering problem for Boolean circuits is embedded in these problems it makes these problems harder than computing I_{ddq} tests for stuck-at faults. We leave open the question of whether or not it is more difficult to compute I_{ddq} tests for bridging faults than to compute I_{ddq} tests for leakage faults. Similar results can be deduced for other test structures like Crosscheck[13].

7.3 Incremental Simulation

By incremental simulation we mean the following. Assume that we have computed the NFTSBF coverage of the test set {T_{1}, …, T_{k}}. We want to compute the the NFTSBF coverage of the test set {T_{1}, …, T_{k}, T_{k+1}}, without going through the entire computation. This is not difficult if we use fault dictionaries. But using fault dictionaries for bridging faults is problematic because of the large space that would be required to store the fault dictionary. However, Algorithm SimNFTSBF can be modified to perform “incremental simulation” of NFTSBFs. The modifications consists of rearranging some of the steps of the computation. Step 1. Compute T ot = the total number of NFTSBFs in C, the given circuit, using

COUNT1. For each input vector T_{j}, until termination condition is reached, do Steps 2, 3.

Step 2. Let E = {E_{1}, …, E_{q}} be the set of equivalence classes of C w.r.t. {T_{1}, …, T_{j−1}}. Compute the value assigned to every line by T_{j}. From the values computed and E compute the equivalence classes of C w.r.t. {T_{1}, …, T_{j}} using Steps 2, 3 of Algorithm EquivClass.

Step 3. Compute UnDetect, the number of undetected faults using COUNT 2. The NFTSBF coverage of \{T_{1}, …, T_{j}\} is 1 − \frac{UnDetect}{T ot}.

7.4 An I_{ddq} Test Generation Strategy

The test generation strategy consists of two phases. In the Phase I, M = ⌈Log(m)⌉ vectors are randomly generated and the coverage of NFTSBFs is computed. The coverage of TSBFs by this initial test set of size M may not be adequate. Therefore, in Phase II, this initial test set is augmented. This is done by generating tests T_{M+1}, T_{M+2}, … using random number generators. For each T_{j} so generated we compute the coverage of NFTSBFs, using incremental simulation discussed above, by the test set {T_{1}, …, T_{M}, T_{M+1}, …, T_{j}}. The process is terminated when the coverage of NFTSBFs exceeds 99.5%. Any other suitable threshold could have been chosen. The procedure is also terminated if the number of consecutive test vectors for which the coverage does not increase exceeds N. In our experiments we used N = 5.

We evaluated this strategy using the ISCAS benchmark circuits[4]. Results obtained from this experiment are tabulated in Table 10. For each circuit a number of random test sets were generated. The number of such test sets is given by the row labeled N.S. The average ( Ave. ) and standard deviation ( S.D. ) of the Coverage, Test Length and the time required for two tasks are shown. The two tasks are: generating the test set, using simulation of NFTSBF only; and evaluating the coverage of both FTSBF and NFTSBFs. The fact that it takes considerably more time to simulate FTSBFs explains the difference in the time for the two tasks. We note the following.

1. The test generation strategy works very well for most of the circuits so far as fault coverage is concerned. Note that for circuits for which the coverage is low the percentage of FTSBFs is rather high ( See Table 1 ). This therefore corroborates our intuition that the method will work well for circuits with very high percentage of NFTSBFs. Note that circuits with small depth, viz. two level circuits, will have an overwhelmingly high percentage of NFTSBFs. This method will therefore work well for such circuits. The important point is that it also works well for some circuits for which a large percentage of the TSBFs are FTSBFs. C432 is an example of such a circuit.

2. For some circuits, like C1908, for which a large percentage of the TSBFs are FTSBFs this approach resulted in an I_{ddq} Test Set with a large coverage but the test generation time ( as well as the test length ) was considerably higher. One possible reason for this is the following. Because of the depth of the circuit and the small number of primary inputs the detection probability of many of these faults is rather low. Consequently, the method converges very slowly for this type of circuits.

3. The actual coverage will be higher than that computed by our algorithm. This is because the set of undetectable faults is counted in the set of faults not covered by the test set. For circuits containing a large number of NOT gates this set will be large. This partially explains the reduced coverage figures for some of the circuits.

We next compare our experimental results will results from the literature [5,20]. This comparison is shown in Table 11. We cannot compare the experimental results from [21] because of lack of information. In Table 11, BD are the results from [5], FL are the results from [20] and CT is a summary of our results.

In Table 11, all Times are in CPU Secs. Time for BD is the product of the total number of faults and the time per fault. The time for preprocessing is not included, as it was not reported in [5]. It also does not include the fault extraction process. This should be included because that processing time will dominate for larger circuits and biases the comparison towards BD. For FL, Time includes the time to extract the fault list from the layout and the total test generation time. For CT, Time is the sum of the test generation and fault simulation time. Faults, in all three cases, is the total number of faults processed by the respective systems. Pats is the size of the test set generated. Rem is the total number of TSBFs not covered by CT.

It should be obvious to the reader that CT is vastly superior to BD in terms of the running time. For example, for C7552 CT processes 350 times more faults in less than \frac{1}{14.5} the time required by BD. One should note that a Sparcstation 2 is considerably faster than a VAX Station 3200. But, the difference in the performance of the two systems cannot be explained by the speed differential between the two machines.

The difference between CT and FL is not as well defined. For the smaller circuits, C432 - C1908, FL takes considerably less time and generates smaller test sets. However, the difference in the total time is not as large as the difference in the size of the fault list they process. For example, for C1908 CT process 90 times more faults using about 13 times more CPU Secs and generates a test set that is about 7 times as large. For the large circuits however the difference is less obvious. For example for C7552, CT processes 130 times more faults is about \frac{1}{2.6} times the time used by FT. CT also generate a smaller test set than FL.

Another important point that we would like the reader to note is the following. The last row of Table 11 shows the number of TSBFs left uncovered by CT. For some circuits, the numbers are roughly same as the number of faults processed by BD or FL. One could therefore use CT in the initial phase and follow this up by generating tests by the test generation phase of systems like BD and FL. We can make a “rough estimate” of the time such a system ( using FL ) would take to generate the tests. This is shown under CT+FL in Table 11. FlTime is the time required by FL for generating the tests after extracting it; AddlT ime = F lT ime × \frac{Rem}{F aults(F L)} and T otalT ime = T Ime(CT) + AddlT ime. An inspection of this time points to the computational feasibility of targeting the TSBFs. We leave a more rigorous experimentation to the interested reader.

The important point is not whether CT runs a couple of secs faster or slower than FL or BD. We wanted to establish the computational feasibility of using TSBFs as a fault model for I_{ddq} Test Generation. Our results clearly show that computationally it is not much more expensive to generate tests for all TSBFs when compared with the process of extracting the fault list from the layout and then computing the tests. The test set computed by the former method will have better defect coverage. Also, the layout information may not be available in which case we are constrained to target all TSBFs.

Conclusion

In the absence of information about the layout and for better defect coverage one is

left with no choice but to targets SBFs. The usefuleness of targeting a small subset

of such faults was established by showing that an I_{ddq} Test Set that covers all TSBFs

also covers all SBFs. The inherent complexity of computing tests for a TSBF and

a Leakage fault as well as a novel simulation algorithm for TSBFs was presented.

Next, we demonstrated the feasibility of using TSBFs as a fault model by presenting

simulation results from randomly generated test sets. These results when compared

with experimental results from [5, 20] showed that for some circuits this method could

be used for computing test sets. For others, it can be used as a preprocessor to a

deterministic test generation system like those presented in [5, 20].

Reference

1. M. Abramovici, et. al., Testing and Testable Design of Digital Systems. Computer Science Press.

2. M. Abramovici and P. R. Menon, “A Practical Approach to fault Simulation and Test Generation for Bridging Faults”, IEEE Trans. on Computers, Vol. C-34, No. 7, pp. 658-663, July 1985.

3. M. Abramovici and P. R. Menon, “A Practical Approach to Fault Simulation and Test Generation for Bridging Faults,” IEEE Trans. on Computers, Vol. C-34, No. 7, pp. 658-663, July 1985.

4. F. Brglez and H. Fujiwara, “A Neural Netlist of 10 Combinational Benchmark Circuits and a Target Translator in Fortran”, special session on ATPG and Fault simulation, IEEE Int’l. Symposium on Circuits and Systems, 1985.

5. S. Bollinger and F. Midkiff, “On Test Generation for I_{ddq} Testing of Bridging Faults in CMOS Circuits”, IEEE International Test Conference, pp. 598-607.

6. S. Chakravarty, “On the Complexity of Computing Tests for Stuck-Open Faults in Complex CMOS Gates”, IEEE Trans. on Comput.-Aided Design, Vol. 8, No. 9, pp. 973 - 980, Sept. 1989.

7. S. Chakravarty, “Testing with internal probes and current monitors: Complexity results and universal test sets”. IEEE VLSI DESIGN, pp. 49-54, 1992.

8. F. J. Ferguson and J. P. Shen, “A CMOS Fault Extractor for Inductive Fault Analysis”, IEEE Trans. on Comput.-Aided Design, Vol. 7, No. 11, pp. 1181 - 1194, 1988.

9. R. Fritzemeier, J. Soden, R. Treece and C. Hawkins, “Increased CMOS IC Stuck-At Fault Coverage with Reduced IDDQ Test Sets”, In Proc. 1990 International Test Conference, pp. 427-435.

10. H. Fujiwara, “Computational Complexity of Controllability/ Observability problems for combinational circuits”, IEEE Trans. on Comput., Vol. 39, No. 6, pp. 762 - 767.

11. H. Fujiwara and S. Toida, “The Complexity of fault detection problems for combinational logic circuits”, IEEE Trans. on Comput., Vol. C-31, pp. 555-560, June 1982.

12. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.

13. T. Gheewala, “CrossCheck: A Cell Based VLSI Testability Solution”, IEEE/ACM Design Automation Conference, 1989, pp. 706 - 709.

14. H. B. Hunt III, R. E. Stearns, “Monotone Boolean formula, distributive lattices, algebraic structures and computational structures”, in Proc. Third Annual Symposium on Theoretical Aspects of Computer Science, Vol. 210, pp. 277-291. Springer-Verlag, Berlin, 1986.

15. K. J. Lee and M. A. Breuer, “On detecting single and multiple bridging faults in CMOS circuits using the current supply monitoring method”, in Proc. 1990 Int’l. Symposium on Circuits and Systems, pp. 5-8.

16. Y. Malaiya and S. Su, “A New Fault Model and a Testing Technique for CMOS devices”, 1982 Int’l. Test Conf., pp. 25-34.

17. W. Mao, R. K. Gulati, D. K. Goel, M. D. Ciletti, “QUIETEST: A Quiescent Current Testing Methodology for Detecting Leakage Faults”, In proc. 1990 International Conference on Computer Aided Design, pp. 280 - 283.

18. P. Nigh and W. Maly, “Test Generation for Current Testing”, IEEE Design and Test of Computers, Feb. 1990, pp. 26 - 38.

19. J. Soden and C. Hawkins, “Test Considerations for Gate Oxide Shorts in CMOS ICs”, IEEE Design & Test of Comput., Aug. 1986, pp. 56-64.

20. F. J. Ferguson and T. Larabee, “Test Pattern Generation for Realistic Bridging Faults in CMOS ICs”, IEEE 1991 International Test Conference, pp. 492 - 499.

21. T. M. Storey and W. Maly, “CMOS Bridging Fault Detection”, IEEE 1991 International Test Conference, pp. 1123 - 1132.

Table 1

Total % NFTSBF % FTSBF
c432 19110  47.79  52.21
c499 29403  56.73  43.27
c880 97903  83.65  16.35
c1355 171991  52.42  47.58
c1908 416328  73.84  21.16
c2670 1127251  95.53  4.67
c3540 1476621  84.05  15.95
c5315 3086370  96.47  3.53
c6288 2995128  70.28  29.72
c7552 6913621  96.80  3.20

Table 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
T 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0
T 2 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0
T 3 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1
T 4 1 1 1 0 1 0 1 0 1 0 1 0 0 1 0
T 5 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0

Table 3

16 17 18 19 20 21 22 23 24 25 26 27
T 1 1 1 1 1 0 0 0 1 1 1 0 1
T 2 0 0 0 1 0 1 1 0 1 0 0 1
T 3 1 0 0 1 0 0 0 0 1 0 0 1
T 4 0 0 0 1 0 1 1 0 1 0 0 0
T 5 1 1 1 1 1 1 1 1 1 1 0 0
28 29 30 31 32 33 34 35 36 37 38
T 1 1 1 1 1 0 0 1 0 1 0 0
T 2 0 0 0 1 0 0 1 1 1 1 1
T 3 1 1 1 1 0 0 1 0 0 0 0
T 4 1 1 1 0 1 1 0 0 1 0 0
T 5 1 1 1 0 1 1 0 0 1 0 0

Table 4

q 1 2 3 4 5 6 7 8 9 10 11 12 13
NumF B(q) 4 5 4 4 7 9 9 8 8 8 10 10 9
q 14 15 16 17 18 19 20 21 22 23 24 25 26
NumF B(q) 9 2 3 3 2 8 7 7 6 1 2 0 0
q 27 28 29 30 31 32 33 34 35 36 37 38
NumF B(q) 3 9 8 4 3 1 1 0 2 1 1 0

Table 5

P  F anNumF B
X2 X4 X5 14 22 24 27 28 29 31 32 T otal(P)
{4, 26} 0 0 1 0 0 1 0 0 0 0 0  1
{9, 32, 33} 0 0 2 2 2 0 2 2 2 2 0  1
{35, 37, 38} 0 0 0 3 0 0 0 3 3 0 0  0
{1, 21, 22} 0 0 0 0 0 0 0 0 0 0 0  2
{17, 18, 23, 25} 4 2 1 0 0 1 0 0 0 0 0  0
{28, 29, 30} 0 0 0 2 0 0 0 1 1 0 0  1
{27, 31, 34} 0 0 2 2 3 0 1 2 2 1 1  1
{19, 24} 0 1 1 0 0 0 0 0 0 0 0  1

Table 6

q 1 4 9 17 18 19 21 22 23 24 25 26
NumF B(q) 0 0 2 3 2 0 1 0 1 0 0 0
q 27 28 29 30 31 32 33 34 35 37 38
NumF B(q) 1 1 1 0 1 0 0 0 2 1 0

Table 7

q 5 6 7 8 9 10 11 12 13 14 15 19 20
T 1 0 1 0 1 0 0 1 0 1 0 0 1 0
T 2 0 0 1 0 0 0 1 1 1 1 0 1 0
T 3 1 0 1 1 0 1 0 0 0 0 1 1 1
T 4 1 0 1 0 1 0 1 0 0 1 0 1 1
T 5 1 0 1 0 1 1 0 1 1 0 0 1 1
q 21 22 27 28 29 30 31 32 33 34 35 36 37 38
T 1 0 0 1 1 1,u u 1 0 0 1 u 1 u u
T 2 1 1 1 0 0, u 0 1 0 0 1 1 1 0 1
T 3 0 1 0 1 1, u u u u u u u 1 u u
T 4 1 1 0 1 1, u u u u u u u 1 u u
T 5 1 1 0 1 1, u u u u u u u 1 u u