zbMATH — the first resource for mathematics

On reliability of circuits over the basis \(\{x \vee y \vee z, x \, \&\, y\, \& \, z, \bar x\}\) under single-type constant faults at inputs of elements. (English. Russian original) Zbl 1121.94032
Discrete Math. Appl. 16, No. 2, 195-203 (2006); translation from Diskretn. Mat. 18, No. 1, 116-125 (2006).
Summary: We consider realisation of Boolean functions over the basis \(\{x \vee y \vee z, x\, \& \, y\, \& \, 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},\cdots, x_{n} )\) such that the functions \(x_{i}\) , \(i = 1, 2,\cdots ,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 \rightarrow 0\).
94C12 Fault detection; testing in circuits and networks
Full Text: DOI
[1] N. P. Redkin, Reliability and Diagnosis of Circuits. Moscow State Univ. Press, Moscow, 1992 (in Russian)
[2] Math. Notes 20 pp 775– (1976)
[3] J. von Neumann, Probabilistic logic and the synthesis of reliable organisms from unreliable parts. In: Automata Studies (C. E. Shannon, Ed.) Princeton Univ. Press, Princeton, 1956, pp. 43-98.
[4] S. I. Ortyukov, On redundancy of realisation of Boolean functions by circuits of unreliable gates. In: Proc. Seminar Discrete Math. Appl. Moscow State Univ. Press, Moscow, 1989, pp. 166-168 (in Russian).
[5] Lecture Notes Comput. Sci. 278 pp 462– (1987)
[6] Discrete Math. Appl. 11 pp 493– (2001)
[7] M. A. Alekhina, Lower bounds for unreliability of networks in some bases under single-type faults at the input of elements. Discrete Anal. Oper. Res., Ser. 1 (2002) 9, No. 3, 3-28 (in Russian). · Zbl 1029.68026
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.