Hierarchical physical defect reasoning in digital circuits/Hierarhiline fuusikaliste defektide analuus digitaalskeemides.
Kostin, Sergei ; Ubar, Raimund ; Raik, Jaan 等
1. INTRODUCTION
Rapid advances in the areas of nanoscale electron technology and
design automation tools enable engineers to design larger and more
complex integrated circuits. On the other hand, the increasing
integration densities pose severe problems with respect to the quality
assurance. The quality and reliability of microelectronic circuits
depend essentially on the efficiency of debug and diagnosis of failures
in circuits. Traditional approaches to diagnosis of digital circuits are
based on gate-level models [1-4]. However, due to the continuous
increasing of the gate count in circuits under diagnosis, the gate-level
methods are becoming less efficient and obsolete.
Two main trends can be observed when searching solutions for the
problems of testing and diagnosis: defect-orientation, and high-level
modelling [5]. The trend towards high-level modelling helps us to cope
with the complexity, but moves us even more away from the real life of
physical defects and, hence, from accuracy of diagnosis. To handle
adequately defects in nanoscale technologies, new fault models and
defect-oriented diagnosis methods should be used. But the
defect-orientation is increasing again the complexity. To get out from
the deadlock, these two opposite trends--high-level modelling and
defect-orientation--should be combined into hierarchical approaches.
The classical fault diagnosis algorithms follow two different
paradigms: cause--effect and effect--cause analysis [6]. The
cause-effect approach begins with mapping the causes of failure to a
specific fault type e.g. stuck-at fault (SAF) model. Then, the fault
tables or fault dictionaries are built by fault simulation. Once the
fault dictionary is available, the effect (or syndrome) of the failing
chip is analysed using dictionary look-up. This approach is also called
fault-dictionary based paradigm or combinational diagnosis approach [7].
However, as designs grow in complexity, dictionary-based fault diagnosis
approaches are becoming infeasible due to prohibitively large dictionary
sizes. Effect--cause approach looks at the failing outputs and starts
reasoning on the logic or topological structure of the circuit to be
diagnosed. Because of the sequential character of reasoning, this
approach is called also sequential fault diagnosis.
Traditional approaches to the cause--effect fault diagnosis lay on
the stuck-at fault model. Many researchers have focused on developing
new fault models for particular types of failure mechanisms like signal
line bridges [6,8], transistor stuck-opens [9,10] or failures due to
changes in circuit delays [11]. Another trend has been to develop
general fault modelling mechanisms and corresponding test tools that can
effectively analyse arbitrary fault types like in [12] where D-cubes are
used to model any arbitrary change in the logic function of a circuit
block. A generalization of this approach has been found in the input
pattern fault model [13] and in the pattern fault model [14], which can
model any arbitrary change in the logic function of a circuit block,
where a block is defined to be any combinational subcircuit, described
at any level of the design hierarchy.
A similar pattern-related fault modelling approach, called
functional fault model, was proposed earlier in [15] for the
module-level fault diagnosis in combinational circuits based on solving
systems of Boolean differential equations. The functional or pattern
fault model allows an arbitrary set of signal lines to be grouped into
activation conditions for a single fault site, allowing a variety of
fault types to be modelled. The functional faults can be either static
or dynamic [16].
In [17], a similar model, called conditional faults, was proposed
for test generation purposes, and in [18] for diagnosis purposes. A
conditional fault allows additional signal line objectives to be
combined with the detection requirements of a particular fault or
physical defect.
The main objective of this work is to carry out the fault diagnosis
at two levels (Fig. 1). To reduce the complexity of the diagnosis
problem we represent the circuit as a network of modules whereas the
modules can be arbitrary gate subnetworks. The task of diagnosis is
considered as a task to locate faulty modules in the network of modules
by using module-level fault dictionaries. The module size can be decided
as the trade-off between the size of the faulty subcircuit to be located
at the higher level and the size of the fault dictionary. Arbitrary and
multiple faults in the module are allowed. However, it is assumed that
no more than a single module is faulty at a time.
[FIGURE 1 OMITTED]
As the result of the fault diagnosis at the higher level, a faulty
module or a subset of suspected faulty modules in the tested circuit is
located. In the next step, this subset will be suppressed by a special
defect reasoning based on using the functional fault (conditional SAF)
model.
At the lower level, the defect location in the suspected faulty
module will be determined. For this purpose we need the defects
dictionaries for suspected modules. In the case when the modules
represent library components used during design, we can precalculate the
dictionaries for each library component beforehand and store the
dictionaries in the library as well. Otherwise, the defects libraries
should be created by simulation ad hoc.
The main objective of this work is to apply the cause-effect fault
diagnosis hierarchically at two levels; first, in the module network to
locate the faulty module, and thereafter, to locate a defect inside the
faulty module by defect reasoning.
At the high level, we use the fault dictionary where instead of
enumerating all the possible fault cases (or defects), we list only the
modules as potential faulty items in the circuit. This helps to cope
with the complexity of the fault dictionaries. At the lower level, two
approaches may be used. In case when the modules represent library
complex gates, we use the low-level defect dictionaries to diagnose the
suspected defect(s). In case when the modules represent logic
subcircuits not described in the component libraries, either low-level
effect-cause reasoning can be carried out to locate the defects, or the
defects libraries should be created for the low-level diagnosis purpose.
The rest of the paper is organized as follows. In Section 2 we
describe the general flow of fault diagnosis. Section 3 presents the
method of high-level fault diagnosis based on modules dictionaries. In
Section 4, we describe the functional fault model. A defect-reasoning
method for pruning the set of suspected faulty modules is explained in
Section 5. Section 6 presents the ideas of the low-level defect
diagnosis, and in Section 7, we describe the experimental results.
Section 8 concludes the paper.
2. GENERAL DESCRIPTION OF THE METHOD
In this paper, we propose a hierarchical approach for the fault
diagnosis in combinational circuits. The high-level model of a circuit
is presented as a network of modules. The modules may be library
components (complex gates) and/or arbitrary single-output logic
subcircuits. A high-level fault dictionary is generated for the given
test where for each test pattern it will be shown in which modules the
defects may be detected by this pattern. The task of the high-level
diagnosis is to determine the faulty module or a subset of candidate
faulty modules.
In the first step, by the procedure of the cause--effect diagnosis,
based on using the high-level fault dictionary, a subset of candidate
modules, suspected as faulty, is determined. On the next step, by using
effect--cause high-level module reasoning, the initial subset of
candidate faulty modules will be suppressed (Fig. 2). The high-level
module reasoning is defect oriented, however the direct defect analysis
is avoided. The defects are modelled indirectly by using the functional
fault model, which is represented by pairs of SAF and defect conditions
[15,18]. In the process of reasoning, only the defect conditions are
considered, which allows to avoid dealing directly with the whole huge
list of defects in the circuit.
Low-level fault diagnosis is carried out in the modules determined
during the high-level reasoning as faulty. For low-level diagnosis
purposes, the modules are represented by sets of local test patterns,
which are treated as conditions for activating physical defects in
modules. This diagnostic information is captured in the form of defect
dictionaries and is stored in the component libraries. Using
pre-generated defect dictionaries, low-level cause-effect reasoning is
carried out to locate the defects in the modules. If the defect location
with the help of defect dictionaries is not possible, or if no
dictionaries for given modules are available, effect-cause low-level
defect reasoning should be carried out to locate the defects in
suspected modules.
[FIGURE 2 OMITTED]
3. CAUSE-EFFECT HIGH-LEVEL FAULT DIAGNOSIS
Consider a combinational circuit C, synthesized as a network of
modules with a single output (library complex gates or arbitrary
sub-circuits) with a set of primary outputs OUT, a set of primary inputs
IN, and a set of internal nodes INT. The network C consists of a set of
modules M where each module [m.sub.i] [member of] M has an output node
[y.sub.i] [member of] OUT [union] INT and a set of input nodes [X.sub.i]
[member of] IN [union] INT.
The circuit represents a graph C = (M, [GAMMA]), where the nodes
correspond to the modules m [member of] M, and [GAMMA] is a relation on
M, where [GAMMA] (m) [subset] M denotes the successor nodes of m, and
[[GAMMA].sup.-1] (m) [subset] M is the set of the predecessor nodes of
m. For all the output nodes [m.sub.j] [member of] M, j: [y.sub.j]
[member of] OUT, we have [GAMMA]([m.sub.j]) = [empty set]. For all the
input nodes [m.sub.j] [member of] M, which represent the modules with
only primary inputs j : [X.sub.j] [subset] IN, we have [[GAMMA].sup.-1]
([m.sub.j]) = [empty set].
Example 1. An example of a combinational network C is presented in
Fig. 3, where to each network component (functional block F) a module
corresponds. The graph C = (M, [GAMMA]) of the network is depicted in
Fig. 4, where are shown modules that correspond to respective functional
blocks (e.g. [F.sub.1] [right arrow] 1) and the connections between the
modules (e.g. [F.sub.1] is connected to [F.sub.4] and [F.sub.7]). The
task of the high-level fault diagnosis is to locate the faulty module if
the testing of the circuit has been failed.
In general case, there will be no restrictions to the fault types
inside the modules (some restrictions considered later may be introduced
to simplify the fault diagnosis at the cost of worse diagnostic
resolution).
The first phase of the high-level fault diagnosis is carried out in
the network of modules according to the cause--effect approach by using
its pre-generated fault dictionary. The module-level fault dictionary is
represented as the matrix D = [parallel] [d.sub.ij] [parallel], where i
denotes th number of test pattern, and j denotes the module [m.sub.j]
[member of] M (a subcircuit or a library component in the network). We
say [d.sub.ij] = 1 if the test pattern [t.sub.i] may detect a faulty
signal on the output [y.sub.j] of the module [m.sub.j].
[FIGURE 3 OMITTED]
Let [M.sub.i] = {[m.sub.j]} [subset] M be the subset of modules
corresponding to the i-th row of the matrix D, so that [m.sub.j] [member
of] [M.sub.i] if [d.sub.ij] = 1.
[FIGURE 4 OMITTED]
Let us have a test set T to be used for fault diagnosis. Partition
the set T in accordance with the results of test experiment into two
subsets: T = [T.sub.F] [union] [T.sub.P], where [T.sub.F] [intersection]
[T.sub.P] = [empty set], [T.sub.F] is the subset of test patterns, which
failed during the test, and [T.sub.P] is the subset of test patterns,
which passed. Denote by the vector
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
the subset of all modules suspected as faulty on the basis of
failing subset of test patterns [T.sub.F], and by the vector
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
the subset of tested modules, which have shown correct behaviour on
the basis of the subset of passed test patterns [T.sub.P].
Consider now the subset of modules [M.sup.*] = [M.sub.F] -
[M.sub.P]. It is easy to understand that if [M.sup.*] [not equal to]
[empty set] then the modules in [M.sup.*] should be suspected as faulty
to explain the failing of test patterns [T.sub.F].
Consider another subset of modules determined as [M.sup.1.sub.cond]
= [M.sub.F] [intersection] [M.sub.P]. All these modules in
[M.sup.1.sub.cond] should be treated as ambiguous, because they may
explain the failing of test patterns [T.sub.F], however, not
necessarily. Let us call this subset as conditionally suspected modules
after the first phase of high-level fault diagnosis. The total subset of
modules suspected as faulty after the first phase of high-level
diagnosis is determined as [M.sup.1] = [M.sup.*] [union]
[M.sup.1.sub.cond].
Example 2. Table 1 represents an example of the module-level fault
dictionary D.
Assume the test patterns [t.sub.1] and [t.sub.2] failed during the
test, e.g., [T.sub.F] = {[t.sub.1], [t.sub.2]}, and other three test
patterns [T.sub.P] = {[t.sub.3], [t.sub.4], [t.sub.5]} passed. Hence,
[M.sub.F] = {[m.sub.1], [m.sub.3], [m.sub.6], [m.sub.7], [m.sub.8]}, and
[M.sub.P] = {[m.sub.2], [m.sub.3], [m.sub.4], [m.sub.5], [m.sub.6],
[m.sub.7], [m.sub.8]}. On this basis, as the result of the first phase
of high-level fault diagnosis, we get: [M.sup.*] = {[m.sub.1]} and
[M.sup.1.sub.cond] = {[m.sub.3], [m.sub.6], [m.sub.7], [m.sub.8]}. The
modules [m.sub.3], [m.sub.6], [m.sub.7], [m.sub.8] remain conditionally
suspected as faulty.
In this phase of high-level diagnosis we cannot use the information
from the passed patterns [T.sub.P] = {[t.sub.3], [t.sub.4], [t.sub.5]}
to reduce the subset of suspected faulty modules in [M.sup.1.sub.cond],
because we do not know which defects have been tested in modules
[M.sup.1.sub.cond] during the test sets [T.sub.F] and [T.sub.P].
4. DEFECT REASONING IN MODULES BY USING THE CONDITIONAL SAF MODEL
In this Section we describe how the functional fault model,
consisting of pairs of SAF and defect conditions, can be used for
high-level defect reasoning in suspected faulty modules.
Consider a module m [member of] M, which is represented by a
Boolean function y = f(X), X = ([x.sub.1], [x.sub.2], ..., [x.sub.n]).
Introduce a symbolic Boolean variable [DELTA] for representing a given
defect in the module, which converts the fault free function f into
another faulty function [f.sup.[DELTA]]. Construct for this defect a
generic parametric function
[y.sup.*] = [f.sup.*]([x.sub.1], [x.sub.2], ..., [x.sub.n],
[DELTA]) = [bar.[DELTA]]f [disjunction] [DELTA][f.sup.[DELTA]]
to model the defect of the module m as a function of the defect
variable [DELTA], which describes jointly the behaviour of the module
for both, fault-free and faulty cases. For the faulty case, [DELTA] = 1,
and for the fault-free case, [DELTA] = 0, i.e. [y.sup.*] =
[f.sup.[DELTA]] if [DELTA] = 1, and [y.sup.*] = f if [DELTA] = 0. The
solutions [W.sub.y]( [DELTA]) of the Boolean differential equation
[partial derivative][f.sup.*]/[partial derivative][DELTA] = 1 (1)
describe the set of conditions (input signals of the module) which
activate the defect [DELTA] to produce an error on the output line y of
the module. To find the conditions [W.sub.y] ([DELTA]) for a given
defect [DELTA], we have to create the corresponding logic expression for
the faulty function [f.sup.[DELTA]], either by logical reasoning or by
carrying out defect simulation directly, or by carrying out real
experiments to learn the physical behaviour of different defects. The
described method represents a general approach to map an arbitrary
transistor level physical defect inside the module m to the higher logic
(or module) level.
Example 3. As an example, assume there is a short inside the
transistor circuit in Fig. 5, described by the function
y = f (X) = [x.sub.1] [x.sub.2] [x.sub.3] [disjunction] [x.sub.4]
[x.sub.5].
The short changes the function of the circuit as follows:
y = [f.sup.[DELTA]] (X) = ([x.sub.1] [disjunction]
[x.sub.4])([x.sub.2][x.sub.3] [disjunction] [x.sub.5]).
Using the defect variable [DELTA] for the short, we create a
generic Boolean differential equation and solve it as follows:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].
From this equation three possible solutions follow: 10x01, 1x001,
01110, where x is don't care value. Each of them can be used as a
test pattern for the given short, or used as the defect condition for
SAF at the output y. According to the definition of the functional fault
model for the defect [DELTA], we have [W.sub.y] ([DELTA]) =
{10x01,1x001, 01110}.
[FIGURE 5 OMITTED]
We call the full set of conditions [W.sub.y] = {[W.sub.y]
([DELTA])} as the functional fault model to represent all the physical
defects through functional deviations in the behaviour of the module m:
a physical level defect [DELTA] produces a higher logic level erroneous
signal on the module output y if [W.sub.y] ([DELTA]) = 1. By using the
set of conditions [W.sub.y], it is possible to map the defects from
lower physical level to higher logic level for fault simulation purposes
or vice versa, to map the faulty logic signals from the module level to
physical defects for fault diagnosis purposes. If the modules of the
circuit represent standard library components (e.g. complex gates) the
described analysis for finding conditions should be made once for all
library components, and the sets of calculated conditions [W.sub.y] will
be included in the form of defect dictionaries into the library of
components.
5. EFFECT--CAUSE HIGH-LEVEL FAULT REASONING
We define the effect-cause high-level fault reasoning as the second
phase of high-level fault diagnosis as follows. We take the set of all
conditional candidate faulty modules [M.sup.1.sub.cond] = [M.sub.F]
[intersection] [M.sub.P], found in the first high-level diagnosis phase,
and create the sets of fault conditions [X.sub.F,i] for all modules
[m.sub.i] [member of] [M.sup.1.sub.cond], suspected conditionally. The
set [M.sup.1.sub.cond] can be interpreted as the effects evoked locally
by the possible defects in the modules m [member of] [M.sub.F]
[intersection] [M.sub.P]. In these suspected modules we have to carry
out the indirect defect reasoning either to determine the possible
defect causes or to remove the not faulty modules from suspicion. The
task of the second phase of high-level fault diagnosis is to locate the
faulty module or to reduce the set of suspected faulty modules as much
as possible.
Denote by [X.sub.ij] the local input condition of the module
[m.sub.i] at the test pattern [t.sub.j]. Let us group all these input
conditions for all the modules in such a way that [X.sub.F,i] contains
all the local input conditions of the module [m.sub.i] during the test
patterns, which tested the module and failed, and [X.sub.P,i] contains
all the local input conditions of the module [m.sub.i] during the test
patterns, which tested the module and passed.
Each condition [w.sub.F] [member of] [X.sub.F,i], so that [w.sub.F]
[member of] [W.sub.i] ([DELTA]), refers to a defect [DELTA], which may
have been detected by the test patterns in [T.sub.F], and therefore
should be suspected because all the test patterns in [T.sub.F] failed.
On the other hand, each input condition [w.sub.P] [member of]
[X.sub.P,i,] so that [w.sub.P] [member of] [W.sub.i]([DELTA]), refers to
a defect [DELTA], which should have been detected by the test patterns
in [T.sub.P]. However, since all the test patterns in [T.sub.P] passed,
the defect [DELTA] cannot be any more suspected.
From the above reasoning it results that only these defects in the
module [m.sub.i], which are activated by the conditions w [member
of]([X.sub.F,i] - [X.sub.P,i]) [intersection] [W.sup.f.sub.i], may be
suspected. Hence, a module [m.sub.i] [member of] [M.sup.1.sub.cond] can
be suspected as faulty only if
([X.sub.F,i] - [X.sub.P,i]) [intersection] [W.sup.f.sub.i][not
equal to][empty set]. (2)
The reasoning proceeds in the following way. We delete from all
conditions [X.sub.F,i], where [m.sub.i] [member of] [M.sup.1.sub.cond],
the conditions [X.sub.P,i], trying to suppress the set
[M.sup.1.sub.cond]. The result of the second phase of high-level fault
diagnosis will be the set of conditionally suspected faulty modules
[M.sup.2] = [M.sup.*] [union] [M.sup.2.sub.cond] where
[M.sup.2.sub.cond] [subset or equal to] [M.sup.1.sub.cond], and for all
[m.sub.i] [member of] [M.sup.2.sub.cond] the condition (2) is valid.
Example 4. Consider again the example in Table 1, where the first
two test patterns failed during the test experiment, and the other three
passed. Let the module [m.sub.3] had the local input vector [X.sub.13] =
(1011) during the test pattern [t.sub.1], which tests the module
according to Table 1. We assume here that the module has 4 input lines.
Since [t.sub.1] failed, it means that in the module [m.sub.3], a defect
[DELTA], activated by the conditions [w.sub.F] = (1011) [member of]
[W.sub.3]([DELTA]) on the inputs of the module, should be suspected. On
the other hand, let the same module had on its inputs the same condition
[w.sub.P] = [w.sub.F] = (1011) during the test pattern [t.sub.4] , which
tested the module [m.sub.3] as well, but passed. Since the test pattern
[t.sub.4] activated the same defect [DELTA], which was under suspicion
after the test pattern [t.sub.1], there is a contradiction, and the
defect [DELTA] cannot be present. So, we can remove the module [m.sub.3]
from the set of suspected modules [M.sup.1.sub.cond] = {[m.sub.3],
[m.sub.6], [m.sub.7], [m.sub.8]}. After such a procedure of the indirect
effect-cause reasoning of defects on the module level, we may get in
ideal case [M.sup.2.sub.cond] = [empty set]. In this case, the result of
the high-level fault diagnosis show that we should suspect a single
module, [M.sup.2] = [M.sup.*] = {[m.sub.1]}, as faulty.
6. LOW-LEVEL FAULT DIAGNOSIS
Low-level fault diagnosis is carried out in the modules determined
during the high-level reasoning as faulty. It may be carried out either
by cause--effect diagnosis, based on the defect dictionaries
pre-computed for the library components, or by effect--cause diagnosis
inside the modules if the defect libraries are not available.
Consider as an example the fault dictionary in Table 2 for a
library complex gate AND2,2/NOR2 [19] regarded as a module in the
circuit under diagnosis. In the table, 25 different defects (shorts
between inputs or internal nodes of the module) are considered with
corresponding names in column 2 and erroneous functions in column 3.
Other columns form the defect dictionary and correspond to the input
patterns of the 4-input module (given with decimal numbers). The entries
"1" in columns show which defects are tested by which
patterns.
Assume that as the result of the test experiment, we have found for
this particular module [m.sub.i] that [X.sub.F,i] = {[w.sub.3],
[w.sub.12]}, and [X.sub.P,i] = {[w.sub.0], [w.sub.5], [w.sub.8],
[w.sub.10], [w.sub.13], [w.sub.15]}. The input patterns not exercised
during the test are highlighted by grey colour. It is easy to see that
the defects [[DELTA].sub.2] and [[DELTA].sub.8] should be suspected as
present. For better diagnostic resolution, to distinguish these defects,
additional input patterns should be used for testing, e.g. [w.sub.7] or
[w.sub.11].
If no diagnosis is possible with using the defect dictionary, for
example, when the real existing defect is not covered by the dictionary,
or in the case when the defect dictionary for a module is missing, the
low-level effect--cause defect reasoning inside the module is needed.
This can be proceeded, for example, by the method of critical path
tracing.
7. EXPERIMENTAL DATA
Experiments were carried out with ISCAS'85, ISCAS'89 and
ITC'99 benchmark circuits (Table 3). The goal of the experimental
research was to evaluate the achievable high-level module-based
diagnostic resolution (Table 4) and to compare it with traditional
stuck-at fault based diagnostic resolution (Table 5). All the circuits
were presented as networks of modules, where as modules the fan-out free
regions (FFR) were selected. Three different types of tests were used
for evaluating the diagnostic resolution (Table 4): long pseudorandom
test sequences, short deterministic test sequences, and combination of
both sequences. The pseudorandom test sequences were generated by
LFSR-based test generator and optimized by selecting proper seeds and
polynomials. The LFSR was stopped when no useful test patterns were
found in a reasonable time. The pseudorandom test was selected to have
more test patterns for detecting the same fault with the goal to improve
the distinguishability of the faults. The deterministic test patterns
were synthesized by a genetic test generator. The quality of test
patterns, i.e. the maximum possible test coverage was not the target.
The goal of the paper was not to generate the best test sequences, but
rather to evaluate and compare the diagnosability, i.e. diagnostic
resolutions for two methods and for a given test sequence. To generate
diagnostic tests with as good as possible diagnostic resolution is the
task not considered in this paper.
In Table 3, the characteristic data of the benchmark circuits are
presented. In columns 2 to 4, the numbers of inputs, outputs and gates
are presented, respectively. Column 5 lists the number of modules, and
in column 6 the complexity reduction (Gates/Modules) in the module-level
model is shown compared to the gate-level network. The reduction on
average 5.7 times reflects the decrease of the complexity in fault
dictionaries in case of using FFR-modules instead of gates and SAF
lists.
In Table 4, the results of diagnostic resolution for three
different test types are presented. In each section, the characteristics
of tests are given (test length, and stuck-at fault coverage (SAF %)),
and the diagnostic resolutions (the number of suspected modules) after
the first and second phases of high-level diagnosis are depicted. The
diagnostic resolution can be improved by generating additional tests.
Table 5 shows the comparison results of the proposed module-level
diagnosis with traditional SAF-based diagnosis based on pseudorandom
tests for ISCAS'85 benchmark circuits. The diagnostic resolution at
the module level on average is similar to or even better than SAF-based
diagnostic resolution.
8. CONCLUSIONS
The main drawbacks of the traditional cause--effect diagnosis
methods are the dependence on the fault model and poor scalability of
fault dictionaries. We consider here fault diagnosis as the following
hierarchical procedure: first, to determine a set of suspected faulty
modules in a circuit by using high-level module-based fault dictionary
for the whole circuit, and second, to locate the physical defects in the
suspected faulty modules either by low-level dictionaries for library
components, or by defect reasoning in case of arbitrary subcircuits
defined as modules.
The proposed high-level fault diagnosis is fault independent, since
instead of specific faults, faulty structural components called modules
are localized. No restrictions to fault multiplicity inside the modules
are set.
On the other hand, the complexity of the proposed method compared
to the flat-level fault model based diagnosis is reduced. The size of
the high-level fault dictionary for the whole circuit depends linearly
only on the number of modules to be determined as faulty or not faulty,
and not on the number of possible faults or defects as traditionally.
The size of the modules, however, will be the trade-off between the
complexity of the high-level dictionary and the diagnostic resolution.
The complexity of the diagnosis problem was reduced on average 5.7
times for the case of FFR-based modules compared to gate-level
diagnosis. The diagnostic resolution in the module-based diagnosis was
similar to, or even better than in the case of SAF-based fault
diagnosis.
The high diagnostic resolution at the module level was achieved by
implementing a novel high-level effect--cause reasoning, based on the
concept of functional fault model (conditional SAF model). This concept
allowed to map physical defects from transistor level to the module
level, and to carry out indirect defect-based reasoning of faulty
modules at higher level. The same concept can be used to improve the
diagnostic exactness by low-level defect reasoning in the faulty
modules.
doi: 10.3176/eng.2011.3.02
ACKNOWLEDGEMENTS
The work has been supported by Estonian Science Foundation (grants
Nos 7068 and 7483), EC FP7 1ST project DIAMOND, ELIKO Development
Centre, Estonian IT Foundation "Tiger University", and
Research Centre CEBE, funded by EU Structural Funds.
Received 7 February 2011, in revised form 14 June 2011
REFERENCES
[1.] Venkataraman, S. and Drummonds, S. B. Poirot: Applications of
a logic fault diagnosis tool. IEEE Trans. Design Test Computers, 2001,
18, 19-29.
[2.] Huisman, L. M. Diagnosing arbitrary defects in logic designs
using single location at a time (SLAT). IEEE Trans. CAD, 2004, 23,
91-101.
[3.] Holst, S. and Wunderlich, H.-J. Adaptive debug and diagnosis
without fault dictionaries. In Proc. 12th European Test Symposium.
Freiburg, 2007, 7-12.
[4.] Rousset, A., Bosio, A., Girard, P., Landrault, C.,
Pravossoudovitch, S. and Virazel, A. Derric: A tool for unified logic
diagnosis. In Proc. 12th European Test Symposium. Freiburg, 2007, 13-20.
[5.] Wang, L. T., Wu, C. W. and Wen, X. VLSI test principles and
architectures. In Design for Testability. Elsevier, 2006.
[6.] Zhuo, L., Lu, X., Qiu, W., Shi, W. and Walker, D. M. H. A
circuit level fault model for resistive opens and bridges. In Proc. VLSI
Test Symp. Napa, CA, 2003, 379-384.
[7.] Liu, C. Compact dictionaries for fault diagnosis in scan-BIST.
IEEE Trans. Computers, 2004, 53, 775-780.
[8.] Acken, J. M. and Millman, S. D. Accurate modeling and
simulating of bridge faults. In Proc. Custom Integrated Circuits
Conference. San Diego, CA, 1991, 17.4.1-17.4.4.
[9.] Jain, S. K. and Agrawal, V. D. Modeling and test generation
algorithms for MOS circuits. IEEE Trans. Computers, 1985, C-34, 426-433.
[10.] Lee, H. K. and Ha, D. S. SOPRANO: An efficient automatic test
pattern generator for stuck open faults in CMOS combinational circuits.
In Proc. Design Automation Conference. Orlando, FL, 1990, 660-666.
[11.] Kristic, A. and Cheng, K. T. Delay Fault Testing for VLSI
Circuits. Kluwer, Boston, MA, 1998.
[12.] Roth, J. P. Diagnosis of automata failures: A calculus and a
method. IBM J. Res. Developm., 1966, 10, 278-291.
[13.] Blanton, R. D. and Hayes, J. P. On the properties of the
input pattern fault model. ACM Trans. Des. Automat. Electron. Syst.,
2003, 8, 108-124.
[14.] Keller, K. B. Hierarchical pattern faults for describing
logic circuit failure mechanisms. US Patent 5546408, Aug. 13, 1994.
[15.] Ubar, R. Detection of suspected faults in combinational
circuits by solving boolean differential equations. Automation and
Remote Control, 1980, 40, 1693-1703 (Plenum Publ. Corp., USA).
[16.] Ubar, R., Devadze, S., Raik, J. and Jutman, A. Fast fault
simulation for extended class of faults in scan-path circuits. In Proc.
5th IEEE International Symposium DELTA. Ho Chi Minh City, Vietnam, 2010,
14-19.
[17.] Mahlstedt, U., Alt, J. and Hollenbeck, I. Deterministic test
generation for non-classical faults on the gate level. In Proc. 4th
Asian Test Symposium. Bangalore, 1995, 244-251.
[18.] Holst, S. and Wunderlich, H.-J. Adaptive debug and diagnosis
without fault dictionaries. In Proc. 13th European Test Symposium.
Verbania, Italy, 2008, 199-204.
[19.] Ubar, R., Kuzmicz, W., Pleskacz, W. and Raik, J.
Defect-oriented fault simulation and test generation in digital
circuits. In Proc. 2nd International Symposium on Quality of Electronic
Design. San Jose, CA, 2001, 365-371.
Sergei Kostin, Raimund Ubar, Jaan Raik and Marina Brik
Department of Computer Engineering, Tallinn University of
Technology, Ehitajate tee 5, 19086 Tallinn, Estonia; {skostin, raiub,
jaan, brik}@pld.ttu.ee
Table 1. Module level fault dictionary
Modules
Test [m.sub.1] [m.sub.2] [m.sub.3] [m.sub.4]
[t.sub.1] 1 1
[t.sub.2] 1
[t.sub.3] 1
[t.sub.4] 1 1
[t.sub.5] 1
Modules
Test [m.sub.5] [m.sub.6] [m.sub.7] [m.sub.8]
[t.sub.1] 1 1 1
[t.sub.2] 1 1
[t.sub.3] 1 1 1
[t.sub.4] 1 1 1
[t.sub.5] 1 1 1
Table 2. Defect library for a gate AND2,2/NOR2 [19]
k Fault Erroneous function Local input test
[[DELTA].sub.k] [f.sup.[DELTA]k] patterns [w.sub.j]
0 1 2 3
1 A/C not((A*C)*(B+D))
2 A/D not((A*D)*(B+C))
3 A/N1 not(B*(not(A)+C+D)+C*D)
4 A/Q A*(not(C*D)) 1 1 1
5 A/gnd not(C*D)
6 A/vdd not(B+(C*D))
7 B/C not((B*C)*(A+D))
8 B/D not((B*D)*(A+C))
9 B/N1 not(A+C*D)
10 B/Q B*(not(C*D)) 1 1 1
11 B/gnd not(C*D)
12 B/vdd not(A+(C*D))
13 C/N1 not((A+B+D)*(A*B+not(C)+D)) 1
14 C/Q C*(not(A *B)) 1 1
15 C/gnd not(A*B)
16 C/vdd not(D+A*B) 1
17 D/N1 not(A*(B+C+notD)+B*notD 1
+not((A+B)*D)
18 D/Q D*(not(A*B)) 1 1
19 D/gnd not(A*B)
20 D/vdd not(C+A*B) 1
21 N1/Q not(A*B*C*D)
22 N1/gnd sa-0 for Q 1 1 1
23 N1/vdd not(C*D)
24 Q/gnd sa-0 at Q 1 1 1
25 Q/vdd sa-1 at Q 1
k Local input test patterns [w.sub.j]
4 5 6 7 8 9 10 11
1 1
2 1
3 1 1 1
4 1 1 1
5
6 1 1 1
7 1
8 1
9 1 1 1
10 1 1 1
11
12 1 1 1
13 1 1 1 1
14 1 1 1 1 1 1
15 1 1
16 1 1
17 1 1 1 1
18 1 1 1 1 1 1
19 1 1
20 1 1
21 1 1
22 1 1 1 1 1 1
23
24 1 1 1 1 1 1
25 1 1
k Local input test
patterns [w.sub.j]
12 13 14 15
1 1
2 1 1
3 1
4 1 1
5 1 1
6
7 1
8 1 1
9
10 1 1
11 1 1
12
13
14
15
16
17
18
19
20
21
22
23 1 1 1
24
25 1 1 1 1
Table 3. Characteristic data of benchmark circuits
Circuits Inputs Outputs Gates
c1908 33 25 1 394
c2670 233 140 2 075
c3540 50 22 2 784
c5315 178 123 4 319
c7552 207 108 5 795
s9234 247 250 5 597
s13207 700 790 12 441
s15850 611 684 14 841
s35932 1 763 2 048 32 624
b12_C 126 127 1 000
b14_C 277 299 19 491
b15_C 485 519 18 248
Average
Circuits Modules Complexity
reduction
c1908 248 5.6
c2670 430 4.8
c3540 378 7.4
c5315 633 6.8
c7552 920 6.3
s9234 1 263 4.4
s13207 2 014 6.2
s15850 2 202 6.7
s35932 7 343 4.4
b12_C 512 2.0
b14_C 2 708 7.2
b15_C 2 872 6.5
Average 5.7
Table 4. Diagnostic resolution for high-level module-based
diagnosis
Pseudorandom test
Average resolution
Test
Circuits length SAF, % Phase 1 Phase 2
c1908 4 420 99.48 86.61 1.42
c2670 22 682 88.65 223.86 3.45
c3540 9 631 95.54 69.63 2.53
c5315 1 793 98.89 213.23 1.85
c7552 24 337 94.08 287.55 2.60
s9234 29 873 86.21 271.31 6.32
s13207 29 694 96.81 781.34 10.53
s15850 29 360 90.99 669.44 10.50
s35932 168 90.81 3 748.42 63.85
b12_C 27 205 98.33 151.42 4.15
b14_C 29 388 88.86 249.80 18.29
b15_C 39 198 86.56 756.54 14.06
Deterministic test
Average resolution
Test
Circuits length SAF, % Phase 1 Phase 2
c1908 121 99.48 110.67 2.08
c2670 72 88.46 235.82 4.39
c3540 155 95.54 85.77 3.89
c5315 119 98.89 238.46 3.45
c7552 188 95.18 304.08 2.90
s9234 365 92.19 398.04 6.75
s13207 434 98.19 1 035.53 9.98
s15850 370 94.19 886.01 10.45
s35932 55 88.49 4 391.17 17.87
b12_C 155 99.77 239.68 5.05
b14_C 848 92.76 655.79 6.15
b15_C 498 88.77 1 069.16 17.67
Both tests
Average resolution
Test
Circuits length SAF, % Phase 1 Phase 2
c1908 4 541 99.48 86.17 1.41
c2670 22 754 90.36 221.05 3.24
c3540 9 786 95.54 69.62 2.51
c5315 1 912 98.89 212.00 1.84
c7552 24 525 95.52 285.78 2.58
s9234 30 238 92.23 205.01 4.50
s13207 30 128 98.19 701.69 7.60
s15850 29 730 94.22 557.32 4.12
s35932 223 90.81 3 554.58 6.45
b12_C 27 360 99.83 126.87 2.83
b14_C 30 236 95.69 531.72 2.69
b15_C 39 696 94.74 929.14 11.08
Table 5. Comparison of SAF- and module-based diagnosis
Test characteristics Diagnostic resolution
Circuits Length SAF, % SAF-based Module-based
c1908 4 420 99.48 2.9 1.4
c2670 22 682 88.65 4.1 3.5
c3540 9 631 95.54 2.2 2.5
c5315 1 793 98.89 2.2 1.9
c7552 24 337 94.08 2.6 2.6
