Article collection "Mathematical Problems of Cybernetics" №11, Moscow, 2002

Authors:Alekhina M.A.

Synthesis and complexity of reliable circuits from unreliable elements

Abstract:

We consider the implementation of Boolean functions by circuits from unreliable functional elements, which subject to one-type constant faults only at the outputs or only at the inputs. We offer a constructive method for constructing of the asymptotically best (asymptotically optimal) on reliability circuit, complexity of which differs from the complexity of asymptotically optimal on complexity circuits only by a multiplicative constant, which depends on the basis. We apply this method in a series of complete irreducible bases of two-input elements and obtain estimates of the unreliability and complexity of the constructed circuits.

Keywords:

unreliable functional elements, reliability of a circuit, unreliability of a circuit, constant faults of type 0 and 1 at inputs and outputs of elements