About the Reliability of Circuits in the Complete Finite Basis Containing an Essential Linear Function

Abstract

We consider the the implementation of Boolean functions by circuits from unreliable functional elements in a complete finite basis, which contains a linear function essentially dependent on at least two variables. We assume that all elements of a circuit are exposed to the faults of type 0 at the outputs with probability ε ∈ (0, 1/2) independently of each other. We prove that almost any Boolean function can be implemented by an asymptotically optimal in reliability circuit functioning with the unreliability which is asymptotically equal to ε with ε → 0.