Logic Testing of Bridging Faults in CMOS Integrated Circuits.
AbstractWe describe a system for simulating and generating accurate tests for bridging faults in CMOS ICs. After introducing the Primitive Bridge Function, a characteristic function describing the behavior of a bridging fault, we present the Test Guarantee Theorem, which allows for accurate test generation for feedback bridging faults via topological analysis of the feedback-influenced region of the faulty circuit. We present a bridging fault simulation strategy superior to previously published strategies, describe the new test pattern generation system in detail, and report on the system's performance, which is comparable to that of a single stuck-at ATPG system. The paper reports fault coverage as well as defect coverage for the MCNC layouts of the ISCAS-85 benchmark circuits.
Introduction
In the search for increased quality of integrated circuits, manufacturers must ensure that shipped
parts are actually good. To do this, manufacturers must test for the defects that are likely to occur.
Shen, Maly, and Ferguson have performed defect simulation experiments showing that the majority
of spot defects in MOS technologies cause shorts and opens [13, 23], and Feltham and Maly have
shown that the majority of spot defects in current MOS technologies cause changes in the circuit
description that result in shorts [11].
The single stuck-at fault model was adopted because it is powerful and simple, but it was never
meant to represent the manner in which circuits behave in the presence of defects. A test set
that detects 100% of single stuck-at faults may not detect a high percentage of the manufacturing
defects. Ferguson and Shen reported that complete single stuck-at test sets failed to detect up to
10% of the probable shorts in the circuits they examined [13].
The need for tests that detect the electrical behavior exhibited by shorts requires a bridging fault
model. The first step to generating bridging fault tests is to decide for which of the approximately
potential bridging faults to target (where n is the number of nodes in the circuit). Also necessary
is a theoretical foundation for bridging fault simulation and test generation that is simple, general,
and easily incorporated into current automatic test pattern generation (ATPG) systems, as well as
When this work was performed, Brian Chess was with the Computer Engineering Board, University of California,
Santa Cruz CA 95064. His current address is Hewlett-Packard Company, 1501 Page Mill Road MS-6UJ, Palo Alto
y Tracy Larrabee's address is Computer Engineering Board of Studies, University of California, Santa Cruz 95064.
This work was supported by the Semiconductor Research Corporation under Contract 93-DJ-315 and the National
Science Foundation under grant MIP-9011254.
implementation techniques that will take the theoretical vision to a complete and accurate system
comparable in efficiency to single stuck-at ATPG systems. The rest of this paper will describe a
theoretical foundation and a practical system that meets these needs.
The next section will define crucial terms and briefly review the differences between the single
stuck-at fault model and the bridging fault model, and it will describe the work of previous
researchers. Section 2 will present the theoretical foundation that makes the implementation possi-
ble. After describing the implementation in detail in Section 3 and reporting on its performance in
Section 4, Section 5 will finish by summarizing the new work and describing interesting problems
that remain open.
1.1 Definitions and Terms
A faulty circuit is an isomorphic copy of an associated fault-free circuit except for the introduction
of a change known as a fault. Some input combinations, when applied both to the fault-free circuit
and to the faulty circuit, will produce identical outputs: in this case the input combination does not
produce a logic error on a circuit output, and it is not a logic test for the introduced fault. If there
is no input combination that produces an error, the fault, considered in isolation, can never change
the logic function of the circuit: in this case the fault is logically undetectable (it is a redundant
fault).
In the popular stuck-at fault model, it is assumed that a circuit becomes faulty because a wire
has lost its ability to switch values; the wire is stuck high (stuck-at 1) or stuck low (stuck-at 0). If
this wire has a permanent value of 0 in the faulty circuit, and an input set causes the corresponding
wire in the fault-free circuit to take on the value 0, the input set will create no fault effect. Any
wire that has a different value in the faulty circuit and the fault-free circuit carries an error, or has
been activated, but this may not cause an error at a circuit output. If the input set produces an
error on a circuit output, the activated fault has been propagated to a circuit output. A successful
test must activate and propagate a fault.
Defects are fabrication anomalies. This paper is concerned with local defects-defects affecting
only a small portion of the IC. Local or spot defects are often the result of specks of contaminates on
the IC or photolithography during manufacturing. The way a defect affects the circuit's behavior
is a fault. It is common for local defects to cause a circuit to behave as if the outputs of two
gates, which are not connected in the fault-free circuit, are connected. This model of faulty circuit
behavior is the bridging fault model [19].
Changes in behavior can be detected as changes in logical function, excess propagation delay,
or excess quiescent power supply current (or any combination). This paper is primarily concerned
with faults that cause changes in the logical function of the circuit, but bridging fault detection by
monitoring excess quiescent power supply current (I DDQ testing) is an important adjunct to logic
testing [2]. I DDQ tests for bridging faults are easy to generate but expensive to apply. The results
in Section 4 suggest that it would be appropriate to produce I DDQ test patterns for the bridging
faults that are either proved untestable or are aborted. This would provide a small number of I DDQ
tests that would significantly increase the percentage of tested defects without the cost of the time
on the tester that would be necessary to provide I DDQ tests for all bridging faults.
A combinational test for a bridging fault shares the same basic characteristics as a test for
a stuck-at fault. To introduce an error, the bridge value must be different from one of the gate
outputs in the fault-free circuit; to propagate the error, at least one path of fault effects from the
bridge to a circuit output must exist. However, the process of activating and propagating the fault
is complicated by the possibility of feedback.
If a bridging fault creates a feedback loop, a formerly stable combinational circuit may oscillate
or take on sequential characteristics that mask the detection of the fault. It is possible to detect
some feedback bridging faults that create sequential behavior with sequences of test vectors [19],
but in this case extensive analysis may be required to ensure not only that the feedback element
can hold state, but that it is guaranteed to hold state. It can be dangerous to assume that the state
element introduced by the fault will achieve a stable digital value. As reported by Abramovici and
Menon [1], the vast majority of feedback bridging faults can be detected with single combinational
tests.
When discussing feedback bridging faults, it is useful to refer to the two bridged wires by their
locations in the circuit. Given any path that goes from a circuit input to a circuit output and
contains the two bridged wires, the back wire is the wire closest to the circuit inputs on this path,
and the front wire is the other bridged wire.
1.2 Previous work
When the idea of test generation for bridging faults was new, the assumption that the bridging faults
caused wired-AND or wired-OR behavior was good. In the dominant technologies of the time (such
as TTL), bridging faults did create wired logic. Abramovici and Menon detailed complete theories
and techniques to perform ATPG on bridging faults (including bridging faults that introduced
in combinational circuits exhibiting wired-logic behavior [1]. However, wired-logic does
not accurately reflect the behavior of bridges in static CMOS circuits [4, 12, 20].
The wired-logic model (wired-AND or wired-OR) is the easiest model to implement for simulation
and test pattern generation; with the exception of feedback, the wired-logic model is almost
as easy for an ATPG system to deal with as the single stuck-at model. A more exact model would
assume that the circuit value at the fault site is described in general by a Boolean function of
the inputs to the gates driving the bridged wires. This function could be derived in a number of
ways-two notable methods are analog simulation [12, 22] and the voting model [3, 4].
Deriving the Boolean function by simulating the two components with the bridged outputs
works well at modeling the upstream components from the fault site, but fails to take into account
the possible sensitive behavior of downstream components. An optimistic model assumes that the
bridge value is always digitally resolvable (in which case the model might not always be correct). A
pessimistic model describes the fault behavior with an incomplete Boolean function, where some of
the bridge's behavior falls within a gray region within which the model fails to give an answer [12].
Both of these approaches have been implemented in bridging fault simulators and test pattern
generators [12, 20].
A more general model assumes that the analog behavior induced by the fault extends for a
certain distance beyond the fault site, after which the circuit behavior is digitally resolvable. The
idea that a bridge voltage can be interpreted differently by different downstream gates is known as
the Byzantine Generals Problem for bridging faults [5]. The EPROOFS simulator [14] implements
this via mixed-mode simulation, where a SPICE-like analog simulation of the region around the
fault site is incorporated into a digital simulation of the rest of the circuit. This method provides
correct answers when previous models might have failed, in particular for many cases involving
feedback bridging faults. EPROOFS results are promising, but EPROOFS is slow compared to
stuck-at fault simulation, and the use of a mixed-mode simulator precludes adaptation of the
technique for test pattern generation. Although EPROOFs is much more accurate than previous
simulators, it still may make errors when accurately predicting the behavior of the faulty circuit
requires a timing analysis of the digital logic. There are faster simulators that do EPROOFS-like
simulation, although they sacrifice some accuracy for speed [18, 22]. There is currently no test
pattern generator that implements such sophisticated models.
A feedback bridging fault may create an asynchronous sequential circuit in a formerly combinational
network. The state of the circuit may prevent stimulation of the fault, or a stimulated fault
may cause oscillation, which may prevent a tester from detecting an error at the circuit outputs.
Feedback faults cannot be ignored as they can comprise a sizable percentage of realistic bridging
faults. Between 10% and 50% of the realistic bridging faults for the MCNC layouts of the ISCAS-85
circuits are feedback bridging faults.
Most approaches to generating tests for feedback bridging faults check for tests invalidated by
oscillation or sequential behavior by analyzing the inversion parity between the two bridged wires
[1, 20]. Because of reconvergent fanout, the inversion parity may change from one input vector to
the next. This means that the inversion parity must be recalculated for every input vector, which
is inefficient. Previous successful bridging fault test pattern systems-notably that of Millman and
Garvey [20]-generate a test as if there is no feedback and then check to make sure that feedback
will not invalidate the test. This can be wasteful: a fault that is undetectable because of feedback
could have numerous legitimate tests unless feedback is taken into consideration. It is much more
efficient to consider feedback as part of the test generation process.
The next section describes the theoretical foundation for the Nemesis ATPG system. Nemesis
incorporates arbitrary logical behavior of bridged components via the primitive bridge function
and prevents feedback complications during test simulation and generation via the Test Guarantee
Theorem.
Theoretical Foundations
Realistic faults have historically been unpopular candidates for test pattern generation. Modeling
the behavior of realistic faults frequently requires the circuit to be treated as an electrical entity
rather than a logical one; this is not amenable to standard test generation techniques. This section
will describe the theoretical foundation for a practical realistic bridging fault ATPG system.
2.1 The Primitive Bridge Function
A bridging fault transforms a portion of the circuit around the bridged wires into a single fault
block in the faulty circuit. The extent of the circuit replaced by the fault block is a question of
the sophistication of the bridging fault model to be used for test pattern generation. The fault
block can range from being a replacement for only the two gates with bridged outputs to being
a replacement for the two gates with bridged outputs as well as many downstream gates (and
perhaps even gates lying along any possible feedback paths). Figure 1 shows how a bridging fault
between the outputs of two NAND gates can create a simple two-component fault block in the
faulty circuit, and Figure 2 shows a more inclusive fault block for the same fault that will do a
better job of modeling varying logic thresholds of downstream gates.
A
Faulty Circuit
Z
Y
Y
Fault-free Circuit

Figure

1: A bridging fault between X and Y creates a simple fault block.
F
A
F
A
Fault-free Circuit Faulty Circuit
Y

Figure

2: The same bridging fault between X and Y creates a more general fault block.
The function of the fault block depends on its size and on the behavior of the bridged components
in the chosen technology. The characteristic function of the fault block is the Primitive Bridge
Function or PBF. The PBF can be specified as a truth table or other Boolean representation.

Table

shows three possible PBFs for the introduced fault block from Figure 1. The column
labeled ZWAND shows the fault block output if the technology in question follows the wired-AND
model, the column labeled ZWOR shows the fault block output if the technology in question follows
the wired-OR model, and the one labeled Z SPICE shows the fault block output derived from circuit
analysis of the CMOS standard cell components from the MCNC library.
This analysis of the two cells driving the bridge to create the PBF is known as two component
simulation. Depending on the accuracy required, the fault block may actually have to replace more
than two components; it may need to include downstream gates in order to make sure that the
outputs of the fault block are digitally resolved [5]. Two-component simulation can also model
arbitrary bridge resistance values by treating discrete bridge resistances as separate faults.
For bridging faults that do not introduce any feedback, the output of the PBF is computed
with wire values from the fault-free circuit. As presented in the next Section, the PBF for bridging
faults that do introduce feedback is computed twice: once with fault-free circuit values, and once

Table

1: PBFs from wired-AND, wired-OR, and SPICE simulation of MCNC cells
with feedback-influenced values.
2.2 The Test Guarantee Theorem

Figure

3 shows a feedback bridging fault with the potential for oscillation when using the SPICE-
derived PBF from Table 1. In fact, we know that this circuit, implemented with the MCNC cell
library, will not oscillate for any set of inputs because the feedback path is too short. Instead, the
bridge will settle to an intermediate voltage favoring the back wire's fault-free value. This result
is not predicted by the PBF for the bridge and is dependent on the length of the feedback path.
The actual behavior of the bridge in this situation is immaterial: because the PBF does not model
the behavior, we cannot reliably use it for detection of the fault. When the circuit
has the potential for oscillation. Figure 4 shows a feedback bridging fault with the potential for
a test being invalidated because of a previous state. For example, when and the
SPICE-derived PBF from Table 1 is used, the outputs of the faulty circuit would be different if the
feedback loop had a previous value of 0 than if it had a previous value of 1. In this case, if input X
is set to 0, the feedback path is broken, and no previous state could invalidate a test.
A
Z

Figure

3: A feedback bridging fault that might oscillate
Z
A

Figure

4: A feedback bridging fault that may hold state

Figure

3 illustrates a situation in which, for certain input values, the back wire will not affect
the value on the front wire in the fault-free circuit but will affect the output of the fault block in the
faulty circuit. Using the SPICE-derived PBF from Table 1, the potential test should
be rejected because it may cause the circuit to oscillate, but if the PBF was for the wired-AND
model, the circuit could never oscillate.
The method for preventing oscillation is the same as the method for preventing sequential
behavior-if an error can be propagated from the back wire without altering the inputs to the PBF
such that the PBF changes the value on the bridge, then neither oscillation or sequential behavior
will prevent a test regardless of which wire carries the fault. This observation leads to:
The Test Guarantee Theorem for feedback bridging faults. If a test creates a situation
in which the result of propagating either Boolean value from the back wire causes the PBF to assign
the same value to the bridge, the test will not be invalidated because of feedback.
Given that the PBF correctly models the behavior of a bridge in the absence of feedback,
the PBF can be guaranteed to correctly model the the behavior of a bridge in the
presence of feedback only when the feedback does not influence the result of the PBF
computation. Since the fault-free circuit is acyclic, the sole source of feedback in the
faulty circuit is the back wire of the bridge. If the value on the back wire does not
affect the result of the computation of the PBF, then no source of feedback can affect
the result of the computation of the PBF, and the PBF correctly models the behavior
of the bridge. 2
Like the wired-logic theorems of Abramovici and Menon [1], the Test Guarantee Theorem
requires that the feedback loop created by the bridge be broken. But unlike the theorems of
Abramovici and Menon, this requirement may not be satisfied simply by stipulating that the back
wire not sensitize the front wire in the fault-free circuit; the back wire must not be allowed to
sensitize the output of the fault block. If the PBF in use is wired-AND, the new theorems will
agree with the Abramovici and Menon theorems; if the PBF in use is more complicated, the
theorem provides additional accuracy. Enforcing the additional constraints imposed by the Test
Guarantee Theorem involves an analysis of the feedback-influenced region of the circuit. A wire is
feedback-influenced if it is on any path between the two bridged wires.
If an error is to be propagated from the back wire, the feedback influenced region is a subsection
of the faulty region, shown in Figure 5. Analysis of the region consists of applying the PBF to
faulty circuit values as well as fault-free circuit values and making sure that the results of the
two PBF computations agree. If an error is to be propagated from the front wire, the feedback
influenced region is disjoint from the faulty region, as shown in Figure 6. Analysis of the feedback
region involves propagating the compliment of the fault-free value of the back wire, and applying
the PBF to the resulting values.
Oscillation and sequential behavior do not need to be prevented by performing a check after
test generation. Instead, independence of previous state and the absence of oscillation can be
established as a requirement for test generation. Because the method of preventing oscillation and
sequential invalidation are the same, there is no need for an analysis of the inversion parity between
the bridged wires.
Back Wire Front Wire
Faulted Region
Feedback Region
Circuit Inputs Circuit Outputs

Figure

5: Error on the back wire: the feedback region is a subset of the faulty region.
Carafe, an Inductive Fault Analysis tool, produces a list of realistic bridging faults-bridging faults
that could be caused by a single defect connecting two gate outputs. Carafe considers the layout of
the circuit and lists the nodes that are adjacent on the same conducting layer of the circuit or that
cross each other on layers separated by a single layer of insulating material[15, 16]. This paper is
only concerned with Carafe-extracted faults in the interconnect: shorts involving internal cell lines
can also be extracted by Carafe, and they present interesting problems [7], but they are beyond
the scope of this paper.
Previously, bridging fault ATPG was thought to be unwieldy because of the number of feasible
bridging faults and the complexity of the bridging fault model. While the number of possible bridging
faults is O(n 2 ) where n is the number of nodes in the circuit, the number of realistic bridging
faults is a much more manageable O(n) [2]. Also, if the PBFs are derived from two component
simulation, the number of different PBFs needed for fault block analysis is not prohibitive because
only one PBF is needed for each type of fault block (and the number of different types will be
small for synthesized layouts). Section 4 will compare numbers of stuck-at faults, realistic bridging
faults, and two-component PBFs for the MCNC layouts of the ISCAS-85 circuits [6].
Carafe reports the likelihood of occurrence for each fault it extracts. This likelihood indicates
how likely the fault is to occur relative to all of the other faults in the list. This means that the
ATPG system can report not only what percentage of the realistic bridging faults are tested, but
what percentage of the probable bridging defects are tested. The defect coverage should be much
more indicative than the fault coverage when it comes to relating test quality to defects per million
parts shipped (DPM) [25].
After Carafe determines the realistic bridging faults, SPICE simulation is used to determine
the PBF for each fault, and then the Nemesis ATPG system[17] generates tests. Figure 7 shows
the organization of the total system.
e
Feedback Region
Circuit Inputs Circuit Outputs
Faulted Region
Front Wire

Figure

on the front wire: the feedback region is disjoint from the faulty region.
Fault
Characterization
Cell Descriptions
Defect Coverage
Test Patterns
Fault Types
PBFs
Layout
Defect Statistics
Carafe Nemesis

Figure

7: System organization
3.1 Simulator
Unlike the bridging fault simulator of Abramovici and Menon [1], for which pseudocode is given
in

Figure

8, the Nemesis method of bridging fault simulation, for which pseudocode is given in

Figure

9, does not associate bridging faults with wires; instead, wires are tagged with Boolean
values representing whether or not an error can be propagated to a primary output [8]. After
attempting to propagate an error from a wire, a field in the wire's data structure is set to reflect
the success or failure of the propagation. If a bridging fault further down the fault list introduces
an error onto the same wire, it can immediately be determined whether or not the fault can be
propagated.
Nemesis bridging fault simulation is modeled after the Parallel Pattern Single Fault Propagation
(PPSFP) simulator of Waicukauski et al. [24]. Note that, given the PBF for a bridge, the bridge
value for each of the parallel patterns is evaluated in the same fashion as that of any other gate (each
of which can perform an arbitrary combinational function). In parallel bridging fault simulation,
faults can be propagated from both of the wires involved in the bridge at the same time. The fault
block does not introduce an error on both of the wires for any input pattern: the error is always on
one wire or the other. This means that each bit-slice in the pair of faulty and fault-free wire values
may represent an error on one wire or the other, but not both. A wire is placed on the simulation
Simulate the fault-free circuit with test vector T
foreach wire (W ) involved in a bridging fault
if T detects a stuck-at fault on W
foreach bridging fault (BF ) associated with W
if the PBF for BF places an error on W and meets the TGT
Accept test T : BF is detected
else
test T does not detect BF from wire W

Figure

8: Pseudo-code for Abromovici and Menon bridging fault simulation
Simulate the fault-free circuit with test vector T
foreach bridging fault (BF )
if the PBF for BF places an error on a wire (W ) and meets the TGT
if a previous simulation of a fault on W can be used
use previous simulation data
else
simulate fault on W introduced by fault block
if the fault introduced by the fault block is detectable
accept test T for this fault: BF is detected
record results of simulation of fault on W for future use

Figure

9: Pseudo-code for Wire Memory bridging fault simulation
event queue if its faulty and fault-free values differ in any bit-position-regardless of whether the
difference represents a value propagated from the fault on the first wire or the second wire. If the
two bridged wires share a significant number of downstream components, the number of individual
component simulations can be as little as half the number required by simulators that associate
bridging faults with wires.
For purposes of comparison, we implemented not only the new method of bridging fault simu-
lation, but also the method of Abramovici and Menon, and we used each of them in the Nemesis
ATPG system. Comparing the two simulation methods, there are a number of reasons for the
greater success of the Wire Memory method. The ability to abort simulations when no errors are
moving forward, which can only be done in the Wire Memory method, saves a great deal of time.
Also, the data structures needed for the Wire Memory method were easily integrated into a system
(such as Nemesis) that treats many different types of faults (such as bridge, I DDQ , stuck-at, and
delay) in a similar fashion. Data structure manipulation in the older method is more complex
because each fault appears twice (once for each wire that may carry an error).
3.2 Test pattern generator
There are two types of feedback faults: given a fault, if every path from the back wire to a
primary output goes through the front wire, the fault is a feedback fault with no fanout; If some but
foreach feedback bridging fault
front wire fault-free
if test generation is successful (sequential behavior must be prevented via the TGT)
FBF is covered, move to the next fault
else front wire fault-free
if test generation is successful (sequential behavior must be prevented via the TGT)
FBF is covered, move to the next fault
else if FBF is a feedback fault with no fanout
FBF is undetectable, move to the next fault
else back wire fault-free
if test generation is successful (oscillation must be prevented via the TGT)
FBF is covered, move to the next fault
else back wire fault-free
if test generation is successful (oscillation must be prevented via the TGT)
FBF is covered, move to the next fault
else FBF is undetectable

Figure

10: Pseudo-code for ATPG for bridging faults that may induce feedback
not all of the paths from the back wire to a primary output go through the front wire, the fault is
a feedback fault with fanout. It is a consequence of the Test Guarantee Theorem that a feedback
fault with no fanout can only be detected with the error placed on the front wire. Pseudo-code for
the feedback bridging fault test generator is shown in Figure 10.
Each attempt to generate a test for a bridging fault enforces constraints on fault-free values for
all wires, on faulty values for wires in between the bridge and a circuit output, and, for feedback
bridging faults, on feedback-influenced values [9].

Figures

11 through 14 show a sample bridging fault and demonstrate how Nemesis will show that
there is no test that will detect the fault. Notice that the inversion parity between the back and front
wire can change depending on circuit input values. This makes it crucial to identify both potential
oscillation and sequential behavior for the same fault. The Nemesis ATPG system uses Boolean
satisfiability, so constraints are not enforced in a particular order [17]. However, for illustration of
each of the four test generation attempts, first initial constraints are shown, then derived activation,
justification, and propagation values, and finally-if they are required-constraints having to do
with the feedback-influenced values.
First,

Figure

11 shows the attempt to generate a test such that the fault-free value of the front
wire is 0 and the fault block output is 1. The first drawing shows the constraints imposed by the
values in the attempted test, and the second drawing shows the direct implications of these values,
including the value that the application of the PBF to the fault-free circuit values would place on
the bridge (the value shown on the dashed line in the illustration). It is not possible to generate
a test because the fault-free circuit values cause the PBF to assign a 0 to the bridge, and the first
attempt requires a test with a 1 on the bridge. Similarly, Figure 12 shows the attempt to generate
a test such that the fault-free value of the front wire is 1 and the fault block output is 0. Once again
the first drawing shows the constraints imposed by the values in the attempted test, and the second
drawing shows the direct implications of these values, including the value that the application of

Figure

11: Front wire stuck-at 11/01/00
0/000

Figure

12: Front wire stuck-at 0
the PBF to the fault-free circuit values would place on the bridge. It is not possible to generate a
test here because the fault effect cannot be propagated through the final NAND gate.
The test cannot be generated with an error on the front wire. The test generation process must
continue because the fault is a feedback with fanout fault, and the fault effect can be propagated
to either circuit output using paths that do not include the front wire.

Figure

13 shows the attempt to generate a test such that the fault-free value of the back wire
is 0 and the fault block output is 1. Once again the first two drawings show the initial constraints
and the direct implications of the constrained values, and the added third drawing shows the results
of applying the PBF the second time to the feedback-influenced values, as required by the Test
Guarantee Theorem. This second PBF application causes the fault block output to change, which
causes the test to be rejected. Figure 14 shows the attempt to generate a test such that the fault-free
value of the back wire is 1 and the fault block output is 0. The three drawings are analogous to
those in Figure 13, and again a test cannot be found because, just as in Figure 13, the circuit has

Figure

13: Back wire stuck-at 1
the potential for oscillation. Because each of the four categories of potential tests for this bridging
fault is unworkable, the fault is untestable for the given PBF.
The Test Guarantee Theorem fits into an ATPG framework elegantly because it allows the
check for feedback or sequential invalidation to occur as a requirement of test generation and not
as a postprocessing consistency check.
4 Experimental Results
This section presents the results for the UCSC system for testing bridging faults. The two-component
PBFs were obtained by SPICE simulation. Bridge voltages were converted to digital
values by using the logic threshold of the smallest inverter in the MCNC cell library.
We compare the performance of the Nemesis bridging fault ATPG system to that of the Nemesis
single stuck-at fault ATPG system, and we compare the performance of our simulator to that of
our implementation of the Abramovici and Menon simulator. All times given are CPU times in
seconds on a Digital Equipment Corporation Decstation 5000/240.

Table

2 shows the number of PBFs, the number of stuck-at faults, the number of total realistic
bridging faults, the number of bridging faults with no feedback, and the number of feedback bridging
faults for the layouts of the ISCAS-85 benchmark circuits using the MCNC cell library. There are
three to nine times as many bridging faults as there are stuck-at faults for the given circuits, so
an efficient bridging fault ATPG system might take up to 10 times as long to produce tests for all

Figure

14: Back wire stuck-at 0
realistic bridging faults as to produce tests for all single stuck-at faults. The number of PBFs is
small compared to the number of faults, and in fact, only 309 different PBFs were used in all ten
of the MCNC layouts of the ISCAS-85 benchmarks.
The number of feedback bridging faults is a significant percentage of the number of bridging
faults: Useful fault coverage could not be achieved without accurate tests for the feedback bridging
faults.

Table

3 compares the new Wire Memory simulation algorithm with the Abramovici and Menon
simulation algorithm for PPSFP random test simulation. The comparison is fair, because any of
the optimizations that can possibly be applied to advantage for the Abramovici and Menon method
is included in our implementation of their method. The Wire Memory method is almost always
faster, and the improvement becomes more striking as the size of the circuits increase. Neither
method uses much memory: either implementation can run all of the benchmarks on a machine
with megabytes of RAM.

Tables

4 and 5 show the number of bridging faults covered, proved untestable, or aborted by
the bridging fault and single stuck-at fault ATPG systems, as well as the time in seconds necessary
to achieve the reported coverage 1 . For all ten circuits, the bridging fault ATPG system takes
an average of 4=3 the time per fault as the single stuck-at system takes, but for most circuits
1 The number of single stuck-at faults for each circuit differs from that reported in the literature because the
MCNC versions of the ISCAS-85 circuits are technology-mapped implementations using standard cells. Note that
not only will the number of single stuck-at faults change, but the number of untestable faults will also be different.
Circuit Stuck-At PBFs Bridging faults
Total No Feedback Feedback

Table

2: Number of faults and PBFs for each circuit
Time in Seconds
Circuit Faults covered A & M Wire Mem.
C1908 4,684 15.3 13.7
C7552 53,271 435.2 287.2

Table

3: Nemesis random parallel simulation
(including four of the five largest circuits), the time per processed bridging fault is less than the
time per processed single stuck-at fault. This shows that realistic bridging fault ATPG is an efficient
and valuable complement to single stuck-at ATPG.

Table

4 also shows the fault coverage and bridging defect coverage for the benchmark circuits.
For the ten circuits, Nemesis covers an average of 99.39% of the faults and 99.33% of the defects.
Nemesis fails to generate tests for or prove untestable very few of the defects. For example, for the
C0432, it generated tests for 98.32% of the realistic defects, it proved 1.62% of the realistic defects
combinationally untestable, and it failed to process 0.06% of the defects. But many of these faults
can still be tested. For example, 1.68% of realistic defects for the C0432 were untestable or were
not processed. The addition of only five I DDQ test patterns will leave only 0.19% of the realistic
defects for the C0432 untested (the remaining faults are both logically untestable and untestable
via detecting excess I DDQ ). This is fewer than one half of the I DDQ test patterns that would be
required to test all of the realistic bridging faults.
The fault coverage and the defect coverage generally track each other, but they can differ by
significant amounts. Using the C7552 as an example, the difference between 99.46% covered faults
Circuit Number of Faults Time % Coverage
Covered Untestable Aborted (Secs.) Faults Defects

Table

4: Bridging fault test pattern generation coverage
Circuit Number of Faults Time
Covered Untestable Aborted (Secs.)

Table

5: Single stuck-at test pattern generation coverage
and 98.94% could make a significant difference in DPM estimation [21].
5 Summary and conclusions
The integrated circuit industry changes at a rapid pace, but one element that does not change is
the need for quality. The bridging fault model offers additional rigor to the manufacturing test
process by modeling the behavior of faults that are likely to occur. In this paper, we have presented
the Primitive Bridge Function-a characteristic function describing the behavior of bridged
components; we have provided a theoretical foundation for test pattern generation that correctly
handles all bridging faults; we have described and reported on the performance of a test pattern
simulator that is faster than previously reported simulators and that accurately simulates all realistic
bridging faults; and finally, we have described and reported on the performance of our complete
ATPG system, which generates tests that cover at least 98.32% of the realistic bridging defects
and an average of 99.33% of the realistic bridging defects in our layouts of the MCNC ISCAS-85
benchmark circuits. The time it takes to generate these tests is comparable to the time necessary to
generate single stuck-at test sets for the same circuits. We have shown ATPG for realistic bridging
faults to be viable and significant.
Future experimentation will involve different and more accurate methods for calculating PBFs-
methods that address indeterminate logic values and differing downstream gate input thresholds [5].
We are also investigating shorts on the inside of the cell [7] and bridging fault diagnosis [10].



--R

A practical approach to fault simulation and test generation for bridging faults.
Testing for bridging faults (shorts) in CMOS circuits.
Deriving Accurate Fault Models.
Accurate modeling and simulation of bridging faults.
Fault model evolution for diagnosis: Accuracy vs precision.
A neutral netlist of 10 combinatorial benchmark circuits and a target translator in FORTRAN.
Testing CMOS logic gates for realistic shorts.
Bridge fault simulation strategies for CMOS integrated circuits.
Generating test patterns for bridge faults in CMOS ICs.
Diagnosis of realistic bridging faults with single stuck-at information
Physically realistic fault models for analog CMOS neural networks.
Test pattern generation for realistic bridge faults in CMOS ICs.
A CMOS fault extractor for inductive fault analysis.
EPROOFS: a CMOS bridging fault simulator.
Carafe: An inductive fault analysis tool for CMOS VLSI circuits.
Carafe: An inductive fault analysis tool for CMOS VLSI circuits.
Test pattern generation using Boolean satisfiability.
Biased voting: a method for simulating CMOS bridging faults in the presence of variable gate logic thresholds.
IEEE Transactions on Computers
An accurate bridging fault test pattern generator.
Limitations in predicting defect level based on stuck-at fault coverage
Fast and accurate CMOS bridging fault simulation.
Inductive fault analysis of MOS integrated circuits.
Fault simulation for structured VLSI.
Defect level as a function of fault coverage.
--TR

--CTR
Ilia Polian , Piet Engelke , Michel Renovell , Bernd Becker, Modeling Feedback Bridging Faults with Non-Zero Resistance, Journal of Electronic Testing: Theory and Applications, v.21 n.1, p.57-69, January   2005
Baradaran Tahoori, Using satisfiability in application-dependent testing of FPGA interconnects, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
Application-dependent testing of FPGAs, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.14 n.9, p.1024-1033, September 2006
Baradaran Tahoori, Application-Specific Bridging Fault Testing of FPGAs, Journal of Electronic Testing: Theory and Applications, v.20 n.3, p.279-289, June 2004
M. Favalli , C. Metra, Bridging Faults in Pipelined Circuits, Journal of Electronic Testing: Theory and Applications, v.16 n.6, p.617-629, Dec. 2000
Donald Shaw , Dhamin Al-Khalili , Come Rozon, Automatic generation of defect injectable VHDL fault models for ASIC standard cell libraries, Integration, the VLSI Journal, v.39 n.4, p.382-406, July 2006
realistic faults;test pattern generation;fault simulation;fault models;bridging faults