Geodesic
On the reliability of schemes in the basis $\{x\vee y\vee z,x\mathbin{\}y\mathbin{\}z,\bar{x}\}$ with single-type constant faults at the inputs of the element
Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 116-125
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider realisation of Boolean functions over the basis $\{x \vee y \vee z, x\mathbin{\}y \mathbin{\}z, \bar{x}\}$ by circuits of unreliable functional elements which are subject to single-type constant faults at inputs of the elements. Let $\gamma$ be the probability of a fault at an input of an element. By the unreliability of a circuit is meant the greatest probability of error at its output. In this paper, we find the asymptotically best realisation of an arbitrary Boolean function $f(x_1,\dots,x_n)$ such that the functions $x_i$, $i=1,2,\dots,n$, are realised absolutely reliably, the constants 0 and 1 are realised as reliably as we wish, and the remaining functions are realised with unreliability asymptotically equal to $\gamma^3$ as $\gamma\to 0$. This research was supported by the Scientific Program ‘Universities of Russia,’ grant 04.01.032. 
@article{DM_2006_18_1_a8,
     author = {M. A. Alekhina},
     title = {On the reliability of schemes in the basis $\{x\vee y\vee z,x\mathbin{\&}y\mathbin{\&}z,\bar{x}\}$ with single-type constant faults at the inputs of the element},
     journal = {Diskretnaya Matematika},
     pages = {116--125},
     year = {2006},
     volume = {18},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2006_18_1_a8/}
}
TY  - JOUR
AU  - M. A. Alekhina
TI  - On the reliability of schemes in the basis $\{x\vee y\vee z,x\mathbin{\&}y\mathbin{\&}z,\bar{x}\}$ with single-type constant faults at the inputs of the element
JO  - Diskretnaya Matematika
PY  - 2006
SP  - 116
EP  - 125
VL  - 18
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_2006_18_1_a8/
LA  - ru
ID  - DM_2006_18_1_a8
ER  - 
%0 Journal Article
%A M. A. Alekhina
%T On the reliability of schemes in the basis $\{x\vee y\vee z,x\mathbin{\&}y\mathbin{\&}z,\bar{x}\}$ with single-type constant faults at the inputs of the element
%J Diskretnaya Matematika
%D 2006
%P 116-125
%V 18
%N 1
%U http://geodesic.mathdoc.fr/item/DM_2006_18_1_a8/
%G ru
%F DM_2006_18_1_a8
M. A. Alekhina. On the reliability of schemes in the basis $\{x\vee y\vee z,x\mathbin{\&}y\mathbin{\&}z,\bar{x}\}$ with single-type constant faults at the inputs of the element. Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 116-125. http://geodesic.mathdoc.fr/item/DM_2006_18_1_a8/

[1] Redkin N. P., Nadezhnost i diagnostika skhem, Izd-vo MGU, Moskva, 1992

[2] Tarasov V. V., “K sintezu nadezhnykh skhem iz nenadezhnykh elementov”, Matematicheskie zametki, 20:3 (1976), 391–400 | MR | Zbl

[3] Neiman Dzh., “Veroyatnostnaya logika i sintez nadezhnykh organizmov iz nenadezhnykh komponent”, Avtomaty, IL, Moskva, 1956, 68–139

[4] Ortyukov S. I., “Ob izbytochnosti realizatsii bulevykh funktsii skhemami iz nenadezhnykh elementov”, Trudy seminara po diskretnoi matematike i ee prilozheniyam, Izd-vo MGU, Moskva, 1989, 166–168

[5] Uhlig D., “Reliable networks from unreliable gates with almost minimal complexity”, Lecture Notes Comput. Sci., 278, 1987, 462–469

[6] Alekhina M. A., “O nadezhnosti skhem v bazise $\{\mathbin{\},\vee,\bar{}\,\}$ pri odnotipnykh konstantnykh neispravnostyakh na vkhodakh elementov”, Diskretnaya matematika, 13:3 (2001), 75–80 | MR

[7] Alekhina M. A., “Nizhnie otsenki nenadezhnosti skhem v nekotorykh bazisakh pri odnotipnykh konstantnykh neispravnostyakh na vkhodakh elementov”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 9:3 (2002), 3–28 | MR | Zbl

[8] Alekhina M. A., “O nadezhnosti dvoistvennykh skhem”, Materialy XI Mezhgosudarstvennoi shkoly-seminara «Sintez i slozhnost upravlyayuschikh sistem», Izd-vo Tsentra prikladnykh issled. pri mekhaniko-matem. f-te MGU, Moskva, 2001, 6–8 | MR