T’riE PATH SHECKEPSG MEYEGEE APPLiEfl
'3'0 WHERE FAEJL? M‘éALYSES
0F SWiTCHii‘éS CEfiCfiE"S

a: ‘7’, ' a‘ &' :l‘ o u .
wSSéitfiuOfi fan. me messes 9% 9:1. 3.

EéiEHEGéifi SEE Lf‘i‘eififiiw
EYE E’Zi‘sfifi CHEN-

2:378

    
   

LI 8 1‘? .-‘ El ’
hlichignn State
University

 

This is to certify that the

thesis entitled

THE PATH CHECKING PETHOD APPLIED TO MULTIPLE
FAULT ANALYSIS OF SWITCHING CIRCUITS

presented by

Tze Tzong Chen

has been accepted towards fulfillment
of the requirements for

 

Ph.D. degree in Computer Science

Major professor

Date Dec; 7% 1976

0-7639

J

 
     

800K BINDERY lNE. ‘:

LIBRARY amnms
m‘NIlfiifimmin mi- ‘

" magma av " a:
fill“ & SUNS' m1

ABSTRACT

THE PATH CHECKING METHOD APPLIED TO MULTIPLE
FAULT ANALYSIS OF SWITCHING CIRCUITS

BY

Tze Tzong Chen

In this thesis, the path checking method is pre-
sented for the fault detection and diagnosis of switching
circuits, both combinational and sequential. In the case
of sequential circuits, signal flows in the circuits and
their relevance to the state diagram can be exposed by this
method which further facilitate the fault analysis.

Using this method, every path of the switching
circuit is checked for its ability to pass both signals, 0
and l. The same approach is applied to both combinational
and sequential circuits, with the sequential circuits
treated as an extension of the combinational circuits.
Thus, for sequential circuits, the fault analysis is con-
ducted at the circuit level rather than at the state
diagram level.

The only restriction imposed on the types of cir-
cuits that are considered is that every path of the cir-
cuits be sensitizible. Although the EXCLUSIVE OR logical

gate is excluded from this study, its exclusion is mainly

Tze Tzong Chen

for the purpose of a straightforward presentation of the

path checking method, rather than any theoretical diffi-

culties involved. Thus the method can easily be extended
to include this gate.

Based on this method, four algorithms are presented
for fault detection and fault diagnosis of combinational
and sequential circuits. For both cases, combinational and
sequential, the results obtained from the fault detection
algorithms are used as a basis for the fault diagnosis
algorithms. The diagnosis process will proceed down to the
level of equivalent faults. However, the diagnosis pro-
cess can terminate at any stage if the level of diagnosis
is satisfactory.

The path checking method, as presented in this
thesis, can be extended to cover switching circuits which
include unsensitizible as well as partially sensitizible
paths, i.e., circuits containing redundant circuitry. The
extended method will then be applicable to most switching
circuits, including LSI circuits, that are encountered in

current fault analysis studies.

THE PATH CHECKING METHOD APPLIED TO MULTIPLE

FAULT ANALYSIS OF SWITCHING CIRCUITS

BY

Tze Tzong Chen

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Computer Science

1976

ACKNOWLEDGMENTS

I am grateful to Dr. Carl V. Page, the chairman
of my guidance committee, for his guidance and encourage-
ment during the course of this thesis. My thanks also go
to Dr. Richard J. Reid, Dr. Richard C. Dubes, the late
Dr. Leo Katz, Dr. Weinberg Bernhard, Dr. Christie G. Enke,
and to Dr. Morteza A. Rahimi for serving on my guidance
committee and for reviewing this work.

I wish to express my thanks to the Division of
Engineering Research for their financial support during
the early stage of the writing of this thesis.

Finally, I am deeply indebted to my parents for

their patience and encouragement.

ii

TABLE OF CONTENTS

LIST OF TABLES . . . . . . . . . . . . . . . . . .
LIST OF FIGURES . . . . . . . . . . . . . . . . .
CHAPTER

I. INTRODUCTION AND THE STATE OF THE ART . .

II.

1.1 Definition of Reliable Computing . .
Forms and Causes of Hardware
Failure in Digital Systems . . . .
Examples of Logical Faults . . . . .
Strategies to Circumvent Hardware
Failure in Digital Systems . . . .

Hid H
94» n:

1.4.1 Preventive Type Approaches . .
1.4.2 Corrective Type Approaches . .

1.5 Contribution and Organization of
the Thesis . . . . . . . . . . . .

SWITCHING CIRCUITS AND THEIR FAULT
ANALYS I S C C C . O C C O C C O I O O O O

2.1 Mathematical Models for Switching
Circuits . . . . . . . . . .

2. 2 Logical Faults of Switching Circuits

2. 3 Methods of Test Generation for
Combinational Circuits . . . . . .

Truth Table Method . . . .
Path Sensitizing Method .
The D-Algorithm . . . . .
Poage' 3 Method . . . . .

Boolean Difference Method . .
Chang' s CGEM Method . . . . .

GUI-IBWNH

NNNNNN
wwwuww

2.4 Methods of Test Generation for
Sequential Circuits . . . . . . . .

iii

Page
vi

vii

UWNH

o
0‘

ll
14
14
20
22
23
23
27
35

38

41

CHAPTER Page

2.4.1 Poage's Method . . . . . . . . . . 42
2.4.2 Other Methods of Fault

Detection of Sequential

Circuits . . . . . . . . . . . . 46

III. FAULT DETECTION AND DIAGNOSIS OF COM-
BINATIONAL CIRCUITS BY THE PATH CHECKING
METHOD 0 O O O O O O O O O O C C C C C O O O 4 8

3.1 Some Network Properties of Com-

binational Circuits . . . . . . . . . 49
3.2 Path Sensitization of Combinational
Circuits O O O O O O O O O O O O O O I 53

3. 2.1 Sensitizing a Path . . . . . . . 54
3. 2. 2 Unsensitizible Paths of Com-

binational Circuits . . . . . . 55
3.2.3 Maximal, Non-Maximal and
True Sensitization . . . . . . . 59

.3 Faults of Combinational Circuits . . . . 69
4 Fault Detection of Combinational
Circuits O O O O O O O O I O O O O O O 75

UN
0

3.4.1 The Path Sensitization Table

and Maximal Compatible Sets . . 77
3.4.2 The Path Checking Fault

Detection Algorithm . . . . . . 87
3.4.3 An Example . . . . . . . . . . . . 89

3.5 Fault Diagnosis of Combinational
Circuits O O I O O O O O C O O O O O O 99

3.5.1 The Diagnosis Approach . . . . . . 99
3.5.2 The Path Checking Fault

Diagnosis Algorithm . . . . . . 109
3.5.3 An Example . . . . . . . . . . . . 113

3.6 Characteristics of the Method as
Applied to Combinational Circuits . . . 116

IV. FAULT DETECTION AND DIAGNOSIS OF
SEQUENTIAL CIRCUITS BY THE PATH
CHECKING METHOD 0 O O O O O O O O O O O O O 119

4.1 Some Network PrOperties of Sequential

Circuits . . . . . . . . . ._. . . . . 121
4.2 Path and Path Sequence Sensitization

of Sequential Circuits . . . . . . . . 128

iv

CHAPTER

#05
o o
be»)

4.6

4.2.1 Sensitizing a Path and a
Path Sequence . . . . . . . .
4.2.2 Unsensitizible Paths in
Sequential Circuits . . . . .
4.2.3 Maximal and True Sensitization
of Path Sequences . . . . . .

Faults of Sequential Circuits . . . . .
Positioning the Sequential Circuits

in a Desired, Known State . . . . . .
Fault Detection of Sequential

Circuits . . . . . . . . . . . . . .

4.5.1 The Path Sequence
Sensitization . . . . . . . .
4.5.2 The Path Sequence Checking
Fault Detection Algorithm
4.5.3 An Example . . . . . . . . . . .

Fault Diagnosis of Sequential Circuits

4.6.1 The Diagnosis Approach . . . . .

4.6.2 The Path Sequence Checking
Fault Diagnosis Algorithm . .

4.6.3 An Example . . . . . . . . . . .

4.7 Characteristics of the Method as

Applied to Sequential Circuits . . .

V. CONCLUSIONS AND SUGGESTIONS FOR FUTURE
WORK 0 O O C O C O O O C O O O O O O O C O

5 O 1 conCIuSionS O O O O O I O O O O O O O O

5.2

BIBLIOGRAPHY

Suggestions for Future Work . . . . . .

Page

128
132
136
142
144

150

151

162
166

179
180
186
190

196

198

198
199

202

LIST OF TABLES
Table Page

2.1. The flow table of the machine of
Figure 2.3 . . . . . . . . . . . . . . . . . 20

2.2. Single propagation D-cubes of the com-
binational circuit of Figure 2.5 . . . . . . 31

2.3. Flow tables for good and faulty circuits
for example of Poage's method . . . . . . . . 44

2.4. Product tables for example of Poage's
method . . . . . . . . . . . . . . . . . . . 45

3.1. The PST for Example 3.5 . . . . . . . . . . . . 82

4.1. The PSST for Example 4.5 . . . . . . . . . . . 157

vi

LIST OF FIGURES

Figure Page
1.1. An open diode in an AND circuit . . . . . . . . 4
1.2. A transistor-diode OR circuit . . . . . . . . . 5
2.1. A basic model for combinational circuits . . . 15
2.2. A basic model for sequential circuits . . . . . 16

2.3. A Mealy type state diagram . . . . . . . . . . 19
2.4. Decision elements . . . . . . . . . . . . . . . 21

2.5. A combinational circuit for the path
sensitizing method . . . . . . . . . . . . . 25

2.6. An OR gate and its singular cover and
prOpagation D—cubes . . . . . . . . . . . . . 28

2.7. A combinational circuit for Chang's
me thOd O O O O O O O O O O O O O O O O O O O 3 9

2.8. A sequential circuit for Poage's
methOd I I O O O O O O O O O O I O O O O O O 4 3

3.1. Examples of paths, subpaths, subcircuits,
partial circuits, and constituent

circuits of a combinational circuit , , , , , 53
3.2. A simple combinational circuit with

fan-out reconvergence . . . . . . . . . . . . 56
3.3. Examples of maximally sensitized and

non-maximally sensitized paths . . . . . . . 65

3.4. Examples of truly sensitized paths . . . . . . 68

3.5. Examples of multiple and equivalent
fau1ts O O O O O O O O O O O I I O O O O O O 76

3.6. A combinational circuit with fan-out
reconvergence for Example 3.5 . . . . . . . . 80

vii

4.3.

4.4.
4.5.

5.1.

Graphical representation of the
diagnosis process . . . . . . . . . . .

A sequential circuit for Example 4.1 . .

A sequential circuit containing partially
unsensitizible path sequences . . . . .

A sequential circuit with all paths
sensitizible . . . . . . . . . . . . .

A sequential circuit for Example 4.4 . .
A sequential circuit for Example 4.5 . .
Partially sensitizible paths result

from concatenating circuits C

and C to form an integrated
CircuI£ O O O O O O O O O O O O O O O 0

viii

Page

110

126

133

137
149
154

201

CHAPTER I

INTRODUCTION AND THE STATE OF THE ART

Digital computers are increasingly being relied
upon as an integral part in the day-to-day operations of
various sectors of modern societies. The speed and effi-
ciency of computers in processing massive amounts of infor-
mation have found their applications in almost any branch
of modern life, from government agencies to private indus-
tries, from weather predictions to patient diagnosis, from
research laboratories to factory assembly lines.

A more sophisticated application of computers is
found in the field of system monitoring and control where
computers are programmed to perform a task independently.
A few examples of these might be highway and urban traffic
control, satellite flight control, and factory production
line control.

With the increasing reliance on digital systems,
the problems of their reliability have become a topic of
practical concern and have developed to be an area of
academic interest. In addition, the current trend toward
higher speed, more complexity, and more miniaturization in
digital systems introduces more stringent requirements on

1

reliability standards. The significance of the reliability
of digital systems is self-evident and needs no further

justification.

1.1 Definition of Reliable Computing

 

Various definitions [31] have been proposed for the
term "reliability" of computers. Even though their
phrasings are quite different, they all agree in the more
generic sense. A typical definition is given here as "the
ability to perform its functions correctly and on schedule
even in the presence of errors." In the definition, the
emphasis on "on schedule" and "in the presence of error"
should not be overlooked. "On schedule" introduces the
timing factor which is critical for accurate computing,
especially in real-time computing. The presence of errors
in a digital system is allowed provided it does not affect
the system's ability to perform its functions correctly.
This provides for the possibility of introducing additional
hardware to enhance the levels of reliability of computing.
The definition of reliability given is very general and
ambiguous and hence some specific measures of reliability
are desirable to allow for practical analysis of reli-
ability problems. Some of the commonly used reliability
parameters are lifetime and mean time between average

failure-rate.

1.2 Forms and Causes of Hardware
Failure in Digital Systems

 

 

Errors in the digital system hardware result from
a variety of causes. The following causes are responsible
for most of the circuit faults in the system [31].

a. External environmental interference such as heat
and humidity.

b. Internal environmental interference such as noise.

c. Inappropriate design or construction.

d. Aging and deterioration of hardware with time.

The circuit faults resulting from these causes can
take on various forms. However, the type of faults which
are most widely studied and are also the concern of this
thesis are called "logical faults." These are the faults
which affect the intended logical behavior of circuits.
These faults might be permanent or intermittent. Physical
failures such as an opened or closed circuit in a com-
ponent, or a broken wire in connections, or erroneous design
or construction might cause permanent faults. On the other
hand, noise interference, close design tolerances, aging
and deterioration of components are some causes of inter-

mittent faults.

1.3 Examples of Logical Faults
The following are typical examples of hardware
failure which are represented by logical stuck—at type

faults.

Example 1.1

 

Figure 1.1 shows a diode AND circuit and its
logical representation. The output at y will register 1
volt whenever both inputs x1 and x2 have a voltage of 1 volt
simultaneously. However, if the diode at x1 is open, the
output would be at 1 volt whenever input x2 is at 1 volt.
This situation is equivalent to xl sticking at 1 volt, or

logically xl sticking at 1 if positive logic is assumed.

+V

 

X ope s-a-l
-1 4-Y -———-l

r‘—] 1V
0V

 

 

 

 

x2 I‘
_J__ ___—‘ ‘— A

—_~ ._-

 

Fig. l.1.--An open diode in an AND circuit.

Example 1.2

Consider a transistor-diode OR circuit in Figure
1.2. In this circuit, returning the base voltage to -VB
wilJ.reverse biase the emitter-base and collector-base

junctions and the two diodes and the output voltage VCE

-V

 

 

 

 

 

 

B +Vo I
$3 J
<RL
/
X
l
r-L #l VCE
X
collector 1
X 2
x ’ emitter
2
.___H___..
/l

 

 

 

v‘.

Fig. 1.2.--A transistor-diode OR circuit.

will be approximately equal to the supply voltage V0.

When 1 volt is applied to either or both inputs at x1 and
x2, the transistor will turn on and the output voltage

VCE will drop to zero indicating the presence of inputs at
x1 or x2 or both. In this case, negative logical values
are adopted for the output. Here an open collector lead
will cause the output voltage VCE to be equal to V0
resulting in the output sticking at a 0 logical fault. On
the other hand, a short between the collector and emitter
leads will create a sticking at 1 fault on the output.

Although not all hardware errors can be translated

into stuck-at type logical faults, stuck-at type faults

constitute the main portion of hardware failures encountered

in actual experience.

1.4 Strategies to Circumvent Hardware
Failure in Digital Systems

 

 

There are numerous approaches available to c0pe
with the reliability problems caused by the factors listed
in section 1.2. However, they can be categorized into two

types of approaches, namely preventive and corrective.

1.4.1 Preventive Type Approaches
This type of approach seeks to prevent the causes
of errors from the digital system, or if errors should
occur in the system, finds methods to mask them so that
normal functions of the system still can be maintained in
the presence of these errors.

1. Ensuring proper operational environments and

 

appropgiate operational procedures. Suitable

 

computer room temperature, humidity control and
use of suitable transmission lines are a few
examples of precautions needed to ensure prOper
performance of the system. Establishment and
observance of operational guidelines often would
considerably reduce system down times and failure
rates.

2. Use more reliable components and design. Higher

 

design and manufacturing specifications to sustain

noise levels and power supply fluctuations, heat

and humidity variations are desirable in a reli-
able system. But this approach is dictated by
available technology and economic constraints.

3. Redundancy. This approach uses additional hard-

 

ware to mask certain circuit faults and thus still
maintain correct logical functions in the presence
of these faults. Through this method, any desirable
degree of reliability can be obtained, however, at
correspondingly higher costs.
Considerable research work has been devoted to this approach
to study various redundancy techniques. It appears that
this approach is widely adopted in systems where higher
reliability is desired and repair work is difficult or
impossible.
The first important study on this method was done

by Von Newmann [40] and published in Automata Studies. In

 

which he proposed two configurations of redundancy; one of
which is called "multiplexing." In this configuration more
than one wire is used to carry a single signal. The out-
puts of each logical operation (each signal of which is
carried by more than one wire) are woven through a
"restoring organ" to enhance the reliability of these
outputs for later stages of logical operations. Later
Moore and Shanon [28] introduced "quadrupling" method which
was applied to relay-type networks. This method was

extended by Tryon [39] to develop a method called "quadding"

which applies to logical gate-type circuits with AND, OR,
and NOT decision elements. It requires four times as many
circuits and masks all single faults. There are other
types of redundancy techniques such as the statistical
decision approach by Pierce [31] and the coding theory by

Armstrong [1].

1.4.2 Corrective Type Approaches

Even with the added protection of redundancy, a
computer system cannot be guaranteed to be error-free
during its entire life span. A single signal error in all
its redundant wires, for example, would be detectable at
the outputs of the circuit and thus could cause system
malfunction. It is through the continuing testing and
correcting approach that a system can be ensured to main-
tain normal operations at all times.

The corrective procedures in these approaches
involve three stages.

1. Applying the developed tests to the system to
determine whether it is functioning properly
(error detection).

2. Determining the causes of malfunction and loca-
tions of faults in case the system is malfunction-
ing (error diagnosis).

3. Taking corrective measures to restore the system

to normal operations.

Of the three stages, the third stage is most straight-
forward and is a simple task once the initial two stages
have been accomplished. While the first and second stages
involve complicated circuit functional analyses and test-
ing and have been subjects of research. Numerous methods
in error detection and diagnosis of digital circuits have
been developed. However, the work is far from complete,
especially in the area of sequential circuits.

The common underlying approach of all the methods
is designing a test set for the circuit which will detect
all faults in the circuit. They differ only in the
methods by which these tests are obtained. Examples of
these methods will be presented in Chapter II, while a
brief discussion now will set the stage for them.

The most simple and straightforward method in
error detection and diagnosis is the truth table method.
In this method an error is assumed, the truth tables for
the fault-free circuit and for the faulty circuit are com—
pared. This comparison will reveal the inputs which
detect this fault. This is done for each fault to be inves-
tigated. This method is effective only for relatively
small circuits, but not for medium or bigger size circuits
duerto the considerable amount of computations and storage
needed.

The path sensitizing method is more effective and

faster than the truth table method. It has been widely

10

investigated and its ideas are extended to develop new
methods. The idea is to propagate an assumed error to an
output terminal along a sensitized path in a forward-
tracing phase, and to trace back from assigned signal
points to the inputs to find input tests for the error in
the backward-tracing phase. One disadvantage of the path-
sensitizing method is that a test may not always be found
even though it exists.

Roth's [35] D-algorithm method represents a sophis-
ticated extension of the path sensitizing method. Sophis-
ticated because, instead of treating the error itself as
a unit of operation, this method puts all the tests of all
possible errors at a logical gate in a "D—Cube." The
tests of the circuit are calculated by applying a set of
operational rules called "D-Calculus" on these cubes in
the "D—Drive" phase (forward-tracing phase) and in the con-
sistency operation (backward-tracing phase). This method
has the advantage that it can detect a wider range of
faults than stuck-at type faults. The number of D-cubes
in a circuit is directly prOportional to the number of
logical blocks. This fact would impose less demands on
storage in computations. Also it is shown that the
algorithm will always find the test for a given error, if
it exists.

Other algebraic methods by Poage [32], Sellers et

a1. [36] and Chang [5] for finding the tests for

11

combinational circuits have also been developed. They all
utilize the algebraic properties of the Boolean expressions
of the circuits to obtain the tests. As is with most of
the previous cases, the big disadvantage of these methods
lies in the storage requirements in the computations of
these tests.

Relatively few papers on the fault detection and
diagnosis of sequential circuits have been published.
Hennie [l4] preposes a general procedure for synthesizing
checking experiments on sequential circuits having a dis-
tinguishing sequence. His procedure is based on the
logical behavior of the circuit. Other papers by Moore
[29], Seshu and Freeman [37], Meyer [25], Hsieh [15] also
approach this study at the logical behavior level.

The path checking method, which is an extension
of the path sensitizing method, is the topic of this
thesis. The advantage Of this method is that this
method can be applied to both combinational and sequential
circuits and thus allows error analysis of sequential cir-
cuits at the network level.

1.5 Contribution and Organization
of the Thesis

 

Although a considerable amount of research has been
devoted to fault analysis of combinational circuits with
respectable results, not very much attention has been given

to sequential circuits, even though they constitute the

 

12

basic foundation of digital computing circuitry. This

results partly from the complexities involved in the

analysis of sequential circuits. Also in those published

works in this area, the approach used in the diagnosis
process has mostly been at the state diagram level of the

sequential circuit. Yet, it seems that an approach which

studies the fault problems at the circuit level possesses

advantages.
This thesis studies fault analysis of combinational
and sequential circuits at the circuit level using the path

checking method. It appears that the path checking method is

a suitable approach for attacking the complexities of signal

flows in sequential circuits caused by feedback. Through

this method, a systematic view of the complex signal flows
in the circuit can be obtained, especially in the case of

sequential circuits, where signal flows and their relevance

to the state diagram become apparent. Although the com-

binational case is also treated in the thesis, the sequen-
tial case is intended to be the major contribution.

Chapter I defines the problem area and gives a

brief discussion of published works in this area. Chapter

II presents some background materials, preliminaries and

terminology of the field. Examples of published methods

are also presented in this chapter. Chapter III will
in<=lude all the related materials in the detection and

diagnosis of combinational circuits by the path checking

13

method. The sequential circuit case is treated in
Chapter IV. Chapter V presents a summary and conclusion
of the thesis, discusses unsolved problems and suggests

materials for future research.

CHAPTER II

SWITCHING CIRCUITS AND THEIR

FAULT ANALYSIS

This chapter is devoted to a review of the related
background materials in switching theory and fault analysis
of switching circuits. Some representative examples of
published results in the field are also included to show
various methods used to approach the subject matter. This
review, however, is far from complete and interested
readers are referred to the original works for more
detailed discussions.

2.1 Mathematical Models for
Switching Circuits

 

 

The term "switching circuits" is used to include
both combinational and sequential circuits which together
form the basic computing hardware of digital systems.
These circuits are usually represented by a mathematical
model which describes their functional behavior in Boolean
algebra. In the case of sequential circuits, another

mathematical model called the seqpential machine is used

 

to describe the logical behavior of sequential circuits.
The sequential machine can be projected into a schematic

14

15

diagram called the state diagram which is a convenient way

 

to express the logical behavior of the sequential circuit
[27].

Consider a combinational switching circuit having
n inputs x1, liiin, and m outputs zj, lijim, as shown in

Figure 2.1.

 

 

 

 

 

 

 

X 7 AZ],
1 . .
comb1nat1onal
x IP22
2 - .
' logic .
o g '
xn % *"sz

 

 

Fig. 2.1.--A basic model for combinational circuits.

Definition 2.1

 

A switching circuit is a combinational switching

 

circuit (or combinational circuit) if its output variables

 

zj, lijim, can be expressed as m Boolean functions of its

input variables, xi, liiin,

z. = f. (x., x

j J 1 2, . . . xn) lijfim.

The outputs of a combinational circuit depend
entirely on the current inputs and thus are time inde-
pendent. In a sequential switching circuit (or sequential
circuit), however, the outputs are functions not only of
present inputs, but also of past inputs as well. These

past inputs are stored in a set of delay elements and are

16

fed back as part of the inputs in the next input-output
reaction. These feedback variables are called EEEEE
variables [27, 23].

Consider a switching circuit with n inputs xi,
liiin, m outputs zj, lfijim, and p state variables yk,

likgp, as shown in Figure 2.2.

 
   
   

z
x 21
x 2
x combinational zm

logic

Fig. 2.2.-~A basic model for sequential circuits.

Definition 2.2

A switching circuit is a sequential switching
circuit (or sequential circuit) if its output and next
state variables can be expressed by two sets of Boolean
functions. The output variables zj, lijfim, are expressed
by.m Boolean functions of input and present state variables
xi, liiin, yk, likip. The next state variables y'k, likip
are expressed by k Boolean functions of input and present

state variables.

17

N
ll

j fj (x1, x2, ..., xn, yl, y2, ..., yk) lijim

Y'k = 9k (x1, x2, ..., xn, yl, yz, ..., yk) likip

Sequential circuits are classified as either
"synchronous" or "asynchronous." Synchronous sequential
circuits are characterized by the use of clock pulses to
synchronize the signal propagation in the circuit. Asyn-
chronous sequential circuits are not provided with such
synchronization control and thus sometimes possess £332

conditions caused by asynchronized reaction times which

 

causes circuit malfunction.

Another mathematical model used to logically
describe a sequential circuit is commonly adopted [27].
Consider the same sequential circuit with input variables
X = {xi; liiin}, output variables 2 = {zj; lijim}, and

state variables Y = {yk; likip}. Let

i = XI be an input,

x=a
w = Z|Z=b be an output,
3 = lily:c be a present state and
s' = YI be a next state of the sequential circuit,

Y=c'

Where a, b, c, and c' are vectors of signal values which
the sequential circuit assumes. The sequential circuit as
given by Definition 2.2 can now be interpreted as follows.

(liven the sequential circuit originally in state s at time

18

t, it will produce an output w and enter into the next
state 3' at time t+1 after being given an input 1.
Formally, this can be described in a mathematical

model called the sequential machine.

 

Definition 2.3

 

A sequential machine M is defined as an ordered 5—
tuple (Q. I, W, T, m) where

1. Q is a finite set of internal states,

 

2. I is a finite set of inputs,
3. W is a finite set of outputs,
4. T is a transition mapping of a subset of O x I
onto a subset of Q,
5. w is an output mapping of a subset of Q x I onto
a subset of W.
The transition mapping 1 defines the next state
3'60 and the output mapping defines the output mew of the
machine originally in state 380 with input ieI.

A sequential machine is connected if given sleQ,

 

there exists 3280 and an input sequence 1* such that

T (31, i*) = 32’

A sequential machine is strongly connected if given
81, s2 8 Q, there exists i* such that T (sl, i*) = 32.
A sequential machine can be represented in a

graphic form called the state diagram. In a state diagram,

 

every state is represented by a circle, and every transition

19

mapping represented by a directed line between the corres-

ponding circles with the corresponding input and output

shown along the line. Figure 2.3 shows a Mealy type state

diagram.

ll/wl

 

l2/w1

Fig. 2.3.--A Mealy type state diagram.

A sequential machine can also be represented in a

tabular form called the flow table [27]. Every state of

the machine is represented by a row and every input is

represented by a column. The next state and output are

then placed in the entry as specified by the transition

mapping like s/w. Table 2.1 shows the flow table of the

sequential machine of Figure 2.3.

The basic logical elements used to realize the

SWitohing circuits are of two types; relay contacts type

and decision elements type. The decision elements type is

more popular in practical applications and is the only type

20

Table 2.1.--The flow table of the machine of Figure 2.3.

 

 

 

 

5‘1 12
S1 sz/wl S3/w2
s2 s3/w2 s3/w2
s3 s3/w2 sl/w1

 

 

considered in the thesis. This type generally includes
AND, OR, NOT, NAND, and NOR. These elements are enough
to realize most of the switching circuits found in real
applications. Their schematic notations are shown in

Figure 2.4.

2.2 Logical Faults of Switching Circuits
A physical fault is a physical defect of a com-
ponent or wire in a circuit which may cause the circuit to

malfunction. Such a fault is called a logical fault if it

 

affects the proper logical behavior of a switching circuit.
Most of the logical faults (or simply faults) can be inter-
preted as stuck-at type faults in which a line input to or
output from a decision element sticks at a fixed signal
Value and thus is not assuming the proper signal values as

exPE< :t ed .

21

 

 

 

o~ :D— w—

AND gate OR gate NOT gate

NAND gate NOR gate

 

 

 

Fig. 2.4.—-Decision elements.

The following definitions present some of the
important concepts found in many fault analysis studies

[4, 28, 31].

Definition 2.4

 

A test for a fault (or faults) of a combinational
circuit is an input vector which, when applied to the com-
binational circuit, can detect the presence or absence of
the fault (or faults) through the comparison of the output
vector thus produced with the output vector of the same
test applied to a fault-free copy of the combinational
circuit. A test for a fault (or faults) of a sequential
circuit is similarly defined with the distinction that the
test may be a sequence of input vectors.

The same meaning for detection as used in Definition

2.4 applies to the following definitions.

22

Definition 2.5

 

A fault is detectable if there exists at least one

 

test which detects this fault. A fault is undetectable

 

if it is not detectable.

Definition 2.6

 

Two faults are equivalent if there does not exist

 

a test which detects one but not the other.

Definition 2.7

 

A test for a combinational circuit is a set of

 

input vectors such that:
1. It detects all detectable faults of the combina-
tional circuit,
2. No subset of it can detect all the detectable

faults of the combinational circuit.

Definition 2.8
A test for a sequential circuit is a sequence of
input—state vectors such that
1. It detects all detectable faults of the sequential
circuit,
2. No subset of it detects all detectable faults of
the sequential circuit.

2.3 Methods of Test Generation For
Combinational Circuits

 

 

Most of the published methods of test generation

apply to combinational circuits only. In this section, a

23

review of some of the best known methods is presented to
show the different approaches available for generating

tests for combinational circuits.

2.3.1 Truth Table Method

The truth table method is the most basic and

 

straight-forward way to generate tests. Assuming a single
fault in a combinational circuit, the truth tables of both
the good and the faulty copy of the circuit are compared
to obtain the input vectors which produce different output
vectors for both circuits. The same procedure is done for
every detectable fault. Complete detection tests can then
be built from these results.

Though simple and straight-forward, the consider-
able amount of storage and computations involved make this

method unattractive for even circuits of moderate size.

2.3.2 Path Sensitizing Method

The one-dimensional path sensitizing method has

 

been widely studied and applied in developing other methods
for fault analysis of combinational circuits. Armstrong
[1] of Bell Telephone Laboratories and Stieglitz of IBM are
Prominently linked with this method even though they never
Published their works on this method.

The idea is first to arbitrarily find a sequence of
gates starting from the site of fault leading to an output

Edge so that the fault can travel along this path to the

24

output edge. This portion of the method is called the

forward tracing phase. In the forward tracing phase, all

 

the input edges to the gates along this path are assigned
signal values such that the output edge at the end of the
path responds solely to the signal value at the edge of

fault. In this way the path is sensitized.

 

After setting up the sensitized path in the
forward tracing phase, a primary input vector to the cir-
cuit must be found which realizes the signal values assigned
to the input edges of the gates along the path. This

portion of the method is called the backward tracing phase.

 

The input vectors thus found are tests for the fault. An

example will best illustrate the procedure.

Example 2.1

 

Consider the circuit in Figure 2.5 in which edge
e7 sticks at 1 (s-a—l). Suppose the sequence of gates
selected 13 G7, G12, 613, G15 Wlth the correspond1ng path
of edges p1 = e7, e10, e12, e13, e15, 22. To sen31tize

the path and test if e7 can assume the signal value 0, let

e7 = e10 = e12 = e13 = e15 = 22 = 0'
x4 = 1,
x5 = O,

and e = l,

25

.cocums mswuwuwmcmm sumo can now uwsouwo HMGOADMGHABOO <I|.m.~ .mflm

 

 

 

mu 30 mm .
mam fillA-_n“”¢llllllll
IllAmnmfi? mx 4|$WWll/Kll
ma All

0 NH
vx

HIMIm

 

 

 

fl

 

 

 

 

 

26

where x4, x5, and e8 are so assigned such that the path

is sensitized. This completes the forward tracing

phase. In the backward tracing phase, one or more primary
input vectors are to be found which yield the signal values
assigned thus far. To do this, the components x1, x2,

and x3 of the input vector have to be decided to satisfy

e7 = 0 and e8 = 1. To satisfy e = 0 let x3 = 1. To

7

realize e = 1, there are three possibilities,

8

‘0

x = 1, x2 0

1
x1 = 0, x2 = 1;
or x1 = 1, x2 = 1,

which can form three different input vectors. Each of
these can be used for sensitizing the chosen path. They
are

(l, 0, 1, 1, O) = (x1, x2, x3, x4, x5),

(0, 1, l, 1, O), and

Applying one of the three tests to the combinational cir-
cuit, one finds
a. e7 s-a-l 1f 22 = 1, or
b. e7 does not s-a-l if 22 = 0.
Several observations concerning this method are

made as follows.

27

a. Since sometimes it is necessary to make a choice
out of several possibilities in assigning signal
values during the backward-tracing phase, it can
happen that inapprOpriate choice may lead to a
conflict with assigned signal values. If this
occurs, one must back up and try the other alter-
natives until the conflict is resolved and a test
is found.

b. The method is not algorithmic. It has been shown
that a test cannot be found using this method for
a combinational circuit even though it exists.

c. Finally, this method has been proven very useful
in practice and the computer running time and
storage requirements are economical.

The failure of the path sensitizing method to find
a test for a combinational circuit where there is one is
caused by the fact that only one path is sensitized at one
time using this method. To overcome this defect, Roth
develOps a method which sensitizes all possible paths
simultaneously from the site of fault to the circuit out-

puts.

2.3.3 The D-Algorithm

Roth's D-algorithm [35] represents the first

 

algorithmic approach in generating tests for combinational
Circuits. The formulation of the method is in terms of a

Calculus called D-calculus for cubical complexes formed

 

 

28

for the logical elements of the circuit. The concepts and

terminology as used by him are briefly explained as follows.

a.

Singular cover

A singular cover of a gate is a compact truth table

 

of the gate which can be used to describe any
logical element. A singular cover of a two-input
OR gate is shown in Figure 2.6 in which x repre—

sents a "don't care" signal value.

 

 

x l l 0 d d
0 0 0 propagation
singular cover D-cubes

Fig. 2.6.--An OR gate and its singular cover and propagation

D-cubes.

Propagation D-cube

The propagation D-cubes of a gate contain all of

 

the possible sensitized paths through that gate
and are derived from the singular cover of the

gate. For the OR gate in Figure 2.6, two propa-
gation D-cubes are obtained as shown in the same
figure where d represents the "variable" on that

path.

29

c. Primitive D—cube of a fault

The primitive D-cubes of a fault on a gate are

 

identical to the prOpagation D-cubes for the gate.
However, the primitive D-cubes of a fault repre-
sent the tests for that fault.

d. D-Intersection
Sensitized paths starting from the sites of faults
to the output edges of a combinational circuit are
formed by interconnecting propagation D-cubes

using D-intersection operations.

 

Roth uses a binary operator 9 to define the D-
intersection. Some of the binary operations are shown as

follows.

d 9 x = d
l 9 x = 1
x Q 0 = 0
d 9 d = d
x Q d = d

The discussions of the D-algorithm are best given

through an example.

Example 2.2
Consider the circuit of Figure 2.5 with fault f =

e7 s-a-l. The propagation D-cubes of all the gates in the

30

circuit are shown in Table 2.2 where d' represents the
complement of d.
The D-algorithm is divided into two phases, the

D—drive phase and the Consistency phase. In the D-drive

 

 

phase, all possible sensitized paths for a fault are
formed leading from the fault site to the circuit output
edges. Input vectors to the circuit compatible with the
signal values assigned thus far are then found in the

consistency phase.

A. The D-drive phase.
1. Label the primitive D-cube of the fault as test

cube 0, tco.

0 3 7 9
to = 1 d' d' d'

The variable d' means that the corresponding edge
should have a signal value of 0 if the fault is
absent and 1 otherwise.

2. Define the D-fanout set of a test cube to as the
set of gates fed by the edges of tc having signal

variable d or d'. The D-fanout set dfo of too is

dfo = {11, 12}.

3. The next step is to D-intersect the test cube with
the propagation D-cubes of each gate of its D-

fanout. The propagation D—cubes of {11} are

Figure 2.5.

31

Table 2.2.--Single propagation D—cubes of the combinational circuit of

 

edges

gates

10

11

12

13

14

15

 

 

 

d'

dl

dl

 

 

 

11

d.

 

ll

dl

 

12

 

12

 

13

 

13

 

14

 

14

 

15

 

 

15

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

l

..1

32

 

 

tc01 _ 3 6 7 9 10 ll
_ 1 0 d‘ drid' d"

tc02 = 3 4 7 9 10 12
1 1 dr d' d' d"

4. The D-drive phase continues with successively
repeating steps 2 and 3 for each new test cubes
obtained at each stage until either the test cube
reaches an output edge or ends in a non-output
edge. The final test cubes obtained for the
example are

012 _ 3 6 7 9 10 11 14 z
tc ‘ 1 o 61*31 a' a 0 dl' C

tc0111 _ 3 4

t

tc0221 _ 3 4 5

t

\

t

tc01111 =

c0112 _ 3 4 6 7 9 10 11 12 14 z

C0222 _ 3 4 5 7 9 10 11 12 13 14 15 z

C0223 _ 3 4 5 7 8 9 10 12 13 14 15

 

7 9 10 11 12 13 14 15
d' d1 d"

I
H
H
dUI
om
D:
04

1
DJ
0.:
Q:

 

7 9 10 11 12 13 14 15
d' d d' d' d' d"

p...-
H
O
00‘
D:
Q:

q

 

1 1 0 d' d' d' 0 d' d' d' d' d' '

 

 

— 22 c
1 1 o d' 1 d' d' d' d' d' d' d' '
3 4 5 6 7 8 9 10 11 12 13 14 15 22 C
1 1 o o d' 1 d' d' d d' d' d' d' d' '

33

Those test cubes reaching an output edge as indicated by a
C above represent the sensitized paths between the fault
site and an output edge. These test cubes are now ready

for the consistency phase.

B. The Consistency phase.

In this phase, one traces along each test cube
reaching an output edge, from those edges of known signal
values towards the input edges of the circuit in order to
determine signal values for those edges not yet assigned.
To do this, one starts with D-intersecting the test cube
with the singular cover of the gate whose output edge is
the highest numbered edge of known signal value (0 or 1)
on the test cube. The process is repeated for all other
edges of known signal value on the test cube. This is done
in descending numerical order until either all the input
edges of the circuit have been assigned signal values or a
conflict of signal assignments exists, in which case, the
path cannot be sensitized.

012

Considering tc , one finds, from the circuit of

Figure 2.5

= e = 0.

e = 0 + e 15

14 13

012

The D-intersection of tc with the singular cover

of Gl3 results in

34

Similarly, the D-intersections of tc012

singular covers concerned find

x4 = 0,
and x1 = 0, x2 = 0,
or x1 = 1, x2 = 0,
or x1 = 0, x2 = 1

Thus the computations of the consistency phase

to012 result in three tests which sensitize the path

P 21. The tests are

012 = x3' e7' e9' 811'

1
t012 = (0, 0, l, 0, 0) = (x1, x2, x3, x4, x5),

2

t012 = (0! 1I 1I 0I 0)!
t3 = (1 o 1 o 0)
012 I I I I -
Since e7 and 21 have different signal values as can be
on tc012, the fault f will show up as 2 assuming the

1
signal value 0 upon applying one of the tests above to

circuit.
Different tests can be obtained from the other
test cubes, all of which will detect the same fault.
This concludes the example and the discussions

the procedures of the D-algorithm method. The compu-

with other

on

seen

the

of

tations for even a single fault are still quite lengthy as

35

demonstrated in the example. In actual situations, tests
for multiple faults are more frequently demanded. It is
possible to apply the D-algorithm on multiple faults by
computing tests for each individual fault and then con-
catenating these tests. However, the total computations

needed will be quite substantial.

2.3.4 Poage's Method

Poage [32] developed a mathematical method for
generating a minimal set of tests to detect all single and
multiple faults. His method applies to both gate and
relay contact combinational circuits. He also developed a
method for test generation for sequential circuits which
will be discussed later in this chapter.

His method is a sort of calculus for faults. For
every edge in the combinational circuit, three Boolean

variables called fault parameters are defined as follows.

 

jO = 1 iff edge j s-a—O
jl = 1 iff edge j s-a-l
jn = 1 iff edge j is fault-free

At any given time, only one of the three fault parameters
can exist. Then if edge j carries a signal having the

Boolean value w, a w* is defined for the edge as:

w* = w ° jn V jl'

36

The expression means that edge j will have a signal value
of 1 either it is fault-free carrying the signal value 1
or it s—a-l. Similarly, a w*' is defined for edge j to

give the conditions for its signal value to be 0 as

*, = , . . .
w w 3n V 30.

This last expression can also be obtained by complementing

w* using the following relations.

.,=. .
3n 30 V 31
.,=. .
3l 30 V 3n
..=. .
3o 31 V 3n

Now, for a given fault-free combinational circuit
realizing some Boolean function f, the corresponding f*
and f*' can be calculated by successively substituting
each edge of the circuit with its * expressions. The
formulations of f* and f*' can start either from the input
edges working towards the output edges or from the output
edges working backward towards the input edges. After com-
plete substitutions, the f* and f*' will be functions of
input variables and fault parameters of the circuit edges.
The * expressions for a given set of faults are then
obtained by substituting the corresponding fault parameters

with the faulty signal values to realize the fault

37

conditions. Let f* and f*' be the * expressions of the
combinational circuit with the given set of faults, a test
t which detects these faults is calculated using the

following relation
t = (f* - f*') v (f*' v f*).

Poage's method is easy to use for relatively small
combinational circuits. But for large scale combinational
circuits, the computations required in calculating the *
expressions would be quite substantial. Also the method
is based on the assumption of the existence of tests. Such

is not the case in real situations.

2.3.5 Boolean Differen
Sellers et a1. [36] developed another mathematical

method called the Boolean difference method for generating

 

tests for combinational circuits. For a combinational
circuit with an output variable f and input variables x1,
x2, ..., xn, the Boolean difference of the output variable

with respect to one of the input variables xi is defined as

xi+l' ..., x2) +

Xi+1’ coo, Xn)

where + is the EXCLUSIVE OR Operation. If Q£_ = 0, then f

dx.
1
is independent of xi. On the other hand, if %E— = 1, f
i
will be a function of xi and then

38

df

. ——— is a test for x. s—a—O
1 dxi 1

and x! §£_ is a test for x. s-a-l.
1 dxi 1

Tests for all the input variables and edges of the circuit

are then combined to form tests for the entire circuit.

2.3.6 Chang's CGEM Method
Chang [5] developed a mathematical model called the

Complete Gate Equivalent Model for combinational circuits.

 

Using this model, a set of Boolean expressions in the form
of sums of products are formulated to completely describe
the logical functions realized by a combinational circuit.
Each product term of the expressions represents a set of
paths which he calls a zj-l or zj_0 set depending on the
signal value at the output when such a set is sensitized.

Faults occurring on the set will cause shrinkage or growth

 

of the product term of the set corresponding to a decrease

or increase of the number of logical gates covered by

the set. To detect the faults, every product term must

be investigated for shrinkage or growth. The tests for
the combinational circuit are thus obtained from testing
every product term for shrinkage or growth. The method is

explained using one of his examples as follows.

Example 2.3

 

The Boolean expressions for the circuit in Figure

2.7 as obtained from its CGEM model are:

39

.ponums m.mcmcu Mom vesouflo Hmcoeumcwneoo ¢I|.h.~ .mwm

 

 

QHH

MHH

 

 

 

De

 

 

q}.-- .-.,—._.. .--

 

on

 

 

 

 

 

 

 

where xi means xi assumes 0 and Ei is the Boolean expression

for z. 0
1

of E"

To detect shrinkage on i 1, for example, an

1x3
input vector, Ml' can be found by intersecting this term

with the complement of every other term of E1.

 

 

M1 = x1x3 (x2x3) (x3x4) x5 = x1x2x3x5

Since §1x3 will cause 21 to assume 1 as indicated by E1

assuming 1 under a fault—free situation, the above calcula-
tion can be interpreted as M1 will detect a shrinkage of
ilx3, i.e., stuck-at-O faults on paths represented by

§1x3, if all other terms assume 0. In effect x1x3 is

sensitized with M1.

To detect a growth on ilx3, i.e., stuck-at-l faults,

every variable of x1x3 must be investigated since a growth

can occur to each variable. The calculations are as
follows,

M8 = x3 E1 = xlx2x3x5,

M9 = x1 E3 = xlx3x4x5.

Thus {M1, M8, M9} will detect all faults on paths of x1x3.
Doing this for every term of the expressions and finding a

41

minimum covering for all the M's terms obtained, a test is
formed.

Chang's method is straightforward and his CGEM
model is flexible to suit a wide range of combinational
circuits. However, separate tests are needed for fault
location when using his method.

2.4 Methods of Test Generation for
Sequential Circuits

 

 

Fault analysis of sequential circuits is a more
involved and complicated task than that of combinational
circuits. First, tests must be generated for every possible
state of the sequential circuit. Hence the amount of com—
putations required to generate the total set of tests for
the sequential circuit is prOportional to the number of
states it possesses. Second, there is the problem of
initiating the sequential circuit to some known state
before testing can be performed on it. This initialization
procedure is in itself a necessary portion of any fault
detection technique for sequential circuits.

Most methods known for fault detection of sequen-
tial circuits approach the problem at the state level;
while relatively few methods treat the problem at the
circuit level. The approach of Poage's method can be

classified as belonging to the latter category.

42

2.4.1 Poage's Method

Poage's method [33] for test generation for sequen-
tial circuits is essentially an extension of his method for
lcombinational circuits. The feedback loops of the sequen-
tial circuit are assumed open to make the circuit combina-
tional. The formulation of the good and faulty circuits
are then done using his method for combinational circuits.
Also a reset mechanism is assumed to be available to set
the circuit to some known starting state. After these
initial steps, the flow tables corresponding to the good
and faulty circuits are built. The main part of Poage's
method involves combining these flow tables into a com-
posite fault table from which optimal test sequences for
given faults are derived. The method is demonstrated

using an example as follows.

Example 2.4

 

The circuit for the example is shown in Figure 2.8

with the set of faults T,

T = e. at, eg}

where e: and e? indicate ei s-a-l, ei s-a-0 respectively.
Conceptually Opening the feedback and applying

Poage's method for combinational circuits to the resulting

circuit, one gets the output and next state expressions

for the good and each faulty circuit as follows.

 

 

 

Q

 

 

 

 

 

 

 

es
62 ._.—._.
a
96
/
\ Y
Fig.

For good circuit
M

circuit
M2

NH

For e

circuit
M3

OOH

For e

circuit

”4

For e

are

circuit

M5

FOI' e

U10

 

 

 

43

 

 

 

.\ y

2.8.--A sequential circuit for Poage's method.

x'y V xy'
XY

x'y
x

x' V y'
XY

x V y
XY

xy'
XY

Corresponding to these Boolean expressions, the flow tables

for the good and faulty circuits are built as shown in

Table 2.3.

44

Table 2.3.--Flow tables for good and faulty circuits for
example of Poage's method.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

X X X
T o 1 T2 0 1 T3 0 1
0 0/0 1/0 y 0 0/0 0/1 y 0 1/0 1/0
1 1/0 0/1 1 1/0 0/1 1 1/0 0/1
X X
T4 0 1,- 35.....- ,_ .0--- .. ,1.
y 0 0/1 1/0 y 0 0/0 1/0
1 t 1/1 1/1 1 l 0/0 l 0/1

 

The main idea of Poage's method is to find input
sequences which will produce different outputs for the good
and the faulty circuits. To do this, the next step is to

form a set of product tables by pairwise concatenating the

 

flow table of the good circuit with that of each of the
faulty circuits. This concatenating procedure starts with
the common starting state of the sequential circuit. The
procedure terminates as soon as a product output with
different components appears in the product table.

The product tables thus formed for the example are
shown in Table 2.4 where the product outputs with different
components are marked in circles.

Test sequences for a given fault are derived from

the corresponding product table. The test sequences are

45

Table 2.4.--Product tables for example Of Poage's method.

X X

me T2 0 T x T3 ' 0 l

l
yy2 0 0 00/00 lO/. yy3 0 0 i 01/00 ll/00

o 1 l01/oo 1w.

1 1 ill/00 00/11

 

 

 

 

 

X X
T x T4 0 1 T x T5 1 o “1
o o 00/00 11/00 0 o i00/oo 11/00
yy4 1 1 11/00 01/11 yy5 1 1 :10/00 00/11
0 1 01/00 11/. 1 o 1 10/00 on.

simply input sequences which, when applied to the corres-
ponding product table, yield the product output with dif-
ferent components. For example, the test sequences for

detecting e1

product table T x T 2

2 can readily be seen as

t = 0n, 1 n 3 0.

21

To find a single optimal test sequence to detect
all of the given faults of the sequential circuit, Poage

forms the sequential fault table which is simply a com-

 

posite table Of the product tables. The Optimal test
sequence can then be found from this sequential fault
table. Using his technique, the Optimal test sequence is

found to be

in which 0, 1 covers T x T2 and T x T3,
0, 1, 0, 1 covers T x T2, T x T3 and T x T5 and
0, l, 0, l, 1 covers T x T2, T x T3 and T x T4.

Poage's method in finding Optimal test sequences
provides a closer look at the fault detection problem at
the circuit level. It is also straightforward and easy
for computer implementation. But his method involves cal-
culations for each individual fault and hence is not very
economical from a practical VieWpoint.

2.4.2 Other Methods Of Fault Detection
Of Sequential Circuits

Most other methods in designing test sequences for
sequential circuits are based on the input-output relations
Of the corresponding sequential machine. The earliest work
using this approach is done by Moore [29] in his gedanken-

experiments. In this experiment, he treated the sequential

 

machine under test as a black box on which input sequences

 

are to be applied. Considering the set of sequential
machines consisting Of the fault-free machine and its

failed COpies each containing one of the permissible faults,
the input-output experiment induces a partition on the set
with respect to the outputs Obtained. Successive experi-
ments will refine the partition and will finally identify
each machine Of the set with one Of the permissible faults

or as fault-free.

47

Moore's approach was widely applied by other
researchers in designing other methods for generating test

experiments called checkipg experiments for sequential

 

machines. In most cases, these methods apply to sequential
machines possessing certain characteristics. Hennie [14]

introduced the transition checking approach for generating

 

checking experiments for sequential machines which possess

a distinguishing sequence (an input sequence used to iden-

 

tify the initial state Of the machine) and do not increase
the number Of states from malfunction. Hsieh [15] developed
several procedures for generating checking experiments for
sequential machines which do not possess any distinguish-
ing sequences. His methods, however, are based on other

types Of characteristic sequences; the compound distinguish-

 

ing sequence, the resolving sequence, the compound resolving

 

 

 

sequence, and the simple I/O sequence.

 

Researchers like Kime [l7], Kohavi [18, 19],
and others have published their results along the same
line.

Some authors have suggested addition of extra
external hardware, modification of the sequential machine
or embedding the machine in a larger equivalent machine
[17, 18, 22] to create certain desirable characteristics
for designing checking experiments. Detailed discussions

Of these methods will not be presented in the paper.

CHAPTER III

FAULT DETECTION AND DIAGNOSIS OF
COMBINATIONAL CIRCUITS BY THE

PATH CHECKING METHOD

The path checking method approaches the task Of
fault detection and diagnosis of switching circuits by
checking all the paths of the circuits to ensure that they
propagate the signals correctly. Through this process, a
set of detection tests are Obtained which can be used for
detection purposes. The detection phase will locate the
given faults to some general areas Of the circuits. The
diagnosis phase will then proceed based on these results.

In this chapter, the path checking method as used
in the fault detection and diagnosis Of combinational cir-
cuits is presented. Two algorithms for fault detection and
diagnosis are formulated using this method.

The type Of combinational circuits treated using
this method possesses the following characteristics:

a. Multiple inputs and multiple outputs.
b. Path fan-out reconvergence allowed.

c. All paths being sensitizible.

48

49

Thus the only restriction imposed on the type of combina-
tional circuits is that every path of the circuit be sen-
sitizible. This, however, will not place any limitations
on the range Of real applications Of this method, since
unsensitizible paths represent redundancy and their removal
will not affect the logical behavior Of the circuits.

Faults treated are both single and multiple, but
are of permanent stuck-at type. The type Of logical ele-
ments considered are as discussed in Chapter II.

3.1 Some Network Properties of
Combinational Circuits

 

 

A brief study Of some of the network structural
properties of the combinational circuits as they relate to
the path checking method will be presented here. This
discussion will help one visualize the combinational cir-
cuits from the "path" point Of view.

A combinational circuit can be viewed as a set Of
interconnected paths such that the leading and trailing
edges Of the paths form the input and output edges of the
circuit. For a single-output combinational circuit all of
its paths will eventually converge tO the single trailing
edge. All fan-out paths residing in it will have to meet
one another before reaching the trailing edge. But in the
case of a multiple-output combinational circuit, fan-out
paths need not meet one another, since they may lead to

different output edges Of the circuit. The multiple-output

50

combinational circuit is characterized by the existence Of
fan-outs branching to different output edges Of the circuit.
Such fan-outs do not reconverge. Other fan-outs may lead
to the same output edges thus forming fan-out reconvergence.
Consider a combinational circuit C with n input
edges xi, liiin, m output edges zj, lijim and the set Of q
labelled edges E = {ek, lfikfiq}. The edges are so labelled
such that the output edge Of any logical element will have
a label with higher order than that Of the label assigned
tO any input edge of the logical element. Also fan-out
edges (edges which are branches of a common edge) are
assigned different labels. A pgpp and a subpath are

defined as follows.

Definition 3.1

 

A pgpp p Of C is a sequence Of edges p = £1, £2,
..., i such that
1. 21, the leading edge Of the path, is an input edge
Of C,
2. 2p, the trailing edge Of the path, is an output
edge Of C, and
3. £1 and £i+l' liiip-l, are either respectively an

input edge and the output edge of the same logical

element or £i+l is a fan-out edge of ii.

51

Definition 3.2

 

A subpath p3 of C is a section of a path p such that
ps includes either the leading edge or the trailing edge
of p.

The number Of paths in a multiple-output combina—
tional circuit is of interest in estimating the amount of
computation needed in designing tests. For a multiple-
Output combinational circuit possibly with fan-out recon-
vergence, the number Of paths is found in the following

theorem.

Theorem 3.1

 

The number Of paths in a multiple-output combina-
tional circuit C with n input edges, m output edges, k
fan-outs and A logical elements are

(n -1)

:3

II

:3

+
I[v1W

:5

I

1...:

II

a

+
II M 2°

Gi

where nFi is the number Of branches at fan-out Fi and

is the number Of edges feeding logical element 61'

nGi

Proof: To compute the number Of paths from the
number of input edges, since every path must start with an
input edge, the number of paths is the sum Of this value
plus extra paths introduced with fan-out branches. For a
- 1 will be the

fan-out F branching into n paths, n

F F

extra paths introduced with this fan-out. TO Obtain the

number Of paths from the number Of output edges,

52

interchange the roles Of inputs and outputs, with each
logical element playing the role of a fan—out. Q.E.D.

The concepts Of subcircuits, partial circuits,

 

and constituent circuits of a combinational circuit are

 

presented here as they will prove useful in later dis-

cussions.

Definition 3.3

 

A subcircuit within a combinational circuit

 

includes all the subpaths of the circuit leading to an

edge (need not be a trailing edge) Of the circuit.

Definition 3.4

 

A partial circuit within a combinational circuit

 

includes a set of paths sharing an output edge Of the com-

binational circuit as their common trailing edge.

Definition 3.5

 

A constituent circuit Of a multiple-output com-

 

binational circuit includes all the paths sharing an output
edge Of the combinational circuit as their common trailing

edge.

Example 3.1

 

These definitions are illustrated in the combina-
tional circuit C of Figure 3.1. Paths include p1 and p2;
subpaths include p81 and p52; P is the partial circuit

formed from p1 and p2; while C2 is the subcircuit formed

53

 

 

 

 

 

p1 = X1' 94' e6' 2 Pz = x2' 92' 35' e6' 2
psl = Xl’ e1' e2 P52 = x2' e2

P = {P1192}

C2 = {Psl'Psz}

C

2 C

Fig. 3.1.--Examples Of paths, subpaths, subcircuits,
partial circuits, and constituent circuits Of
a combinational circuit.

from pSl and p52 with the subscript 2 indicating that the

edge e2 is its output edge and the constituent circuit Cz

corresponds to the combinational circuit C itself.

3.2 Path Sensitization Of
Combinational Circuits

 

 

If a path Of a combinational circuit is to be
checked for correct signal propagation, it must be gaggi-
Eiggd. However, an input vector sensitizing a path needs
not necessarily guarantee its sensitization due to the
existence of faults. This section discusses the problems

Of absolute path sensitization and designs input vectors

54

which ensure absolute path sensitization for combinational

circuits.

3.2.1 Sensitizing a Path
When a signal propagates through a logical element,

it may assume one of two possible modes, sensitizing or

 

dominant. For example, the signal value 0 would propagate
through an OR gate sensitizingly, since for it to pass
through this gate, all other edges incident on it should
take on the sensitizing signal 0 too. On the other hand,

1 can propagate through the OR gate regardless of other
signals incident on the gate, i.e., dominantly. Thus the
OR gate will be a sensitizing gate to 0 and a dominant gate
to 1. This is true of all the logical elements considered
in this thesis. To sensitize a path, all the edges incident
on it must assume the corresponding sensitizing signals and
thus the signals propagating through the path are sensi-

tized.

Definition 3.6

 

A path is said to be sensitized if a change of the

 

signal value at its leading edge alone will cause a change
of the signal value at its trailing edge.

A signal can propagate through a path even though

 

the path is not sensitized. A signal is said to propagate

 

through appath if, traveling down the path, it maintains

 

the same signal value when going through a gate of even

55

parity, and changes its signal value when going through a
gate of Odd parity. Also the path is said to prOpagate the
signal. A signal propagating through a path is said to be
of 0-type for the path if it shows up as 0 at the trailing
edge; it is of l-type if it shows up as 1. However, for a

path to be tested, it still has to be sensitized.

Definition 3.7

 

A path p is said to pass an s-type signal, indicated

 

by ps, if it is sensitized and its s-type signal propagates

through it. P is said to be tested toppass s if it is

 

sensitized and its s-type signal is applied to its leading
edge. It is tested if both signals are applied to its
leading edge. And it is checked if it passes both signals.

Even though combinational circuits considered in
this thesis are required to possess sensitizible paths only,
generally, combinational circuits may include unsensitizible
paths. Unsensitizible paths may also result from faults in
the circuits.

3.2.2 Unsensitizible Paths of
Combinational Circuits

The unsensitizibility of a path in passing a signal
is caused by the fact that some edges incident to the path
are not free to assume the corresponding sensitizing
values because of fan-out reconvergence. If a path is

unsensitizible in passing a signal s, then there is at least

56

an edge on the path at which an E-type fault (assuming E at

the trailing edge when detected) is not detectable.
Consider, for example, the simple combinational

circuit in Figure 3.2 with three paths, p1 = x1, e5, 2,

p2 = x2, e3, e5, z and p3 = x2, e4, z. In the circuit,

p1 is unsensitizible in passing both signals; p2 is unsen-

sitizible in passing 0 and p3 is completely sensitizible.

To sensitize p1, e3 should assume 0 and e4 assume 1 causing

an impossible situation for x For p2 to pass 0, x

2' 2
should assume 0 which makes the sensitizing edge e4 impos-

sible to assume 1. Thus x1 s-a—O and e5 s-a-l are unde-

tectable. Actually the circuit is a unitary circuit and

e represents redundancy and hence can be removed from the

5
circuit resulting in the simple circuit consisting of p1

 

 

 

 

 

 

only.

f1

s-a-O
x1 =§ ____w

r »
es
93 s—a-l

X2 r’ J

 

 

Fig. 3.2.--A simple combinational circuit with fan-out
reconvergence.

57

Definition 3.8

 

A path is s—sensitizible if it can be tested to

 

pass 3, otherwise it is not s-sensitizible or a:

unsensitizible. It is sensitizible if it can be tested to

 

 

pass both signals, partially sensitizible if it can be

 

tested to pass only one signal and cannot be tested to pass
the other.

Partially sensitizible and unsensitizible paths
pose extreme difficulties in fault analysis of the com—
binational circuits. First, they may be caused sensitizible
through the presence of other faults and second, a group of
faults consisting of both detectable and undetectable
faults may become undetectable. For example, e4 s-a-l in
Figure 3.2 causes p1 sensitizible and e4 s-a-l concurrently
with x1 s-a-O is not detectable.

The elimination of partially sensitizible and
unsensitizible paths from a combinational circuit will not
alter the original logical behavior of the circuit. This

is proved in the following theorem.

Theorem 3.2

 

For every combinational circuit in which not every
path is sensitizible, there exists a combinational circuit
with all paths sensitizible which realizes the same logical
behavior.

Proof: Given a combinational circuit C with

1

partially sensitizible or unsensitizible paths, another

58

combinational circuit C2 with all paths sensitizible will
be built from C1 by removing all paths which are 3-
unsensitizible (s = 0 or 1). An unsensitizible path is
also s-unsensitizible. If a path p of Cl is s-
unsensitizible with an input vector i, then there exists at
least one gate on p at which at least one of the incident
edges assumes the corresponding dominant value. Let such a

gate which is closest to the trailing edge of p be called

the front gate for i. Since p is s-unsensitizible, there

 

exists a front gate for every s-type input vector (i.e., an
input vector which assigns the s-type signal to the leading
edge of p) to p. Of all the front gates, let G be the gate
closest to the leading edge of p. Then the edge e of p
feeding G is never sensitized for all the s-type input
vectors to p and its s-a-§ fault f is not detectable. If

E is dominant to G, then f will prOpagate down p to some
edge e' feeding G' and the fault f': e' s-a-s' is equivalent
to f. Since f (f') is undetectable, one can assign the
sensitizing value E (s') to e (e') permanently, or equiva-
lently, remove e (e') from C, without affecting the logical
behavior of Cl' Edges on the subpath between the leading
edge of p and e (e') which are not shared by other paths
can also be removed. Sequentially removing all the s-

unsensitizible paths from C1, one arrives at the equivalent

circuit C2 with all paths sensitizible. Q.E.D.

59
3.2.3 Maximal, Non-Maximal and
True Sensitization
If a path of a combinational circuit is sensitized
with an input vector, it may not actually be sensitized
under a fault detecting situation. This is due to the
fact that a faulty subpath may be used as a sensitizing
subpath and thus the path in question is not actually
sensitized with the input vector. To prevent such situ-
ations from affecting a detection test, one should seek

input vectors which assure maximal or true sensitization

 

for every path of the circuit. To do this an incident sub—

circuit needs to be maximally assigned if possible.

 

Definition 3.9

 

A subcircuit is said to be maximally assigned a

 

signal value 5 or simply s-maximally assigned, if, with an

 

input vector, s prOpagates through every subpath of it.

Otherwise it is said to be s-nonmaximally assigned.

 

If a subcircuit Ci is s-maximally assigned, then
its output edge ei will assume the signal value 3 unless

ei sticks at E. This is proved in the following theorem.

Theorem 3.3

 

If the output edge ei of a subcircuit Ci does not
stick at E, the input vector i, with which Ci is s-
maximally assigned, will assign s to ei.

Proof: If ei does not stick at E, then there exists

at least one subpath of C1 which is free of E-type faults.

60

With the input vector i, s will propagate through this
subpath and ei will assume 5. Q.E.D.
For example, with an input vector i = (x1, x2, x3,
x4) = (0, 0, 0, 0) applied to the circuit of Figure 3.1,
the output edge e5 of subcircuit C will assume 0 unless

5

e5 s-a-l. E1ther x1 and x2 s-a-l or x3 and x4 s-a-l w1ll

result in e5 s-a-l. Otherwise i will cause e5 to assume 0.
When a path p is sensitized to pass 3, some of its

incident edges are also simultaneously s-sensitized if they

assume the sensitizing value 5. Their correctly assuming

the sensitizing values in sensitizing p is of no concern

because being sensitized, the values they assume are detected

at the trailing edge of p. However, the other edges called

strictly sensitizing edges, which are not simultaneously

 

sensitized with p, must be guaranteed to assume the correct
sensitizing values in order for p to be actually sensitized.
To do this the corresponding sensitizing subcircuits,

called strictly sensitizing subcircuits must be maximally

assigned if possible.

Qafinition 3.10

A path p is said to be s-maximally sensitized, if

 

on being sensitized to pass 5, every strictly sensitizing
subcircuit is E-maximally assigned. If this is possible,

it is said to be s-maximally sensitizible. And it is said

 

to be maximally sensitizible if this is possible for both

 

61

values of s. If p is not s-maximally sensitized, it is

said to be s-non-maximally sensitized.

 

Maximal sensitization means actual sensitization
and a path will always be maximally sensitized if possible.
However, a path might not be maximally sensitizible if the
combinational circuit possesses fan-out reconvergence. A
path is maximally sensitizible if it doesn't involve fan-

out reconvergence.

Theorem 3.4

 

A path p with the trailing edge 2 of a combina-
tional circuit C is maximally sensitizible if no fan-out
paths with the same trailing edge reconverge before
reaching 2.

Proof: Since every subpath of C which is incident
on p is part of a path with z as the trailing edge, hence
it does not involve fan-out reconvergence. Thus each such
subpath is free to assume its corresponding sensitizing
value for the sensitization of p. This implies that every
subcircuit incident on p can be maximally assigned its
corresponding sensitizing value. Q.E.D.

From this theorem, one finds that every path of a
fan-out reconvergence free combinational circuit is

maximally sensitizible.

62

Corollary 2.1

 

Every path of a combinational circuit free of fan-
out reconvergence is maximally sensitizible.

Proof: Since the combinational circuit is free Of
fan-out reconvergence, from the above theorem, every path
is thus maximally sensitizible. Q.E.D.

The path sensitization of combinational circuits
with fan-out reconvergence is more involved than was found
in the case of combinational circuits free of fan-out
reconvergence. The complication arises from the fact that
not every path of the circuit is maximally sensitizible.
For those paths which are not s-maximally sensitizible, one
seeks, instead of s-maximal sensitization, to make sure
that every non-maximally assigned strictly sensitizing
subcircuit is capable of providing the right sensitizing
value.

For a path p which is s-non-maximally sensitized.
consider one of its strictly sensitizing, non-maximally
assigned subcircuit Ci with the sensitizing value 3. Since
it is not E-maximally assigned, its subpaths can be divided
into two sets for this particular input vector: those
through them 5 propagates to the output edge ei of Ci and
the others E does not propagate through. The first set are
responsible for providing the sensitizing value 5 and at
least one subpath of this set should be able to pass 5 in

order to make ei assume ;. Thus, in this connection,

63

one seeks a path pi which contains such a subpath of Ci

and that pi pass E.

Definition 3.11

 

Given p s-non—maximally sensitized with an input
vector i and with one of its strictly sensitizing, non-
maximally assigned subcircuits C1' the output edge of which
is ei. Let E propagate through a subpath pSi to ei pro-
viding the sensitizing value E in the sensitization of p.

A path p' containing pSi is called a critical sensitizing

 

path of p with i. The signal value E is the critical

sensitizing value of p'. PSi is called a critical sensi—

 

 

tizing subpath, with the critical sensitizing value E.

 

Note that, with respect to a particular strictly
sensitizing, non-maximally assigned subcircuit Ci' there
are possibly more than one critical sensitizing paths.
Each of these passing the sensitizing value E would be
sufficient in sensitizing p, with respect to C1' One can
say that p depends on one of these paths, with respect to
Ci' in its sensitizing with an input vector i. It will be
expressed in a notation as follows.

i: ps/{(Ci. pii): (Cj

s.
, pjj); .....}

The notation means given p non-maximally sensitized to
pass 5 with an input vector i, p depends, for actual

sensitization, on p1 passing 51' with respect to Ci' and

on pj passing sj with respect to Cj' etc. If there is only

64

one such input vector i, or where i is understood, 1 will
be omitted. Ci and Cj will also be omitted if confusion
will not hence occur.

These definitions are illustrated in the following

example.

Example 3.2

 

In the combinational circuit with fan-out recon-
vergence as shown in Figure 3.3, p1 = x1, e18, z is l-
maximally sensitized, p6 = x4, e8, e13, e17, e19, z and
p8 = x5, e15, e17, e19, z are 1-non-maximally sensitized
with the input vector indicated in the figure, where the
subcircuit C16 is not maximally assigned. P3 = x2, e11,
616' e19, z is the only critical sensitizing path for C16’

To actually sensitize an s-non-maximally sensi-
tizible path p with some input vector i, then, with each of
its strictly sensitizing non-maximally assigned subcircuit,
at least one of the critical sensitizing paths, p', must be
E-maximally sensitized directly or indirectly with some
other input vectors. Indirectly, because, like p, it may
be E-non-maximally sensitizible. Then the same process
for searching actual sensitization must be done for p'.
However the search is guaranteed to terminate with positive
results as will be proved later. Thus the actual sensi-
tization of p to pass 3 must be accompanied by a set of

input vectors which, directly or indirectly, maximally

65

.mnumm couwuemsmm madewxmelcoc can OONADHmcom Saamswxme mo moamsmxuin.m.m .mwm

ma

mam

 

 

 

 

 

 

 

 

 

 

 

IIQ >\r H mx
A H 24 H
o a a a
ma m
il ex
H
H H mm
. Sm
I . .
o a q mx
0H NH D\\\ o o
O m _
Z

 

 

 

 

66

sensitize at least one critical sensitizing path passing E
for each non-maximally assigned strictly sensitizing sub-

circuit.

Definition 3.12

 

Given

1: pS/{(C1, p1); (C2, P2); ...3 (Cn. pn)}

and a set of input vectors I, where each pi, liiin, is a
critical sensitizing path with respect to the strictly
sensitizing subcircuit Ci with the critical sensitizing

value E, p is said to be s-maximally sensitized of first

 

order with 1, within I if each pi is E-maximally sensitized

with some i' e I. Similarly p is s-maximally sensitized

 

 

of second order if each pi is either E- maximally sensitized
or E-maximally sensitized of first order within I. And p

is s-maximally sensitized of nth order if each pi is either

 

E-maximally sensitized of (n-l)th order or less.
With the above definitions, true sensitization of a

path can be conveniently defined as follows.

Definition 3.13

 

A path p is said to be s—truly sensitized with an

 

input vector 1, within a set of input vectors I if there
exists a number n such that p is s-maximally sensitized

of nth order with 1, within I.

67

Example 3.3

 

To illustrate these definitions, consider the
circuit of Figure 3.3 with two of the input vectors i1
shown in Figure 3.3 and i2 in Figure 3.4. Paths p6 and p8
(see example 3.2) are l-non-maximally sensitized in Figure
3.3 with the critical sensitizing path p3 = x2, e11, e16,
e19, 2. But p3 again is O—non-maximally sensitized in
Figure 3.4 with the critical sensitizing path p1 = x1,
818' z. Finally pl is maximally sensitized in Figure 3.3.
Thus p6, p8 and p3 are all truly sensitized within i1 and
12.

The question of whether the search for true sen-
sitization will always end with positive results will have
to be answered during path sensitization. In the case of
combinational circuits in which every path is sensitizible,
the answer is yes. Because otherwise such circuits con-
taining faults on the paths not truly sensitizible only
would be still proved fault-free. But it can be proved
that if a combinational circuit has every path sensitizible,

then at least one fault is detectable if it contains at

least one fault.

Theorem 3.5

 

In a combinational circuit with every path sen-
sitizible, every s-non-maximally sensitizible path is s-

truly sensitizible.

68

.msumm Omuwuwmcmm masuu mo mOHmEOXMII.v.m .mHm

 

 

 

 

 

 

 

 

 

o ado
ma mm a
m
[ fix
I H
O .
H mm a
em _ o
I
no
mo_
H Sm AVAIL
o Ham
Nx
0 HR cam o

 

 

69

Proof: First of all, if a combinational circuit
with every path sensitizible, then at least one fault is
detectable if it contains at least one fault. Otherwise
it would mean that the reduced circuit resulting from the
original circuit with the faults is equivalent to the
original circuit. This in turn would imply that there were
redundant edges in the original combinational circuit.
However, a combinational circuit with every path sensi-
tizible is free of redundant edges.

Now if there existed a path which was not s-truly
sensitizible, then each of its critical sensitizing path
would not be E-truly sensitizible and so on. Thus there
would exist a set of paths such that for each of the set,
there would be nothing to depend on in its s'-sensitization
for some 3'. Hence its s'-sensitization cannot be guaran-
teed. Because of this, there could exist a set of faults
on this set alone in the whole circuit which would be
undetectable. This is in clear contradiction to the sen-

sitizibility assumption. Q.E.D.

3.3 Faults of Combinational Circuits
In this section, faults in the combinational cir—
cuit will be analyzed and interpreted in terms of path
checking. Faults interact in the combinational circuit to
form undetectable faults, multiple faults and equivalent
faults. These phenomena will also be studied from the

viewpoint of path checking. It appears that the total

70

fault structure of the switching circuit can be clearly
interpreted through this viewpoint.
Faults propagate as do signals. A fault f: e s-a-s

with e feeding a gate G is said to be sensitizing to G if

 

s is sensitizing to G, it is dominant to G if s is dominant

 

to G. Thus faults will propagate through gates to which
they are dominant and stop at gates where they are sen-
sitizing. A fault is a O-type fault on a path p if it
would cause the trailing edge of p to assume 0 when sen-
sitized and l-type otherwise. So if a path is checked,
then, being able to pass both signals, it is free of stuck-

at faults.

Theorem 3.6

 

If a path is actually sensitized and tested to
pass both signals, it is free of stuck—at faults iff it
is checked.

Proof: Given a path passing both signals, and
suppose there are some stuck-at faults on it. Consider
the fault closest to the trailing edge. Since the path is
sensitized, the fault will appear at the trailing edge
regardless Of the signal applied to the leading edge con-
tracting to the assumption. Thus the path is free of
stuck-at faults. Conversely, if the path is free of stuck—
at faults, then since it is guaranteed to be sensitized,

it should pass both signals. Q.E.D.

71

If every path of a combinational circuit is indi-
vidually determined for its ability in passing both signals,
then all the detectable faults in the circuit can be located
down to equivalent faults. This will be discussed in the
diagnosis process later. Faults interact to form detect-
able, undetectable, single, multiple and equivalent faults

within a given fault picture.

 

Definition 3.14

 

A fault picture is the set of all faults verified

 

and detectable that occur at any given stage of fault
analysis of a combinational circuit under test.

A single fault is a fault which is by itself

 

detectable and can be exactly located. An s-type single

fault will occur at the output edge of an s-type maximal

 

faulty subcircuit.

 

Definition 3.15

 

A subcircuit Ci of a combinational circuit C is

an s-type faulty subcircuit if every path of C containing

 

a subpath of C1 is such that either it is E-unsensitizible
within the given fault picture (due to other faults) or
that the E signal cannot propagate through it. C1 is an

s-type maximal faulty subcircuit if there does not exist

 

another s-type faulty subcircuit which includes Ci.
The following theorem finds the locations of single

faults.

72

Theorem 3.7

 

A fault of a combinational circuit C is an s-type
single fault iff it occurs at the output edge of an s-type
maximal faulty subcircuit Ci with which there exists at
least a path of C containing a subpath of C1 which is E-
sensitizible.

Proof: Consider an s-type fault f on some edge ei
which is the output edge of a subcircuit Ci' Since ei
sticks at the s-type fault, so every path of C containing
a subpath of Ci must be either E-non-sensitizible or E-
sensitizible but cannot pass the signal E. Since f is
detectable, then at least one such path p is E-sensitizible.
Also there exists at least a path p' of C containing the
subpath between f and the trailing edge of p such that p'
passes E. Hence f doesn't propagate down to p'. On the
other hand, given Ci’ since ei cannot assume the E type
signal whenever it is E- sensitized, it sticks at the s-type
fault. And since it is E-sensitizible along p, its stick-
ing at the s-type fault is detectable. Q.E.D.

When every path containing a subpath of an s-type
maximal faulty subcircuit is E-non-sensitizible, within a
given fault picture, then the fault at the output edge of
the subcircuit is undetectable. This is due to the fact
that faults occur on all the critical sensitizing paths of
every path along which the fault in question is being E-

sensitized. This phenomenon causes undetectable faults,

73

multiple faults and equivalent faults during the diagnosis
process and will be called fault interaction. A multiple
fault consists of a set of individual faults which are

detectable only as a group.

Definition 3.16

 

A multiple fault is a set of faults such that these

 

faults are detectable only as a set.
First consider undetectable faults not within a
maximal faulty subcircuit. These faults will be called

uncovered undetectable faults. Faults within a maximal

 

faulty subcircuit are not detectable and are not of con—

cern. These faults also occur at the output edges of the
maximal faulty subcircuits. But in this case, not a path
containing a subpath of the maximal faulty subcircuits is

E-sensitizible.

Theorem 3.8

 

A fault of a combinational circuit C is an s-type
uncovered undetectable fault iff it occurs at the output
edge of an s-type maximal faulty subcircuit Ci with which
every path of C containing a subpath of Ci is E-
unsensitizible.

Proof: Let f be an s—type uncovered undetectable
fault which occurs on some edge ei which is the output edge
of some subcircuit Ci' Since f does not propagate down

along some path which contains it, Ci must be maximal. And

74

since not one path containing a subpath of C1 is E-
sensitizible, f is not detectable. On the other hand,
given Ci and the fact that every path of C containing a
subpath of Ci is E-non-sensitizible, then every s-type fault
in Ci is undetectable which is equivalent to ei sticking
at the s-type fault which is undetectable. Q.E.D.
Uncovered undetectable faults might interact among
themselves to form multiple faults. An uncovered unde-
tectable fault by itself (without other uncovered unde-
tectable faults) is undetectable. However, such a fault,
say of s-type, might become detectable if at least one path
containing a subpath of its s-type maximal faulty subcir-
cuit becomes E-sensitizible and hence the fault in question
becomes E-sensitized along the path. This will occur if
some other uncovered undetectable faults propagate down
along the corresponding sensitizing paths, due to another
faults, to provide the correct sensitizing values. In
other words, an uncovered undetectable fault becomes
sensitized with other uncovered undetectable faults. If a
set of such uncovered undetectable faults are mutually

sensitizing, then they form a multiple fault. Notice that

 

each individual fault cannot be individually sensitized.

Theorem 3.9

 

A multiple fault f is formed from a set of mutually

sensitizing uncovered undetectable faults.

75

Proof: Since each individual fault of f is unde-
tectable, and detectable as a set, it must be an uncovered
undetectable fault. And since it is undetectable without
the other individual faults of f, it must be sensitized with
the rest of f. Q.E.D.

Finally, addition or removal of undetectable faults,
both covered or uncovered but uninteracting, from a given
set of faults can create an equivalent set of faults. This
is obvious since the added or removed faults are undetect-

able, no input vector will detect the change.

Example 3.4

 

Consider the circuit of Figure 3.5 in which f1,
3, f7 and f11 are detectable faults. Given these faults,

18 and f9 are each by itself undetectable and are detect—

able together. Also f

f
f
17 is undetectable. Addition of it
to {f7, £11} results in z2 s-a-l. Thus {f7, £11} 15
equivalent to fzz: 22 s-a-l.

3.4 Fault Detection of
Combinational Circuits

 

 

In this section, the design of detection tests for
combinational circuits based on the path checking method
is discussed and an algorithm for forming such tests is
presented. The main purpose of a detection test is to
determine whether a circuit is fault-free or faulty, but
not to locate the faults which is the objective of a diag-

nosis process. However, one of the characteristics of the

76

.muasmu unmam>wsvm can mamwuass mo moamawxmtu.m.m .mwm

 

 

 

 

 

N
N
545

 

 

mam

Astana .ma

mo

 

 

 

 

 

 

 

 

 

h
HIMIm m
i; bun
HNQ CFHU aHIMIm stHv D
. cam
mun
a. {hills 2.
ma
» m m as Alarm Ham
claim an x m
«x
cam

 

 

 

 

NH
mam a

mo Astana .amo

 

 

 

 

77

path checking method is that the results of a detection
test will indicate the approximate areas of faults of a
combinational circuit if it is determined to be faulty.
Thus the results of a detection test will be used for the
diagnosis algorithm discussed in the next section.

The basic principle behind the path checking method
is to make certain that every path can pass both signal
values 0 and l in order to prove that it is fault-free.
That principle is used here in synthesizing detection tests.
But since the presence of faults can prevent actual
sensitization, hence the detection tests should be designed
such that every path of the combinational circuit is s-
maximally sensitized or, if impossible, s-truly sensitized
to ensure its actual sensitization. It will be proved
later in the section that a combinational circuit is fault-
free iff every path of it is checked.

3.4.1 The Path Sensitization Table and
Maximal Compatible Sets

The main point in designing detection tests for a
combinational circuit is that each of the input vectors
used in the tests should s-maximally sensitize the paths
being sensitized with the input vector. For those paths
not s-maximally sensitizible, then their s-true
sensitization will be required within the input vectors
included in the tests. Such an input vector is called a

maximal compatible input vector or mci. For a given

 

78

combinational circuit, a set of mci's can be found from
which the detection tests will be formed. Such a set is

called the maximal compatible set, MCS, of the combina-

 

tional circuit and it will be shown to be unique for a
given combinational circuit.

The MCS is built from the path sensitization

 

table, PST. The PST is a table which includes all the
input vectors sensitizing the paths of a combinational

circuit.

The Construction of the PST

 

Consider a multiple-output combinational circuit
with fan-out reconvergence C with ni input edges, nO
output edges and a total of ne edges including input and
output edges with each edge uniquely labelled. Fan-out
edges succeeding the fan-out points are differently

labelled. Let there be np paths.

P = {pi; liiinp}

The PST consists of input vectors sensitizing every
path of P and is built as follows:
1. There are ne columns corresponding to the ne edges
of C.
2. For every path p, there are two rows to test p
pass 0 and l denoted by p0, pl respectively.
3. For any given row corresponding to some p passing 1

(0 or 1) pl, assign the corresponding sensitizing

79

values to edges incident on p and i to edges on

p with even parity and I to edges on p with odd
parity between the edges and the trailing edge of
p.

4. Enter signal values to edges which can be deter-
mined through fan-outs and NOT gates, from edges
already assigned values. Also the input edges to
OR gates whose output edges having been assigned 0
and the input edges to AND gates whose output
edges having been assigned 1 can also be deter-
mined.

5. Rows correSponding to the same constituent circuit
are grouped together (for convenience).

Except for the arrangement of the rows within it,
the PST thus formed is unique. Notice that only those
edges on the paths, incident on the paths and edges related

to them are assigned values.

Example 3.5

 

Consider a 7-input 2-output combinational circuit

C, as in Figure 3.6, with a total of 23 edges and 10 paths.
P = {pi; 131110}

where

p2 = “2' 98' e18'

80

.m.m wamemxm “Om monomuo>coomu HOOIOMw sues aesouwo Hmsowuocwneoo «11.0.m .mwm

.N A

 

 

Hialm m

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Sm
_
_ omm
m
0-.-. mm x [Q] :
Ham Humum me
..i um
36
m
m
l
_
31‘“

19'

There are two constituent circuits Cz and C22

1
each consisting of five paths.

CZ]. = {p1, p2! p3! p4! p5}

C22 = {P6I p7I p8! ng P10}

The PST will be a table of 20 rows, 2 for each path, and
23 columns corresponding to the 23 edges of C. The table
is shown in Table 3.1. Each row is labelled p? indicating
path pi is sensitized to pass x. Three types of entries
have been assigned values; all other entries still remain
blank. Those entries on the path sensitized are assigned
values according to their parities. For example, x1,

e

and z of p 0 assume 0 so that p is sensitized to pass
18 1 1 l

0. The second type are those which are incident on the

Table 3.1.--The PST for Example 3.5.

82

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

810 11 e12 e13 14 e15 16 17 e18 19 20 21 21
0
pl 0 1 O
1
pl 1 1 1
0
92 0 1 0
1
pz 1 1 1
0
p3 o o 1 o 1 o o
1
p3 1 1 1 1 1
0
p4 1 1 o o 1 o 0
p41 o o 1 1 1 1 1
0
ps 0 1 o o
1
o 1 1
95 1
o
96 o o o
1
1 o
96 0
p70 o o 1 1 1 o o o 0
p71 1 1 o 1 1 1 o 1 0
98° 1 1 o o o o 1 o 0
p81 1 1 o 1 1 1 o 1 0
99° 1 1 o o o o
1
p o o o 1 o 1
9
p10° o o o 1 o o
p 1 o o o 1 o 1
10 1

 

 

 

83

path; these entries should assume the corresponding sen-
sitizing values. For p1, there are e8 and e19 assuming 0
and 1 respectively to sensitize p1. The third type are
those entries whose values can now be determined through
and e will of course assume the same

2 9

value as e8 and are so assigned.

fan-outs. For p2, x

The Forming of the MCS

 

The PST lists the minimum requirements for the
paths to pass the signals. A set of the rows of the PST
might be compatible to each other and thus can be combined
to form a new row and the individual paths are then simul-

taneously sensitized to pass the signals.

Definition 3.17

 

A set of rows of the PST are compatible to one

 

another if there are no contradictory entries on the same
column (i.e., 0 and 1 not on the same column). A maximal

compatible set of rows is a compatible set such that it is

 

not a subset of another compatible set. A maximal com-

 

patible row is formed by combining all the rows of a

 

maximal compatible set of rows through intersecting the
entries of the same column (the intersection of x and
blank is x).

The first step in forming the MCS is to form the
maximal compatible rows for each constituent circuit of C.

For example, continuing with the preceding example, pl0

84

and p20 can be combined to form a maximal compatible row

1 l .
for Czl and p9 and p10 can be comb1ned for C22.

_ o o
v11 ' {pl ' pz }

(OIOIIIIIIOIOIIIIIIIIloll-lilo!)

1 1
25 ' {p9 ' p10 }

<:
l

(IIIlolollllllIlolollolllllolllll)‘

Each of the maximal compatible rows vi represents a
set of paths simultaneously sensitized. Hence vi repre-
sents some partial circuit Pi being sensitized to pass some
5. The blank entries of vi represent the strictly sensi-
tizing subcircuits Ci's incident on Pi and they will be
maximally assigned, if possible.

In the second step, the blank entries are free to
assume any values except for those entries on fan-out paths.
For entries not on fan-out subpaths within each Ci’ assign
the same type of signal values as the output edges ei of
C1' Then all related entries which can be determined thus
far through fan-outs, NOT gates, output edges of OR gates
assuming 0 and output edges of AND gates assuming 1, are
thus determined. Fan-out entries are finally assigned.
Each fan-out will assume all the values without causing
contradiction of assignments, i.e., both 0 and 1 if
possible. In this step all the entries of vi corresponding

to the constituent circuit Czi will be determined.

Thus, for example, vll and v25 become

V (OlolllolllIololololllIlolllolllllol)I

11

v25 = (IIlolololllIlololllolollolllIlolllll)0

In the final step, all the maximal compatible rows
are again combined to form maximal compatible rows for the
entire circuit C. Those entries undetermined thus far are
unrelated in even maximal sensitization and are free to
assume any values. Their corresponding input edges are
assigned, say 0 and thus all the entries are determined.
The rows now obtained are maximal compatible input vectors
and the whole set is the MCS. For example, combining v

11'

v25 one finds the mci

14 = {V11' V25} = (X1' X2' x3' x4' x5' x6' x7)

(0,0,1,0,0,0,1).

A mci is non-maximally assigned if its partial

 

circuit is not maximally sensitized. With each mci non-
maximally assigned, those paths not maximally sensitized
need a set of critical sensitizing paths passing the
corresponding critical sensitizing values for the paths
to be truly sensitized.

is

For the example, the dependence set of i4

0

. o 1
14- pl . 92 /{pS }.

86

Thus every s-maximally sensitizible path of C can
be thus sensitized with an input vector of the MCS.' Also
every s-truly sensitizible path of C is thus sensitized

with an input vector of C and within the MCS.

Theorem 3.10

 

Every s-maximally sensitizible path is s-maximally
sensitized with some input vector of the MCS.

Proof: Let piS

be s-maximally sensitizible in the
combinational circuit C. Then in being sensitized to pass
5, every strictly sensitizing subcircuit Ci incident on p

can be E-maximally assigned. Since this is possible, it

is done in forming the MCS. Q.E.D.

Theorem 3.11

 

Every s-non-maximally sensitizible path is s-truly
sensitizible within the MCS.

Proof: Let PiS not s-maximally sensitizible in the
combinational circuit C. Then pi is s-truly sensitizible
within all the input vectors of C. Thus there exists a
set of input vectors with the corresponding sensitizing
values that pi depends on. Further every path pj of the
set is s'-maximally sensitizible with the corresponding
critical sensitizing value 5'. Now, from Theorem 3.10, pj
is s'-maximally sensitized with some input vector of the
MCS. Hence pi is s-truly sensitized within the MCS. Q.E.D.

The set MCS thus formed is unique.

87

Theorem 3.12

 

The MCS is unique.

Proof: First all the steps are performed in a
definite sequence. Second, for each step, the entries are
assigned definite values except for fan-out assignments in
the final step. But here fan-outs are assigned all pos-
sible non-contradicting values. Also maximal compatibili-
zation should produce unique results. Q.E.D.

3.4.2 The Path Checking Fault
Detection Algorithm

The Path Checking Fault Detection Algorithm can

now be conveniently formulated. Given a combinational

circuit C with the set of paths
P = {pi; 1:1:np},

a fault detection algorithm to detect the presence of
faults in C is formulated as follows.
Step A. Form the MCS for C.
Step B. Form the detection tests T for C. A detection
test t e T is formed in the following way.
1. It consists of mci's of the MCS.
2. Every p: is included in t for liiinp, s =
0 and l.
3. Every p: is either s-maximally sensitized or
s-truly sensitized within t.

4. It is not a subset of another test.

88

Step C. Apply a t e T to C. If every path is checked,
then C is fault-free, otherwise it is faulty.
The validity of the algorithm is proved in the following
theorems. First the existence of a detection test is

proved.

Theorem 3.13

 

There exists at least a detection test t as defined
in the algorithm.

Proof: The only point that needs be pointed out is
that if a path p is s-truly sensitizible only, then it
depends on a set of paths which is each s'-maximally
sensitizible for some 3'. Since every s'-maximally sen-
sitizible path is s'-maximally sensitized in the MCS,
hence p is s-truly sensitizible within the MCS. Q.E.D.

The validity of a test is proved next.

Theorem 3.14

 

A multiple-output combinational circuit is fault-
free iff a detection test detects no faults. It is faulty
iff the detection test detects the presence of faults.

Proof: If the circuit is fault-free, then certainly
the test will not detect any faults. On the other hand, if
the test detects no faults, then since every path is
actually sensitized, maximally or truly, it is guaranteed
to be checked, the existence of faults would have been

detected at the output edges contradicting to the given

89

results. In the other case, if the circuit is faulty,
then those faults on paths s-maximally sensitized are
guaranteed to be detected. For those faults on paths 5-
truly sensitized, then faults on the critical sensitizing
paths may create multiple faults. However, there exists a
set of paths s'-maximally sensitized upon which the paths
in question depend. Faults on the set are detected. If
the set is fault-free then faults on s-truly sensitized
paths are detected. If the test detects the existence of
faults, the circuit cannot be fault-free, because a fault-
free circuit will have every path pass both signals. Q.E.D.
The results of a detection test serve two important
functions in addition to detecting the existence of faults.
First, they indicate the approximate areas of faults. The
partial circuits s-maximally sensitized and found to be
fault—free are guaranteed to be free of E type faults. And
the E type faults are only to be found in other parts of
the circuit. Also the partial circuits s-maximally sensi-
tized and found to be faulty are the areas where some of
the E type faults occur. Second, the results serve as

the basis for the diagnosis process.
3.4.3 An Example

Example 3.6

 

Continue with the preceding examples with the com-

binational circuit C of Figure 3.6. The maximal compatible

90

rows for the constituent circuits Cz and C22 are formed

1
as follows in the first step.

MCR = {MCR1, MCRZ}
MCR1 = {V11' V12' V13' v14' V15' V16}
MCR2 = {V21' V22' V23' v24' V25}

_ o o
V11 - {Pl I P2 }

(0'0!IIIIlololllllllllolllllol)

_ o o
v12 ‘ {P3 ' ps }
= (IOIOIOIIIIOIOIOIOIlIIIOIIIlIOIIIOI)

_ o o
v13 ' {p4 ' p5 }

(IllolllllIllllllllolllolI'llolllol)

l

_ 1
V14 ‘ {Pl ' p5 }

= (lIOIlIIIIIOIOIIIIIIOIIIlIlIIIlI)
_ 1 l
v15 ‘ {92 ' ps }
= (OIlIlIIIIIlIlIIIIIIOIIIlIlIIIlI)
v = { l l 1}
16 p2 I P3 I 94

= (OlllolollllllllololllI’ll!Illllllll)

91

v = { o o o
21 p6 ' p7 ' p9

}
= (IllololllllllololllllllI010]!IOIOIIO)

v = { o o o}
22 p6 ' p8 ' p10

= (IllllolololI'llllololollolllllololI0)

1}

<
ll

23 {96
= (I'llllIIIII'IIIIOIIIIlIOIIl)

v = { 1 1}
24 p7 ' P8

= (II'llollllllllllolllllIllolllllolll)

v = { l 1}
25 p9 ' p1o

(IIIIololllllIllolollolllllolllll)

In the second step, the blank entries of each of the
maximal compatible rows belonging to the same constituent
circuit are assigned the corresponding sensitizing values
according to their parities. Some of these entries may

have two possible assignments. The results are as follows.

vll = (0,0,1,0,,,,0,0,0,0,1,,,0,,,0,1,,,0,)
v12 = (1,0,0,0,,,,0,0,0,0,l,,,O,,,1,0,,,0,)
vl3 = (l,l,0,1,,,,1,1,1,1,0,,,O,,,l,0,,,0,)
v (l,O,1,1,,,,0,0,1,1,0,,,O,,,1,l,,,l,)

92

v15 = (0,1,1,1,,,,1,1,1,1,o,,,o,,,1,1,,,1.)
v16 — (0,1,o,o,,,,1,1,o,o,1,,,1,,,1,1,,,1,)
v21 = (,,,o,o,1,1,,,o,o,1,1,1,,o,o,,,o,o,,0)
v22 = (,,,1,o,o,o,,,1,1,o,o,o,,o,1,,,o,o,,0)
v231 = (,,,o,1,o,o,,,o,o,1,o,o,,o,1,,,1,o,,1)
v232 - (,,,o,1,1,o,,,o,o,1,1,1,,o,o,,,1,o,,1)
v24 (,,,1,o,1,o,,,1,1,o,1,1,,1,o,,,1,o,,1)
v25 = (,,,o,o,o,1,,,o,o,1,o,o,,o,1,,,o,1,,1)

Notice that with v23, there are two possible assign-

ments for x6.

In the third step, performing the maximal com-
patibility Operation on the set of maximal compatible rows
obtained in the second step results in the set of maximal

compatible input vectors MCS, for C.
MCS = {ij; 15j318}

i = {v v } = {p 0 p 0 p 0 p
1 11' 21 1 ' 2 ' 6 ' 7

(OIOIlIOIOIlIl) = (11! 12I

. _ _ o o 1
l2 ’ {V11' V231} ‘ {p1 ' p2 ' p6 }

(0,0,1,0,l,0,0)

= {v . v } = {p 0. p 0. p 1: p
13 24 4 5 7 8

={V;V}={P1IPIIPOIPOIP
14 22 l 5 6 8 10

93

{ 0

v v }= {p 0 p p 1}
11' 232 l ' 2 ' 6
(0.0.1.0.1.1.0)

_ o o 1 1
{V11' V25} ‘ {91 ' p2 ' p9 ' p10 }

(0,0,1,0,0,0,1)

o o
. p9 }

{v v } = {p O p 0 p O p
12' 21 3 ' 5 ' 6 ' 7
(lloyoropoplpl)

_ o o 1
{V12' V231} ‘ {P3 ' p5 ' p6 }

(1,0,0,0,1:0.0)

o 1
, p6 }

_ o
{VlZ' V232} ’ {p3 ' p5
(1,0,o,o,1,1,0)

{V12' V25} = {p30' p50' p91' 9101}
(1,0,o,o,o,o,1)

{V13' V22} = {940' p50, p60’ p80' 9100}
(1,1,o,1,o,o,0)

1}
(1,1,o,1,o,1,0)

0}

(1,0,1.1.0,0,0)

12

13

14

15

16

17

18

For

94

_ 1 1 1 1
V14I V24} ‘ {P1 I P5 I p7 I p8 }

= {
= (lIoIlIlIOIlIO)

{V I V } = {P 1I P l! P OI P or p 0}
15 22 2 5 6 8 10

= (OIlIlIlIOIOIO)

1 1
. p8 }

= {v v } = {p 1 p 1 p
15' 24 2 ' 5 ' 7
= (OIlIlIlIOIlIO)

l 1 l 0 0 0

= (0,1,0,0,0,1,1)

—{v v}={p1 1 pl 1}
16’ 231 2 ' p3 ' 4 ' p6

= (0,1,0,0,l,0,0)

_ 1 l 1 1
{V16' V232} ’ {92 ' p3 ' P4 ' p6 }
= (OIlIOIOIlIlIo)

_ _ 1 l l 1 1
- {V16I V25} ‘ {P2 I P3 I 94 I p9 I P10 }
= (0,1,0,0,0,0,l)

those mci's not maximally assigned, their

dependence sets are as follows.

112

12:

o o 1
p1 . p2 /{p5 }

o o 1
pl . p2 /{p5 }

95

. 1 o
12' p6 /{Plo }

o o 1
3. pl . p2 /{p5 }

3‘ Pal/{P70}

. o o 1
14. pl . p2 /{p5 }
. o o 1
15. p3 . p5 /{p1 }

o o 1
6' p3 ' Ps /{91 }

. 1 o
16' p6 /{P1o }

. 0 0 1
17- p3 . p5 /{pl }
9 l o
17. p6 /{p7 }

. o o 1
18. p3 . p5 /{pl }

1 1 o
13‘ p2 ' 95 /{P4 }

. 1 1 o
114' 92 ' P5 /{P4 }

. 1 o
116' p6 /{P1o }

17‘ pal/{p70}

In forming the detection tests, the dependence

sets can be excluded from consideration in this example.

0

Notice that, of the sets, p51 depends on p4 which is 0-

maximally sensitized and is included in every test. All

96

the others, p100, p70, p11, p40, p7O are all maximally

sensitized and each included in every test.

It seems a tedious task to form the tests, but a
little observation will reduce it to a simple one. For
example, p10 and p20 appear only in il, 12, i3, and i4,
so every test should include one of these four mci's. And
also p91, p101 appear in i4, i8 and 118’ so one of the
three mci's should be in every test, etc. Working along
this line, one should find it easy to form a test. Although
more tests can be formed, there are 12 tests each consisting
of 5 mci's that are most economical in terms of test size.

Define this set as Te' one has

Te = {ti; 131512},

1 '5' i6' i9' i12' i4}'

t2 = {15' 18' 19' 112' 12}'

t3 = {16’ 115' 19' 112' 14}'
t4 = {16' 118' 19' 112' 11}'
t5 = {18’ i15' i9' i12' iz}'

t6 = {i8’ 116' 19' 112' 11}'

t = {i

5’ 16'

18'

97

t9 = {16’ 115' 110' 111' i4}'
t10 = {16' 118' 110' 111' 11}'
t11 = {18' 115' 110' 111' 12}'

t12 = {18’ 116' 110' 111' 11}°

Consider the set of faults F on the circuit in

Figure 3.6,

s-a-l,

S-a-O I

Of the set F, f is made undetectable by f and f f

9 l 5’
fll reduce Cz2 to p8 and p9 which 15 equivalent to 22

7'

s-a-l. Let t = t1. Applying t1 to C, the output vectors

obtained are as follows:
05 = (0:1) = (le 22)!

0 (1'1)!

16 =

98

09 = (0(1)!
012 = (Oil)!
04 = (0,1).

Thus the results of the test reflect the following
detections:

i detects {p6, p7, p9} s-a-l,

5
19 detects {p6, p8, p10} s-a-l,
112 detects {p1, p5} s-a-O.

Notice that the partial circuit in each case is s-
maximally sensitized and thus its detection is ensured.
Also the partial circuit is faulty in at least one path,
but not necessarily all the paths due to the fact that all
the paths are simultaneously sensitized.

The partial circuits s-maximally sensitized and

found to be fault-free are
116: {p2, p3, p4} pass 1,
i9: {p4, p5} pass 0,
112: {p7, p8} pass 1,
14: {p9, p10} pass 1.

Being s-maximally sensitized, these parts of the
circuit are sured to be free of the types of faults being

suspected. Other detections involve s-non-maximal

99

sensitization and cannot be readily interpreted, but will
be treated in the diagnosis process.

Thus the results indicate the approximate areas of
faults in the circuit as well as serve as the basis for the
diagnosis process.

3.5 Fault Diagnosis of
Combinational Circuits

In this section the approach to locate faults in
the combinational circuit by determining the ability of
every path of the circuit in passing the signals is dis-
cussed. Using this approach, an algorithm is developed
to locate all the detectable faults in the circuit based
on the results of a detection test. Even though different
detection results might be obtained from different tests
used, the diagnosis process based on the different results
should always locate the same set of faults except possibly

for equivalent faults.

3.5.1 The Diagnosis Approach

A detection test as designed in the previous
section does not individually check every path of a combina-
tional circuit in passing both signals. But rather a set
of compatible paths are simultaneously checked for a
certain type of faults using a maximal compatible input
vector; Faults thus detected might not occur on every path
0f therset. Thus a diagnosis process is needed to actually

locate the faults within the set. However, the results of

100

a detection test do indicate the approximate areas where
both types of faults will occur. The responsibilities of
a diagnosis process are then to locate all the faults
within these areas. These areas include all the paths
each of which is suspected of not being able to pass some
signal 3. Thus every path of these areas has to be tested
to pass the corresponding signal s if it is s-sensitizible
within the existing fault picture. If it is not 5-
sensitizible, then it has to be tested for the possibility
of being part of some multiple fault. If every path of
these areas is thus tested, then all the faults of the
combinational circuit can be located down to equivalent

faults. A path is said to be suspected of sticking at s

 

if it has not been proved to pass the signal 3. Or, simply

it is a suspected path.

 

Theorem 3.15

 

If every s-sensitizible suspected path of a com-
binational circuit is tested to pass 5, and every 3-
unsensitizible suspected path is tested for possible E-type
multiple faults, the faults of the combinational circuit
will be located down to equivalent faults.

Proof: First an s-unsensitizible suspected path
which does not include any multiple faults can be con-
sidered as either sticking at g or as being able to pass 5
because of the fact it is not s-sensitizible within the

given fault picture. After every s-sensitizible suspected

101

path has been tested to pass 5, and every s-unsensitizible
suspected path has been tested for s-type multiple faults,
the remaining s-unsensitizible paths can then be assigned
as either sticking at s or passing 8. Hence every path is
thus determined for its ability to pass both signals. All
the maximal faulty subcircuits can then be identified and
all the single faults are thus located. Multiple faults
are of course identified during the process. Thus every
type of faults is included in the process of testing every
individual path. Different sets of the equivalent faults
can result from the different assignments given to the s-

unsensitizible paths. Q.E.D.

Location of Single Faults

 

Locating single faults is equivalent to identifying
maximal faulty subcircuits. To do this, a set of input
vectors must be found which detects a maximal faulty sub-
circuit.

A set of paths Pi of a combinational circuit is

said to define a subcircuit Ci if Pi totally forms Ci

 

except for the subpath between the output edge of C1 and
the common trailing edge of Pi'

The following theorem expresses the characteristics
of a set of input vectors which detect a maximal faulty

subcircuit.

102

Theorem 3.16

 

Given a maximal subcircuit Ci defined by a set of
paths Pi with at least one p 5 Pi which is s-sensitizible
within the existing fault picture, for a set of input
vectors I to determine Ci as faulty of s-type, it must test
for the failure of the signal s in propagating through
every s-sensitizible path p.

Proof: If Ci is faulty of s-type, then every p 6 Pi
which is s-sensitizible cannot pass 5. Thus 5 cannot
propagate even through one path of P. Since there exists
at least one s-sensitizible path, I can be found. Q.E.D.

The formation of such a set of input vectors is

defined as follows.

Definition 3.18

 

Given a maximal subcircuit Ci with the output edge
ei and defined by a set of paths Pi with the trailing edge

zi, Ci is suspected of being faulty of s—type. A fault

 

 

sensitizing vector I for Ci' or 9i sensitizing vector is a
set of input vectors which is composed as follows.

1. The subpath between ei and zi is sensitized by
every i e I. Using part of C1 in the sensitization
should be avoided if possible.

2. Every fan-out of different parities of C1 should
be assigned all the different possible non-
contradicting signal values resulting in several

different input vectors for I.

103

3. The rest of Ci is s-maximally assigned.

For example, given the fault f x s-a-l in

l' 1
Figure 3.4, for the fault £17: el7 s-a-O, a C17 sensi-
tizing set would include two input vectors I = {(d, l, l,

1, l), (d, 1, 1, 0, 1)}. Notice that d can assume any

value because of f1 and x4 is assigned both values due to
the fan-out of different parities.

It is not hard to see that such a set of input
vectors will detect a maximal faulty subcircuit. The main
point is that the subcircuit is applied with all possible
input vectors to cause its output edge to assume the signal
value 5 in order to disprove its sticking at E. If at least
one input vector of I causes the corresponding output edge
to assume 3, then Ci is not faulty of s-type and the smaller
subcircuits within Ci faulty of the same type will have to
be tested similarly.

Location of Multiple Faults
and Multiple Paths

 

 

After every s-sensitizible path of the combina-
tional circuit has been determined in passing both signals,
those paths which are s-unsensitizible given the proved
faults can be combined in locating multiple faults.

Since multiple faults are formed through the mutual
sensitization of a set of uncovered undetectable faults,
input vectors must be formed which cause these undetectable

faults to propagate and meet at some gate where they

104

mutually sensitize one another. For this to happen, the
faults must all be sensitizing to the gate at which they
meet and each is sensitized to propagate through the gate.
A multiple fault occurs only on a set of paths called a

multiple path.

 

Definition 3.19

 

An s—sensitizible multiplegpath is a set of paths

 

Pi' each of which is to be tested to pass 5, pi, and it has

the following characteristics.

1. Every pj 8 Pi is s-unsensitizible,

2. There exists a set of logical gates G on Pi such
that at least two paths of Pi meet at each 9 e G.
Further the set G is such that the s-type signal
propagating through paths of Pi is dominant to G,

3. Pi is s-sensitizible, i.e., every pj 8 Pi is s-
sensitizible except for those sensitizing edges
belonging to other paths of Pi' These edges will
assume the dominant value 5, and feed the logical
gates of G,

4. No subset of Pi has the above characteristics.

The following theorem finds the locations of

multiple faults.

Theorem 3.17

 

An s-type multiple fault occurs only on an s-

sensitizible multiple path Pi'

105

Proof: Let Pi be the set on which f occurs. Since
f is multiple and of s-type, so each p 6 Pi is s-
unsensitizible. In order for £1, fj e f to sensitize each
other, 5 must be sensitizing to the gate g s G where
the corresponding two paths Pi and Pj of Pi meet.
Hence s is dominant to 9. Also in order for f to be
sensitized, Pi must be s-sensitizible. Finally since
f should not include another multiple fault, hence
Pi should not include another multiple path. Q.E.D.
During the diagnosis process, it should not be
too complicated in identifying multiple paths. Because
usually multiple paths are formed from fan-out paths due
to the fact that unsensitizibility is caused by fan—outs.
x s-a-O and f : e

1‘ 1 12
s-a-l in Figure 3.4, the two paths p2 = x2,

For example with the faults f 12

810' e18' z

and p3 = e e 2 become a multiple path and

19'

£18: e18 s-a-l and £11: ell

A multiple fault sensitizing input vector which s-sensitizes

x2' 911' 16'

s-a-l become a multiple fault.

the multiple path Pi will then detect the multiple fault f.

Sensitization Involving
Unsensitizible Critical
Sensitizing Paths

 

 

 

During the diagnosis process, it might occur that
unsensitizible critical sensitizing paths have to be used
in the sensitization of a suspected path. Being unsen-

sitizible in passing the critical sensitizing values,

106

these critical sensitizing paths are not known to be able
to provide the critical sensitizing values. However, it
can be shown that the path to be s-sensitized for detecting
s-type detectable faults on it can be considered as s-
sensitizible by assuming that all the critical sensitizing
paths are capable of providing the necessary critical
sensitizing values even though they cannot be tested to
pass the critical sensitizing values with the existing

fault picture. This is proved in the following theorem.

Theorem 3.18

 

Given a path p to be s-sensitized and a set of
critical sensitizing paths Pu = {pi; i = l, ..., n} with
the critical sensitizing values {si; i = l, ..., n} where
si = 0 or 1. Each pi is si-unsensitizible. Further let
pS/{pil, p32, ..., pin} and p is s-unsensitizible if any
pi e Pu is not used as a critical sensitizing path. Then
p is s-sensitizible and hence the s—type faults on it are
detectable iff every pi E Pu is capable of providing the
corresponding critical sensitizing value.

Proof: If pi e Pu passes 81' then p is s-sensitized
as the critical sensitizing values are provided. If the
s-type faults on p are detectable, then p is s-sensitized
which implies every pi provides the necessary critical
sensitizing value otherwise p becomes s-unsensitizible

because pS/{pil, p32, ..., pin} and every pii is needed.

Q.E.D.

107

Thus p is s-sensitizible only by assuming every
unsensitizible critical sensitizing path as capable of

providing the critical sensitizing value.

Outlines of the Diagnosis Process

 

In addition to actually determining the suspected
paths to be faulty or fault—free, some of the suspected

paths can be indirectly determined through the determina-

 

tion of other related suspected paths. A suspected path

is said to be confirmed if it is proved to be faulty of the

 

suspected faults. It is said to be disproved if it is

 

proved to be free of the suspected faults. It is determined

 

if it is either confirmed or disproved.
Suspected paths can be determined with fault sen-

sitizing vectors. For suspected paths to be indirectly

 

determined, the following operation is defined.

 

The indirect determination of suspected paths

 

includes

1. If a set of paths was s-maximally sensitized and
found faulty of s-type, then if all paths of the
set except one are disproved of s-type faults,
the remaining path is indirectly confirmed faulty
of s-type.

2. If a set of paths was s-non—maximally sensitized
and found faulty of E-type, then if all paths of
the set except one are disproved of s-type faults

and the dependence set is proved able to pass the

108

critical sensitizing values, the remaining path is
indirectly confirmed faulty of s—type.

3. If a set of paths was s-non-maximally sensitized
and found free of s-type faults, then if its
dependence set is proved able to pass the critical
sensitizing values, the set is indirectly disproved
faulty of s-type.

4. If a subcircuit was s-sensitized and found faulty
of s-type, then if all of its dependence sets are
proved able to pass the critical sensitizing
values, the set of paths defining the subcircuit
is indirectly confirmed faulty of s-type.
According to their capabilities in passing the

signals, the paths of the combinational circuit can be
divided into four sets during the fault diagnosis process.
They are the disproved or good set PG' the confirmed or

bad set P the suspected set PS and the unsensitizible set

BI

P A diagnosis process is then to establish the set of

u.

faults F by completely establishing the set PB. This is

done in the following steps.

1. Reduce P to null by determining and assigning

8
every p: 6 PS to one of the other three path sets.
2. Find faulty multiple paths from PU and include them
in PB.
3. Assign every p: e PU which remains to either PG
or PB without creating any new faults for the

circuit. And finally

109

4. Establish F from PB.

The process can be graphically represented as in Figure 3.7.

3.5.2 The Path Checking Fault
Diagnosis Algorithm

The basis of the diagnosis algorithm is derived
from the results of a detection test. It consists of the

P P and P as obtained in the following

four sets P B' U S

G'
way.

Given a combinational circuit C with the set of
paths P and tested with a detection test t, the basis of
the diagnosis algorithm is formed as follows.

1. Include every pi e P as p: in PG if pi is s-
maximally sensitized with some i s t which detects
no suspected faults.

2. Include every pi e P as p: in PG which is indirectly

disproved of sticking at s.
3. Include every pi e P as p: in PB which is indirectly
confirmed of sticking at E.
4. Include every pi e P as p: in PU which is s—
unsensitizible with the results of the first
three steps.
5. Include the remaining paths of P as p: in P for
the appropriate s.
Given a no-output combinational circuit C with the

set of paths P and no constituent circuits Czi' liiinor

and tested with a fault detection test t. C is faulty

110

 

 

A

A
/
"U
c:

Step 1

1

Step 2

Step 3

 

O .I O
O

 

 

 

Step 4

Fig. 3.7.--Graphical representation
process.

4
w

of the diagnosis

with the resulting diagnosis basis B = {P

111

G' PB' PU' PS}'

A fault diagnosis algorithm to locate all the detectable

single and multiple faults, the set of faults F, is pre-

sented

A.

as follows.

For each C2 of C, find a set of s-sensitizible

i

paths P: e P which, except for the s-

S

unsensitizible subpaths of a subcircuit Ci' define

Ci' If no such P: exists, then find such a set

P: which depends on P for critical sensitizing

U
paths. Notice that s = 0 or 1.

Form a set of Ci-sensitizing input vectors Ii for
each Ci'

Form a set of maximal compatible vectors IC from
the sets Ii's formed in B. The undetermined
entries in each i 5 IC can be arbitrarily assigned.
Apply IC to C. If Ci is known to be s-sensitized
with Ic' then if Ci is found faulty of s-type

move P: to P or if Ci is found free of s-type

BI

faults and Ci is defined by one path only, move

P: to P Otherwise mark Ci as tested.

GI

Move every p: from PS to either PG or PB if it is

thus indirectly determined. Move p: to PU if p is
caused s-unsensitizible within the existing fault
picture.

Repeat A through E until all maximal faulty sub-

circuits have been tested. A subcircuit previously

112

tested should not be chosen in Step A. Move the

remaining PS to PU.

G. Test every s-sensitizible multiple path P: e PU
for multiple faults. If multiple faults are
detected, remove P: from PU and include it in PB.

H. Remove any one P: e PU to either PG or PB.

1. Remove every p: e PU to either PG or PE if it is
thus indirectly determined.

J. Repeat H and I until PU is reduced to null.

K. For every P: = {p:; lfijini} in PB defining a
maximal faulty subcircuit Ci of s-type, with the
output edge ei include fi: ei s-a-s in F. If fi
propagates down some path and stops at ej assuming
the signal value 5', then instead of fi' include

f.: ej s—a-s' in F. In this case fi is equivalent

3
to fj' Remove P: from PB. Since even one pS can
define a maximal faulty subcircuit, so P is thus

B

reduced to null.
The validity and convergence of the algorithm is proved

in the following theorem.

Theorem 3.19

 

The path checking fault diagnosis algorithm will
locate all the detectable single and multiple faults of a
combinational circuit C in a finite number of steps.

Proof: Every s-sensitizible path ps 8 P is

S

included in either PG or PB only if it is so determined.

113

Otherwise it is always included into P And every 3—

U.
sensitizible multiple path P: s PU is included in PB if it
is thus identified. Hence the remaining pi's e PU are 5-

unsensitizible and thus their assignments as done in the
algorithm do not introduce additional faults and thus do
not affect the original fault picture. So every path of C
is being determined for its sensitizibility, including
sensitizibility through faults providing the sensitizing
values (multiple paths), all the faults, single and multi-
ple, can be thus identified. Since in identifying maximal
faulty subcircuits, the algorithm moves from the outputs
of the circuit towards the inputs of the circuit and each
maximal faulty subcircuit is tested at most once, the
algorithm will terminate in a finite number of steps.

Q.E.D.

3.5.3 An Example

Example 3.7

 

Continuing with the results of Example 3.6, one

finds the basis as

1},

P={11100111
G p2 ' p3 ' p4 ' P4 ' ps ' p7 ' Pa ' p9 ' p10

_ 0 0 0 l l 0 0 0 0
PS ’ {pl I P2 I p3 I pl I p5 I p6 I P7 I p8 I p9 I

0 1}
p10 I p6

I

114

To apply the algorithm, there are six maximal

faulty subcircuits from P as follows,

S

o _ o o . .
P18 - {pl , p2 }, defining C18’

"U
II

0 . .
3 {p3 }, defining C9,

{p11}, defining C

"U
ll

1'

'6
ll

1 . .
5 {p5 }, defining C3,

0

_ o o o o
022 — {p6 . p7 . Pa . p9 . P10 } and

{p61}, defining C

"U
ll

5.
. 0 0 l 0 l 1 1
For C21, Since {p1 , p2 }/{p5 }, {p3 }/{p1 }, {p1 }/{p5 },
and {p51}/{p40}, so {p51} should be chosen first because
p40 e P . The maximal faulty subcircuit for C22 is 022.

G
The C3-sensitizing input vector to test p5l is

I = {i

l }= (OIOIlIlIII)°

19

For C22, the 0-type sensitizing set is
I2 = {120' 121}'

120 = (IIIOIOIOI0)I

i21 (...0,0,1.0)-

Since they are not compatible, the blank entries can be

arbitrarily assigned. Applying the sensitizing input

115

vectors to C, one finds both P5 and C22 faulty. That is
p5 cannot pass 1 and every path of C22 fails to pass 0.

The updated basis becomes

P : unchanged,

G
P5 = {P10' P20' p30' Pil}'

PB = {p51’ 960' 980' p90, p100},
PU = {p61}.

where p6 becomes l-unsensitizible due to {p61}/{p70;
P100}'

0: the set p5, {p10, p20}/{p51}, {p11}/{p51}, so
these two subcircuits also become O-unsensitizible and 1-
unsensitizible respectively. But since {p30}/{p11}, so p1
can be assumed to be capable of providing the critical
sensitizing value 1. The 0-type P3-sensitizing vector is

then
I3 = {izz} = (1,0,0’0"')o

Applying 122 to C, one gets 21 = 0 detecting no faults.
Thus p3 also becomes O—unsensitizible and PS is to be all

included in PU.

0 0 0 1 1
PU = {P1 I P2 I P3 I p1 I p6 }

From this, the following O-sensitizible multiple paths are

formed.

116

Pm1 = {91' 92}

The input vector iml = (0,0,0,1,..) testing P31 detecting

no multiple faults. The same input vector also tests p32
for multiple faults. Thus PU is unchanged. Different
assignments for PU will result in different sets of

equivalent faults. For C22, it is clear that C22 sticks

at 1 which is equivalent to {f5, f7, fll}. If one includes
PU in PG,
only detectable fault which is equivalent to {f1, f9, f3,

then pS failing to pass 1, i.e., f3, will be the

£5}.
3.6 Characteristics of the Method as
Applied to Combinational Circuits

In reviewing and comparing the path checking method,
as it is applied to combinational circuits, to the other
methods included in Chapter II, the following character-
istics concerning this method are observed.

First, the main differences between this method
and the other methods are that in this method no assump—
tions about the existence of certain faults are made in
developing the tests, and that every path of the combina-
tional circuit is guaranteed to be sensitized if possible
‘with the tests formed from this method. For example, Roth's
Inethod [35] assumes the existence of some certain faults

in order to formulate tests for that faults. Chang's

117

method, even though employing, in effect, path sensitiza-
tion, does not require that the paths be maximally sensi-
tized when possible. While, with the path checking method,
every path of the combinational circuit is either maximally
sensitized or truly sensitized to achieve actual sensiti-
zation.

Second, as a result of the emphasis on actual
sensitization, every test from this method carries
detection as well as diagnosis information and the detection
test serves partial diagnosis functions.

Third, during the fault detection and diagnosis
process with this method, the approximate faulty areas of
the circuit are clearly defined at each stage of the pro-
cess. This will prove very useful in fault analysis of
integrated circuits.

Fourth, this method can be extended to cover com-
binational circuits which include EXCLUSIVE OR gates.
Since every signal value is sensitizing to these gates, to
actually sensitize a path containing such gates, every
edge feeding such a gate and incident on the path should
assume the same signal value, in the sensitization of this
path, throughout a detection test. Thus the maximal
compatibility procedures have to be modified to achieve
'this requirement.

Fifth, this method can be extended to cover com-

binational circuits which include redundant circuitry. By

118

employing the concept of "multiple paths" as presented in
this chapter, unsensitizible and partially sensitizible
paths in such circuits can be incorporated into the path
checking method.

Finally, the path checking method can also be
applied to sequential circuits as will be discussed in

the next chapter.

CHAPTER IV

FAULT DETECTION AND DIAGNOSIS OF
SEQUENTIAL CIRCUITS BY THE

PATH CHECKING METHOD

From the path point of view, the fault analysis of
sequential circuits can be regarded as an extension of the
fault analysis of combinational circuits. This is evident
if one treats the feedback lines of a sequential circuit as
"connectors" of the paths found in the combinational
portion of the sequential circuit. Thus instead of paths,
the analysis will involve sequences of paths with each path
sequence beginning with a circuit input edge and ending
with a circuit output edge. The main approach used in the
analysis is to study the combinational portion of the
sequential circuit. To do this, every path of the
"embedded" combinational circuit should be included in some
path sequence checked in order for the path to be checked.
Thus the path sequences of a sequential circuit covered in
a fault analysis should cover all the paths of its com-
binational portion. Further, fault detection and diagnosis

of sequential circuits involve a more complicated process

119

120

as well as some additional considerations that are unique
to sequential circuits.

One of the requirements that confronts the fault
detection and diagnosis of sequential circuits is "syn-
chronization" of the feedback lines. Synchronization pro-
vides the necessary control over the feedback signals so
as to correctly sensitize the path sequences of the cir-
cuits. Another requirement before a fault analysis is
undertaken is to guide the sequential circuits to some
known state. This initial procedure is necessary in order
to correctly interpret the test results and to accurately
detect and locate the faults in the circuits.

This chapter is devoted to the fault analysis of
sequential circuits. As in the previous chapter, the
analysis is divided into two parts: fault detection and
fault diagnosis. In addition to the synchronization
requirement, the limitations placed on the types of cir-
cuits, faults and logical elements of sequential circuits
considered are identical to that of combinational circuits.
In this case, every path should be embedded in at least
one s-sensitizible path sequence. Also faults on feedback
lines are included in this case.

The basic concepts and approaches from the com-
binational case are adopted and extended from the "path"

viewpoint to the "path sequence" viewpoint to apply to

121

sequential circuits. Most of the nomenclature from the

previous case is also adopted with the like modifications.

4.1 Some Network Properties of
Sequential Circuits

 

 

Just as a combinational circuit can be viewed as a
set of interconnected paths, a sequential circuit can be
considered as a set of interconnected path sequences.

From this vieWpoint, the logical behavior of the sequential
circuit can thus be interpreted in terms of signal propa-
gation within this set. It is along this approach that the
fault analysis of the sequential circuit proceeds. In

this section, a brief discussion of some of the network
properties from such a viewpoint is presented.

A sequential circuit with all its feedback lines
disconnected reduces to a combinational circuit. The com-
binational circuit thus obtained has all of the network
properties as discussed in Chapter III.

The combinational circuit obtained from disconnect-
ing all of the feedback lines of a sequential circuit will
be called the associated combinational circuit of the
sequential circuit. With all of its feedback lines mathe-
matically disconnected, it becomes clear that all the given
stuck-at type faults of a sequential circuit can be com—
pletely translated into faults of its associated combina-

tional circuit. Hence the logical starting point in fault

122

analyzing a sequential circuit is to check every path of
its associated combinational circuit.

When the terminology defined in Chapter III for
combinational circuits is used in this chapter in connection
with a sequential circuit, it will he meant to refer to
its associated combinational circuit. Thus a path of a
sequential circuit will be used to mean a path of its
associated combinational circuit.

Consider a sequential circuit C with n input edges
x1, liijn, m output edges, zj, lijim, g state input edges
(present state variables), yk, likiq, q state output edges
(next state variables), y'k, likiq, and the set of n

P
paths P = pi; liiinp , a path sequence and a subpath

 

seguence of C are defined as follows.

Definition 4.1

 

A path sequence ps = 21, £2, ..., 2p, of C is a

 

sequence of paths of C such that

1. l the leading path, contains an input edge of

1:
C as its leading edge,

2. 2 , the trailing path, contains an output edge of
C as its trailing edge, and

3. li and £i+l'

a state output edge y' of C as its trailing edge

liiip-l, are such that 2i contains

and £i+l contains the state input edge y, which
is connected to y' through a feedback line, as its

leading edge.

123

A subpath seguence psS of C is a section of a path
sequence ps such that psS includes either the leading edge
or the trailing edge of ps or a middle section of ps.

Thus a path sequence of a sequential circuit is a
sequence of paths which starts with an input edge and ends
with an output edge of the circuit, with the paths in
between connected by feedback lines. A path sequence thus
defined needs not be of finite length.

To check a path of a sequential circuit, it must
be embedded in a path sequence so that it can be tested
to pass signals which propagate from the input edges,

through the paths, to the output edges of the circuit.

Theorem 4.1

 

For every path of a sequential circuit, there
exists at least one path sequence which contains it.

Proof: A path which is not part of any path sequence
is either not accessible from the inputs of the sequential
circuit or signals passing through it will never reach the
outputs of the sequential circuit. Hence such a path
serves no logical functions at all and thus need not be
considered as part of the circuit. Q.E.D.

Analogous to the combinational case, partial cir-
cuits and constituent circuits can also be defined on

sequential circuits.

124

Definition 4.2

 

A partial circuit of a sequential circuit C con-

 

sists of a set of path sequences of C which share a cir—
cuit output edge of C as their common trailing edge of

their trailing paths.

Definition 4.3

 

A constituent circuit of C consists of the set of

 

all path sequences which share a circuit output edge as
their common trailing edge of their trailing paths.

For a path p of a sequential circuit, there can be
infinite number of path sequences which contain it, con-
sidering the fact that there may exist a path within the
path sequence which can be infinitely repeated within the
sequence. Thus, of the set of all possible path sequences
which contain p, there exists a subset which is of interest

in checking p. Such a subset is called the set of minimal

 

path sequences of p.

 

Definition 4.4

 

A minimal path sequence ps of a path p of a sequen-
tial circuit C is a path sequence which satisfies these two
conditions.

1. It contains p.
2. It cannot qualify as a path sequence if any path(s)

are deleted from it.

125

The set of minimal path seguences of p is the set of path

 

sequences consisting of all the minimal path sequences of

p.

Examples of these definitions are illustrated in

the following example.

Example 4.1

 

For the sequential circuit C of Figure 4.1, there

are nine paths.

P = {pi;
p1 = x1.
x1,
p2 = X1'
p3 = X2'
X2,
P4 = X3I
P5 = Y4:
Y4I
P6 = Y4:
Y4:

131:9}

e e or

7' 14’

e I

e 14' Y 4

7.
e8' 913' Y's
14' 1

914' Y'4

elO' e14'
e9' e10' 814'
15'

e9' 911'

11' 15'

126

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f s-a-OI e 2
x2 2 A $ 14 fig 1
x
3 e3
I
e10 Y 4
y4 e9
y5 :
e11
e z
e 15 2
Y6 [:>c>—f s-a-O
12 .
Y 5
e f
13 _ - 4
l:>[: ‘_, f6 s a l 1
>_—_———T s-a-
11 1.3 ’E#
Y's
f5
f*‘”
Fig. 4.l.--A sequential circuit for Example 4.1.

The set

The set

The set

127

p7 = Ys' e9' 910' e14' 21 or
I
Ys' e9' e10' e14' Y 4
P8 = Ys' e9' 911' e15' 22 or

I
Ys' e9' e11' 915' Y 5

Y6' 912' e5' Y's
of minimal path sequences PS9 of p9 is
PS9 = {p591, p892}.
P391 = P2: P9:
ps92 = p4' p9’
of minimal path sequences P88 of p8 is
P88 = {9581' ps82' ps83' P584}'
p881 = P1: P6: P8:
P582 = P2: P9: P8:
ps83 = p3' p6' p8'
ps84 = p4' p9' p8'
of minimal path sequences PS6 of p6 is

P56 = {ps61' pS62' pS63' P564}'

128
9361 = 91' 96.
P362 = P2: P9: P7: P6!
p863 = p2! p6!

P364 = P4: ng P7, p60

9, PS

Thus, PS and PS can be combined to form a partial

8' 6
circuit.

A subpath sequence psS = p2, y6 can be formed from

p391 and consists of a leading section of p391.

4.2 Path and Path Sequence Sensitization
of Sequential Circuits

 

 

As was stated earlier in this chapter, the fault
analysis of sequential circuits is in essence an extension
of the fault analysis of combinational circuits; whereas
one was concerned with path checking in the former case,
he has to deal with path sequence checking in the latter.
As a matter of fact, it can be said that the analyst is
confronted with the same problems in both cases except
that the problems are formulated either in terms of paths
or path sequences.

4.2.1 Sensitizing a Path and
a Path Sequence

In order for a path of a sequential circuit to be

checked, it must be embedded in a path sequence and the

path sequence must be sensitized to pass the signals. If

129

a path sequence consists of more than one path, then the
signals have to prOpagate through its sequence of paths to
reach an output edge of the circuit from an input edge of
the circuit. To do this an initial state and a series of
input vectors to the circuit have to be found so that the
path sequence is sensitized all the way to pass its testing
signals. The point thus becomes clear that the feedback
lines of the sequential circuit have to be synchronized to

ensure this requirement.

Definition 4.5

 

A path sequence ps = pl, p2, ..., pn of a sequential

circuit C is sensitized with a sequence of input vectors,

 

is = il, i2, ..., in, applied to C starting from state s1,
if p1, p2, ..., pn are sequentially sensitized with the
input-state vectors (i1, 51), (12, $2), ..., (in' sn),
where si = T (Si-1' 1i_l), 2:13p.

The definitions for signal propagation through a

 

path sequence, a path sequence passing an s-type signal, a

 

path sequence tested to pass 3, pss, and a path sequence

 

checked would be similarly defined as a path in Chapter III.
The only difference is that, in this case, one deals with
a set of paths in a sequential order. Also a path sequence

being s-sensitizible or s-unsensitizible are similarly

 

 

defined.

130

The main point that one is concerned with, however,
is that a path of a sequential circuit must be sensitizible

in order for it to be checked.

Definition 4.6

 

A path p of a sequential circuit is sensitized if

 

it is embedded in a path sequence ps which is sensitized.

p passes an s-type signal if ps passes an s-type signal.

 

p is tested to pass 5 if ps is tested to pass 8. p is

 

tested if ps is tested to pass both signals and checked
if ps passes both signals.

A path of a sequential circuit being s-sensitizible,

 

s-unsensitizible, sensitizible or partially sensitizible

 

 

 

are defined as in Chapter III but based on the above
definition.

The set of minimal path sequences of a path p needs
not contain all the s-sensitizible path sequences that one
has to consider in checking p. A minimal path sequence of
p may be s-unsensitizible. In this case, it can be, but
not necessarily, expanded by inserting paths in it to make
it s-sensitizible. The resulting s-sensitizible path

sequences will be called expanded minimal path sequences

 

and will take the place of the original minimal path
sequence. For example, the minimal path sequence p581 =
p1, p6, p8 of p8 in Example 4.1 is not 1-sensitizible.

This is because in l-sensitizing p1, then p6 becomes

131

l—unsensitizible. Thus one can insert p5 into ps81
. . , = . . _ . . .
resulting in ps 81 pl, p5, p6, p8 which is 1 senSitizible.

The set of path sequences of p and the set of path

 

 

sequences of C that are all one has to consider in fault

 

analysis of C are defined as follows.

Definition 4.7

 

The set ofgpath sequences of a path p of a sequen-

 

tial circuit C is a set of path sequences PS which is
formed as follows.

1. Include the set of minimal path sequences of p in
PS.

2. If ps 6 P8 is s-unsensitizible (s = 0 or 1),
include its s-sensitizible expanded minimal path
sequences in PS.

3. If, after step 2 is done for all minimal path
sequences, ps 6 PS is unsensitizible, delete ps
from PS.

The set of path sequences of C is the union of the sets of

 

path sequences of all the paths of C.
The following theorem shows the value of the set

of path sequences of C.

Theorem 4.2

 

The set of path sequences PS of a sequential cir-
cuit C consists of all the s-sensitizible path sequences

of minimal length (no portions can be deleted).

132

Proof: From Definition 4.7, it is clear that every
s-sensitizible path sequence of minimal length is included
in PS. Also every ps 8 PS is s-sensitizible for some 8 as
required by the definition. Q.E.D.

For the remaining portion of this chapter, whenever
a path sequence is referred, it will belong to the set of
path sequences of the sequential circuit.

As with combinational circuits, the reconvergence
of path sequences can cause some paths of a sequential
circuit to be partially sensitizible or completely unsen-
sitizible. This can happen even though the associated
combinational circuit has all its paths sensitizible.

4.2.2 Unsensitizible Paths in
Sequential Circuits

If a path of a sequential circuit is s-
unsensitizible, then there is at least one edge on the
path at which an s-type fault is undetectable. These
edges thus represent redundancy.

Consider, for example, the sequential circuit in
Figure 4.2. In this circuit, every path sequence con-
taining the path p7 = y4, e10, e12, y'4 cannot be sen-
sitized to pass 0. This is because whenever p7 is sensi-

tized to pass 0, the other fan-out path p6 = y4, e9, e z

11'
is also sensitized to pass 0 which in turn causes y3 to
assume 0 preventing the succeeding path p6 of the path

sequence being considered from being sensitized. Thus the

133

N

.mmoamsvom

sand manwufiuflmcmmcs madmwuumm mcfisflmucoo uwsouwo Hmfiusosvmm <11.m.v .mwm

 

 

 

 

4

 

 

 

 

 

Q

 

 

 

 

 

NH

Ha

 

 

 

 

 

 

 

 

 

 

 

 

 

 

134

edge e , which is found on p7 only, sticking at 1 is unde-

10
tectable. In this case, the fan-outs on the edge y4 recon-
verge, after the feedback lines, at the logical element G1.
As with the combination case, a sequential circuit
with all paths sensitizible can be derived from any given
sequential circuit containing partially sensitizible or
unsensitizible paths. A path of a sequential circuit is
s-sensitizible if it can be embedded in at least one s-
sensitizible path sequence. It is s-unsensitizible if no
such path sequences can be found. The following theorems

are useful in determining if a sequential circuit has all

its paths sensitizible.

Theorem 4.3

 

A sequential circuit C will have all of its paths
sensitizible iff for every path pi of C, there exist at
least two path sequences psj, psk (they can be the same
path sequence), of the set of path sequences PSi of pi
such that psj is s-sensitizible and psk is s-sensitizible.

Proof: If C has all its paths sensitizible, then
psj and psk can be found. Since PSi contains all the s-
sensitizible and s-sensitizible path sequences containing
p1 hence psj and psk are included in PSi. On the other
hand, if not one ps a PS1 is s-sensitizible or E-
sensitizible, then clearly pi is not sensitizible. Q.E.D.

The elimination of partially sensitizible and

unsensitizible paths will not alter the logical behavior

135

of the sequential circuit. This is proved in the following

theorem.

Theorem 4.4

 

For every sequential circuit in which not every
path is sensitizible, there exists a sequential circuit
with all paths sensitizible which realizes the same logical
behavior.

Proof: The proof is similar to that of Theorem 3.2.
Given a sequential circuit C1 with partially or unsensi-
tizible paths, another sequential circuit C2 with all

paths sensitizible will be built from C by removing all

1
paths which are s-unsensitizible (s = 0 or 1). Since Cl
contains s-unsensitizible paths, find a path pi such that
all paths of its set of path sequences PSi are 3-
unsensitizible. The rest of the proof is similar to that
of Theorem 3.2 if one focuses his attention on the associ-
ated combinational circuit of C1. Q.E.D.
For example, the path p7 of the circuit C of

Figure 4.2 is O-unsensitizible. The set of path sequences

PS7 of p7 includes

ps71 = 92' 97' p6'
P372 = p4! P7I p6'

both being O-unsensitizible where

._ I
92 ‘ x1' e6' 912' Y 4'
P4 = x2' e8' Y'4'
P6 ‘ Y4' e9' 911' z'

I
P7 ‘ Y4' 910' 812' Y 4-

Of p7, the edge e10 is not shared by any other paths of C.

Thus e10 s-a-l is undetectable. Removing both e and the

10

resulting redundant gate G2 from C results in C2 with all

paths sensitizible as shown in Figure 4.3.
4.2.3 Maximal and True Sensitization
of Path Sequences

The sensitization of a path sequence is defined in
terms of the sensitization of its consisting paths. Thus
the maximal and true sensitization of a path sequence will
be expressed in a similar way. However, in defining the
maximal and true sensitization of a path sequence, one
must consider, in addition to path-wise maximal sensiti-
zation, the maximal sensitization of the whole path
sequence which in turn, requires the maximal assignment

of all the strictly sensitizing sequential subcircuits.

 

For example, to sensitize ps = p4, p6 of the cir-
cuit of Figure 4.3, the sensitizing edge y3 must assume 1
in sensitizing p6, which in turn implies the sequential

subcircuit Cy3 must be l-maximally assigned, along with

137

 

 

 

 

 

 

 

 

 

X e
1 5
f
X e _—__f\ e
2 7 433/ 10 T2
e
9
Y
3 11‘ G
____. 1 '
Y4
e6

 

 

 

 

 

 

 

 

 

 

A
A

I
x1' 65' e10' z °r “1' 65' e10' Y 3

 

 

 

 

 

 

 

 

 

 

'0
F:
H

'U
n:
u

x1' e6' Y'4

p3 ‘ x2' e7' 610’ z °r x2' e7' 910' y'3
P4 = x2' e3' Y'4

95 = y3' e9' e10' z °r y3' e9' elO' y'3

p6 ‘ Y4' e9' 610' z °r Y4' e9' e10' y'3

i = (OIO) = (xlIx2)I 11 = (0'1)! i2 (1'0)! 13 (lIl)

so = (0,0) = (Y3IY4)I 31 = (011)! 32 ‘ (1'0)! 33 (III)

Fig. 4.3.—-A sequential circuit with all paths sensitizible.

138

the sensitization of p4, in order for ps to be maximally

sensitized.

Definition 4.8

 

Given a path sequence ps = pl, p2, ..., pn of a
sequential circuit C, sensitized with a sequence of input-
state vectors to C, is = v1, v2, ..., vn, a sequential

subcircuit Ce, with the output edge e incident on pi,

 

lsisn, consists of a set of subpath sequences and/or
sections of path sequences all with the common trailing

edge e. The sequential subcircuit is formed as follows,

 

starting from e proceeding towards the leading edges of
the consisting subpath sequences or sections of path
sequences.
1. Include the subcircuit with the output edge e, of
the associated combinational circuit of C, in Ce'
2. If Ce includes a state input edge y, then Ce
should be extended to cover the constituent cir-
cuit Cy, of the associated combinational circuit.
3. Repeat 2 to correspond to pi_1, pi_2, ... p2, p1.
Thus for the example above, the incident sequential
subcircuit Cy3 incident on p4, in the sensitization of ps

is

CY3 = {pll Y3; p3! Y3; pSI Y3; p6! Y3}’

139

The maximal assignment of a sequential subcircuit
will be similarly defined as a subcircuit in a combina-
tional circuit. With this, the maximal sensitization of a

path sequence can be readily defined.

Definition 4.9

 

 

A path sequence ps = pl, p2, ..., pn is s-maximally

sensitized, if every pi, lsispn is s-maximally sensitized

 

and every strictly sensitizing sequential subcircuit is E-

maximally assigned. It is s—maximally sensitizible if

 

this is possible. It is maximally sensitizible if it is

 

possible for both values of s.
If a path sequence is to be s-sensitized, but is
not s-maximally sensitizible, then, as in the combinational

case, s-true sensitization should be sought instead. In

 

this situation, as in the combinational case, at least one
subpath sequence for every s-non-maximally assigned sen-
sitizing sequential subcircuit must be included in some
s-maximally sensitizible path sequence in order to attain
s-true sensitization for the path sequence in question.

Such a path sequence is called a critical sensitizing path

 

sequence, with s as its critical sensitizing value, as in

 

the combinational case. In this way, the s-sensitization
of a path sequence ps, is said to depend on its critical
sensitizing path sequences, psi, ps., etc., being able to

3
pass their corresponding critical sensitizing values, 31’

140

Sj' ..., in order for ps to be actually sensitized to

pass 3. This is expressed in notation as follows.

. . s 51 . sj .
is. ps /{(Ci' psi ), (Cj, psj ), ....},

where is is the sequence of input-state vectors used to
sensitize ps to pass 3, C1 is the non-maximally assigned
sensitizing sequential subcircuit corresponding to pi,
etc. If confusion will not thus occur, isJ Ci and C.
will be omitted.

If a path sequence ps is defined to be s-maximally
sensitized of nth order with a sequence of input-state
vectors, is! within a set of sequences of input-state

vectors, IS, as in Definition 3.12, the s-true sensiti-

 

zation of ps can be defined as follows.

Definition 4.10

 

A path sequence ps is said to be s-truly sensitized

 

with a sequence of input-state vectors is! and within a set
of sequences of input-state vectors IS, if there exists a
number n such that ps is s-maximally sensitized of nth

order with is, and within IS.

Example 4.2

 

The circuit C of Figure 4.3 will be used to illus-

trate these definitions. The path sequence ps4 = p4, p6

is l-maximally sensitized with isI = i3, 10 applied to C
in state s3. The path sequence ps2 = p2, p6 is not

141

l-maximally sensitized with is.2 = 10, 10 applied to C in
state 53 since the sequential subcircuit Cy3 is not 1-
maximally assigned. The critical sensitizing path sequence
section is p5, y3 or p6, y3 with the critical sensitizing
value of l. The path sequence ps52 = p3, p5 is l-maximally
sensitized withis52 = '1, 10 applied to C in so. Thus
with ps4, p552 l-maximally sensitized, ps2 is l-truly
sensitized with isz and within (i3, 53), (i0, 33), (i1, so),
(io, 53), with which ps4 and p352 are l-maximally sensitized
respectively.

The maximal and true sensitization of a path of a
sequential circuit are defined in terms of its embedding

path sequence.

Definition 4.11

 

A path p of a sequential circuit is s-maximally

 

sensitizible if at least one path of its set of path

 

sequences PS is s-maximally sensitizible, otherwise it is

s-non-maximally sensitizible. If p is s-non-maximally

 

sensitizible, then it is s-truly sensitizible if at least

 

one path of PS is s-truly sensitizible. The question of
s-true sensitizibility of the s-non-maximally sensitizible
paths of a sequential circuit also arises in connection
with its fault analysis. As in the combinational case,
every s-non-maximally sensitizible path is s-truly sensi-

tizible.

142

Theorem 4.5

 

In a sequential circuit with every path sensi-
tizible, every s-non-maximally sensitizible path is s-
truly sensitizible.

Proof: The proof is similar to that of Theorem 3.5.
If there existed a path which was not s-truly sensitizible,
then since none of its set of path sequences is s-maximally
sensitizible, there could exist a set of undetectable
faults in contradiction to the assumption that every path
of the circuit is sensitizible. And the assumption causes
at least one detectable fault if the circuit is faulty.

Q.E.D.

4.3 Faults of Sequential Circuits

 

Faults in sequential circuits will be analyzed and
interpreted, as in combinational circuits, in terms of
path sequence checking. Thus by determining the ability
of the path sequences in passing both signals, faults in
the sequential circuit can be detected down to equivalent
faults. The basic approach used in studying faults of a
sequential circuit is the same as that used for a combina-
tional circuit, with the path sequences taking the place
of paths.

If a path sequence is actually sensitized and
tested to pass both signals, it is free of stuck-at faults
iff it is checked. The proof for this would be similar

to that of Theorem 3.6 and is thus omitted.

143

The same types of faults, undetectable, single,
multiple and equivalent faults, are also found in a
sequential circuit. In addition, faults may occur on
feedback lines.

The definitions for Section 3.3 will also apply
in this section with "paths" replaced by "path sequences"
and "a combinational circuit" by "a sequential circuit."

If a set of subpath sequences defines an s-type
maximal faulty sequential subcircuit, then an s-type
fault will occur at the output edge of such a subcircuit.
Similar to Theorem 3.7, an s-type fault in a sequential
circuit is single iff it occurs at the output edge of an
s-type maximal faulty sequential subcircuit. The proof
would be analogous.

If an s-type maximal faulty sequential subcircuit
has every subpath sequence s-unsensitizible, i.e., not one
path sequence including it is s-sensitizible, then the s—
type fault at its output edge is undetectable. Such unde-
tectable faults might form multiple faults as in a com-
binational circuit.

Thus all the faults in a sequential circuit are
identified, in the same way as in a combinational circuit,
within the context of the set of path sequences selected
for a test to cover all the paths of the sequential circuit.
The following example will illustrate the different types

of faults.

144

Example 4.3

 

Consider the sequential circuit of Figure 4.1. The
fault f6:y'6 s-a-l will be a single fault caused by the
two subpath sequences x1, e8, e13, y'6 and x3, y'6 sticking

f f all

7’ 2' 12
:y'S s-a-l, will not be detectable because

at 0 and 1 respectively. With the faults f

s-a-O, then f5

y'4 cannot assume the sensitizing value 1 due to the fan-
out at e9. Similarly, f4:y'4 s-a-l will not be detectable

in the presence of f7, f2 and £12. However, f4 amd f5

collectively form a detectable multiple fault in the

f and f .

presence of f 2 12

7’

4.4 Positioning the Sequential Circuits
in a DesiredL_Known State

 

 

Given a sequential circuit under test in a random
and unknown state, it must first be initialized to some
desirable and known state before a detection or diagnosis
experiment can be performed on it. The positioning of the
circuit in the desired state means applying a selected
input sequence and observing the corresponding output
sequence to ensure that the circuit has been correctly
positioned. This section is devoted to designing such
input sequences and additional procedures that are neces-
sary to position the sequential circuit under test at some
desirable and known state.

The positioning procedure consists of two steps;

the first step drives the circuit from some unknown state

145

to any known state from which the second step drives the
circuit to a desirable state according to the state dia-
gram of the circuit.

Before one attempts to design a method of obtaining
the positioning input sequences a couple of observations
will be made. First, if the circuit under test is actu-
ally faulty, then it might be possible that no input
sequences will ever drive the circuit to the desired state.
This, of course, will be indicated by the absence of the
correct corresponding output sequences expected. In this
case, the circuit in effect has been detected faulty.
Second, if the circuit is initially in a state from which
the desired state is unaccessible even though the circuit
is fault-free, it is impossible then to drive the circuit
to the desired state. For such circuits, fault detection
and diagnosis are clearly confined to those states acces-
sible from the starting state the circuit was in at the
time of test.

The basic idea used in the designing of the posi-
tioning input sequences for the first step is to assign
signal values to the state variables of the circuit, or, if
impossible for some of the state variables, to find out the
signal values they assume throughout this step. Thus the
signal values of all the state variables, and thus the
current state of the circuit are determined at the end of

the application of such an input sequence. In order for

146

this to be possible, the state variables of the circuit

should each be observable at the output edges. A state

 

variable is observable at the output edges if there exists at

 

least an input sequence such that, through the application
of the input sequence, a subpath sequence starting with
the state input edge of the state variable and ending

with a circuit output edge is sensitized.

It can be proved that every state variable of a
sequential circuit is observable if every path of the
sequential circuit is sensitizible. This is because unob-
servable state variables will in no way contribute to the
logical behavior of the circuit and hence are redundant.

In addition to being observable, a state variable

may also be controllable, which makes it possible for some

 

signal value to be assigned to the state variable from the
input edges of the circuit. A state variable is control-
issis from the input edges if there exists at least an
input sequence such that through the application of the
input sequence, a subpath sequence starting with a circuit
input edge and ending in the state input edge of the state
variable is sensitized. Thus a state variable being con-
trollable provides part of the logical function of intro-
ducing some of the applied signal values to the memory of
the circuit.

Through the controllability and observability of

its state variables, a sequential circuit can be

147

positioned in a known state regardless of the original
state it assumed before the application of a positioning
input sequence. The positioning input sequences, however,

will be determined during the positioning process.

Theorem 4.6

 

For every sequential circuit with all paths sen-
sitizible, there exists at least one input sequence which
drives the circuit to a known state from an unknown state.

Proof: First, since all paths of the circuit are
sensitizible, all state variables of the circuit are
observable. Also at least one of the state variables is
also controllable. Otherwise the circuit could not be
sequential. Hence every state variable of the circuit will
either be controlled or observed during the application of
a selected input sequence which can be determined during
the positioning process. Since the number of state vari-
ables is finite, the signal values on all the state vari-
ables can be determined with an input sequence of finite
length. And thus at the end of the application of such an
input sequence, the state of the circuit is known. Q.E.D.

Design of Positioning Input
Sequences

 

 

A positioning input sequence consists of two parts,
the known—state part and the desired-state part.
To design the known-state part, first assign the

signal variable si to the state variable yi for all the

148

state variables. Then whenever the value of yi is known,
it is assigned to 51’ Then for every state variable not
controllable, find the input sequence which causes it
observable and assign the value to its signal variable.
After all the state variable not controllable have thus
been determined, the remaining undetermined variable can
easily be determined since they are controllable. The
known—state part will then consist of such input sequences.

The desired—state part is then calculated from the
state diagram of the circuit.

The following example will help illustrate the

procedure.

Example 4.4

 

Consider the circuit C of Figure 4.4 with two state
variables yl and y2. Clearly y2 is controllable while y1
is not. Because for all the possible assignments to x and
Y2' the next state variable y'1 is still a function of yl.
Thus there is no way to assign a signal value to yl.
However, y1 is observable when y2 has a signal value of 1.
Thus an input sequence of is = 1,1 will sensitize the path
p = y1, ea, eb, 2. And at the end of is, 2 will have the
signal value y1 assumed at the previous state of the cir-
cuit. From this one can calculate the previous state, and

thus the current state of the circuit.

149

.4.4 mamamxm mom aflsouflo Hanucmsvmm <1:.v.q .mwm

 

 

 

 

AV Y

 

 

 

 

 

 

 

AV v

 

 

 

 

 

 

 

 

 

 

_1_1

 

 

 

 

 

 

 

 

 

NAI

 

v!

150

4.5 Fault Detection of
Sequential Circuits

 

 

In this section, the design of detection tests and
an algorithm for conducting the fault detection of sequen-
tial circuits are presented. The results of such a
detection test can be used for fault diagnosis as will be
discussed in the next section.

A faulty sequential circuit may also be detected,
apart from a detection test, through the positioning pro-
cedure to initialize the circuit in a starting state, when
the expected output sequences are not obtained as a
response to the positioning input sequences applied. In
this'case the same diagnosis algorithm will also be used
to locate the faults.

The basic approach in designing and fault detecting
a sequential circuit is to check every path of the sequen-
tial circuit. This means that for every path of the sequen-
tial circuit, there should be included in the test at least
two path sequences (they may be the same) which contain the
path and one of which is sensitized to pass 1 and the other
sensitized to pass 0. Every path sequence should be either
s-maximally sensitized or s-truly sensitized within the
test.

Another aspect in designing a detection test, that
is unique to sequential circuits is the sequencing of the
individual input-state vectors to form testing input

sequences. This is necessary to provide for the

151

consistency of the present next state serving as the next
current state throughout the testing sequences.
4.5.1 The Path Sequence Sensitization
Table and Maximal Compatible Sets

The whole procedure used in forming the Path
Sequence Sensitization Table, PSST, and the MCS for a
sequential circuit is similar to that of a combinational
circuit; the main difference is that, instead of the paths,
one is working with the path sequences of the sequential
circuit. The MCS, from which a detection test is formed,
is built from the PSST. The PSST is a table which includes

all the path sequences of the sequential circuit.

The Construction of the PSST

 

Consider a sequential circuit C with ni input
edges, nS state input edges, nO output edges and nS state
output edges. The edges of C, including fan-out edges,
are uniquely labelled. Let there be a total of ne edges
which include the circuit input edges, the state input
edges, the circuit output edges, the state output edges

and the remaining edges of C. Let PS be the set of path

sequences of C.

}

PS = {psi; lilinps

The PSST consists of input-state vectors (input

vector concatenated with state vector) each of which

152

sensitizes one or more paths of C. The PSST is formed as

follows.

1.

There are ne columns corresponding to the ne
edges of C.

For every path sequence ps E PS, there are two
sets of rows to test ps pass 0 and l, denoted by
ps0 and ps1 respectively.

For a given set of rows corresponding to psis,
assign the corresponding sensitizing values to
edges incident on ps, 3 to edges on ps with even
parity, E to edges on ps with odd parity between
the edges and the trailing edge of ps.

Enter signal values to edges which can be deter-
mined through fan-outs, NOT gates and feedback
lines. The input edges to OR gates whose output
edges assuming 0 and the input edges to AND gates
whose output edges assuming 1 can also be deter-

mined.

Except for the arrangement of the rows within it,

the PSST thus formed is unique. The only edges assigned

values on the PSST are those on the path sequences, those

incident on the path sequences and those whose values are

thus determined from the first two types of edges. An

example

illustrates the procedure.

Example 4.5

 

153

Consider the sequential circuit C of Figure 4.5

with four circuit input edges, two circuit output edges

and three state variable edges.

edges and 15 paths.

p1 X1' e14' 917' 21

p2 X1' 914' Y's

p3 Xz' e8' 914' e17' 2
p4 X2' ea' e14' Y's

95 x2' e9' e15' e18' 2
p6 X2' 99' e15' y'7

p7 X3' e10' e15' 918'
pa X3' e10' e15' Y 7
p9 X3' Y's

p10 = x4' e16' 22

p11 7 Y5' 311' 912' e16'
p12 = Ys' 811' e13' 21
p13 = Ye' e11' 912' e16'
p14 = Ye' 911' 913' 21

There are a total of 23

154

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

f s-a-O
x 1
ea
x2————J»
e9
6 I
f J
10 €10 y! 1
x s-a-O 6
3 v
f s-a-O
4
612
e
y5 ell 13
I’D
Y6 y-, y,
Y' ‘--- 5
L ‘L 7
1* .
Y 5
A 4
Z: ~4~
4—

 

 

 

 

 

 

 

Fig. 4.5.--The sequential circuit for Example 4.5.

follows.

The

PS

PS

PS

PS

PS

PS

PS

PS

155
y7' 22

sets of path sequences of the paths are as

= {psl} = p1

= {9521' p522}
p821 = 92' p11
pS22 = p2' p12

= {ps3} = p3

= {9541' 9342}
ps41 = p4' p11
ps42 = p4' p12

= {p85} = p5

= {p56}
ps6 = p6' p15

= {ps7} = p7

= {p58}

p88 = p8' p15

156

P89 = {9591' p592}

pS91 = p9' p13

ps92 = p9' p14
PS10 = {9510} = p1o
PS11 = {9321' 9341}
PS12 = {9322' 9542}
PSl3 = {p591}
PSl4 = {p592}
PS15 = {p56, p58}
Thus there are a total of 13 path sequences,

PS

{psll p321! p522! ps3! p841! p842! p55! p36
p37' pSB' 9391' 9592' pSlO}'

The PSST will be a table of 26 sets of rows, two
sets for each path sequence passing both 0 and l, and 23
columns corresponding to the 23 edges of C. It is shown

in Table 4.1.

The Forming of the MCS
The process used in forming the MCS from the PSST
is somewhat different from that of the combinational case.

This is due to the fact that within the same constituent

Table 4.1.-'Tho PSST tor Ext-pl. 4.5.

1.55'7

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

I I
751% ’7 ‘1d'11 e12"13 .14.ISI.16°17‘.18]Y r01‘"?
0 0
901(5) 11 111101101011
1 1
9.1191) 11 1 1 1 1 1 1 1 1 1 1 1
s° 1 0 1 o
921 1 0 1 1
o
(p2.pn) 011 o 0 o 0
1
pin 1 1 1 1 1 1 1 1
1
(lep11) 111 1 1 1 1
0
pa” 1 0 1 0 1 0 1 1
(p°p°) 011 o 0 o 1 1 1 1 1 1
2'12
1
9-22 [1 1 1 1 1 1 1 1
1
(132.912) 111 1 1 1 1 1 1 1 1 1 1
”30(1230) 11 1 1101101011
1 1
9.3“:3) 11 1 1 1 1 1 1 1 1 1
° 1 o 1 o 1 o 1 1
9'41
o
(p‘ . 911 ) o 1 1 0 0 0 0
1
p.“ 1 1 1 1 1 1 1 1
1
(p‘.pu) 111 1 1 1 1
0
pg“, 1 o 1 o 1 0 1 1
(° °) 011 0 o 0 1 1 1 1 1 1
1
pa“ 1 1 1 1 1 1 1 1
1
(p‘.p12) 111 1 1 1 1 1 1 1 1 1 1
p.5°(p5) 1 1 o 1 1 1 1 o 1 o 1 o o
1 1
pas (ps) 1 1 0 1 1 1 1 1 1 1 1 o 1
o
p. 0 0 o 0 0
6
(p6 . 915 ) 0 0 0 O 0 1
1
p06 0 1 1 1 1 1 0 1
1
(126.1215) 101 0 o 0 1
p370 (p70) 1 1 0 1 1 1 1 O 1 0 1 0 0
”71(5) 11 111111 11111
p.80 0 o o o 0
0
(128.915) 00 0 o 0 1
1
p08 1 1 1 1 1
1
0
9191 o 1 1 1 1 1 0 1
0
p.91 1 1 1 1 1 1 1 1
1 1
0
p.92 0 1 1 1 0
0
(1:94:14) 10 0 0 0 1 1 1 1 1 1
1
p.92 1 1 1 1 1 1 1 1
(129.54) 111 1 1 1 1 1 1 1 1 1
pom (p10) 1 0 o 0 o
[2010(910) 1 o 0 o 1

 

 

 

 

 

158

circuit, there are path sequences of different lengths
(number of paths). In forming the maximal compatible rows
for the constituent circuits, only rows of the same order
will be combined to form maximal compatible rows. Given a
path sequence ps = pl, p2, ..., pn, the row pis; lsisn,

will be called of (n - i + l)th order. Another point that

 

needs attention is that in assigning signal values to the
path sequences, the state input edge and state output edge
of the same state variable should assume the same signal
value at all times to ensure consistency of signal assign-
ments for the path sequences.

The first step in forming the MCS is to form the
MCS for each of the constitient circuits. To do this, the
rows of the first order of the path sequences belonging to
the same constituent circuit are first considered in form-
ing maximal compatible rows. Then if a set of path sequences
PS whose rows of ith order form some maximal compatible row,
the rows of (i + l)th order of PS only will be used further
in forming maximal compatible rows. In this way, the path
sequences of the same constituent circuit are considered
in forming the MCS starting from the trailing paths working
towards the leading paths.

For example, for the constituent circuit C21

1 l l l 1
(Example 4.5) the rows pl (ps1 ), p7 (ps7 ), p14
1 l l l l
(ps92 ), p12 (ps22 ) and p12 (ps42 ) of the PSST form
a maximal compatible row (l,0,l,,l,l,l) = (x1, x2, x3, x4,

159

l and ps7 are of

length l and p522, ps42 and p592 are of length 2. Thus
1 l

y5, y6, y7). Of the path sequences, ps

the rows p21 (pszzl), p4 (ps4zl) and p9 (psgzl) of 2nd

order can only be considered further for forming maximal

compatible rows. Of the three rows, p2l (pszzl) and p91

(psgzl) form a maximal compatible row (1,0,1,,,,) and p41

l (psgzl) form another maximal compatible

(ps4zl) and pg
row (0,1,1,,,,).

In the second step, on the maximal compatible rows,
the entries corresponding to the sequential subcircuits
incident on the path sequences being sensitized are
assigned values. These sequential subcircuits are assigned
values as was done in the combinational case: maximally
assigned if possible.

For example, of the path sequences previously con-
have all the entries corresponding to

sidered, ps and ps

1 7
C21 assigned in the maximal compatible row (l,0,l,,l,l,l).

For ps and ps with the rows (l,0,l,,,,), (l,0,l,,l,l,l),

22 92
all the sensitizing sequential subcircuits have also been
assigned values. The sequential subcircuit incident on

p2 (p322) is the subpath x2, e8 which has been assigned

in (l,0,l,,,,). The sequential subcircuits incident on

p12 (p522) are the subpath sequence x3, y'6, y6, the
sequential subcircuits C817 and Cel8' The subpath sequence

has been aSSigned Wlth (l,0,l,,,,) and Ce17 and Ce18 have

been completely assigned with (l,0,l,,l,l,l).

160

Since it takes a sequence of maximal compatible
rows to sensitize a path sequence of length larger than

one, such a sequence will be called a maximal compatible

 

row sequence. It should also be pointed out that a row

 

as referred to here actually is an incompletely defined
input-state vector.

In the third step, all the maximal compatible row
sequences will be used to form maximal compatible row
sequences for the entire circuit. However, in doing so,
two considerations need to be made. First, it is neces-
sary to form input-state vector sequences from the row
sequences later in designing the tests. So the state
variable components of the row sequences which have not
been assigned values should be left free to assume all
possible values in order to make concatenations of row
sequences possible. Second, in order to require every
individual row perform detection in a test, row sequences
of equal lengths only will be used in forming maximal com-
patible row sequences in this step.

The state variable components then will be assigned
the value x, which is compatible to itself only.

In the final step, the remaining entries in the
maximal compatible row sequences are arbitrarily assigned
values as they don't affect the sensitization of the path
sequences. Or their assignments can be delayed until the

input-state vectors are being formed later.

161

The set of input-state vector sequences thus
obtained is the MCS. The following theorems prove that the
MCS is all that one needs in forming the detection tests.
First the s-maximal sensitization of s-maximally sensi-

tizible path sequences with the MCS is proved.

Theorem 4.7

 

Every s-maximally sensitizible path sequence is
s-maximally sensitized with some input—state vector
sequence from the MCS.

Proof: First, every s-sensitizible path sequence
is included in the PSST. Given ps s-maximally sensitizible
with an input-state vector sequence is. Thus with is,
every strictly sensitizing sequential subcircuit is maxi-
mally assigned. Now in forming the MCS from the PSST, the
strictly sensitizing sequential subcircuits of ps are
assigned values in the second step. In that step every
sensitizing sequential subcircuits are maximally assigned
if possible. Hence since ps is found in the PSST, is will
be found in the MCS. Q.E.D.

The next theorem proves the s-true sensitization
of s-non-maximally sensitizible path sequences within the

MCS.

162

Theorem 4.8

 

Every s-non-maximally sensitizible path sequence
is s—truly sensitizible within the input-state vector
sequences that can be formed from the MCS.

Proof: First, every s-non-maximally sensitizible
path sequence ps is s-truly sensitizible with some is_
within all the possible vector sequences to the sequential
circuit. That means all the critical sensitizing path
sequences of ps found in is are either s'-maximally sensi-
tizible or indirectly s'-maximally sensitizible. In other
words, ps depends on a set of path sequences which are s'-
maximally sensitizible for some values of 3'. But the set
are s'-maximally sensitized within the MCS from Theorem 4.7.

Q.E.D.
4.5.2 The Path Sequence Checking
Fault Detection Algorithm

The Path Sequence Checking Fault Detection Algo-
rithm can now be formulated. One problem of fault detection
of a sequential circuit that was not found in the fault
detection of a combinational circuit is the necessity to
ensure the prOper starting state of the sequential circuit
before a test is applied. Thus it will be assumed that
the actual starting state of the sequential circuit can
be known so as to guarantee that the correct starting

state is obtained before a test is applied.

163

Given a sequential circuit C with the set of paths

P

{pi; lilinp},

a fault detection algorithm to detect the presence of

faults is formulated as follows.

Step A.

Step B.

Form the MCS for C.

Form the detection tests T for C. A detection

test t e T is formed as follows.

1.

Select a set of path sequences PS such that

t,
every path of C is included in the set.

Find a set of input-state vector sequences,

IS from the MCS such that every psis,

t!

ps 8 PS 5 = 0 and l, is s-maximally sensitized

t,

with some is 8 IS or s—truly sensitized with

t!

is, within ISt'

The set ISt is not a subset of another IS't
that can be formed in step 2.

Form an input sequence with the set Ist'
placing maximally assigned input-state vector
sequences (i.e., they s-maximally sensitize
their corresponding path sequences) at the
beginning portion of the sequence, if possible.
Appropriately assign values to entries with x

in the input sequence so that the current and

next state variables have the same signal

164

values. Arbitrarily assign values to the
remaining entries.
Step C. Position C to some starting state 50 so
that a test t e T is applicable to C. If C is
detected faulty during the positioning to the
starting state, as found from the incorrect output
vectors, the presence of faults have been detected,
and there is no need to proceed in the algorithm.
Step D. Apply a t e T to C. If every path is checked,
then C is fault-free, otherwise it is faulty.
The validity of the algorithm is proved in the

following theorems.

Theorem 4.9

 

There exists at least a detection test as defined
in the algorithm.

Proof: As was shown previously, one can find a set
of input-state vector sequences as defined in 2 of Step B.
Thus a test can always be found. The state variable com-
ponents of the input-state vector sequences have been
allowed to assume any values and hence a sequence of input-

state vector sequences can be designed. Q.E.D.

Theorem 4.10

 

A sequential circuit (with all paths sensitizible)
is fault-free iff a detection test, as described in the

Path Sequence Checking Fault Detection Algorithm, detects

165

no faults. It is faulty iff the detection test detects
the presence of faults.

Proof: Since every path of the circuit is included
in the test, thus the whole circuit including the feedback
lines are included in the test. If the circuit C is fault-
free, then certainly the detection test t will detect no
faults. If t detects no faults, then those path sequence
s-maximally sensitized are free of s-type faults. Then
those path sequences s—truly sensitized in turn are free
of s-type faults because all of their critical sensitizing
path sequences are s-maximally sensitized. And since the
starting state is guaranteed to be correct, hence C is
fault-free. On the other hand, if C is faulty, then since
the starting state is correct, t will detect faults,
otherwise C would be fault-free. If t detects the presence
of faults, then faults will occur on some path sequences
s-maximally sensitized or s-truly sensitized or both.
Otherwise, with the correct starting state, the output
vector sequence produced would not reflect detection of
faults on s-maximally sensitized path sequences, and thus
also would not reflect detection on s—truly sensitized path

sequences. Q.E.D.

166

4.5.3 An Example

Example 4.6

 

The circuit C in Figure 4.5 will be used in the
example. The PSST is shown in Table 4.1. The first step

in forming the MCS is to form the maximal compatible rows

for both constituent circuits C21 and C22.
MCR = {MCR1, MCRZ}
For Czl’ the rows of first order are used to form the

following maximal compatible rows.

0 o
. p3 }

V11 = {pl
= (OIOIlIIlIlI)

0 0 0 0 }

v12 = {p12 (ps22 ). p12 (ps42 )

= (IIIIOIlIlIIIIOIOIOIlIlIIlIlIlIIlIOI)

_ o o

= (lIOIOIIlIlI)

_ o
v14 ' {P14 }

= (IIIIIIOIIIIIOIOIOIlIlIIlIlIlIIllol)

_ 1 1 1 l l l 1
V15 - {pl I p7 I p12 (p322 )I P12 (p542 )I p14 }

= (lIOIlIIlIlIl)

167

1 1}

v = {p l p l p 1 (ps 1) p (ps 1) P
16 3 ' 5 ' 12 22 ’ 12 42 ’ 14

(Olllolllllll)

0

0
and p542

The rows of second order corresponding to p522

of v12 are combined to form

0

_ o o o
v17 — {p2 (ps22 ). p4 (ps42 )}

(010111!!!)-
For v14, there is only one row of second order
_ 0 0
V18 ‘ {99 (9392 )}
= (IIOIIII)o

For v15, two maximal compatible rows can be formed.

_ 1 1 1 1
V19 - {p4 (ps42 ). p9 (ps92 )}

= (OrlIlIIII)

_ 1 1 1 1
v110 — {p2 (ps22 ). p9 (ps92 )}

(IIOIIIIII)

Similarly for V16' there are two maximal compatible rows.

1 1 }

_ 1 1
viii ‘ {P4 (9542 )' p9 ‘ps92 ’

(Oil-Ill!!!)

v19

168

1 1 1 }

_ 1
V112 ' {92 (9322 )' p9 (9592 )

= V110

So for C the maximal compatible rows formed in the

21'
first step are

MCR1 = {V11' V12' v13' v14' V15' V16' V17' v18'

v19' V110}'

For C22, the maximal compatible rows formed from the first

order rows are

_ o o o o o
v21 ‘ {P11 (9321 " p11 (p541 )' p10 }

I

= (IIIOIOIlIl) I

0 0 0 }'

_ o
v22 {p15 (ps6 ). p15 (ps8 )

=(III1IIOIO)I

0}.

v ={p 0(ps 0) p
23 13 91 ' 10

= (IIIOIlIOIl) I

1 1 1 1

1
(ps42 ). p15 }

I

(ps 1) p (ps 1) p
21 ' 11 8 ' 13

v24 = {p11
= (III0I1I1I1)I

1 1}

(ps 1) p
6 ' 10

<
II

I

25 {915

(III1I1I0I1)I

26

The maximal

rows are as

27

28

29

210

V211

v212

213

169

1 1}

l

I
(,,.l.,l.l)-

compatible rows formed from the second order

follows.

_ o o o o

_ {p2 (P521 )I P4 (9541 )}
= (OIOIlIIII)

_ 0 0 0 O

— {p6 (ps6 ). Pa (988 )}

= (IOIOIIII)

_ 0 0

— {p9 (P591 )}

= (IlIOIIII)
_ 1 1 1 1 1 1
- {p2 (ps21 ). pg (988 ). p9 (p89l )}

= (1I0I1IIII)

1 1

= {94 (ps411). p9 (p8911)}

= (oIlIlIIII)

1 l }

= {96 (986 )

= (IlIOIIII)

1

_ 1
— {98 (ps81 )}

= (IoIlIIII)

170

Thus for C ,
22

MCR = {

2 V21' v22' V23' v24' v25' v26' V

V

27' 28'

v29' V210' V211' V212' V213}'

In the second step in forming the MCS, every sensitizing
sequential subcircuits are assigned values maximally, if
possible. For example, notice that p392 being 0-sensitized

With isgz = V18' V14 has the senSitiZing sequential sub-

circuit C and the sensitizing subcircuit C and C
y5 e17 e

To max1mally aSSign Cy5' vl8 becomes

18'

V (lIlIoIIII)I

18 =

and v becomes

14

V (IIIIlIOIlIIIIOIOIOIlIlIIlIlllIIlIOI)°‘

14 =

To max1mally aSSign Ce17 and Ce18’ vl4 becomes

v14 = (l,l,1,,1,0,1).

The other maximal compatible rows can be similarly further

defined as follows.

V12 = (l,1,l,,0,l,1)
v22 = (,,,l,l,0,0)
v26 = (,,,l,0,l,l)
v28 = (1,0,0,,,,)

171

V29 = (lllIOIIII)
V212 = (1I1I0IIII)
V213 = (OIOIIIIII)

In the third step in forming the MCS, assign x to
the state variable components, y5' y6, y7, which have not
yet been assigned, in every row. And then forming maximal
compatible row sequences from the row sequences of equal
lengths found in the second step, one gets the following

input-state vector sequences.

0

- _ _ 0
is — {v11} — {pl , p3 }

(OIOIllllllIX)

. _ o o o
——2 ’ {V17' V12' V27' V21} ' {9522 ' ps42 ' ps21 '

I'"
U)
I

s 0 0}
P 41 ' p10

(0.0.1,,XIXIX). (1,1,1.0,0,1.1)

° _ _ 0 0
£§3 - {V13} — {P5 I P7 }

(lIOIoIIlIlIX)
. _ _ o o
1&4 — {V28' v22} - {ps6 , p38 }

= (lIOIOIIXIXIX)I (IIIlIlIOIO)

is

18

is

is

is

is

——10

1&11

= {

={

172

0

0 0}

{V18’ V14' v29' V23} = {9592 ' ps91 ' p10

(1.1.0..X.X.x).
_ o

{v23} — {p10 }
(Illollloll)
_ o
{v21} — {p10 }

(IIIOIOIlIl)

{

s 1 s 1 1
P 8 I P 91 I pl I p7

(1.0.1..X.X.x).

{

1 1

V110' Vis' V210' V24} = {9322

(1,1,1,0,1,0,1)

1
1}

(1,0,1,0,1,1,1)

_ 1
v210' v24' V112' V16} ‘ {9522 ' ps92 '

l 1 1}

(1.0.1..X.X.x).

1 1

V19' V15' V211' V24} = {9542

(OIlIOIOIIIlII)

1

1 1

p841 I P391 I p1 I p7 }

(0.1.1..x,X.x).

(1,0,1,0,1,1,1

”211' ”24' V111' V16} = {9541

1 1 1 1
9842 . 9892 . p3 . 95 }

(ollllIIXIXIX)I

(0,1,0,0,1,1,1

S l S l
I p 92 I p 21 I

1

S l
I P 92 I

)

1 s 1
I p 91 I

)

173

- _ _ 1 1
1212 " {V15} ’ {pl ' P7 }
= (lIOIlIIlIlIl)
- _ _ 1 1

= (OIlIOIllIlIl)

is = {v

_ o 1 1
-—14 18’ V14' V212' V25} ‘ {9592 ' pS6 ' p1o }

(lplIOIIXIXIX). (1,1,1,1,1,0,1)

is = {v v v v } = {ps 0 ps 0
——15 17’ 22' 213' 26 22 ' 42 ’

1 1
p58 ' ps10 }

(OIOIlIIXIXIX)I (lllllIlIOIlIl)

1}

£316 {V25} = {p10

(IIIlIlIOIl)

. 1
LE17 = {V26} = {P10 }

(,rylroylpl)

In the final step, the remaining entries can be
assigned any values. However, it would be preferable to
delay the assignments until the test sequence is to be
formed in order to form maximal compatible input—state

vector sequences at that time.

174

For those path sequences not s-maximally sensitized

with the input-state vector sequences, their dependence

sets are listed in the following.

Step B,

sets of

0 1}

. . o 1, 1 1
iii' Pi ' p3 /{p7 ' ps22 or ps42 or ps92

0 0

. o 1
i§2° pS21 ' pS41 ' p10 /{Pss }

. . o o 1, 1 1 1
£53' ps ' p7 /{Pi ' ps22 °r ps42 °r ps92 }

. o o 1
$§4° pS6 ' p58 /{Pio }

0

. o 1
£55' ps91 ' p10 /{Pse }

is ° p 0/{ps 1- ps 0}
-—6° 10 6 ' 91

. . o 1, o o
is7. p10 /{ps8 , psz1 or p341 }

i£114: 9101/{95910}
i315‘ p101/{95210 °r 95410}
i316‘ piol/{psgio}
i§17‘ p101/{95210 °r 95410}

This concludes the construction of the MCS. In
the detection tests are designed. There are two

path sequences each cover all the paths of C.
P51 = {931. p522, ps3. p541. pss. pss. ps7. p88.

9591' 9392' 9310}

175
P32 = {981. p821. ps3. p842. p85. ps6. ps7. 988.

9591' 9592' 9510}

To cover PS there are two sets of input-state

1!
vector sequences from the MCS that can be formed, each of

which qualifies to form an input sequence.

Isl = {151. E2: 1.8.3. g4. 15.5. 1_58. 1511. 1_Sl4}
IS2 = {-1—31' 52' gr 1—“?'-4' 1215. Lg9' Qio' 1—5-14}

To cover PS the same two sets are also formed. Thus IS

2' 1
and 182 are the only sets of input-state vector sequences
for consideration in the synthesis of input sequences.

To form an input sequence from IS the state vari-

ll
ables can now be assigned values. Since all psis are not
s-maximally sensitized with 1&4: it will be placed at the
end of the input sequences. If one forms an input sequence

as
t1 = 32' 335' 3—5-8' iS-ii' 9314' 334'

then the state variables can be assigned as follows and

thereby is and is3 can be eliminated from t, since they

1
form maximal compatible vectors with is and is4 respec-

tively.
is = (oIoIlIIlIlI1)I (llllllolollll)

is = (1I1I0II1I1I1)I (lllIllollloll)

176
_i_s_8 = (llolllllllll)l (lIOIlIOIlIlIl)

isll = (0,1,1,,1,1,1), (0,1,0,0,1,1,1)

£14 = (1I1I0II1I0I1)I (lllllllllloll)

E4 = (lIOIoIIlI1I1)I (IIIlIlIOIO)

The remaining entries can assume any values since they
do not serve any purposes in the test. Let all assume
zeros.

Let the sets of inputs, states and outputs of C be

assigned as follows.

10 = (OIOIOIO) = (XII x2! X3I X4)
i1 = (Olololl)

115 = (l,l,l,l)

So = (0,010) = (YSI YGI Y7)

U)
l

(0.0.1)

(1,1.1)

(I!
II

177

00 = (0,0) = (21, 22)
01 = (0,1)
02 = (1,0)
03 = (1,1)

Then the input—state vector sequences can be expressed in

terms of inputs and states of the circuit as follows.

——8 10' 7' 10' 7
i—§11 = i6' S7' i4' S7
£314 = 112' S5' 115' S5
£§4 = 13' S7' 11' 54

Similarly from 182' t2 is formed as

t2 = E2' E5' E9' lg10' E141' $34
with

i_89 = (1I0I1I0I1I1I1)I (0I1I0I0I1I1I1)I

£10 = (0I1I1I0I1I0I1)I (1I0I1I0I1I1I1)I

-_1_S_141 = (1I1I0I0I1I1I1)I (1I1I1I1I1I0I1)I

178

or in terms of inputs and states.

£59 = 110' S7' 14' S7'

£510 = 16' 55' 110' S7'

$§141 = 112' S7' 115' 55'

In Step C, the circuit should be positioned in s7 for
either test. Since every state variable is controllable

from the input variables, an input of i14 or i15 alone

should guide C to $7.

In step D, applying the test sequence

to C and observing its output vector sequence thus produced

constitute a detection test.

Let the set of faults be F occurring on C, in

Figure 4.5 where

f }I

f10' 4

s-a-0, flo: elo s-a-O and f4: x4 s-a-O.

The output vector sequences obtained, 0, under a
:fiault-free condition and o (F) with F, as well as the state

Sequence obtained with F, s (F) are listed as follows.

179

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Stl S7 s3 s7 85 S7 87 S7 S7 s5 S5 s7 s4 s0
115t1 115 12 114 112 114 110 110 16 14 112 115 18 l1
ot1 1 01 00 03 oo 03 03 03 01 00 01 01 001

!

St1(F) 5 s7 52 s7 s5 s7 52 s2 s7 35 35 37 80 s
i
z ;
°t1(F) °1 lo °3 °o °1 °o °o °3 °o °o °1 °o§

 

 

The results of the detection test clearly indicate the
presence of faults. For example, the first discrepancy of
output vectors was detected with the application of is8 =
110, 37, 110' s7 which resulted in the output vector
sequence of 01’ 00 from the fault F, instead of 03, 03
under a fault-free situation. The results can be further

analyzed to serve as a basis for a diagnosis procedure.

This is discussed in the next section.

4.6 Fault Disgnosis of Sequential Circuits
The basic approach in the fault diagnosis of
sequential circuits is the same as that of combinational
circuits: to determine the ability of the paths of the
sequential circuit in passing both signals. The diagnosis
process, however, is more complicated due to the necessity
of positioning the state variables when detecting input-

state vector sequences are to be applied to the circuit.

180

An algorithm is presented in this section to locate all
the detectable faults in the circuit. As in the combina-
tional case, different sets of equivalent faults can be
obtained from different assignments of s-unsensitizible

path sequences.

4.6.1 The Diagnosis Approach
The process of checking the paths of the sequential
circuit involves identifying maximal faulty subcircuits of
the associated combinational circuit for single faults.
After this step, multiple faults can then be located by

checking multiple path sequences.

Location of Single Faults

 

The method of identifying maximal faulty subcir—
cuits in a sequential circuit is more complicated than that
of the combinational case. In determining a suspected
maximal faulty subcircuit, every path of the subcircuit
which has not been determined in its ability to pass the
corresponding signal should be tested to pass that signal.

Given a detectable s-type maximal faulty subcircuit
within a given fault picture, there exists at least a path
of the subcircuit which is s-sensitizible; i.e., the path
can be embedded in an s-sensitizible path sequence. To
confirm the maximal faulty subcircuit, then, every 5-

sensitizible path of the subcircuit must be shown to fail

181

to pass 3. The proof is similar to Theorem 3.16 and is
omitted.

The following definition describes the formation
of input-state vector sequences to sensitize a maximal

faulty subcircuit.

Definition 4.12

 

Given an s-type suspected maximal faulty subcir-
cuit Ci defined by a set of paths Pi with ei as the output
edge of Ci' A set of Ci-sensitizing input-state vector
sequences is formed as follows:

1. For every path p.

3
within the given fault picture, find all the s-

6 Pi which is s-sensitizible

sensitizible path sequences containing pj. Then
find the input-state vector sequences each of which
causes the s-type signal to prOpagate between the
leading edges and ei of the path sequences and the
s-type signal is sensitized between ei and the
trailing edges of the path sequences.

2. Form maximal compatible input-state vector sequences
ISi from the input-state vector sequences found in
l for all s-sensitizible paths of Pi'

3. Find input-state vector sequences to drive the
sequential circuit to the desired starting states
of 131.
The following theorem proves the existence and

validity of the input-state vector sequences, as found in

182

Definition 4.12, in sensitizing the maximal faulty subcir-

cuits.

Theorem 4.11

 

A set of Ci-sensitizing input-state vector sequences
as defined in Definition 4.12 exists and will s—sensitize
Ci, suspected faulty of s-type.

Proof: Since Ci is s-sensitizible within the given
fault picture, hence there exists at least a path sequence
containing pj 8 Pi which is s-sensitizible on the subpath
sequence between ei and its trailing edge. Hence an input-
state vector sequence exists which can s-sensitize the path
sequence as described. Now since ISi contains all such
input-state vector sequences s-sensitizing all the s-
sensitizible path sequences defining Ci' hence ISi will
detect Ci' Also for every s-sensitizible path sequence
psj defining Ci' the circuit can be driven to a starting
state for‘isj e ISi to s-sensitize psj, otherwise psj

would be s-unsensitizible. Q.E.D.

Example 4 . 7

 

To illustrate Definition 4.12 consider the circuit
C of Figure 4.3 with Ce9 suspected of s-a-O. For y3,
the path sequences W111 be either p551 = pl, p5 or p352
(see Example 4.2). This is because if e5 and e7 both s-a—O,
then Ce9 s-a-O is not detectable. Similarly for y4, the

path sequences will be ps2 and ps If the fault picture

4.

183

being e s-a-O, then the input sequence (,1,,), (0,0,l,l)

5

will l-sensitize Ce If e s-a-0,

9 52 4' 7
then the input sequence (l,l,,), (0,0,l,l) will also 1-

along ps and ps

senSitize Ce9 along pss1 and ps4. In this example, no

initial positioning input sequences are needed.

Location of Multiple Faults

 

The situation in which multiple faults in a
sequential circuit are detected is similar to that of a
combinational circuit; the difference being that the paths
containing the detectable multiple faults must be embedded
in multiple path sequences for the multiple faults to be

detected.

Definition 4.13

 

An s-sensitizible multiple path sequence is a set

 

of path sequences Psi, each psj e PSi is to be tested to
pass 3, and it has the following characteristics.
1. Each psj e PSi is by itself s-unsensitizible.
2. There exists a set of gates G on PSi such that the
s-type signal propagating on path sequences of PSi
is dominant to every 9 e G.
3. PSi is s-sensitizible, i.e., every psj e PSi
is s-sensitizible except for those incident edges
belonging to other path sequences of PSi' These

edges are feeding gates of G and will assume the

dominant value 3 in the s-sensitization of psj.

184

4. No subset of PSi has the above characteristics.
Thus, as in a combinational circuit, multiple
faults will occur on multiple path sequences in a sequen-
tial circuit. The proof is similar to that of Theorem
3.17 and will not be repeated.
Sensitization Involving

UnsensitiEibIe Critical
Sensitizing Paths

 

 

 

In the s-sensitization of a path sequence involving
unsensitizible paths to provide the necessary sensitizing
values, the unsensitizible sensitizing paths can be assumed
to be capable of providing the right sensitizing values.

This was proved in Theorem 3.18.

Outline of the Diagnosis Process

 

As in the combinational case, the diagnosis process
seeks to establish the fault set F starting from the results
of a detection test. Based on the detection results, the

P P P can be formed. A diagnosis

G’ B' U' S
process will then reduce PU and PS to null and thus will

four sets P

completely establish PG and PB' From PB the set of faults
F, or its equivalent, will be located.

However, there is one situation in the diagnosis
process of a sequential circuit which was not found in the
combinational case. If a sequential circuit was found

faulty during the initial state positioning for a detection

test, then a detection test was never applied to it.

185

Thus, in this case, the most one can do is to, based on
the output vector sequences obtained from the positioning
input sequences, assign maximal faulty subcircuits to the
output edges of the sequential circuit. And the set PS
will include all the pi8 or psiS and the other three sets
will be null as the starting basis of the diagnosis pro-
cess.

A suspected path or path sequence can also be
indirectly determined as follows.

1. If a set of path sequences was s-maximally
sensitized and found faulty of s-type, then if all
path sequences of the set except one are disproved
of s-type faults, the remaining path sequence is
indirectly confirmed faulty of s-type.

2. If a set of path sequences was s-non-maximally
sensitized and found faulty of E—type, then if all
path sequences of the set except one are disproved
of s-type faults and the dependence set is proved
able to pass the critical sensitizing values, the
remaining path sequence is indirectly confirmed
faulty of s-type.

3. If a set of path sequences was s-non-maximally
sensitized and found free of s-type faults, then
if its dependence set is proved able to pass the
critical sensitizing values, the set is indirectly

disproved faulty of s-type.

186

4. If all paths of a path sequence that can contain
s-type faults were disproved faulty of s-type,
the path sequence is indirectly disproved faulty
of s-type.

5. If a path sequence was confirmed faulty of E—
type, then if all of its paths except one are dis-
proved faulty of s-type, the remaining path is
confirmed faulty of s-type.

6. If a sequential subcircuit was s-sensitized and
found faulty of s-type, then if all of its depend-
ence sets are proved able to pass the critical
sensitizing values, the set of path sequences
defining the sequential subcircuit is indirectly
confirmed faulty of s-type.

The graphical representation of the diagnosis
process for a combinational circuit in Figure 3.7 also
describes the diagnosis process of a sequential circuit.

4.6.2 The Path Sequence Checking Fault
Diagnosis Algorithm
The diagnosis algorithm proceeds with the basis

B = {PG' P P , PS} obtained from the results of a

B' U
detection test. Given a sequential circuit C with the
set of paths P and tested with a detection test t which

covers the set of path sequence PS. The basis B is

formed as follows.

187

1. For every path sequence psi 8 PS s-maximally

sensitized with some is e t which detects no E-

type faults on psi, include psiS in PG.
2. For every path sequence psi 8 PS which is indirectly

disproved of sticking at E, include psiS in PG.

3. For every path sequence psi 6 PS which is

indirectly confirmed of sticking at 5, include

3 .
psi in PB.

4. Include every path sequence psi 6 PS as psi5 6 PU
if it becomes s-unsensitizible within the fault
picture established thus far.

5. Include the remaining path sequences as psis in
PS for the appropriate 3.
If C was found faulty, during an initial state
positioning process, include every path sequence psi 6 PS

as psis, for both values of s, in PS. The other sets of

B are null.

Given a sequential circuit C with the set of paths

P. It is found faulty either in the application of an

initial state positioning input sequence or from a detection

test t which covers the set of path sequences PS. The

P

resulting basis established is B = {PG’ P PS}. A

B' U'
fault diagnosis algorithm to locate all the detectable
single and multiple faults, F, is presented as follows.

A. Find a set of s-sensitizible path sequences PsiS 5

PS which, except for the s-unsensitizible paths of

 

188

a maximal faulty subcircuit Ci’ defines Ci' If
no such PSiS exists, then find such a set which

depends on P for critical sensitizing paths.

U
Notice that s = 0 or 1.

Form a set of Ci-sensitizing input-state vector
sequences ISi.
Apply ISi to C. If Ci is known to be s-sensitized

with ISi’ then if Ci is found faulty of s-type,

8

move PSi to P or if Ci is found free of s-type

BI
faults and Ci is defined by one path sequence only,

move PSiS to P Otherwise mark Ci as tested.

G.

s . .
Move every psi 8 PS to either PG or PB if psi

is thus indirectly determined. Also move psis

to PU if it becomes s-unsensitizible within the
existing fault picture.

Repeat A through D until all maximal faulty sub-
circuits have been tested. A maximal faulty sub-
circuit tested should not be chosen in step A.
Move the remaining psiS 8 PS to PU.

Test every s-sensitizible multiple path sequence

PSiS e PU for multiple faults. If multiple faults
are detected, move PsiS to PB.
. S .
Ass1gn any psi 6 PU to either PG or PB.
3 . . . .
Remove psi e PU to either PG or PB if it is thus

indirectly determined.

Repeat G through H until PU is reduced to null.

189

J. For every PsiS 6 PB which defines a maximal sub-
circuit Ci faulty of §-type, with the output edge ei,
include fi: ei s-a-s in F. If fi propagates down
some path and stops at ej assuming the signal value
5', then include fj: ej s-a-s', instead of fi' in
F. Remove Psis from PB. Repeat this until PB is
reduced to null.

The validity and convergence of the algorithm is

proved in the next theorem.

Theorem 4.12

 

The path sequence checking fault diagnosis algorithm
for the sequential circuit will locate all the detectable
single and multiple faults of the circuit in a finite number
of steps.

Proof: A fault in a sequential circuit is detect-
able if it can be sensitized to an output edge of the
circuit within the given fault picture. The rest of the
proof is similar to that of Theorem 3.19; the only differ-
ence is that one works with the path sequences which cover
all the paths of the circuit in this case, rather than the

paths of the circuit. Q.E.D.

190

4.6.3 An Example

Example 4.8

 

Continue with the results obtained from the

detection test in Example 4.6, one finds the following

basis,

P = {ps 0 ps 0 ps 0 ps 1 ps 1 p 1

G 22 ' 42 ' 92 ' 41 ' 91 ’ 3 ’

l
ps92 }'

where ps 0 and ps 0 are determined from is ps 0

22 42 ——2' 92

. l l . l 1

from 1.5 and ps41 , p591 from isll, p3 from ps42 , and

l 1
p392 from p59l ,

_ 0 0 0 0 0 0 0
P — {p1 I P3 I p341 I ps I ps6 I p7 I p58 I

S o o 1 S 1 1 S 1 1
p 91 ' p10 ' p1 ' P 22 ' p5 ' P 6 ' p7 '

l 1
p88 I p10 }

I

PB=PU=g.

Since ezl and e22 are free of faults, the maximal faulty

sequential subcircuits are found as follows.

0 _ 0 O . .
Pl7 — {pl , p3 } defining C17

0 _ 0 0 . .
P18 — {p5 , p7 } defining C18

0 0 0 0

_ 0 . .
PSl6 — {p10 , ps41 , p52l , p591 } defining C16

0 0

_ o . .
PS7 - {ps6 , p38 } defining C7

191

1 1 1 . .
1 {p1 , p52l , p322 } defining C1

PS

1 _ 1 1 . .
PS9 — {p5 , p56 } defining C9
1 — 1 1 O .
PS10 - {p7 , p58 } defining C10
1 _ 1 O C

To start the diagnosis procedure from the outputs

of the circuit, C will be determined first. The fault-

17

sensitizing input-state vector sequence for C17 is

£318 (lllIlIIII)I (OIOIlIIlIlI1)’

= V181' V182!
. . . 0 0 1
With isl8. pl , p3 /{p7 }.
The output vector sequence obtained from the
application of is to C is

18

018 = (I)! (0I1)I

which indicates no detection of faults. Hence the basis
is not updated. For C18’ the input-state vector sequence

and the resulting output sequence are

$§19 = Vl8l' (1'°'°"1'1'1) = V181' V19'

. o o 1
1§19o 95 1 p7 /{p1 }.

019 = (I)I (OI-1)-

192

Again no faults are detected and the basis is not updated
due to the undetermination of p11.

For C16’ there are two fault-sensitizing input-

state vector sequences,

1&20 (1.1.0....). (,,,o,1,o,l) = v201' V202'

is ° 0 s 0 s 0/{ s 1}
.—-2° P10 ' P 41 ' P 21 P 8

I

0

. . o 1
iizo' P10 ' P591 /{P36 }°

The input-state vector sequence is2 was used in the

detection test. The output vector sequence from is20 is
020 = (I)! (I0).

No faults are detected and again the basis is not updated.
For C7, the fault-sensitizing vector sequence and

the resulting output vector sequence are

ifi (lIOIOIIII)I (IIIlIlIOIO)

21 = = V211' v212

1},

. o 0
i521' PS6 ' P38 /{P10
021 = (I)! (I0)-

Again no faults are detected and the basis is not updated.
For C1, the fault-sensitizing vector sequence and

the output vector sequence are

193

_j-_S_22 = V181! (1I0I1II1I1I1)I (1I1I1I0I1I1I1)'

V181' V221' V222'

022 = (I)I (Oll)I (0'0).

Hence the results indicate that p522 s-a-O is confirmed.
This in turn indirectly confirms p1 s-a-O. Because of

p1 s-a-O, p5, p7 become 0-unsensitizible. Also p7 becomes
l-unsensitizible. This also in turn makes p1 and p3 0-

unsensitizible. Thus the basis is updated as follows.

PG: unchanged

_ o 1
Ps - {ps41 . 936 . p53 . p891 . p10 . p5 . 936 .

s 1 1}
P 8 I P10

1 l
B {p1 ' ps22 }

"U
II

{ 0 0 l 0 0}
U p5Ip7lp7Ipllp3

P

is

The fault sensitizing vector sequence for C10

(III1I1I1I1)I

i§23 V181' V221'

= V181' V221' ”23'

The resulting output vector sequence is

023 = (I)! (011)! (OIO)°

. . l 1 . .
Since is23. p58 /{p10 }, so the baSis is unchanged.

194
For C9, the fault-sensitizing vector sequence is

is =

24 v181I (lllIoII1I1I1)I (III1I1I0I1)I

= V181' V241' V242°

The output vector sequence obtained is

024 = (I)I (1'1)! (I0)

which indicates no detection of faults on p5 and detection

 

of faults on p36. But since p5 is l-maximally sensitized
with i§24, so p5 passing 1 is confirmed. Which in turn

indirectly confirms ps6 passing 1.

Also indirect determination finds psglo, p100 a

. . . 1 .
PG which in turn finds p10 8 PB. Again ps6 and ps8

become 0-unsensitizible, p38 becomes l-unsensitizible due

to p101 5 PB. And ps41 becomes O-unsensitizible because
of p581 8 PU. Hence the basis is updated as follows.

P = { s O s 0 s 0 s 1 s 1 l
G P 22 ' P 42 ' P 92 ' P 41 ' P 91 ' P3 '

1 l l 0 0
p592 I ps I p56 I p591 I P10 }

{ l s 1 1}
B P1 ' P 22 ' P10

'O
II

_ 0 0 0 0 1 0 0 0
PU _ {ps I p7 I pl I p3 I p7 I ps6 I p88 I p841

p381}

Of the set PU, the following multiple path sequences can

be formed.

195

PSml — {p3, p5}

Psz = {ps4l, ps6}

The fault sensitizing input-state vector sequence testing

0 .
PSml is

i§m1 = V181' (°'°'°"1'1'1) = V181' Vmi'

The resulting output vector sequence is

Oml = (I)! (OI)-

Thus no multiple faults are detected.
For PSmZ' the fault-sensitizing input-state vector
sequence testing Pszo and the resulting output vector

sequence are

ismz = (OIoIlIIII)I (OIOIlIO) = vm21l Vm22I

(I), (.0).

0m2

Also no multiple faults are detected.

Now different assignments of elements of PU to

either PG or P will result in equivalent sets of faults.

B

If one assigns pl0 6 PB, then p30 6 PB is determined.

Because of these assignments, p5 and p7 become 0-sensitizible

and p7 becomes 1-sensitizible and hence p50, p7O a PG,

p l e P are obtained. And no multiple faults are created.

7 B
0

Also if one assigns p360 8 PB' then p58 6 PB is deter-
mined. Also p5410 e P results because of p380 6 P

G B'

196

Finally p581 can be randomly assigned since p58 is still

l-unsensitizible. Let p581 5 PB. Hence the basis result-

ing from these assignments looks as follows.

P = { s 0 s 0 s 0 s 1 s 1 l
G P 22 I P 42 I P 92 I P 41 I P 91 I P3 I
1 1 1 o o o 0
P592 I PS I P56 I P391 I P10 I PS I P7 I
0
P541 }

{ 1 S 1 1 0 0 l S 0
B Pl I P 22 I P10 I Pl I P3 I P7 I P 6 I

"U
ll

0 1
ps8 , p58 }

The set of faults obtained from PG is
FT = {fl' flO’ f4, £17, £7}:
where
£17: el7 s-a—l,
f7: e7 s-a-l.

Since both f7 and £17

of F, hence both sets of faults, F

are not detectable in the presence

T and F, are equivalent.

4.7 Characteristics of the Method as
Applied to Sequential Circuits

 

 

The observations of Section 3.6 regarding the path
checking method as applied to combinational circuits
similarly apply to sequential circuits. In addition to

these observations, the following further observations can

197

be made of the path checking method as applied to sequen-
tial circuits.

First, the fault analysis proceeds at the circuit
level, rather than at the state diagram level. Thus one
does not have to be concerned with the various character—
istics of the sequential machine, i.e., state accessibility,
equivalency of states, etc.

Second, this method is general enough to cover a
wide range of sequential circuits. The only condition is
that every path of the circuit under test is sensitizible.
If the method as presented in this thesis is extended to
cover sequential circuits containing redundant circuitry,
then the method will be applicable to practically all types
of sequential circuits found in current fault analysis

studies.

CHAPTER V

CONCLUSIONS AND SUGGESTIONS FOR FUTURE WORK

5.1 Conclusions

 

This thesis presents a method to detect and locate
stuck-at type logical faults in switching circuits by
checking every path of the circuits for its ability to
pass both signals. The method approaches both combinational
and sequential circuits from the same "path" viewpoint, with
the sequential circuit considered as an extension of the
combinational circuit.

Based on the path checking approach, two detection
algorithms are developed for the generation of detection
tests for combinational and sequential circuits. The
results of a detection test can then be used as a basis
for the fault diagnosis algorithms. The checking of maximal
faulty subcircuits is the basic approach used in developing
the two fault diagnosis algorithms for combinational and
sequential circuits. The fault diagnosis process is more
involved than the fault detection process because of its
dependence on the current fault pictures as found throughout

the process. However, the fault diagnosis algorithms can

198

199

terminate at any point during the diagnosis process if the
corresponding degree of fault diagnosis is satisfactory.

Since the detection process is straightforward,
the detection algorithms can be easily implemented. The
implementation of the diagnosis algorithms, however, is
more complicated due to the dependence of the diagnosis
algorithms on the current fault picture.

The method serves as a starting point for fault
analysis of sequential circuits at the circuit level. The
various difficulties and the resulting restrictions
encountered during the development of the method are dis-

cussed as follows for further research.

5.2 Suggestions for Future Work

 

One obvious extension of the method that needs
further research is to allow unsensitizible and partially
sensitizible paths in the switching circuits considered.
This extension allows, in effect, redundant circuitry to
be added to the circuits and thus covers most types of
switching circuits that are found in current fault analysis
studies. Unsensitizible and partially sensitizible paths
were encountered during the diagnosis process as a result
of other faults in the circuit. The difficulties of sen-
sitizing these paths were solved, in this thesis, by
treating these paths as multiple paths. Thus, it seems
that the concept of "multiple paths" is one approach to

check the redundant parts of the switching circuits.

200

The EXCLUSIVE OR gates were excluded from conside-
ration in this thesis not because of any unsolved diffi-
culties with them, but because of the need for extra
attention to paths containing them. A path going through
an EXCLUSIVE OR gate is always sensitized, at the gate,
regardless of the signal value on the other input edge of
the gate. Thus it is necessary for the other input edge
of the EXCLUSIVE OR gate to assume the same signal value,
throughout the computation of a test, in order for the
path in question to be validly sensitized. This will
hence modify the procedures for designing the tests as
presented in the thesis.

Further studies need to be done on the various
relations and interpretations of the various character-
istics at the sequential machine level in terms of the
path structure at the circuit level. For example, equiva-
lence of states in a sequential machine can be interpreted
in terms of path sensitization in its realized circuits.

Finally, more research needs to be done to adopt
this method to integrated circuits. When individual com-
ponent circuits are combined to form integrated circuits,
unsensitizible or partially sensitizible paths may be
created in the integrated circuits even though all the
individual component circuits contain sensitizible paths
only, as shown in Figure 5.1. In the figure the paths

P1 = la! eCI eel zI P2 = 1b, ed, ef’ Z are l-

201

 

 

 

 

 

CI C11

Fig. 5.l.--Partially sensitizible paths result from con-

catenating circuits C and C to form an inte-

. . I II

grated Circuit.
unsensitizible. The multiple path approach might be used
to solve this problem. Also it might be interesting to
investigate the methods to combine individual detection
tests for the component circuits to form "integrated tests"

for the resulting integrated circuits. This could prove

to be a worthy effort.

BIBLIOGRAPHY

I “\pmfi

10.

BIBLIOGRAPHY

Armstrong, D. B. "A General Method of Applying Error
Correction to Synchrous Digital Systems." Bell
System Tech. J., Vol. 40, pp. 577-593.

 

 

Breuer, M. A. "Testing for Intermittent Faults in
Digital Circuits." IEEE Trans. Comput., Vol. C-22,

 

Carter, W. C. "Fault-Tolerant Computing: An Intro-
duction and a Viewpoint.” IEEE Trans. Comput.,
Vol. C-22, pp. 225-228, March 1973.

 

Chang, H. Y., Manning, E., and Metze, G. Fault
Diagnosis of Digital Systems. New York: Wiley-
Interscience, 1970.

 

Chang, L. "Fault Analysis of Combinational Logic
Networks." Ph.D. Thesis, Michigan State Univer-
sity, 1974.

Clegg, F. W. "Algebraic Properties of Faults in
Logics Networks." Ph.D. Thesis, Stanford Univer—
sity, 1970.

Du, M., and Weiss, D. "Multiple Fault Detection in
Combinational Circuits: Algorithms and Computa-
tional Results." IEEE Trans. Comput., Vol. C-22,
pp. 235-240, March 1973.

 

Farmer, D. E. “Algorithms for Designing Fault-
Detection Experiments for Sequential Machines."
IEEE Trans. Comput., Vol. C-22, pp. 159-167,
February 1973.

 

Friedman, A. D. "Faults Detection in Redundant Cir-
cuits." IEEETrans. Electron. Comput., Vol. EC-l6,
pp. 99-100, February 1967.

 

Harrison, M. A. "An Analysis of Errors in Finite
Automata." Inform. Contr., Vol. 8, pp. 435-450,
August 1965.

202

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

203

Hartmanis, J., and Stearns, R. E. "A Study of Feed-
back and Errors in Sequential Machines." IEEE
Trans. Electron. Comput., Vol. EC-12, pp. 223-232,
June 1963.

 

Hartmanis, J., and Stearns, R. E. Algebraic Structure
Theory of Sequential Machines. Englewood CIiffs,
N.J.: Prentice-Hail, 1966.

 

 

Hecht, H. "Figure of Merit for Fault-Tolerant Space
Computers." IEEE Trans. Comput., Vol. C-22, pp.
246-250, March 19731

 

Hennie, F. C. "Fault Detecting Experiments for
Sequential Circuits." Proc. §th Annual Symp.
Switching Theory and Logical Design, November 1964.

 

 

Hsieh, E. P. "Checking Experiments for Sequential
Machines." IEEE Trans. on Computers, Vol. C-20,
pp. 1152-1168, October 1971.

Kamal, S. "Diagnosis of Intermittent Faults in
Digital Systems." Ph.D. Thesis, Michigan State
University, 1973.

Kime, C. RI "A Failure Detection Method for Sequen-
tial Circuits." Dept. of Elect. Eng., Tech. Rep.
66-13, University of Iowa, 1966.

Kohavi, I., and Kohavi, Z. "Variable-Length Distin-
guishing Sequences and Their Applications to the
Design of Fault—Detection Experiments." IEEE
Trans. Comput. (Short Notes), Vol. C-l7, pp. 792-
795, August 1968.

 

Kohavi, z., and Lavallee, P. "Design of Sequential
Machines with Fault-Detection Capabilities."
IEEE Trans. Electron. Comput., Vol. EC-16, pp. 473-
484) August 1967.

 

Kriz, T. A. "Machine Identification Concepts of
Path Sensitizing Fault Diagnosis." IEEE Conf. 10th
Annual Symposium on Switching and Automata Theory,
pp. 171-181.

 

 

Lyons, R. E., and Vanderkulk, W. “The Use of Triple-
Modular Redundancy to Improve Computer Reliability."
IBM J. Res. Dev., Vol. 6, pp. 200-209, April 1962.

 

Martin, R. L. "The Design of Diagnosible Sequential
Machines." Proc. Hawaii Internat. Conf. Syst. Sci.,
1968.

23.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

204

McCluskey, E. J., Jr. Introduction to the Theory of
Switching Circuits. New York: McGraw-Hill, 1965.

 

McCluskey, E. J., Jr., and Clegg, F. W. "Fault
Equivalence in Combinational Logical Networks."
IEEE Trans. Comput., Vol. C-20, pp. 1286-1293,
November 1971.

 

Meyer, J. F. "Fault Tolerant Sequential Machines,"
IEEE Trans. Comput., Vol. C-20, pp. 1167-1177,
October 1971.

 

Meyer, J. F. "On the Structure of Fault Tolerant
Sequential Machines." Proc. 3rd Hawaii Int. Conf.
Sci. (Part I), pp. 443-447, January 1970.

 

Miller, R. E. Switching Theory Vol. II: Sequential
Circuits and Machines. New York: John Wiley &
Sons, Inc., 1965.

 

Moore, E. F., and Shannon, C. E. "Reliable Circuits
Using Less Reliable Relays." J. Franklin Inst.,
Vol. 262, pp. 191-208, September 1956, and pp. 281-
297, October 1956.

 

Moore, E. F. "Gedanken Experiments on Sequential
Machines." Automata Studies, Annals oi Mathe-
£22195 Studies, no. 34, pp. 129-153. Princeton,
N.J.: Princeton University Press, 1956.

 

 

Peterson, W. W. Error-Correcting Codes. New York:

1

Wiley and Cambridge, Mass.: M.I.T. Press, 1961.

Pierce, W. H. Failure-Tolerant Computer Design,
Chapts. III and IV. New York: Academic Press,
1965.

 

Poage, J. F. "Derivation of Optimal Tests to Detect
Faults in Combinational Circuits." Proc. Symp. on
Mathematical Theory of Automata, PolytechniEi
Institute of BroOklyn, pp. 483-528, 1963.

 

 

Poage, J. E., and McCluskey, E. J., Jr. "Derivation
of Optimum Test Sequences for Sequential Machines."
Proc. 5th Annual Symp. Switching Theory and Logical
Design, 1964}

 

Ramamoorthy, C. V. "Fault-Tolerant Computing: An
Introduction and An Overview." IEEE Trans.
Comput., Vol. C-20, pp. 1241-1244, November 1971.

 

35.

36.

37.

38.

39.

40.

205

Roth, J. P. "Diagnosis of Automata Failures: A
Calculus and a Method." IBM J. Res. Devel., Vol.
10, pp. 278-291, July 1966.

 

Sellers, F. F., Hsiao, M. Y., and Bearnson, L. W.
"Analyzing Errors with the Boolean Difference."
IEEE Trans. Comput., Vol. C-l7, pp. 676-683,
July 1968.

 

Seshu, S., and Freeman, D. N. "The Diagnosis of
Asynchronous Sequential Switching Systems."
IRE Trans. on Electronic Computers, Vol. EC-ll,
pp. 459-465, 1962.

Su, S. Y. H., and Chang, S. Y., and Breuer, M. A.
"Location of Multiple Stuck-Type Faults in Com-
binational Networks." IEEE Comput. Soc.
Reposit. R-72-l96, 1972.

 

Tryon, J. G. "Quaded Logic." Redundancy Techniques
for Computing Systems, pp. 205-228. Washington,
D.C.: Spartan Books.

 

Von Neumann, J. "Probabilistic Logics and the Syn-
thesis of Reliable Organisms from Unreliable Com-
ponents." Automata Studies, Annalsgf Mathe-
matics Studies, no. 34, pp. 43-98. Princeton
University Press, 1956.

 

 

 

“nil
...Kuu.
......J- . In”.
_