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

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

В отличие от автомата Мура, состояния автомата Мили не соответствуют операторным вершинам ГСА, а отмечаются на дугах ГСА перед вершинами, следующими за операторными. Исключение составляет начальное (оно же конечное) состояние автомата. Его удобно обозначать символом а₀ или а₁. Символом а₀ или а₁ отмечают вход вершины, следующей за начальной и вход конечной вершины ГСА. Входы всех остальных вершин, следующих за операторными, также отмечаются символами: а₁, а₂, …

Используем для примера ГСА УА (рис.3.2) для синтеза автомата Мили. Обозначим начальное состояние как а₁, а остальные: а₂, а₃, а₄.

В случае, когда в вершину, следующую за операторной, входит более чем одна дуга, состояние необходимо отметить на дуге так, что бы для всех входящих дуг соблюдалось правило разметки состояний. На ГСА (рис.3.19) это состояния а₂ и а₃. Состояние а₂ необходимо отметить ниже входящей слева стрелки, а состояние а₃ – выше входящей справа стрелки. В первом случае в а₂ сошлись пути из двух операторных вершин, а во втором – путь из а₂ не приводит в состояние а₃ (этот переход был бы «пустым», без прохода через операторную вершину), а приводит в состояние а₄ (после операторной вершины).

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

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

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

Прямая таблица переходов строится по графу переходов (рис.3.20).

Таблица 3.8

Количество строк в таблице равно количеству переходов в графе. В столбце а_m записываются состояния, из которых начинается переход, в столбце a_s – состояния, в которые перешел автомат из состояния а_m. В столбце Y a_ma_s записываются Y_i – микрокоманды, вырабатываемые автоматом при переходе из состояния a_m в состояние a_s. В столбце Xa_ma_s записываются логические условия (их конъюнкция), обеспечивающие переход из состояния а_m в состояние a_s.

Прямая таблица позволяет проверить полноту переходов, показанных на графе переходов: дизъюнкция всех Xa_ma _s из состояния a _m должна быть равна «1» (ÈXa_ma_s=1). В нашем примере дизъюнкция всех Xa₁a_s равна: ÈXa₁a_s = Xa₁a₁ Ú Xa₁a₂ = Ø x ₃ Ú x ₃ = 1. Аналогично: ÈXa₂a_s = Xa₂a₃ Ú Xa₂a₄ = x ₁ Ú Øx ₁ = 1, ÈXa₃a_s = Xa₃a₄ = 1, ÈXa₄a_s = Xa₄a₁ Ú Xa₄a₂ = x₂ Ú Øx₂ = 1.

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

Кодирование состояний автомата Мили производится также как и автомата Мура.

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

n = ] log₂ | A | [ = ] log₂ 4 [ = 2.

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

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

К а₁ = 00, К а₂ = 01, К а₃ = 10, К а₄ = 11.

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

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

Таблица 3.9

При заполнении столбца F a _m a _s следует обратить внимание на то, что управление RS-триггерами отличается от управления D-триггерами. Если состояние некоторых разрядов RS-триггеров памяти автомата не изменяется при переходе из a_m в a_s , то нет необходимости вырабатывать соответствующие сигналы управления S=1 или R=1, так как комбинация S=0 и R=0 соответствует режиму хранения в RS-триггерах. Например, в третьей строке структурной таблицы описан переход из состояния a₁ с кодом Ka_m = 00 (Q₁ =0, Q₀ =0) в состояние a₂ с кодом Ka_s = 01 (Q₁ =0, Q₀=1). Что бы обеспечить переход из a₁ в a₂ нужно сохранить значение Q₁ =0, а вмладший разряд памяти состояний Q₀ установить «1», поэтому в столбце Fa_ma_s третьей строки записано «S ₀», что означает S₀=1. При поступлении на вход синхронизации памяти состояний синхроимпульса С, триггер Т₁ не изменит своего состояния (так как R₁ =0 и S₁ =0), а триггер Т₀ перейдет из состояния «0» в состояние «1» (так как R₀=0, а S₀=1). В столбце Fa_ma_s не будем записывать R_i = 0 или S_i = 0, а будем записывать только те R_i и S_i, значения которых должны быть равны «1».

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

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

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

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

Смысл этих выражений следующий (например для R₁): значение функции R₁ должно быть равно «1» (см. обратную структурную таблицу) в двух случаях (2-ая и 4-ая строки таблицы): если автомат находился в состоянии a₄, а значение x₂ = 1 или, если автомат находился в состоянии a₄, а значение Øx₂ =1. Таким образом, функция R₁ имеет вид:

R ₁ = a ₄ x ₂ Ú a₄Øx ₂ = a_{4 .}

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

S ₁ = a₂ x ₁ Ú a₂ Øx ₁ = a_{2 .}

R ₀ = a ₄ x ₂ Ú a₂ x ₁

S ₀ = a ₁ x ₃ Ú a₃

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

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

Смысл этого выражения следующий (например для y₄): значение функции y₄ должно быть равно «1» (см. обратную структурную таблицу) при переходе автомата из состояний a₂ или a₃ в состояние a₄ (6-ая и 7-ая строки таблицы). Иначе: если автомат находился в состоянии a₂, а значение Øx₂ = 1 или, если автомат находился в состоянии a₃, то при переходе автомата из состояний a₂ или a₃ в состояние a₄ значение y₄ должно быть равно «1». Таким образом, функция y₄ имеет вид:

y ₄ = y ₅ = a₂ Øx ₁ Ú a ₃

Остальные функции выходов имеют вид:

y ₁ = y ₂ = a ₁ x ₃ . y ₃ = a₂ x₁.

y ₆ = a₄Øx ₂ y ₇ = a₄ x ₂

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

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

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

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

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

· Память состояний. В нашем примере – два триггера Т₁ Т_0.

· Дешифратор состояний DC. В нашем примере – дешифратор DC имеет 2 входа и 4 выхода. На вход DC подается Ka_m – код состояния a_m , а на выходах DC формируется унитарный код состояния автомата a _m: единица на i-ом выходе дешифратора DC формируется при Ka_m = i.

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

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

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

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

· Память логических условий. В нашем примере это три D – триг­гера Т_x1 Т_x2 Т_x3 . Значения логических условий на входе автомата Мили могут измениться во время формирования микрокоманды y _i, что может привести к формированию «ложных» (лишних) микроко­манд. Поэтому необходимо зафиксировать значения x_i , поступившие на входы автомата к моменту прихода импульса синхронизации, на время формирования микрокоманд y_i. Таким образом, по положи­тельному фронту импульса синхронизации С значения x _i, запомина­ются на триггерах Т_xi, при С = 1 формируются микрокоманды y_i и функции управления элементами памяти R _i и S _i , а по отрицатель­ному фронту импульса С автомат пере­ходит в сле­дующее состо­яние, опреде­ляемое значе­ниями R _i и S _i на входах па­мяти состоя­ний авто­мата.

Временная диаграмма, поясняющая работу автомата Мили приведена на рис.3.22, функциональная схема – на рис.3.23.

Из временной диаграммы видно, что по положительному фронту импульса синхронизации С значения логических условий Х на входе автомата запоминаются на триггерах Т_xi. Значения логических условий с выходов этих триггеров и текущее состояние автомата a _m используются для вычисления У_{m s} – микрокоманд, вырабатываемых автоматом на переходе из состояния a _m в состояние a _s . Дешифратор состояний DC (рис.12) имеет вход разрешения V: при V=1 дешифратор выдает на одном из своих выходов значение «1», при V=0 – на всех выходах DC логический «0». Это означает, что при С=0 (а значит и V=0), все выходные сигналы автомата У_{m s} равны нулю. Автомат вырабатывает микрокоманды только при С=1.

3.1.3. Вопросы оптимизации автоматов с жесткой логикой.

1.Кодирование состояний автоматов.

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

Оптимальное кодирование состояний УА на D-триггерах.

Очевидно, что выражение для функций управления элементами памяти состояний D_i будет тем короче, чем реже встречается D_i в столбце Fa_ma_s обратной структурной таблицы автомата. К такой минимизации длины выражений D_i приводит следующая процедура:

1. Каждому состоянию a_i поставим в соответствие число, равное числу переходов в состояние a_i (столбец a_s обратной структурной таблицы).
2. Состояния упорядочиваются по убыванию рассчитанной харак­теристики и кодируются следующим образом:

- K=000..0 – присваивается первому состоянию в последовательно­сти.

- Коды с одной единицей присваиваются следующим состоя­ниям.

- Затем, коды с двумя единицами – следующим состояниям, и т. д.

В рассмотренном выше примере синтеза автомата Мура количество переходов в состояния a_s таково: в состояние a₀ имеется 2 перехода, в a₁ – 1 переход, в a₂ – 2 перехода, в a₃ – 3 перехода, в a₄ – 1 переход. Полученная по убыванию числа переходов последовательность состояний: a₃ a₂ a₀ a₁ a₄ . Поэтому кодирование состояний в нашем примере можно считать оптимальным: K a₃ = 000, K a₂ = 010, K a₀ = 100, K a₁ = 001, K a₄ = 101.

Оптимальное кодирование состояний УА на RS-триггерах.

Очевидно, что длина выраже­ний для функции R_i и S_i будет зави­сеть от того, сколько раз встречаются R_i или S_i в столбце Fa_ma_s структурной таб­лицы автомата. Минимизация вы­раже­ний возможна при использовании сосед­него кодирования состояний ав­томата. При соседнем кодировании любые два состояния а_m и a_s, связан­ные дугой на графе, кодируются набо­рами (двоич­ными числами), разли­чающимися лишь в одном разряде. Например, на рис.3.24 приведен фраг­мент графа переходов, в котором может быть применено соседнее ко­дирование состояний.

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

Если в примере (рис. 3.24) закодировать состояния следующим образом:

Кa₁= 00, Кa₂ = 10, Кa₃ = 01, Кa₄ = 11, то кодирование будет соседним, так как при переходе из a_m в a_s необходимо формировать только одну функцию R или S:

a₁ ® a₂ : 00 ® 10 - S₁

a₁ ® a₃ : 00 ® 01 - S₀

a₂ ® a₄ : 10 ® 11 - S₀

a₃ ® a₄ : 01 ® 11 - S_1.

Унитарное кодирование состояний автомата.

Унитарный код – это n-разрядный двоичный код, в котором только одна единица и n-1 нулей (или наоборот). При унитарном кодировании состояний автомата с числом состояний n, необходимо n-элементов памяти, однако не требуется дешифратор (DC) состояний.

При унитарном кодировании состояний и памяти на D-триггерах в каждой строке структурной таблицы автомата может быть записана всего одна функция D_i – для установки в «1» триггера, соответствующего состоянию a_s = a_i . При использовании RS-триггеров, в каждой строке таблицы (если состояние автомата должно измениться), записываются две функции: R_m и S_s. Функция R_m «сбрасывает» состояние a_m , а функция S_s «подготавливает» переход в новое состояние a_s .

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

2. Синтез УА по структурной таблице с узлами.

Описанные выше методы синтеза УА универсальны, однако для сложных ГСА функции переходов и выходов оказываются также очень сложными и плохо поддаются минимизации.

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

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

из состояния a_m в узел q_s : a_m ® q_s;

из узла q_m в узел q_s : q_m ® q_s;

из узла q_m в состояние a_s : q_m ® a_s

из состояния a_m в состояние a_s : a_m ® a_s.

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

· узлы – это не состояния, они не кодируются;

· на переходах в узел в автомате Мили ( a_m ® q_s или q_m ® q_s) не должны встречаться операторные вершины;

· на переходах в узел ( a_m ® q_s или q_m ® q_s), независимо от типа автомата, не заполнять столбцы Y a_ma _s или Ya_m и F a_ma_s структурной таблицы автомата.

Рассмотрим пример построения автомата Мили на D-триггерах с использованием узлов ( ГСА рис.3.25).

1) Разметим состояния a_i автомата Мили.

2) Разметим узлы q_I в точках схода путей. На ГСА автомата - 4 состояния и 2 узла.

3) Не будем в нашем примере строить прямую таблицу и граф переходов автомата. Определим необходимое число элементов памяти: n = ] log₂ 4 [ = 2. В качестве элементов памяти используем 2 D-триггера: Т₁ Т_{0 .}

4) Построим обратную структурную таблицу автомата. Обратная структурная таблица автомата Мили (Таблица 3.10) содержит переходы четырех видов: a_m ® q_s; q_m ® q_s; q_m ® a_s; a_m ® a_s. Будем заполнять таблицу в указанной последовательности переходов.

5) Закодируем состояния автомата в соответствии с рекомендациями по минимальному кодированию состояний с памятью на D-триггерах:

К a ₁ = 00; К a ₂ = 11; К a ₃ = 10; К a ₄ = 01;

Таблица 3.10

6) Запишем функции выходов и управления элементами памяти сле- дующим образом. Сначала запишем функции переходов в узлы q ₁ и q₂ :

q ₁ = a₁ x₀ Ú a ₂

q ₂ = a ₃ Ú a₄ Øx₄ Ú q ₁ Øx ₁ x ₂

Затем введем вспомогательные функции переходов f _I (где i – соответствует номеру перехода вида q_m ® a_s или a_m ® a_s в таблице):

f ₈ = q ₁ Øx ₁ Øx ₂ f ₉ = q ₁ x ₁

f ₁₀ = q ₂ Øx ₃ f ₁₁ = q ₂ x ₃

Далее, выразим функции D ₁ и D ₀ через дизъюнкцию f _I :

D ₁= f ₈ Ú f ₉

D ₀ = f ₈ Ú f ₁₀ Ú f ₁₁

Функции выходов запишем аналогично с использованием функций f _I , заметив, что y ₅ = D ₀ , а y ₁ = D ₁ Ú f ₁₀ :

y ₁ = f ₈ Ú f ₉ Ú f ₁₀ = D ₁ Ú f ₁₀

y ₂ = f ₉ Ú f ₁₀

y ₃ = f ₉ Ú f ₁₁ .

y ₄ = f ₈ Ú f ₁₁

y ₅ = f ₈ Ú f ₁₀ Ú f ₁₁ = D ₀

y ₆ = a ₄ x ₄

Функциональная схема автомата приведена на рис.3.26.

Рассмотрим пример построения автомата Мура с памятью состояний на RS-триггерах по ГСА рис.3.27.

В отличие от автомата Мили можно отметить еще один узел q₃. В узел q ₃ переходы из состояний a₄ и a₅. Построим обратную структурную таблицу автомата Мура без учета узлов.

Обратная структурная таблица автомата Мура по ГСА (рис.3.27) без учета узлов q содержит 17 строк (17 переходов), причем в переходах участвует большое число логических условий x _i . Поэтому выражения для функций управления элементами памяти R_i и S_i будут достаточно громоздкими.

Обратная структурная таблица автомата Мура по ГСА (рис.3.27) без учета узлов q.

Таблица 3.11

Построим обратную структурную таблицу автомата Мура с учетом узлов. При этом обратим внимание на формирование столбца таблицы Fa_ma_s. Для каждого состояния a_s определяется множество сигналов R_i и S_i, которые обеспечивают переходы из a_m в a_s, проходящие через узлы q. В столбец Fa_ma _s таблицы записываются R_i и S_i, которые находится объединением найденных множеств сигналов R_i и S_i.

Эта операция нужна только при реализации памяти состояний автомата на RS-триггерах; в автомате на D-триггерах сигналы управления элементами памяти D_i зависят только от состояния a_s.

Обратная структурная таблица автомата Мура по ГСА (рис.3.27) c учетом узлов q содержит 13 строк, а условия переходов значительно проще, чем без узлов.

Запишем функции выходов и управления элементами памяти следующим образом. Сначала запишем функции переходов в узлы q₁, q₂ и q₃ :

q ₁ = a₁ x₀ Ú a ₃

q ₂ = a ₂ Ú q ₁ Øx ₁ x ₂ Ú q ₃ Øx₄

q ₃= a ₄ Ú a ₅

Таблица 3.12

Затем введем вспомогательные функции переходов f _I (где i – соответствует номеру перехода вида q_m ® a_s или a_m ® a_s в таблице):

f ₉ = q ₃ x ₄ f ₁₀ = q ₁ x ₁

f ₁₁ = q ₁ Øx ₁ Øx ₂ f ₁₂ = q ₂ Øx ₃

f ₁₃ = q ₂ x ₃

Далее, выразим функции R _I и S _I через дизъюнкцию f _I :

R ₀ = f ₁₂ Ú f ₉

S ₀ = f ₁₃ Ú f ₁₀ Ú f ₁₁

R ₁ = f ₁₃ Ú f ₉

S ₁ = f ₁₀ Ú f ₁₁ Ú f ₁₂

R ₂ = f ₁₂ Ú f ₁₃

S ₂ = f ₁₀

Функции выходов:

y ₁ = a ₂ Ú a ₃ Ú a ₄ y ₂ = a ₂ Ú a ₄

y ₃ = a ₂ Ú a ₅ y ₄ = a ₃ Ú a ₅

y ₅ = a ₃ Ú a ₄ Ú a ₅ y ₆ = a ₁

Функциональная схема автомата приведена на рис.3.28.

В приведенной схеме для установки автомата в начальное состояние используется специальная схема, состоящая из шести мультиплексоров MS. При значении Reset=0 сигналы R_i и S_i, формируемые комбинационной схемой автомата, подаются через MS на соответствующие входы R_i и S_i триггеров памяти состояний автомата. . При значении Reset=1 сигналы R_i и S_i формируются в зависимости от схемы подключения входов «1» мультиплексоров к шинам «0» или «1». Так как в нашем примере начальное состояние a ₁ имеет код Ka₁=000, то на все входы R_i через MS подается «1», а на все входы S _i через MS подается «0». По положительному фронту импульса синхронизации С автомат устанавливается в начальное состояние.