RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2013 Issue 6, Pages 56–57 (Mi pdma119)

Математические основы компьютерной безопасности и надёжности вычислительных и управляющих систем

About basises whose unreliability coefficient equals 1

A. V. Vasin

Penza State University

Abstract: Circuits composed of unreliable functional elements in a complete finite basis $B$ are considered. It is assumed that all elements are independently of each other subjected to inverse failures at the outputs with the probability $\varepsilon$ ($\varepsilon \in (0, 1/2)$). In the paper, a set $G$ of Boolean functions is found, and it is proved that if $B\cap G\neq\emptyset$, then almost all Boolean functions are realized in basis $B$ by asymptotically optimal on reliability circuits with unreliability $\varepsilon$ under $\varepsilon\to 0$.

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

UDC: 519.718



© Steklov Math. Inst. of RAS, 2024