A model for sequential machine testing and diagnosis

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 as a 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 acceptor is derived from the observer; it accepts diagnosing sequences and can also be used to generate test sequences. We then associate probabilities with this nondeterministic acceptor 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 random 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.This work was supported by the Natural Sciences and Engineering Research Council of Canada, Grants OGP0000871 and OGP0000243, and a grant from the Information Technology Research Centre of Ontario. Preliminary papers leading to this work have appeared earlier [1] [2].