Geodesic
On Reliability of Combinatorial Circuits in Bases Containing Functions with at Most Three Variables
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 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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$.
Keywords: unreliable functional gates, optimal combinatorial circuits, inverse faults, realization of Boolean functions by combinatorial circuits with unreliable functional gates, synthesis of reliable circuits. 
@article{UZKU_2009_151_2_a3,
     author = {M. A. Alekhina and A. V. Vasin},
     title = {On {Reliability} of {Combinatorial} {Circuits} in {Bases} {Containing} {Functions} with at {Most} {Three} {Variables}},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {25--35},
     year = {2009},
     volume = {151},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a3/}
}
TY  - JOUR
AU  - M. A. Alekhina
AU  - A. V. Vasin
TI  - On Reliability of Combinatorial Circuits in Bases Containing Functions with at Most Three Variables
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2009
SP  - 25
EP  - 35
VL  - 151
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a3/
LA  - ru
ID  - UZKU_2009_151_2_a3
ER  - 
%0 Journal Article
%A M. A. Alekhina
%A A. V. Vasin
%T On Reliability of Combinatorial Circuits in Bases Containing Functions with at Most Three Variables
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2009
%P 25-35
%V 151
%N 2
%U http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a3/
%G ru
%F UZKU_2009_151_2_a3
M. A. Alekhina; A. V. Vasin. On Reliability of Combinatorial Circuits in Bases Containing Functions with at Most Three Variables. 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. http://geodesic.mathdoc.fr/item/UZKU_2009_151_2_a3/

[1] von Neuman J., “Probabilistic logics and the synthesis of reliable organisms from unreliable components”, Automata studies, eds. C. Shannon, J. Mc. Carthy, Princeton Univ. Press, Princeton, 1956, 43–98 | MR

[2] Alekhina M. A., Sintez asimptoticheski optimalnykh po nadezhnosti skhem iz nenadezhnykh elementov, Inf.-izd. tsentr PGU, Penza, 2006, 157 pp.

[3] Alekhina M. A., Shilov A. V., “Verkhnie otsenki nenadezhnosti skhem v nekotorykh bazisakh pri inversnykh neispravnostyakh na vykhodakh elementov”, Izv. vuzov. Povolzhskii region. Estestv. nauki, 2006, no. 5(26), 4–12

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

[5] Alekhina M. A., “O nadezhnosti skhem v bazisakh, soderzhaschikh medianu”, Diskretnye modeli v teorii upravlyayuschikh sistem, VIII Mezhdunar. konf. (Moskva, 6–9 apr. 2009 g.), eds. V. B. Alekseev, V. A. Zakharov, Izd. otdel f-ta VMiK Mosk. un-ta, MAKS Press, M., 2009, 13–17

[6] Vasin A. V., “O funktsiyakh spetsialnogo vida”, Diskretnye modeli v teorii upravlyayuschikh sistem, VIII Mezhdunar. konf. (Moskva, 6–9 apr. 2009 g.), eds. V. B. Alekseev, V. A. Zakharov, Izd. otdel f-ta VMiK Mosk. un-ta, MAKS Press, M., 2009, 43–46