Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 63
Текст из файла (страница 63)
Таким образом, при построении функционального графа Х „. учитывают коэффициент развет- 1 аления Й „„базисных элементов. Окончательный результат прег Хг «г образования структурного графа в функциональный в базисе ( — ь, О) показан на рис. 4.59. Абсолютная минимальность логической схемы в функциональном базисе определяется как семантикой частичного упорядочения мографа, задающего реализуемый автоматный оператор, так и семантикой базисных элементов.
Знание семантики базисных элементов позволяет привести структурный граф Н(у) к минимальному с точки зрения затрат базисных элементов виду, Вид этот представляет собой суперпозицию структурных графов Н(6;), 6! б В, т. е. минимальную структурную декомпозицию. Рассмотрим семантику базисных элементов Ч и 3с при ларафазном представлении входной информации, т. е. при наличии на входе схемы переменных х; и их отрицаний х(.
Дизъюнктор (элемент ИЛИ) реализует а-структуру, конъюнктор (элемент И)— к-структуру. Следовательно, структурные графы, соответствующие выходам логических схем, построенных из этих элементов при парафазном представлении входной информации, представляют собой параллельно-последовательные структуры. Утверждение, Запрещенными фигурами проектированил логических схем иэ диэъюнкторов и конъюнкторов при пара- 14.8. Синтез логических структур в несвлэных базисах 351 фаэном представлении входной информации лвллюгпсл графы вида ЯГ и Яд (рис.
4.53). Хз «! х! «г о Хз х! о «3 о Х! о х! Хг Х, Рнс. 4.$9 Проиллюстрируем этот результат рассмотрением примера Беркхарта у = хуи ЧхуигЧххииУухииг. 1 г 3 4 Мограф, определяющий эту функцию, изображен на рис. 4.60, а. Мограф содержит запрещенные фигуры вида и'(3, 4), у(1, 4), х(1, 3) и'(3, 4), у(2, 4), х(2, 3) Ялз = х(2, 3), и'(3, 4), ю(2, 4) Ял, = у(1, 4), и'(3, 4), и(1, 3) 1, 2, 4) нй, я(3, 4) я х и' к(и, я) а У х Рнс.
4.б1 Рнс. 4.бО 12 я. А Горяаьо 352 Гл. 4. Теория формальных граммагпик и аетоман1ое Семантическая таблица упорядочения мографа представлена в табл. 4.21. Тяблния 4.21 Находя минимальное покрытие этой таблицы, получаем представленный на рис. 4.60, б структурный граф, соответствующий мографу (рис. 4.60, а). полученный граф содержит запрещенные фигуры, определяющие семантику дизъюнкторов и конъюнкторов, следовательно, необходимо дальнейшее расщепление вершин полу- х(1, 2, 3) ченного графа или устранение запрещенных фигур путем выравнивания путей.
Второй способ является предпочтительным, так как часто позволяет произвести устранение запрещенных фигур без увеличения числа вершин графа. Его реализация представлена на рис. 4.60, в. Окончательно согласно структурному графу 34.8. Синтез логических структур е несвязных базисах 353 : рис. 4.60, в) получаем схему минимальной сложности ' рис. 4.60, г), которой соответствует скобочная форма вида у = (хи Ч хуихи Ч ут), или структурная декомпозиция, выраженная через связки к- и а'-структур, вида Н( = к(а(к(х, и), гг(х, у)), а(к(х, о), (г(у, и))). В полученном выражении существует взвимно однозначное соответствие между входными каналами схемы и переменнымн в выражении, при котором существует взаимно однозначное соотВетствие между элементами схемы и идентификаторами соответствующих подструктур (в данном случае к и а).
Таким образом, ликвидировав запрещенные фигуры этого базиса, получим структурный граф Ну (рис. 4.60,в), интерпретируемый в категориях заданного базиса. Цикломатическое число и(Н(6()) каждого элемента 6( любого несвязного базиса В равно нулю, отсюда структурный граф Н(6;) этого элемента представляет собой дерево, следовательно, на выходе любого несвязного элемента порождается к(г-структура.
Графы Н(6;) для наиболее применяемых несвязных базисов приведены на рис. 4.61: Утверждение. Запрещенными фигурами проектирования логических схем в любом несвязном базисе при парафазном представлении входной информации являются графы вида ЯТ и Я (рис. 4.53). ри снятии ограничения на парафазное представление входной информации распределение запрещенных фигур Ог и Яд в структурном графе Ну с точностью до и элементов определяет абсолютную минимальность схемы, где и — число переменных булевой функции у. Для'получения абсолютно минимальной сложности 354 Гл.4.
Теория формальных ерамматик и автоматов логической схемы необходимо учитывать распределение переменных х< и их отрицаний хе в структурном графе Ну. Согласно весам х;, х; вершин структурного графа Ну раскрасим его вершины в два цвета (количество цветов равно значности используемой логики): вершины, взвешенные переменными х;, раскрасим в цвет сь, вершины, взвешенные отрицаниями переменных хо — в цвет 6.
Вершинам, раскрашенным цветом а, на рисунках не будем приписывать штрихи, а вершинам, раскрашенным в цвет 4, будем приписывать. Распределение весов х;, х; или раскраска структурного графа в базисе называются разрешенными, если существует взаимно однозначное соответствие межу входными каналами и вершинами графа Ну, при котором граф Ну представим в виде бесповторной (с точностью до повтора одинаковых частей при одномерной записи) структурной декомпозиции, связками которой являются идентификаторы структурных графов базисных элементов.
Прн разрешенной раскраске на входе логической схемы не включено ни одного инвертора. Разрешенная раскраска порождается путем подстановки структурных графов, задающих базисные элементы друг в друга. Задача приведения заданной раскраски вершин графа Ну к разрешенной сводится к перекраске вершин, нарушающих разрешенное распределение. Перекраска вершины о(х, '), а; = 6, 1, означает появление на входе логической схемы иивертора, на вход которого подается переменная х;. Очевидно, что возможна перекраска не одной вершины, а сразу всех вершин некоторого подграфа Ну„Ну,. С Ну, что эквивалентно включению инвертора внутри или на выходе схемы; при этом для соблюдения эквивалентности реализуемой булевой функции у перекрашиваемый подграф Нй заменяется инверсным Йу,.
Следовательно, для доказательства абсолютной минимальности спроектированной схемы необходимо осуществить возможную перекраску подграфов Нй заданного графа Ну. Проиллюстрируем учет распределения весов х;, х; вершин структурного графа Ну проектированием логической схемы в базисе Шеффера. Для определенности возьмем входной коэффициент Й,„(число входных каналов) базисного элемента, равный 2. Пусть задана булева функция у(х, у, х) хх х Ч ух, структурный граф Ну которой представлен на рис. 4.62, б. Разрешенной раскраской для изоморфиых этому графу графов является раскраска графа Ну,, изображенного на рис. 4.62, а. Сравнивал эти раскраски, замечаем, что для приведения раскраски заданного графа к разрешенной необходима перекраска всех трех вершин. Следовательно, сложность схемы будет равна 5: ~4.8.
Синтез яоеичееких структур в несвязных базисах 355 два элемента необходимы для реализации структурного графа Ну„ имеющего разрешенную раскраску, и три элемента — для перекраски вершин заданного графа Ну (рис. 4.62, б). При перекраске всех вершин включением инвертора на выходе логической схемы для реализации инверсного графа Йу необходимо четыре элемента (рис. 4.62,в), так как в нем необходима перекраска одной вершины. Разрешенная раскраска графа Ну„изоморфного Йу, предста'влена на рис.
4.62,г. Таким образом, любая логическая схема (рис. 4.62, б, в) является абсолютно минимальной при реализации функции у. На рис. 4.62, д изображен граф Ну„изоморфный графу е у х х Рис. 4,62 Нуз (рис. 4.62, г) и имеющий самую сложную раскраску своих вершин. Перекраска отдельных вершин не определяет минимальную реализацию (рис. 4.62,д), ее определяет перекраска всего графа (рис. 4.62, е). Рассматривая аналогично проектирование логических схем в других несвязных базисах (импликативиом, коимпликативном, Вебба), можно показать структуру запрещенных фигур как при нарафазном представлении входной информации, так и при непара- 356 Гл. 4.
Теория формальнык грамматик и ав>помотав фавном. Для определенности входной коэффициент Ь,„ функциональных элементов возьмем равным 2. Утверждение. Запрещенными фигурами проектирования логических схем в импликативном и коимпликативном базисах при парафазном представлении входной информации являются графы Ядвм (рис. 4.63, а), при непарафазном представлении— графы Ядк,„(рис. 4.63, б). Утверждение.
Запрещенными фигурами проектирования логических схем в базисах Вебба и Шеффера при парафазном представлении входной информации являются графы Яд, „ С) ОО 9, ООС) (рис. 4.63,в), при непарафазном представлении в базисе Вебба — графы Юдв.в (рис. 4.63,г), в базисе Шеффера — графы Яд,„(рис. 4.63, д). При увеличении входного коэффициента эти фигуры увеличивают свою высоту и ширину. При иепарафазном представлении входной информации эти две величины равны й,„, при парафазном высота фигур либо равна Ь,к, либо на 1 или 2 больше согласно рис.
4.63,а,в. Ширина фигур либо равна Ь,к, либо на 1 больше согласно тем же рисункам. Подстановкой диаграммы Н вместо вершины о диаграммы Н называется операция, в результате которой: 1) буква, соответствующая вершине о, вычеркивается и вершина и заменяется диаграммой Н так, что каждая максимальная вершина диаграммы Н является началом всех дуг, выходящих из 14.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
