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

 

Конечный автомат, реализующий микропрограмму работы дискретного устройства, называется микропрограммным автоматом.

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

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

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

На этапе получения отмеченной ГСА входы вершин, следующих за операторными, отмечаются символами a₁, a₂, ... по следующим правилам:

- символом a₁ отмечаем вход вершины, следующей за начальной и вход конечной вершины;

- входы всех вершин, следующих за операторными, должны быть помечены;

- если вход вершины помечается, то только одним символом;

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

Для расстановки отметок потребуется конечное число символов. Для определённости входы вершин помечаются символами a₁ , ... , а_M.

Результатом выполнения первого этапа является отмеченная ГСА, которая служит основой для выполнения второго этапа - переходу к графу автомата. Применение первого этапа к граф - схеме автомата на рис.70 даёт отмеченную ГСА, изображённую на рис.72.

Если идти от одной отметки a_m к другой отметке a_s в направлении ориентации дуг ГСА, выписывая содержимое лежащих на этом пути вершин, то каждому такому пути можно поставить в соответствие слово в алфавите:

{},

где

Таким образом, Для обозначения того, что выписанное слово соответствует пути по ГСА из a_m в a_s, это слово ограничивается слева и справа символами a_m и a_s соответственно.

Практический интерес представляют слова двух видов:

Соответствующие этим словам пути в граф - схеме называются путями перехода.

В пути вида (D) возможен случай R=0, то есть:

a_mY_t a_s .

Таким образом, путь вида (D) - это путь в ГСА из одной отметки a_m в другую отметку a_s (допустимо a_m=a_s), содержащий точно одну операторную вершину. Путь вида (E) - это путь из некоторой отметки a_m в отметку a₁ (недопустимо a_m=a₁), проходящий точно через все условные вершины.

Каждому пути (или слову) типов (D) или (E) ставится в соответствие конъюнкция

Для краткости эти пути обозначаются

a_m X(a_m,a_s) Y(a_m,a_s) a_s и

a_m X(a_m,a₁) a₁,

где Y(a_m,a_s) = Y_t.

Схематично пути перехода из a_m в a_s изображается так, как показано на рис.73, где волнистой линии соответствует путь через условные вершины.

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

 

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

- находятся все пути перехода в отмеченной ГСА. Если при некотором r (r=1, ... , R) имеется несколько вхождений символа в путь перехода, то все символы , кроме одного, из этого пути удаляются. Если при некотором r (r=1, ... , R) в путь перехода входят как x_r , так и , то такой путь перехода из дальнейшего рассмотрения исключается;

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

- каждому пути перехода вида a_m Y(a_m,a_s) a_s (a_m,a_sÎ{a₁ , ... , a_M}) ставится в соответствие переход автомата S из состояния a_m в состояние a_s , где a_m и a_s определяются так же, как и раньше. Входной сигнал на этом переходе также равен конъюнкции содержимого условных вершин на этом пути. Так как множество условных вершин на этом пути пусто, а конъюнкция пустого множества переменных равна единице, то соответствующий входной сигнал считается равным 1, а выходной сигнал, как и ранее, Y(a_m,a_s );

- каждому пути перехода вида a_m X(a_m,a₁) a₁ ставится в соответствие переход из a_m в a₁. При этом a_m и входной сигнал определяются как и раньше, а выходной сигнал полагается равным Y₀ (пустой оператор).

В результате получается граф автомата Мили S, имеющий столько же состояний, сколько символов потребовалось для отметки входов вершин ГСА. Граф автомата Мили, соответствующий примеру на рис. 72, приведён на рис. 74.

Отличительная особенность микропрограммных автоматов, синтезированных описанным выше способом, состоит в том, что приписанные дугам графа входные сигналы являются элементарными конъюнкциями тех переменных, которые входят в соответствующие пути перехода, причём ранг (длина) этих конъюнкций существенно меньше числа L всех входных переменных.