ack> Below is a cache of http://www.ece.ucdavis.edu/~halasaad/Data/css05.pdf. It's a snapshot of the page taken as our search engine crawled the Web.
The web site itself may have changed. You can check the current page or check for previous versions at the Internet Archive. Yahoo! is not affiliated with the authors of this page or responsible for its content.
EGFC: AN EXACT GLOBAL FAULT COLLAPSING TOOL FOR COMBINATIONAL CIRCUITS 1
Abstract
Fault collapsing is the process of reducing the number
of faults by using redundance and equivalence/dominance
relationships among faults. Exact fault collapsing can be
easily applied locally at the logic gates, however, it is
often ignored for most circuits, due to its high demand of
resources such as execution time and/or memory. In this
paper, we present EGFC, an exact global fault collapsing
tool for combinational circuits. EGFC uses binary deci-
sion diagrams to compute the tests for faults and conse-
quently achieve efficient global fault collapsing.
Experimental results show that EGFC reduces the number
of faults drastically with feasible resources.
Keywords
: Global fault collapsing, fault simulation, physi-
cal fault testing.
1 Introduction
To test a digital circuit, an automatic test pattern gener-
ation (ATPG) tool generates a test set that targets possible
physical faults. As the complexity of the digital circuit
increases, the possible number of physical faults increases
that consequently leads to a significant slow down of the
test generation process using the ATPG tool. One
approach for considerably reducing the length of the test-
ing process as well as producing compact test sets is fault
collapsing. Fault collapsing [1] is the process of reducing
the number of faults by using redundance, equivalence,
and dominance relationships among faults. Exact fault
collapsing can be easily applied locally at the logic gates;
however, it is often not feasible to apply it globally for
most circuits.
Several researchers have worked on fault collapsing.
An algorithm was presented in [2] that collapse all the
structurally equivalent faults in a circuit, plus many of the
functionally equivalent faults. Application of the algo-
rithm to the ISCAS-85 benchmark circuits [3] establishes
that identification of functionally equivalent faults is fea-
sible, and in some cases, they are a large fraction of the
faults in a circuit. However, the overall produced col-
lapsed fault list is still large in comparison to the global
collapsed fault list.
A graph-theoretic hierarchical fault collapsing method
was presented in [4][5] that can collapse faults in any large
cell-based circuit. Since functional analysis (equivalence
and dominance) is computationally expensive, it is only
applied to standard cells. As an example, consider the size
of the collapsed fault list for an exclusive-OR cell. Using
the method of [5], the collapsed fault list reduces to just
four faults when functional fault collapsing is considered.
With the traditional method of structural collapsing this
set contains 13 faults. When the exclusive-OR cell is used
to build an 8-bit adder circuit, the size of the collapsed
fault list produced by [5] reduces to 112 faults from a total
of 466 faults. Traditional structural fault collapsing would
have given a set of 226 faults. Although a significant
reduction is achieved here, the method assumes a hierar-
chical design with a good use of standard cells. Moreover,
the size of the produced collapsed fault list is still large in
comparison to the exact global collapsed fault list.
Efficient techniques for identifying functionally equiv-
alent faults in combinational circuits were presented in
[6]. The techniques are based on implication of faulty val-
ues, and evaluation of faulty functions in cones of domina-
tor gates of fault pairs. Experimental results show that
most of the equivalent fault pairs are identified. However,
this work does not aim at producing a small collapsed
fault list.
In our previous work [7], we have presented a prelimi-
nary method that produces a compact fault listan
approximation of the global collapsed fault list. Our
approximate global fault collapsing technique is based on
the simulation of random vectors. Experimental results
show that our method produced significant reduction in
the size of the collapsed fault list. However, our prelimi-
nary approximate global fault collapsing tool (a set of
scripts manipulating several academic CAD tools) turned
out to be resource intensive and memory hungry process.
Even with only 1,000 test vectors, many of the smaller
benchmark circuits required several hours to simulate.
EGFC: AN EXACT GLOBAL FAULT COLLAPSING
TOOL FOR COMBINATIONAL CIRCUITS
Hussain Al-Asaad
Department of Electrical & Computer Engineering
University of California
One Shields Avenue, Davis, CA 95616-5294
E-mail: halasaad@ece.ucdavis.edu 2
In this paper, we describe EGFC, an efficient tool for
exact global fault collapsing. We review fault collapsing in
Section 2 and present our efficient technique for exact
fault collapsing and the EGFC tool in Section 3. We
present some experimental results in Section 4 and finish
with our conclusions in Section 5.
2 Fault Collapsing
In physical fault testing, physical defects are abstracted
into a logical fault model. The most widely-used logical
fault model is the Single Stuck-Line (SSL) model [1].
Under this model, every single signal line can become per-
manently fixed (stuck) at a logical 1 or 0 value. The model
is simple and technology-independent. It represents a large
number of different physical faults, and tests derived for
SSL faults detect many design errors/faults. In this paper,
we only consider SSL faults; however, our method is
applicable to several other fault models.
Fault collapsing first removes redundant faults from the
fault list. A fault is redundant if there is no test that can
detect it. In other words, a fault is redundant if the faulty
function is the same as the correct function. Fault collaps-
ing then reduces the number of faults using two relation-
ships among faults: fault equivalence and fault dominance.
Two faults are considered equivalent if the faulty functions
(for the case of a single-output circuit) produced by the
two faults are equal. Alternatively, the two faults are
equivalent if they can be detected by the same tests. In this
case, there is no way to distinguish between the two faults.
For example, the SSL fault a stuck-at 0 represented by a/0
in Figure 1 is equivalent to the fault z/0. If two faults are
equivalent then one of the faults can be dropped from the
fault list since the detection of the other fault guarantees
the detection of the dropped fault.
A fault f is considered to dominate another fault g when
every test for g is also a test for f. For example, the fault z/
1 dominates the fault a/1 in Figure 1 since the only test
vector 01 for a/1 (shaded in the figure) is also a test for z/1.
If a fault f dominates a fault g, then the fault f can be
dropped from the fault list since the detection of g guaran-
tees the detection of f.
By applying fault collapsing to the AND gate in Figure
1, we can reduce the number of faults from six to three.
First, there are no redundant faults on the AND gate that
should be dropped. Second, the faults a/0 and b/0 are
dropped since they are equivalent to z/0. Finally, the fault
z/1 is dropped since it dominates both a/1 and b/1. The
collapsed fault list is thus {a/1, b/1, z/0}. A test set that
detects the faults in the collapsed list can be derived from
the table in Figure 1 as {01, 10, 11}. This test detects all
faults in the collapsed fault list and consequently all six
faults in the AND gate.
There are two approaches to fault collapsing: local and
global. The local fault collapsing method computes the
collapsed fault list for individual gates and then collects
the collapsed fault lists for the gates to form the overall
collapsed fault list for circuit. For example, by using fault
collapsing over the gates in the circuit shown in Figure 2,
we get the results shown in the figure. Both stuck at faults
on line s (called a stem since it branches to other lines)
need to be considered because s is not an input or output of
any gate. Using local fault collapsing, we combine the
faults on the gates to form the collapsed fault list for the
circuit as {s/0, s/1, s
3
/0, s
3
/1, a/1, b/1, s
2
/1, c/0, d/0, z/1}.
Therefore, by using local fault collapsing we were able to
reduce the fault list from 18 to 10.
Global fault collapsing is similar to local fault collaps-
ing, except that we perform the same process of fault col-
lapsing on the entire circuit as opposed to individual gates.
In other words, we look for equivalent and dominance
relationships among all faults in the circuit. For example,
to perform global fault collapsing for the circuit in Figure
2, we compute a table for all faulty functions (called a
fault table) as shown in Figure 2. It is simpler to start with
the local collapsed fault list since it has less faults than the
original fault list for the circuit. We then drop faults from