Volume 22, No 1, 2015, P. 5-18

UDC 519.718
A. V. Vasin
On a wide class of bases with unreliability coefficient equal to one

Abstract:
On a wide class of bases with unreliability coefficient equal to one Abstract. We consider a realization of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis B. We assume that all elements are subjected independently of each other to inverse failures on the output with probability ε (0, 1/2). We find a set of functions G and prove that the unreliability coefficient of the basis B which contains functions of G equals 1.
Ill. 3, bibliogr. 13.

Keywords: unreliable functional element, circuit asymptotically optimal with respect to reliability, inverse failure on outputs of elements, synthesis of circuits composed of unreliable elements.

DOI: 10.17377/daio.2015.22.435

Alexey V. Vasin¹
1. Penza State University,
40 Krasnaya St., 440026 Penza, Russia
 е-mail: alvarvasin@mail.ru

Received 27 Deсember 2013
Revised 24 April 2014

References

[1] S. I. Aksenov, On reliability of circuits over an arbitrary complete system of functions under inverse failures at the element outputs, Izv. VUZ. Povolzh. Reg., Ser. Estestv. Nauki, No. 6, 42–55, 2005.

[2] V. B. Alekseev, Lektsii po diskretnoi matematike (Lectures on Discrete Mathematics), Izdatel’skii Otd. Fak. VMiK MGU, Moscow, 2004.

[3] M. A. Alekhina, Sintez asimptoticheski optimal’nykh po nadezhnosti skhem iz nenadezhnykh elementov (Synthesis of Asymptotically Optimal Reliable Circuits from Unreliable Elements), Inf.-Izdatel’skii Tsentr PGU, Penza, 2006.

[4] M. A. Alekhina, S. I. Aksenov, and A. V. Vasin, On functions and circuits used to improve reliability of circuits, Izv. VUZ. Povolzh. Reg., Ser. Fiz.-Mat. Nauki, No. 3, 30–38, 2008.

[5] M. A. Alekhina and A. V. Vasin, On reliability of combinatorial circuits in bases containing functions with at most three variables, Uch. Zap. Kazan. Gos. Univ., Ser. Fiz.-Mat. Nauki, 151, No. 2, 25–35, 2009.

[6] A. V. Vasin, On functions of a special form, in Trudy VIII Mezhdunarodnoi konf. “Diskretnye modeli v teorii upravlyayushchikh sistem” (Proc. VIII Int. Conferentsii “Discrete Models in the Theory of Control Systems”), Lesnoi gorodok, Moscow Reg., Russia, Apr. 6–9, 2009, pp. 43–46, MAKS Press, Moscow, 2009.

[7] A. V. Vasin, On asymptotically optimal circuits in the base {&, ¬} under inverse failures at the element outputs, Diskretn. Anal. Issled. Oper., 16, No. 6, 12–22, 2009.

[8] O. B. Lupanov, Asimptoticheskie otsenki slozhnosti upravlyayushchikh sistem (Asymptotic Bounds on Complexity of Control Systems), Izdatel’stvo MGU, Moscow, 1984.

[9] J. von Neumann, Probabilistic logics and the synthesis of reliable organisms from unreliable components, in C. E. Shannon and J. McCarthy, eds., Automata Studies, pp. 43–98, Princeton, NJ: Princeton Univ. Press, 1956. Translated in Avtomaty, pp. 68–139, Izdatel’stvo Inostrannoy Literatury, Moscow, 1956.

[10] S. I. Ortyukov, On redundancy of Boolean function realization with circuits of unreliable elements, in Trudy seminara po diskretnoi matematike i ee prilozheniyam (Proc. Seminar on Discrete Mathematics and its Applications.) Moscow, Russia, Jan. 27–29, 1987, pp. 166–168, Izdatel’stvo MGU, Moscow, 1989.

[11] V. V. Chugunova, Synthesis of asymptotically optimal reliable circuits under inverse failures at the element outputs, Cand. Sci. Dissertation, Penz. Gos. Univ., Penza, 2007.

[12] S. V. Yablonskii, Asymptotically best method for synthesis of reliable circuits from unreliable elements, in J. L. Kulikowski, M. Michalewicz, S. V. Yablonskii, and Yu. I. Zhuravlev, eds., Discrete Mathematics, pp. 11–19, Instytut Matematyczny PAN, Warsaw, 1982 (Banach Cent. Publ., Vol. 7).

[13] D. Uhlig, Reliable networks from unreliable gates with almost minimal complexity, Fundamentals of Computation Theory (Proc. Int. Conf. FCT′87, Kazan, USSR, June 22–26, 1987), 462–469, Springer-Verl., Berlin, 1987 (Lect. Notes Comput. Sci., Vol. 278).