Solutions to the minimization problem of fault-tolerant logic circuits

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