A new approach is developed for finding multiple fault detection tests under quite arbitrary fault models. Computational results are reported and discussed.

A new approach is presented for the design of multiple fault detection tests in which the structure of a combinational circuit is used to reduce the number of input combinations required. The structure is defined by the interconnection of the basic elements, each of arbitrary complexity. The fault model assumes that the functions realized by the basic elements may undergo any deviation whatsoever, but that the circuit structure is fault free. Thus, arbitrary combinations of multiple faults within one or more basic elements are included in the model. Decomposition theory can be used to verify that a set of input combinations is a multiple fault detection test set under this model. A process called expansion will be introduced to simplify this task. A well-defined procedure is given for deriving a suitable test set which for some circuits is minimal or near minimal. It will yield a multiple fault detection test of length less than 2nfor any circuit with a nontrivial nondisjoint decomposition, defined by a basic-element partition. Higher order basic-element partitions are introduced as a generalization. An upper bound is given on the length of a multiple fault detection test for any circuit with a given structure, independent of the function realized on the structure. The bound is tighter when function information is also used.

Dynamically self-checked or fault-tolerant realizations of switching functions and sequential machines are proposed under a fault model that permits arbitrary logic faults in a single-logic module, where the modules are explicitly defined. These realizations permit considerable logic sharing, organized around an (n, m, r)-basis for decomposing switching functions. The logic sharing permits more economical realizations than can be obtained using classical parity and triple-modular redundancy schemes for obtaining logic circuits with the corresponding property.

Universal base functions (UBF's) which are generalizations of universal logic functions are defined. An (n, m, r)-UBF can be implemented as a single module (UBM) with n+m inputs and 1 output. An arbitrary n-variable switching function fn(X) is then realized on the fixed UBM by realizing a suitable set of m r-variable functions with which to drive m inputs of the UBM, the remaining n inputs being driven by X. The fan-in of a UBM for r ≥2 is shown to be considerably less than that of a universal logic module (a special case corresponding to r = 1). Specific UBF's are proposed for r = 2 in which m is on the order of 60 percent of the value obtained by using the UBF defined by the familiar Shannon decomposition formula. This is close to the theoretical lower bound on m. The use of UBM's provides a new way to realize an arbitrary function or set of functions, completely specified or otherwise, by assembling a small number of circuits selected from a small set of standard logic modules of limited fan-in. For the case r = 2, the number of two-input devices required to drive the m inputs of the UBM is often considerably less than m. DON'T CARES can be used to advantage to reduce this number still further.

A terminal stuck fault in a logic network is represented by one or more stuck-at-1 or stuck-at-0 faults on the n input lines or single output. It is shown that for n ≤ 5, a least upper bound on the test length is n + 1, and for n > 5, an upper bound is 2n - 4. A greatest lower bound is 3, for all n > 1. The upper bounds are based on a maximum size alternating 1-tree in the n-cube representation of the function. Of the more than 600 000 equivalence classes of functions of n variables, n ≤ 5, only one does not have an n-edge alternating 1-tree. An algorithm is proposed for constructing tests based on alternating 1-trees.

This paper is a study of switching functions realizable by a single cascaded switching network composed of two-input, one-output elements where a distinct variable is applied to one input and the other receives the output of the previous element. A special type of Boolean formula called a standard cascade form is introduced with the property that all cascade realizable functions, and only these, can be written in this form. This characterization leads to a strong necessary condition on such functions: there is no consensus for any pair of its prime implicants which are, therefore, all core. It also leads to a new, efficient procedure for testing an arbitrary function f for cascade realizability. The test operates on the prime implicants of f, and yields a realization employing a particular complete set of cell types from which it is especially easy to derive any other realization using any other complete set.

Most switching functions are not realizable by a single cascade of 2-input 1-output switching elements, even if repeated inputs are allowed. However, arrays of such cascades feeding a single collector cascade of AND or OR cells can be used to synthesize any function. This paper is concerned with optimal array realizations of this form.