Кодирование состояний асинхронного автомата. (до 90 минут)

Читайте также:

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

Универсальный способ кодирования предполагает, что для k полезных состояний используется k элементов памяти. Каждое i-е состояние кодируется как 00..010..0, где стоит в

а) Отсутствие гонок.

00 01 01 01 01

000 001 101 111

б) некритические гонки

00 11 11 11 11 11

101 110 100 000

в) критические гонки

10 10

01 10 10

111 100

110 10

г) генерация при отсутствии гонок

01 00 00 00

011 111 110 010

рис. 25.1

i – позиции. Между i-м и j-м полезным состоянием вводится, если необходимо соблюсти требование соседнего кодирования, транзитное состояние, содержащие единицы в i-й и j-й позиции.

На рис. 25.2а приведён граф переходов автомата с четырьмя состояниями S₁ S₂ S₃ и S₄.

На рис. 25.2б приведён пример соседнего кодирования состояний рассматриваемого автомата на основе универсального способа. Как видно из этого рисунка, для выполнения требования соседнего кодирования пришлось ввести дополнительно шесть транзитных состояний.

Для автомата на рис. 25.2а берём начальное число триггеров

]log₂4[ = 2

Приписываем состоянию S₁код 00, состояниям S₂и S₃коды 01 и 10, соседние по отношению к коду S₁(рис. 43в). Убеждаемся что двух триггеров не достаточно, поэтому увеличиваем число триггеров до трёх

(рис.25.2 г) присваиваем состоянию S₁код 000, а состояниям S₂ S₃ и S₄, смежным с S₁- коды, соседние по отношению к 000. Введение трёх транзитных состояний как показано на рис. 25.2г, приводит к решению поставленной задачи.

0001 0011 0010

а) S₁S₂б) S₁S₂