?
Об одновременной оптимизации формул по сложности и задержке на наборах в модели с задержками соединений между элементами
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. Traditional synthesis problem under study 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 construction of circuits that are asymptotically optimal according to several parameters simultaneously apply to the described problem.
The goal of the work is to carry known results in the area of circuit synthesis, that apply to simultaneous circuits optimization over several parameters, over circuit models that reflect capacitive peculiarity of gate interconnections with greater accuracy and also reflect timing parameters of gates under different input signals. 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 depend on signals passed on its other inputs and 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 the technique of universal sets of Boolean functions and technique of Boolean functions modelling on components of Boolean cube special partitions. The synthesis method of formula type circuits that are asymptotically optimal both by complexity and by delay is implemented for 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. It is proved that incorporation of an additional delay component such as its input signals dependence doesn’t lead to a change of Shannon function asymptotical behavior. Formula type circuits asymptotically optimal both by complexity and by delay are constructed.
Conclusions
Established results allow to educe the applicability of the earlier known results concerned with simultaneous formula type circuits optimization over several parameters to a wider class of delay models.