Delay in networks of functional elements in a model with an arbitrary distribution of basis element input delays

Computational Mathematics and Modeling. 2012. Vol. 23. No. 4. P. 487–506.

Lozhkin S. A., Danilov B.R.

В работе изучается модель задержки схем из функциональных элементов в произвольном конечном полном базисе Б, в которой задержки базисных элементов по различным входам могут различаться. В рассматриваемой модели получены асимптотические оценки вида τБn±O(1), где τБ ― константа, зависящая только от базиса Б, для задержки мультиплексорной функции порядка  n, то есть функции с n адресными и 2n информационными переменными равной той информационной переменной, номер которой задаётся в двоичной системе счисления набором значений адресных переменных. На основе этих оценок в рамке данной модели установлены также асимптотические оценки высокой степени точности вида τБ(n-loglogn)±O(1) для соответствующей функции Шеннона, то есть для задержки самой «плохой» функции алгебры логики, зависящей от заданных n переменных.

Ключевые слова: булева функция, Boolean function, control systems synthesis and complexity, синтез и сложность управляющих систем, Shannon function, функция Шеннона