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

Prikl. Diskr. Mat., 2019 Number 45, Pages 44–54 (Mi pdm670)

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



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024