Article collection "Mathematical Problems of Cybernetics" ¹14, Moscow, 2005

Authors:Red'kin N.P.

Minimal self-correcting scheme for the binary digit comparison operator

Abstract:

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 scheme’s elements weights. For the Boolean function s_{n}(x, y) = (¬x_{1}\/ó_{1})&…&(¬x_{n}\/ó_{n}) where n≥2, Ð ≥3 and δ ϵ{0, 1} we show that L(s_{n}(x, y)) = 6n+P-2.