The optimization problem of a general approach for designing fault-tolerant circuits is investigated. The gate minimization problem is solved so that optimal design with respect to the numbers of gates and levels is obtained. The concept and properties of block design are used to formulate, solve for, and construct the optimal form. The gate minimization problem for a fault-tolerant circuit is formulated and a lower bound to the number of minimum gates for any design is established. For certain design parameters, explicit minimum solutions are given. When no minimum solution is found, sets of explicit block designs which produce near-minimum designs are characterized. In both cases, minimum and near-minimum algorithms which generate the blocks required to construct the logic for fault-tolerant circuits in linear times are devised. If a block design does not have any connection with the minimum or near-minimum classes, an approximation algorithm which generates near-minimum blocks in a polynomial time is suggested.>

The necessary conditions for designing testable static redundancy system-level fault-tolerant circuits are derived. In addition, algorithms are proposed for the efficient generation of test patterns for fault-tolerant circuits designed to satisfy these testability conditions. The test generation algorithm has been incorporated with an algorithm for the construction of majority voting devices and automated to produce a software package that generates testable fault-tolerant circuits along with test patterns to test the resultant circuit completely. As input, the algorithm requires a testable original circuit, along with an associated set of test patterns and the desired design parameters E, R, and K.>

The use of redundancy to attain a fault-tolerant system design is described. Specifically, a general theory of redundancy is proposed that allows the design of fault-tolerant structures at the system-level, gate-level, or both. The theory accounts for classic approaches to redundant design such as TMR, NMR, and quadded and interwoven logics. It is shown that, by using mathematical block theory, it is possible to describe complex interconnections of redundant elements in a simple, straightforward fashion. Comparisons are made with other approaches to redundant design.>