Design for Testability:Test Pattern Generation for Combinatorial Circuits

Test Pattern Generation for Combinatorial Circuits

This section describes how to compute test pat- terns for functional tests using an automatic test pattern generation (ATPG: automatic test pattern generator). With functional tests only the primary outputs of a circuit can be used to observe the circuit behavior. Additional information about power consumption or thermal dissipation are not considered.

For the sake of simplicity, at first we only consider combinatorial circuits. Later on in section 15.5 the results will be applied to sequential circuits.

A combinatorial circuit is a circuit without memory cells and without feedbacks. Such circuits perform Boolean functions, for any assignment (x1, x2, ... , xn) to the primary in- puts one obtains after some time a unique result (y1, y2, ..., ym) at the primary outputs depend- ing only on x.

In contrast to this definition the result y of a sequential circuit may not depend only on the current input x but also on internal states of the circuit and thus on previous inputs. As an example figure 15.12 gives a sequential circuit such that for input x1 = 1 and x2 = 1 there are two different stable states of the circuit. Alternatively the output y = (1, 0) or y = (0, 1) is derived as described by table 15.4. Actually the circuit represents an RS

present at the same time the correct result y = 1 is produced for the test pattern.

This does not mean that it has become impossible to detect the fault ‘γ s-a-0’, but that the complete test used originally is not well chosen. There- fore in constructing a test for stuck at faults one should pay attention that the test cannot become ineffective because of other undetectable faults. In practice it is often helpful not to use minimal sets of test patterns (minimal tests) but to generate several test patterns for each stuck at fault.

Test Pattern Generation by Path Sensitization

With the method of Boolean differences described in section 15.4.1 it is possible to derive test patterns for every detectable fault of the respective fault model. However, this method is quite complex. More favorable and much easier to implement is a method called path sensitization that is also applied for the D algorithm of test pattern generation. This method again uses the idea of Boolean differences but avoids transformations of Boolean formulas.

A test pattern for the fault ‘α s-a-0’ causes the wire α to change from logic value 1 in the correct circuit to the faulty value 0. This situation of a signal changing from a correct ‘1’ to a faulty ‘0’ will be denoted by the new signal value D. Accordingly D denotes the case that a signal ‘0’ in the correct circuit is replaced by ‘1’ in the faulty circuit.

The method of path sensitization tries to construct a D chain from the fault location α to a primary output. α is labeled by D or D depending on the fault type and then one tries to propagate symbol  or D to a primary output by applying appropriate input patterns. The resulting path from α to a primary output is called a D chain. In figure 15.20 such a D chain is shown for the fault ‘α s-a-0’.

According to table 15.10 only with β = 0 or β = D can the OR gate supply a suitable output signal. Since to observe the fault at wire α one cannot presuppose that there is also a faulty change of sig- nal beta, only β = 0 can be used to propagate the fault. Accordingly x5 = 1 is needed to complete the D chain through the NAND gate to output y.

We then conclude that the D chain found only exists for the case of β · x5 = 1. Thus the condition x3x4 ·x5 = 1 has to be satisfied. Since this condition also describes when the output y depends on α , the existence of a D chain from α to y is equivalent to Therefore the construction of D chains is a simple method of computing Boolean differences. In particular, for the circuit in figure 15.20 we obviously

As a consequence the characteristic equations for computing test patterns for stuck at 0 faults (Eq. (15.3)) and for stuck at 1 faults (Eq. (15.4)) can also be formulated in terms of D chains. For the example, the input pattern x = (1, 1, 0, 0, 1) is a suitable test pattern for ‘α s-a-0’ because it stimulates α = 1 and generates the sketched D chain.

The following theorem holds:

A fault ‘α s-a-0’ (resp., ‘α s-a-1’) can be detected exactly in the case when:

• the fault can be stimulated, at fault location α signal D (resp. D) can be generated; and

• a D chain can be generated from fault location α to a primary output.

An input pattern stimulating the fault and generating a D chain is a test pattern for the fault.

In practice, however, constructing a D chain is not always easy. In particular, for branching nodes it is not clear which branch to use for the D chain. If one decides arbitrarily for a path and does not succeed in constructing the D chain then one has to revise the decision and has to try alternative paths. Therefore if one needs n decisions between two possible branches, then in the worst case one has to consider 2n different approaches for D chains. This method is used by the D algorithm for test pattern generation:

• Input: A combinatorial circuit S and a stuck at fault at wire α connecting a gate output a to a gate input e

• Output: One test pattern to detect the fault if it is detectable. Otherwise a message is generated to indicate that the fault is undetectable.

• Method: Remove wire α .

Search (using back tracking) a stable state of the modified circuit with signals from such that following conditions hold:

2. For all primary inputs: xi ∈ {0, 1};

3. There is a primary output yi with yi ∈ {D, D}.

If a solution is found report the labels of primary inputs x1, ..., xn as test pattern. Otherwise, report that the fault is undetectable.

Of course, it is also possible that all attempts to construct D chains fail because no such chain exists for the given fault. Then the fault can not be observed at primary outputs because in spite of the fault the circuit always generates correct results. In this case there is an unintentional redundancy within the circuit such that the circuit can be simplified, or the circuit was designed to become fault redundant in such a way that it is insensitive to certain kinds of faults.

A simple example of a redundant circuit is given in figure 15.21. On trying to construct a D chain from x1 to y it turns out that x2 = 1 is neces- sary to propagate D through the AND gate, but on the other hand x2 = x3 = 0 has to hold for propagation through the NOR gate. Therefore there is no D chain and the output y does not depend on x1. As a check of that result one can transform the circuit function y = f (x1 , x2, x3) into y = x1x2 + (x2 + x3) = x2(x1 + 1) + x3 = x2 + x3 in order to recognize that indeed y does not depend The D algorithm determines for a given com- binatorial circuit with n primary inputs, and for a given stuck at fault, whether the fault is detectable at primary outputs. For detectable faults it generates a test pattern for the fault. In the worst case the algorithm needs a computational time which depends exponentially on n.

The description of the D algorithm stated above does not contain details of how to find a stable state of the circuit, a consistent signal assignment to all nodes using signals from {0, 1, D, D�. Instead, the ‘back tracking method’ known from computer science is mentioned. The actual implementation of the search is crucial for the attainable rate of pattern generation. Indeed, one applies heuristics to favor more promising approaches whenever de- cisions have to be made, and one uses a branch and bound method to detect wrong decisions as soon as possible.

One such optimized implementation of the D algorithm is called the PODEM algorithm (PO- DEM: Path Oriented Decision Making). For that implementation signal assignments are restricted to primary inputs in order to limit the solution space for back tracking. However in spite of all the tricky implementations the worst case compu- tationial time of the D algorithm is exponential in the number of primary inputs of the circuit 1). Thus the D algorithm is a very time consuming method.

In the following an efficient search for a test pattern is demonstrated using the example circuit from figure 15.22. At first the primary inputs are labeled with the signal set {0, 1} and the terminals a and e of the faulty wire are labeled with a = {1} and e = {D} (a = {0} and e = {D} for the fault ‘α s-a-1’). Then these sets are propagated forward through the circuit obtaining a label for each node denoting a set of possibly assigned signals. This way one recognizes at which primary output the fault eventually might be observed. This is because D chains can only reach outputs having the symbol D or D in its signal set. Figure 15.23 gives the signal sets obtained after forward propagation. It can be seen that the fault ‘α s-a-0’ can at most be observed at output y2 but cannot be observed at output y1.

Now one has to try out several additional assump- tions. For example, one may delete the signal 0 from x1 = {0, 1}, thus defining x1 = {1} and obtaining effects on other signal sets as shown in figure 15.27. Since the signal set of the output y2 furthermore contains the signal D, the arbitrary definition of x = 1 can be maintained for the time. Coincidentally, all signal sets are reduced to con- taining only one signal. Therefore a test pattern x = (1, 1, 0) has been found and the D algorithm terminates.

On the other hand, if instead of x1 = 1 one would have decided on x1 = 0 for the given example, the same procedure would have derived another test pattern for the fault ‘α s-a-0’. Thus in the example it never becomes necessary to revise a wrong decision.

With slight modifications the D algorithms can also be used for other fault models such as hard bridging faults or cellular faults.

Fault Simulation

Fault simulation is another method of test pattern generation. Whilest the D algorithm constructs one test pattern for a given fault, the method of fault simulation determines all faults which can be detected using a given input pattern. At first, according to the respective fault model a list of all possible faults is created. For example in the circuit presented in figure 15.28 containing five wires there are ten possible single stuck at faults. The five stuck at 0 faults will be denotes as a0, b0, c0, d0, y0 and for the five stuck at 1 faults we introduce the notation a1, b1, c1, d1, y1.

As shown below, the algorithm of fault simulation sequentially considers all possible input patterns (for the example there are 8 input patterns) and computes the output for the correct circuit and the output for all faulty circuits:

For the example of figure 15.28 the protocol of a fault simulation is presented in table 15.12. In the table erroneous output values are marked by underlining. Whenever a fault is detected, a test pattern for the fault has been found, and this case of a faulty circuit is no longer simulated.

In the first column it is indicated whether an input detects a fault not discovered before. Finally, the set of indicated patterns defines the test of the circuit. For the example we obtain a complete test{(000), (001), (010), (100), (110)}, a test with fault coverage of 100 %, for the single stuck at fault model.

However, in practice the input patterns used for fault simulation are not arranged in numerical or- der because in this way fault simulation might start with a lot of irrelevant patterns. For example, it may be necessary to set an enable input to 1 and reset to 0 in order to obtain relevant patterns.

Thus one often starts fault simulation using stimuli defined by the circuit designer for verification by simulation. Such simulation inputs should rep- resent typical stimuli that are also relevant for practical applications of the circuit. Afterwards fault simulation continues to work with random patterns at primary inputs.

During fault simulation one first observes a large increase of fault coverage, because typically many faults can be detected by many different patterns. Such faults are easy to detect. After that it needs more time to obtain a new test pattern. That is because hard to detect faults can only be observed by a few patterns and there is only a low prob-

ability of finding such a pattern by chance. For that reason fault simulation is often aborted when the fault coverage obtained is good enough or a predefined computational time is exceeded.

Please note that because fault simulation permanently administrates a list of undetected faults on every occasion the fault coverage actually achieved is known. Thus the algorithm can also be used to determine the fault coverage for a given set of test patterns, for this one differentiates between (surely) detected faults and potentially detected faults. For example, fault simulation may achieve undefined signals X owing to a transistor fault, such that it is not known whether in practice a value 0 or 1 will be observed. Then a fault is detected with high probability if a sequence of X values corresponds to a lot of well defined signal changes in the correct circuit. In this case it is very unlikely that during chip test a faulty circuit coin- cidentally produces the correct output sequence.

Optimization of Test Pattern Generation

It is possible to combine the advantages of fault simulation and the D algorithm. In practice one first performs a fault simulation using stimuli from circuit simulation and using arbitrary inputs until too much computational time is needed to find additional test patterns. Afterwards random pat- tern generation is replaced by the D algorithm to derive suitable test patterns for remaining faults. This way one limits the number of calls of the D algorithm to faults which are hard to detect, and, furthermore, all faults which are detected by the same test pattern are deleted from the fault set.

Another strategy of optimization is to use some preprocessing to identify sets of equivalent faults or dominating faults.

Equivalent faults: Two faults of a combinatorial circuit are equivalent if they can be ob- served by exactly the same set of test patterns.

For test pattern generation one reduces computational time and storage requirement if only one fault of a set of equivalent fault is taken into the error set. It is still better only to consider dominat- ing faults.

Dominating fault: A fault f dominates an- other fault g if any test pattern suitable for observing f can also be used to observe g.

This will be demonstrated by a simple example. Since the circuit given in figure 15.29 consists of six wires, there are twelve possible stuck at faults.

Amongst them the faults ‘α s-a-0’ and ‘β s-a-1’ are equivalent.

This directly results from the characteristic equa- tions of test patterns. For ‘α s-a-0’ we have α · dy/ dα = 1. With β = α and applying the concatenation rule for Boolean differences we obtain exactly the characteristic equation β · dy/ dβ = 1 of the fault ‘β s-a-1’, proving that both faults are equivalent. Accordingly α s-a-1 and β s-a-0 are also equivalent.

More general stuck at faults at the input of an inverter are equivalent to faults at the output. For an AND gate all stuck at 0 faults at an input or the output are equivalent. Furthermore, all stuck at 1 faults at inputs of an AND gate are dominating the stuck at 1 fault at the output.

As a result of such rules for the example it is sufficient only to derive test patterns for the following four faults: ‘α s-a-0’; ‘a s-a-1’;‘b s-a-1’; ‘c s-a-1’. Thus a fault simulation only has to consider four faults instead of twelve. Accordingly the D algorithm only needs four instead of twelve procedure calls.

Generally one can prove that for a fan out free combinatorial circuit it is sufficient to derive test patterns for all faults at primary inputs. The following theorem extends this result to arbitrary combinatorial circuits:

In order to detect all single stuck at faults of a combinatorial circuit it is sufficient to apply test patterns for all faults at primary inputs and for faults at outputs of branching nodes.

A further optimization method for test pattern generators concerns the propagation of signals through combinatorial circuits. Considering gates in a favorable order, one has only to perform each gate function for one time. Such an optimal sequence of gates can be obtained by topological sorting of the gates.

Some implementations of fault simulation also use the respective word length of computers to simultaneously perform several simulations. Typically, bit wise Boolean operations can be applied to com- plete data words. For example, with a word length of 32 bits one operation of a computer can simultaneously simulate an OR gate for 32 different pairs of arguments.

In spite of all the optimizations mentioned, test pattern generation remains an extremely hard problem and requires high computational time. Therefore the techniques described in sec- tion 15.4.6 and section 15.6 are of special interest to design circuits in way such that they become easy to test. In particular, for extreme cases one can avoid any test pattern generation.

Controllability and Observability of Signals

For a complete test concerning stuck at faults it is necessary to change every signal of a circuit at least one time. The effort needed to control a signal using only primary inputs is measured in terms of controllability.

For example, one may compute the entropy of signals. If p0 and p1 are the probabilities for signal x to become 0, resp., 1, then the entropy H(x) of signal x is defined as a value in the range between 0 and 1.

H(x) = −(p0 log2 p0 + p1 log2 p1).

H(x) = 0 means that the signal value never changes and H(x) = 1 indicates that the signal is perfectly random. Accordingly, the observability of signal x describes the influence of random changes, owed to a fault, on primary outputs.

Using such measures based on entropy, one can estimate whether a circuit is testable with random patterns, how difficult it is to derive suitable test patterns by fault simulation. Amongst other ap- plications such measures can be used in ASIC design tools to control automatic logic synthesis to generate easy to test circuits.

As examples some measures of controllability (CC: Cost of Controllability) and observability (CO: Cost of Observability) are presented. CC0(s) and CC1(s) describe the effort of assigning logical 0, resp., logical 1 to signal s considering the number of relevant primary inputs and the number of gates which have to be passed. For example, to set output y of an AND gate to logic 1, both inputs must be set to ‘1’ and signals have to be propagated through one gate. Thus for the AND gate one defines CC1(y) = CC1(x1) + CC1(x2) + 1. In order to set y to ‘0’ only one input of the OR gate has to be set to ‘0’. Therefore one defines CC0(y) = min [CC0(x1), CC0(x2)] + 1. The controllability of primary inputs is defined to be ‘1’.

Defining the observability the costs of primary outputs are set to 1. Then the observability of signal s results from the effort of propagating the signal to a primary output, to construct a D chain. This measure does not depend on the logic value of s.

Alternative definitions of measures are normalized so that all values are in the range between 0 and 1. In addition to combinatorial measures one also defines similar measures to describe the sequential reachability and observability of states also consid- ering the number of needed clock cycles [15.48].

For circuit designers there are simple methods to improve the controllability and observability of signals. For example, the combinatorial depth of a circuit can be limited by introducing a shift register to partition the circuit into smaller sub- circuits. Introducing a test mode and additional ports for sequential write and read operations, in- ternal signals become controllable and observable, thus increasing the testability of the circuit. For sequential circuits this technique is known as the Scan Path method and is described in more detail in section 15.5.1.

Another approach to improving the controllability of signals uses special signal codings. To explain that method we will construct combinatorial circuits such that only two test patterns are sufficient for setting all signals both to logic 0 and to logic 1 [15.22]. However, this may need a large amount of additional hardware. Therefore in practice one will not use this extreme case of a complete observability with only two input patterns but will use more refined codings.

As an application example we consider the com- binatorial circuit shown in figure 15.30 consisting of primary inputs a, b, c, d, primary output y, and five gates. Using the method of red/black coloring its controllability will be improved. At first we double all signals and gates obtaining ‘red’ inputs and outputs ar, br, cr, dr, yr and the ‘black’ inputs and outputs as, bs, cs, ds, ys. Accordingly we introduce red and black gates. As shown in figure 15.31, wiring is arranged so that all ports of gates are connected to signals of the same color. Only for inverting outputs is the color changed.

Using the assignment ar = as = a, br = bs = b, cr = cs = c, and dr = ds = d at primary inputs we obtain yr = ys = y. Thus the new circuit twice calculates the same result as the original circuit. Now we remove all gates and signals which are not needed for computing yr and obtain the smaller circuit shown in figure 15.32. Again that circuit  is equivalent to the original circuit but there is an additional interesting property. If all ‘red’ inputs are set to ‘0’ (resp., ‘1’) and all ‘black’ inputs are set to ‘1’ (resp., ‘0’) then all signals of the same color also have the same value. Thus using the two input patterns as = bs = cs = ds = 0, cr = 1, and as = bs = cs = ds = 1, cr = 0 every signal within the circuit can be set to ‘0’ and ‘1’. Indeed, only two input patterns are sufficient for full controlla- bility of all wires.

For the example, the signal coding mentioned be- fore replaces the signal c by the pair of signals (cr, cs). For normal operation of the circuit one uses cr = cs; however, for test mode one uses cr j= cs. Because of the coding there are additional input patterns available for testing. Please also note that using the presented method only controllability has been improved but not observability. In particular, for the generated circuit all possible single stuck at faults are stimulated by the two test patterns but it is not clear whether the faults can be observed at primary outputs.

Test Pattern Sequences

For transistor faults (section 15.3.5) and bridging faults (section 15.3.3) the behavior of a combina- torial circuit may become sequential. In such a case it is not always possible to detect a fault by applying only one test pattern.

For example, a transistor stuck open fault in a combinatorial CMOS gate may isolate the output node in such a way that for some input patterns the output will not represent the desired result, but the previously computed value.

To detect such effects the output node has to be pre-loaded. If the intended output value is ‘1’ (resp., ‘0’) the output node has to be set to ‘0’ (resp., ‘1’) before applying the test pattern. Then because of the changing output signal one can be sure of observing the actual output and not the previous one.

Using this method two inputs are needed for any test pattern. To reduce the number of necessary inputs one can arrange the test patterns in such a way that whenever possible one test pattern per- forms the pre-loading for the next one.

For example the test pattern set {11, 10, 01} de- scribes a complete stuck at test of a NAND gate.

Table 15.15 gives a suitable sequence consisting of five inputs such that the output signal is correctly pre-loaded for every test pattern. This way stuck open faults are also detected.

Because of the next theorem the method of using pairs of test patterns also works well for large cir- cuits as long as only one gate is faulty. In general, if more gates are defective two input patterns may not be enough because pre-loading of an internal signal may also fail as a result of a second fault.

In a non-redundant combinatorial circuit with gates in complementary CMOS logic every single stuck open fault can be detected using a pair of test patterns. This also holds for multiple stuck open faults as long as only one gate is affected.