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