Построение графа автомата и структурной таблицы переходов и выходов

Имея отмеченную ГСА проектируемого управляющего микропрограммного автомата, следует описать его работу известными способами - графическим и табличным. Если количество состояний автомата и переходов между ними невелико, то задание его в виде графа позволяет наглядно представить работу МПА.

Граф автомата есть ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними. Причем, две вершины графа а_m и а_s - соединены дугой, направленной от а_m (исходное состояние) к а_s (состояние перехода) если в ГСА существует этот переход.

Для автомата Мили каждой дуге приписываются входные и выходные сигналы, если они определены. Для автомата Мура дугам приписаны только входные сигналы; выходные сигналы приписаны вершинам графа.

Замечания.

1. В графе автомата необходимо указывать все возможные переходы между состояниями, "проходя" встречающиеся на пути из аm в аs условные вершины по всем исходящим из них дугам.

2. При построении графа автомата Мили необходимо избегать "пустых" переходов, то есть переходов, на которых не вырабатываются управляющие сигналы (или на которых не встречается операторной вершины, что эквивалентно). Чтобы не снижать быстродействия МПА, надо в графе показать переход в следующее состояние, если это возможно.

Если автомат имеет большое число состояний и переходов между ними, то наглядность графа теряется. Тогда удобно использовать табличный способ задания автомата. При синтезе МПА строят прямые (или инверсные) структурные таблицы переходов и выходов.

Таблица 2.

В таблице 2 дана прямая структурная таблица для автомата Мили. Для автомата Мура столбец 6 таблицы (выходные сигналы) следует располагать вслед за первым столбцом.

Состояния, перечисляемые в первом столбце таблицы, должны быть упорядочены, то есть сначала следует указать все переходы из а₀, затем из а₁ и т.д. Аналогично и для инверсной таблицы переходов (все переходы в а₀, в а₁ и т.д.). При формировании столбца 5 (входные сигналы) следует указывать конъюнкцию всех входных сигналов, записанных в логических вершинах ГСА на данном переходе. Причем Х_i берут без отрицания, если переход выполняется по единичному значению сигнала, и с отрицанием, если по нулевому значению сигнала.

Первоначально столбцы 2 и 4 таблицы (коды состояний) не могут быть заполнены, так как еще не выполнено кодирование состояний автомата. По этой же причине не могут быть определены и функции возбуждения элементов памяти (столбец 7). Формирование структурной таблицы будет завершено позднее.