About the reliability of logic circuits in all complete bases with three-input elements and failures of zero type on their outputs

M. A. Alekhina

Prikladnaâ diskretnaâ matematika, no. 3 (2020), pp. 98-107.

Résumé

We consider the implementation of Boolean functions by circuits from unreliable functional elements in a complete basis containing functions of three variables. We suppose that the elements of the circuit pass to faulty states independently of each other, and they subject to the single-type constant faults of 0 type at outputs. For each complete basis, either the exact value of the coefficient of unreliability is found, or the upper estimate for this coefficient is calculated.

Détail

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

Bibliographie

[1] Von Neuman J., “Probabilistic logics and the synthesis of reliable organisms from unreliable components”, Automata Studies, eds. C. Shannon, J. McCarthy, Princeton University Press, 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 | MR | Zbl

[3] Ortyukov S. I., “On the redundancy of the Boolean functions implementation by circuits from unreliable elements”, Proc. Seminar 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”, LNCS, 278, 1987, 462–469

[5] Pippenger N., “On networks of noisy gates”, 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., 7, no. 1, 1982, 11–19 (in Russian) | DOI

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

[8] Alekhina M. A., “On the synthesis of reliable circuits of $x/y$ functional elements at the same type constant faults at the element outputs”, Vestnic Moskovskogo Universiteta. Matematika. Mekhanika, 1991, no. 5, 80–83 (in Russian)

[9] Alekhina M. A., Synthesis, Reliability and Complexity of Circuits With Unreliable Functional Gates, Doctoral dissertation in Mathematics and Physics, Penz. State Univ., Penza, 2004, 169 pp. (in Russian)

[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., Gusynina Yu. S., Shornikova T. A., “About reliability of circuits with faults of type 0 at the outputs of elements in a full finite basis containing a special function”, Russian Mathematics, 63:6 (2019), 79–81 | DOI | MR | Zbl

[12] Alekhina M. A., Klyanchina D. M., “On asymptotically optimal on reliability circuits in bases containing an essential linear function and a function of the form $x_1^a \ x_2^b$”, XVI Int. Conf. “Problems of theoretical cybernetics” (Nizhny Novgorod, 20–25 June 2011), Nizhny Novgorod State Univ., Nizhny Novgorod, 2011, 33–37 (in Russian)

[13] 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, 56–62 (in Russian)

[14] Alekhina M. A., Barsukova O. Yu., Shornikova T. A., “On the reliability of circuits with type 0 faults at the outputs of the elements in the complete finite basis containing an essential linear function”, Lobachevskii J. Mathematics, 40:12 (2019), 2027–2033 | DOI | MR | Zbl

[15] Alekhina M. A., Grabovskaya S. M., Gusynina Yu. S., “Sufficient conditions for implementation of Boolean functions by asymptotically optimal on reliability circuits with the trivial estimate of unreliability in the case of faults of type 0 at the element outputs”, Prikladnaya Diskretnaya Matematika, 2019, no. 45, 44–54 (in Russian)

[16] Alekhina M. A., Shornikova T. A., “On the reliability of circuits with type 0 faults at the outputs of elements in a complete finite basis containing some pairs of functions”, Russian Mathematics (in Russian)

[17] Alekhina M. A., “On reliability of circuits over an arbitrary complete finite basis under single-type constant faults at outputs of elements”, Discr. Math. Appl., 22:4 (2012), 383–391 | MR | Zbl

[18] Alekhina M. A., Pichugina P. G., “On the reliability of dual circuts in the complete finite basis”, 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)