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

University proceedings. Volga region. Physical and mathematical sciences, 2008 Issue 4, Pages 2–16 (Mi ivpnz753)

This article is cited in 7 papers

Mathematics

On asymptotically optimal schemes in the basis of $\{x\&y, x\vee y, \overline{x}\}$ with inverse faults at the outputs of the elements

A. V. Vasin

Penza State University, Penza

Abstract: The problem of synthesizing asymptotically optimal schemes implementing Boolean functions with inverse faults at the outputs of elements in the basis $\{x\&y, x\vee y, \overline{x}\}$ is considered. It is proved that almost all Boolean functions can be implemented with asymptotically optimal reliability schemes that function with an unreliability asymptotically equal to $3\epsilon$ at $\epsilon\to 0$, where $\epsilon$ is the probability of an inverse malfunction at the output of the base element. The complexity of the proposed schemes exceeds the complexity of the minimum schemes built only from reliable elements by no more than 3 times.

UDC: 718.95



© Steklov Math. Inst. of RAS, 2024