Hybrid Fault Simulation for Synchronous Sequential Circuits.
We present a fault simulator for synchronous sequential circuits that combines the efficiency of three-valued logic simulation with the exactness of a symbolic approach. The simulator is hybrid in the sense that three different modes of operationthree-valued, symbolic and mixedare supported. We demonstrate how an automatic switching between the modes depending on the computational resources and the properties of the circuit under test can be realized, thus trading off time/space for accuracy of the computation. Furthermore, besides the usual Single Observation Time Test for the evaluation of the fault coverage, the simulator supports evaluation according to the more general Multiple Observation Time Test Strategy (MOT). Numerous experiments are given to demonstrate the feasibility and efficiency of our approach. In particular, it is shown that, at the expense of a reasonable time penalty, the exactness of the fault coverage computation can be improved even for the largest benchmark functions.
Introduction
Simulation is a basic technique applied in many areas of electronic design. As is well known, the
task of simulation at gate level is to determine values (in a given logic) for every lead of the circuit
with respect to a set of primary input assignments. Also in the testing area numerous tools use
simulation as a fundamental underlying algorithm: E.g. the quality of classical Automatic Test
Pattern Generation (ATPG) tools [2] significantly relies on efficient fault simulation, a specific
type of simulation, where the current test patterns are simulated to determine all faults of
a fault model that are also detected by the computed patterns. More recently, a new type
of ATPG tool, the so-called Genetic Algorithm-based tool [30, 14] has emerged. Here, fault
simulation as the core algorithm plays an even more important role. Apart from this, test set
compaction, switching activity computation, signal probability computation, and fault diagnosis
provide further examples of the application of simulation/fault simulation in testing.
Here, we are mainly interested in fault simulation for synchronous sequential circuits. Several
gate level based fault simulation algorithms are known, e.g. [12, 21, 24, 3]. In general, these
simulators focus on performance, and accuracy is not a main concern. On the other hand, if
there is no information about the initial state of the circuit available, the algorithm has to deal
with this unknown initial state.
Very often a three-valued logic (0,1 and X for modeling an unknown value) is used. It is well
known, that in general only a lower bound for the fault coverage is determined. Even for some of
the usual benchmarks [4] the gap between this lower bound and the real fault coverage is large.
The reason for this gap is the inherent inaccuracy of the three-valued logic. For instance, there
are circuits whose synchronizing sequence cannot be verified using three-valued logic [23].
synchronizing sequence is an input sequence which drives the circuit into a unique state starting
in any initial state.)
A lot of work has been done to overcome these problems. On the one hand, if possible,
changes made already during the design phase may help: The problem of synchronization can
be bypassed by implementing a full-reset or a full scan environment and additionally making the
assumption that the added circuitry is fault-free. However, besides this assumption there are
some further disadvantages with such approaches, e.g. the long and sometimes inadequate test
evaluation for full scan circuits, due to the scan-in and scan-out overhead. Also, the area and
delay penalty for full scan circuits might be high and unacceptable. Circuits with partial reset
have been shown to be a good alternative. For example, in [22, 28] partial reset has been used
to improve fault coverage and test length for a given circuit. Thus, assuming a (partially) non-
resetable circuit has its advantages. Furthermore, a sophisticated state assignment procedure
[8] may avoid initializability problems. Nevertheless, the above methods can only be applied
during synthesis and not if an already designed circuit is considered.
In that case, the fault simulation algorithm itself has to handle the unknown initial state.
One possibility, apart from the standard way of using three-valued logic, is complete simulation,
where the unknown values are successively simulated for all possible combinations of 0 and 1
[7, 27]. In general, this approach is only reasonable for circuits with a small number of memory
elements. A more promising approach is based on symbolic traversal techniques, well known in
the area of verification. Ordered Binary Decision Diagrams (OBDDs) [5] may be used for an
representation of the state space and its traversal, i.e. they offer the potential
of calculating the exact values for all signals in the circuit. The computation of minimum (or
almost minimum) reset sequences [16, 31] and test generation with symbolic methods [6, 9, 10]
denote successful applications of this concept.
Nevertheless, the advantage of exact computation is paid for by the complexity of handling
the OBDDs. Indeed, in practical applications it happens quite frequently that circuits leading
to large BDDs have to be treated. Thus, purely symbolic methods are either only applicable to
smaller circuits or they have to be combined, e.g., in the case of test generation, with classical
path-oriented methods to allow the handling of large circuits.
Concerning fault simulation, test generation using symbolic methods should be accompanied
by a fault simulation tool exploiting the potential of the symbolically generated test sequences.
Of course, for the reasons already mentioned before, fully exact symbolic fault simulation in general
cannot be performed for large circuits. Contrary to verification and ordinary test generation
OBDDs for sets of faults have to be constructed and kept in memory. One possibility to handle
this problem is to implement a combination with incomplete, but more efficient strategies.
The hybrid fault simulator H-FS presented in this article follows this approach. Hybrid in
our context means that the algorithm supports different simulation modes, one of them being
the symbolic mode. The simulator assumes a gate level description of the circuit and supports
the stuck-at fault model. It allows a dynamic, fully automatic switching between the modes and
thereby guarantees correctness of the transformation steps between the modes. More precisely,
H-FS uses three kinds of fault simulation procedures:
ffl a fault simulation procedure X-FS based upon three-valued logic,
ffl a symbolic fault simulation procedure B-FS based upon OBDDs, and
ffl a fault simulation procedure BX-FS which is hybrid itself in the sense that a symbolic true-
value simulation and an explicit fault simulation procedure based upon the three-valued
logic are combined.
These procedures differ in their time and space requirements and the accuracy of their fault
simulation. H-FS tries to combine the advantages of these procedures by choosing a convenient
logic before starting the simulation for the next test vector. For instance, if the space
requirements of B-FS is becoming too large, the hybrid fault simulator will select BX-FS or if
necessary X-FS. After the application of a few patterns, that possibly initialize a large number
of memory elements and thereby reduce the space requirements of B-FS, the algorithm will try
to continue with B-FS. For that reason, the hybrid fault simulation strategy works also for the
largest benchmark circuits [4]. Experiments show that H-FS is able to determine the exact fault
coverage for many benchmarks or at least a tighter lower bound than previously known.
Until now, we have considered fault simulation based on the Single Observation Time Test
Strategy (SOT) which is inaccurate in itself. To overcome the limitation of SOT a more general
definition of detectability has to be considered. This led to the Multiple Observation Time Test
Strategy (MOT) which is used e.g. in [26] to increase the efficiency of test generation. Pomeranz
and Reddy realized the necessity to support MOT-based test generation by a MOT-based fault
simulation and proposed three-valued fault simulation based on MOT in [27, 29]. For "complete"
MOT it is necessary to compare the sets of fault-free responses with the set of responses obtained
in the presence of faults (for all possible states of the circuit). This is especially time consuming
if long test sequences and a large number of memory elements exist. To overcome these problems
a restricted version of MOT (rMOT) has been proposed which nevertheless is more accurate
than SOT [26].
In addition to SOT, H-FS supports rMOT and MOT as well. It turns out that rMOT and
MOT can be included in the symbolic parts of H-FS without too much effort. The use of OBDDs
makes it possible to handle a large number of output sequences. Experiments demonstrate that
we succeed in computing the exact MOT fault coverage for many of the considered benchmark
circuits. In case the space requirements of the OBDD-based approach exceed a given limit, which
is determined by the working environment, the hybrid fault simulator may e.g. change to the
SOT strategy based on the three-valued logic for some simulation steps and then again return
to the symbolic evaluation and the MOT strategy. This guarantees that the MOT strategy can
be applied even to large circuits. In contrast to the general MOT strategy, the rMOT strategy
allows a test evaluation by comparing the output sequence of the circuit under test with the
unique output sequence of the fault-free circuit. We show experimentally that the accuracy of
fault simulation based on rMOT is almost identical with that based on MOT for many circuits.
With regard to performance it can be observed that for some circuits a symbolic rMOT fault
simulation works even more efficiently than a symbolic SOT fault simulation. Thus, the results
generated according to rMOT have all attributes important for a fault simulation algorithm:
reasonably fast simulation time, high fault coverage, and normal test evaluation.
The paper is structured as follows: Section 2 presents some definitions and important properties
of synchronous sequential circuits. In Section 3, the different fault simulation components
and their properties are described. The resulting hybrid fault simulator H-FS based on SOT
and the symbolic extensions for MOT are explained in Section 4. Section 5 gives some experi-
ments, which demonstrate the efficiency of the presented hybrid fault simulator. We finish with
a summary of the results in Section 6.
Preliminaries
In this section we repeat some basic definitions and notation necessary for the understanding of
the paper. SOT, MOT and rMOT are introduced. Finally, the complexity of fault simulation
for sequential circuits is briefly analyzed from a theoretical point of view.
2.1 Basic Definitions and Notation
As is well known, the input/output - behavior of a synchronous sequential circuit can be described
by a Finite State Machine (FSM) [18]; an illustration is given in Figure 1.
More formally, a finite state machine M is defined as a 5-tuple
is the input set, O the output set, and S the state set. ffi : S \Theta I ! S is the next state function,
O is the output function.
combi-
national
logic
INPUT
OUTPUT

Figure

1: Model of a finite state machine
Since we consider a gate level realization of a FSM, we have
the number of primary inputs (PIs), l the number of primary outputs (POs),
and m the number of memory elements. ffi and - are computed by a combinational circuit. The
inputs of the combinational circuit which are connected to the outputs of the memory elements
are called secondary inputs (SIs) or present-state variables. Analogously, the outputs of the
combinational circuit connected to the inputs of the memory elements are called secondary
outputs (SOs) or next-state variables.
For the description of our algorithms we use the following
denotes an input sequence of length n with
denotes the value that is assigned to the i-th PI before starting simulation at time
step t. (s(p; 0); denotes the state sequence defined by Z, the initial state
and the next state function ffi, i.e.
is the output sequence defined by the initial state p, input sequence
Z and output function -, i.e. o(p; n. The notion
l is used to denote the value at the i-th PO after simulation in time step t.
As usual, the behavior of a circuit affected by a stuck-at fault f is described by a faulty FSM
, the states s f (p; t) and the outputs are defined analogously
to the fault-free case.
Notice that for the case of an unknown initial state, we have to assume that the initial state
of the fault-free machine and the faulty machine as well may be any element in B m .
2.2 Fault Detection in Sequential Circuits
Detectability of faults in synchronous sequential circuits in general depends on the (possibly)
unknown initial state [1, 15, 26]. Here, we consider the Single Observation Time Test
(SOT) [1], the Multiple Observation Time Test Strategy (MOT), and a restricted version of
MOT [26] together with the single stuck-at fault model.
Definition 2.1
A fault f is SOT-detectable by an input sequence
1g such that 8 states
According to the above definition a fault is SOT-detectable if there is a unique point in time
such that independent of the initial states of both machines the Boolean output values on a
particular PO are to each other's inverse.

Figure

2: Example of SOT (MOT) fault detection.
It turns out that there are some intuitively detectable stuck-at faults which are not detectable
according to this definition. For illustration consider Figure 2 [27]. The figure shows two fault
simulation steps for the test sequence There are four possible initial state
pairs: 1)g. These four pairs can be separated into two cases:
there is a difference at the PO in time frame one,
but there is no difference at the PO in time frame two. For (p; q) 2 f(0; 1); (1; 0)g there is a
difference at the PO in time frame two, but there is no difference in time frame one. Hence,
this fault is undetectable according to SOT since there is no single time frame for that all initial
state pairs cause the faulty and fault-free outputs to differ. On the other hand, the fault is
detectable according to MOT:
Definition 2.2
A fault f is MOT-detectable by an input sequence
l such
According to MOT, there is an individual point in time for each possible initial state pair
(p; q), such that the Boolean output values on a particular PO are complementary. In other
words, there is no state pair (p; q), such that the corresponding output sequences resulting from
application of input sequence Z (to the fault-free and faulty circuit) are identical. Hence, it is
clear that MOT is more general than SOT. Furthermore, MOT-detectability is equivalent to the
fact that the set of output sequences (obtainable for a fixed sequence Z and all possible initial
states) for the fault free and faulty circuit are disjoint.
Restricted MOT requires a unique output value for the fault-free circuit, thus being less
general than MOT, but more general than SOT:
Definition 2.3
A fault f is rMOT-detectable by an input sequence
(Notice that the fault given in the example of Figure 2 is MOT-detectable, but not rMOT-
detectable.) As mentioned before, the advantage of rMOT compared to MOT results from the
fact that rMOT allows a test evaluation by comparing the output sequence of the circuit under
test with a (partially defined) unique output sequence of the fault-free circuit.
We close this section by analyzing the complexity of fault simulation for synchronous sequential
circuits. While it is well known [2] that fault simulation in combinational circuits can be
solved in O(n \Delta size of the circuit and number of patterns), the situation
is more difficult in the sequential case: The run-time of sequential fault simulation based on
three-valued logic is identical to this bound, but a three-valued simulation in general computes
only a lower bound for the fault coverage. (An example circuit will be shown later.) However,
the exact solution of the problem of sequential fault simulation, i.e. the computation of the
exact fault coverage for a given test sequence, is much more complex, even with respect to SOT.
For an analysis of the complexity of exact sequential fault simulation we consider the following
decision problem which has to be solved during fault simulation.
Instance: Synchronous sequential circuit, input sequence Z and stuck-at fault f
Question: Is f SOT-undetectable by Z?
We construct a (polynomial time) reduction of the non-tautology problem to SOT-FSIM-UNDE-
TECT. (The non-tautology problem corresponds to the question whether a given combinational
circuit C evaluates to 0 for at least one assignment of the variables.) Since non-tautology is
well-known to be NP-complete we obtain.
Theorem 2.1
SOT-FSIM-UNDETECT is NP-hard.
Sketch of the Proof: For the reduction we consider any combinational circuit C. Then
the PIs of C are replaced by memory elements, so there are no longer any PIs. The resulting
sequential circuit together with the empty input sequence and the sa-0 fault at the PO forms
an instance of SOT-FSIM-UNDETECT. Due to the unknown initial state the fault is SOT-
undetectable (for the empty input sequence) iff C is a non-tautology. 2
Note that the above result is valid also for rMOT and MOT, because a test sequence of
length 1 is considered.
From Theorem 2.1 it follows that there is no hope of finding an efficient polynomial time
algorithm for obtaining an exact solution. Thus, from the point of view of complexity theory,
using OBDDs with an exponential worst case behavior is justified, if we want to attack the
problem of finding an exact solution. Furthermore, we will see in the following how the exact
algorithm can be modified to trade off runtime of the method for exactness of the result.
3 Components of Hybrid Fault Simulation
In this section we introduce the three main components of H-FS: the three-valued fault simulation
procedure X-FS, the symbolic simulation procedure B-FS and a mixed simulation procedure
BX-FS. Since all of them follow the same basic simulation method we introduce this method in
advance to simplify the presentation.
3.1 Basic Fault Simulation Scheme
In our approach the overall fault simulation scheme corresponds to an event-driven single-fault
propagation (SFP) [2]. Since procedures with different logics are going to be combined in the
final algorithm we do not make use of the machine word length for parallel evaluation of input
patterns.
At the beginning the fault simulation procedure receives a set of faults F and a test sequence
Z of length n. Also, an encoding of the unknown initial state is defined depending on the logic
used. Then the simulation of the sequential circuit for each time frame is performed similar to
the simulation of a combinational circuit by evaluating the gates in a topological order, with
the extension that the value of a secondary input at time t, 1 - t - n, is defined by the value
of the corresponding secondary output at time t \Gamma 1.
At first, a true-value simulation is carried out. Subsequently, the faults are injected one by
one and an event-driven SFP is performed. Thereby the effects of each fault are propagated
towards the POs and SOs. If any fault reaches a PO it will be marked as detected. Of course
the fault is dropped and it will not be considered during following simulation steps. If an SO
changes, the next state of the faulty circuit is different from the next state of the fault-free
circuit and it has to be stored for the next simulation step. This means, only those memory
elements are stored whose value differ from that of the fault-free case. This helps to reduce the
memory requirements of the simulator.
3.2 Three-Valued Fault Simulation
As already mentioned fault simulation using the logic Xg, in this paper denoted
as X-FS, is the usual way to handle circuits with an unknown initial state. (0 and 1 are called
defined values. X is used to denote the unknown or undefined value.) The unknown initial state
is encoded by (X; thus representing the set of all possible binary initial states. A
fault f is marked as detectable by the input sequence Z, if during explicit fault simulation based
on logic BX a PO is reached where the fault-free and the faulty circuit compute different but
defined values. Since this difference is obtained without using any information about the state
of the (fault-free and faulty) circuit it follows immediately that the fault is SOT-detectable by
Z.
FFr
r
r
r
a
c
r
r
r
r

Figure

3: BX -uninitializable circuit.
On the other hand, the undefined value X is not able to capture dependencies between
two undefined signals and thus leads to inaccurate computations. A simple example is given
in

Figure

3, where a simulation based upon the three-valued logic is not able to verify the
synchronizing sequence given by [a=1,b=0,c=0]. (As shown in [23] the choice of the binary
encoding may be a further reason for inaccuracy preventing the verification of synchronizing
sequences with the three-valued logic.) The advantage of three-valued fault simulation is its
time and space behavior. Based upon the three-valued logic the fault simulation of a circuit C
for a test sequence of length n can be performed in time O(n \Delta jCj 2 ).
In summary, X-FS efficiently determines a lower bound for the exact fault coverage with
respect to SOT.
3.3 Symbolic Fault Simulation
Unlike X-FS, the symbolic fault simulation procedure called B-FS aims at representing the exact
values of all signals in the circuit under the assumption that the initial state is not known and
a fixed input sequence Z is given. To do so, the signal value in each time step is completely
defined by a Boolean function depending on the m memory elements and the fixed Boolean
values of the sequence Z.
Thus, B-FS is based upon the logic B i.e. the elements of the logic are
single output Boolean functions with m Boolean variables, where to each memory element a
Boolean variable p i is assigned, representing the unknown value at the beginning of the simulation
of both the fault-free and the faulty circuit. The two constant functions contained in
will be abbreviated by 0 and 1. (At the beginning of the simulation of each time step they
are assigned to the PIs according to the values of the sequence Z.) For the representation of
the elements in B s we use OBDDs. Using OBDD manipulation algorithms a symbolic fault
simulation along the general scheme presented in Section 3.1 can now be performed. According
to SOT, a fault f is marked as detectable by Z, iff there exists an output for which M and M f
lead to different but constant functions in a certain time frame. (We want to mention at this
point, that, in contrast to X-FS, the symbolic simulation scheme also offers the possibility to
determine detectability with respect to rMOT and MOT. The details are more complicated and
will be discussed separately in Section 4.2.)
Concerning time and space behavior the following should be noted: In each time step B-FS
assigns an OBDD to each lead of the circuit during true-value simulation. This OBDD must be
stored for the event-driven explicit fault simulation. Moreover, the symbolic representations for
the state vector of the fault-free circuit and all state vectors of the faulty circuits, not detected
in the previous time steps, have to be stored for the next simulation step.
In short, B-FS determines the exact fault coverage with respect to SOT. But, even when using
heuristics to find a "good" variable order, the space and time requirements may be prohibitively
high (in the worst case exponential) and prevent an application of a purely OBDD-based fault
simulation algorithm to large circuits.
3.4 Mixed-Logic Fault Simulation
We take a first step towards a hybrid fault simulation procedure by combining X-FS and B-FS.
The resulting mixed-logic fault simulation procedure BX-FS basically works as follows:
ffl The true-value simulation which is carried out only once per input vector uses the accurate
i.e. the values are represented by OBDDs and the initial state is given
by the variable sequence (p 1
ffl The expensive explicit fault simulation uses the three-valued logic BX , thus the unknown
initial state is modeled by
In the following we discuss problems emerging from the use of differing logics in the simulation
of the fault-free and of the faulty machine in combination with the SFP method.
Algorithm BX sim (Figure 4) gives a more detailed description of the mixed-logic true-value
simulation: At first the PIs and SIs are initialized (Line 1). After an OBDD-based evaluation of
the gate g (Line 2) the output-OBDD TB [output(g)] at signal output(g) is transformed according
to - (Line 3):
Here, - is a mapping realizing a transformation of symbolic values to values
0,1,X as follows:
Note that - is surjective but not injective, since all non-constant values in B s are mapped to
the value X.
Line 4 of Algorithm BX sim ensures that an OBDD is freed (and finally deleted) as soon as
the OBDD is no longer necessary. This is different from the pure symbolic simulation. There, all
OBDDs of the true-value simulation have to be stored for initializing the faulty circuits. Here,
this storing is only done for the OBDDs of the next state. The storing for the remaining signals
is done more efficiently by logic elements of BX . Note that only elements of BX are required
for the explicit fault simulation part.
procedure BX sim( z(t), s(t) )
vector
vectors of length No.of leads
(1) initialize the primary and secondary inputs
with the OBDDs z(t) and s(t) ;
for each gate g 2 G in topological order
else if (
else
all successors of input(g;
are evaluated )

Figure

4: Algorithm BX sim for mixed-logic true-value simulation
Using the transformed true-value assignment instead of using a three-valued true-value simulation
increases the accuracy of the explicit fault simulation. A simple example illustrates the
improvement. Consider the circuit shown in Figure 3 again. This circuit cannot be initialized by
the input assignment using the three-valued logic as shown in Section 3.2. However, algorithm
BX sim initializes the fault-free circuit and assigns a 1 to the primary output of the circuit,
whereas a three-valued simulation would assign the value X. Thus, a stuck-at 0 fault at the
output becomes detectable now.
On the other hand, combining different logics for fault simulation together with the efficient
method of event-driven simulation leads to a new problem. For illustration consider Figure 5,
which shows a symbolic assignment determined by the true-value simulation on the left-hand
side and the assignment after the logic transformation on the right-hand side. f , g, h, 0 and 1
are elements of B s with f , g, h 62 f0; 1g and f \Delta h 62 f0; 1g.
Now assume that a stuck-at 0 fault at u is injected and the resulting event is propagated
towards w by SFP as usually done in three-valued fault simulation; see the right-hand side of
MUX MUX MUX MUX

Figure

5: How to combine different logics in in BX-FS event-driven single-fault propagation?

Figure

5. At first, the multiplexers are evaluated. Since no event is produced at the outputs
SFP stops and the value on lead v remains 0 for the faulty circuit. If we now evaluate the OR
gate (which has an event at the right input), we obtain 1=0 at the output. Thus, the fault would
be judged to be detectable at output w. This is not correct, however, as a look at the left-hand
side of Figure 5 easily reveals.
Therefore, the event-driven SFP has to be modified to guarantee its correctness: Whenever
a gate evaluated during the event-driven single fault propagation and the value at the output of
the gate is equal to X in the faulty case, we in general do not know anything about the symbolic
value represented by X. In particular we do not know whether X stands for a value that is
identical to the value of the signal in the fault-free case. Thus, to be correct, SFP at this point
has to be continued i.e. X has to be considered as a (potential) event. Consider again Figure 5.
Evaluating both multiplexers leads to X on the multiplexer outputs in the fault-free and faulty
cases. Consequently, the following AND gate has to be evaluated and we get a 0=X event at v.
Evaluating the OR gate leads to 0=X at w and the fault is not observable, which is the correct
answer. Algorithm BX fa sim in Figure 6 describes this event propagation more precisely.
procedure BX fa sim( f , L f ,
list of faulty state values
computed by BX sim
(2) for all (lead, value) 2 L f
while exists gates g with marked input leads
then
if (output(g) is PO with
then f is SOT-detectable; exit;
s is a marked SOg;

Figure

Algorithm BX fa sim for mixed-logic explicit fault simulation
F denotes the three-valued assignment of the faulty circuit and TX the three-valued assignment
determined by Algorithm BX sim (Figure 6): After the initialization of the value vector (Line 1)
the present state of the faulty circuit is loaded from L f , the list storing the state values different
from those of the fault-free circuit. L f will be updated in Line 8 at the end of the algorithm. In
Line 3 the fault is injected and the corresponding lead is marked. As long as there is a gate in
the queue (sorted by the level of the gate), the body of the loop is executed (Line 4). After the
computation of the output value of g (Line 5), Line 6 checks for an event. If an event reaches
a PO, a fault is detected with respect to SOT (Line 7). If after the while-loop the fault is not
detected, the next state of the faulty circuit is stored (Line 8).
Based on the description of BX-FS and the considerations given above, we are now ready to
conclude the correctness of the algorithm: The true-value simulation performed by Algorithm
BX sim is similar to that of B-FS. In particular, it guarantees that all constant values at the POs
are computed. The modified event propagation as given by Algorithm BX fa sim guarantees
that all potential events are propagated. Thus, a 0=1 or 1=0 difference at a PO guarantees the
detectability of the fault according to SOT. Furthermore, a slight modification of the example
in

Figure

shows that B-FS in general detects more faults than BX-FS.
Theorem 3.1
The procedure BX-FS determines (only) a lower bound for the fault coverage with respect
to SOT. The lower bound in general is tighter than the bound determined by X-FS.
As already mentioned, the space and time requirements of BX-FS are considerably smaller than
those of B-FS, since fewer OBDDs have to be stored and fewer OBDDs have to be constructed.
Consequently, with the same parameter setting for the OBDD-manager, larger OBDDs can
be built. Thus, in terms of accuracy and complexity, BX-FS is positioned between X-FS and
B-FS. We will see in the experiments that from the practical point of view BX-FS also offers a
reasonable compromise between efficiency and accuracy.
4 The Hybrid Fault Simulator H-FS
In this section the integration of the three simulation procedures in H-FS is discussed. To
repeat our motivation, pure symbolic fault simulation with B-FS and even a mixed simulation
with BX-FS may be infeasible for specific large circuits. On the other hand, fault coverage
should be determined as precisely as possible, thus symbolic methods should be applied as often
as possible. For that reason, we developed a hybrid scheme which is able to automatically
select a suitable simulator and switch back and forth between the simulators depending on the
resources available and the properties of the circuit under test.
We firstly describe how hybrid fault simulation with respect to SOT is performed. Then, we
extend the concept to also work with rMOT and MOT.
4.1 Hybrid Fault Simulation with respect to SOT
To perform hybrid fault simulation for synchronous sequential circuits with an input sequence
Z, H-FS receives as additional inputs a space limit S max and an initial mode. S max bounds
the memory which can be used by the OBDD package. In its basic form H-FS works in three
modes based upon X-FS, B-FS, BX-FS. The modes differ in their accuracy and space/time
requirements.
performs a fault simulation using the three-valued logic. In this mode, it
works like X-FS.
tries to perform a fault simulation using BX-FS. If the space required by
the OBDD-based true-value simulation exceeds the space limit S max , H-FS selects X-FS
and simulates the next \Delta 1 time steps in mode MX , starting with the resimulation of the
current fault-free circuit. Subsequently, H-FS works in mode MBX again if necessary. A
change back to MBX is unnecessary if all memory elements of the fault-free circuit are
initialized.
tries to perform fault simulation using B-FS. If the space required by B-FS
exceeds the space limit S max , H-FS selects BX-FS and works in mode MBX for the rest
of the current and the next \Delta 2 time steps, starting with the resimulation of the current
faulty (or fault-free) circuit. Subsequently, H-FS changes to mode MB again if necessary. A
change to MB is unnecessary, if all memory elements of the faulty circuits are initialized.
Clearly, if the space limit is never exceeded by B-FS, H-FS determines the exact fault
coverage achievable with the test sequence Z.MB
input sequence
mode memory exceeded
all memory
elements initialized
I

Figure

7: Automatic switching between different simulation modes.

Figure

7 illustrates the mode selection. In this example H-FS starts in mode MB . If the memory
limit is exceeded it changes to mode MBX or MX , respectively. After \Delta i steps it returns to mode
MB . If all memory elements are initialized in mode MB (in Figure 7 at time t I ) H-FS switches
to mode MX . The values of and the space limit S max have a strong influence on the
run time and the accuracy of H-FS. For instance if no space limit is given H-FS started in mode
MB determines the exact fault coverage and has the same run time behavior as B-FS. Using a
small space limit and large values for \Delta i the accuracy and the efficiency of H-FS "converges" to
that of X-FS. In the current version of H-FS the pair defined by the user. Based on
numerous tests, we used the pair (5; 7) for our experiments in Section 5.
We now want to point out details of the switches between the three simulation modes.
According to the definition of the modes a switch from a mode to a less precise mode - a switch-
may occur during a time frame, while a switch to a more accurate mode - a switch-up -
only occurs at the beginning of a time frame. In both cases signal values have to be transformed
between the corresponding logics B s and BX .
We first consider the switch-down from MB to MBX . Here, stored symbolic state vectors
of the faulty circuits are transformed to BX by using transformation - already introduced in
Section 3.4. In particular this means, that any correlations between signal values before time
step t are lost, unless the values are constant.
Transformations for a switch-down from MBX to MX are performed analogously for the
fault-free circuit. For an example see Table 1, where the transformation of symbolic state
vectors into three-valued state vectors is illustrated. s(t) is the state vector computed by the
fault-free circuit at time t, and s f 1 (t) and s f 2 (t) are the state vectors computed by the faulty
circuits having fault f 1 and f 2 , respectively.
We now consider the transformations necessary for a switch-up. In this case values from
BX have to be replaced by symbolic values. Since - is not injective an inverse mapping cannot
\Gamma!

Table

1: Transformation of symbolic state vectors into three-valued state vectors.
be defined. We make use of the fact that a switch-up is performed only at the beginning of a
time step and therefore an "inverse" transformation has to be applied only to state vectors. Let
am ) be a three-valued state vector. Then the transformation is defined by -
1 if a
An example for the transformation of three-valued state vectors into the corresponding symbolic
state vectors after a time step t is shown in Table 2. If the i-th component of a state
vector is undefined, it is replaced by p i , otherwise, the corresponding defined value is used. In
the following time steps, the OBDDs are defined only over the remaining p i variables, resulting
in a (much) smaller memory demand.
s
\Gamma!

Table

2: Transformation of three-valued state vectors into symbolic state vectors.
Of course, the efficiency of H-FS depends on the selected mode. To improve the efficiency,
H-FS checks after each simulation step whether there is any memory element left that is not
initialized either in the fault-free circuit or in any faulty circuit. H-FS automatically changes
from mode MB to mode MX if all memory elements of the fault-free circuit and of the faulty
circuits are initialized because gate evaluations based upon the three-valued logic are much more
efficient than gate evaluations based upon OBDDs. See Figure 7 for an example. In simulation
step t I the correct and all faulty circuits are initialized and the simulator switches from mode MB
to mode MX without losing accuracy. Notice that only the fault-free circuit must be initialized
to allow a switching from MBX to MX without a disadvantage.
The hybrid fault simulation procedure H-FS uses X-FS for reducing the space requirements of
B-FS and BX-FS. It profits from the fact that after some three-valued simulation steps, in most
cases the number of memory elements which are not initialized is greatly reduced. Consequently,
the space required by B-FS or BX-FS is reduced because the number of variables introduced to
encode the current state of the circuits is smaller. Noting that the space requirements may be
exponential in the number of variables introduced, the importance of the three-valued simulation
steps is obvious. Consequently, H-FS partially allows a symbolic fault simulation even for very
large circuits. This will be shown by experiments in Section 5.
4.2 Hybrid Fault Simulation with respect to rMOT and MOT
As mentioned in Section 2 there are stuck-at faults which cannot be detected by any fault
simulation based on SOT. However, as the example in Figure 2 shows, a fault may be detectable
by watching the output sequence for several time frames and applying the MOT strategy.
According to the definition of MOT in Section 2.2 it is necessary to compare sets of fault-free
responses with sets of responses obtained in the presence of faults. This is especially costly if
long test sequences and a large number of memory elements exist.
An elegant way to solve this task by using symbolic methods is presented in the sequel. We
define the MOT-detection function D MOT
f;Z (p; q) :=
Y
l
Y
for each fault f and test sequence Z. denote the state
variables for the initial state of the fault-free and faulty circuit, respectively.
f;Z compares all output sequences of the fault-free and faulty circuits simultaneously. As
long as there is an initial state p of the fault-free circuit that causes the same output sequence
(with respect to Z) as a faulty circuit with initial state q, the two circuits cannot be distinguished,
and D MOT
f;Z 6= 0. We conclude:
Lemma 4.1 A fault f is MOT-detectable by the input sequence Z iff
To illustrate the computation of D MOT
f;Z consider the circuit shown in Figure 2 again. For
the test sequence and the stuck-at 1 fault f indicated in the figure we obtain
f;Z
Consequently, the fault is MOT-detectable.
According to the definition of rMOT a "restricted" version of the MOT-detection function
f;Z is sufficient: The product has to be taken only over terms with i.e. we
obtain the rMOT-detection function D rMOT
defined by
f;Z (q) :=
Y
1-t-n;1-j-l
for each fault f and test sequence Z. We obtain a lemma analogous to that for MOT:
Lemma 4.2 A fault f is rMOT-detectable by the input sequence Z iff
Fault simulation with respect to rMOT and MOT is now realized during symbolic fault
simulation with B-FS by iteratively computing the detection functions D rMOT
f;Z and D MOT
f;Z ,
respectively. To do so, we consider the function Detect f;Z , which initially is set to the constant
function 1 and then incrementally "enlarged" to finally represent
f;Z or D MOT
f;Z . If in course
of the fault simulation process the i-th PO is reached during time frame t, the observability
of the activated fault f is checked and, depending on the current test strategy, Detect f;Z is
modified as follows:
Detect f;Z (p; q) / Detect f;Z (p; q) \Delta [o i (p;
1g. If Detect f;Z is evaluated to 0 the fault is marked as rMOT-detectable.
Note that the OBDD-representation for
already provided by the event-driven
SFP of B-FS.
Besides the correct output function we have to compute the faulty output function
Thus a second set of Boolean variables q for the memory elements of
the faulty circuit is required. Again we profit from the fact that the OBDD-representation
for
with the variable set by the event-driven SFP
of B-FS: We obtain
(q; t) from
by a compose operation on the corresponding
OBDDs, which basically replaces p i by q i for all i. This is much more efficient than computing
separately and thereby unnecessarily increasing the memory demand of the
OBDD-manager, since equivalent functions would have to be stored twice, once for each
variable set. Moreover, the SFP method cannot be applied directly. Finally, we compute
Detect f;Z (p; q) / Detect f;Z (p; q) \Delta [o i (p;
If Detect f;Z is evaluated to 0 the fault is marked as MOT-detectable.
Besides the usual advantages of a symbolic approach compared to explicit enumeration tech-
niques, the integration of the approach in the hybrid fault simulator H-FS allows the application
of the MOT strategy even to large circuits. If the space requirements of the symbolic fault simulation
exceed a given limit the hybrid fault simulator changes to the SOT strategy and works
as described in Section 4.1. After a few simulation steps using e.g. the three-valued logic, which
usually reduces the space requirements for the subsequent symbolic simulation, H-FS returns to
the MOT strategy again. In doing so, the detection function Detect f;Z has to be re-initialized
with the constant function 1.
Concerning efficiency and accuracy we want to make the following points: MOT works more
accurately than rMOT. On the other hand the space requirements of MOT is larger, because
MOT requires different variables for encoding the initial state of the fault-free and the faulty
circuit. rMOT uses the output value of the fault-free circuit only if it represents a constant
function. Therefore, no additional set of variables is used, and Detect f;Z usually is smaller. A
further important advantage of rMOT is that it allows the same test evaluation method as SOT
but achieves higher fault coverages. This means there is an advantage in fault coverage without
any drawback for test evaluation, as explained next.
c(n) be the output sequence which is obtained by applying Z to the circuit
under test. Then test evaluation requires the decision whether or not the circuit under test is
faulty.
In case of a test sequence which is determined with respect to SOT or rMOT the test
evaluation can easily be done: Only a single (partially defined) output sequence of the
fault-free circuit has to be compared with the output sequence of the circuit under test, i.e. the
circuit under test is declared faulty if there are t - n and i - l with
1g.
In case of a test sequence which is determined with respect to MOT the test evaluation is
more complicated. The implementation proposed in [27] requires checking whether the output
sequence contained in the set of output sequences caused by the different initial
states of the fault-free circuit. Since the number of output sequences may be exponential in
the number of memory elements, test evaluation may be very time-consuming. To reduce the
time requirements we propose the comparison of the sequence with the symbolic
representation of the fault-free output sequence. The comparison can be done by evaluating
step by step the product
Y
l
Y
If the result of this computation is 0 the circuit under test is faulty. Experimental results given
in the next section assure that this symbolic test evaluation in many cases requires very small
resources in both time and space.
5 Experimental Results
To investigate the performance of our approach we implemented hybrid fault simulation with
respect to SOT, rMOT and MOT in the programming language C++. The measurements were
performed on a SUN Ultra 1 Creator with 256 Mbytes of memory. For our experiments, we
considered the ISCAS-89 benchmark suite [4]. A space limit S max of 500,000 OBDD-nodes
(300,000 for the circuits s9234.1 and larger) was used to ensure that the procedures of H-FS
based upon OBDDs work efficiently. This number of nodes guarantees that small and mid-size
circuits can be simulated fully symbolically. For larger circuits we noticed that increasing the
node limit does not help to increase efficiency or accuracy. Therefore, a reduced number of
nodes guarantees that execution time otherwise wasted is saved.
We give a short overview on the sets of experiments performed. At first SOT fault coverage
and execution times for a number of benchmark circuits with respect to the deterministically
computed patterns of HITEC [25] (Table 3) is analyzed. Surprisingly, for some benchmarks,
mode MB is faster than both other modes. To explain these execution times, a closer look at
the number of gate evaluations during the simulation is taken in Table 4. The test patterns of
HITEC are determined based on BX . Thus, the special abilities of a symbolic simulation could
not be considered. To do so, test patterns of a symbolic ATPG tool [17] have been used for

Table

5. Table 6 summarizes the results for random patterns applied to circuits hard to initialize
with three-valued random pattern simulation. The graph shown in Figure 8 depicts the possible
large gap of fault coverage between the three simulation modes for one of these circuits.
Finally, Tables 7 and 8 collect the advantages of (r)MOT. The first table considers the
deterministic patterns of [17]. In the second table 500 random patterns are used. The MOT-
fault evaluation is considered in Table 9.
5.1 H-FS and SOT
Fault coverage [%] CPU time [sec]
Cct. jZj MX MBX MB MX MBX MB
s838.1 26 5.16 5.16   5.16 0.48 4.74 97.11

Table

3: SOT results for test sequences generated by HITEC.
evaluations
Cct. MX MBX MB
s386 4.81 8.04 6.42
s400 449.44 449.61 239.85
evaluations
Cct. MX MBX MB
s1494 193.24 194.82 41.15

Table

4: Number of gate evaluations for test sequences generated by HITEC.
Fault coverage [%] CPU time [sec]
Cct. jZj MX MBX MB MX MBX MB
s400 691 90.09 90.09   92.22 1.98 2.00 [1] 16.23
s953 196 8.34 25.58   99.07 5.72 25.58 [18] 2.96 [57]

Table

5: SOT results for deterministic patterns generated by Sym-ATGP.
The fault coverages and execution times for several benchmark circuits for deterministic test
sequences computed by HITEC [25] are shown in Table 3. jZj denotes the length of the test
sequence. Comparing the fault coverages determined by H-FS working in different modes we
observed that, as expected, the fault coverage determined in mode MB is higher than the lower
bounds determined in modes MX or MBX . The fault coverages determined by H-FS in modes
MX and MBX are equal for all circuits except two. This is not surprising, because using a
deterministic test sequence after a few input vectors the fault-free circuit is initialized and H-FS
automatically switches to mode MX . For MBX and MB the simulation step after which H-FS
works in mode MX due to the initialized state vectors is given in square brackets. Note that we
are now able to classify the accuracy of a fault simulation procedure based upon the three-valued
Fault Coverage [%] CPU time [sec.]
Cct. jZj MX MBX MB MX MBX MB
1000 0.00 21.45   100.00 6.40 172.99 79.44
s953 100 8.34 33.55   48.84 2.90 20.63 10.57
500 8.34 59.59   86.28 14.37 91.57 12.66
1000 8.34 62.56   90.92 30.65 172.88 14.14
500 59.67 59.77 59.90 13.32 27.73 70.91
s9234.1 100 5.28 5.47 5.47 30.00 415.87 1411.60
500 5.28 5.47 5.47 148.45 1583.88 4161.27
1000 5.37 5.56 5.64 300.07 3205.65 8453.75
500 8.74 12.23 12.55 386.17 6149.53 5855.76
1000 8.98 13.65 13.94 743.01 9161.44 8655.97
500 19.67 20.08 20.11 293.19 473.42 5055.48
1000 22.99 23.36 23.41 547.70 957.79 9665.74
500 3.53 4.99 4.99 835.36 9527.66 10137.90
s38584.1 100 26.86 28.66 28.82 317.16 484.93 1158.75
1000 52.08 52.37 52.49 1771.85 1976.83 5158.50

Table

results for random patterns and hard-to-initialize circuits.
logic by comparing the fault coverage determined in mode MX with the exact fault coverage
determined in mode MB . Such exact results which were obtained without a temporary change
to the three-valued logic during hybrid fault simulation are indicated by an '\Lambda'. For the first
time it is possible to show that for half of the benchmark circuits considered in Table 3 the exact
fault coverage with respect to the patterns from [25] is already computed by mode MX . For the
other half of the circuits, the gap between the exact fault coverage and the three-valued one is
very small.
Comparing the execution times, we observed that only one third of the simulations in mode
MB are considerably slower than those in modes MX or MBX . At first sight, it should generally
hold that MB is slower than MX and MBX . But for circuits s820, s832, s1488, and s1494,
mode MB is even faster than both other modes! This can be explained by Table 4, which shows
the number of gate evaluations performed during the simulation of the HITEC test sequences
given in units of 10 000 gate evaluations. For almost all circuits H-FS performs far fewer gate
evaluations in mode MB than working in the other modes, because besides the fault-free circuit
most of the faulty circuits are initialized during simulation. In mode MBX , H-FS performs the
Faults detected CPU time [sec]
Cct.
s953 1079 989   979   979   979 3.47 5.03 9.73

Table

7: Comparison of SOT with rMOT and MOT for patterns generated by Sym-ATPG.
largest number of gate evaluations due to the modified single-fault propagation. Of course, a
gate evaluation performed during an OBDD-based simulation is much more expensive than a
gate evaluation performed by a simulation based on the three-valued logic. But a smaller number
of gate evaluations can neutralize these more expensive OBDD evaluation costs. From this it
follows that mode MB can accelerate the fault simulation. Note that H-FS working in mode MX
is very fast for deterministic test sequences. In many examples its efficiency is approximately
comparable with that of fault simulators published in [3, 24, 12].
Since HITEC is based on BX , it is not surprising that the symbolic simulation modes of H-FS
do not provide an essential advantage. Therefore, in Table 5 test sequences generated by using
methods during ATPG ("Sym-ATPG") are considered [17]. The underlying (symbolic)
simulator used there is H-FS, as proposed here. Table 5 shows that for nearly all circuits mode
MB improves the fault coverage (up to 2.2%). Moreover, for some hard-to-initialize circuits
(s953, s510) the gap of fault coverage between mode MX , MBX , and MB is significantly higher.
Another important observation is that circuit s510 does not contain any fault that is redundant
with respect to SOT. Consequently, an application of the expensive multiple observation
time test strategy as proposed in [27] is not necessary. Likewise, a full-scan approach as proposed
in [11, 13] is also not necessary for reasons of fault coverage. However, in [13] the test length
for the full-scan version of s510 is 90 patterns, whereas here 245 patterns are necessary to also
achieve 100% fault coverage. In [11] 968 patterns have been computed for 100% fault coverage.
More known hard-to-initialize circuits are considered in Table 6. Moreover, in [16] it was
shown that some of these circuits cannot be initialized, not even symbolically. Random test
sequences have been used for the different modes of H-FS. For all circuits, H-FS increases the
fault coverage working in mode MB . For instance, consider the fault coverages obtained for
circuit s510. After simulating a random sequence of length 1000 we get a fault coverage of
100% again. This fault coverage for random patterns is much better than the fault coverage
determined by the ATPG procedure VERITAS [10] which only achieves a fault coverage of 93:3%
with a test length of 3027, possibly due to the non-symbolic fault simulation used there. The
Faults detected CPU time [sec]
Cct.
26 26 95.40 3656.37 76.59
s9234.1 6927 6561 13 19 19 4448.82 4487.38 3877.41

Table

8: Comparison of SOT with rMOT and MOT for 500 random patterns.
small difference in the execution times for circuit s510 for fault simulation with 500 and 1000
patterns is explained by the fact that during the simulation, after 553 input vectors the state
vector of the fault-free circuit and the state vectors of all faulty circuits were initialized and
H-FS continues to work in mode MX .
In contrast to other procedures using symbolic methods, we are also able to perform a more
accurate fault simulation for the largest benchmark circuits. For instance, using H-FS in mode
MB the fault coverage achieved for circuit s13207 is approximately 5% higher than using MX .
Furthermore, the table shows also a more general behavior of modes MBX and MB : They detect
faults sooner in the test sequence, see e.g. s510, s953, s38584.1. Thus, a given level of fault
coverage is obtained with far fewer random patterns.
For a direct comparison of the accuracy of H-FS working in different modes consider Figure 8.
It shows the fault coverage as a function of the test sequence length for circuit s953 depending
on the different modes. The resulting graph illustrates the gap between the exact fault coverage
determined in mode MB and the lower bounds computed in modes MX or MBX .
Cct. Max. product size CPU time [sec]
s13207.1 16926 9.36
s38584.1 173466 85.17

Table

9: Results for MOT test evaluation for 500 random patterns.
test sequence length
Mx
Mb
Mbx

Figure

8: Dependence of fault coverage on the working mode for circuit s953.
5.2 H-FS and rMOT and MOT
To compare the performance and the accuracy of the different observation strategies we performed
two sets of experiments. Firstly, we took the deterministic patterns (Table 7), already
used for Table 5. Secondly, randomly determined test sequences of length 500 were used (Ta-
ble 8). The experiments are separated into four parts: First, all three-valued SOT-detectable
faults are eliminated. Then, a symbolic random fault simulation based on the SOT, rMOT
and MOT strategies is performed. Note, that all three symbolic simulations and the initial
three-valued simulation use the same (randomly determined) test sequence. jF j denotes the
number of faults. jF u j denotes the number of faults that were not detected by the three-valued
fault simulation. For each strategy the results are given with respect to this set of remaining
faults. Again, exact computations are denoted by a '\Lambda'. Due to the OBDD-based simulation all
strategies permit a further classification of detectability of faults.
Obviously, MOT has no advantage over rMOT for the deterministic patterns (Table 7). This
becomes clear looking at the time steps, when the fault-free circuit is initialized (see Table 5,
Column 7). With an initialized fault-free circuit, there is no difference between MOT and
rMOT. However, this table shows, that even for patterns computed for a symbolic evaluation
the more advanced test strategies rMOT and MOT will increase the fault coverage with almost
no overhead for simulation time.
For the randomly determined patterns (Table 8), in general, fault simulation based on MOT
detects more faults than fault simulation based on rMOT, and rMOT detects more faults than
a SOT-based fault simulation. In all but eight examples we even succeeded in computing the
exact MOT fault coverage of the test sequences. On the other hand, in most cases where MOT
was not exact we succeeded at least in improving the accuracy compared to the three-valued
fault simulation and the SOT approach as well. For all but six circuits the rMOT strategy
computed the same fault coverage as the MOT strategy. However, for these six circuits MOT
does detect considerably more faults than rMOT.
Using rMOT instead of SOT also led to an improvement in execution time for a number of
circuits. For all other circuits, with exception of s526n, s3384, and s5378, the simulation time
of rMOT is about the same time as that of SOT. Although many OBDD-operations must be
performed for MOT, this strategy is faster than rMOT (SOT) for seven (eleven) circuits. In
general, this happens for circuits for which MOT computes a higher fault coverage than rMOT
(SOT) and due to earlier detection of the faults.
In order to investigate the space and time needed for the test evaluation of MOT, we measured
the maximal size of the symbolic output sequences evaluation product (see Section 4.2) and the
necessary execution time. The same 500 random patterns as used for the results of Table 8 have
been used. We considered the circuits for which the MOT strategy detects faults which cannot
be detected either by the SOT or the rMOT strategy. Additionally, to show the feasibility of
the MOT test evaluation the largest benchmark circuits are considered.
In order to estimate the maximum time needed for the test evaluation we computed a possible
test response of the fault-free circuit as follows: (1) Initialize the memory elements of the fault-free
circuit at the beginning of the simulation with random values. Then (2) simulate the test
sequence. Since the output sequence of the circuit under test is correct the test evaluation
does not terminate until the test sequence is fully evaluated. Also note that a test response of
a fault-free circuit under test requires the computation of the product of all symbolic output
values. The maximal size of this product is given in the table together with the execution time.
The experiments show that MOT-test evaluation can efficiently be performed in both time and
space.
6 Conclusions
In this paper we presented the hybrid fault simulator H-FS for synchronous sequential circuits.
It is able to automatically select between three different logics during simulation: the well known
three-valued logic, a Boolean function logic, and a mixed logic. Consequently, H-FS can profit
from the advantages which are offered by the different logics. On the one hand, it may use the
efficiency of the three-valued fault simulator, on the other hand, it may use the accuracy of the
simulator. Furthermore, the advantages of both strategies are combined in the
mixed-logic simulator.
Experiments have shown that H-FS is able to increase the fault coverage even for the largest
benchmark circuits. Of course, in some cases H-FS requires more time and space than a fault
simulator merely based upon the three-valued logic. On the other hand, the accuracy can be
considerably increased. Moreover, for many benchmark circuits it computes the exact fault
coverage, not known before.
The symbolic parts of the H-FS can be enhanced by the more advanced Multiple Observation
Time Test Method (MOT) with only a few extensions to the fault detection definition. This
results in a further improvement of fault coverage. Additionally, we showed that test evaluation
can also be performed efficiently for MOT. Moreover, using restricted MOT, which achieves the
same fault coverage as MOT for many circuits, the usual SOT-test evaluation method need not
be modified. Thus, evaluating a test sequence according to rMOT one obtains an advantage
without any drawbacks. Additionally, the fault simulation time with respect to rMOT is often
shorter than that with respect to SOT.



--R

On redundancy and fault detection in sequential circuits.
Digital Systems Testing and Testable Design.
FAST-SC: Fast fault simulation in synchronous sequential circuits.
Combinational profiles of sequential benchmark circuits.

Full symbolic ATPG for large circuits.
Accurate logic simulation in the presence of unknowns.
State assignment for initializable synthesis.
Redundancy identification/removal and test generation for sequential circuits using implicit state enumeration.
Synchronizing sequences and symbolic traversal techniques in test generation.
Advanced techniques for GA-based sequential ATPG
PARIS: a parallel pattern fault simulator for synchronous sequential circuits.
New techniques for deterministic test pattern generation.
Sequential circuit test generation using dynamic state traversal.
Sequentially untestable faults identified without search.
On the (non-) resetability of synchronous sequential circuits
Combining GAs and symbolic methods for high quality tests of sequential circuits.
Switching and Finite Automata Theory.
A hybrid fault simulator for synchronous sequential circuits.
Symbolic fault simulation for sequential circuits and the multiple observation time test strategy.
HOPE: An efficient parallel fault simulator for synchronous sequential circuits.
Partial reset: An inexpensive design for testability approach.
The sequential ATPG: A theoretical limit.

HITEC: A test generation package for sequential circuits.
The multiple observation time test strategy.
Fault simulation for synchronous sequential circuits under the multiple observation time testing approach.
On the role of hardware reset in synchronous sequential circuit test generation.
Fault simulation under the multiple observation time approach using backward implication.
A test cultivation program for sequential VLSI circuits.
On the initialization of sequential circuits.
--TR
Graph-based algorithms for Boolean function manipulation
The Multiple Observation Time Test
HOPE: an efficient parallel fault simulator for synchronous sequential circuits
Symbolic fault simulation for sequential circuits and the multiple observation time test strategy
Fault simulation under the multiple observation time approach using backward implications
CRIS
On the Role of Hardware Reset in Synchronous Sequential Circuit Test Generation
A Hybrid Fault Simulator for Synchronous Sequential Circuits
Sequentially Untestable Faults Identified Without Search ("Simple Implications Beat Exhaustive Search!")
Full-Symbolic ATPG for Large Circuits
On the Initialization of Sequential Circuits
Advanced Techniques for GA-based sequential ATPGs
Sequential Circuit Test Generation Using Dynamic State Traversal
On the (non-)resetability of synchronous sequential circuits
20.2 New Techniques for Deterministic Test Pattern Generation

--CTR
Martin Keim , Nicole Drechsler , Rolf Drechsler , Bernd Becker, Combining GAs and Symbolic Methods for High Quality Tests of Sequential Circuits, Journal of Electronic Testing: Theory and Applications, v.17 n.1, p.37-51, February 2001
symbolic simulation;fault simulation;MOT;BDD;SOT