This article is cited in
10 papers
Brief communications
Sufficient conditions for realizability of Boolean functions by asymptotically optimal circuits with the unreliability $2\varepsilon$
M. A. Alekhina,
A. V. Vasin Chair of Discrete Mathematics, Penza State University, Penza, Russia
Abstract:
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$.
Keywords:
unreliable functional elements, circuits asymptotically optimal with respect to reliability, inverse failures on outputs of elements, synthesis of circuits composed of unreliable elements.
UDC:
519.718 Received: 10.11.2009