Sufficient conditions for realizability of Boolean functions by asymptotically optimal circuits with the unreliability~$2\varepsilon$

M. A. Alekhina ; A. V. Vasin

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 5 (2010), pp. 79-82

Résumé

We consider realizations of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis $B$. We assume that all elements independently of each other with the probability $\varepsilon$ ($\varepsilon\in(0;1/2)$) are subjected to inverse failures at the output. We construct Boolean functions $\varphi(x_1,x_2,x_3)$ such that the presence of at least one of them in the considered basis $B$ guarantees the realizability of all three Boolean functions by circuits whose reliability does not exceed $2\varepsilon+144\varepsilon^2$ with $\varepsilon\le1/960$. In addition, if $B\subset B_3\setminus G$ ($B_3$ is the set of all Boolean functions of three variables $x_1$, $x_2$, and $x_3$, and $G$ is the set of Boolean functions such that each one of them is congruent either to $x_1^{\sigma_1}x_2^{\sigma_2}\vee x_1^{\sigma_1}x_3^{\sigma_3}\vee x_2^{\sigma_2}x_3^{\sigma_3}$, or to $x_1^{\sigma_1}x_2^{\sigma_2}\oplus x_3^{\sigma_3}$, or to $x_1^{\sigma_1}x_2^{\overline\sigma_2}\vee x_2^{\sigma_2}x_3^{\sigma_3}$ ($\sigma_1,\sigma_2,\sigma_3\in\{0,1\}$)), then the presence of at least one of functions $\varphi(x_1,x_2,x_3)$ guarantees the realizability of almost all Boolean functions by asymptotically optimal (with respect to the reliability) circuits, whose unreliability equals $2\varepsilon$ with $\varepsilon\to0$.

Détail

Keywords: unreliable functional elements, circuits asymptotically optimal with respect to reliability, inverse failures on outputs of elements, synthesis of circuits composed of unreliable elements.