Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 64
Текст из файла (страница 64)
Синтез логических структур в несвязныг базисах 357 и, и каждан минимальная вершина Н является концом всех дуг, входящих в вершину о; 2) если буква, соответствующая вершине, является инверсной, то производится операция инверсии диаграммы зс (Н). Операция, обратная подстановке, называется операцией свер- тывания диаграммы Н в вершину о. Структурные графы Ну, не содержащие запрещенных фигур 9дк.в! Ядк,в! Ядв,в! Ядв.к, Яды,в, при свертывании диаграмм, соответствующих базисным элементам, свертываются в вершину, взвешенную выходной буквой у. При этом существует взаимно однозначное соответствие между буквами структурного графа Ну и вхождением их в структурную декомпозицию с точностью до по- вторения общих частей.
В качестве упражнения читателю предлагается выделить за- прещенные фигуры Яд, Яд „, Ядк,к! Ядв,в! Чдв,к! Чд . и пре- образовать структурный граф Ну = (У(Х), <): У(Х) = = 1о(х1) ! о(х1) > о(х2) ! и(хг), ю(хг) ! и(хз) ! 6(хз) > и(х4), о(х4) ) > о(х4 < и(хз), о(х4 < и(хз > и хз) < и(х4), в минимальные логические схемы в базисах импликативном, ко- импликативном, Вебба, Шеффера. Полученные результаты будут иметь следующий вид: Ну = Ь„(Ь„(Ь„(хз, Ь„(х4, О)), И„(Ьв(Ив(х4! О), хз), (Ь„(х„Ь„(хг, О)))), Ь„(Ь„(Ь„(х1, Ь„(хг, О)), Ик(Ив(х4> О)> хэ))> Ин(Ик(Ьв(х2> О)> х1) > 0))) ! Ну — Ик(1> Ьк(Ьк(Ик(1! Ьк(Ьк(1! х2)> х1))> Ик(Ик(Ик(1! Ьк(х1! Ик(1> х2))) > х4) > хз))> Ьк(Ьк(Ик(х1! Ик(1! хг))> Ик(Ик(1! х4)! хз))> Ьк(хз> Ик(1> х4)))))> НУ = Ьв(Ьв(Ьв(Ьв(хэ! Ив(Ив(х2> х4) ! Ив(Ьв(х2> х2)! Ьв(хя, х4)))), Ь,(Ь,(х4, Ь,(хг, хг)), Ив(хз, хз))), х1), Ь,(Ь,(хг, Ьв(хт> х1))! Ьв(хз, х4))), Ну = Ь (Ьы(И (Ик(Ьш(хз! хз), Ьш(хя, хя)), Ьш(хз, х4)), Ь (Ьы(хт, хг))), Ьм(Ь (Ь (Ь (Ь„,(Ь (хз, хз), Ь>в(х4, х4)))! Ьы(хг! хг))! Ьш(Ьы(х1> х1), Ьш(хг! хг))))), где Ьа, Ь„, Ь„Ь>к — идентификаторы структурных графов Н(Ь), соответствующих элементам в базисах импликативном, коимпли- кативном, Вебба, Шеффера соответственно.
358 Гл.4. Теория формальных граммагаик и автоматов Полученные структурные композиции определяют логические схемы сложностью 13, 15, 16, 16. Аналогично проектируются абсолютно минимальные логические схемы в любом несвязном базисе. Характеризация семантики связных базисов в виде нахождения запрещенных фигур проектирования логических схем в этих базисах является открытой проблемой. Трудность заключается в том, что для связных элементов необходимо согласовывать структурйые графы, получающиеся внутри цикла графа, соответствующего базисному элементу.
Это согласование учитывает вторую группу уравнений в системе 4.26. Точное проектирование логических схем в несвязных базисах на основе их семантики заключается в реализации следующих преобразований. 1. Синтезируется структурный граф НЦ), реализующий заданную булеву функцию У(хз, хэ, ..., х„). 2. Минимальным расширением носителя структурного графа Н(г) с помощью покрытия семантической таблицы он приводится к виду ка-графов. 3. Определяются структурные графы Н(6;), соответствующие элементам заданного базиса. 4.
Начиная от выходного канала к входным структурный граф Н(у покрывается графами Н(6;). роиллюстрируем эти преобразования проектированием логической схемы, реализующей булеву функцию у(хз, хз, ..., хз) = хзхзхв Ч хзхзхз Ч хзхзхз Ч Ч хзхзхв Ч х«хзхв Ч хзхвхв в классическом базисе, базисах Шеффера, Вебба, импликативном и коимпликативном с Й,„б (2, 3 'р Выполнение пп. 1-3 было проведено выше (см. рис. 4.46,б, 4.54, 4.61). Рассмотрим реализацию п. 4. Преобразование в классическом базисе осуществляется тривиальным образом.
В полученном согласно п. 2 выражении Н(У) = а(к(хз, и(к(хм хв), к(х„о(хв, хв)))), к(хз, х,«1 хв), зг(ц(хз, хз), хз, хв)) связки и и зг заменяются соответственно на элементы Й и Ч (рис. 4.64). В других базисах при покрытии возможно появление согласующего элемента в каналах связи, работающего по схеме НЕ, когда внешние связки базисного элемента не совпадают с внешней связкой непокрытого структурного графа Н(г). Результат покрытия НЯ графами Н(6;) в остальных базисах изображен на рис. 4.65- 4.67. Проектирование осуществлено при допустимом парафазном представлении входной информации. 64.8. Синтез логических структаур в несвязных базисах 359 Определим понятия вида и типа булевых функций. Класс булевых функций, каждан из которых получается из другой путем переименования переменных, называется видом булевых функций. Класс булевых функций, каж- дз дая из которых получается из другой путем переименования леременных и замены переменных их отрицаниями, называется глинам яз булевых функций.
Часто эти преобразования называются преобразованиями Джевонса (по имени ученого, предложившего понятие гз "типа булевых функций). Структурный граф ннвариантен относительно преобразований Рис. 4.64 однотипности. Логическая схема инвариантна относительно переименования переменных. Вид является подклассом типа. Очевидно, что ~А(Н;«) — 1(Н,«Я < п, 1(Н «) — минимальная сложность логической схемы в базисе В, который реализует булеву функцию г(хз, хз, ..., х„) вида сз (зз = з, у) и типа 6, если на реализацию отрицания в этом базисе требуется один элемент.
Следовательно, минимальная сложность логической схемы, реализующей булеву функцию от и переменных в заданном базисе, Хз хз тз Рис. 4.66 360 Гл.4. Теорив формальных грамматик и автоматов определяется с точностью до п свойствами тица, который характеризуется структурным графом, показывающим с точностью до отрицания объединения и пересечения общих частей в логиче- 64.9.
Синтез логических структур в сввзных базисах 361 В рассмотренном в этом параграфе примере не учитывалось распределение красок в структурном графе Н(1), так как допускалась парафазное представление входной информации. Читателю предлагается опустить это ограничение и построить абсолютно минимальные логические схемы в рассматриваемых пяти базисах с учетом распределения красок в структурном графе НЯ, как это делалось в конце предыдущего параграфа. Рнс.
4.66 ской схеме. Другими словами, минимальная сложность логической схемы с точностью до п элементов определяется распределением запрещенных фигур Яд, Яя в мографе, задающем реализуемую булеву функцию. Абсолютную минимальность логической схемы в несвязном базисе определяют распределение запрещенных Р с. 4.6т фигур Я,~, Ян в мографе С~(у), распределение запрещенных фигур ЯГ, Яд в структурном графе Н(у) и удаленность раскраски вершин графа Н(1) от разрешенной раскраски графа НЦ), изоморфному графу Н(у), 94.9. Синтез логических структур в связных базисах В общем виде решение системы связных структурных уравнений (4.26) является открытой проблемой при поиске минимальных логических структур. Рассмотрим приближенное решение этой проблемы.
Число направлений, на которое разлагается структурный граф при преобразовании его в функциональный, равно числу входных каналов базисного элемента. В зависимости от выбранных направлений при выполнении операции разложения получаем различные сложности функционального графа. Если преобразуемый структурный граф НЯ имеет Ф (Ф > Ь,„) максимальных вершин, то для получения функционального графа минимальной сложности необходимо произвести („) различных разложений и М каждое из них оценить.
Для оценки разложений будем использовать тапологические характеристики структурных графов Н(у) и Н(Ь). Сравнение тоцологических характеристик этих графов дает возможность определять оптимальное разложение структурных графов, что особенно важно при проектировании логических схем в многофункциональных базисах, т. е. базисах, содержащих многофункциональные модули — модули, на которых выделена группа входных каналов, в зависимости ат настройки которых выполняется та или иная булеза функция.
В качестве топологических 'характеристик будем рассматривать: и — цикломатическое число; 1 — длину графа (максимальную длину пути, содержащегося в графе); р — число путей; С— н связность, С = 1/я 2 в;, где в; — степень 1-й вершины, я — чисюг ело вершин, щ — число дуг; сс — число максимальных элементов; ,а — число минимальных элементов. Оптимальное разложение структурного графа НЯ оценивается минимальным значением одного из функционалов арг(Н1, Ну) = ((и(Ну) — и(Ну)) + (1(Н1) 1(Ну)) + + (р(Н,) — р(Ну))'+ (С(Н,) — С(Н,))'+ (я(Н1) — я(Ну))'+ + (тп(Н1) — т(Ну)) + Цс«(Ну) — 11(Ну)~ — ~а(Ну) — 1У(Ну)!) ) ', 362 Гл. 4.
Теория формальных грамматик и автоматов узэ(Ну, Н ) = геа — + геа — + геа — + ИНу) 1(Ну) р(Ну) и(Н ) 1(Н,) р(Н ) С(Н,) 'я(Ну) ' -(Н,) ' У.(Н,) — Р(НУ "" С(Н3) '".(Н,) ""-(Н3) "" 1-(Ну) -,в(Н;и где индексы у относятся к реализуемой функции, а индексы з' — к выбранному разложению (настройке многофункционального модуля), геа — остаток от целочисленного деления. Функционал у1(Ну, Н ) применяется, когда среднее значение отклонения их тополагических характеристик не превышает 2, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
