We consider the problem of fault detection in iterative logic arrays (ILA's). This problem has been studied by numerous researchers for many years. The results can be succinctly summarized by stating that one dimensional arrays can be effectively analyzed and significant results obtained while the problems associated with arrays of dimension two or greater appear to be intractable (i.e., NP-complete) for general arbitrary ILA's. However as is the case for many other switching theory problems, general case problems that are intractable, can be readily handled for the special cases defined by functions commonly encountered in practice. We show that arrays of dimension two or greater can be effectively tested for the case when the functions defined by the arrays have inverses. Many specific arithmetic functions satisfy this property. We also show that even for functions which do not satisfy this property, the functional approach simplifies testing problems considerably.>

This paper deals with the use and development of high-level (functional) primitive logic elements for use in a system which automatically generates tests for complex sequential circuits. The concept of solution sequences to test problems for primitive elements is introduced and a functional language used to describe solution sequences is presented. Functional test generation models for two basic elements, a shift register and a counter, are derived, including procedures for implication, D-drive and line justification. Primitive algorithms which generate single as well as multivector (sequences) solutions to D-drive and line justification problems are presented.

The advent of microprocessors as low-cost general- purpose computing elements has made feasible the implementation of multiprocessor systems containing a large number of cooperating modules. When the number of modules in the system is large it is unlikely that all of them are busy with computation at all times. Therefore, it may be possible to utilize this "slack" by having the nonbusy modules perform diagnostics. In this way computation and diagnosis are performed concurrently in real time. In this correspondence we consider the problem of designing systems in which concurrent computation/diagnosis is possible and we evaluate the potential of such approach.

A new measure of system diagnosis, t/s diagnosability, originally proposed by Friedman, is used to study the diagnosability of digital systems. This new measure incorporates the concept of possible replacement of fault-free units in system repair, whereas the previous measures have only considered the replacement of faulty units. Two categories of the new measure, one-step t/s diagnosability and sequential t/s diagnosability, are investigated. Two canonical classes of systems, single loop systems and DδAsystems (⌊t/2⌋ < A ≤ t), are examined based on these two categories of diagnosability. For each system class, the necessary and sufficient condition for one-step ts diagnosability is obtained and related to some previous results on t-fault diagnosability; also, an efficient one-step t/s repair procedure is presented. For both these system classes, optimal one-step t/s diagnosable system designs, which minimize the number of units and test links, are considered. Several sequential diagnosis strategies are presented for each system class. For all these diagnosis strategies optimal system designs are also considered. Finally, all the diagnosis strategies are compared and the tradeoff between the number of units replaced and the number of test iterations performed is discussed.

In multi-module and multi-processor systems, system performance can be greatly enhanced by the use of reconfiguration. In this paper we attempt to categorize and present standard definitions for the many different types of reconfigurable systems. Illustrations from the literature for each category are presented.

In this paper, we consider the problem of determining if a given set of simple combinational functions, called logic primitives, can be used to realize any arbitrarily complex combinational function. The complex combinational function is realized by suitably interconnecting the primitives, and in most cases several copies of the primitives. Such a set of primitives is said to be complete in some sense. Two important types of logical completeness that have been previously studied are: 1) strong completeness where the circuit inputs are the uncomplemented variables x1,x2,···,xn, and 2) weak completeness where the circuit inputs are 0,1,x1,x2,···,xn. In this paper, we discuss two new types of logical completeness: strong c-completeness with inputs x1, x̄1, x2, x̄2,···,xn, x̄n and weak c-completeness with inputs 1, 0, x1, x̄1, x2, x̄2,···, xn, x̄n, and we derive necessary and sufficient conditions for a set of primitives to be strong c-complete or weak c-complete. We also discuss the relations between the above four types of completeness. Finally, we consider two more types, complement completeness and dual completeness, which may have applications to some recent technologies.

The use of self-checking checkers in the design of highly reliable systems has many significant advantages. It allows errors to be detected upon occurrence without testing, whether the error is caused by a permanent or intermittent fault. However, there are relatively few codes for which efficient self-checking checkers have been designed. In this paper we present procedures for designing efficient self-checking checkers for m-out-of-n codes (i.e., codes where each valid code word consists of m bits with value 1 and n – m bits with value 0). Codes for arbitrary values of m and n are considered. Realizations which require significantly less logic than previously known realizations are presented for all cases except n = 2m and m = 1. These checkers are totally self-checking for all single and unidirectional multiple stuck-type faults. They are also very easy to test compared with previously presented realizations. Saving in logic complexity and testing complexity of 70 to 97 percent is demonstrated.

Most work on diagnosis of digital circuits has concentrated on the model of stuck-type faults. Although these faults are probably the most important class of faults, other types of faults do occur in practice and the occurrence of these other faults may affect the diagnosis of stuck-type faults. In this correspondence we consider the problems associated with detection of two other fault models, shorted diode and input Bridge faults, both corresponding to shorts. We present procedures for generating tests for stuck-type faults which also detect these other faults if they are detectable. Unlike stuck-type faults, the presence of undetectable short-circuit faults does not imply that the circuit can be simplified by removing inputs or gates. Undetectability of short-type faults corresponds to the ability to move fan-out points from an input to an output of a gate without changing the function realized by the circuit. Elimination of this type of redundancy does not necessarily lead to a simplified circuit.

The problem of selecting test points to reduce the number of tests for fault detection in combinational logic networks is examined. A method is presented for labeling the lines of a network. Procedures are described for obtaining a minimal labeling, i.e., one corresponding to a minimal set of tests, for fanout-free circuits and for a restricted class of circuits with fanout. Using these procedures, a branch-and-bound algorithm is developed for selecting an optimal (or near-optimal) set of q test points in fanout-free networks. Some difficulties associated with test point placement in general networks are pointed out. It is shown that the labeling approach is also applicable to the problem of selecting and placing control logic.

It has been shown that the number of tests required to detect all faults in a one-dimensional unilateral combinational iterative array consisting of p cells will, in general, be proportional to p. In this paper we consider properties of such systems that enable them to be tested with a fixed constant number of tests independent of p, the number of cells in the system. Such systems are referred to as C-testable. Necessary and sufficient conditions on the basic cell state table are derived for an iterative system to be C-testable. It is shown that an arbitrary N-state cell table can be augmented by the addition of, at most, one row and less than [log2 N]2 columns (for N ≥ 2) so as to be C-testable.

This paper shows that the imposition of some restrictions on the realization of a sequential machine facilitates the derivation of efficient checking sequences for some machines. Specifically, it is assumed that the state logic or the output logic may be faulty, but both of them cannot be faulty at the same time. This condition is satisfied if there is no shared logic between the state and output logic and at most a single fault in the circuit. It is also assumed that the normal machine has a synchronizing sequence. With these restrictions on the realization, the machine identification approach may be used to derive checking sequences that are often shorter than those without the restrictions and detect a larger set of faults than with the circuit testing approach.

This correspondence shows that, contrary to a statement in the cited paper, fault location is sometimes possible in one-dimensional arrays in which only the outputs of the rightmost cell are observable.

This note considers the operation of systems composed of interconnected asynchronously operating modules and shows that some such systems may enter "blocking conditions" in which no module can change state. The model considered applies specifically to asynchronous systems in which each module is controlled only by its neighbors, but may also be relevant to other systems such as parallel computational schemes. We also demonstrate a procedure that may speed up computation and we show that the function computed by a given network may depend upon the initial state.

Kautz has studied the problem of testing one-and two-dimensional arrays of combinational cells under the assumptions that all cell inputs must be applied to a cell to test it completely and that a fault in a cell may cause any arbitrary change in its outputs. In this paper we study the same problem under a more restricted set of assumptions: 1) all faults in a cell can be detected by a known set of inputs (usually smaller than the set of all inputs); and 2) each fault will affect the cell outputs in a known manner. Necessary and sufficient conditions for detection of faults in one-dimensional arrays are obtained. A procedure for deriving efficient tests for one-dimensional arrays is presented. Sufficient conditions for the testability of two-dimensional arrays and procedures for constructing tests for some arrays are obtained.

In the design of synchronous sequential machines, various canonical realizations which make use of feedback shift registers have been developed oped [1], [2]. This paper attempts to extend some of these results to realize asynchronous machines in a similar manner.

This paper considers the general problem of the synthesis of asynchronous combinational and sequential circuits based on the assumption that gate delays may be unbounded and that line delays are suitably constrained. Certain problems inherent to circuit realizations with unbounded gate delays are discussed and methods of solving them are proposed. Specific synthesis techniques are presented for both combinational and sequential circuits. The use of completion detection necessitated by the assumption of unbounded gate delays also causes the circuits to stop operating for approximately half of all possible single faults, thus achieving a degree of self-checking.

In this paper we consider the problem of deriving upper bounds on the number of state variables required for an n-state universal asynchronous state assignment (i.e., a state assignment which is valid for any n-state asynchronous sequential function). We will consider a special class of state assignments called SST assignments which were first derived by Liu [1] and later extended by Tracey [2]. In these assignments all variables which must change in a given transition are allowed to change simultaneously without critical races. The best universal bound known so far has been developed by Liu and requires 2so-1 state variables, where S0 = [log2n], n being the number of states, and [x] being the least integer > x. We shall show how this bound can be substantially improved. We further show that, by generalizing the state assignment to allow multiple codings for states, the bounds can be still further improved.

In this paper, we extend the partition theory developed by Hartmanis and Stearns for synchronous sequential circuits to asynchronous sequential circuits. A method which utilizes the concept of partition pairs to obtain single transition time asynchronous state assignments with reduced dependence is presented. Parallel and serial decompositions of asynchronous sequential circuits are also considered. Single transition time and multiple transition time serial decompositions are discussed and procedures for obtaining such decompositions are presented.

Abstract—In an earlier paper, Unger showed that any normal mode flow table can be realized by an asynchronous sequential circuit without inserted delays in the feedback paths if and only if the flow table contains no essential hazards. No restrictions were placed on the relative magnitudes of line and gate delays. In this paper, we show that if the line delays are less than the minimum gate delay in the circuit, any normal mode sequential function can be realized without inserted delays. It is also shown that a weaker line delay assumption is sufficient. Two procedures for realizing asynchronous sequential circuits without inserted delays are presented.

Abstract—A frequently imposed restriction in theoretical treatments of asynchronous sequential circuits is that only one input variable be allowed to change during a transition. In this paper, we present three methods for realizing asynchronous sequential circuits allowing multiple-input changes, but requiring that all input changes associated with an input transition be completed within a specified time after the first change. We also show that a single delay element is sufficient in the realization of normal mode flow tables, under these conditions.

It is shown that a set of diagnostic tests designed for a redundant circuit under the single-fault assumption is not necessarily a valid test set if a fault occurrence is preceded by the occurrence of some (undetectable) redundant faults. This is an additional reason (besides economy) for trying to eliminate certain kinds of redundancy from the circuit. However, single-fault analysis may remain valid for some types of redundancy which serve a useful purpose, such as the elimination of logic hazards in two-level circuits.

In this paper we consider minimum feedback loop realizations of synchronous sequential switching circuits. It is shown that any finite state sequential function can be realized as a synchronous sequential circuit with a single feedback loop, or equivalently, as a one-dimensional iterative circuit with one amplifier between stages. Techniques are described which enable us to find such a realization for a given flow table. A simple test procedure is described to determine if a sequential function can be realized as a sequential circuit using its output function as feedback, whether the output is completely or incompletely specified.

In this paper we attempt to realize any flow table of a desired sequential circuit so as to minimize the feedback index (number of feedback loops) of the resulting asynchronous sequential switching circuit. It is shown that any flow table M, which describes the circuit action of a normal fundamental mode asynchronous sequential circuit, can be realized as a fundamental mode circuit with feedback index [log2S], where S is the maximum number of stable states in any input column of M. The realization requires no inverters (assuming double rail inputs) and thus can be shown to be a minimum transistor, as well as a minimal feedback index, realization for any transistor-diode circuit realization of M. Nonfundamental mode realizations of normal mode flow tables are also considered, and it is shown that such a realization can be found with only one feedback loop, assuming ideal inertial delays, for any given flow table. However, no ideal inertial delay realization has been discovered which does not contain internal feedback. Finally, minimum feedback realizations of non-normal and nonfundamental mode flow tables are briefly considered.