RUS  ENG
Full version
JOURNALS // Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki // Archive

Kazan. Gos. Univ. Uchen. Zap. Ser. Fiz.-Mat. Nauki, 2009 Volume 151, Book 2, Pages 154–163 (Mi uzku758)

The XV International Conference "Problems of Theoretical Cybernetics"

About Circuit Reliability in Full Bases, Containing a Vote Function with Input Inverse Failures

V. V. Chugunova

Penza State University

Abstract: The paper considers Boolean functions to be realized by circuits of reliable functional elements being prone to input failures with fault probability $\varepsilon$, $0<\varepsilon<1/2,$ on any functional element input. It is shown that if to each of non-reducible full bases containing functions with at most two variables there will be added a vote function, then a reliability estimate of asymptotically optimal reliable circuits is equal $3\varepsilon^2$ (with $\varepsilon\to0$) for all Boolean functions $f(x_1,x_2,\dots,x_n)$ except for constants 0,1 and functions $x_i$, $\overline x_i$, where $i=1,\dots,n$.

Keywords: Boolean functions, asymptotically optimal reliable circuits.

UDC: 519.718

Received: 21.02.2009



© Steklov Math. Inst. of RAS, 2024