There has been considerable study of the tradeoff between improved reliability and additional hardware. An alternative is to trade speed for improved reliability, as in alternating logic, which is based on the successive execution of a function and its dual. In addition to doubling time, this approach involves an increase in hardware which, however, is generally modest compared to the usual hardware redundancy approaches. This paper will explore recent advances in the design of sequential circuits using self-checking alternating logic.

This paper details the fault detection capability of a design technique named "alternating logic design." The technique achieves its fault detection capability by utilizing a redundancy in time instead of the conventional redundancy in space and is based on the successive execution of a required function and its dual. In combinational networks the method involves the utilization of a self-dual fumction to represent the required function and the realization of the self dual function in a network with structral properties which are sufficient to guarantee the detection of all single faults. One network structure with sufficient structral properties to detect all single stuck-line faults is the standard AND/OR or OR/AND two-level network [1]. However, other more general combinational logic structures also possess sufficient structural properties. Necessary and sufficient structural properties for any alternating network to be capable of detecting all single faults are derived.

Strongly fault secure logic networks are defined and are shown to include totally self-checking networks as a special case. Strongly fault secure networks provide the same protection against assumed faults as totally self-checking networks, and it is shown that when stuck-at faults are assumed a strongly fault secure network can be easily modified to form a totally self-checking network. A class of strongly fault secure networks is defined in terms of network structure. This structural definition of these "path fault secure" networks facilitates their design and implies other interesting properties. Finally, networks that are strongly fault secure with respect to single stuck-at faults are discussed. A large class of these networks is shown to be easily characterized, and network behavior under nonmodeled faults is considered.

These comments point out first that the difficulties encountered in a recent paper1in applying the theorems of Boolean algebra to a multivalued system using max and min functions are not due to the type of complement that is chosen, but due to the attempt to deqne a multivalued Boolean algebra using the max and min functions which are not Boolean functions except in the 2-valued case; and second, that the three types of complement defined are well known in the context of multivalued non-Boolean algebras.

In the above paper1, the partial Boolean difference is defined and an algorithm for deriving complete minimal test input sequences for single-fault detection is given. In this correspondence, it is shown that the presentation of the algorithm is inadequate with respect to the need for multiple path sensitization. It is further shown that the computational procedure used in footnote 1 does not guarantee minimality of the test set and does not permit the extension to fault location as claimed in the paper.

This paper discusses a technique whereby a logic design which is unconstrained may be replaced quasi-optimally with modules from a constrained library. Necessary and sufficient conditions for the replacement of modules within a network are developed and then reformulated as integer linear programs. These integer linear programs are solved during individual steps of a dynamic programming formulation of the network replacement problem. Execution time of the algorithm increases linearly with the network size and the algorithm produces optimal replacements of fan-out-free networks.

The fundamentals of Post algebras are presented and Post and Boolean functions are examined. A functional representation is developed that facilitates the comparison of Post and Boolean algebras. Based on this representation, relationships between finite, higher-order (that is, more than 2-valued) Boolean algebras and functions in these algebras and finite, higher-order Post algebras and their corresponding functions are develop.

This paper examines the dynamic fault behavior of asynchronous sequential machines, specifically identifying the faults which cause critical races and hazards, and presents a state assignment technique leading to a machine that enters one of a small set of error states whenever a fault occurs. Entry into an error state can be checked by very simple check circuits; a self-testing check circuit and one requiring only two tests for fault detection are discussed. An extension of the state assignment technique to produce a machine that is fail-safe is also presented. The fail-safe design has the property that once a fault has caused the machine to malfunction and enter an error state, the machine never leaves the error state and therefore does not produce erroneous outputs. This machine detects all but a small class of multiple faults.

The design of totally self-checking check circuits for m-out-of-n codes is described. Totally self-checking m-out-of-n checkers provide an error indication whenever the input is not an m-out-of-n code or whenever a fault occurs within the checker itself. Since the checker checks itself, there is no need for additional maintenance access or periodic exercise of the checker to verify its ability to detect errors. The basic structure of the checker relies on the use of majority detection circuits. Various gate level implementations for the majority detection circuits are also presented, although the self-checking capability of the checker does not depend on their particular implementation since they are exhaustively tested by code inputs. The self-testing checkers for k-out-of-2k codes are discussed in the most detail since the totally self-checking checkers for 1-out-of-n and arbitrary m-out-of-n codes are constructed by first translating the code to a k-out-of-2k code via a totally self-checking translator.

A new redundancy technique termed dotted logic is presented. Critical input errors are eliminated by joining together the output of NAND gates and NOR gates. The remaining subcritical errors are corrected by introducing redundant inputs to each logic element. Two different schemes, dotted alternating and dotted identical, are described and compared with existing error-correcting techniques. It is shown that these new methods have several advantages over quadded or triple modular redundancy (TMR) networks. In addition to correcting single faults, dotted schemes are easily extended to cover multiple faults. Methods for initial failure determinations for dotted schemes are proposed. Finally, it is shown that a network consisting of complex function elements can be made more reliable by dotting.

A new representation for faults in combinational digital circuits is presented. Faults that are inherently indistinguishable are identified and combined into classes that form a geometric structure that effectively subdivides the original circuit into fan-out-free segments. This fan-out-free characteristic allows a simplified analysis of multiple fault conditions. For certain circuits, including all two-level single-output circuits, it is shown that the detection of all single faults implies the detection of all multiple faults. The behavior of any circuit under fault conditions is represented in terms of the classes of indistinguishable faults. This results in a description of the faulty circuit by means of Boolean equations that are readily manipulated for the purpose of fault simulation or test generation. A connection graph interpretation of this fault representation is discussed. Heuristic methods for the selection of efficient tests without extensive computation are derived from these connection graphs.

This paper considers the design of diagnosable combinational networks. The diagnosability criterion used here requires that the single fault detection test set for the network also detects all multiple faults. Several recent studies in the area of multiple fault diagnosis are reviewed and the results which are pertinent to this investigation are summarized. It is shown that, under certain conditions, internal fan-out may be present without adversely affecting the detection of multiple faults. These results suggest design techniques which lead to readily diagnosable networks.

The use of N-valued logics in the design of base N adder circuits is considered. Two types of N-valued logics are examined, Post N-valued logics and binary-coded N-valued logics. Specific implementations of these nonbinary logics are discussed. General formulas for the sum and carry functions of an adder are established in order to calculate the cost of base N adder stages using the Post logics. Relative costs of the base N adders using both types of N-valued logics are discussed in terms of a cost function. It is shown that for the model used, the binary-coded logics yield adders that have, in general, lower relative cost than comparabloe adders based on the Post logics, and that base 2 adders have a lower relative cost than the base N adders.

We thank C. H. Haspel for pointing out our error with respect to his packaging procedure. We further basically agree with him as to the trend of logic design toward more logically complex modules. However, we do not share his optimism with regard to the capability of functional decomposition techniques in treating modules of the expected complexity. Rather we envision the evolution of functionally, instead of logically, oriented system design techniques which would perform intermodular design. Intramodular design would then be performed by some such technique as NAND decomposition.

Abstract—The principal synthesis example of Schneider and Dietmeyer's paper [1] is examined by applying a new synthesis algorithm. The minimum NOR gate realization thus obtained is used to illustrate the nonoptimality of their approach and to question their definition of delay. Arguments are advanced for synthesis with simple modules.

This paper treats the problem of automatic fault diagnosis for systems with multiple faults. The system is decomposed into n units u1, u2, . . . , un, where a unit is a well-identifiable portion of the system which cannot be further decomposed for the purpose of diagnosis. By means of a given arrangement of testing links (connection assignment) each unit of the system tests a subset of units, and a proper diagnosis can be arrived at for any diagnosable fault pattern. Methods for optimal assignments are given for instantaneous and sequential diagnosis procedures.

Binary square rooting algorithms which yield a root in a redundant representation using digits 1, -1, and 0 are analyzed, particularly those yielding a root in a representation in which the number of nonzero digits is minimal. An algorithm which may lead to any possible minimal representation of the square root is developed.

Binary division methods employing a redundant quotient representation in which quotient digits assume the values 0, 1, or -1 have been analyzed previously. The method in which partial remainders are always normalized is of particular interest; it yields quotients represented with a minimal number of nonzero digits for all divisors D in the range ⅗≤|D|≤¾. This method is extended to yield minimally represented quotients for all normalized divisors.