Об одновременной оптимизации формул по сложности и задержке на наборах в модели с задержками соединений между элементами

Актуальность и цели. Проблема синтеза дискретных управляющих систем является одной из основных проблем математической кибернетики. В общем виде она состоит в построении для заданной дискретной функции ее оптимальной (в том или ином смысле) структурной реализации в рассматриваемом классе управляющих систем. Теоретические результаты, полученные при решении указанной проблемы, находят применение в различных прикладных областях, к числу которых относятся задачи проектирования современных интегральных схем. Традиционная задача синтеза в рассматриваемой в работе постановке относится к изучению функции Шеннона для задержки, т.е. задержки самой «плохой» функции алгебры логики, зависящей от заданных n переменных. К рассматриваемой задаче относится ряд классических результатов теории дискретных управляющих систем, связанных, в частности, с нахождением схем асимптотически оптимальных одновременно по нескольким параметрам. Целью данной работы является перенесение известных результатов в области синтеза схем, связанных с одновременной оптимизацией схем по сложности и задержке на уровне асимптотических оценок, на новые модели задержки, отражающие емкостную специфику взаимосвязей элементов в интегральных схемах, а также различия временных характеристик элементов на различных наборах входных сигналов. Так, в работе изучается модель задержки в произвольном конечном полном базисе, в которой задержка базисного элемента - положительная действительная величина - по любому из его входов зависит от сигналов, подаваемых на остальные входы этого функционального элемента, и складывается из двух компонентов: задержки межэлементного соединения входа с выходом предыдущего элемента и, собственно, внутренней задержки рассматриваемого элемента. При этом задержки элемента по разным входам, вообще говоря, считаются независимыми величинами. Материалы и методы. Используемые инструменты включают в себя технику универсальных множеств функций и технику моделирования булевых функций переменными на компонентах специальных разбиений булевого куба. Метод синтеза схем формульного типа асимптотически оптимальных одновременно как по задержке, так и по сложности применяется к синтезу схем в рассматриваемой модели задержки. Результаты. Получена линейная относительно величины n асимптотика функции Шеннона для задержки функций алгебры логики от заданных n переменных. Оказалось, что привлечение дополнительной зависимости задержки от функциональной составляющей элементов базиса не приводит к изменению поведения функции Шеннона на уровне асимптотики. Построены схемы формульного типа, асимптотически оптимальные как по сложности, так и по задержке. Выводы. Установленные результаты позволяют сделать вывод о возможности перенесения классических результатов, связанных с одновременной оптимизацией схем формульного типа по сложности и по задержке, на новую модель задержки.