Volume 20, No 6, 2013, P. 3-15
Vasin A. V.
Asymptotically reliability optimal schemes in special bases
We consider realization of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis $B\subset B_3$ ($B_3$ is the set of all Boolean functions of three variables $x_1,x_2$ and $x_3$). We assume that all elements are independently of each other subjected to inverse failures at the output with the probability $\varepsilon\in(0;1/2)$. We find bases in which it is possible to realize almost all Boolean functions by asymptotically reliability optimal circuits with unreliability $3\varepsilon$ with $\varepsilon\to0$. We proved that there are no other bases where it's possible to realize almost all Boolean functions by asymptotically reliability optimal circuits with unreliability $3\varepsilon$.
Keywords: unreliable functional element, asymptotically reliability optimal circuit, inverse failure on outputs of elements, synthesis of a circuit composed of unreliable elements.
Vasin Alexey Valerevich 1
1. Penza State University,
20 Krasnaya St., 220030 Penza, Russia