 |
Этапы синтеза асинхронного автомата.
|
|
|
|
Этап синтеза относится к асинхронному автомату также используется и в асинхронном, однако есть и отличие.
На этапе абстрактного синтеза нужно добавить следующие действия:
1) Осуществить перекодировку входных и выходных символов для обеспечения распознаваемости соседних одинаковых сигналов.
2) На этапе переходе от алфавитного оператора и автомату необходимо обеспечить все состояния автомата устойчивости.
Если уже автомат задан виде графа, то необходимо проверить устойчивость всех состояний, если это условие не обеспечивается, то надо вернуться в синтезе назад и обеспечить устойчивость, при этом может придется перекодировать входные символы.
Пример перекодирования входных и выходных символов:
P = {a,b} W = {a,b,c}
Вид входного сигнала:
P1 = {a, a1, b, b1} W = {a, b, c, c1}
На исходной временной диаграмме до перекодирования не различимы входные сигналы между I и II интервалом и III и IV. Выходной сигнал не различим между II и III интервалами.
На структурном этапе синтеза отличие следующие:
1) Иной тип элемента памяти, который используется в автомате.
2) Отличие в способе кодирования состояний автомата.
3) Иной метод синтеза комбинационного узла.
1. Кодирование состояний асинхронного автомата.
Цель кодирования – обеспечить устойчивую работу асинхронного автомата, затем устранение так называемого явления состязания памяти.
Состязание элементов памяти
a) τ1 = τ2 à 01à10
b) τ1 > τ2 à 01à00à10
c) τ1 < τ2 à 01à11à10
Это явление называется состязанием элементов памяти.
Реальные элементы памяти обладают задержкой, величина задержки определяется не только в процессе изготовления, но и зависит от внешних факторов, поэтому заранее определить соотношение задержек различных элементов памяти не возможно.
|
|
|
Если в примере q1 и q2 имеют задержки τ1 и τ2, то между ними могут быть соотношение, либо a либо b либо c, в этом случае переход из Si в Sj будет иметь варианты a,b,c. В случае b и c появляются дополнительные состояния 00 и 11, именно такие переходы через дополнительные состояния называются состязанием элементов памяти.
Состязания могут быть критическими и не критическими. Если состязание приводит к переходу в незапланированное устойчивое состояние, то такое состояние называется критическим.
Если же состязание приводит к переходу в незапланированное неустойчивое состояние, а потом и к переходу в верное устойчивое состояние, то такое состояние является некритическим.
Рассмотрим пример:
Закодируем в предыдущем графе 3 состояния следующим образом:
| S/q | q1 | q1 |
| S1 | 0 | 0 |
| S2 | 0 | 1 |
| S3 | 1 | 1 |
тогда автомат будет:
| Pi / Si | 00 | 01 | 10 | 11 | |
| 0 | 00 | 00 | 00 | 11 | 01 |
| 0 | 01 | 00 | 01 | 01 | 01 |
| 1 | 11 | 00 | 01 | 11 | 01 |
Рассмотрим 00à11
q1q2
(τ1 τ2)
- Пусть τ1 > τ2
10
00à01- - >11
Состязание критическое, из-за задержки автомат оказывается в состоянии 01, для которого входной сигнал 10 является устойчивым или приводит к устойчивости, и переходит в состояние 11 не произойдет.
- τ1 < τ2
10 10
00 à 10 à 11
Состязание не критическое.
Если промежуточное состояние в нашем случае некритическое состязание присутствует в графе, то состязание однозначно не критическое, однако если такого состояния нет, то на этапе кодирования можно считать его не критическим. После окончательного синтеза необходимо проверить на наличие петли в таком промежуточном состоянии.
2. Способы кодирования асинхронного автомата.
|
|
|
Так как заранее не известно соотношение между задержками элементов памяти, то необходимо кодировать так, чтобы избежать критических состояний элементов авмяти, либо избежать состязаний вообще.
Для того, чтобы избежать состязаний вообще необходимо закодировать состязания так, чтобы при новых переходах меняется только один элемент памяти.
Существует 2 способа кодирования:
1) Соседними кодами
Для того чтобы на каждом переходе не было состязаний, состояние между которыми есть переход колируют соседними кодами, которые отличаются только в одном разряде.
Однако число переходов обычно настолько велико, что используя код минимальной длины не удается на всех переходах закодировать состояние соседними кодами. В этом случае вводят дополнительное промежуточное состояние, которое является неустойчивым, такие состояния называются транзитивными. Число транзитивных состояний на любом переходе может быть любым. Они служат для задания определенного порядка изменения элементов памяти.
2) Кодирование унитарным кодом
При данном способе кодирования состояние Si кодируется кодом, в котором устанавливается 1 в I разряде.
Для отсутствия состязаний элементов памяти на каждом переходе из Si в Sj устанавливают транзитное состояние и кодируют его кодом, в котором 2 единицы в i и j разрядах.
Данный способ кодирования позволяет записать функции возбуждения прямо по графу, причем они будут не сложными.
Закодируем состояние из примера:
S1 = 100
S2 = 010
S3 = 001
D триггер (там где установка в 1)
D1 = ⌐X1⌐X2q3 v ⌐X1⌐X2q2 v q1⌐q2⌐q3
S3à S1/3 S2à S1/2 S1à S1
S1/3à S1 S12à S1 S1à S1/2
S1à S1/3
D2 = X1X2q1 v ⌐X1X2q3 v X1X2q3 v q1q2⌐q3
S1à S1/2 X2q3 X2q3 S2àS2
S1/2à S2 S3à S23 S3à S23 S2à S12
S23à S2 S23à S2
D3 = X1⌐X2q1 v ⌐q1⌐q2q3
S1à S1/3 S3à S3
S13à S3
Нарисуем временную диаграмму:
Предположим, что автомат находится в состоянии S1, q1,q2,q3 = 100, а входные сигналы X1 X2 = 01, функции возбуждения триггера дают следующие значения D1 = 1, D2 = 0, D3 = 0, что подтверждает состояние 100, до момента t0 схема устойчива.
|
|
|
Схема X1 в момент t0 изменяет D2, которое устанавливает к моменту t1 и вызывает изменение q2 к моменту времени t2; на интервале t2 и t3 получаем состояние 110, т.е. S12. Смена q2 сбрасывает D1, которое в свою очередь переводит q1 в ноль (момент t4), после t4 автомат находится в состоянии 010, т.е. в состоянии S2.
При переходе из S1 в S2 последовательно меняется вначале q2 и затем q1. Это обеспечивало отсутствие состязаний элементов памяти, с другой стороны затянуло переход из S1 в S2, т.е. снизило быстродействие.
Запишем функции возбуждения для RS триггера.
В отличие от D триггера RS должны меняться, когда он сбрасывается и переходит в 1.
R = 1 – сброс
1à 0
S = 1 – установка
0 à 1
R = 1
0 à 0
S = 1
1 à 1
S1 = q3⌐X1⌐X2 v q2⌐X1⌐X2
S3à S1/3(0à1) S2àS1/2 (0à1)
S1/3à S1(1à1) S1/2à S1(1à1)
R1 = q2X1X2 v q3X1⌐X2
S1/2à S2(1à0) S1/3àS3 (1à0)
S2à S2 (0à0) S2à S3(0à0)
S2 = q1X1X2 v q3X2
S1à S1/2(0à1) S3àS2/3 (0à1)
S1/2à S2(1à1) S2/3à S2(1à1)
R2 = q2⌐X1⌐X2
S1/2à S1(1à0)
S1à S1 (0à0)
S3 = q1X1⌐X2 = q1⌐ q2⌐ q3X1⌐X2 v q1⌐q2q3X1⌐X2
S1à S1/3(0à1) (0à1)
S1/3à S3(1à1)
Два разряда q1q2 10 определяют 2 состояния S1 и S13, один разряд q1 = 1 определяет 3 состояния S1,S13,S12, т.е. состояние S1 и транзитное от него. В записи для S3 присутствует также X1, ⌐X2 , что однозначно удаляет состояние S12 следовательно, вместо q1⌐q2, можно записать только q1 и выражение q1X1⌐X2 будет определять только 2 состояния S1 S13.
R3 = q3⌐X1⌐X2 v q3X2
S3à S1(1à0) S2/3àS2(1à0)
S1à S1(0à0) S2 àS2(0à0)
Рассмотрим временную диаграмму S1àS2
| q1 | q2 | q3 | X1 | X2 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 |
|
|
|
Следовательно S3 = 0, R3 = 0
Классификация по логическому функционированию делят на RS, JK, D, T.
По принципу записи и считыванию информации.
Триггеры делят:
a) В зависимости от наличия или отсутствия синхросигнала (синхронные и асинхронные)
b) В зависимости от времени записи новой информации и ее появление на выходе делят на триггеры с задержкой(с разделением процессов записи и считывания) и триггеры без задержки (без разделения) процессов записи и считывания.
В триггерах с задержкой новое значение появляется на выходе по окончанию сигнала, который произвел запись этого нового значения.
На примере RS триггера:
- Асинхронный
a) без задержки
b) с задержкой
- Синхронный
a) без задержки
b) 
с задержкой
Реализация асинхронного RS триггера на логических элементах.
В качестве элемента памяти воспользуемся асинхронным D триггером.
Приведем таблицу переходов D триггера:
0
0 à 0 т.е. значение D пишется над стрелкой.
1
0 à 1
0
1 à 0
1
1 à 1
Следовательно
Это абстрактный закодированный автомат, представленный RS триггер.
Код состояния совпадает со значением выходного сигнала Q.
| RS/q | 00 | 01 | 11 | 10 |
| 0 | 0 | 1 | -- | 0 |
| 1 | 1 | 1 | -- | 0 |
Нарисуем карты Карно
| ------------R | ||||
| ------------S | ||||
| 0 | 1 | -- | 0 | |
| Q - | 1 | 1 | -- | 0 |
тогда Q = S v ⌐RQ = ⌐⌐(S v ⌐RQ) = ⌐(⌐S * ⌐(RQ))
или
| ------------R | ||||
| ------------S | ||||
| 0 | 1 | -- | 0 | |
| Q - | 1 | 1 | -- | 0 |
тогда Q = (Q v S) ⌐R = ⌐(⌐(Q v S) v R)
Подавая различные разрешенные комбинации на входы триггера, убеждаемся что второй выход является ⌐Q. На запрещенных комбинациях на прямом и инверсных выходах мы получаем одно и тоже, либо 0, либо 1 все зависит от использованной элементной базы.
Рассмотрим 1 триггер (с инверсными входами).
Временная диаграмма:
T ⌐S à Q = τ (задержка)
T ⌐S à ⌐Q = 2 τ
При появлении ⌐S = 0, сигнал поступает на верхний элемент и на триггер и устанавливает Q в 1 и лишь затем ⌐Q становится равным 0.
Аналогично при появлении ⌐R = 0 вначале устанавливается ⌐Q в 1, а затем Q в 0.
Рассмотрим второй триггер:
T (S à ⌐Q) = T (R à Q) = τ
T (S à Q) = T (R à ⌐Q) = 2 τ
|
|
|
