Проблема гонок сигналов в асинхронных конечных автоматах.

На рис. .4.1 приведена общая модель асинхронных конечных автоматов. Модель аналогична модели для синхронных конечных автоматов, за исключением того, что здесь отсутсвуют тактовые сигналы. В асинхронных схемах в качестве запоминающих элементов (ЗЭ) используются однотипные триггеры, но при этом нельзя сделать допущение, что величина задержек на этих ЗЭ одинаковы.

Как видно из модели, в асинхронных конечных автоматах выходы ЗЭ через обратные связи оказывают воздействие на входное слово. Это обстоятельство дает возможность неправильного срабатывания автомата за счет явления, получившего гонок или состязаний сигналов. Проявление гонок сигналов объясняется тем, что ЗЭ имеют различные, хотя и близкие друг другу времена срабатывания. В свою очередь, различны и задержки сигналов, поступающих на ЗЭ через логические схемы комбинационной части автомата.

Рис.4.1. модель асинхронного конечного автомата.

В статистических данных приводятся такие данные: разброс задержек на схеме И-НЕ составляет 5-10 нс, а на триггере – 10-40нс.

На задержках так же сказывается старение элементов и схем. При старении задержки меняются на 0,04 нс при изменении внешней температуры на 1^оС и на 0,07 нс на 1 пф емкости.

Задержки так же увеличиваются при колебаниях напряжения питания – при изменении питания на 0,5 в задержка увеличивается на 4%.

Из сказанного должно быть ясно, что если по условиям срабатывания конечного автомата в какой-либо момент времени сразу несколько запоминающих элементов меняют свое состояние, то между сигналами с этих элементов начинаются гонки. Тот запоминающий элемент, который выиграет эти гонки, т.е. изменит свое состояние раньше других, может через цепь обратной связи изменить входное слово конечного автомата до того, как другие, учавствующие в гонки запоминающие элементы, изменят свое состояние. Это может вызвать переход конечного автомата не в то состояние, которое предусмотрено его таблицей переходов.

Рассмотрим граф переходов некоторого асинхронного автомата (рис.4.2).

Рис.4.2. Граф переходов асинхронного конечного автомата.

В процессе перехода автомата из состояния S_i в состояние S_e под воздействием сигнала xy, автомат может оказаться в некотором промежуточном состоянии S_j или S_k, в зависимости от того, какой ЗЭ выигрывает гонки. Если затем, при том же входном сигнале х, автомат из состояния S_j или S_k перейдет в состояние S_e, предусмотренное алгоритмом его работы, то такие гонки называются допустимыми или не критичными гонками.

В том случае, когда в автомате есть переход, например, из состояния S_k в состояние S_q (S_q≠S_e) под воздействием того же сигнала х, то автомат может перейти в состояние Sq и правильность его работы будет нарушена. Такие гонки называются критическими гонками.

Существует несколько способов устранения гонок.

Один из способов устранения гонок сигналов заключается во введении второй памяти. (рис. 4.3.).

В этом случае каждый ЗЭ дублируется, причем перепись информации из ЗЭ1 в ЗЭ2 происходит в момент отсутствия сигнала, т.е. р=0. Сигналы обратной связи для получения функций возбуждения и функций выходов конечного автомата снимаются со вторых запоминающих элементов (ЗЭ2). Сигналы в цепи обратной связи не могут измениться, пока сигнал р не станет равным нулю.

Второй способ заключается в том, что кроме входных сигналов на вход автомата подается сигнал р от генератора, который в соответствующий момент времени равен единице, а в моменты отсутствия входных сигналов, сигнал р равен нулю. Таким образом на переходе (S_i,S_e) на вход автомата подается не сигнал х, а сигнал хр. В этом случае, если длительность сигнала р будет меньше самого короткого пути прохождения сигнала по комбинационной части автомата, то к моменту перехода в промежуточное состояние S_k, сигнал р будет равен нулю, то следовательно и хр будет равно нулю, что исключает гонки сигналов.

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

Второй подход в решении проблемы гонок сигналов заключается в специальном кодировании внутренних состояний конечных автоматов. Такое кодирование получило название противогоночное.

Введем некоторые определения и понятия.

Пусть Х и У пара двоичных кодов длинной n.

Пара кодов {X,У} называется развязанной, если при некотором i (1≤i≤n), i-ый разряд кода принимает одно значение на коде У.

В противном случае коды называются связанными.

Утверждается, что в конечном автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют тогда, и только тогда, когда для любых двух переходов (S_i,S_j) и (S_i,S_k) (j≠k), происходящих под воздействием одного и того же входного сигнала, соответствующие пары кодов, кодирующих эти состояния автомата развязаны.

Отсюда следует алгоритм противогоночного кодирования:

1. Последовательно просмотреть все пары переходов конечного автомата, для которого имеется хотя бы один общий входной сигнал, осуществляющий эти переходы.

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

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

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

Рис.4.4. Пример противогоночного кодирования.

Из примера видно, что при любом переходе конечного автомата в соседнее состояние изменяет состояние только один запоминающий элемент, что заведомо исключает гонки сигналов.

Недостатком такого метода кодирования является то, что соседнее кодирование не всегда возможно.