В.Б. Алексеев, С.А. Ложкин - Элементы теории графов, схем и автоматов (DJVU) (1055625), страница 7
Текст из файла (страница 7)
При построении "сложных' СФЭ из более простых мы будем опираться на понятие подсхемы и принцип эквивалентной замены (см. ~9)). СФЭ К' называется иодстемой СФЭ Е, если множестно ее вершин (дуг) является подмножеством множества вершин (соответственно дуг) Х, а нее те вершины Е', из которых в Е выходит хотя бы одна дуга, не принадлежащая Г, или которые являются выходами Е, являются выходами Е'. При этом предполагается, что все дуги в Е' имеют те же номера, что и н Х, а все вершины Е' имеют те же ФС., что и в Е.
Принцип эквивалентной замены для СФЭ вытекает из определения их функционирования и состоит в том, что если подсхему Г СФЭ Е заменить эквивалентной ей СФЭ Г', то полученная в результате СФЭ Е будет эквивалентна СФЭ Х. В связи с этим подсхемы, которые не имеют общих внутренних вершин, можно рассмагривагь как (много- выходные) макроэлементы. Лемма 5.1.
Для любого нит)«1)ильного )«, с««!«Чист«)«г)«ет «хсемны)1 д«г««г!«ф1)«)10О1) т!«)1)Ядж«т х),. ОмеРО'щУ,'Й слОИ«)нОстпь не «)«)ле«». 'чем т). 2 . в глУбин)1 не более„»«емй ) 1оо») п [+1. ДО)!«)ааттжль«)тт)о«). Для по«т!'рОения искОм()ГО ден)ифр)ъгора ДОстаточно каждую ФАЛ системы ф, реанизовагь по ее совершенной ДНФ [5.1) на основе д-ярусн«?го дерева из н ФЭ Й, Где д. =)1ой' т«[ «см. рис.
5.1). Следствие. АЯ,) и ° 2"+'. Следу)о?цее у)верждение доказывается. по су)пегову. арик!«?пением к построеннол)у в лемме 5.1 схемному дешифратору операции удаления зквивалентных в«-ршин 1см. х4). Теорема 5.1. Сл«)ж)««)с)т)ь м)тнимильи«)га си:емн«)г«) д«)Т!)нфр«ттт)от)«) т!«)1)Яд)»«) и 1)«)йн«) 2" + О(т! 2 "~~).
Дон:азатпельстт!«)«). Поскольку любой дешифратор порядка и при п2 реализует «истему из 2н ФАЛ, отличных от БП„то в нем должно быть по крайней мере 2" вершин, очличных от входов. Синд«)ваге)«ьно» с„')Ожнос?ь ли)бого дшнифрв;)Ора порядка и, н2, в классе СФ3 не меньп?е. чем 2". Г«изобьем набор входных БП «г = (,г!»...,.Гн) на поднаборы х' = («Г?,...,: «,) ));Г" = [.;)+?,...,.:Гн)) )тдЕ й: — тор))н 1.' !." р 1 )' 1«! — 1). Пусть Я~ и Ян — функциональные ден?и«рра)оры порядка и) и 1)! — Л,) от БП г~ и ч'~, а Е«и )" — соответствующие им «хемные депп!«1)р)иОры» КОч Орые и(?«'"!'рО«»ны по лен?м«» '.).1. Л!)ГкО виде)ь, чтО любую ФАЛ Щ,Я» 1«2" » можно представить в виде где !' = 2" 1[1 — 1) + 1 и 1121» 1/2н !'. Дешифрагор Е порядка а от БП «г содержит де)пи«1)раторы К',Г в ка пастве подсхем и реализует каждук) ФАЛ Ян[«1» 1«2") с помощью одного ФЭ Й) входы которого "1ерез 1а[ обозна»)ае)»ся ближайшее сверху к а ?«ел«н число: о«нонание 2 у ло)врифмон опускаетсн.
прис()(тдинены к выходам» и: «1ск!. ри('. 5.2) В сОО'!'Ветс1*вии (" 15.3). Из построения Е следует, что цъ ) — о(» + цт««) + цт'««)2п + .- + т,, 2««+! + [:- Г,)оя ((+! и позтому при Й = [))/2~ получим: Х [Е)2" + О[т! 2"т~). Теорема доказана. Следствие 1. Постт)т)оенньнй дешифратт)ор т)о1)ядна и имеет глубину не больше, чем 11оцн[+2. Следствие 2. Есле е нанеен(ае де(анф~)атт)о1)оа Е' н Ка взят))ь деши4)рипоры» уж:е т)остт)1)оенные т)о тт(еореме 5.1, тио т(олученный деш(4(1)ратт)о1) т)орядна и бтд(«тт! име)аь ел(»н()ноеттгь 2" + ОИ21+ ОИ(1+ О[и, 2"(4)2' + "от«/в+О[)(.
2 т4) 3 /2 2 О«»цд ) о(«+ о(«(2 + О[ 2»«/4) ЗЛ 2 !»Ие. Г».г Лемма 5.2. Дл)( любого натнурального н еущеетиауета са!емный мультт(н~~.йеь.:О1) т)орлдьа и, );;отт)о1тьнй ((меетт! (ло~сно(.тт(ь не более, «им 3 2™ + О[т! 2*'т'"). Дона!»атт)ель(."тт)ео ПО(тгрои«»! схемный му))ь'Гии..(екс(ц) «.«В (*.Оотве1'- с(вии с 15.2) на Основе деГНГ(Фргггора Еа (н)рядка и. кото1)ый являе(схт! его подсхемой. для мого каждый выход Ка и соо(ветс)вук)щий ему инфор«»(а(1ионн!»)й ВхОд «присо(«диним к вхОдах! ФЭ А „а зггГ(.'.м прО- дизь)онктируем ВЫХОД~ В(ех таких ФЭ Й. Если ««1етп)(~)ратор.~а взят!» из теоремы 5.1«то полуненньтй таким Образом ыуг(ьт)п):!ек( Ор Е будет искомым. Лем ма доказана.
Следствие. Поетароенный мультт)тат(л(.)Гсор т)орядка н имеет глубину не больше, чем т(+~1оц)([+3. Теорема 5.2. Существует схемный мдльтиплексор порядка и, имеющий сложность 2'+ + О(2"~~). Доказатиельсгиво. Разобьем набор х = (х1,...,х„,) адресных БП мультиплексора и, на поднаборы х' и х"так же, как это было сделано при доказательстве теоремы 5.1, а набор д = (до,..., д~» 1) его информационных БП ---- на поднаборы д~~~,..., д~~ ~ длины 2" ~ каждый, где д~~~[1] = д„~ при ~, '= 2" ~ (1 — 1) + 1 и всех ~',1 таких, что 112~, И2" ".
При этом из (5.2), (5.3) следует, что: и поэтому р„(х,д) = рх(х',р„х(х",д~ ~),...,р, ~(г",д~ ~)). (5.4) Рассмотрим мула гиплексор Е, который реализует р„по формуле (5.4). Для каждого у, у = 1,....,2"', Е содержит в качестве подсхемы мультиплексор К' порядка (ьз — й) от БП х", д~~~, причем выходы этих мула хиплексоров подаются в соответствии с (5.4) на информационные входы мультиплексора Е' порядка й с адресными БП х' (см.
рис. 5.3). Если мультиплексоры Е' и Е', у = 1,...,2, построить в соответствии с леммой 5.2, а затем перейти от СФЭ Е к эквивалентной ей строго приведенной СФЭ 1 (см. х4), то при Й = [и/2~ мы получим искомый мулыиплексор. Действительно, из доказательства леммы 5.2 следует, что все мультиплексоры Е", 1 = 1,...,2~, имеют общий дешифратор Е" порядка (ьз — Й), и поэтому х.(~)х ( ') + 2'+'+ х.(~:")2"+'+ О(2"~ ) в силу теоремы 5.1. Теорема доказана. Сл~пствие. Х(р„)2'+'+ О(2 ~2) Наряду с дешифратором Я„и мульхиплексором р„порядка и иногда рассматривают также полддеиюфратор Я, порядка ьз с входными БП х1,..., т„и полдмдльтитилексор й„порядка и с входными БП х1„..., х„, до....., д~.-1 ~, такие, что где ! = 1,...,2" .
Заметим. что при х! — — О иче!«?! место равенства: Аналогично доказанным выше утве1?ждениям устанавливаются оцен- !'ис, г?.г Перейдем теперь к по!«троению шифраторов. Определим систему ФАЛ Х)?, дл~~ы а от БП х = (хо, х?„...,хе~ !) зак, что а=(~ ?,.",т! |,!.а?+?, ",о4 для всех !, ! = 1,...,а. Заметим, что О,Ц = 1 то!«ц. и только гогда„ когда «реди БП х~„?' = 0„1,..., 2" — 1, ги??~?е~? кого1?ых име«т! едят?ицу в ?-м разряде своей двоичной запи«-и, есть хотя бы одна БП, раная единице. Это означает; гго система ФАЛ В?! явг?яе!«я 1функциона?ьным) шифрагором порядка нь Если для каждого !, 1 = 1,..., и,, ФАЛ В„Я реализов ?я ь форму??ой ~б.б), то мы получим схемный н?иф1?<т?ор с.;!ажно(-?и ??(2' ' — 1), так как и каждую дизы«?нкцик! ~б.б) вход?п ровно половина БП набора х. Следовгггь?г?ьно, доказано утверждение: Лемма 5.3.
Длл любого натауральнага ьз сущестт?вуетн схемны!?, шифратиор т?г?рядн«? н, ?«атт?«?рый нмеети «!ложнг?сттгь не более. чем и ° 2?! — ! Более "экономный" «хемный шифратор может быть построен с помогцью 1?еку1?свиного ??а??биения множества вх«?дных БП пополам. Теорема 5.3. Суи~естт?е?уетт?, сх!?мный шт?фритиар т?арядка и, сл«?:ж:н«?став натварага нс !К?ль?и«!. чем 2~~ . Д«?назатт?ельстт?в«?. Разобьем наоор БП х = !хо...,,хг !) на поднаборы х' = ~хо,... „х? -! !) и х" = !х?»-?,...,х2 !). Пусть В' и Х?"— функциональные шифраторы порядка (и — Ц от БП г' и х".
а Е' и Е" — соответствуюгцие им схемные шифрагоры. Из (э.5) следует, что О„[!' + Ц = Х1Я '!«' Б" [('« для всех (, ( = 1., (и — 1). Следовагельно, из шифраторов Е' и К««, а также (2(я — 2) ФЭ Ч на основе (5.6) — (5.7) можно построитыпифрм ор .~ НОрядка и, для которОГО: Ч=) Й-') + И ") + (2г — 2) Ис(н)льзуя неравенс ! во (5.8) рекурсиьч(О н по«!агая., что (.(Ю!) 1., так как В( состоит из БП (;(, получим: .("(К)2(«!.— 1)+4(п — 2)+...+3 2" 4+2 2" "+2" ' = — 9" ! 1+1.2+ + 1 (, 1) 2" ! Е ~;Ю С«: 2Я вЂ” ! ~~- 1- 2«(+! (=!«=8 Тео рек(а,«(оказана. Следствие. ( (П,„) 2"+'. 'Хе(зрема 5.4.
Мцни«иальиь((( рии««««рсал(ь((ьЮ .((ногог(о«((о«.и«(к ао- ~Н ря(«(((( «! ((((ес(т! сл(!«(сн««сг«(ь 2 — я. Даная«(ги««льсптаа. Нижняя оценка следует из того, что универ- 211 сальный многопо«носник порядка и реализует систему из 2' — и. ФА.«1„ Отличных От БП (см. доказжгельсгво теоремы 5. 1) . Для получения верхней О(венки построим универсальный много(пх:посник .
~ по (.овершенным ДНФ всех реализуемых ФА,«1 (см. лемму 4.1), а затем перейдем от него к зквивал( нтной строго приведенной СФЭ К' ((.м. ~(4). Заметим, что число вершин СФЭ К', огличных от входов, не болыпе, чем числа различных ФАЛ от БП г(,..., х„, о(г(и (ных от з! их БП. Следов(ггел ьно „ Теорема доказана. ~ 6. Реализация некоторых "арифметических" систем ФАЛ в классе СФЗ Рассмотрим теперь некоторые "'арифметические" системы ФАЛ и построим реализующие их СФЭ.
Системы Я,, ЛХ„и И»„, состоящие из (и+ 1), 2и и и ФАЛ от БП х = (хл ....., х„), д = (дл,..., д„) соответственно, такие,. что )5,,(х,д)) = )х)+ ~у~, ~М,(х.,д)) = )х! )у), и, если Ц (д(, то /И„(х,у)/ = /х/ — /д/. называются (функциональньвл) сумматором, умножптелем лл еьччитпателем порядка п соответственно. Система С„, состоящая из (и+ 1) ФАЛ от БП х = (хл,...,х~ ), такая, что значение ~С„(х) ~ равно числу единиц в наборе х, называется (функциональным) счегичпколл порядка и. Б (8) приведен суммагор порядка и, ~лмеющий сложность 9и — 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
