Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 65
Текст из файла (страница 65)
е. первый функционал используется при малом различии их типологических характеристик, в противном случае применяется второй функционал воз(Ну, Н.). В качестве иллюстрации введенных функционалов рассмотрим проектирование логической схемы, реализующей булеву функцию У(х1, зз, хз, хв) ~1 — — Ч(0, 1, 2, 7, 15), на элементах УСЭППА. Структурный граф НЦ) имеет следующий вид: Н(зе) = а'(я(х1, хз, п(кз, хв)), 7Г(хз, хз, хв)). Структурный граф Н(6), соответствующий элементу УСЭППА, имеет матрицу соединений Я = (з; ] вида 0 0 0 -1 0 0 -1 0 0 0 -1 0 0 -1 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 О 0 0 0 0 0 О 0 0 1 0 0 -1 0 0 0 0 0 0 О О 0 0 0 0 0 0 0 0 0 Структурные графы Н1 и Нз, соответствующие двум направлениям разложения, имеют соответственно вид: Н1 = я(З1~ о(ЗЗ, ЗЗ)) ~ Нэ = 1Г(УЭ~ ЗЗ~ З4) ° В данном случае применим функционал ~р1(Ну, Н ): ~р1(Но, Н1), 1р1(Но, Нз), у1(НЭ, Н1), уз1(Нд, Нз), Матрица соединений является двухвходовой матрицей, каждой строке (столбцу) которой взаимно однозначно соответствует вершина структурного графа Х = (У, Н), и 1, если (о;, о ) б Н и эта дуга не перечеркнута, -1, если (о;, и ) б Н и эта дуга перечеркнута, т.
е, она является инверсной, О, (;,;) ФН. 14.9. Синтез логические структур в связныз базисах 363 где Но — Я(Х1 ХЗ П(ХЗ, ХВ)), НД = К(Х2~ ХЗ~ ~4) Каждое из вычисленных значений функционала характеризует близость соответствующих структурных графов 43 Р1(Н , Н1) = ((Π— 0)з + (3 — 2)з + (2 — 2)з + — — -) + (4 — 3) + (3 — 2) + ()1 — 2) — )2 — Ц)з) ' 1/3, 04. Аналогично вычисляем ~р1(Н, Нз) в 1/4,04, р1(Нд, Н1) = 1ГЗ, уз1(Нд, Нз) = О. Согласно вычисленным значениям уз1(Ну, Н,) структурный граф Н разлагаем цо Н1, Нд — по Нз.
В результате получаем структурно декомпозицию вида Н(У) = Цк(хм зз), зв, хз, хз), где Ь вЂ” идентификатор структурного графа Н(6), определяющего элемент УСЭППА. Действуя аналогично, для функции к(х1, зз) окончательно получаем оптимальную логическую схему, состоящую из двух элементов УСЭППА при парафазнам представлении входной информации: НЯх1, хг, хз, хв)) = 6(ЦО, х1, 1, хэ), з4, хз, зз). Структурный граф, соответствующий входу базисного элемента, с точностью до применения операции инверсии является подграфом структурного графа, соответствующего выходу этого же базисного элемента. Отсюда можно предложить следующий метод преобразования структурного графа в функциональный при синтезе в связных базисах.
Для каждого элемента 6, связного базиса перечисляем различные режимы Н его работы и соответствующие им графы Наа Режимы получают путем объединения входов элемента 6; и лутем подачи на вход констант, если такая возможность имеется. Оцениваем графы Нвн по числу вершин и согласна этой оценке упорядочиваем их в порядке убывания этих чисел, Выбираем первый граф Н1 этого ряда и определяем, является ли преобразуемый структурный граф Ну суперпозицией согласно Н1 своих подграфов или их инверсий Н „Н „..., Н, . Если является, та подграфы Н „Н „..., Н „являются искомыми на этом шаге преобразования. Если нет, то выбираем второй граф Нз этого ряда и повторяем проверку и т. д. до получения функцианальнога графа. Оптимизацию этого процесса можно проводить, оценивая удаленность Ну от Н; (Н „ Н „ ..., Н „ ), 1 = 1, 2,..., по их тополагическим характеристикам. Л; Ф: а=о Ь сл аЬ сИ Ос С)4 аЬ Осл а 1ЬсИ х((1, 2 х хс(4, 5) а сИ хз(5) хг(1 ) Рис.
4.66 Рис. 4.66 аЬса О Рис. 4.70 -ьГ. и -и„, Ь=хг П Хз Ь тг Рис. 4.71 364 Гл.4. Теорил Яормальных грамматик и автоматов Проиллюстрируем этот метод логических схем на элементах УСЭППА. Пусть необходимо синтезировать логическую схему на элементах УСЭППА, реализуюшую булеву функцию вида з (х1 хг, „хэ) = х)хг Ч хтхз Ч х)хз Ч хгх4Х5 Ч хгхзх4 г э 4 5 мограф которой изображен на рис. 4.68.
Наиболее интересными режимами являются 8 режимов 1В(/ 1 = 1, ..., 81, представленных реализуемыми структурными графами на рис. 4.69. Провернем, является ли структурный граф Нн„реализуемый режимом В1, подграфом структурного графа НЦ), определяющего булеву функцию у. Для этого вводим операцию разности Н -Нд —— Нч структурных графов Н = (К Ра), Н() = (У, Рд); Р, Рд — множества путей графов Н„, Нр, 'Нч сс ( и', Р.„), Р, = Ра\,Р(), И рассматриваемом случае граф Нн, является подграфом графа НЯ.
Производим эту операцию и находим разность этих графов (рис. 4.70). Следовательно, выходным элементом должен быть элемент, реализующий один из режимов Вв или Вв. Структурный граф Ну — Нн, имеет вид п(хэ, о(х1, п(хг, хв))), следовательно, по своим топологическим характеристикам он ближе к графу, реализуемому режимом Вв. Таким образом, определили выходной элемент. Структурный граф, соответствующий третьему входу выходного элемента, реализуется режимом Вв. Окончательно получаем логическую схему, содержащую три элемента УСЭППА (рис. 4.71). Предложим второй, менее трудоемкий метод проектирования логических схем в связных базисах, в котором не производится построение структурного графа Ну, а проектирование осуществля- 64.9.
Синтез логических структур в связных базисах 366 ется цо мографу С~(у), определяющему заданную булеву функ- ЦИЮ У(Х1, Хг,, Ха). Этот метод состоит из следующих преобразований. 1. Мограф (х~(у) преобразуется в трехъярусный структурный граф Н(з)(у), в котором минимальным элементам взаимно однозначно соответствуют переменные булевой функции, максималь- ному элементу сопоставляется буква, идентифицирующая реализуемую функцию у, элементам промежуточного яруса — идентификаторы слов мографа Сь*(у).
Максимальный элемент соединяется с любым элементом промежуточного яруса перечеркнутой дугой. Минимальный элемент соединяется с вершиной промежуточного яруса дугой, если эта переменная входит в соответствующее слово с отрицанием, и соединяется перечеркнутой дугой, если без отрицания.
366 Гл.4. Теорие формальных грамматик и автоматов Преобразование»лм(у) -+ Нз(у) для рассматриваемого примера приведено на рис. 4.72. 2. Булеза функция»ре(х1, хз, ..., хь), реализуемая режимом В,, преобразуется в трехъярусный структурный граф Н, . Такое прео- (з) У х,(1. хь(4, 5» хэ(1 "з(5» х, хэ хэ х~ хэ Рис. 4.72 аОЬсл Ь с а=1Ь со Ь с а' Й ФА Рис.
4.73 бразование осуществляется для каждого режима (рис. 4.73). Полученные структурные графы (Н ) упорядочиваются по убыванию (з) сложности соответствующих графов Нн,. 14.9. Синтез логических структур в связных базисах 367 3. Определяется в порядке упорядочения, произведенного в п. 2, содержится ли граф Нй) в качестве подграфа в Н(з)(у). Если да, то путем, состоящим из двух перечеркнутых дуг, выход элемента, реализующего этот режим, соединяется с максимальной верши- ной графа Н(з)(у) с одновременным вычитанием графа Ня из (з) Н(з)(эс) Если ни одни из графов (Нй.)) не содержится в Н(з)(7), то (з) ' применением схемной алгебры А, = (Н(з), О, ), изоморфной ал- гебре множеств А„= (М, О, ), граф Н(з)Я приводится к виду, пРи котоРом он содеРжит один из гРафов (Нн 1. (з) Схемкой алгеброй А, называется совокупность (Н(з) где носитель Н(з) — множество трехъярусных структурных гра- фов; сигнатура: 0 — объединение трехъярусных структурных графов Но 0 Нд — — Н», Но — — (Ъ; Ро), Н(» — — (К Рд); Ро, (з) (з) (з) (з) (з) Рр — множества путей графов Н, Н, Н» = (К Р»), Р» = (з) (з) (з) = Р 0 Рд, — инверсия структурного графа.
Выразим через операции 0 и третью операцию — пересече- ние структурных графов Н (1 Нд Н(з) Н(з) Н(з) Н(з) З вЂ” о д В силу изоморфизма этой алгебры и алгебры множеств сигна- тура алгебры А, удовлетворяет следующим законам." 1) коммутативности объединения и пересечения (рис. 4.74, а) а0Ь=Ь0а, а()Ьсс5(»а; 2) ассоциативности объединения и пересечения (рис. 4.74, б) а 0 Ь 0 с = а 0 (Ь 0 с) = (а 0 Ь) 0 с, а П Ь Г» с = а й (Ь П с) = (а Г» Ь) Г) с; 3) дистрибутивности пересечения относительно объединения и объединения относительно пересечения (рис.
4.75) а Г» (Ь 0 с) = (а П Ь) 0 (а П с), а 0 (Ь П с) = (а 0 Ь) Г) (а 0 с); 4) идемпотентности объединения и пересечения (рис. 4.76, а) а0а=а, а()асса; 5) законам действия с константами (рис. 4.76, б) а00=а, а01=1, а0а=1, а»)О=О, ай1еса, аПа=О; а а а Ь с а в =О а б с б Рис. 4.74 о а 1 а а б Рис. 4.76 а с х1 хзхзхс Ь с б Рис. 4лб а с 368 Гл.
4. .4. Теория формальных грамматик и автоматов с4,9, Синтез логических структур в связных базисах 369 6) двойной инверсии (рис. 4.76, в) а = о. 4. Если полученный граф Н(з1(Ц) не является графом, представляющим собой вершину, взвешенную буквой у, то возвращаемся к выполнению п. 3, если является, то конец. ЛА= Рассматриваемый структурный граф Н(з1(у) (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
