On Bases with Unreliability Coefficient~$2$

M. A. Alekhina ; A. V. Vasin

Matematičeskie zametki, Tome 95 (2014) no. 2, pp. 170-201.

Résumé

Consider the realization of Boolean functions by networks from unreliable functional components in a complete basis $B\subset B_3$ ($B_3$ is the set of all Boolean functions depending on the variables $x_1$, $x_2$, $x_3$). It is assumed that all the components of the network are subject to inverse faults at the outputs independently of each other with probability $\varepsilon\in(0,1/2)$. In $B_3$, we obtain all complete bases in which the following two conditions simultaneously hold: 1) any function can be realized by a network with unreliability asymptotically not greater than $2\varepsilon$ ($\varepsilon\to 0$); 2) there exist functions (denote their set by $K$) that cannot be realized by networks with unreliability asymptotically less than $2\varepsilon$, $\varepsilon\to 0$. Such bases will be called bases with unreliability coefficient $2$. It is also proved that the set $K$ contains almost all functions.

Détail

Keywords: synthesis of reliable networks from unreliable components, Boolean function, complete basis, unreliability coefficient, error probability of a network, reliability-based optimal network, inverse faults of components, von Neumann iterative method, upper (lower) bound for the unreliability of a network.

Bibliographie

[1] O. B. Lupanov, Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, M., 1984

[2] J. von Neumann, “Probabilistic logics and the synthesis of reliable organisms from unreliable components”, Automata Studies, Ann. of Math. Stud., 34, Princeton Univ. Press, Princeton, NJ, 1956, 43–98 | MR

[3] S. I. Ortyukov, “Ob izbytochnosti realizatsii bulevykh funktsii skhemami iz nenadezhnykh elementov”, Trudy seminara po diskretnoi matematike i ee prilozheniyam (Moskva, 27–29 yanvarya 1987 g.), Izd-vo Mosk. un-ta, M., 1989, 166–168

[4] D. Uhlig, “Reliable networks from unreliable gates with almost minimal comlexity”, Fundamentals of Computation Theory. Intern. conf. FCT'87 (Kazan, June 1987), Lecture Notes in Comput. Sci., 278, Springer-Verl., Proc. Berlin, 1987, 462–469

[5] S. V. Yablonskii, “Asimptoticheski nailuchshii metod sinteza nadezhnykh skhem iz nenadezhnykh elementov”, Discrete Mathematics, Banach Cent. Publ., 7, PWN, Warsaw, 1982, 11–19 | MR | Zbl

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

[7] V. V. Chugunova, Sintez asimptoticheski optimalnykh po nadezhnosti skhem pri inversnykh neispravnostyakh na vkhodakh elementov, Diss. $\dots$ kand. fiz.-matem. nauk, Penza, 2007

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

[9] M. A. Alekhina, A. V. Vasin, “O nadezhnosti skhem v bazisakh, soderzhaschikh funktsii ne bolee chem trekh peremennykh”, Fiziko-matematicheskie nauki, Uchën. zap. Kazan. gos. un-ta. Ser. Fiz.-matem. nauki, 151, no. 2, Izd-vo Kazanskogo un-ta, Kazan, 2009, 25–35

[10] A. V. Vasin, “Ob asimptoticheski optimalnykh skhemakh v bazise $\{\,\lnot\}$ pri inversnykh neispravnostyakh na vykhodakh elementov”, Diskretn. analiz i issled. oper., 16:6 (2009), 12–22 | MR | Zbl

[11] A. V. Vasin, “O funktsiyakh spetsialnogo vida”, Trudy VIII Mezhdunarodnoi konferentsii “Diskretnye modeli v teorii upravlyayuschikh sistem” (Lesnoi gorodok Mosk. obl., 6–9 aprelya 2009 g.), MAKS Press, M., 2009, 43–46

[12] M. A. Alekhina, S. I. Aksenov, A. V. Vasin, “O funktsiyakh i skhemakh, primenyaemykh dlya povysheniya nadezhnosti skhem”, Izv. vuzov. Povolzhskii region. Fiz.-matem. nauki, 2008, no. 3, 30–38

[13] N. P. Redkin, “O polnykh proveryayuschikh testakh”, Matematicheskie voprosy kibernetiki, 2, M., 1989, 198–222

[14] M. A. Alekhina, P. G. Pichugina, “O nadezhnosti dvoistvennykh skhem v polnom konechnom bazise”, Sintez i slozhnost upravlyayuschikh sistem, Materialy XVIII Mezhdunarodnoi shkoly-seminara im. O. B. Lupanova (g. Penza 28 sentyabrya–3 oktyabrya 2009 g.), Izd-vo mekh.-mat. f-ta MGU, M., 2009, 10–13

[15] A. V. Vasin, “O bazisakh, v kotorykh asimptoticheski optimalnye skhemy imeyut nenadezhnost $2\varepsilon$”, Materialy X Mezhdunarodnogo seminara “Diskretnaya matematika i ee prilozheniya” (g. Moskva, 1–6 fevralya 2010 g.), Izd-vo mekh.-mat. f-ta MGU, M., 2010, 94–97

[16] M. A. Alekhina, A. V. Vasin, “Dostatochnye usloviya realizatsii bulevykh funktsii asimptoticheski optimalnymi skhemami s nenadezhnostyu $2\varepsilon$”, Izv. vuzov. Matem., 2010, no. 5, 79–82 | MR

[17] A. V. Vasin, “O nadezhnosti skhem v polnykh konechnykh bazisakh, soderzhaschikh lineinuyu funktsiyu”, Trudy mezhdunarodnogo simpoziuma “Nadezhnost i kachestvo, 2010”, T. 1 (g. Penza, 24–31 maya 2010 g.), IITs PGU, Penza, 2010, 241–242

[18] A. V. Vasin, Asimptoticheski optimalnye po nadezhnosti skhemy v polnykh bazisakh iz trekhvkhodovykh elementov, Diss. $\dots$ kand. fiz.-matem. nauk, Penza, 2010