The authors describe a method for increasing the testability of digital circuits for single line stuck-at faults at the logic gate level by the addition of controllable and observable points in structures called testing modules. They also present a test generation algorithm that generates complete test sets, i.e. test sets that cover every possible fault, for increasingly large subcircuits. The test generation algorithm forms the basis for the design-for-testability method described. The authors introduce the concept of exhaustive test generation and of test set reduction, and show that the worst-case complexity of test generation can be estimated on the basis of the these concepts, without having to perform worst-case test generation. They describe the testing-module placement algorithm, whose aim is to reduce the complexity of test generation. It is based on the estimated complexity of test generation as developed. The extension of the method to sequential machines is briefly discussed.>

The authors present a method for increasing the testability of combinational circuits for single stuck-at faults by partitioning the circuit and inserting testing-modules. A testing-module structure that allows lines in the circuit to be logically disconnected is shown. It allows the circuit to be partitioned into independent subcircuits. A test generation algorithm that is based on test set merging is presented. An optimal testing-module placement algorithm is described for fanout free circuits. A special type of circuit with fanout for which optimal testing-module placement can also be performed is defined, and a testing-module placement algorithm for them is outlined. For general fanout circuits, polynomial testing-module placement and test generation algorithms are described. Testing-modules are used for partitioning the circuit into fanout free subcircuits. Test set merging that yields a complete test set for the circuit is described.>

In this note we investigate the conditions under which the paths which propagate a fault in a combinational network to the network output are not necessarily entirely sensitized.

The problem considered in this paper is that of generating sequential decision trees (SDT's) for fault diagnosis in digital combinational networks. Since in most applications of the decision tree the final conclusion will be that the network is failure-free, we are interested mainly in decision trees containing minimal fault detection paths. Such a procedure will reduce the cost of verifying the proper operation of the network.

Detection of intermittent faults was considered in a number of publications [1],[2]. Recently, Kamal [3] presented an approach to the diagnosis of intermittent faults in combinational networks. The methods developed so far, however, do not yield a minimal diagnosis experiment. Moreover, complete diagnosis is not obtained even in cases where it is possible.

In this paper, which is a follow up to [8], we are concerned with the problem of generating minimal experiments to locate and diagnose faults in combinational tree networks. We establish lower bounds on the necessary number of fault-locating tests and show how, in a systematic way, such experiments can be obtained. Two types of testing procedures are considered—adaptive and preset.

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.

In this paper, we are concerned with the problem of generating minimal fault-detection experiments for fanout-free combinational logic networks. We establish the greatest lower bound on the necessary number of fault-detecting tests and show in a systematic way how such experiments can be obtained.

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.

This paper is concerned with the problem of determining, by means of terminal experiments, whether a given combinational switching circuit operates correctly or is impaired by some malfunction. We shall be primarily concerned with permanent faults due to component failures. It is assumed that other methods will be employed to protect the circuit against the effects of transient faults. A procedure is presented for the detection of failures in combinational switching circuits. The procedure provides minimal sets of tests for two-level circuits and nearly minimal sets of tests for most multilevel circuits.

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.

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.

The realization of the output circuit is a topic which has been neglected in current publications in spite of the indisputable importance of the subject. In recent papers dealing with the problem of secondary assignment [1]-[3], [5], the main consideration was given to the transitions between the states and the realization of the circuits that control the secondary variables. In assigning the states of the secondary variables to the blocks of the partitions with substitution property or to the blocks of the partition pairs, we have a considerable amount of freedom. In the present paper it is shown how this freedom is used in order to obtain simpler Output circuits with reduced dependencies. The chief tools in this discussion are the partitions with substitution property in conjunction with the output-consistent partitions. Further it is shown how a simpler output circuit can be obtained by recognizing ``partially independent'' subsets in the output table and by using this property in order to achieve an assignment with reduced dependencies. The concept of partially independent subsets is seen to apply to machines which do not possess any partitions with substitution property or partition pairs and is used as a tool for obtaining simpler secondary assignments as well as simpler output circuits.

One of the most important and complicated problems in the synthesis of a sequential machine described by a state diagram or table is the assignment of the states of the secondary variables to the states of the machine. The secondary assignment for a given machine varies in accordance with the requirements of the design. It has already been shown that the partition with the substitution property and the partition pairs are of great significance in the secondary assignment. However, only few machines possess these properties, and hence, a more general method is needed. This paper presents a method of obtaining for any given machine M an equivalent machine M' which has a partition with the substitution property or partition pairs and therefore can be decomposed into two or more submachines connected in cascade or possibly in parallel. It is also shown that for machine M' we can find an assignment with self-dependent subsets. The method is shown to be general for any completely or incompletely specified sequential machine.