Устройство синхронизации сигналов

соответствии с таблицей выходов объединяем состояния в эквивалентные классы:

P1 = {B ,B ,B ,B }

B = {q ,q ,q }

B = {q }

B = {q }

B = {q }

2)

P2 = {C ,C ,C ,C ,C ,C }

C = {q }

C = {q }

C = {q }

C = {q }

C = {q }

C = {q }

Число классов 2-эквивалентных состояний автомата равно числу состояний автомата, соответственно автомат минимален.

Выбор способа противогоночного кодирования

Для устранения гонок могут использоваться следующие методы:

-  тактирование входных сигналов автомата;

-  дублирование памяти;

-  противогоночное кодирование.

Использование тактирования нецелесообразно, так как требует введения в состав устройства дополнительного генератора тактовых импульсов.

Синтезируемое устройство является достаточно простым, поэтому дублирование памяти приведет к существенному увеличению объема оборудования, и, соответственно, также нецелесообразно.

По вышеуказанным причинам выбираем метод противогоночного кодирования.

Существует ряд способов противогоночного кодирования, которые можно разбить на две группы:

1) методы, позволяющие устранить все состязания

2) методы, устраняющие только критические.

Для упрощения схемы и увеличения быстродействия устраним только критические состязания.

Противогоночное кодирование состояний автомата

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

Выпишем все пары, подлежащие развязыванию:

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

Первый цикл развязывания проведем по всем парам, а далее будем пользоваться сокращенной таблицей.

Развязывание переходов M0:

1) (q ,q ) (q ,q ). Вводим переменную  τ1 (элемент памяти), доопределяем состояния до набора 0011.

2) (q ,q ) (q ,q ) соответствует набор 0011 в τ1, следовательно пара развязана.

3) (q ,q ) (q ,q ) соответствует набор 00-- в τ1, доопределяем его до 0011.

4) (q ,q ) (q ,q ) соответствует набор 11-0 в τ1, доопределяем его до 1100.

5) (q ,q ) (q ,q ) соответствует набор 1111 в τ1, вводим новый элемент памяти τ2, доопределяем состояния до набора 0011.

6) (q ,q ) (q ,q ) соответствует набор 11-0 в τ1, доопределяем его до 1100.

7) (q ,q ) (q ,q ) соответствует набор 1100 в τ1, следовательно пара развязана.

8) (q ,q ) (q ,q ) соответствует набор 0011 в τ2, следовательно пара развязана.

9) (q ,q ) (q ,q ) соответствует набор 1100 в τ1, следовательно пара развязана.

10) (q ,q ) (q ,q ) соответствует набор 0011 в τ1, следовательно пара развязана.

11) (q ,q ) (q ,q ) соответствует набор 0011 в τ1, следовательно пара развязана.

Развязывание переходов М1:

12) (q ,q ) (q ,q ) соответствует набор 0011 в τ1, следовательно пара развязана.

13) (q ,q ) (q ,q ) соответствует набор 0010 в τ1, а в τ2 --0-. Доопределяем его до 1100.

14) (q ,q ) (q ,q ) соответствует набор 1100 в τ2, следовательно пара развязана.

15) (q ,q ) (q ,q ) соответствует набор 1110 в τ1, 0000 в τ2. Вводим новый элемент памяти τ3, доопределяем состояния до набора 0011.

16) (q ,q ) (q ,q ) соответствует набор 1100 в τ1, следовательно пара развязана.

17) (q ,q ) (q ,q ) соответствует набор 0011 в τ2, следовательно пара развязана.

18) (q ,q ) (q ,q ) соответствует набор 1100 в τ1, следовательно пара развязана.

19) (q ,q ) (q ,q ) соответствует набор 0011 в τ2, следовательно пара развязана.

20) (q ,q ) (q ,q ) соответствует набор 1000 в τ1, а в τ2 00-1. Доопределяем его до 0011.

21) (q ,q ) (q ,q ) соответствует набор 0011 в τ2, следовательно пара развязана.

22) (q ,q ) (q ,q ) соответствует набор 0011 в τ2, следовательно пара развязана