Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf

Два графа называются гомоморфными, если один из них получается из другого путем введения дополнительных вер­ шин на его ребра. Предложим алгоритм соседнего кодиро­ вания, основанный на следующей лемме.

Лемма: Размерность гиперкуба, в который вкладывается граф, гомоморфный графу переходов G, не Меньше степе­ ни s (G) графа G.

Окрестностью радиуса R вершины ѵ называется множе­ ство вершин { Ѵі ), для каждой из которых минимальная дли­ на цепи [и, .. ., ѵі] равна R.

Предлагаемый алгоритм соседнего кодирования состоит из следующих шагов:

1.В графе переходов G находим вершину Ѵо максималь­ ной степени 5макс> причем при подсчете степени вершин па­ раллельные ребра, т- е. ребра, имеющие одинаковые концы (эти концы между собой различны),условно считаем заодно ребро; петли графа переходов при подсчете s (ѵ) не учиты­ ваем. В дальнейшем будем называть найденную вершину ѵ0 центром соседнего кодирования. Центр соседнего кодирова­ ния ѵ0 образует окрестность радиуса R, равного 0 вершины VQ. Кодируем произвольным образом вершину о0-

2.Рассматриваем окрестность радиуса R, на 1 большего, чем радиус предыдущей закодированной окрестности.

При рассмотрении вершин окрестности радиуса R воз­ можны три случая, когда необходимо вводить дополнитель­ ные вершины, соответствующие неустойчивым состояниям

автомата:

43

а) k вершин рассматриваемой окрестности попарно смеж­ ны, т. е. образуют полный подграф. В каждое ребро этого полного подграфа помещаем дополнительную вершин}'';

б) имеется вершина ѵа , которая смежна с R ' (R '> R , R — радиус рассматриваемой окрестности) вершинами окрестно­ сти радиуса ^ —1. В этом случае на каждую из R '—R ребер, выбранных произвольным образом и соединяющих вершину ѵа с вершинами окрестности радиуса R — 1, помещаем до­ полнительную вершину. Тем самым этот случай сводится к предыдущему случаю;

в) число вершин NR рассматриваемой окрестности радиу­ са R больше числа сочетаний из s (G) по R, т. е.

рых отличаются в R разрядах от кода некоторой зафиксиро­ ванной вершины этого куба; Тогда введением дополнитель­ ных вершин, смежных с одной стороны вершинам окрестно­ сти радиуса R — 1, с другой стороны, вершинам, наличие ко­ торых обусловливает выполнение неравенства, переводим из­ быток вершин в окрестность радиуса R + 1, так чтобы число

вершин окрестности радиуса R не превосходило

Вследствие того, что за центр соседнего кодирования взята вершина с максимальной степенью, случаи б) и в) од­ новременно иметь место не могут.

После введения дополнительных вершин согласно пунк­ там а), б), в), производим соседнее кодирование вершин ок­ рестности радиуса R.

3.Увеличиваем радиус рассматриваемой окрестности на 1

ипереходим к пункту 2, и так до тех пор, пока не получим искомое соседнее кодирование внутренних состояний авто­ мата. При выполнении пункта 2 может случиться ситуация,

когда размерности гиперкуба не хватает. В этом случае раз­ мерность увеличиваем на 1 и переходим к пункту 1.

Проиллюстрируем этот алгоритм кодированием вершин графа переходов G (рис. 3-5).

Находим вершины максимальной степени, таких вершин

вграфе две: 5г и S3, степень которых равна 3. За центр со­ седнего кодирования выбираем вершину S2 и присваиваем ей

код 111. Тогда вершины Si, S3 и SÖ образуют окрестность ра­ диуса R, равного 1. Условия а), б), в) для этой окрестности

44

не выполняются, следовательно, имеется соседнее кодирова­ ние. Оно следующее:

Окрестность радиуса R, равного двум, образуют вершины S 4 , S 5 . Для этой окрестности также не выполняются условия а), 6 ), в), и соседнее кодирование этих вершин имеет вид

оценивать коэффициентом плотности графа перехбдов.

45

Коэффициент плотности kp (G) позволяет оценивать гра­ фы переходов до применения алгоритма соседнего кодирова­ ния и выбирать из эквивалентных графов наилучший в смыс­ ле оценки kv (G).

Если коэффициент плотности kp равен единице, т. е. граф G является полным, то число дополнительных вершин, вводимых в этот граф, как нетрудно показать, равно

Согласно (3-2) и (3-3), превышение Av(G ) мощности но­ сителя графа, имеющего соседнее кодирование, над мощ­ ностью носителя графа переходов G = <^V, LT>, гомоморф­ ного ему в среднем, можно оценить как

Анализ автоматов управления показывает, что коэффи­ циенты плотности графов переходов, задающих автоматы уп­ равления ЦВМ, малы. Коэффициенты плотности графов пе­ реходов автоматов управления промышленной автоматики велики, т. е. равны 1 или близки к ней. Следовательно, при соседнем кодировании графов переходов автоматов управ­ ления промышленной автоматики число вводимых неустой­ чивых состояний растет довольно' быстро с ростом числа вер­ шин заданного графа переходов. Например, при числах вер­ шин графов переходов, равных

5, 10, 15, 20, 25, 30,

числа неустойчивых состояйіій равны или близки соответ­ ственно к

б, 37, 91, 161, 276, 406.

46

ными в нем операциями /і,'/2, f„, где М называется носи­ тель алгебры, а fi, f'2 , ..., fn — сигнатурой алгебры), сигнатура которой представляет собой две операции: операция объе­

ГПі ß (ГПі Unij) = пц.

Геометрически структура представляется в виде графа G (рис. 4-1).

Например/результаты операций объединения U H пересе­ чения ß для структуры, представленной на рис. 4-1, будут следующими:

48

Результат операции объединения /?г* U rtij есть ближайший к гпі и nij элемент (вершины графа), в котором пересекают­ ся пути, проведенные из и nij и направленные по стрел­ кам графа. Результат операции пересечения

ІПі [\ГПі

есть ближайший к /п* и itij элемент (вершина графа), в ко­ тором пересекаются пути, проведенные из пц и rrij и направ­ ленные против стрелок графа. ,

Мультиструктурой называется объединение по элементам нескольких структур (рис. 4-2).

Другими словами, мультиструктура, есть алгебра с неод­ нозначными операциями, например, для мультиструктуры рис. 4-2 результаты операции

тц U тъ — т 2, т 3; т 2 т 3= і Ші, т5.

Мультиструктура называется взвешенной, если каждому ее элементу сопоставлен некоторый элемент из множества весов Р = ,{р\, р2 , ... ), причем если множество Р есть множе­ ство булевых функций, то мультиструктура называется функ­ циональной, а если булевы функции есть только функции утверждения и функции отрицания, то мультиструктура на­ зывается булевой.

Будем считать, что объединение всех элементов носите­ лей мультиструктуры

4-2. Минимизация булевой функции с учетом теоретико-структурных свойств функции

Булева мультиструктура, соответствующая булевой функ­ ции, определяет общие части и их пересечения в функцио­ нальной мультиструктуре, реализующей заданную функцию, она определяет структуру синтезируемой схемы. Сложность синтезируемой функциональной мультиструктуры в основ­ ном определяется сложностью соответствующей булевой мультиструктуры, сложность которой определяется распре­ делением квазиполных подмоделей в модели i|)(/), задающей булеву функцию /[11]. Это распределение определяет теоре­ тико-структурные свойства булевой функции. Следовательно, теоретико-структурные свойства в основном определяют сложность синтезируемого функционального графа. Отсюда для учета этих свойств необходимо проводить минимизацию числа вершин соответствующего структурного графа, прово­ дить поиск РДНФ [11] функции f с минимальной сложно­ стью. При большом числе переменных очевидна комбинатор­ наясложность этого поиска, ибо нужно для каждого ТДНФ функции построить РДНФ, найти их сложность и выбрать РДНФ с минимальной сложностью.

Для снижения трудоемкости при минимизации булевой функции с учетом теоретико-структурных свойств функции предложим следующий метод синтеза оптимальной ТДНФ,

50