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


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

 

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

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

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

 

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

 

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

 

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

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

Таблица 3.8

am as Xamas Yamas
a 1 a 1 a 2 Ø x 3 x 3 - y 1 y 2
a 2 a 3 a 4 x 1 Ø x 1 y 3 y 4 y 5
a 3 a 4 y 4 y 5
a 4 a 1 a 2 x 2 Ø x 2 y 7 y 6

 

 

Количество строк в таблице равно количеству переходов в графе. В столбце аm записываются состояния, из которых начинается переход, в столбце as – состояния, в которые перешел автомат из состояния аm. В столбце Y amas записываются Yi – микрокоманды, вырабатываемые автоматом при переходе из состояния am в состояние as. В столбце Xamas записываются логические условия (их конъюнкция), обеспечивающие переход из состояния аm в состояние as.

Прямая таблица позволяет проверить полноту переходов, показанных на графе переходов: дизъюнкция всех Xama s из состояния a m должна быть равна «1» (ÈXamas=1). В нашем примере дизъюнкция всех Xa1as равна: ÈXa1as = Xa1a1 Ú Xa1a2 = Ø x 3 Ú x 3 = 1. Аналогично: ÈXa2as = Xa2a3 Ú Xa2a4 = x 1 Ú Øx 1 = 1, ÈXa3as = Xa3a4 = 1, ÈXa4as = Xa4a1 Ú Xa4a2 = x2 Ú Øx2 = 1.

 

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

 

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

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

n = ] log2 | A | [ = ] log2 4 [ = 2.

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

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

 

К а1 = 00, К а2 = 01, К а3 = 10, К а4 = 11.

 

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

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

 

Таблица 3.9

 

a m Kam a s Ka s X a ma s Y a m a s F a m a s
a 1 a 4 a 1 Ø x 3 x 2 - y 7 - R 1 R 0
a 1 a 4 a 2 x 3 Ø x 2 y 1 y 2 y 6 S 0 R 1
a 2 a 3 x 1 y 3 S 1 R 0
a 2 a 3 a 4 Ø x 1 y 4 y 5 y 4 y 5 S 1 S 0

При заполнении столбца F a m a s следует обратить внимание на то, что управление RS-триггерами отличается от управления D-триггерами. Если состояние некоторых разрядов RS-триггеров памяти автомата не изменяется при переходе из am в as , то нет необходимости вырабатывать соответствующие сигналы управления S=1 или R=1, так как комбинация S=0 и R=0 соответствует режиму хранения в RS-триггерах. Например, в третьей строке структурной таблицы описан переход из состояния a1 с кодом Kam = 00 (Q1 =0, Q0 =0) в состояние a2 с кодом Kas = 01 (Q1 =0, Q0=1). Что бы обеспечить переход из a1 в a2 нужно сохранить значение Q1 =0, а вмладший разряд памяти состояний Q0 установить «1», поэтому в столбце Famas третьей строки записано «S 0», что означает S0=1. При поступлении на вход синхронизации памяти состояний синхроимпульса С, триггер Т1 не изменит своего состояния (так как R1 =0 и S1 =0), а триггер Т0 перейдет из состояния «0» в состояние «1» (так как R0=0, а S0=1). В столбце Famas не будем записывать Ri = 0 или Si = 0, а будем записывать только те Ri и Si, значения которых должны быть равны «1».

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

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

R i = F( a m , X a m a s).

S i = F( a m , X a m a s).

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

R 1 = a 4 x 2 Ú a4Øx 2 = a4 .

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

S 1 = a2 x 1 Ú a2 Øx 1 = a2 .

R 0 = a 4 x 2 Ú a2 x 1

S 0 = a 1 x 3 Ú a3

 

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

y i = F( a m , X a m a s).

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

y 4 = y 5 = a2 Øx 1 Ú a 3

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

y 1 = y 2 = a 1 x 3 . y 3 = a2 x1.

y 6 = a4Øx 2 y 7 = a4 x 2

 

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

 

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

Память состояний (ПС), де­шифратор состояний (DC), комбинационная схема фор­мирова­ния сигналов управ­ления эле­ментами памяти состояний (КСF), комбина­ционная схема формирова­ния выходных сигналов ав­томата (КСУ). Взаимодейст­вие узлов автомата следую­щее. Автомат находится в некотором состоянии am, код которого Kam в виде значений Q на вы­ходе триггеров памяти состояний (ПС) пода­ется на вход дешифратора состояний (DC), на выходе которого собственно и формируются зна­чения переменных am. На выходах комбинационной схемы КСF формируются значения функций управления элементами па­мяти Famas, которые обеспечивают переход автомата в новое состояние as при поступлении импульса синхронизации С на вход синхронизации ПС, а на выходах комбинационной схемы КСУ при этом формируются значения функций выходов автомата Yamas.

 

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

 

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

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

· Дешифратор состояний DC. В нашем примере – дешифратор DC имеет 2 входа и 4 выхода. На вход DC подается Kam – код состояния am , а на выходах DC формируется унитарный код состояния автомата a m: единица на i-ом выходе дешифратора DC формируется при Kam = 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, что может привести к формированию «ложных» (лишних) микроко­манд. Поэтому необходимо зафиксировать значения xi , поступившие на входы автомата к моменту прихода импульса синхронизации, на время формирования микрокоманд yi. Таким образом, по положи­тельному фронту импульса синхронизации С значения x i, запомина­ются на триггерах Тxi, при С = 1 формируются микрокоманды yi и функции управления элементами памяти 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.Кодирование состояний автоматов.

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

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

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

1. Каждому состоянию ai поставим в соответствие число, равное числу переходов в состояние ai (столбец as обратной структурной таблицы).

2. Состояния упорядочиваются по убыванию рассчитанной харак­теристики и кодируются следующим образом:

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

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

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

 

В рассмотренном выше примере синтеза автомата Мура количество переходов в состояния as таково: в состояние a0 имеется 2 перехода, в a1 – 1 переход, в a2 – 2 перехода, в a3 – 3 перехода, в a4 – 1 переход. Полученная по убыванию числа переходов последовательность состояний: a3 a2 a0 a1 a4 . Поэтому кодирование состояний в нашем примере можно считать оптимальным: K a3 = 000, K a2 = 010, K a0 = 100, K a1 = 001, K a4 = 101.

 

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

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

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

 

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

Кa1= 00, Кa2 = 10, Кa3 = 01, Кa4 = 11, то кодирование будет соседним, так как при переходе из am в as необходимо формировать только одну функцию R или S:

a1 ® a2 : 00 ® 10 - S1

a1 ® a3 : 00 ® 01 - S0

a2 ® a4 : 10 ® 11 - S0

a3 ® a4 : 01 ® 11 - S1.

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

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

При унитарном кодировании состояний и памяти на D-триггерах в каждой строке структурной таблицы автомата может быть записана всего одна функция Di – для установки в «1» триггера, соответствующего состоянию as = ai . При использовании RS-триггеров, в каждой строке таблицы (если состояние автомата должно измениться), записываются две функции: Rm и Ss. Функция Rm «сбрасывает» состояние am , а функция Ss «подготавливает» переход в новое состояние as .

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

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

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

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

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

из состояния am в узел qs : am ® qs;

из узла qm в узел qs : qm ® qs;

из узла qm в состояние as : qm ® as

из состояния am в состояние as : am ® as.

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

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

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

· на переходах в узел ( am ® qs или qm ® qs), независимо от типа автомата, не заполнять столбцы Y ama s или Yam и F amas структурной таблицы автомата.

 

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

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

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

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

 

 

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

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

К a 1 = 00; К a 2 = 11; К a 3 = 10; К a 4 = 01;

Таблица 3.10

am, qm Kam as, qs Kas X am as Yamas F amas
a 1 a 2 q 1   x 0 - - - -
a 3 a 4 q 1 q 2   Øx 4 Øx 1 x 2 - - - - - -
a 1 a 4 a 1 Øx 0 x 4 - y 6 - -
q 1   a 2 Øx 1 Øx 2 y 1 y 4 y 5 D 1D 0
q 1   a 3 x 1 y 1 y 2 y 3 D 1
q 2 q 2   a 4 Øx 3 x 3 y 1 y 2 y 5 y 3 y 4 y 5 D 0 D 0

 

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

q 1 = a1 x0 Ú a 2

q 2 = a 3 Ú a4 Øx4 Ú q 1 Øx 1 x 2

Затем введем вспомогательные функции переходов f I (где i – соответствует номеру перехода вида qm ® as или am ® as в таблице):

f 8 = q 1 Øx 1 Øx 2 f 9 = q 1 x 1

f 10 = q 2 Øx 3 f 11 = q 2 x 3

Далее, выразим функции D 1 и D 0 через дизъюнкцию f I :

D 1= f 8 Ú f 9

D 0 = f 8 Ú f 10 Ú f 11

Функции выходов запишем аналогично с использованием функций f I , заметив, что y 5 = D 0 , а y 1 = D 1 Ú f 10 :

y 1 = f 8 Ú f 9 Ú f 10 = D 1 Ú f 10

y 2 = f 9 Ú f 10

y 3 = f 9 Ú f 11 .

y 4 = f 8 Ú f 11

y 5 = f 8 Ú f 10 Ú f 11 = D 0

y 6 = a 4 x 4

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

 

 

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

 

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

 

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

 


 

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

Таблица 3.11

a m K a m a s K a s X a m,a s Y a s F a m, a s
a 1 a 4 a 5 a 1 Øx 0 x 4 x 4 y 6 - R 1 R 0
a 1 a 3 a 2 x 0 x 1 x 1 y 1 y 2 y 3 S 2 S 1 S 0 S 2
a 3 a 1 a 3 Øx 1Øx 2 x 0Øx 1Øx 2 y 1 y 4 y 5 - S 1 S 0
a 1 a 2 a 3 a 4 a 5 a 4   x 0Øx 1 x 2Øx 3 Øx 3 Øx 1 x 2Øx 3 Øx 3Øx 4 Øx 3Øx 4 y 1 y 2 y 5 S 1 R 2 R 0 R 0 - S 1 R 0
a 1 a 2 a 3 a 4 a 5 a 5   x 0Øx 1 x 2x 3 x 3 Øx 1 x 2x 3 x 3Øx 4 x 3Øx 4 y 3 y 4 y 5 S 0 R 2 R 1 R 1 R 1 S 0 -

Построим обратную структурную таблицу автомата Мура с учетом узлов. При этом обратим внимание на формирование столбца таблицы Famas. Для каждого состояния as определяется множество сигналов Ri и Si, которые обеспечивают переходы из am в as, проходящие через узлы q. В столбец Fama s таблицы записываются Ri и Si, которые находится объединением найденных множеств сигналов Ri и Si.

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

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

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

q 1 = a1 x0 Ú a 3

q 2 = a 2 Ú q 1 Øx 1 x 2 Ú q 3 Øx4

q 3= a 4 Ú a 5

 

Таблица 3.12

a m, qm Kam a s, qs Ka s X a m a s Y a s F am as
a 1 a 3 q 1 - x 0 - - - -
a 2 q 1 q 3 - - q 2 - Øx 1 x 2 Øx 4 - - - - - -
a 4 a 5 q 3 - - - - -
a 1 q 3 - a 1 Øx 0 x 4 y 6 - R 1 R 0
q 1 - a 2 x 1 y 1 y 2 y 3 S 2 S 1 S 0  
q 1 - a 3 Øx 1Øx 2 y 1 y 4 y 5 S 1 S 0
q 2 - a 4 Ø x 3 y 1 y 2 y 5 R 2 S 1 R 0
q 2 - a 5 x 3 y 3 y 4 y 5 R 2 R 1 S 0

 

Затем введем вспомогательные функции переходов f I (где i – соответствует номеру перехода вида qm ® as или am ® as в таблице):

f 9 = q 3 x 4 f 10 = q 1 x 1

f 11 = q 1 Øx 1 Øx 2 f 12 = q 2 Øx 3

f 13 = q 2 x 3

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

R 0 = f 12 Ú f 9

S 0 = f 13 Ú f 10 Ú f 11

R 1 = f 13 Ú f 9

S 1 = f 10 Ú f 11 Ú f 12

R 2 = f 12 Ú f 13

S 2 = f 10

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

y 1 = a 2 Ú a 3 Ú a 4 y 2 = a 2 Ú a 4

y 3 = a 2 Ú a 5 y 4 = a 3 Ú a 5

y 5 = a 3 Ú a 4 Ú a 5 y 6 = a 1

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

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



Дата добавления: 2021-11-16; просмотров: 297;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.052 сек.