О поведении функции Шеннона для обобщённой глубины схем в модели, где глубина межэлементного соединения определяется надсхемой ограниченного размерастатья
Аннотация:В работе рассматривается массовая задача синтеза асимптотически оптимальных
по глубине в худшем случае схем из функциональных элементов над конечным
полным базисом. Рассматривается одно из возможных обобщений понятия глубины
схем из функциональных элементов, при котором глубина функциоанльного
элемента по каждому его входу определяется подключённой к нему схемой
ограниченного размера. Установлены асимптотические оценки функции Шеннона
для обобщённой глубины функций из класса функций алгебры логики, зависящих
от переменных x1, ..., xn, при их реализации схемами из функциональных
элементов и обобщённой глубины мультиплексорной функций порядка n, в
некоторых случаях имеющие так называемую высокую степень точности.
Мультиплексорная функция порядка n - это функция алгебры логики с n
адресными и 2^n информационными переменными, равная той информационной
переменной, номер которой задаётся в двоичной системе счисления набором
значений адресных переменных, а глубина этой функции - это глубина
наименьшей по глубине схемы её реализующей.