17-03-2014, 09:41 PM
ABSTRACT
We present an efficient and fault-model independent method €or
diagnosing multiple faults in digital systems. Our method is
simpler to implement than the method that employs a ATMS
with a constraint system, or the method that employs a theorem
prover with the minimal hitting set algorithm.
Given the model of a boolean digital system, an input vector,
and a set of observed output values, our method computes the
set of all minimal diagnoses (candidates). Our method begins
with a system output that is incorrect. Using system behavior
model it computes a set of minimal potential candidates that
account for the behavior of that incorrect output. Our method
then incrementally considers the remaining system outputs and
extends the existing minimal potential candidate set to account
for their behaviors.
A minimal candidate is a minimal set of components whose
hypothesized faulty outputs account for all correct and incorrect
outputs of the system under some input vector. We show that
minimal candidates do not contain components whose faulty
outputs are either masked or non-observable. We also show
that for boolean systems supersets of candidates are candidates
only for certain component fault models.
1. INTRODUCTION
Diagnosis determines the causes of the differences between a
system's expected behavior and its observed behavior under
some input vector. The expected behavior of a system is
derived from the system's model. A system model specifies the
system's structure and the standard behaviors of the system's
primitive components. Model-based approaches to diagnosis
employ only general diagnosis principles and system models.
This paper presents a model-based approach to diagnosing multiple
faults in combinational boolean digital systems.
A candidate (diagnosis) is a set of components all of which
have been hypothesized to be faulty to account for all correct
and incorrect outputs observed in a system under an input vector
I. If all components in a candidate are actually faulty, then
replacing them with good components guarantees that all system
outputs will be correct under input vector I. Note that our
definition of a candidate is for a particular input vector I, not for
all input vectors.
In some model-based approaches to diagnosis of faulty boolean
systems, only a single faulty component is assumed [Gen84].
This assumption is used because the number of multiple faults
is much too large for most systems.