RUS  ENG
Full version
VIDEO LIBRARY

International workshop "Syntax and semantics of logical systems"
August 11–16, 2019, Ņamp site on the shore of Lake Hovsgol


About the reliability of circuits in the basis containing a special function

M. A. Alekhina, Yu. S. Gusynina, T. A. Shornikova

Penza State Technological University

Abstract: We consider the realization of Boolean functions by the circuits from unreliable gates in a complete final basis B, containing a special function. We assume that all gates of a circuit are exposed to the faults type 0 at the outputs with probability $\varepsilon \in (0,1/2)$ independently of each other. We show that almost any Boolean function can be implemented by an asymptotically optimal in reliability circuit functioning with the unreliability which is asymptotically equal to $\varepsilon$ with $\varepsilon \to 0$.


© Steklov Math. Inst. of RAS, 2024