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

M. A. Alekhina ; S. M. Grabovskaya ; Yu. S. Gusynina

Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 44-54.

Résumé

The implementation of Boolean functions by circuits of unreliable functional elements is considered in a complete finite basis, containing a function of the set $M$, where $M = {\bigcup\limits_{i=1}^4 \left(M_i \cup M_i^* \right)}$, $M_1 = \text{Congr}\{x_1^{\sigma_1}x_2^{\sigma_2} \vee x_1^{\bar\sigma_1}x_2^{\bar\sigma_2}x_3^{\sigma_3} : \sigma_i \in \{0,1\}, i\in\{1,2,3\}\}$, $M_2 = \text{Congr}\{x_1^{\sigma_1}x_2^{\sigma_2}x_3^{\sigma_3} \vee x_1^{\sigma_1}x_2^{\bar\sigma_2}x_3^{\bar\sigma_3} \vee x_1^{\bar\sigma_1}x_2^{\sigma_2}x_3^{\bar\sigma_3}: \sigma _i \in \{0,1\},i \in \{1,2,3\}\}$, $M_3 = \text{Congr}\{\bar x_1 (x_2^{\sigma_2} \vee x_3^{\sigma_3}): \sigma _i \in \{0,1\},i \in \{1,2,3\}\}$, $M_4 = \text{Congr}\{x_1^{\sigma_1}x_2^{\sigma_2}x_3^{\sigma_3} \vee x_1^{\bar\sigma_1}x_2^{\bar\sigma_2}x_3^{\bar\sigma_3}: \sigma _i \in \{0,1\},i \in \{1,2,3\}\}$. The set $M_i^*$ is the set of functions, each of which is dual to some function of $M_i$. All functional elements independently of each other with the probability $\varepsilon \in (0, 1/2)$ are assumed to be prone to faults of type 0 at the element outputs. These faults are characterized by the fact that in good condition the functional element implements the function assigned to it, and in the faulty — constant 0. It is proved that almost any Boolean function can be implemented in a complete finite basis $B$, $B\cap M \neq\emptyset$, by an asymptotically optimal on reliability circuit working with unreliability asymptotically equal to $\varepsilon$ at $\varepsilon\to 0$.

Détail

Mots-clés : circuit
Keywords: faults of type $0$ at the element outputs, unreliability, asymptotically optimal on reliability circuit, Boolean function.

Bibliographie

[1] Von Neumann 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”, 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”, 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:1 (1982), 11–19 (in Russian) | DOI | MR

[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 MSU, Matematika Mekhanika, 1991, no. 5, 80–83 (in Russian)

[9] Alekhina M. A., The synthesis of asymptotically optimal on reliability circuits, Penz. State Univ., Penza, 2006, 156 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., Klyanchina D. M., “Sufficient conditions for the implementation of Boolean functions by asymptotically optimal circuits with a trivial estimate of unreliability”, Int. Symp. “Reliability and quality, 2010” (Penza, Russia, 24–31 May 2010), Penz. State Univ., Penza, 2010, 229–232 (in Russian)

[12] Alekhina M. A., Klyanchina D. M., “On asymptotically optimal on reliability circuits in some special bases”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2010, no. 4 (16), 3–13 (in Russian) | MR

[13] 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)

[14] Gavrilov G. P., Sapozhenko A. A., Tasks and Exercises in Discrete Mathematics, tutorial, 3rd ed., revised, Fizmatlit Publ., M., 2006, 416 pp. (in Russian)

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

[16] 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 | DOI | MR | Zbl

[17] 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)

[18] Alekhina M. A., Gusynina Yu. S., Shornikova T. A., “On the reliability of circuits in case of faults of type 0 at the outputs of elements in the complete finite basis, containing a special function”, Izv. Vyssh. Uchebn. Zaved. Mat., 2019, no. 6, 85–88 (in Russian)

[19] 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)