This paper describes procedures for the design of experiments that distinguish a given n-state machine from all other machines which have n states or less. Such experiments can also be used in certain cases to determine whether or not a given machine is operating correctly. We shall be mainly concerned with finite-state, strongly connected machines which are in a reduced form.

New techniques are presented for generating fault-detection experiments for combinational logic networks. Only single-output functions are considered. Test-covering and test-equivalence relations between networks are defined and these relations are shown to be Instrumental in generating the experiments. The techniques presented provide minimal experiments for detecting multiple faults In two-level networks and provide nearly minimal experiments for most other networks.

Abstract—A variable-length distinguishing sequence (VLDS) is a preset distinguishing sequence X0such that, if the machine is started in an unknown state, the output response of the machine to some prefix of X0will identify the initial state. The length of the required prefix is a function of the initial state. The properties of such sequences are investigated and a method which employs a modified version of the diagnosing tree is developed for generating and displaying all such sequences. The fixed-length distinguishing sequence (FLDS) is shown to be a special case of the more general VLDS. The VLDS is next applied in the design of simple and efficient preset fault-detection experiments for sequential machines.

The minimal number of terms required for representing any switching function as a modulo 2 sums of products is investigated, and an algorithm for obtaining economical realization is described. The main result is the following: every symmetric function of 2m+1 variables has a modulo 2 sum of products realization with at most 3mterms; but there are functions of n variables which require at least 2n/n log23 terms for sufficiently large n.