RUS  ENG
Full version
JOURNALS // University proceedings. Volga region. Physical and mathematical sciences // Archive

University proceedings. Volga region. Physical and mathematical sciences, 2010 Issue 1, Pages 64–79 (Mi ivpnz615)

This article is cited in 5 papers

Mathematics

On the bases in which asymptotically optimal schemes function with unreliability

A. V. Vasin

Penza State University, Penza

Abstract: We consider realization of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis $B \subseteq B_3$ ($B_3$ is the set of all Boolean functions of three variables $x_1, x_2, x_3$). We assume that all elements are subjected independently of each other to inverse failures at the output with the probability $\epsilon$ ($\epsilon \in (0,1/2)$). In this article we found bases, in which almost all boolean functions is possible to realize by asymptotically optimal on reliability circuits with unreliability equal $5\epsilon$ with $\epsilon \rightarrow 0$. We proved that there are not other bases where it's possible to realize almost all boolean functions by asymptotically optimal on reliability circuits with unreliability $5\epsilon$.

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

UDC: 519.718



© Steklov Math. Inst. of RAS, 2024