KIAM Main page Web Library  •  Publication Searh   

Article collection "Mathematical Problems of Cybernetics" 14, Moscow, 2005
Authors: Red'kin N.P.
Minimal self-correcting scheme for the binary digit comparison operator
We consider 1-self-correcting schemes with functional elements from then AND, OR, NOT basis i.e. the ones that realize the same boolean function both in their regular state and when one unreliable element switches to a faulty state. Every reliable element has weight P and always realizes the basis function that is assigned to it. Every unreliable element has weight 1 and realizes the assigned basis function only in a non-faulty state, and, when faulty, turns into a Boolean constant δ. Let L(f) be the least complexity of a 1-self-correcting scheme for the function f; complexity of a scheme is here considered to be the sum of schemes elements weights. For the Boolean function sn(x, y) = (x1\/1)&&(xn\/n) where n≥2, ≥3 and δ ϵ{0, 1} we show that L(sn(x, y)) = 6n+P-2.
functional elements, self-correcting schemes, complexity
Publication language: russian,  pages: 16 (p. 19-34)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text: