This article is cited in
1 paper
Mathematical Backgrounds of Computer and Control System Reliability
Sufficient conditions for implementation of Boolean functions by asymptotically optimal on reliability circuits with the trivial estimate of unreliability in the case of faults of type $0$ at the element outputs
M. A. Alekhinaa,
S. M. Grabovskayab,
Yu. S. Gusyninaa a Penza State Technological University, Penza, Russia
b Penza State University, Penza, Russia
Abstract:
The implementation of Boolean functions by circuits of unreliable functional elements is considered in a complete finite basis, containing a function of the set
$M$, where $M = {\bigcup\limits_{i=1}^4 \left(M_i \cup M_i^* \right)}$, $M_1 = \text{Congr}\{x_1^{\sigma_1}x_2^{\sigma_2} \vee x_1^{\bar\sigma_1}x_2^{\bar\sigma_2}x_3^{\sigma_3} : \sigma_i \in \{0,1\}, i\in\{1,2,3\}\}$, $M_2 = \text{Congr}\{x_1^{\sigma_1}x_2^{\sigma_2}x_3^{\sigma_3} \vee x_1^{\sigma_1}x_2^{\bar\sigma_2}x_3^{\bar\sigma_3} \vee
x_1^{\bar\sigma_1}x_2^{\sigma_2}x_3^{\bar\sigma_3}: \sigma _i \in \{0,1\},i \in \{1,2,3\}\}$, $M_3 = \text{Congr}\{\bar x_1 (x_2^{\sigma_2} \vee x_3^{\sigma_3}): \sigma _i \in \{0,1\},i \in \{1,2,3\}\}$, $M_4 = \text{Congr}\{x_1^{\sigma_1}x_2^{\sigma_2}x_3^{\sigma_3} \vee x_1^{\bar\sigma_1}x_2^{\bar\sigma_2}x_3^{\bar\sigma_3}: \sigma
_i \in \{0,1\},i \in \{1,2,3\}\}$. The set
$M_i^*$ is the set of functions, each of which is dual to some function of
$M_i$. All functional elements independently of each other with the probability
$\varepsilon \in (0, 1/2)$ are assumed to be prone to faults of type 0 at the element outputs. These faults are characterized by the fact that in good condition the functional element implements the function assigned to it, and in the faulty — constant 0. It is proved that almost any Boolean function can be implemented in a complete finite basis
$B$,
$B\cap M \neq\emptyset$, by an asymptotically optimal on reliability circuit working with unreliability asymptotically equal to
$\varepsilon$ at
$\varepsilon\to 0$.
Keywords:
circuit, faults of type $0$ at the element outputs, unreliability, asymptotically optimal on reliability circuit, Boolean function.
UDC:
519.718
DOI:
10.17223/20710410/45/5