On self-correcting logic circuits of unreliable gates

Abstract:

The following statements are proved: 1) for any integer m ≥ 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.

Keywords:

logic circuit, self-correction, unreliable gate, Boolean function

Publication language:russian, pages:18

Research direction:

Mathematical modelling in actual problems of science and technics