Содержание к диссертации
Введение
Глава 1. Построение формул максимального ранга при ограниченной глубине. Нижние оценки функций Шеннона для глубины и задержки 30
1.1 Простейшие асимптотические оценки ранговой функции базиса 30
1.2 Шаблоны подключений и их связь с ранговой функцией 37
1.3 Ранговая функция однородного шаблона подключений 43
1.4 Ранговая функция в базисах специального вида 52
1.5 Нижние мощностные оценки функций Шеннона 60
Глава 2. Синтез схем для различных ФАЛ. Поведение функций Шеннона для глубины и задержки. Оценки сложности получаемых схем 66
2.1 Вспомогательные утверждения о реализации некоторых ФАЛ 66
2.2 Мультиплексорные ФАЛ и их обобщённое разложение 72
2.3 Реализация мультиплексорных ФАЛ 79
2.4 Асимптотически наилучшие оценки функций Шеннона для глубины и задержки, а также глубины и задержки мультиплексорных ФАЛ в базисах общего вида 91
2.5 Уточнённые оценки и оценки высокой степени точности функций Шеннона для глубины и задержки, а также глубины и задержки мультиплексорных ФАЛ в базисах специального вида 103
Заключение 116
Литература
- Ранговая функция однородного шаблона подключений
- Нижние мощностные оценки функций Шеннона
- Реализация мультиплексорных ФАЛ
- Уточнённые оценки и оценки высокой степени точности функций Шеннона для глубины и задержки, а также глубины и задержки мультиплексорных ФАЛ в базисах специального вида
Ранговая функция однородного шаблона подключений
Во введении упоминалось1, что операции удаления висячей вершины и поднятия ветвления выхода функционального элемента к входам схемы не изменяют ни задержки, ни глубины схем и позволяют преобразовать любую СФЭ (СФЭ с одним выходом) над заданным базисом в эквивалентную ей систему формул (соответственно формулу) над тем же базисом, задержка и глубина которой совпадают с задержкой и соответственно глубиной исходной СФЭ. Поэтому в дальнейшем нам достаточно ограничиться рассмотрением формул.
Переходя к формулам, приведём еще несколько необходимых определений. Единственный выходной функциональный элемент формулы будем называть её главным функциональным элементом. В особом случае тривиальной формулы-переменной, не имеющей в своём составе функциональных элементов, главным функциональным элементом назовём элемент, приписанный в качестве пометки её единственного входа-выхода. Максимальные по включению2 собственные подформулы данной нетривиальной формулы назовём её главными подформулами. Выходы главных подформул поступают на входы главного функционального элемента содержащей их формулы. Корневой подформулой назовём такую формулу-подсхему объемлющей схемы формульного типа, которая содержит её выходной функциональный элемент (вход-выходную переменную). Корневая подформула, вообще говоря, не является подформулой в смысле включения строк. Каркасом фор-1См. с. 19. 2Включение формул рассматривается в этом определении как включение строк. мулы назовём соответствующий её схемному представлению граф (корневое квазидерево), в котором опущены пометки вершин переменными. Назовём переменную формулы существенной, если эта переменная является существенной для реализуемой этой формулой ФАЛ. Будем называть формулу абсолютной (бесповторной), если каждая её переменная (соответственно каждая её существенная переменная) входит в формулу ровно один раз.
Определим константы, связанные с базисом Щ, которые будут использоваться на протяжении всего дальнейшего изложения: кmin = min hi, kmax = max hi, Dmin = mmDijs, Dmax = maxDyS, Tmax = maxT-v! , Lmax = maxL. J i ? l j ki, &ЄВ Замечание. Для облегчения записи, подобно обозначениям для количества Ь, типов Si, арностей кг, глубин Dijs, задержек Т$ элементов базиса % введённые здесь (и некоторые другие вводимые далее3) константы не снабжены обозначением базиса, к которому они относятся. Будем всегда относить эти константы к базису, который в рассматриваемом контексте обозначается буквой Щ.
Приведённая глубина тф базиса Щ является ввиду своего фундаментального значения единственным исключением из указанного в замечании правила обозначения базисных констант. Напомним читателю её определение (4), данное на с. 22: t Тф = Ит , (4) t +oo log2 Ry(t) и докажем следующие два утверждения относительно этой величины. Утверждение 1 [55, с. 83]. Нижний предел (4) конечен и положителен. Доказательство. Для любого положительного t глубина формулы Tt, представляющей собой полное4 [t/Dmax\ -ярусное дерево, составленное из любых функциональных элементов базиса Щ, не больше t, и поэтому Щ(і) R t) к\m i n , 3См. также замечание на с. 59. 4Через [d\, \d \ обозначаются ближайшее к d снизу и соответственно сверху целое число. откуда для приведённой глубины базиса $ получаем тф max/ log2 кmin. С другой стороны, структурная глубина формулы, на которой достигается значение Ry(t), не больше чем t/Dmin, и поэтому R $(t) /Сm a xmin, откуда Гф Дmin/ log2 A;max. Утверждение доказано. Утверждение 2 [55, лемма 2]. Существует конечный верхний предел lim і—Ігттт, который совпадает с приведённой глубиной базиса т р. Доказательство. Покажем, что для любого положительного є существует положительное число Do = DQ{S) такое, что для любого t DQ Тф + є. (1.1) log2 R $(t) В силу (4) найдём формулу Т такую, что: /гЧ ДИ . log2 R\J ) о , Тф Н—, (1.2) Є log2 іг(у-) З Рассмотрим формулу J7!, которая получается из Т «зацикливанием», то есть заменой пометок входов Т пометкой, связанной с типом её выходного функционального элемента, и для которой, очевидно, R{T\) = Я( г), D(Ti) D ) + Dmax, то есть в силу неравенств (1.2) выполняются соотношения D(FX) D{F) + Dmax 2 g2rt(y-ij log2rt(y-j З Для каждого т = 2,3,... построим формулу Тт, которая представляет собой полное т-ярусное дерево, составленное из формул Т\ как из «макроэлементов». Заметим, что при этом log2 R(J-m) = mlog2 R{J-\) и D(J-m) = m D(J-i), (1.3) то есть DiJ-m) D(J-\) = Гф H—є. (1.4) log2 R{J-m) log2it(y-i) 3 Выберем натуральное число mo так, чтобы выполнялось неравенство Щ -\—є)(1Н ) Гф + є, (1.5) V 3 TTIQ положим Do = то D(Fi) и докажем, что для любого t DQ справедливо (1.1). Действительно, выберем т = [t/D(Ti)\ m0 и рассмотрим формулу Тт, для которой в силу (1.3) выполняются неравенства t — D(J-\) D(J-m) t. Следовательно, учитывая (1.3)–(1.5), получим: І ТЧ/-Г- T% Є " ТЧ-Г- log2ii(yO) 3 mlog2R(J-i) D(J-m) + D(J-\) f 2 \ D(J i / 2 \/ 1 \ / 2 \/ 1 \ hpH—є ) I 1 H r H—є 1 H тю + є. V 3 m V 3 m,( [og2 Ky{t) log2 K{J-m) v 3 2 \ / -ЄІ + v 3 m 3 mo Утверждение доказано. Утверждение 2 показывает нам, что возможно следующее эквивалентное (4) определение приведённой глубины базиса Щ: t 4= Нт , (1.6) t- +oo log2 Ky{t) из которого непосредственно вытекает утверждение теоремы 1 со с. 22, приводимое в этом месте повторно. Теорема 1 . Для любого (конечного, полного) базиса Щ выполняются асимптотические соотношения: Ky{t) = zT , (5) в которых ту-приведённая глубина базиса %
Рассматриваемая далее лемма 4 позволяет установить существование формул наперёд заданного ранга с «хорошей» глубиной и используется нами во второй главе наряду с нижними оценками соответствующих функций (теоремы 3, 5) для оценки глубины мультиплексорной функции (теорема 7) и построения формул асимптотически оптимальных по глубине и задержке (теорема 8). Прежде чем мы приведём утверждение леммы, докажем одно свойство ранговой функции базиса.
Нижние мощностные оценки функций Шеннона
Напомним, что в настоящей работе стандартным называется базис %, который состоит из трёх функциональных элементов &, Еу, , реализующих соответственно ФАЛ х\ Х2, Х\ V Х2, Х\. Результаты текущего параграфа носят вспомогательный характер и относятся к реализации некоторых специальных ФАЛ в стандартных базисах.
Рассмотрим операцию присоединения (конкатенации) двоичного набора а Є Вп к двоичному набору /З Є Вт, результатом которой является двоичный набор 7 Є Вп+т, получающийся из набора а приписыванием к нему справа набора /3. В этом случае будем писать 7 = а . /3 и говорить, что набор а является префиксом набора 7, а набор /3 - его суффиксом.
Число, двоичной записью которого является набор а Є Вп, будем записывать через v(a), а набор длины п, который является записью целого числа d, О d 2п — 1, в двоичной системе счисления, обзначим через v l(d). Вектором значений ФАЛ / называется двоичный набор /, составленный из значений ФАЛ /, взятых на наборах значений её аргументов, расположенных в порядке следования задаваемых ими с помощью -нумерации чисел. Назовём альтернированием alt(a) булевого набора а минимальное число отрезков постоянства, на которые он распадается, уменьшенное на единицу, а альтернированием alt(/) ФАЛ f — альтернирование её вектора значений.
Назовём ФАЛ h ступенчатой, если alt(h) 1, и заметим, что любая такая ФАЛ является либо монотонной, либо антимонотонной. Для целого числа і, О і 2П, назовём ФАЛ h,{xh ..., хп) 1-ой монотонной ступенчатой ФАЛ по 67 рядка п, если hi(a) = 0 тогда и только тогда, когда ь {а) і. При этом ФАЛ hi будем считать 1-ой антимонотонной ступенчатой ФАЛ порядка п. Лемма 20 [54, лемма 1]. Для любого а Є В и целых п, і (п 2, 1 і 2п — 1) в классе формул над базисом % найдётся формула Т = Т }, реализующая г–ую ступенчатую ФАЛ1 Щ порядка п, для которой выполняются неравенства: S(J-) 2 log2n] — о-, {J7) п Г1ё2п1 +2 — 0". Доказательство. Построим формулы 7 ), структурная глубина которых удовлетворяет условию леммы, а сложность — более сильному условию: (rfj) 2Г1о&пЬ1 [log2n] + 2 - а. Проведём построение указанных формул индукцией по к (к = 1,2,...) для всех п из диапазона 2 п 2к. Базис индукции составляет случай, когда к = 1, в котором для единственно возможного п = 2 и каждого і Є {1, 2, 3} для реализации ФАЛ Щ, а Є В, доста (2) точно взять формулы Т;!, задаваемые равенствами: Т-(2) \/ Т-(2) Т-(2) J-[ { = Х\ V #2, "i 2 = ЖЬ І 3 = Ж1Ж2, т-.(2) - х.(2) - т-.(2) Пусть для натурального к искомые формулы построены при всех п таких, что 2 п 2к. Для доказательства индуктивного перехода достаточно построить требуемые формулы для любого п заключённого в пределах 2к + 1 п 2к+, то есть любого такого п, для которого log2n] = к + 1. (2.1) Заметим, что ФАЛ hi, 1 і 2П — 1, порядка п получается из ФАЛ hi22k+i_n порядка 2k+l удалением последних [2k+l — п) фиктивных переменных. Построим для п = 2к+1 и целого і, 1 і 22 — 1, формулу Т\ { , реализующую монотонную ступенчатую ФАЛ /г порядка п. Рассмотрим ФАЛ hi как ФАЛ, зависящую от Обозначение х, а Є В, традиционно понимается в следующем смысле: х = х, х1 = х. переменных группы х = (х , х"), где2 X = [Х\ , , Х2к+1) , Xі = [Х\, . . . , Х2к ) , ж" = (ж2й+1, , Ж2й+1)
В соответствии с разбиением переменных группы х на подгруппы х и х" представим число г в виде: г = 22Y + і", где целые і , і" принадлежат отрезку [0, 22 — 1] и не равны нулю одновременно. Искомую формулу Т\ I построим на основе следующего разложения ФАЛ щ: Ы(х) = hi +i(x ) V hi»(x")Kj (x ), где ФАЛ К (х ) представляет собой конъюнкцию тех и только тех переменных группы х , которые соответствуют единичным разрядам набора u kl(i ). Пусть і ф {0,22 — 1} и і" ф 0. По предположению индукции построим для N = 2к и каждого j Є {і ,і + 1,і"} формулу Т\л, для которой справедливы неравенства: IJ }) 2 fc - 1, K if) 2 _1ife + 1. (2.2) Построим, далее, формулу JCj, реализующую ФАЛ К+ на основе квазиполного3 дерева, составленного из элементов &, для которой выполняются соотношения: S()C ) /с, (tei ) 2 — 1. (2.3) Искомую формулу jj$ определим равенством Т І (х) = J \ii-\-\(% ) V J-\\Vi(х"))С (х ), которое в случаях, когда либо і = 0, либо і" = 0, либо і = 22 — 1, а і" ф 0, переходит в одно из равенств: J7}" ( ) = J\ i +i (% ) V J i J (х"), J7}" (х) = J-\ І (xr), J-ІІ (x) = 7-\_ 1{х")1С {х ). Традиционно, результат объединения групп переменных, получающийся приписыванием одной группы к другой, записывается как (х ,х"), а не как результат их конкатенации х . х". Везде далее объединение переменных надо понимать в описанном здесь смысле. 3Дерево называется квазиполным, когда глубина его листьев отличается не более чем на один. Для построенной формулы jj$, используя (2.1)-(2.3), получим: 5{J-ii) 2 к — 1 + 2 = 2-(& + 1) — 1 = 2 log2n] — 1, (J ii) 2-(2 А; + 1) + 2 —1 = 2 (A; + l) + 1 2 og2n log2n] + 1. Инвертируя с помощью функционального элемента формулу T f, получим формулу JQ І , реализующую антимонотонную ступенчатую ФАЛ hi такую, что 5(J-Q]) 2 log2n] , (J-Q]) 2 og2nl log2n] + 2. Лемма доказана. Лемма 21 [54, лемма 2]. Для целого п 2 и отличной от константы ФАЛ д, д Є Р2(п), найдётся реализующая g формула Т над стандартным базисом %, для которой справедливы неравенства: S(J-) 2 log2n] + [log2(alt( ))J + 1, (2.4) З (J-) - п [log2n] dlt(g). (2.5) Доказательство. В случае п = 2 в справедливости данной леммы нетрудно убедиться непосредственным перебором. Пусть п Зид- это число отрезков постоянства ФАЛ g из условия леммы. Если g — ступенчатая, то неравенства (2.4) и (2.5) вытекают из леммы 20, в противном случае q 3.
Реализация мультиплексорных ФАЛ
Для каждого указанного і рассмотрим множество G всех тех ФАЛ из Р2(т), которые на множестве наборов 5j, 1 j d и j 7 і, равны otij. Положим по опре делению G = G U U G . Нетрудно убедиться, что теперь равенство (2.100) имеет место для любой ФАЛ д, если в качестве ФАЛ Qj, 1 j d, выбрать ФАЛ из которая на Sj совпадает с ФАЛ д 0 ctjj, а в случае d р положить ФАЛ gi, d i p, равной той единственной ФАЛ, которая составляет множество Gw. Следовательно, построенное таким образом по разбиению А множество G является р-универсальным порядка т. Мы доказали следующее утверждение.
Утверждение 33. Для любой существенной ФАЛ р(уи ...,ур) и любого разбиения А = (#i,..., dp) куба Вт на р компонент существует р-универсальное множество G ФАЛ из Р2{т) мощности не превосходящей 2 + + 2 .
Замечание. Как мы видели, утверждение 33 применимо и, когда количество компонент d разбиения А меньше р. В этом случае необходимо формально считать недостающие комоненты пустыми: 6d+1 = 6Р = 0. Соответствующие пустым компонентам множества G d+1\ ..., G& содержат каждое по одной ФАЛ.
Второе понятие, которое необходимо нам для дальнейших построений, - это понятие регулярного множества двоичных наборов. Пусть т q, назовём множество наборов 6 С Bq m-регулярным, если \6\ = 2т и все префиксы длины т наборов из 6 различны. Регуляное множество наборов 6 интересно тем, что любая ФАЛ из p2(q) на нём совпадает с некоторой ФАЛ из р2(т), если рассматривать р2(т) как множество всех ФАЛ из p2(q) с несущественными переменными Хт+\, ..., xq. При этом некоторые ФАЛ из р2(т) совпадают на 6 с переменными х\,..., xq или их отрицаниями, а именно: этим свойством обладают ФАЛ системы ф Є P29_m(m), такой что двоичный набор 7 = а Р, где а Є Вт, /З Є Bq m, принадлежит 5 тогда и только тогда, когда ф(а) = (3.
В связи с указанными свойствами регулярных множеств дадим следующее определение о моделировании ФАЛ. Пусть G — множество, содержащее ровно А ФАЛ из Р2(т), а А = (до, , 29-m-i) —разбиение куба Bq на т-регулярные компоненты. Скажем, что разбиение А моделирует ФАЛ множества G с помощью переменных или их отрицаний, если для любого j, 0 j 2q-m -1, любая ФАЛ д из G совпадает на 6j с некоторой переменной х\,..., xq или её отрицанием. При этом компонента 53 считается хорошей компонентой разбиения А относительно множества G в том случае, когда любая ФАЛ д из G совпадает на 6j с некоторой переменной х\,... ,xq в чистом виде (без отрицания). Если компонента не является хорошей, то мы называем её плохой. Справедливо утверждение (см. по этому поводу также [30, 2]).
Утверждение 34. Для любых натуральных чисел т, X, q, связанных соотношением т + А q, и любого множества G ФАЛ из Р2(т) мощности X найдётся разбиение А = (#о,... , #2 г--і) куба Bq на т-регулярные компоненты, моделирующее ФАЛ множества G с помощью переменных или их отрицаний, и такое что компонента 6v0y (З Є Bq m, является хорошей относительно G, когда число нулей в наборе /3 не меньше А.
Доказательство. Будем обозначать через р(а) количество единиц в записи двоичного набора а -так называемый вес набора а. Пусть двоичные наборы а, 7 имеют одинаковую длину и пусть 0 п р(а), тогда обозначим через (7й)п двоичный набор длины п, который составлен из тех расположенных в порядке возрастания их номеров п разрядов набора 7, для которых соответствующие им (по номерам) разряды набора а равны единице, то есть если а = (а\,..., as), 7
Приступим к доказательству. Вместо множества G из условия будем рассматривать соответствующую ему систему попарно различных ФАЛ ф = (ф\,... ,ф\) из Р}(т). Пусть г 1и двоичный набор /З Є Bq m разбит на последовательно (слева направо) расположенные и составленные из подряд идущих символов (непустые) наборы /Зі,..., (Зг, то есть: (3 = (3\ . . (Зг, где (3j Є Aj, Aj 1, для всех j, 1 j г. Если формально считать, что /30 - единичный (состоящий только из единиц) набор длины А, то число г и указанное разбиение набора /3 однозначно определятся величиной А и двумя условиями: 1) для любого j, 1 J г — 1, (ненулевая) величина Aj равна p{(3j-\); 2) если набор (Зг-\ отличен от нулевого, то Аг р{(Зг-\). Пусть теперь 7 Є Bq, тогда построенное разбиение набора (3 индуцирует для 7 разбиение вида 7 = 7о -7i -Ъ, где 7j Вх? для всех j, 0 j г, а Ао = т. Охарактеризуем т-регулярное множество 6 , С Bq, конструируемое для заданных ф, /3, следующим критерием: набор 7 входит во множество 6 , тогда и только тогда, когда 1) 71 Ф А = Ф(їо); 2) для любого j, 2 j г, если набор /3j-\ отличен от нулевого, то 7j 0 Pj = (7.7-1 $j-\\$j-\)\-; 3) если /3r_i — нулевой набор, то 7г = А. мм , так Отметим важный факт, заключающийся в том, что система множеств = ( іу(в))в вч-т образует разбиение Bq на т-регулярные компоненты. Действи тельно, так как \5о\ + + #2 г-т-і = 29, то достаточно показать, что А —покры тие16 Bq. Будем считать набор 7 Є Bq произвольным и подберём к нему такой набор /З Є Bq m, что 7 Є Кф). Последовательно определим числа Лі,Л2,... и двоичные наборы /Зі Є Вх\/32 Є Вх\ ..., исходя из следующей пошаговой проце дуры. На первом шаге положим Лі = Л, (3\ = (7о) Ф 7і и завершим построение, полагая г = 1, если g = т + Л. Рассмотрим шаг с номером j 2. Пусть для краткости S(j) = Ло + Лі + + Xj-i, где как и прежде Ло = т. Если p(f3j-i) = О, то определим г = j, Xr = q — S(r), /3r = 7r и завершим построение, в противном случае положим Xj = minjg — S(j), p(/3j_i)} и /3j = (7j-i 0 /3J_I/3J_I)A- 0 7j. По сле этого, если S(j + 1) q, то переходим к следующему шагу, иначе завершаем построение, полагая г = j. Вследствие того, что на каждом шаге величина S(j) увеличивается не менее чем на единицу, указанная процедура завершится не более, чем через (q — т) шагов, при этом по построению 7 Є $vCe), что и требовалось. Утверждение доказано.
Уточнённые оценки и оценки высокой степени точности функций Шеннона для глубины и задержки, а также глубины и задержки мультиплексорных ФАЛ в базисах специального вида
Доказательство. Для того, чтобы построить формулу из условия, достаточно модифицировать формулу Ф, построенную при доказательстве теоремы 12. Рассмотрим натуральное число т = т!{п) в качестве нового параметра и, используя лемму 13, выбрав в этой лемме в качестве т число 2т /s, построим формулу Ф , ранг р , глубина и сложность t которой удовлетворяют соотношениям: 2m /s р аи 2т /s, (2.191) )(Ф ) = щ{т — log2 s) ± 0(1), (2.192) tf = e(2 m /s). (2.193)
Пусть простой шаблон подключений S состоит из единственного функционального элемента г, на котором достигается приведённая сложность базиса Щ. Предположим, что Г[5] Тф, и обозначим через тг положительную величину (T[S] — Гф). Выберем с помощью леммы 9, положив в ней m равным 2 п Тг, 114 абсолютную формулу Ф" Є [S]. Нетрудно показать, что функция c(t) в разложении (1.41) однородного простого шаблона подключений, не являющегося циклическим, имеет асимптотику вида c(t) CQ. В частности, это справедливо для шаблона S, поэтому из замечания к лемме 9 следует, что для ранга и глубины формулы Ф" выполняются соотношения: 2С(п)/тг щф, 2с(п)/тг + 0 (2.194) )(Ф ) = ((п) ± 0(1). (2.195) С другой стороны формула Ф" целиком составлена из функциональных элементов одного типа, поэтому: (Ф") = . (2.196) кг — 1
Пусть абсолютная формула Ф получается из формулы Ф , подстановкой вместо её первых 2т /s переменных формулы Ф", записанной каждый раз для новых переменных, тогда вследствие (2.191)–(2.196), с учётом того, что р = Lr/(kr — 1), для ранга р, глубины и сложности формулы Ф вместо соотношений (2.181), (2.182), (2.183) будут соответственно выполняться соотношения: 2 m /s р (2 m /s) (і + о(1)), (2.197) 1)(Ф) = т (т — log2 s) + ((п) ± 0(1), (2.198) от от Ь(Ф) = Lr 1{Ф") + OCt ) = f)y$— (1 + о(1)) + 0(2т /s), (2.199) s s в которых через т обозначена величина (т + (С(п)/тг)). Далее, переписываем условие (2.106) с учётом (2.197) в виде: от т (1 + о(1)) п, (2.200) s и, следуя доказательству теоремы 12, продолжаем с очевидными изменениями продиктованными соотношениями (2.198), (2.199). В результате получаем вместо соотношений (2.188), (2.190) соответственно соотношения: D(J-) = щ{п — log2 s) + ((п) ± 0(1), (2.201) ЦТ) = рщо(1)) + 0(2n"c(n)/TVs) + 0(q 22q-m) + 0(2n"m). (2.202) s 115 Выбор параметров т , s, определяемый равенствами т = [2 log2 [log2 п\ — ((n)/rr\, s = [log2 п — log2 log2 п\ — 3, удовлетворяет для всех достаточно больших п условиям (2.200), (2.115), (2.121), (2.189), а из соотношений (2.201), (2.202) при указанных значениях параметров вытекают соотношения (27), (28). Теорема доказана. Замечание. Заметим, что в тех случаях, когда шаблон подключений S из доказательства теоремы 13 доставляет одновременно и приведённую сложность и приведённую задержку базиса Щ (T[S] = тф, pr = p%), утверждение теоремы 13 справедливо для ((п) = 0, а для сложности формулы Т также справедлива оценка (22). В этих случаях в качестве формулы Ф достаточно взять формулу Ф , для которой вместо (2.191), (2.192) выполняются соответственно (2.197), (2.198), а вместо (2.193) соотношение:
Результаты, полученные в диссертации, относятся к задаче синтеза дискретных управляющих систем в её классической массовой постановке. В качестве класса управляющих систем изучаются схемы из функциональных элементов и формулы над произвольным конечным полным базисом. Основным параметром изучения являются параметры, характеризующие скорость срабатывания рассматриваемых систем. К таким параметрам относятся глубина и задержка схем, которые оптимизируются на уровне соответствующих функций Шеннона. В работе также представлены результаты, касающиеся задачи индивидуального синтеза для мультиплексорных функций алгебры логики на уровне определения асиптотиче-ских оценок глубины и задержки этих функций.
В диссертации предложены обобщения классического параметра глубины схем, которые идут в двух направлениях. Первое из них связано с расширением понятия глубины в сторону учёта ёмкостных характеристик отдельных входов, выходов функциональных элементов, а также их межэлеметных связей. Второе рассмотренное обобщение понятия глубины приводит нас к задержке, которая принимает во внимание функциональные характеристики элементов и позволяет учитывать такие эффекты, связанные со скоростью срабатывания вычислительных устройств, которые возникают при работе устройства на различных поступающих на его входы сигналах. Предложенное в работе понятие задержки является попыткой «комбинаторного» описания процесса распространения сигнала в схеме через множество её главных цепей в отличие от более динамического понятия задержки по Храпченко [31–33].
В первой главе получены нижние оценки рассматриваемых функций Шеннона и функционалов сложности мультиплексорных функций. Здесь предложен общий подход к решению проблемы через анализ асимптотического поведения так называемой ранговой функции базиса, который для двух классов базисов, характеризующихся специальными видами распределений глубин функциональных элементов, позволяет эффективно определять приведённую глубину базиса — константу, задающую асимптотическое поведение функций Шеннона для глубины и задержки, а также глубины и задержки мультиплексорных функций. При этом эффективное задание указанной константы оказывается необходимо и для построения эффективных методов синтеза схем асимптотически достигающих нижние оценки соответствующих функций Шеннона и функционалов сложности. Для базисов, не попадающих ни в один из упомянутых классов, предложенный подход позволяет производить оценки величины приведённой глубины базиса.
Вторая глава посвящена получению верхних асимптотических оценок функций Шеннона для глубины и задержки, глубины и задержки мультиплексорных функций. Здесь представлены алгоритмы построения соответствующих схем, которые распространяют известные асимптотические оценки высокой степени точности на обобщённую модель глубины для базисов, обладающих специальным распределением глубин элементов. При этом на базисы общего вида распространяется асимптотически оптимальный метод синтеза, который даёт схемы одновременно оптимальные как по глубине так и по обобщённой структурной сложности. В этой же главе описывается новый приём опережающей подачи управляющих сигналов, который позволяет достигать оптимальных значений задержки в основной для этого параметра части схемы, что делает возможным использование известных асимптотических методов синтеза схем для получения схем одновременно асимптотически оптимальных как по задержке, так и по обобщённой структурной сложности. Этим самым выявляется интересная особенность определённого нами функционала задержки схем, при которой определяющими на уровне асимптотики становятся минимальные (при рассмотрении всевозможных входных сигналов) параметры рассматриваемого функционала.