In enhanced scan, each storage element contains the corresponding bits of both the initialization and test vector. This can be implemented in several ways. In a flip-flop design, the flip-flops can be connected in a scan chain, and their outputs connected to holding latches. After the initialization vector has been scanned into the flip-flops, the vector is transferred to the holding latches, initializing the circuit under test. The test vector is then scanned in and transferred to the holding latches to apply the test to the circuit. This approach has the advantage that the initialization and test vectors are independent of one another. A second advantage is that the circuit PPIs are fixed while the test vector is scanned in, drastically reducing test power. Test power is discussed in Chapter 7. Because the initialization and test vectors are independent, a third advantage of enhanced scan is increased delay fault coverage. The disadvantage of enhanced scan is the extra area, power, and delay associated with the holding latch. The area and delay overhead of the holding latch preclude the use of enhanced scan in most designs.

Most designs implement scan by using muxed-D flip-flops, as discussed in Chapter 2. That is, the D (data) input of a D-type flip-flop is fed by a 2:1 multiplexer, with one multiplexer input fed by the circuit logic (the PPO) and the other fed by the previous flip-flop in the scan chain. The scan enable (SE) signal controls the multiplexer. The advantage of the muxed-D scan design is that the system clock is used to clock the flip-flops in both normal and test modes, and the design has low area and delay overhead. The disadvantage of the muxed-D design approach is that PPIs change with each shift of the scan chain, resulting in high power dissipation during scan-in or scan-out. This is discussed further in Chapter 7.

Delay test pattern application in scan designs uses a variable clock approach. The test pattern is slowly shifted into the scan chains, fast system clock cycles are used to apply the test, and then slow shift cycles are used to shift out the result (and shift in the next test pattern). This approach makes each test pattern independent. The slow shift speed avoids critical timing along the serial data path of the scan chain and reduces the power dissipated during scan shifting.

For enhanced scan, the initialization vector is scanned in and then loaded into the hold latches. The test vector is then scanned in and launched when the hold latches are loaded, and then it is captured with the system clock. The disadvantage of this approach is that the hold latch enable must be able to operate at system speed, so that the latch enable to system clock timing is accurate. In contrast, scan testing using muxed-D flip-flops uses the system clock to launch and capture patterns, so there are no timing correlation issues related to the clock tree.

The muxed-D scan design has only one bit stored in each PPI. Because the flip-flop input is only connected to the PPOs of the circuit under test and the neighboring scan cell, this constrains the relationship between the initialization and test vectors. The initialization vector is scanned in, so it does not have any constraints. The test vector, however, can only be derived in two ways. The first is to have the test vector be a 1-bit shift from the initialization vector. This is generated by shifting the scan chain by 1 bit. This 1-bit shift to launch the transition is known as launch-on-shift (LOS), launch-off-shift, or skewed load [Patel 1992] [Savir 1992]. The procedure for applying a LOS test is as follows:

The advantage of LOS is that a combinational ATPG can enforce the pattern constraint with only minor modifications; fast test generation methodologies for combinational circuits can be applied without many modifications; and the constraint can be met for most faults, minimizing test patterns and test generation time. The primary disadvantage of LOS is that in a muxed-D scan implementation, after the shift has occurred to launch the transition, the scan enable must be flipped at the rated system clock speed, so that the PPOs can capture the test result on the next system clock cycle. This requires designing the scan enable to have the same timing performance as the system clock. This requires too much power, area, and design effort for most designs. An alternative is to have separate scan enables for the launch and capture flip-flops, so that the launch SE can remain in scan mode while the capture SE is already in capture mode. Multiple scan enables are sometimes used to reduce test power dissipation (see Chapter 7). This places constraints on the scan design, because the inputs and outputs of a combinational logic block must be controlled by separate scan enables. Level sensitive scan design (LSSD) based scan can use LOS because it uses separate clocks for the L1 and L2 latches [Savir 1992]. Another disadvantage of LOS is that some false long paths may be exercised. Because the test vector is the shifted version of the initialization vector, such a state transition may not be possible in the functional mode, thereby allowing nonfunctional behavior.

If LOS cannot be used, the alternative is to derive the test vector from the PPOs feeding the flip-flops. The PPO values in turn are generated by the initialization vector. This is known as launch-on-capture (LOC), launch-off-capture, functional justification, double-capture [Wang 2006a], or broad-side test [Savir 1994]. The procedure for applying a LOC test is as follows:

The advantages of the LOC approach are that the SE has no timing constraint, and the test vector is a legal state of the circuit, assuming the initialization vector is a legal state. This reduces the testing of false paths, which can lead to yield loss. This is discussed further in Section 6.7. The primary disadvantage of LOC is the need to justify the test vector back one time frame to determine the initialization vector, increasing test generation time, and pattern count. This constraint also makes some faults untestable. This was listed earlier as an advantage, but a sequentially redundant fault may present a reliability hazard. If such redundant faults occur in online error-checking hardware, they must be tested to verify the correct function of this hardware.

The preceding discussion assumes that the timing between the launch and capture of a test pattern uses the rated system clock period. The drawback is that some test generation methods, particularly for transition faults, typically use a breadth-first search algorithm that tends to select short paths through each fault site. As a result, when tested at rated speed, many paths have considerable timing slack, and so only relatively large delay defects can be detected. One solution is to generate one or more longest paths through each fault site [Majhi 2000] [Sharma 2002] [Qiu 2003a], as discussed in Section 6.6. However, the increased path length increases test data volume [Qiu 2004a]. Rather than maximizing the length of the tested paths, the alternative is to shrink the capture clock timing to minimize the slack for each pattern [Mao 1990]. However, separate timing for each pattern drastically increases test data volume. An alternative is to group patterns into sets of almost equal-length paths [Kruseman 2004]. The test engineer must trade off between the number of groups and test data volume. Because the chip is being tested at faster than its rated speed, logic transitions may still be occurring when the capture clock is applied. Those flip-flops fed by paths that exceed the cycle time or containing hazards must be masked off. The faults that are not detected because of masking are targeted by patterns run at the next lower clock speed [Barnhart 2004]. Applying transition fault patterns at faster than the rated speed has been shown to catch small delay defects that escape traditional transition fault tests [Kruseman 2004] [Amodeo 2005].

Faster-than-at-speed testing can be applied whenever test patterns propagate on paths with timing slack. There are two primary concerns when using this test approach. The first is the accuracy of the timing models. If paths are slower than predicted, a faster-than-at-speed test can reject chips that pass at the rated speed. Timing margin must be added statically or dynamically, reducing the effectiveness at screening small delay defects. The second problem is the additional power supply noise introduced by operating at faster than rated speed. The power grid has less time to recover from the launch, so the circuit may operate more slowly than it would if clocked at the rated speed.

The most commonly used delay fault model is the transition fault (TF) model [Barzilai 1983]. In this model, a gate input or output is assumed to have a slow-to-rise (STR) or slow-to-fall (STF) delay fault. For every stuck-at fault in a circuit, there is a corresponding transition fault (TF). The delay of the TF is assumed large enough that any path through it will be detected as slow—that is, the delay increase because of the TF must exceed the slack of the shortest path through that line.

The primary advantage of the TF model is that test generation does not need to consider circuit timing. A stuck-at fault test generator can be modified to meet the additional requirements for generating TF tests [Waicukauski 1987]. Because a stuck-at fault can be considered a very slow TF, a TF test set will detect all the corresponding stuck-at faults. The TF model has more constraints than the stuck-at fault model, so the TF coverage is normally lower than stuck-at fault coverage. Top-off vectors can be generated to test the stuck-at faults not detected by the TF test set.

The primary disadvantage of the TF model is that its resolution is limited by the difference in delay between the longest and shortest path through the fault site. Stuck-at and TF test generators normally select the easiest path to test, which is the shortest path, because this has the fewest necessary assignments. This problem can be avoided by propagating along low-slack paths [Lin 2006a]. Another major problem with the TF model is that TF tests often only propagate a glitch from the fault site, which may not be detected unless the delay fault is large [Lin 2005a].

Production experience shows that many delay defects are due to resistive interconnect vias, which cause both the rising and falling transitions through that line to be slow [Benware 2003]. This can be modeled by the inline-delay fault. This fault is analogous to the TF, except that only one of the STR or STF faults must be detected at each fault site. A test set for inline-delay faults is smaller than a test set for TFs.

Even though resistive vias are more common in newer technologies, misshapen transistors, resistive contacts, and resistive shorts can still cause STR or STF faults without the opposite slow transition. Therefore, high delay fault coverage still requires a TF test set. If a technology contains many inline-delay faults, test generation can first be done for them, and then top-off TF patterns can be generated. If testing stops on the first failure, this combination of patterns will reduce average test time without loss of TF coverage.

A spot defect that causes a small delay fault for a particular transition on a gate input or output can be modeled as a gate-delay fault, also termed a local delay fault [Carter 1987]. Here “small” is a delay that is larger than the minimum slack but smaller than the maximum slack for that line. Testing such faults requires testing a long or longest path with the appropriate transition through the fault site. The quality of a test set is defined by how close the minimum detected delay fault sizes are to the minimum detectable fault sizes [Iyengar 1988].

The line delay fault model [Majhi 2000] extends the gate-delay fault model to test a rising or falling delay fault on each line in the circuit. Detecting the smallest delay defect that can cause failure requires propagating along the longest sensitizable path through that line.

The path-delay fault model [Smith 1985] models the distributed delay on a path. A path is a sequence of gates from PIs to POs, with a transition on each gate output along the path. The gate input on the path is referred to as the on-input, or on-path input, whereas the other inputs are side inputs or off-inputs. If the circuit contains a path that is slow for a rising or falling transition, then it contains a path-delay fault. Unless explicitly mentioned, we refer to the transition direction at the input to the path. The path-delay fault model assumes that any path can have any delay, so fault coverage is defined as the fraction of all paths (or all sensitizable paths) tested. The path-delay fault model is more general than the fault models discussed above, because a path-delay fault test will detect the corresponding transition, inline, or gate-delay faults, as well as distributed delay resulting from process variation (global delay faults) or supply noise.

The primary drawback of the path-delay fault model is that the number of paths can be exponential in the size of the circuit, so computing and achieving high coverage is difficult. For example, ISCAS-1985 benchmark circuit c6288, a 16-bit multiplier, has close to 10²⁰ paths. Almost all of the long paths in this circuit are false paths [Qiu 2003c]. Coverage estimates can be improved by eliminating untestable paths [Cheng 1993] [Lam 1993], but these methods are expensive. Path-delay testing is primarily used to test a set of longest (or critical) paths provided by static timing analysis.

A fault model intermediate between gate and path delay is the segment delay fault model. It assumes that a segment along a path is slow [Heragu 1996]. Because the segment length is bounded, the number of segment faults is linear in the circuit size. The propagation delay fault model combines the transition fault and path-delay fault models [Lin 2005a]. It assumes that the sum of the local delay and the distributed delay of the fault propagation path causes a failure, with at least one robust propagation path.

The models described here do not adequately describe the delay defects that are more common in advanced technologies. As a result, such models cannot achieve the desired product quality. In practice, delay faults can be a combination of local and global disturbances. Delay faults caused by local disturbances are termed local delay faults, and those caused by global disturbances are termed global delay faults [Luong 1996] or distributed path-delay faults [Sivaraman 1996]. Resistive shorts and opens and capacitive crosstalk cause local delay faults, whereas power supply noise, intradie temperature distributions, and process variation cause global delay faults. The combined delay fault (CDF) model was developed to incorporate all of these effects [Qiu 2003b, 2004b]. Resistive short, open, and capacitive crosstalk locations can be extracted from the layout design, and are roughly linear in circuit size [Stanojevic 2001]. The circuit-level delay behavior of shorts, opens, and crosstalk can be abstracted to rules for test generation [Chen 1999] [Krstic 2001] [Li 2003]. Linear approximations [Lu 2005] can be used for nonlinear process correlation effects [Luong 1996]. A Monte Carlo approach can identify potentially longest paths under process variation [Liou 2002a] [Krstic 2003]. The statistical delay quality model incorporates process variation and defect characteristics into the coverage model [Sato 2005].

Rather than directly targeting a delay fault model, defect-based delay tests can attempt to maximize observations of each fault site. For example, the N-detect stuck-at test [Ma 1995] can be extended to target transition faults [Pomeranz 1999]. A related approach is to generate transition tests to each reachable output of a transition fault site, that is, transition fault propagation to all reachable outputs (TARO). The TARO test was shown to achieve high defect coverage [Tseng 2001] [McCluskey 2004] [Park 2005]. Similarly, the DOREME [Dworak 2004] test approach that increases the excitation and observation of fault sites increases the detection of delay defects.

Technology scaling has led to increased power supply noise, which can cause the chip to incorrectly fail at rated speed during testing [Saxena 2003]. Test generation must take power supply noise into account [Krstic 1999] [Liou 2003]. The primary challenge is accurate supply noise (delay) estimation at low cost [Wang 2006b]. An alternative is to use on-chip test structures to calibrate the supply noise [Rearick 2005]. See Section 7.3 for a further discussion of noise during testing.

The CDF coverage metric [Qiu 2004b] was developed to accurately reflect test quality, considering realistic delay defects. In the CDF coverage metric, the correlation in path delays is used to substantially reduce the pessimism of the path-delay fault model while avoiding the optimism of the transition and gate-delay fault models. The CDF coverage metric exploits structural and spatial correlation between paths [Luong 1996] [Lu 2005]. Two paths have structural correlation when they share a common path segment. For example, in Figure 6.3, path a-d-e and b-d-e are structurally correlated because they share segment d-e. Two paths can also have spatial correlation because the path delays are functions of the manufacturing process parameters, which are spatially correlated. For two paths that are physically close to each other, the delay correlation is high because the paths have similar process parameters.

Figure 6.3. Example of structurally correlated paths.

Figure 6.4 shows the delay space [Luong 1996] for two paths, assuming the path delay is a one-dimensional function of process parameters. The delay space is the bounded region in which the probable delay value combinations are represented. It is assumed that each path has min-max delays. If the two paths have no correlation, the delay value combination can be anywhere within the rectangle. If they are perfectly correlated, the delay space shrinks to a line, which means if path 1 has max (min) delay under a combination of certain process parameters, path 2 also reaches its max (min) delay under the same combination of process parameters. In reality, the correlation is somewhere in between, and the realistic delay space is the shaded area. Using correlation information, the delays on the untested paths can be predicted by the delays on the tested paths [Brockman 1989], reducing the paths that must be tested.

Figure 6.4. Delay spaces for different path correlations.

In terms of probability, the coverage for test set t is as follows:

Equation 6.1. 

Under the CDF model, a single local delay fault on a line is assumed, termed the fault site. Any path through the site is subject to process variation. A delay fault may be caused by a local delay fault, a global delay fault, or a combination of the two.

CDF detection is probabilistic, instead of deterministic. For example, suppose there are two paths, P₁ and P₂, through a fault site, and the local extra delay is not large enough for either path to be definitely slow. Figure 6.5 shows the delay space [Sivaraman 1996] for this fault. t_max is the maximum specified delay of the circuit. The circuit has some probability that path 1 or 2 is slow. If test set t₁ tests path 1 only and test set t₂ tests path 2 only, then both t₁ and t₂ are required to guarantee detection of the fault.

Figure 6.5. Delay space of a fault.

Using this probability model, Formula (6.1) can be translated into Formula (6.2) to compute the detection probability (DP) for fault site i with local extra delay Δ (the size of the local delay fault):

Equation 6.2. 

In the example shown in Figure 6.5, if test set t tests path 1 only, the DP is area(B∪C)/area(A∪B∪C); if t tests path 2 only, the DP is area(B∪A)/area(A∪B∪C); and if t tests both paths, the DP is 100%.

The preceding analysis is for a fixed local extra delay Δ. For fault site i with an arbitrary Δ, the DP for site i is computed as:

Equation 6.3. 

where Δ_{0, i} is the minimum slack at the fault site and p_i(Δ) is the probability density function (PDF) of Δ at fault site i, based on the PDF of resistive shorts and opens. The overall fault coverage for test set t is:

Equation 6.4. 

where w_i is the weight for fault site i(Σ_i w_i = 1). Fault sites might be weighted based on the probability of a delay fault occurrence, such as the critical area.

Based on Formula (6.2), if the path delays are correlated, the DP computation is dependent on the delay space. For example, in Figure 6.5, the areas of A, B, and C change if the delay space changes. Because accurate spatial delay correlations are usually not known, coverage can be computed assuming no correlation and 100% correlation. This provides lower and upper bounds on the coverage.

The CDF coverage metric (Formulae 6.2–6.4) is inexpensive, because only a small subset of paths must be considered. For example, Figure 6.6 shows the delays of four paths through a fault site, each having a delay distribution because of process variation. Suppose path P₁ is tested by t, and the longest testable path P₀ is not tested. When Δ₀ < Δ < Δ₁, DP_i,Δ (t) is 0; when Δ > Δ₂, DP_i,Δ (t) is 100%, because the tested path P₁ is definitely slow; when Δ₁ < Δ < Δ₂, DP_i,Δ (t) increases from 0 to 100% as Δ increases. Thus, the fault coverage computation is required only in this interval. The main cost is computing the fault efficiency, which is the number of tested faults over the number of testable faults. This requires checking the sensitization for all the paths whose length is within the interval where DP_i,Δ (t) rises from 0 to 100%. A lower bound on coverage can be quickly computed by assuming all structural paths are testable. Experiments on ISCAS-1985 circuits show the error of this approximation is <4% [Qiu 2004b].

Figure 6.6. Fault coverage computation.

The CDF fault coverage metric suggests a test strategy:

Figure 6.7 shows the conceptual relationship between fault coverage and the percentage of tested paths, sorted in decreasing order of length. If there is no local delay fault, the fault coverage increases quickly and reaches 100% after all potentially critical paths are tested. The curves for the CDF coverage metric have “jumps,” where the first path through a fault site is tested. The traditional path-delay fault coverage assumes the percentage of testable paths tested.

Figure 6.7. Fault coverage versus percentage of tested paths.

Simulation experiments with the CDF coverage metric on ISCAS-1985 benchmark circuits [Qiu 2004b] show that a TF test set achieves reasonably high coverage (98.96%), but lower than what can be achieved by a K longest paths per gate (KLPG) test set (see Section 6.6.4), or a combination of TF and a set of critical paths. Figure 6.8 shows the fault efficiency for c7552, assuming the number of longest rising and falling paths per line increases from 1 to 5. As the figure shows, only a small number of longest paths are needed through each fault site to achieve high fault efficiency. In addition, the benefit of testing one longest rising and one longest falling path (the fault efficiency increase from the transition fault test to the K = 1 test) is more significant than testing more long paths (increasing K from 1 to 5).

Figure 6.8. Fault efficiency for c7552, assuming the K longest rising and falling paths through each gate are tested (K = 1 to K = 5). UB is the upper bound (no intradie process variation), and LB is the lower bound (random intradie process variation).

Transition fault simulation is similar to stuck-at fault simulation, except for the additional criterion that the fault is sensitized by the appropriate transition [Waicukauski 1987]. Good machine simulation determines the transitions at each fault site. For example, a rising transition sensitizes an STR fault. Each sensitized fault is then propagated to see if the fault effect reaches a PO or PPO.

Gate or line delay fault simulation must account for circuit delays, in order to determine the smallest detected delay fault [Carter 1987] [Pramanick 1988]. The method in [Carter 1987] assumes that an earliest arrival time and latest stabilization time is known for each signal waveform when transitioning from its initial value to its final value. The signal has an unknown value during this time interval. First good machine simulation is performed to compute these values for all signals. Propagating the earliest arrival times and latest stabilization times is based on the controlling values at each gate. For example, the latest stabilization time for a signal transitioning from 0 to 1 on an AND gate input determines the latest stabilization time for the output to transition from 0 to 1. For each pair of input vectors, fault simulation consists of injecting an extra delay at each fault site, determining if this extra delay propagates in terms of new arrival and stabilization times, and then whether it is detected at the POs and PPOs at the observation time. This process is repeated for all fault sites and patterns. Fault detection may be uncertain, if the observation time is between the earliest arrival and latest stabilization times.

A large number of path-delay fault simulators have been developed, for example [Smith 1985] [Schulz 1989] [Fink 1992] [Kagaris 1997]. These can be classified into enumerative and nonenumerative methods. Enumerative methods use a list of paths and compare the paths sensitized by a given vector pair to the list. The value algebra used for determining signal propagation must be sufficient to handle the sensitization criteria. For example, [Smith 1985] used a six-valued algebra to handle hazards when computing robust test coverage. Because the number of paths in most circuits is very large, nonenumerative methods were developed to compute fault coverage without an explicit list of paths. Such techniques allow for a compact graph representation of all path-delay faults in the circuit, called the path status graph (PSG). The PSG is modified dynamically during test generation or fault simulation to account for the set of faults that remain to be targeted.

CodSim is a CDF fault simulator for combinational circuits [Qiu 2003b]. It incorporates resistive shorts and opens, capacitive coupling, and process variation, and considers robust and nonrobust propagation on paths through each fault site. CodSim computes the detection probability for each fault site, for test set t. If the DP is above the specified threshold, the fault site is dropped. The DPs for all fault sites are then used to compute the overall fault coverage. The three phases of the fault simulation algorithm are as follows:

After good machine simulation, the initial and final logic values and the nominal transition time of the last event for each line are known, as shown in Figure 6.10. The numbers next to the transition symbols indicate the transition time, assuming a unit gate delay model. S1 or S0 indicates a stable 1 or 0.

Figure 6.10. Robust propagation path identification.

In phase 2, the robust/nonrobust propagation paths through each line are identified. A line’s robust propagation paths can be computed using its immediate fanout lines’ robust propagation paths. In Figure 6.10, suppose line d has a robust propagation path P₁ with length 6, and line e has path P₂ with length 7. The robust propagation paths for line b are computed by checking the final logic values on the side inputs of gate G₁ and G₂. Then two paths are identified: b-P₁ with length 7 and b-P₂ with length 8. Because the propagation paths are robust, the extra delay Δ on a line must be detected if t_trans + Δ + l_prop >t_max, where t_trans and l_prop are the transition time and propagation path length associated with that line, respectively. Because t_trans and l_prop are statistical values, the computed Δ is also statistical. For resistive shorts, the opposite logic value on the other shorted line must be checked.

The nonrobust propagation paths can be identified in a similar way. The difference is that if there is no transition on a line, the nonrobust propagation paths from that line must also be computed, such as line g in Figure 6.11. The reason is that a local delay fault on line d may generate a glitch on g, and the computation of the nonrobust propagation paths from d uses g’s propagation paths. The time complexity of phase 1 is O(V · C), for V vectors and C lines in the circuit.

Figure 6.11. Nonrobust propagation path identification.

Fault detection through a nonrobust propagation path is dependent on the delays on the side inputs to the path. In Figure 6.11, an extra delay on line b does not affect the transition time on line h, even though line b has a nonrobust propagation path. Therefore, the validation of these paths must be checked (phase 2). After phase 1, each line has a few nonrobust propagation paths. The validation check can be performed by introducing an extra delay Δ on the line, where Δ = t_max – t_trans – l_prop, and running fault simulation for the test pattern which sensitizes this path to check if the slow signal can be detected at any PO or PPO. This procedure starts with the smallest Δ. If a small Δ can be detected, the validation check for the paths that can only detect large Δ is not necessary. Experiments show that normally only a few paths must be checked for each line.

Checking only robust and nonrobust paths may miss some functional sensitizable paths [Cheng 1996b]. However, because these paths always appear in pairs and the shorter path determines the delay, in most cases they do not contribute to the fault coverage. Thus, these paths are not checked unless there is no long robust or nonrobust propagation path through the fault site.

In phase 3, the extra delay due to coupling is computed. Similar to phase 2, phase 3 introduces an extra delay Δ at the fault site, where Δ can cause one propagation path (either robust or nonrobust) to be slow, and runs the fault simulation considering coupling for the vector sensitizing the path. The delay Δ is introduced because the coupling alignment is dependent on Δ. Because of the interdependence of aggressor and victim signal timing, iterative simulation is used. The phase 3 analysis is only performed for long paths.

Simulation experiments on ISCAS-1985 circuits with resistive opens show that for 10,000 random patterns applied at rated speed, the CDF and transition fault coverages are within 1%, as each fault site has a high probability of having many long paths tested. The fault efficiency of a KLPG-5 test (see Section 6.6.4) is 99.9%+. Simulation of resistive shorts shows fault coverage of approximately 90%. The reduced coverage is because resistive shorts on fault sites with large slack cannot be detected until the short resistance is so low that it nearly causes a stuck-at fault [Li 2003]. Simulation of KLPG-5 tests shows much higher resistive short coverage, because the longest paths are tested.

Transition fault ATPG is based on modified stuck-at fault ATPG [Waicukauski 1987]. The initialization vector sets the initial value, and the test vector launches the transition and propagates it to a PO or PPO. For example, for a STR fault on line g, a logic 0 is set on g by the initialization vector, and in the test vector the value on g is set to 1, with a propagation path sensitized. These conditions can result in test invalidation due to hazards [Lin 2005a]. Such hazards can be reduced by attempting to generate single input change (SIC) patterns, in which the test vector differs from the initialization vector by only a single bit.

A simple ATPG model is created by introducing a seven-valued algebra, with logic values representing two time frames of a sequential circuit. The seven values are S1, S0, R1, F0, U1, U0, and X, denoting steady 1 across both time frames, steady 0 across both time frames, a rising transition across the two frames, a falling transition across the two frames, don’t care in the first frame and logic 1 in the second frame, don’t care in the first frame and logic 0 in the second frame, and don’t care in both frames, respectively. Boolean operators can operate on this seven-valued logic, and an ATPG can be developed to generate test vectors for each target transition fault.

One may also employ a stuck-at ATPG to generate tests for transition faults. By noting that a transition fault can be mapped to two stuck-at faults, vectors from a stuck-at suite can be used to construct the transition test set. For example, consider a fault x STR. To detect this fault, signal x must be set to logic 0 in the first time frame, and in the second vector, launch a transition by setting x = 1 and simultaneously propagating its fault effect to a PO or PPO. In other words, the first vector excites x stuck-at 1, and the second vector detects x stuck-at 0. As the two vectors may be uncorrelated, this technique works well under the enhanced-scan architecture. A test set can thus be constructed by matching stuck-at vectors. A graphical representation of all the test vectors and stuck-at faults can permit finding a minimum length test set. A concept of transition test chains was proposed in [Liu 2002, 2005] [Wang 2006a] to compute short chains that maximize detection of transition faults.

Despite the work that has gone into transition fault test generation, a complete transition fault test set may not detect all critical paths, because the ATPG decision process often favors those easier paths to launch or propagate the fault. The easier paths are generally the shorter paths. Conversely, a test set that exercises the longest paths in the circuit may not detect all transition faults, because a transition fault may not be robustly or nonrobustly launched or propagated [Gupta 2004]. Therefore, there has been effort to generate test sets that also cover long paths, such as [Sharma 2002], [Qiu 2003a], and [Gupta 2004]. Among these approaches, some try to generate a set of longest paths such that every gate is covered. Subsequently, a test set that tests these paths would also achieve full transition fault coverage. Alternatively, in [Gupta 2004], the aim was to launch the transition as late as possible, while at the same time propagating it through the longest propagation path. This technique thus elevates the quality of generated transition tests so that long paths are exercised.

A transition fault that is testable under one application scheme (e.g., LOC) may become untestable under another test application. Consider the circuit fragment shown in Figure 6.12. Suppose a, b, and c are outputs of scan flip-flops. The STF transition on line d would be untestable under the LOS test application. This is because to detect this STF, ab = 00 and c = 0 in the test (second) vector are needed for the transition to propagate through the AND gate. In other words, the test vector must be abc = 000. However, under LOS, this vector is a shifted version of the initialization vector. For the test vector to be abc = 000, the initialization vector must be abc = 00X. However, this initialization vector cannot set d = 1. Consequently, this STF fault is untestable under LOS.

Figure 6.12. Launch-on-shift untestable transition fault.

Now, as the previous example illustrated, a LOS untestable fault may be testable under other methods of test application. Interestingly, however, if a transition fault is LOC untestable, it is guaranteed to be functionally untestable. This is because under LOC, the two vectors are functionally correlated in that the second vector is derived from the first via clocking the circuit. Because the starting state of a LOC test is fully controllable, any fault that is untestable would also be functionally untestable as no initial state would be able to both launch the transition and observe its effect. Note that, however, a functionally untestable transition fault may be detected under LOS, because the two vectors are not functionally correlated [Liu 2003].

Gate delay fault ATPG attempts to generate a long path through every gate input and output for both rising and falling transitions. This overlaps with the goal of many path delay subset ATPG approaches [Sharma 2002], described later. Here we focus on extensions to transition fault ATPG to improve the detection of small delay defects. One approach is to make random decisions when selecting the propagation path from the fault site. This should result in a longer path length than the normal approach of using breadth-first search, which tends to produce the shortest path. However, this approach had little benefit in a recent experiment [Qiu 2006].

A second approach is to use static timing analysis (STA) to compute the timing slack of each line in the circuit. The ATPG then attempts to propagate through the fault site on one or more low-slack paths [Lin 2006a]. Because the least slack path may be false, the ATPG must consider other low-slack paths. When the paths through a fault site are of similar length, it does not matter which path is chosen, particularly if none of the paths is critical [Qiu 2004b]. When there is a significant difference in path length, the ATPG should attempt to propagate on the longest path. A low-cost approach to achieve this goal is to take the difference between the maximum and minimum structural path lengths in the fanin and fanout cones of a fault site [Kajihara 2006]. The cone with the larger difference is given search priority. On average, this results in longer path lengths than a standard TF ATPG algorithm.

Test generation for path-delay faults can be categorized into enumerative and nonenumerative approaches. Enumerative methods generate a list of long structural paths and check their testability [Li 1989] [Majhi 2000] [Murakami 2000] [Shao 2002]. This approach works well when most paths are testable, but it is inefficient if many long paths are untestable. Rather than testing all paths, the globally longest paths can be targeted [Lin 1987].

To increase the efficiency, NEST [Pomeranz 1995] generates paths in a nonenumerative way, but it is only effective in highly testable circuits. DYNAMITE [Fuchs 1991] improved the efficiency for poorly testable circuits, but it has excessive memory consumption for highly testable circuits. RESIST [Fuchs 1994] exploits the fact that many paths in a circuit have common subpaths and sensitizes those subpaths only once, which reduces repeated work and identifies large sets of untestable paths. RESIST can handle circuits such as ISCAS-1985 benchmark c6288 with an exponential number of paths. However, both the enumerative and nonenumerative algorithms are too slow to handle industrial circuits.

The RESIST algorithm was extended to find a set of longest testable paths that cover every gate [Sharma 2002]. This test set targets line delay faults. This method takes advantage of the relations between the longest paths through different gates and guarantees their testability. However, this work assumes a unit delay model and fails on c6288.

The CDF fault coverage metric suggests that testing multiple paths through each fault site will increase fault coverage. The K longest paths per gate (KLPG) test generation algorithm [Qiu 2003a, 2004a] was developed to test the K longest sensitizable paths through each gate or line for both STR and STF faults at the fault site. Figure 6.13 illustrates the KLPG path generation algorithm. A launch point (of a path) is a PI or PPI, and a capture point is a PO or PPO. In the preprocessing phase, STA computes the maximum delay from each gate to capture points, without considering any logic constraint. This value is termed the PERT delay or STA delay. In the path generation phase, partial paths are initialized from launch points. A partial path is a path that originates from a launch point but has not reached any capture point. A value called esperance [Benkoski 1990] is associated with a partial path. The esperance is the sum of the delay of the partial path and the PERT delay from its last node to a capture point. In other words, the esperance of a partial path is the upper bound of its delay when it becomes a complete path that reaches a capture point.

Figure 6.13. KLPG path generation algorithm.

In each iteration of the path generation algorithm, the partial path with the maximum esperance value is extended by adding one gate. If the last gate of the partial path has more than one fanout, the partial path splits. Then the constraints to propagate the transition on the added gate, such as noncontrolling side input values required under the robust or nonrobust sensitization criterion, are applied. Direct implications are then used to propagate the constraints throughout the circuit. If there are any conflicts, the search space containing the partial path is trimmed off. If the partial path does not reach a capture point, some false path elimination techniques [Qiu 2003a] are applied to prevent it from growing to a false path. Then, its esperance is updated and the partial path is inserted back into the partial path store. If a partial path becomes a complete path, final justification is performed to find a vector. This process repeats until enough longest testable paths are generated. Because the longest path through a fault site is likely the longest path through other fault sites along the path, fault dropping is performed when a new path is generated.

An iteration of the path generation begins by popping the max esperance partial path from the path store. The partial path is extended by adding a fanout gate along the max esperance path. For example, in Figure 6.14, the partial path g₀ ... g_i is extended by adding gate g_j because extending to g_j could potentially preserve the max esperance. If the partial path has more than one extendable fanout, it must be copied, its esperance updated and pushed into the path store. For example (Figure 6.14), because gate g_i has two fanouts, and extending the partial path to g_j may result in false paths later, the partial path g₀ ... g_i must be saved because extending it to gate g_k may get a longer testable path. Because fanout g_j has been tried, the min-max esperance in the copy becomes 11/11.

Figure 6.14. Extending a partial path: (a) before extension and (b) after extension.

After the partial path is extended (g₀ ... g_ig_j in Figure 6.14) the constraints to propagate the transition on the added gate (g_j) are applied. Under the nonrobust sensitization criterion, noncontrolling final values on the side inputs are required. Under the robust sensitization criterion, in addition to noncontrolling final values, the side inputs must remain noncontrolling if the on-path input has a transition to the controlling value. Then direct implications are used to propagate the constraints throughout the circuit and discard false partial paths. For example (Figure 6.14), if extending partial path g₀ ... g_i to gate g_j results in a conflict (see Figure 6.15), both path g₀ ... g_r and g₀ ... g_s are false, and the partial path is deleted from the path store. Experimental results show that most false paths can be eliminated by direct implications [Benkoski 1990] [Qiu 2003a].

Figure 6.15. Conflict after applying direct implications.

If the launch-on-shift approach is used, the logic values on neighboring scan flip-flops are dependent on each other. For example, in Figure 6.16, the logic value of cell A in the initialization vector is the same as that of cell B in the test vector. The relation between cell B and C is the same. Therefore, if there is a rising transition assigned to cell B, direct implications will try to assign logic 1 to cell A in the initialization vector and logic 0 to cell C in the test vector and propagate the new assignments throughout the circuit. If there are any conflicts, the partial path is a sequential false path under the launch-on-shift constraints. This algorithm does not consider modification of the scan chain design to reduce the dependence, such as inserting dummy cells between the scan flip-flops.

Figure 6.16. Implications on scan flip-flops.

If LOC is used, dependence exists between the two vectors. Even if the circuit had a pipeline structure, in which the two vectors are independent, the structure can also be seen as the general structure shown in Figure 6.16. The conversion is shown in Figure 6.17. Thus, the test vector is the output of the combinational circuit, derived from the initialization vector, excluding the PIs and POs. In other words, V₂ = C(V₁), where V₁ and V₂ are the two vectors and C is the logic of the combinational circuit. For example, if it is assumed that a testable path has a rising transition launched from cell A and a rising transition captured on cell B, in Figure 6.16, then for the initialization vector, output a′ must be logic 1 (then it becomes the value for input a in the second vector); and for the test vector, input b must be logic 0 because it is derived from the initialization vector. Then more direct implications can be performed from a′ and b.

Figure 6.17. A pipeline circuit structure.

Most designs include non-scan flip-flops. Even after simulation of the test setup sequence and scan procedure, some flip-flops remain uninitialized. In addition, embedded memories and “black boxes” are assumed uncontrollable, so their outputs have unknown values. A seven-valued algebra is used to distinguish between controllable and uncontrollable unknown values. The seven values are logic 0/1, x (unknown/unassigned), u (uncontrollable), 0/u (0 or uncontrollable), 1/u (1 or uncontrollable), and x/u (unknown or uncontrollable). At the beginning of test generation, the lines from the uncontrollable memories are u and all the other lines are x. The x values may be assigned a known value during test generation. In a two-input AND gate, if one input is x and the other is u, the output is 0/u because if the input with x is assigned a logic 0, the output becomes 0, but if this input is assigned a logic 1, the output becomes uncontrollable. Figure 6.18 shows two examples, assuming M₁ is a non-scan memory cell and M₂ is a scan flip-flop. The logic values assigned by simulation are shown. If the conventional three-value algebra is used, all the lines are assigned x’s.

In Figure 6.18a, line n₃ can never be logic 1, so all paths through n₄ are false. Using a three-value algebra, test generation may have to check all paths through n₄. Moreover, it can be learned that n₅ can never be logic 1, so its faults are untestable. Because all the paths through n₄ contain n₅, the faults on n₄ are also untestable. Figure 6.18b shows how this algebra permits additional searching. When a partial path reaches gate g₂, the value of the test vector on side input n₃ is set to logic 0 and direct implications performed. The value on n₂ is set to 0 and further direct implications can be performed from M₂. In the conventional three-value logic, direct implications stop at gate g₁.

Figure 6.18. Application of seven-value algebra in path-delay test: (a) trimming the search space and (b) enabling additional search.

Final justification is used to find a delay test pattern when a complete path is found, using the corresponding LOS or LOC constraints. For LOC, one time frame expansion is used, as shown in Figure 6.19. The initialization vector V₁ can be generated within one time frame, but since the test vector V₂ = C (V′₁), the goal is to find a satisfying V′₁. Because V₁ and V′₁ are identical excluding the “don’t care” bits, in the justification process, there must be no conflicts between V₁ and V′₁.

Figure 6.19. Time frame expansion for final justification using launch-on-capture.

A KLPG-1 test set is constructed as follows. For each fault, a test is first generated using the longest robustly testable path (as this is the most reliable test, even though it may not be the longest path). If there is no robust test, the longest restricted nonrobustly testable path is selected. The restrictions are that the test must have the required transition at the fault site, and the local delay fault must be detected at a capture point, if there are no other delay faults. In other words, the test is also a TF test.

For example, path n₁-n₂-n₃-n₅ is a nonrobustly testable path in Figure 6.20. It is a valid nonrobust test for lines n₂ and n₃. However, it is not a valid nonrobust test for line n₅ because the glitch (or transition) may not happen if the delay of path n₁-n₄ is greater than the delay of path n₁-n₂-n₃. Similarly, it is not a valid nonrobust test for line n₁ because the slow-to-rise fault may not be detected even if there are no other delay faults.

Figure 6.20. Restricted nonrobust test.

If a fault has no robust or nonrobust test, a transition fault test that can detect a small local delay fault is generated. In KLPG test generation, this case usually happens when the local delay fault can only be activated or propagated through multiple (functionally sensitizable) paths, such as the slow-to-fall fault on line n₂ in Figure 6.21. The length of the shortest paths in the activating or propagating path set determines the test quality. The longer the shortest path, the smaller the local delay fault that can be detected. A similar situation occurs when an uncontrollable value selects between two propagation paths. Only the shorter of the two paths can be assumed.

Figure 6.21. Transition fault test.

Experimental results with KLPG test patterns show that the execution time and number of paths rise slowly with K, since many gates share the same paths. More faults are detected with LOS than LOC, with each having unique detects [Qiu 2004a]. The LOS robust path lengths are close to those of enhanced scan, while LOC path lengths are often shorter. This indicates that LOS and enhanced scan sensitize false paths. Silicon results with KLPG-1 test patterns have shown that they detect delay faults that escape TF tests [Qiu 2006].

Logic implications capture Boolean dependencies between various nets in a circuit. Logic implications have been used in ATPG engines in the past. For details of computing static implications, refer to [Zhao 1997] [Wang 2006a]. In the rest of the discussion, the following notations will be used:

Impl[g, v, t]: Set of implications resulting from assigning logic v to gate g in time frame t.

[g, v, t] → [h, w, t₁]: The assignment g = v in time frame t implies h = w in time frame t₁.

There are relationships between nets that are valid in the same time frame but can only be learned through “sequential learning” (i.e., Boolean learning across time frames). Such relationships are missed if only one time frame is analyzed. Furthermore, not all sequential relationships can be learned by time frame expansion [Syal 2006]. During ATPG, all combinational constraints will be automatically factored in the process and need not be stored. On the other hand, sequential relations are of great help to the ATPG to avoid those undesirable state spaces.

Multiliteral Constraints

Although the pair-wise sequential constraints may help to capture a large set of illegal states, they capture relationships only between a pair of gates. These may be insufficient to capture illegal states that require an analysis on more than two gates. To cover such illegal states, an approach to identify sequential relationships between multiple nets (multinode constraints) was proposed [Syal 2006].

The concept of multinode implications is rather simple. Starting with (A = 0, B = 1, C = 0), if via simulation an implication (D = 1) is obtained, then the multinode implication would simply be [(A = 0, B = 1, C = 0) → (D = 1)].

Let A_i represent an assignment of the form [g_i, v_i, t], where g_i is a gate in the circuit, v_i ε {0, 1}, and t is the time frame of this assignment. In other words, each A_i denotes a value assignment to a variable in the net-list. The form of pair-wise implication is A_i → A_j whereas the form of multinode implication is (A₁ Λ A₂Λ ... Λ A_m) → (A_m+1. The element on the left-hand side of the arrow is called the implicate. The element on the right-hand side of the arrow is called the implicant.

Because the implicate of a multinode constraint is a conjunction of terms, the probability of the implicate evaluating to true reduces with the number of terms. Thus, the usefulness of a multinode constraint decreases with its size. Thus, multinode constraints are often restricted to a small size. Similar to pair-wise constraints, multinode constraints are also restricted to reside within the same time frame.

Consider the circuit fragment illustrated in Figure 6.23. Two important implications can be computed for gate D, namely (1) [D, 1, 0] → [F, 0, 1] and (2) [A, 1, 0] Λ [B, 1, 0] → [D, 1, 0]. By the transitive property of implications, a third relationship can be learned in a straightforward manner: (3) ([A, 1, 0] Λ [B, 1, 0] → [F, 0, 1]. Note that implication (i) is a pair-wise relation while relationships (2) and (3) are multinode constraints. Such relationships can be derived in linear time simply by analyzing every two-input gate.

Figure 6.23. Fragment of sequential circuit.

However, deriving constraints this way is not entirely desirable. Specifically, constraint (2) is a combinational relationship and, as stated previously, is useless as a functional constraint because it does not block any states that could violate this constraint. Constraint (3) involves gates across time frames and is thus not considered for representing multinode constraints.

As a result, a different approach is needed. Assume that the following sequential relationships have been identified: [g_i, v_i, 1] → [A, 1, 0] and [g_j, v_j, 1] → [B, 1, 0], then a new multinode constraint can be deduced: [g_i, v_i, 1] Λ [g_j, v_j, 1] → [F, 0, 1]. Note that this multinode constraint has all the desirable characteristics, namely that it is not a combinational constraint and all the involved gates reside in the same time frame. In addition, the constraint can be learned by analyzing relationships around every single gate, retaining the linear complexity.

The preceding discussion begs the following question: How can one efficiently discover the gates g_i that hold the relations [g_i, v_i, 1] → [A, 1, 0] and [g_j, v_j, 1] → [B, 1, 0]? In essence, the task is to identify the implicates of [A, 1, 0] as well as for [B, 1, 0]. At first glance, this task seems daunting. However, the contrapositive law allows for an efficient computation of such implicates. Recall that the contrapositive law states that if x → y, then ¬y →¬x. In other words, it is sufficient to compute what [A, 0, 0] implies, then by the contrapositive law, the implicates can be obtained. For example, if [A, 0, 0] → [g_i, ¬v_i}, 1] and [B, 0, 0] → [g_j, ¬v_j, 1] then by the contrapositive law, [g_i, v_i, 1] → [A, 1, 0] and [g_j, v_j, 1] → [B, 1, 0]. These implications are exactly what are needed to form the desired multinode constraint discussed earlier. Consider the circuit of Figure 6.22 again. Because it is known that [A, 0, 0] → [C, 1, 1] and [B, 0, 0] → [E, 0, 1], by contrapositive law, [C, 0, 1] → [A, 1, 0] and [E, 1, 1] → [B, 1, 0] are obtained. So the multinode constraint can be constructed to be [C, 0, 1] [E, 1, 1] → [F, 0, 1]. Again, this constraint can be generalized (([C, 0, t] [E, 1, t]) → [F, 0, t]; for all values of t) and it can be used as a constraint during constrained ATPG.

Finally, note that for the AND gate D, D = 1 is used to search for the multinode constraint. If it were an OR gate, the opposing value would have been chosen. In essence, the particular value assignment is chosen in order to form a conjunction of values necessary to form a multinode constraint. In the AND gate case—that is, ([A, 1, 0]Λ [B, 1, 0]) → [D, 1, 0].

The complexity for computing the prescribed multinode constraints is thus linear with respect to the number of gates in the circuit. Both the pair-wise and multinode constraints are computed and stored, which are then used to constrain the ATPG process.

Suppose we are given a set of functionally untestable delay faults, F_u, and we want to make sure that the generated vectors will not incidentally detect any fault in F_u. A naive approach is to fault simulate the faults in F_u whenever a vector is obtained, and the ATPG engine would backtrack if some faults in F_u are incidentally detected and continue to search for a different pattern. However, this naive approach can be computationally expensive. To reduce the expense, instead of focusing on F_u, each fault in F_u is projected onto the state space S, to identify subspaces that will detect them. The projected state space S essentially constitutes a portion of the illegal states. This is because any state s that can detect any fault f in F_u is an unreachable state, because fault f would otherwise be functionally detectable. Subsequently, the ATPG needs to use the projected state space to avoid searching in the identified illegal subspaces. The projected state space, S, can be represented as a constraint formula, as explained earlier in Section 6.7.

Given a constraint formula that represents the set of illegal states, during the ATPG process, we must make sure that no clause in the constraint formula ever evaluates to false (i.e., all literals in a clause simultaneously evaluate to false). The set of constraints also enables speed up of the ATPG by avoiding futile search spaces. Whenever a decision is made on a state variable s_i, we apply this decision assignment to all the constrained clauses in the formula that contain s_i. Application of this assignment may result in some unit clauses (a unit clause is an unsatisfied clause with exactly one remaining unassigned literal left). This remaining literal is called an implication. The implied variable automatically becomes the next decision variable. For example, consider a constraint clause (¬s1 +¬s2 +¬s3). Suppose s1 has been decided or implied to be 1, and the current decision makes s2 = 1. At this time, this clause yields an implication, s3 = 0. With s1 = s2 = 1, the only way not to cause any conflict is to have s3 = 0. We also check whether there is conflict (where one clause evaluates to false). If there is a conflict, the ATPG backtracks immediately [Liu 2003].