Синтез автомата Мура по ГСА. Простейшая реализация

1.Разметка состояний автомата Мура по ГСА.

Каждой операторной вершине ГСА автомата Мура соответствует определенное состояние - a_i . Начальное состояние автомата соответствует началу ГСА, а точнее – входу в первую вершину ГСА. Первая вершина ГСА обычно соответствует логическому условию «Пуск». Поэтому начальное состояние можно отметить на входе этой вершины. Поскольку этому состоянию не соответствует никакая операторная вершина, то и автомат в начальном состоянии не выдает никаких микрокоманд. При такой отметке начального состояния конечное состояние автомата соответствует завершению ГСА (перед вершиной «Конец»).

Для корректной работы автомата необходимо, что бы после завершения выполнения алгоритма автомат вернулся в начальное состояние. Таким образом можно совместить начальное и конечное состояния автомата и обозначить их одинаково a₀.

Часто дополнительно введенную операторную вершину, соответствующую микрокоманде «Операция выполнена», отмечают как конечное состояние автомата (a₀). А так как конечное состояние автомата должно совпадать с начальным, в ГСА вводится еще одна дополнительная операторная вершина, которая отмечается состоянием a₀, так же, как конечная (см. рис.3.14). Такое преобразование ГСА имеет определенные преимущества: если автомат «свободен», он не «молчит», а выдает микрокоманду «Операция выполнена», что говорит о его готовности к работе.

Остальным операторным вершинам соответствуют состояния, которые можно пронумеровать так: a₁, a₂, a₃ и т.д. (рис. 3.14).

Таким образом ГСА автомата Мура (рис.53.14 в нашем примере) отличается от исходной ГСА (рис.3.2) еще одной дополнительной вершиной с состоянием a₀. Обе вершины, помеченные состоянием a₀, можно мысленно совместить, так как после завершения операции автомат должен вернуться в начальное состояние

2.Построение графа переходов автомата Мура (по ГСА рис.3.14)

Вершины графа соответст­вуют состояниям автомата, дуги – переходам из состояния a_m в сос­тояние a_s. У вершин графа записы­ваются микрокоманды, соответст­вующие состояниям, в начале дуги – логические условия, опреде­ляющие переход из состояния a_m в состояние a_s (рис.6).

3.Построение прямой таблицы переходов автомата Мура.

Прямая таблица переходов (Таб­лица 3.6) строится по графу переходов (рис.3.15). Количество строк в таблице равно коли­честву переходов в графе. В столбце а_m за­писываются состояния, из которых начи­нается переход, в столбце a_s – состояния, в которые перешел автомат из а_m. В столбце Ya_s записываются Y_i – мик­рокоманды, вырабатываемые автоматом в состоянии a_s. В столбце Xa_ma_s записываются логические условия (их конъюнкция), обеспечи­вающие переход из состояния а_m в состояние a_s. Прямая таблица по­зволяет проверить полноту переходов, показанных на графе перехо­дов: дизъюнкция всех Xa _ma _s из состояния a _m должна быть равна «1». В нашем примере дизъюнкция всех Xa₀ a _s равна: Ø x ₃ Ú x ₃ = 1 .

Таблица 3.6

№	am	a s	Yas	Xamas
	a 0	a 0 a 1	y7 y1, y2	Ø x 3 x 3
	a 1	a 2 a 3	y3 y4, y5	x 1 Ø x 1
	a 2	a 3	y4, y5
	a 3	a 4 a 0	y6 y7	Ø x 2 x 2
	a 4	a 2 a 3	y3 y4, y5	x 1 Ø x 1

4. Кодирование состояний автомата. Выбор элементов памяти.

Так как поведение автомата всегда зависит от его текущего состояния а_m, необходимо хранить код состояния а_m в памяти состояний автомата. Объем памяти зависит от способа кодирования состояний. При минимальном кодировании каждому состоянию соответствует число в двоичном представлении, причем количество разрядов этого числа n определяется выражением: n = ] log₂ | A | [. Другой крайний случай – унитарное кодирование, при котором: n = | A | . От выбранного способа кодирования и самого кодирования состояний может зависеть сложность схемы автомата.

Используем для нашего примера минимальное кодирование состояний. Так как автомат имеет пять состояний, то минимальное количество элементов памяти

n = ] log₂ | A | [ = ] log₂ 5 [ = 3.

Выберем в качестве элементов памяти D-триггера. Для нашего примера их количество равно трем. Обозначим их как Т₂ Т₁ Т₀ , причем Т₂ соответствует старшему разряду кода состояний. Выходы триггеров обозначаются соответственно Q₂Q₁Q₀. Значение числа Q₂Q₁Q₀ на этих выходах - есть код состояния автомата.

Закодируем состояния автомата произвольно (Ka _i = Q₂Q₁Q₀):

К а₀ = 100. К а₁ = 001. К а₂ = 010.

К а₃ = 000. К а₄ = 011.

5. Обратная структурная таблица автомата Мура.

Обратная структурная таблица автомата Мура строится на основе прямой таблицы переходов путем упорядочивания строк по столбцу a _s .и добавления столбцов:

Ka _m - код состояния a _m.

Ka _s - код состояния a _s.

F a _m a _s – функции управления элементами памяти при переходе из состояния a _m в состояние a _s. Поскольку в качестве элементов памяти используем D-триггера, в этом столбце записываем только D_i, соответствующие триггерам, которые необходимо установить в состояние «1», что бы обеспечить переход в состояние с кодом K a _s.

Таблица 3.7

№	a m	Kam	a s	Kas	Xamas	Yas	Famas
	a 0 a 3		a 0		Ø x 3 x 2	y 7	D 2 D 2
	a 0		a 1		x 3	y 1, y 2	D 0
	a 1 a 4		a 2		x 1 x 1	y 3	D 1 D 1
	a 1 a 2 a 4		a 3		Ø x 1 Ø x 1	y 4, y 5	- - -
	a 3		a 4		Ø x 2	y 6	D 1 D 0

6. Функции управления элементами памяти и функции выходов автомата

Функции управления элементами памяти записываются по обратной структурной таблице автомата:

D _i = F( a _m , X a _m a _s).

Смысл этого выражения следующий (например для D₂): значение функции D₂ должно быть равно 1 (см. обратную структурную таблицу) в двух случаях (1-ая и 2-ая строки таблицы): если автомат находился в состоянии a₀, а значение x ₃ = 0 и если автомат находился в состоянии a₃, а значение x ₂ =1. Таким образом, функция D ₂ имеет вид:

D ₂ = a₀Øx ₃ Ú a₃ x ₂.

Остальные функции D ₁ и D ₀ записываются аналогично:

D ₁ = a₁ x ₁ Ú a₄ x ₁ Ú a₃Øx ₂ = x ₁ (a₁ Ú a₄) Ú a₃ Øx ₂.

D ₀ = a₀ x ₃ Ú a₃Øx ₂.

Функции выходов так же записываются по обратной структурной таблице автомата:

y _i = F( a _s).

Так как y_i в автомате Мура зависят только текущего состояния автомата, то для нашего примера они имеют вид:

y₁ = y₂ = a₁. y₃ = a₂. y₄ = y₅ = a₃. y₆ = a₄. y₇ = a₀,

что означает следующее: в состоянии a₁ автомат вырабатывает микрокоманды y₁ и y₂ , в состоянии a₂ - микрокоманду y₃ и т.д.

7. Структурная схема автомата Мура на жесткой логике

Структурная схема автомата Мура состоит из следующих цифро­вых узлов (Рисунок 3.16):

Рисунок 1.16

Рисунок 3.16

Память состояний (ПС), де­шифратор состояний (DC), комбинационная схема фор­мирования сигналов управ­ления элементами памяти состояний (КС_F), комбина­ционная схема формирова­ния выходных сигналов ав­томата (КС_У). Взаимодейст­вие узлов автомата следую­щее. Автомат находится в некотором состоянии a_m, код которого Ka_m в виде значений Q на вы­ходе триггеров памяти состояний (ПС) подается на вход дешифратора состояний (DC), на выходе которого собственно и формируются зна­чения переменных a_m. На выходах комбинационной схемы КС_У формируются микрокоманды У, а на выходах схемы КС_F формируются значения функций управления элементами памяти, которые обеспечивают переход автомата в новое состояние a _s при поступлении импульса синхронизации С на вход синхронизации ПС.

8. Функциональная схема автомата Мура на жесткой логике

Функциональная схема автомата Мура состоит из следующих цифровых узлов:

· Память состояний. В нашем примере – триггера: Т2 Т1 Т0.

· Дешифратор состояний DC. Дешифратор необходим для преобразования двоичного кода состояний автомата Ka _m в унитарный, соответствующий переменным a _i , используемым в записанных выше функциях. В нашем примере – дешифратор DC имеет 3 входа и 8 выходов. На вход DC подается Ka_m – код состояния a_m , а на выходах DC формируется унитарный код состояния автомата a _m: единица на i-ом выходе дешифратора DC формируется при Ka_m = i.

· Комбинационная схема формирования сигналов управления элементами памяти состояний автомата реализует функции:

D _i = F( a _m , X a _m a _s)..

· Комбинационная схема формирования выходных сигналов автомата реализует функции: y _i = F( a _s).

В функциональной схеме (рис.3.17) использованы «шины». Шины представляют из себя множество соединений схемы, изображенных в виде одной утолщенной линии. Вход в шину и выход из нее конкретного соединения обозначается либо одним и тем же числом, либо содержательным обозначением сигнала, передаваемого по этому соединению. Применение шин в схемах позволяет избежать большого числа пересечений на схеме и делает ее более простой для чтения.

С целью упрощения схемы, в ней не по­казаны элементы, обеспечивающие ус­тановку автомата в начальное состояние а₀ с кодом Ка₀ = 100. Этот вопрос будет рассмотрен ниже.

На рис.3.18 приведены временные диаграммы, поясняющие работу автомата Мура. Находясь в некотором состоянии a _i автомат вырабаты­вает выходной сигнал (микрокоманду) y_j ,соответствующий этому состоя­нию. В это же время формируются сигналы управления элементами памяти D _i , которые определяют следующее состояние автомата в зависимости от теку­щего и значений логи­ческих условий x _i. При поступлении на вход синхронизации авто­мата положительного фронта импульса С, ав­томат переходит в но­вое состояние, определяемое значениями D_i на входах триггеров Т₂ Т₁ Т₀.