В.Б. Алексеев, С.А. Ложкин - Элементы теории графов, схем и автоматов (DJVU), страница 8

Мы построим такой же сумматор несколько иначе. Теорема 6.1. Существует схемный сумматор порядка и, име- лощиЬ слкнсостпь 9и — 5. Доказиилельсплоо. Для и = 1 сумматор Кл показан на рнс. 4.4. На рис. 6.1.а показана СФЭ Е' сложности 9, которая реализует систему ФАЛ Я' от БП х, у и д' такунл, гго ~Я(х,у„д)~ = х+у+ а, т. е. реализует сложение трех одноразрядных чисел. Действительно, на выходе»~ СФЭ Г реализуегся ФАЛ хЗд»Вд', а на выходе ~л единица появляется только тогда., когда либо х = д = 1, либо х 9 д = д' = 1, т. е.

на выходе ~1 в СФЭ Г реализуется ФАЛ хд Ч (х й д)д = хд л»' х»1 Ч до = Ь(х.д,а). Схемный суммагор Е.„порядка и с входными БП хл,..., х„дл,..., д.„ и выходными БП о, -.л,..., е„можно построить из суммагора Е, л лло1ля,|лка (и — 1) с входными БП х2,...,х„д2,...,у„и выходными БП =.л~, 9,..., ~„а также одной СФЭ К' так, как это показано на 1лис. 6.2. Заметим, что переход от суммагора Е„л к суммаго1лу моделирует сложение и-разрядных чисел в два этапа: на первом этапе складываются числа, образуемые (и — 1) младшими разрядами, а на ИТО1х)м эГа!Ге складываготся с!Я~)п!ИР ~)аз1)ЯД!»1 и перенос.

Возникший на перво~! 1) Гане!,. О»!!»видно» '-!То Теорема доказана. Следствие. Х,ф„) 9п — 5. Замечание. Если схему Г на, рис. 6.2 заменить на схему Е". показаннук) на !)!1с. 6.1.6, мы и!).!!у»)им (сх!»мный) к»вав1)с~л)магг)ор Г)Г)- 1)яд~'в и, п2, Ко~~рый иыее! с.')ожнос»1 ь 9п — 9 и !!1)аве!1!Ьно складывает! ))-[)аз1)я)ГИЫ!» двои»!!1!»П»»!и!ла, Каждое из К!)!О1)ых не прев!)сходи ! 2" »! »О Теорема 6.2.

Существует с!Качам!)', вь)чптвгг!ель порядка и. имекпчий слоясность не 6ольше, ч!!м 11п — 5. Дов!Озагг)Г!л)»сп)во. Заме!Им, н!о 1:г~ = 2'" — 1 — И, где»в = 1х1»... „.)!,!), х = 1х1,...,.Г„), и поа Гому 11:"„1х,д) = Ц вЂ” ~Р~ = 2™ — 1 — ~2" — 1 — И+ ~))~) =У ~~.',и) С!Ге»ГОваГельнО ° схе иный вычита!е»!ь ИО$)ядка х! х1О)кот быть НО!)у»1!»н из схемного ! умматора порядка п в резу)!ь тате инвертирования входов е!Т) первого слагаемого„а также всех его выходов, и имеет сложность не больше, пем 11п — 5. ТФ»О1)!»К»!а дОказана. Замечание.

Из Гн)строенного вынитагеля в результате 'поднятия" отрицаний, присоединенных к выходам "~ схемы К! Или К1 в соответствии с равенствами («де и и со — выходы ФЭ ~з и (?'СФЭ К~ ~см. рис. 4.4.6), можно получить вьпппатель сложности не больше, чем 10п — 4. Теорема 6.3. Су(цссптуе)п, с?аннины), счеп)чик горядь() и? ьт))))орый н)(е()))) сл(?:)(сиость не более, чем 9 2". Доъ()зяи)сльс)п()О Счетчик ?„ИОрядка и с вхОдными БП х)...., т? и выходными БП =) ?.... с„+) можно постро)п ь из счетчика.

Е,„) порядка 1)) — 1) с входными БП х),,х? -? и выходными БП 2?,„..., =?, такого же счетчика К„( с входными БП ?г? -?+), .х- и и выхо«?(ны?~н( БП л „..., -„. а, гакже квазисуыыа)ор«с( ~ск(. за~((~«(анг(е к теореме 6,1) Е порядка н с входными БП =)~,..., -,'.„-'~',.... -,",' и выходными БП ч.... ?,-??+) 1см. рнс.

6.3). поскольку на выходах счетчиков К,? ) чис«ла„боль)ние, гем 2" '. не позволяю)ся. В (илу заме')«(ния к теореме 6.1 квазисуммигор . ? Можно посзроить со сложностью не оольше, чем 9ьз — 9, и по?пому Используя неравенство ('6.1) рекурсивно и полагая, что ЦЕ)) = 4, так как ( )Щ = х) х?Х)[2) = х) !,'; х2, то (сть (ч = Я1? пОлучим Цт',„)9~)) — 1)+18~)) — 2)+...+9 2" 2+4 2" Следовательно ~сы. выкладки в конце доказательства теоремы 6).3), „)9 2' Теорема доказана. Следствие. Х,1С;,)9 2".

«) ?:т«-? ?:) — ~+? Х) * ЗЗМЕЧаНИЕ В ОбЩ(?ы случае счетчик„'гО е(") ь ()хема с и выхО- дами„на которых появляе) ся дьч)ична,я запись числа единиц в набор('. зн~ч~ний входных пер(:манных? ь(ожет иметь Л', 2' ' Л" ~ 2'. в~~дон. Такой счетчик можнО п(кгтроить из ""стандартных' счет')иков, пор))дки когорых соогвегсгвукгг номерам единичных компонен) набора о, о (= В", такого, ч го Ц = Х, и не более чем 1и — 1)-го ( уыы«ггора порядка и. К««ая(дый из стандартных с«)етчикОн вычисляет чис)ю единиц в своей части набора из К переменных, а сумматоры складывают числа) появившиеся на выходах счетчиков.

Сложность построенной схемы не превосходит, очевидно, 9(К + и ). Рассмотрим теперь сложность умножи'геля ЛХ, для умножения двух неотрицагельных ц-разрядных двоичных чисел Х ~(х1) х2,...,хц) ~ и У = ~(д1) д2)...) д))) ~. Так как Х < 2' и 1' < 2', то ХУ < 2~' и для представления результата требуется не более 2в выходов. Обозначим через Хм(п) наименьшее возможное число элементов в умножителе ЛХ„.

Очевидно, что Хм(1) = 1, так как умножение 1-разрядных чисел осуществляет элемент кон ьюнкция. Утверждение. Существует СФЭ для умножения и-разрядного числа Х на, 1эразрядное число у с числом элементов и. Действительно, если Х = ~(х~,х2,...,х„)~ и Хд = г, )(.~, ...))... ) =-,) ), то г;=х,;у для всех г' = 1, 2)..., п. При умножении двух п.-разрядных чисел Х и 1' 'в столбик' надо и раз умножить Х на 1-разрядное число (всего и коньюнкций) и затем и — 1 раз сложить числа длиной не более 2ц.

Такой алгоритм (схема) имеет сложность по порядку и~. Следующая теорема. показывает, что алгоритм умножения "в столбик' не оптимален но порядку Теорема 6.4 (Карацуба А. А. [4)). Сущестедет такая константа с) что для всех и Хм(п)си~к' з. Докажем сначала несколько вспомогательных лемм. Лемма 6.1. Сущесгпвует консгпанта с) такая, что Х.м(п + 1) Х м (п) + с) и для всех и. Доказательство. Пусть требуется перемножить два (и + 1)-разрядных числа Х) = )(хшх~)...,х„)) и У) — — )(до)у~)...,у,)). Тогда ооозначим /(х~)х2)...,,г,,)/ = Х и ~(М)д2) )д))~ = 1' При этом Х1 = х02" +Х) Ъ'! = д02" +у и ~-Х~ = хоуо2 '+ (хоУ + уоХ) 2" + Х1'". Поэтому для вычисления Х~Ъ'~ достагочно использовать умножитель М„для вычисления ХУ, 2п, элементов для вычисления хоЪ'' и уоХ, 1 элемент для вычисления худо и 3 суммагора порядка не более 2п + 2, так как ХЖ < 2~"~~.

Отметим) что числа худо хоУ + АХ надо подавать на сумматоры со сдвигом, одновременно подавая на младшие разряды О. При этом О можно предварительно получить подсхемой с 2 элементами, реализующей хохо = О.Так как сложность каждого сумматора можно сделать не более 9(2п+ 2), а сложность ЛХ, равной Хм(п), то сложность полученной схемы будет не больше чем Хм(и) + с) и для некоторой константы с). Лемма доказана. Лемма 6.2 «основная). Сди~кксгг)к)уегг) )(О)(стк)нг)т с) г))акая. Нкпо й;г«2)))ЗЕ(«г)) + к.~)). для в(.(т и. Дк))кк)ак(гк(ельс)аео.

Пусть нужно ))е4)ек()(о)кит)~ два 2()-1)азряд~~~х числа Х и У. Разобьем их на части, содержащие по и разрядов. Тогда получим Х = Х (2" + Х) „У = 1'(2" + 12. Огс к)да Х1 = Х)У(2'" + «ХА~+Х2У))2 + ) )12 = = Х(1')' -'"+ ИХ) + Х~) «У) + 1."~) — Х)1') — Х~Ч " + ХА~. Так как Х)12+Х)У|0, то при вычитании в квадратной скобке не возникает отрицательных чисел.

Такиы образом, схему для умножения ХУ можно по(")1)оить, используя 2 оптимальных умножнтеля ЛХ„О числом э(!еыее(ГОН .Е~(г «а) в каждом д:(я вычисления Х)У) и А~1~. ъмножигель Ы+( с чи(лом элементов Х (к«))+1) для вычисления «Х)+Х~) «У)+1~)) 4 суммато1)а. По))ядка не бо.:и)(. 4Н «"гак квк Л1 С 2 ") и 2 вычигат('.ля порядка 2г) + 2. В некоторых сумматорах опять на младп(ие разряды надо ПОдавс(Гь 0„1(оторый ре)м) изуем НОд( хемОй ( 2 элементами: 0 = тх, где т - лг()бая входная переменив~). Для но(т))оенной сх("мы ЛХ2„с учетом леммы 6.1 получим длг) )!екоторых ко)!стан) с и с2.

Х «ЛХ2,)2Х)г«г)) + 1)г«а + 1) + сг)ЗХ(г«а) + с)а + кт). = Зллг«г() + с~)) Лемма 6.3. Сщ(стк(уст)) гки))гам ь(>астк)аатьк) с(, что для л)о()к)г() )(()ту1)альнк)гк) Й к)ы)итнястся Х (т«2 ')с(3 '. ь, г у к~)) ДО)(азателькггк)(кк). Поло)ким ~ф) = ". ~. Тогда из предыдущей леммы имеем Егг«2кк) Х,.ьг«2)) 1) с2 2 ) ф Зг — ! ЙЮФ вЂ” 1)+ — '«:)' 'М вЂ” 2) + — '«-)" '+ — '«:)"' ' 33 33 33 - Ю)+ — 1-+«-)'+ +«-)' Ъ 33 3 ''' 3 для некоторой константы сл поскольку сумма в квадр(ггных скобках не превосходит сумму 2 бесконечно убыва)огней геометрической прогр(ссии с (И1)выы чл("..нОы — и зиса)енж)е.чеы -„. 1аким ОорвзОЫ вЂ” ) — к( 2 .

. .,, , 2 , , - „ . Х )к(2)) :) ' :) 3 ' Х,(г «2"'):,)3"'. Доказк(теяьстг)(кк) тек)1)(ьмы Кк)рк)цдбы. Пусть а — любое натуральное число и а ~ 1. Тогда существует натуральное () такое, что 2' ~ ))2'. Для умножения н-разрядных чисел будем использовать г — ) 4О гх(-.;му ЛХ2(: (.' ~п((.,(!Ом элем((нтов Х(!Г(2 ), НОдаВая на (,таргние 2 — ьз Вход- 1 ...,, 1 ных 1~(рядов Обоих сомножнге.'п(й О,, пре~1вар!г!Вл(*но реа:п(зован11ый подсхемой из 2 злементов.

То!гда имеем Х„1!!)Х, ~2"'') + 2 13ь + 2 = 3 331' + 2 = = 3 (!2(" 11'(з ~ + 2 < 3 в .'"'к-"' + 2 ' 'к'-'1 для некоторой константы (:, В зак;:почение отметим, что существует а,!Норитм Шенхаге и ШГрас(.'.сна для умнОж(.'ния двух и-раз1!ядных чисез(„даьзц!Ий О!Венку Х~11 ~п)с7! 1оя н 1оя 1О$ н, 1де с - нгкОВ Оран КОнс Ганза и:*!Огарифмы мОжнО очи Гагь дВОи ч1!Ыыи. З 7. Метод Шеннона для синтеза СФЗ. Верхние и нижние опенки функпии Шеннона и сложности некоторых ФАЛ В ~)4 был рассмотрен простейгний метод синтеза СФЭ для произвольной ФА.

1 Дх1„...,х„)„(!снованный на моделировании ее соверпн.иной ДНФ. Если прн эгом воспользоваться замечанием к лемки 4.1 и все кон:ьк!нкции Вида х!' ... х~" реализовиь с помон(ьн! одного схемного деп(иф!!(Ггора, 10 в сиз!у т("О1гемы 3.1 Можно по(произ'ь СФЭ Ку( которая реализует ФАЛ Д~х(„,х„) и для которой ).~Я+! + о~, зй/2) Ра(!ск!О!рим (.ще бо.:!Ое "зкономнь(й' метод синтеза СФ: !— Шеннона.