Design of Sequential Machines with Fault-Detection Capabilities

A sequential machine for which any input sequence of a specified length is a distinguishing sequence is said to be definitely diagnosable. A method is developed to obtain for any arbitrary sequential machine a corresponding machine which contains the original one and which is definitely diagnosable. Similarly, these techniques are applied to embed machines which are not information lossless of finite order, or which do not have the finite-memory property, into machines which contain either of these properties. Simple and systematic techniques are presented for the construction, and the determination of the length, of the distinguishing sequences of these machines. Efficient fault-detection experiments are developed for machines possessing certain special distinguishing sequences. A procedure is proposed for the design of sequential machines such that they will possess these special sequences, and for which short fault-detection experiments can be constructed.