О поведении функции Шеннона для задержки схем в модели, где задержка соединений определяется типами соединяемых элементов

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