?
О поведении функции Шеннона для задержки схем в модели, где задержка соединений определяется типами соединяемых элементов
Background
The problem of synthesis of discrete control systems is one of the main problems of mathematical cybernetics. In general form 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 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 study considers integral circuits via the model of networks of functional elements and gives the particular meaning to the delay in this model. 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 asymptotic 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 so called high accuracy asymptotic estimates.
The goal of the work is to carry known results in the area of circuit synthesis over circuit models that reflect capacitive peculiarity of gate interconnections with greater accuracy. The work considers a delay model over an arbitrary finite complete basis where delay of the gate (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
Used instruments involve, among other things, solution of the system of finite difference equations, matrix approach, Perron theorem. The known synthesis method of optimal delay circuits is implemented to circuit synthesis in the described delay model.
Results
Obtained linear in regard to n Shannon function asymptotic for the delay of Boolean functions that depend on a given n variables and linear in regard to n multiplexor (or data access) function delay, i.e. Boolean function with n address and 2^n data variables that equals to the value of the data variable numbered with the set of values given by address variables interpreted in binary notation. High accuracy asymptotic estimates similar to earlier known estimates in simpler delay models are established for Shannon function for delay and for delay of multiplexor function in a certain subclass of bases under study.
Conclusions
Established results allow to educe the existence of asymptotic for Shannon function for delay and the applicability of the earlier known optimal delay circuit synthesis methods in a wider class of delay models.