d9e5a92d

Реализация некоторых “управляющих” систем функций алгебры логики

и называется функцией Шеннона для класса СФЭ над базисом Б. Функция Шеннона характеризует сложность самой "сложной" ФАЛ от БП ад,... ,хп в классе СФЭ над базисом Б.
Вместо сложности L(E) СФЭ Е можно рассмотреть ее глубину D(E), а затем аналогичным образом определить глубину Dj^(F) для системы ФАЛ F в базисе Б и ввести функцию Шеннона D jy(n). Можно рассмотреть "взвешенную" сложность (глубину) СФЭ, когда при подсчете сложности (соответственно глубины) каждый ФЭ учитывается со своим коэффициентом, и т. п. Можно рассматривать подобные функционалы сложности для подклассов класса СФЭ (класса формул, класса ДНФ и т. д.).

В дальнейшем мы, как правило, будем рассматривать оптимальную по сложности реализацию ФАЛ в классе СФЭ над базисом Д. В связи с этим индекс Б = Д будем опускать.
Для решения задачи синтеза СФЭ можно использовать переборный алгоритм, который просматривает все схемы сложности 1,2,3,... до тех пор, пока не найдет схему, реализующую заданную систему ФАЛ. Следует отметить, что трудоемкость этого метода синтеза очень быстро растет с ростом числа переменных гг, и что при го 5 он становится практически неприменимым.
С другой стороны, всегда можно использовать метод синтеза, основанный на моделировании совершенной ДНФ. Следующее утверждение непосредственно вытекает из (4.4).
Лемма 4Л. Для любой ФАЛ /(ад,..., хп) существует СФЭ, реализующая / со сложностью не более, чем п ¦ 2П+1.
Следствие. Ь{п)п ¦ 2П+1.
Замечание. Во многих случаях после построения СФЭ по лемме 4.1. целесообразно использовать операцию удаления эквивалентных вершин для перехода к соответствующей строго приведенной СФЭ.

§ 5. Реализация некоторых "управляющих" систем функций алгебры логики в классе СФЭ


Рассмотрим примеры решения задачи индивидуального синтеза СФЭ синтеза СФЭ для систем ФАЛ, которые часто встречаются в практике проектирования дискретных управляющих систем и для которых хотелось бы иметь более простые схемы, чем схемы, построенные по лемме 4.1.
Для множества А и любого натурального п через (А)п или просто Ап обозначается, как обычно, гг-я декартова степень множества А, т. е. множество наборов (слов, систем) длины п с элементами из А. Для набора (3, (3 ? через Д[г], где 1 і п, обозначается его /-и элемент, т. е. [3 = (Д[1],..., ft[n]). Если а ? Вп, то число Е"=і сф'] ¦ 2п~\ т. е. число, двоичная запись которого совпадает с а, называется номером а и обозначается через |о.'|.
Пусть Р'2(п), п = 1.2..... множество всех ФАЛ от БП
х\, х-2,..., хп, а РД(гг) его т-я декартова степень, т = 1.2.....
і. е. множество систем из т ФАЛ от БП х\, Х2,..., хп. Определим некоторые "управляющие" системы ФАЛ и рассмотрим реализующие их СФЭ.

При этом мы часто будем давать одно и то же название как самой системе ФАЛ, так и СФЭ, которая ее реализует, добавляя к нему в случае необходимости слово "функциональный", если речь идет о системе ФАЛ, и слово "схемный", если речь идет о схеме.
Система ФАЛ Q,, из Р-{п) такая, что при всех /. і = 1.2.....2.
справедливо равенство:
Qn[i] = хТ1 ¦ ... ¦ (5.1)
где а = (егі,..., ап) ? Вп и |ег| = г 1, называется (функциональным) дешифратором порядка п. Это связано с тем, что на любом наборе а, а ? Вп, значений БП ... ,хп ровно одна из ФАЛ системы Qn ФАЛ с номером |а| + 1 обращается в 1.
Функция рп от (входных) БП хі,..., хп, г/о, у\,, У2п-і такая, что при всех а, а ? Вп, и і. і ? В1 . имеет место равенство:
/гДсц Д) = Д[г],


где (і 1) = Н, называется (функциональным) мультиплексором порядка п. Если рассматривать БП х\,...,хп как "адресные" БП, а БП г/о, г/і,... , г/2_і как "информационные" БП, то значение мультиплексора уп равно значению той его информационной БП, номер которой поступил на адресные БП /іп. Легко убедиться в том, что для ФАЛ /іп справедливо представление:
2
цп{хі,...,хп,у0,...,у2п-і) = V Qn[i] ¦ Уі-1- (5.2)
і=і
Под (функциональным) шифратором порядка п понимается любая система из п ФАЛ от входных БП xq, ад,..., х2п_\ такая, что каждому входному набору а, в котором равна 1 только одна БП xj. О j 2" 1, она сопоставляет выходной набор j3,j3 Е Вп, для которого \{3\ = j. Тем самым, шифратор вырабатывает "адрес" той входной БП, которая равна 1, если другие входные БП принимают при этом нулевые значения.
Будем называть схемным дешифратором, мультиплексором или шифратором любую СФЭ, которая реализует соответствующую систему ФАЛ.
Обозначим через ?„ систему длины 22 из всех различных ФАЛ множества Р2(п), в которой столбец значений ФАЛ ?„ [г], 1 і 22, рассматриваемых! как двоичный набор длины 2", имеет номер (г 1). Систему ?„ будем называть универсальной системой ФАЛ порядка п, а любую СФЭ, которая ее реализует, универсальным многополюсником порядка п.
Отметим, что дешифратор, мультиплексор и шифратор часто используются в качестве составных частей схем записи и чтения информации по заданному адресу.
Рассмотрим теперь вопросы, касающиеся сложности описанных
схем.
При построении "сложных" СФЭ из более простых мы будем опираться на понятие подсхемы и принцип эквивалентной замены (см. [9]). СФЭ Е/ называется подсхемой СФЭ Е, если множество ее вершин (дуг) является подмножеством множества вершин (соответственно дуг) Е, а все те вершины Е', из которых в Е выходит хотя бы одна дуга, не принадлежащая Е', или которые являются выходами Е, являются выходами Е'.

При этом предполагается, что все дуги в Е/ имеют те же номера, что и в Е, а все вершины Е/ имеют те же ФС, что и в Е. Принцип эквивалентно!! замены для СФЭ вытекает из определения их функционирования и состоит в том, что если подсхему Е' СФЭ Е заменить эквивалентно!! ей СФЭ Ем, то полученная в результате СФЭ Е будет эквивалентна СФЭ Е. В связи с этим подсхемы, которые не имеют общих внутренних вершин, можно рассматривать как (многовыходные) макроэлементы.
Лемма 5.1. Для любого натурального п существует схемный дешифратор порядка п, имеющий сложность не более, чем п ¦ 2п+1, и глубину не более, чем ]logro[+l.
Доказательство. Для построения искомого дешифратора достаточно каждую ФАЛ системы Qn реализовать по ее совершенной ДНФ (5.1) на основе ^-ярусного дерева из п ФЭ , где d =] log гг[ (см. рис.

5.1).



Следствие. L(Qn)n ¦ 2п+1.
Следующее утверждение доказывается, по существу, применением к построенному в лемме 5.1 схемному дешифратору операции удаления эквивалентных вершин (см. х4).
Теорема 5.1. Сложность минимального схемного дешифратора порядка п равна
2п + 0(п-2п/2).
Доказательство. Поскольку любой дешифратор порядка п при п2 реализует систему из 2 ФАЛ, отличных от БИ. то в нем должно быть по крайней мере 2" вершин, отличных от входов.

Следовательно, сложность любого дешифратора порядка го, го2, в классе СФЭ не меньше, чем 2".
Разобьем набор входных БП х = (ад,..., хп) на поднаборы х' = (ад,..., Xk) и хи = {xk+i, - - - , хп), где к некоторый параметр и 1 к (п 1). Пусть Q' и Q функциональные дешифраторы порядка к и (го к) от БП хг и х, а Е/ и соответствующие им схемные дешифраторы, которые построены по лемме 5.1. Легко видеть, что любую ФАЛ Qn[i], 1*2", можно представить в виде
Qn[i] = Q'\j]-Q[l\, (5.3)
где і = 2n~k(j 1) + I и 1 j2*, Ш-*. Дешифратор Е порядка го от БП х содержит дешифраторы Е', Ем в качестве подсхем и реализует каждую ФАЛ Qn[i], 1*2", с помощью одного ФЭ , входы которого присоединены к выходам Е/ и Ем (см. рис.

5.2) в соответствии с (5.3). Из построения Е следует, что
L(E) = 2 + L(Yj') + L(Yj)2n + п +к ¦ 2к+1 + (п - к)2п~к+1,
и поэтому при к = [гг/2] получим:
L(E)2 + О(п ¦ 2п/2).
Теорема доказана.
Следствие 1. Построенный дешифратор порядка п имеет глубину не больше, чем ] log n[+2.
Следствие 2. Если в качестве дешифраторов Е/ и Ew взять дешифраторы, уже построенные по теореме 5.1, то полученный дешифратор порядка п будет иметь сложность
2 + 2[/2] + 2]п/2[ + О (гг ¦ 2п/4)2 + 3^2п/2 + 0(гг ¦ 2п/4) гг поэтому
2L(5„) = 2 + М2/2 + о(„. ¦ 2'4).



Рис. 5.2
Лемма 5.2. Для любого натурального п существует схемный мультиплексор порядка п, который имеет сложность не более, чем
3-2 + 0(п-2/2).
Доказательство. Построим ехемнвій мультиплексор Е в соответствии с (5.2) на основе дешифратора Ем порядка гг, который является его подсхемой.

Для этого каждый выход Е?? и соответствующий ему информационный вход Е присоединим к входам ФЭ , а затем про-дизъюнктируем выходы всех таких ФЭ . Если дешифратор Е?? взять из теоремы 5.1, то полученный таким образом мультиплексор Е будет искомым.
Лемма доказана.
Следствие. Построенный мультиплексор порядка п имеет глубину не больше, чем n+] logn[+3.
Теорема 5.2. Существует схемный мультиплексор порядка п, имеющий сложность
2п+1 + 0(2п/2).
Доказательство. Разобьем набор х = (ад,..., жп) адресных БП мультиплексора уп на поднаборы х' и хтк же, как это было сделано при доказательстве теоремы 5.1, а набор у = (г/о,..., У2п-і) его информационных БП на поднаборы у^1\ ..., г/(2 ) длины 2n~k каждый, где уС)Щ = у(_г при і = 2n~k(j 1) + I и всех j,l таких, что lj’2*, H2n~k. При этом из (5.2), (5.3) следует, что:
2* /2п~к
?п(х,у) = ? Q![j] ( v Q[l\ ¦ уі])Щ
і=1 V і=і
и поэтому
/Іп(х, у) = /ік(х\ Уп-к(х, у{1)), - - - , Уп-к(х, у{2к)))- (5.4)
Рассмотрим мультиплексор Е, который реализует уп по формуле (5.4). Для каждого /. / = 1,... ,2*, Е содержит в качестве подсхемы мультиплексор EJ порядка (n к) от БП х, у^\ причем выходы этих мультиплексоров подаются в соответствии е (5.4) на информационные входы мультиплексора Е/ порядка к с адресными БП х’ (ем. рис.

5.3).
Если мультиплексоры Е? n EJ. / = 1.....2/\ построить в соответствии
е леммой 5.2, а затем перейти от СФЭ Е к эквивалентной ей строго приведенной СФЭ Е (ем. х4), то при к = [гг/2] мы получим искомый мультиплексор. Действительно, из доказательства леммы 5.2 следует, что все мультиплексоры EJ, j = 1,..., 2*, имеют общий дешифратор Tj порядка (го к), и поэтому
L(E)L(E/) + 2n+l + L(E,,)2n+1 + 0(2n/2)
в силу теоремы 5.1.
Теорема доказана.
Следствие. Ь(цп)2П+1 + 0(2/2)
Наряду е дешифратором Qn и мультиплексором уп порядка п иногда рассматривают также полудешифратор Qn порядка п е входными БП ад,..., агп и полу мультиплексор (іп порядка п е входными БП ад,..., хп, г/о,..., !)¦)¦¦ -1 і - такие, что
2?г 1_J
/Д, = V yjQn[j + 2" 1 +1], Qn[i\ = Qn[2" 1 + Ф
3=0
где / = 1.....2 С Заметим, что при х\ = 0 имеют место равенства:/А 0, [/] 0.
Аналогично доказаннвім ввіше утверждениям устанавливаются о цен-
Ч4,) = 2-1 + 0(2Д
Ц/?)2 + 0(2-'2).
Перейдем теперв к построению шифраторов. Определим систему ФАЛ Dn длинві п от БП х = (xq, ад,..., Х2-і) так, что
Д,.И = V *М (5.5)
(Т(оі
для всех /. і = 1.....п. Заметим, что D„[i) = 1 тогда и толвко тогда,
когда среди БП xj. / = 0. 1.....2 1, номер которвіх имеет единицу
в /-М разряде своей двоичной записи, еетв хотя бві одна БП, раная единице. Это означает, что система ФАЛ Dn является (функционалв-
нвім) шифратором порядка п. Если для каждого /, / = 1...../к ФАЛ
Dn[i\ реализоватв формулой (5.5), то мві получим ехемнвій шифратор сложности гг(2"-1 1), так как в каждую дизъюнкцию (5.5) входит ровно половина БП набора х. Следовательно, доказано утверждение:
Лемма 5.3. Для любого натурального п существует схемный шифратор порядка п, который имеет сложность не более, чем п ¦
Г)п1
Более "экономный" схемный шифратор может быть построен с помощью рекурсивного разбиения множества входных БП пополам.
Теорема 5.3. Существует схемный шифратор порядка п, сложность которого не больше, чем 2п+1.
Доказательство. Разобьем набор БП х = (xq, ..., Ж2_і) на поднаборы х! = ((Со, . . . , Ж2-І_і) И х = ((С2-1, - - - Л2п-і).

Пусть D' и D функциональные шифраторы порядка (го 1) от БП х' и х, а Е/ и Ew соответствующие им схемные шифраторы. Из (5.5) следует, что
("'-!) І=1
и для всех г, г = 1,..., (гг 1). Следовательно, из шифраторов Е/ и ЕЕ а также (2п 2) ФЭ V на основе (5.6)-(5.7) можно построить шифратор Е порядка го, для которого: Используя неравенство (5.8) рекурсивно и полагая, что L(D\) 1, так как D\ состоит из БП х\, получим:
L(E)2(ro - 1) + 4(го - 2) + ... + 3 ¦ 2_3 + 2 ¦ 2-2 + Т~1 =
= 2 t1 + f 2 + ¦ ¦ ¦ + Ут( - 1)) 2-1 (? Дт) =
ОО ОО 1
_ syn1 \ - \ - х _ суп+Х
" 2-j 2.J пі-і "
s=lt=s z
Теорема доказана.
Следствие. L(Dn)2п+1.
Теорема 5.4. Минимальный универсальный многополюсник порядка п имеет сложность 22 го.
Доказательство. Нижняя оценка следует из того, что универсальный многополюсник порядка п реализует систему из 22 п ФАЛ, отличных от БП (см. доказательство теоремы 5.1). Для получения верхней оценки построим универсальный многополюсник Е по совершенным ДНФ всех реализуемых ФАЛ (см. лемму 4.1), а затем перейдем от него к эквивалентной строго приведенной СФЭ Е/ (см. §4).

Заметим, что число вершин СФЭ Е', отличных от входов, не больше, чем число различных ФАЛ от БП ад,, хп, отличных от этих БП. Следовательно,
L(E')22 - го.
Теорема доказана.

Реализация некоторых "арифметических" систем ФАЛ в классе СФЭ


Рассмотрим теперь некоторые "арифметические" системы ФАЛ и построим реализующие их СФЭ.
Системы 5„, Мп и Wn, состоящие из (го + 1), 2го и го ФАЛ от БП х = (ад, ..., хп),у = (г/і,, г/п) соответственно, такие, что
\Sn(x,y)\ = |Д + |г/|, \Мп{х,у)\ = |Д ¦ |г/|, и, если |ж||г/|, то
\Wn(x,y)\ = |Д - |г/|,
называются (функциональным) сумматором, умножителем и вычи-тателем порядка го соответственно.
Система С„, состоящая из (го + 1) ФАЛ от БП х = (ад,... , ад), такая, что значение \Сп(х) \ равно числу единиц в наборе ад называется (функциональным) счетчиком порядка го.
В [8] приведен сумматор порядка го, имеющий сложность 9го 5. Мы построим такой же сумматор несколько иначе.
Теорема 6.1. Существует схемный сумматор порядка го, имеющий сложность 9го 5.
Доказательство. Для го = 1 сумматор Еі показан на рис.

4.4. На рис. 6.1.а показана СФЭ Е/ сложности 9, которая реализует систему ФАЛ S' от БП х, у и q' такую, что
\S'(x, y, q’) \ = x + y + q’,
т. е. реализует сложение трех одноразрядных чисел. Действительно, на выходе z-j СФЭ Е/ реализуется ФАЛ х у /'. а на выходе : | единица появляется только тогда, когда либо х = у = 1. либо х ® у = qr = 1, т. е. на выходе z\ в СФЭ Е' реализуется ФАЛ
ху V (х Ш y)q' = ху V xq' V yq' = h(x, г/, q').
Схемный сумматор Е„ порядка го с входными БП ад,... ,xnj уі,... ,уп и выходными БП zq, zi,..., zn можно построить из сумматора Е„_і порядка (го 1) с входными БП ад,..., xnj г/2,... , уп и выходными
БП ‘.|. :-2.....а также одной СФЭ Е/ так, как это показано на
рис. 6.2.

Заметим, что переход от сумматора Е„_і к сумматору Е„ моделирует сложение го-разрядных чисел в два этапа: на первом этапе складываются числа, образуемые (го 1) младшими разрядами, а на втором этапе складываются старшие разрядві и перенос, возникший на первом этапе. Очевидно, что
Ь(Е„) = 9го - 5.
Теорема доказана.
Следствие. L(Sn)9n 5.
Замечание. Если схему Е/ на рис.

6.2 заменитв на схему Ем, показанную на рис. 6.1.6, мві получим (ехемнвій) квазисумматор порядка го, го2, которвій имеет сложности 9п 9 и правилвно екладвівает го-разряднвіе двоичнвіе числа, каждое из которвіх не превосходит 2п~1. Теорема 6.2. Существует схемный вычитатель порядка п, имеющий сложность не больше, чем Иго 5.
Доказательство. Заметим, что
\х\ = 2 1 |ж|,
где х = (жі,..., хп), х = {хі,... , хп), и поэтому
Wn(x,y) = \х\ - \у\ = 2п -1 - (2п - 1 - \х\ + |2/|) = Sn(x, y)
Следователвно, ехемнвій ввічитателв порядка го может бвітв получен из схемного сумматора порядка го в резулвтате инвертирования входов его первого слагаемого, а также всех его ввіходов, и имеет сложности не болвше, чем Нго 5.
Теорема доказана.
Замечание. Из построенного ввічитателя в резулвтате "поднятия" отрицаний, приеоединеннвіх к ввіходам z-j ехемві Е/ или Ej в соответствии е равенствами
и V tv.
где и и ш выходы ФЭ и V СФЭ Ej (ем. рис. 4.4.6), можно получить вычитатель сложности не больше, чем Юго 4.
Теорема 6.3. Существует схемный счетчик порядка п, который имеет сложность не более, чем 9-2".
Доказательство. Счетчик Еп порядка п е входными БП х\,..., х-2 и выходными БП , zn.|_і можно построить из счетчика
Е„_і порядка (п 1) е входными БП х\,.., Ж2-і и выходными БП z[,..., z!n, такого же счетчика Еп_і е входными БП Ж2-і-|_і,..., х-j и выходными БП z,..., z, а также квазиеумматора (ем. замечание к теореме 6.1) Е порядка п е входными БП і\.....z'n, zr{,..., zun и выход
ными БП z\,..., zn+i (ем. рис. 6.3), поскольку на выходах счетчиков Е„_і числа, большие, чем 2П_1, не позволяются.
В силу замечания к теореме 6.1 квазиеумматор Е можно построить со сложностью не больше, чем 9гг 9, и поэтому
L(E)2L(E;) + (9п - 9) (6.1)
Используя неравенство (6.1) рекурсивно и полагая, что L(Ej) = 4, так как Сі[1] = х\ ¦ х-2,Сі\2] = х\ ® х-. то есть С\ = Si, получим
L(E„)9(n - 1) + 18(гг - 2) + ... + 9 ¦ 2п~2 + 4 ¦ 2п~1 Следовательно (ем. выкладки в конце доказательства теоремы 5.3),
Ь(Е„)9 ¦ 2
Теорема доказана.
Следствие. L(Cn)9 ¦ 2п.
Хі Х2п-і *2n-1+l *2
Замечание. В общем случае счетчик, то есть схема е п выходами, на которых появляется двоичная запись числа единиц в наборе значений входных переменных, может иметь N. 2п~1 N 2", входов.

Такой счетчик можно построить из "стандартных" счетчиков, порядки которых соответствуют номерам единичных компонент набора а, a G Вп, такого, что |а| = N. и не более чем (го 1)-го сумматора порядка го. Каждый из стандартных счетчиков вычисляет число единиц в своей части набора из N переменных, а сумматоры складывают числа, появившиеся на ввіходах счетчиков.

Сложности построенной схемві не превосходит, очевидно, 9(Л' + гг2).
Рассмотрим теперв сложности умножителя Мп для умножения двух неотрицателвнвіх n-разряднвіх двоичнвіх чисел X = \(х1,х2, ...,хп)\ и Y = I (г/і, г/2, - - - , Уп)\- Так как X 2п и Y 2, то XY 2'2п и для представления результата требуется не более 2п выходов. Обозначим через Ьм{п) наименьшее возможное число элементов в умножителе Мп.

Очевидно, что Lm{ 1) = 1, так как умножение 1-разрядных чисел осуществляет элемент конъюнкция.
Утверждение. Существует СФЭ для умножения п-разрядного числа X на 1-разрядное число у с числом элементов п.
Действительно, если X = |(жі, х2, . . . ,хп)\ и Ху = Z =
I(zh z2,..., zn)I, то :/=.- /// для всех г = 1,2,..., п.
При умножении двух гг-разрядных чисел X и Y "в столбик" надо п раз умножить X на 1-разрядное число (всего п2 конъюнкций) и затем п 1 раз сложить числа длиной не более 2п. Такой алгоритм (схема) имеет сложность по порядку п2.

Следующая теорема показывает, что алгоритм умножения "в столбик" не оптимален по порядку.
Теорема 6.4 (Карацуба А. А. [4]). Существует такая константа с, что для всех п Ьм(п)сп]о2^.
Докажем сначала несколько вспомогательных лемм.
Лемма 6.1. Существует константа с\ такая, что Ьм{п + 1 )Ьм{п) + щп для всех п.
Доказательство. Пусть требуется перемножить два (гг +
1)-разрядных числа Х\ = |(т0, хи ..., хп)\ и Yx = |(г/0, г/ь ..., у„)\. Тогда обозначим |(жі, х2,... ,хп) \ = X и \(уі, г/2,..., уп) \ = Y. При этом Х\ = х02п + X, Yi = г/о2 + Y и
ХіЧ = хоУо 22 + (x0Y + г/0*)2 + А У.
Поэтому для вычисления X{Y\ достаточно использовать умножитель Мп для вычисления Л’У . 2п элементов для вычисления xqY и //уЛ’. 1 элемент для вычисления xqijq и 3 сумматора порядка не более 2п + 2, так как X{Y\ 22п+2.

Отметим, что числа ждг/о и XqY + у$Х надо подавать на сумматоры со сдвигом, одновременно подавая на младшие разряды 0. При этом 0 можно предварительно получить подсхемой с 2 элементами, реализующей xqXq = О.Так как сложность каждого сумматора можно сделать не более 9(2тг + 2), а сложность Мп равной Lм (гг), то сложность полученной схемы будет не больше чем Ьм{п) + с\п для некоторой константы с\. Лемма доказана.
Лемма 6.2 (основная). Существует константа с2 такая, что Ьм{2п)ЗЬм{п) + с2гг, для всех п.
Доказательство. Пусть нужно перемножить два 2гг-разрядных числа X и Y. Разобьем их на части, содержащие по п разрядов.

Тогда получим X = Л’|2 + Х-у- Y = У’|2 + У2. Отсюда
XY = ХХі'22 + (ВД + Х21'і)2 + X2Y2 =
= ХТІ22 + [(Xj + X2)(l'i + 1'2) - ХЗІ - Х2У2]2 + Х21'2.
Так как X\YiYХ^ХД. то при вычитании в квадратной скобке не возникает отрицательных чисел. Таким образом, схему для умножения XY можно построить, используя 2 оптимальных умножителя Мп с числом элементов Ьм{п) в каждом для вычисления X{Y\ и X-jYj. умножитель Мп.|_і с числом элементов Ьм{п+1) для вычисления (Хі + Х^Уі+Уф, 4 сумматора порядка не более 4п (так как XY 24') и 2 вычитателя порядка 2п + 2. В некоторых сумматорах опять на младшие разряды надо подавать 0, который реализуем подсхемой с 2 элементами: 0 = л.с. где х - любая входная переменная. Для построенной схемы Л/2„ с учетом леммы 6.1 получим для некоторых констант с и с2:
L(M-2n)2LM(ri) + LM(n + 1) + cn3LM(n) + с\п + сп = 3 LM(n) + с2п
Лемма 6.3. Существует такая константа с%, что для любого натурального к выполняется Ьм(2.к)сДк.
Доказательство. Положим f(k) = Ьм^ ^ ¦ Тогда из предыдущей леммы имеем
LM(2k) LM(2k~1) С2 2 k_i
3 з-1 3l3j
и/()/( - 1) + - 2) + + Іф-1
схему М.2к с числом элементов Ьм(2*), подавая на старшие 2к п вход-нвіх разрядов обоих сомножителей 0, предварителвно реализованнвій подсхемой из 2 элементов. Тогда имеем
LM(n)LM(2k) + 2с33* + 2 = ЗсзЗ*-1 + 2 =
= 3c32(i-1)lofe3 + 2 3c3nlogi3 + 2cnlofe3
для некоторой константві с.
В заключение отметим, что существует алгоритм Шенхаге и Штрассена для умножения двух тг-разряднвіх чисел, дающий оценку Ьм{п)сп log п log log гг, где с - некоторая константа и логарифмві можно ечитатв двоичнвіми.7.

Метод Шеннона для синтеза СФЭ.


Верхние и нижние оценки функции Шеннона и сложности
некоторых ФАЛ
В §4 бвіл рассмотрен простейший метод синтеза СФЭ для про-изволвной ФАЛ f(xі,..., ад), оенованнвій на моделировании ее совершенной ДНФ. Если при этом восполвзоватвся замечанием к лемме 4.1 и все конъюнкции вида хр ¦ ¦ хр реализоватв с помощвю одного
схемного дешифратора, то в силу теоремві 5.1 можно поетроитв СФЭ Е/, которая реализует ФАЛ /(ад,.., хп) и для которой
L(E/)2+1 + 0(n-2/2).
Рассмотрим еще более "экономнвій" метод синтеза СФЭ метод Шеннона.
можно построить
Теорема 7.1. Для любой ФАЛ /(ад,..., хп СФЭ Е/, которая реализует / и для которой



Содержание раздела