On the reliability of schemes in the basis $\{x\vee y\vee z,x\mathbin{\}y\mathbin{\}z,\bar{x}\}$ with single-type constant faults at the inputs of the element

M. A. Alekhina

Diskretnaya Matematika, Tome 18 (2006) no. 1, pp. 116-125

Résumé

We consider realisation of Boolean functions over the basis $\{x \vee y \vee z, x\mathbin{\}y \mathbin{\}z, \bar{x}\}$ by circuits of unreliable functional elements which are subject to single-type constant faults at inputs of the elements. Let $\gamma$ be the probability of a fault at an input of an element. By the unreliability of a circuit is meant the greatest probability of error at its output. In this paper, we find the asymptotically best realisation of an arbitrary Boolean function $f(x_1,\dots,x_n)$ such that the functions $x_i$, $i=1,2,\dots,n$, are realised absolutely reliably, the constants 0 and 1 are realised as reliably as we wish, and the remaining functions are realised with unreliability asymptotically equal to $\gamma^3$ as $\gamma\to 0$. This research was supported by the Scientific Program ‘Universities of Russia,’ grant 04.01.032.