Method of reliable cellular circuit synthesis using the choice function

Background. One of the most important fileds of mathematical cybernetics is the theory of synthesis, reliability and complexity of control systems. Such models of discrete functions computing as circuits made of functional gates are well known. These circuits, made of both absolutely reliable and unreliable gates, have been studied for a long time; there have been obtained multiple results. However, in real circuits it is necessary to take into account not just functioning of gates, but a circuit's geometry as well. In this connection there has been suggested a model of cellular circuits made of functional gates, where the circuit is represented as a rectangle, divided into cells, containing circuit's gates, having certain sizes and occupying a certain area. Cellular gates may be both functional, i.e. performing some function from their inputs, and switching ones, that transmit a signal to the next gate with a possible change of direction. The work presupposes that switching gates are absolutely reliable, and at any of two outputs of each functional gate at the same probability independently there occur inverse failures. Previously, there was suggested the method of building asymptotic reliability-optimal cellular circuits, based on expansion of a function by a variable. However, the circuits, built in such manner, are too complicated. The aim of the article is to signidicantly improve complexity estimation for asymptotically reliability-optimal cellular circuits. Materials and methods. In order to build asymptotically reliability-optimal cellular circuits the author used cellular circuits realizing the choice functions. The article shows how to realize any Boolean function from n variables using such circuits, as well as estimates reliability and complexity of the suggested circuits, having a significantly lower complexity compared to the previously known. Results. The author suggested the method of synthesis of asymptotically reliability-optimal cellular circuits with improved complexity. The researcher estimated reliability of the suggested circuits and proved the theorems of complexity thereof. Conclusions. The known complexity estimation for asymptotically reliability-optimal cellular circuits has been significantly improved.