RUS  ENG
Full version
JOURNALS // Preprints of the Keldysh Institute of Applied Mathematics // Archive

Keldysh Institute preprints, 2021 049, 18 pp. (Mi ipmp2966)

This article is cited in 1 paper

On self-correcting logic circuits of unreliable gates

K. A. Popkov


Abstract: The following statements are proved:
1) for any integer $m \geqslant 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: mathematical modelling in actual problems of science and technics.

DOI: 10.20948/prepr-2021-49



© Steklov Math. Inst. of RAS, 2025