A model for sequential machine testing and diagnosis

Abstract. A mathematical framework for the testing and diagnosis of sequential machines is developed. A very general fault model is used in which a faulty machine is represented asa sequential machine, possibly with state and output sets different from those of the good machine. A deterministic finite automaton, called observer, describes the process by which one gains information from the observation of the responses to test sequences. It generalizes the work of Hennie on distinguishing and homing sequences, by modelling all the possible conclusions that could be drawn from observing the circuit under test. A nondeterministic a ceptor is derived from the observer; it ac-cepts diagnosing sequences and can also be used to generate test sequences. We then associate probabilities with this nondeterministic a ceptor which, together with a stochastic source of input symbols, provides a probabilistic diagnoser. As a particular application we consider the testing and diagnosis of random-access memories by ran-dom test sequences. Our model generalizes the work by David et al. on the calculation of the length of a random test sequence required to guarantee that the probability of detection of a fault exceeds a prescribed threshold