On Reliability of Combinatorial Circuits in Bases Containing Functions with at Most Three Variables

M. A. Alekhina ; A. V. Vasin

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Kazanskii Gosudarstvennyi Universitet. Uchenye Zapiski. Seriya Fiziko-Matematichaskie Nauki, Tome 151 (2009) no. 2, pp. 25-35

Résumé

We consider the realization of Boolean functions by combinatorial circuits with gates realizing functions from a complete basis $B$, containing functions with at most three variables. We assume that gates can have inverse faults on the outputs independently with the probability $\varepsilon$ ($\varepsilon\in(0;1/2)$). We describe a set $G$ of Boolean functions depending essentially on three variables, and prove that for almost all Boolean functions the unreliability of asymptotically optimal circuits is asymptotically equal to $\varepsilon$ (when $\varepsilon$ tends to 0) if and only if $G\cap B\ne\emptyset$.

Détail

Keywords: unreliable functional gates, optimal combinatorial circuits, inverse faults, realization of Boolean functions by combinatorial circuits with unreliable functional gates, synthesis of reliable circuits.