Лекция 13. Тема 7.2. Структурный синтез МПА на жесткой логике

Тема 7.2. Структурный синтез МПА на жесткой логике. Синтез МПА автоматов

Мили на жесткой логике. Вопросы оптимизации МПА

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

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

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

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

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

Рис. 3.19

Рис. 3.20

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

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

Количество строк в таблице равно количеству переходов в графе переходов. В столбце а_m записываются состояния, из которых начинается переход, в столбце a_{s –} состояния, в которые перешел автомат из состояния а_m.

Таблица 3.8

В столбце 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.

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

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

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

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

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

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

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

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

Таблица 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_{0 –} установить «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».

3.1.2.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₂ ;

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

S ₀ = a ₁ x ₃ Ú a_3.

Функции выходов автомата 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 _2.

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

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

Рис. 3.21

3.1.2.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. Функциональная схема автомата Мили

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

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