Синтез микропрограммного автомата Мура

Синтез автомата Мура по граф - схеме алгоритма также состоит из двух этапов:

- получение отмеченной ГСА;

- построение графа автомата.

На первом из этих этапов начальная, конечная и операторные вершины отмечаются символами a₁ , ... , a_M по следующим правилам:

- символом a₁ помечаются начальная и конечная вершины;

- различные операторные вершины все отмечаются различными символами;

- все операторные вершины должны быть помечены.

Таким образом, при синтезе автомата Мура, в отличие от автомата Мили, помечаются не входы вершин, следующих за операторными, а сами операторные вершины. За счёт начальной и конечной вершин общее количество пометок будет на единицу больше числа операторных вершин в ГСА.

В результате применения рассмотренной процедуры получения ГСА на рис.75 получается отмеченная ГСА микропрограммного отмеченной автомата по примеру рис.70. Построение графа автомата Мура начинается с нахождения в отмеченной ГСА путей перехода вида:

Как и ранее для краткости эти пути обозначаются a_m X(a_m,a_s) a_s , причём, если между a_m и a_s имеется множество путей вида a_m X_h(a_m,a_s) a_s при (h=1, ... , H), то считается, что этому множеству путей соответствует дизъюнкция , а само множество путей по-прежнему обозначается a_m X(a_m,a_s) a_s и называется обобщённым путём перехода.

В пути вида не исключено R=0, когда между операторными вершинами не расположено ни одной условной вершины и путь превращается в путь .

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

- каждому пути перехода a_m X(a_m,a_s) a_s (a_m,a_sÎ{a₁ , ... , a_M}) ставится в соответствие переход автомата S из состояния a_m в состояние a_s под действием входного сигнала X(a_m,a_s), а пути перехода a_m a_s - под действием единичного сигнала;

- при определении выходных сигналов учитывается, что в каждом состоянии независимо от того, откуда в него произошёл переход, выдаётся выходной сигнал, который записан в операторной вершине, отмеченной символом этого состояния.

На рис.76 приведён граф автомата Мура, построенного по отмеченной ГСА примера на рис.75.

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

- a_m - исходное состояние;

- a_s - состояние перехода;

- X(a_m, a_s) - входной сигнал на переходе (a_m, a_s);

- Y(a_m, a_s) - выходной сигнал на переходе (a_m, a_s).

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

В ряде случаев оказывается удобным пользоваться обратной таблицей переходов, в которой столбцы обозначены точно также, но сначала записываются все переходы в первое состояние, затем во второе и так далее.

В случае описания автомата Мура можно обойтись всего тремя столбцами, записывая выходной сигнал в прямой таблице рядом с соответствующим ему исходным состоянием, а в обратной - рядом с состоянием перехода. Обратной является таблица 42 для автомата Мура, построенная по рис.75.

Таблицы переходов микропрограммного автомата (прямые или обратные) составляются непосредственно по ГСА, когда в эти таблицы заносятся все пути переходов. Поскольку графическое и табличное описания микропрограммных автоматов равноценны, то для заполнения таблиц переходов автоматов предварительного составления графа автомата не требуется.