About the reliability of circuits under failures of type $0$ at the outputs of elements in a complete finite basis containing some pairs of functions

M. A. Alekhina ; T. A. Shornikova

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 7 (2020), pp. 10-17.

Résumé

We consider the realization of Boolean functions by the circuits from unreliable elements in a complete finite basis containing some pairs of functions. We assume that all elements of a circuit are exposed to the faults type $0$ at the outputs with probability $\varepsilon \in (0,1/2)$ independently of each other. We prove that almost any Boolean function can be implemented by an asymptotically optimal in reliability circuit functioning with the unreliability which is asymptotically equal to $\varepsilon$ with $\varepsilon \to 0$.

Détail

Keywords: unreliable functional gates, reliability and unreliability of circuit, synthesis of circuits composed of unreliable gates.

Bibliographie

[1] Von Neumann J., “Probabilistic logics and the synthesis of reliable organisms from unreliable components”, Automata studies, Princeton Univ. Press, Princeton, 1956, 43–98 | MR

[2] Dobrushin R. L., Ortyukov S. I., “Upper bound on the redundancy of self-correcting arrangements of unreliable functional elements”, Problems Inform. Transmission, 13:3 (1977), 203–218 | MR | Zbl

[3] Ortyukov S. I., “On the redundancy of the Boolean functions implementation by circuits from unreliable elements”, Seminar on Discr. Math. and its Appl. (Moscow, 27–29 Jan. 1987), MSU Publ., M., 1989, 166–168 (in Russian)

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

[5] Pippenger N., “On networks of Noisy Gates”, Materials of 26th Ann. Symp. Foundations of Computer Science (Portland, 21–23 Oct. 1985), 30–38

[6] Yablonskiy C. V., “Asymptotically best method for synthesizing reliable circuits from unreliable elements”, Banach Center Publ., 1982, no. 7, 11–19 (in Russian)

[7] Tarasov V. V., “The synthesis of reliable circuits from unreliable elements”, Math. Notes, 20:3 (1976), 775–780 | MR | Zbl

[8] Alekhina M. A., “On synthesis of reliable schemes consisting of functional elements x/y wiht similar incorrectedness of elements outputs”, Vestnic Moskovskogo Univsiteta, Seriya 1, Matematika Mekhanika, 1991, no. 5, 80–83 (in Russian)

[9] Alekhina M. A., Synthesis, reliability and complexity of circuits from unreliable functional elements, Дисс. ... докт. физ.-матем. наук, Moscow State University, M., 2004

[10] Vasin A. V., Asymptotically optimal on reliability circuits in complete bases of three-input elements, PhD Thesis, Penz. State Univ., Penza, 2010, 100 pp. (in Russian)

[11] Alekhina M. A., Vasin A. V., “On bases with unreliability coefficient 2”, Math. Notes, 93:2 (2014), 147–173 (in Russian) | Zbl

[12] Gavrilov G. P., Sapozhenko A. A., Tasks and exercises in discrete mathematics, 3rd ed., Fizmatlit, M., 2006 (in Russian)

[13] Alekhina M. A., Gusynina Yu. S., Shornikova T. A., “Upper Estimate of Unreliability of Schemes in Full Finite Basis (in $P_2$) for Arbitrary Faults of Gates”, Russian Mathematics, 61:12 (2017), 70–72 (in Russian) | Zbl

[14] Alekhina M. A., “On the reliability of circuits in a complete finite basis containing a linear function of two variables and a generalized disjunction”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2019, no. 1, 64–73 (in Russian)

[15] Alekhina M. A., Pichugina P. G., “On the reliability of dual circuts in the complete finite basis”, Materials of XVIII Int. School-seminar «Synthesis and complexity of control systems» (Penza, 28 Sept.–3 Oct. 2009), Faculty of Mechanics and Mathematics of Moscow State University, M., 2009, 10–13 (in Russian)