Синтез МПА Мили по ГСА

Для получения графа автомата Мили исходная ГСА отмечается метками Мили. Каждой метке на ГСА ставится во взаимно однозначное соответствие состояние автомата. Алгоритм отметки ГСА метками Мили состоит в следующем:

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

- входы всех вершин, следующих за операторными отмечаются метками а₂,…,а_m;

- одной меткой может быть отмечен только один вход.

На рис. 49 приведена ГСА, отмеченная метками Мили.

Кодирование состояний автомата может быть выполнено, как и ранее, если каждому состоянию поставить в соответствие двоичный эквивалент номера состояния. Для нахождения всевозможных переходов автомата на отмеченной ГСА отыскиваются все пути вида

При достаточно большом числе состояний и переходов удобным является представление автомата структурной таблицей, содержащей всю необходимую для синтеза информацию. Структурная таблица может быть прямой или обратной. В прямой таблице (табл. 40) вначале записываются все переходы из со стояния а₁, затем из состояния а₂ и т.д. В обратной таблице сначала записываются все переходы в состояние а₁, затем в а₂ и т.д..

Для реализации блока памяти МПА использованы RS-триггеры. В последнем столбце отмечены те функции возбуждения, которые приводят к изменению содержимого каждого из элементов памяти на соответствующем пере

ходе. В таблице в столбце F(a_ma_s) приведены функции переключения элементов памяти.

Для построения схемы, реализующей синтезируемый МПА, удобно результаты, приведенные в структурной таблице (табл. 40), представить в виде таблицы истинности (табл. 41).

Таблица 41.

x₁x₂x₃x₄t₁t₂t₃	y₁y₂y₃y₄y₅y₆y₇y₈y₉y₁₀y₁₁y₁₂ S₁R₁S₂R₂S₃R₃
0 - - - 0 0 0 1 - - - 0 0 0 - - - - 0 0 1 - 1 - - 0 1 0 - 0 - - 0 1 0 - 0 1 - 0 1 1 - 0 0 - 0 1 1 - 1 - - 0 1 1 - - - - 1 0 0 - - - 1 0 1 1 - - - 0 1 0 0	1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1