Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 61
Текст из файла (страница 61)
б. Производим выравнивание длин путей. 6. Если структурный граф не построен, т. е. порядковый номер синтезированного яруса не равен максимальной длине пути графа, то переходим к и. 2, в противном случае производим подсчет слож- ности ЦНЬ) синтезированного графа. 7. Если ЦНь) = п(у) (и()) — число первичных терман исход- ной ДНФ функции у), то получена бесповторная реализация графа и осуществляем переход к и.
9, Если 1(Нь) > пЦ), то выбираем граф Н из следующего соот- ЦН) = ппп (1,(Нь), ЦНь 1)), гпе 1.(Нь 1) — сложность графа, полученного на предыдущем этапе; ЦНь) — сложность графа, полученного на данном этапе. 8. Выбираем следующий элемент из множества уровней, пре- тендующих на покрытие первого яруса, и ~ереходим к и. 2. Если цля всех уровней, полученных в и. 1, графы синтезированы, то переходим к п. 9.
9. Конец. Лроиллюстрируем предлагаемый метод синтеза структурных графов на следующем примере. Пример 4.5. Сннтезнравзть струвтурныйгрзф, резвнзуюшнйбулеву функ- шио вида т (Х1~ Хэ) ..., ХЬ) = Х1Х2х5 Ч хтхэхэ Ч х!ХЗХЬ Ч х1хэх4 Ч Х1хэх5 Ч хэ хэХЬ.
Зздзнной ТД~Ф этой функция соответствуег матрица ннцндентностн вндз »1 У1 Х2 ХЗ ХЗ Хэ »4 хэ ХЬ 54.7. Синтаеэ логических слтррктлрр е шолологических базисах 337 »1 У1 хэ хз хз »4 Х4 »5 55 12г = ~~0 0 0 1 0 0 1 0 О~~ хэ хэ хэ хэ Вэ хэ УЬ ((О 0 0 0 0 1 0 1 О)(' Плннз всех рзссмзтрнвземьпт слов одна н тв не. Производя локрытне лодмзтрнц 52 „Язт н Я „выделяем лодуравнн. В результате локрытня кодмвтрнцы 42~1 имеем следующие мнонествз: (Х5, 25), (Х2,ХЗ, ЗЗ), (ХЗ,Х5), (Х2,ХЗ, ХЬ).
ПодУРовна (хэ), (хэ,хэ) обРазУютмнонество кокРытнй лодмзтРнцы Ягт. Покрытиями лодмзтрнцы Я», являются (хэ), (хэ). Веса додгрзфов, локрывзюшнх валучеяяые лодуровнн, образуют следуюшне мнанествзт для подуровней буквы хт Ь1(ХЬ~ УЬ)»» (Х2, ХЗ~ ХЗ), ЬЗ(ХЗ~ ХЗ~ Уэ) (Хээ ХЬ)~ ЬЗ(хэ~ ХЬ) (Хэ~ Хээ ХЬ)~ Ьэ(Х2, Хээ ХЬ) — (ХЗ~ ХЬ); цля лодуравней буквы Ут ЬЬ(хэ) = (хэ, УЬ), Ьэ(хэ, УЬ) = (хэ); для кодуравней буквы хэ Ьт(хЬ) = (х,), Ьэ(хэ) = (хэ). Матрица ннцнндентносгн имеет следуюшнй внл: 51 Ьт ьэ 54 5$ Ьэ ьт ьэ »2 *э »5 »4 ХЬ 1 1 0 '0 О О 0 0 1 0 0 1 0 1 О 0 1 1 0 0 0 0 0 0 0 0 0 0 О 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 О 1 1 1 О О О Ьг(тр) = Вьшеляем мнонество кретеялентов нз кервый ярус.
Квндый лретендент нз взвешивание кервого яруса является покрытием матрицы кнцндентностн (уровнем тннз А нлн С). В нашем случае имеем сдедуюшне покрытия: (Х11 У1~ Х2)4 (Х11 ХЗ ХЬ)4 (т1 хэ~ УЬ)~ (",У,х), (2,",=.), (-х.,",=.), [Х1, Х1, хэ)~ (хэ~ ХЗ~ .т$)1 (Х14 хэ~ Уэ~ 35)1 (Х1 Х2 ХЗ) (ХЗ Х4 ХЬ) (Х1 Х4 Хэ~ ХЬ)~ (хт,хэ,хэ), (хэ,хэ, УЬ), (Ут, хт, Уэ,хэ).
Всего имеем 15 кокрытнй ДХя Ы Хс) = 15). Следовательно, для нзхондення графа мнннмзльнай сланнастн необходимо сннтезнровзть 15 грзфов н выбрать граф с минимальной слонностью Взвесим лервый ярус уровнем (хт, хт, хэ), рзсшецнв хэ. Элементам выбранного уровня соответствуют кадмзтрнцы Лт Хэ Хэ »3 Хэ Хэ ХЬ ХЬ 338 Гл.4.
Теория формальных грамлзотпик и оепзомашое Кендый уровень, вввешнввюшнй сннтеэнруемый ярус, оценнвветсн суммарной веднчнной абретныд значений пранввадныд, вычисленных ддк кендой пары подуровней, вкадншнд в оцениваемый уравеньс 10 155 = К К 15 „;;„,=,,',„„,. 1,55 5,т 'ш) еп) 1п 1зт +15 21 +1 + 15 21 +1т — 0+0+0=0, 15 — 21м+15 15 — 21зт+1т + 1ет 1 +0+0=0,6, 1ь — 21зт+ 1т 3 — 2 1+ 1 1зз 1зз 1з — 21зз + 15 1з — 21зз + 1з 15з 1 1 о 15 — 21зз+1з 2 — 2 1+2 2 — 2 1+1 2 — 2 ° 0+1 Оценке принимает ненбадьшее значение ддн уровни (Ьз, Ьз, Ьз), элементы катарога выбираются в качестве весов второго яруса.
Сдедаветедьна, вершины второго яруса взвешивают подуровни Ьз = (кз,хз,кз), Ьз = (тз), Ьз = (хз). Подывтрнцы ннцнндентностн, соатветствуюшне хз й Ьз н хз Е Ьз, не равны друг другу, следовательно, имеем ресшепденне первого типа буквы тз. Я5 Я5 ,я, гз т, гт хз дз о б Рнс.
4.46 Двдьнейшее пастроешге нскаыаго графе однавнечно. Сданность подученного структурнага графа (рнс. 4.46,а) равна 11 (7.(Нт). = 11). Остальные 14 структурныд графов проектируются енедогнчныы обрезом. Трудоемкость алгоритма проектирования структурного графа оптимальной сложности существенно уменьшается, если произвести оценку покрытий в п. 1 с помощью функционала р=~:Л-Я+ , ', 'Л,, (4.19) 1 5~1 ттеу где 1, т — элементы покрытия; Л, 115 — частоты букв;  — число слов мографа. 34.7.
Синтез логических структур е топологическит боэисот 339 Этот функционал показывает удаленность элементов покрытия от условий взвешивания этими элементами яруса синтезируемого графа Н согласно (4.13). С учетом такой модификации и. 1 алгоритма поиска оптимального структурного графа среди 15 графов заменяется на поиск среди трех графов, которым соответствуют покрытия с минимальным значением (4.19).
Этими покрытиями являются покрытия (Х1т Х1) Х4), (Хт) Хэт ХЗ~) (Х4) ХВ) ХЗУ с оценкой функционала, равной нулю. Последние два покрытия порождают абсолютно минимальные структурные графы (рис. 4.46, б). Переход Н -ь Я от структурного графа Н к переключательной схеме Я в базисах первого и третьего топологических классов осуществляется тривиально: заменой вершин на ключевые элементы, дуг — на соединительные каналы с односторонней проводимостью и включением выходного сопротивления в эмиттерную цепь.
Заметим, что включение этого сопротивления в коллекторную цепь соответствует реализации отрицания заданной булевой функции. При преобразовании Н -+ Я в базисах второго типологического класса возможно появление лишних путей из-за двусторонней проводимости соединительных каналов, если структурный граф Н содержит подграф Яя, изображенный на рис. 4.47,а. При снятии ориентации дуг (рис. 4.47,б) неб е сравнимые элементы становятся Рнс. 4.47 сравнимыми и появляется лишний путь, что выводит граф из класса эквивалентных в смысле реализации заданной функции графов. Для ликвидации лишних путей необходимо ориентировать диагональное ребро, помещая на него развязывающий диод (рис.
4.47, е). Утверждение. Граф Яя (рис. 4.47, а) является эапрещенной фигурой преобразования Н ~ Я е базисах второго топологического класса. Следовательно, минимизация развязывающих диодов сводится к покрытию семантической таблицы, в которой запрешеннымн фигурами являются подграфы Яя, а их компонентами — диагональные ребра, в которые помещаются развязывающие диоды. Переход Н ~ Н в базисах второго топологического класса осуществляется, как и в базисах первого класса, ориентацией диагональных ребер в запрещенных фигурах Ян. Например, переключательная схема, реализованная на МОП-транзисторах по структурному графу Н (рис.
4.46, б), соответствующему покрытию (хе, хв, хв), имеет вид, изображенный на рис. 4.48, а. При преобразовании Н -+ 5 в базисах этого класса абстракцией переключательной схемы (рис. 4.48,а) является линейный Рис, 4.49 хз Рис, 4.50 хг 2 хз Рис. 4А9 340 Гл.4, Теория формальных грамматик и автоматов граф (рис. 4.48, б), дуги которого взвешены первичными термами или единицами, соответствующими разрывающим диодам. Линей- л ный граф получается заменой вершин структурного графа Н дугами с теми же весами при сохранении исходных путей.
При преобразовании Н ~ Я в базисах четвертого топологического класса возможно появление лишних путей не только из-за двусторонней проводимости соединительных каналов, но и в результате двусторонней проводимости элементов. При этом лишние пути возникают, если структурный граф содержит подграф Яг, гомеоморфный подграфу Ян. Утверждение. Запрещенной фигурой ЯГ (рис. 4.49, а) преобразования Н -.+ Я в баэисах четпвертпого тпопологического класса являетпся подграф, гомеоморфный фигуре ЯЛ.
В рассматриваемом структурном графе Н (см. рис. 4.46, 6) при его преобразовании в переключательную схему четвертого топологического базиса запрещенными фигурами будут подграфы Яят и 94.7. Синтов яогических структур в топологических баэисах 341 Язт (рис. 4.49, 6) из-за двусторонней проводимости соединительных каналов и подграфы Ярт и Ярт (рис.
4.49, в) из-за двусторонней проводимости самих ключевых элементов. Для ликвидации лишних путей, вызванных двусторонней проводимостью самих элементов, один из элементов, находящийся на диагонали запрещенной фигуры, ориентируется последовательным соединением с ним развязывающего диода, Переход Н -+ Я в базисах рассматриваемого класса осуществляется, как и в первом топологическом базисе, с последующей ориентацией диагональных ребер в запрещенных фигурах ЯГ. Например, переключательная схема, реализованная на криотропах и реализующая функцию у (функция у задается структурным графом Н (рис. 4.48, 6), соответствующим покрытию (хг, хв, хв)), имеет вид, изображенный на рис.
4.50, а. При преобразовании Н -+ Я в базисах четвертого топологического класса абстракцией переключательных схем является линейный граф, ребра которого взвешены первичными термами или единицами, соответствующими развязывающим диодам, и который получается заменой вершин структурного графа Н ребрами с теми же весами при сохранении исходных путей (рис. 4.50, 6). Сложность переключательных схем равна сложности структурного графа, который преобразуется в схему, в нечетных толологических базисах.
Во втором топологическом классе к этой сложности добавляются развязывавшие диоды, определяемые распределением подграфов Ян. Сложность схем в четвертом классе равна сложности соответствующего структурного графа плюс развязывающие диоды, определяемые распределением фигур ЯГ, и минус количество контуров длины 2, ребра каждого из которых взвешены одним и тем же первичным термам. Каждый из таких контуров 344 Гл.4. Теория формальных грамматик и автома»лов (» = 1, ..., )с), каждый из которых состоит из всех вершин (о / у = 1, ..., Ц и соединяющих их дуг, для которых в графе Н найдется путь, соединяющий и, б (иу/ у = 1, ..., Ц и оь б К.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
