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. Alekhina ; S. M. Grabovskaya ; Yu. S. Gusynina

Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 44-54

Résumé

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$.

Détail

Mots-clés : circuit
Keywords: faults of type $0$ at the element outputs, unreliability, asymptotically optimal on reliability circuit, Boolean function.