On Self-Correcting Logic Circuits of Unreliable Gates
Кирилл Андреевич Попков · Lobachevskii Journal of Mathematics · 2021
We consider a problem of implementation of Boolean functions by self-correcting logic circuits of unreliable gates in different bases. A set of permitted faults for each gate is predefined, with no restrictions imposed, except that it should be non-void. The following statements are proved: 1) For any integer $$m\geq 3$$ there is a basis consisting of Boolean functions of no more than $$m$$ variables, in which any Boolean function can be implemented by a logic circuit of unreliable gates that self-corrects relative to certain faults in an arbitrary number of gates. 2) For any positive integer $$k$$ there are bases consisting of Boolean functions of no more than two variables, in each of which any Boolean function can be implemented by a logic circuit of unreliable gates that self-correct relative to certain faults in no more than $$k$$ gates. 3) There is a functionally complete basis consisting of Boolean functions of no more than two variables, in which almost no Boolean function can be implemented by a logic circuit of unreliable gates that self-correct relative to at least some faults in no more than one gate.