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.

Bibliographie

[1] Vasin A. V., “O funktsiyakh spetsialnogo vida”, Tr. VIII mezhdunarodn. konf. “Diskretnye modeli v teorii upravlyayuschikh sistem”, MAKS Press, M., 2009, 43–46

[2] Alekhina M. A., Vasin A. V., “O nadezhnosti skhem v bazisakh, soderzhaschikh funktsii ne bolee chem trekh peremennykh”, Uchen. zap. Kazansk. un-ta. Ser. fiz.-matem. nauki, 151, no. 2, 2009, 25–35

[3] Aksenov S. I., “O nadezhnosti skhem nad proizvolnoi polnoi sistemoi funktsii pri inversnykh neispravnostyakh na vykhodakh elementov”, Izv. vuzov. Povolzhskii region. Estestven. nauki, 2005, no. 6, 42–55

[4] Alekhina M. A., Sintez asimptoticheski optimalnykh po nadezhnosti skhem iz nenadezhnykh elementov, IITs PGU, Penza, 2006, 157 pp.

[5] Alekhina M. A., Pichugina P. G., “O nadezhnosti dvoistvennykh skhem v polnom konechnom bazise”, Materialy XIII Mezhdunarodn. shkoly-seminara “Sintez i slozhnost upravlyayuschikh sistem”, Izd-vo mekh.-mat. f-ta MGU, M., 2009, 10–13