RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2010 Number 5, Pages 79–82 (Mi ivm6738)

This article is cited in 10 papers

Brief communications

Sufficient conditions for realizability of Boolean functions by asymptotically optimal circuits with the unreliability $2\varepsilon$

M. A. Alekhina, A. V. Vasin

Chair of Discrete Mathematics, Penza State University, Penza, Russia

Abstract: We consider realizations of Boolean functions by circuits composed of unreliable functional elements in some complete finite basis $B$. We assume that all elements independently of each other with the probability $\varepsilon$ ($\varepsilon\in(0;1/2)$) are subjected to inverse failures at the output.
We construct Boolean functions $\varphi(x_1,x_2,x_3)$ such that the presence of at least one of them in the considered basis $B$ guarantees the realizability of all three Boolean functions by circuits whose reliability does not exceed $2\varepsilon+144\varepsilon^2$ with $\varepsilon\le1/960$. In addition, if $B\subset B_3\setminus G$ ($B_3$ is the set of all Boolean functions of three variables $x_1$, $x_2$, and $x_3$, and $G$ is the set of Boolean functions such that each one of them is congruent either to $x_1^{\sigma_1}x_2^{\sigma_2}\vee x_1^{\sigma_1}x_3^{\sigma_3}\vee x_2^{\sigma_2}x_3^{\sigma_3}$, or to $x_1^{\sigma_1}x_2^{\sigma_2}\oplus x_3^{\sigma_3}$, or to $x_1^{\sigma_1}x_2^{\overline\sigma_2}\vee x_2^{\sigma_2}x_3^{\sigma_3}$ ($\sigma_1,\sigma_2,\sigma_3\in\{0,1\}$)), then the presence of at least one of functions $\varphi(x_1,x_2,x_3)$ guarantees the realizability of almost all Boolean functions by asymptotically optimal (with respect to the reliability) circuits, whose unreliability equals $2\varepsilon$ with $\varepsilon\to0$.

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

Received: 10.11.2009


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2010, 54:5, 68–70

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024