О задержке схем из функциональных элементов в модели с произвольным распределением задержек элементов базиса по входам и входным наборамстатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 24 января 2020 г.
Аннотация:В работе изучается модель задержки схем из функциональных элементов в
произвольном конечном полном базисе Б, в которой задержки базисных
элементов задаются произвольными положительными действительными числами
для каждого входа и каждого входного набора переменных, поступающих на
остальные входы. В рассматриваемой модели для задержки мультиплексорной
функции порядка n получены асимптотические оценки вида $\tau_Б n
\pm O(\log n)$, где $\tau_Б$ - константа, зависящая только от
базиса Б. На основе этих оценок в рамках данной модели установлены
асимптотические оценки вида $\tau_Б n \pm O(\log n)$ для
соответствующей функции Шеннона, т.\,е. для задержки самой "плохой"
функции алгебры логики, зависящей от заданных n переменных.