Синтез автомата Мура по граф-схеме — метод построения функциональной схемы автомата.

Описание[править]

Автомат Мура (Moore machine) — кортеж из 6 элементов, включающий: множество внутренних состояний S (внутренний алфавит); начальное состояние S₀; множество входных сигналов X (входной алфавит); множество выходных сигналов Y (выходной алфавит); функция переходов X; функция выходов Y.

Определение[править]

Автомат Мура — абстрактный автомат второго рода — конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и, не зависит напрямую, в отличие от автомата Мили, от входных значений. Автомат Мура назван в честь описавшего его свойства Эдварда Ф. Мура.

Обозначения[править]

ГСА — граф-схема автомата;

ФСА — функциональная схема автомата;

b₀ — операторная вершина — начальное и конечное состояние автомата;

b_m — операторная вершина — исходное состояние перехода;

b_s — операторная вершина — конечное состояние перехода;

ө_s — узел — дополнительная операторная вершина для упрощения ГСА;

b_m→b_s — переход из одной операторной вершины в другую;

b_m→ө_s, ө_m→b_s, ө_m→ө_s — дополнительные переходы;

X(b_m, b_s) — логическое условие перехода;

S_i — значение на S-триггере;

R_i — значение на R-триггере.

Примеры:[править]

Пример 1[править]

Синтез автомата Мура по ГСА (рис.1).

Рис.1. ГСА автомата Мура с узлами.

Разметка состояний[править]

В автомате Мура каждой операторной вершине соответствует состояние автомата. Переход из состояния b_m в состояние b_s — это переход из одной операторной вершины в другую при выполнении логический условий X(b_m,b_s) на пути из b_m в b_s. Т.к. начальное и конечное состояние автомата совпадают, на ГСА искусственно добавлена еще одна операторная вершина, соответствующая состоянию b₀. Узлы ө используются для упрощения формул переходов и ставятся на ГСА в точках, где несколько путей сходятся, а затем расходятся. Узлы не кодируются.

Рис.2. Размеченная ГСА автомата Мура с узлами.

Построение прямой таблицы переходов 1[править]

Отличительная особенность: в данном примере в ГСА введены узлы ө. В ГСА с узлами возможны переходы четырех видов: b_m→b_s, b_m→ө_s, ө_m→b_s, ө_m→ө_s. Все эти переходы описываются в прямой таблице переходов.

Таблица 1.

В столбце X(b_m,b_s) единица записывается тогда, когда b_m в b_s переход осуществляется всегда.

Кодирование состояний[править]

Произведём кодирование узлов (узлы ө не кодируются). В данном примере — автомат имеет четыре состояния (кроме начального), для кодирования необходимо не менее трёх двоичных разрядов. Память состояний на RS триггерах. Коды состояний: k(b₀)=000; k(b₁)=001; k(b₂)=010; k(b₃)=011; k(b₄)=100.

Построение обратной структурной таблицы 2[править]

Вначале описываем переходы в узлы, затем остальные переходы автомата.

Таблица 2.

Если переход в некоторое состояние b_s происходит из узла ө, то в автомате с памятью на RS триггерах значения R_i и S_i в обратной структурной таблице записываются с учетом кодов состояний b_m из которых был переход в узел ө.

Рис.3. Схема определения значений R_i и S_i.

Запись функции выходов и переходов автомата[править]

По обратной структурной таблице запишем функции для ө, Y_i, R_i и S_i.

Легко заметить, что использование узлов в ГСА автомата Мура позволило значительно упростить функции выходов и переходов.

Построение ФСА автомата Мура[править]

Рис.4. ФСА автомата Мура на жёсткой логике.