Synthesis and Complexity of Asymptotically Optimal Circuits with Unreliable Gates

• Autorzy: Alekhina M.Z.
• Języki publikacji: EN

Abstrakty

EN

We consider the realization of Boolean functions by combinatorial circuits with unreliable gates computing the functions from a complete final basis B. We assume that all gates of the basis can have inverse faults on the outputs independently with probability ε(ε∈(0,1/2). We describe a set Mk (k≥3) of Boolean functions, presence even by one of which in basis B guarantees the computing of almost all Boolean functions by asymptotically optimal circuits with unreliability ε at ε→0. We prove that, for almost all functions, the complexity of asymptotically circuits with unreliable gates exceeds the complexity of the minimal circuits constructed from absolutely reliable gates by a multiplicative factor of 3(1 + b) for any b > 0.

Słowa kluczowe

EN

Boolean function; synthesis; complexity; reliability of combinatorial circuits

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 104, nr 3
• Strony: 219--225
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Alekhina M.Z.

• Penza State University, Krasnaya st., 40, Penza, Russia,

Bibliografia

• [1] J. von Neumann: Probabilistic logic and synthesis of reliable organisms from unreliable components, Automata Studies, ed. C.E. Shannon and J. McCarthy, Princeton-New Jersey, 1956.
• [2] S. I. Aksenov: On the reliability of circuits in any full basis at inverse faults on outputs of gates, Transactions of the Volga region universities (Izvestiya Vysshykh Uchebnykh Zavedeny. Povolgsky Region). Natural sciences. N 6, 2005. P. 42-55.
• [3] N. P. Red'kin: Reliability and diagnostic of the circuits, Moscow (in Russia), 1992.
• [4] S. I. Ortyukov: On the redundancy of the realization of Boolean functions by the circuits of unreliable gates, Transactions of seminar on discrete mathematics and its applications (Moscow, 27 - 29 January 1987). Moscow (in Russia), 1989. P. 166-168.
• [5] D. Uhlig: Reliable circuits of unreliable elements with almost minimal comlexity, Fundamentals of Computation Theory. Intern. sonf. FCT'87 (Kazan, June 1987 - Proc. Berlin: Springer-Verl., 1987. P. 462-469. (Lecture Notes in Comput. Sci.; V. 278).
• [6] O. B. Lupanov: On the one method of synthesis of circuits, News of high schools, Radiophysics. 1958. V. 1. N 1. P. 120-140.
• [7] M. A. Alekhina: On reliability and complexity of circuits in basis {x|y} at inverse faults on outputs of elements, Discrete analysis and research of operations. Series 1. 2005. V. 12. N 2. P. 3-11.
• [8] M. A. Alekhina: Synthesis of the asymptotically optimal on the reliability combinatorial circuits (Monograph), Penza (in Russia), 2006.