On behaviour of the Shannon function of circuits delay of a model where interconnections delay is determined by types of connectable gates

Background. The problem of discrete control systems synthesis is one of the main problems of mathematical cybernetics. In general it consists in construction of an optimal (in a varying sense) structural implementation of a given discrete function in a given class of control systems. Theoretical results obtained during the solution of the mentioned problem find their applications in different applied areas among each are the problems of integral circuits design. One of the main parameters of an integral circuit is its performance which is determined, among other things, by the speed of signal transmission from circuit inputs to its outputs. This property of a circuit is called a delay. Generally delay is a rather complex parameter that is determined by a number of circuit elements' properties and means of elements interconnections. Mathematical definition of the synthesis problem under investigation considers integral circuits via the model of networks of functional elements and gives the particular meaning to the delay in this model. The traditional synthesis problem in its given definition particularly concerns the study of the Shannon function for delay, i.e. the delay of the “worst” Boolean function that depends on a given set of n variables. A number of classic results in the theory of discrete control systems concerned with establishment of the Shannon function asymptotics for the delay apply to the described problem. A number of new areas also apply to this problem and, in particular, the branch concerned with establishment of the so-called high accuracy asymptotic estimates. The goal of the work is to carry the known results into the area of circuit synthesis over circuit models that reflect the capacitive peculiarity of gate interconnections with greater accuracy. The work considers a delay model over an arbitrary finite complete basis where the gate delay (a positive real quantity) over any of its inputs is composed of two components: the gates' interconnection delay of the input with the output of the previous gate, and the inner delay of the gate. Meanwhile, delays of a gate over its different inputs are, generally speaking, considered to be independent values. Materials and methods. The instruments used involve, among other things, a solution of the system of finite difference equations, the matrix approach, the Perron theorem. The known synthesis method of optimal delay circuits is implemented to the circuit synthesis in the described delay model. Results. The obtained Shannon function asymptotics, linear in regard to n, for the delay of the Boolean functions that depend on the given n variables and the multiplexor function delay, i.e. the Boolean function with n address and 2$^n$ data variables that equal to the value of the data variable numbered with the set of values given by the address variables interpreted in binary notation. High accuracy asymptotic estimates similar to earlier known estimates in simpler delay models are established for the Shannon function for delay and for multiplexor function delay in a certain subclass of bases under investigation. Conclusions. The established results allow to conclude about the existence of asymptotics for the Shannon function for the delay and the applicability of the earlier known optimal delay circuit synthesis methods in a wider class of delay models.