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

Задача кодирования состояний является одной из основных задач канонического метода структурного синтеза автоматов. Переход автомата из состояния a_m  в состояние  a_s сопровождается переключением некоторых (возможно, всех) элементов памяти. Если при переходе автомата из какого-либо состояния в смежное должно произойти переключение более чем одного элемента памяти, то возникает ситуация, называемая состязаниями элементов памяти. При этом из-за технологической не идентичности триггеров время переключения их оказывается различным. Под воздействием внешнего сигнала первым переключится триггер, время задержки которого окажется минимальным. Затем произойдет переключение следующего триггера и т.д. Кроме того, различны времена распространения сигналов возбуждения по цепям различной длины. Тот элемент, который выигрывает состязания, т.е. изменит свое состояние раньше других элементов, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие участвующие в состязаниях элементы памяти изменят свое состояние. Это может привести автомат в состояние, не предусмотренное его графом. Поэтому в процессе перехода автомат может оказаться в некотором промежуточном состоянии a_k или a_j в зависимости от того, какой элемент памяти выиграет состязания. Если затем при том же входном сигнале автомат перейдет в состояние a_s, то такие состязания называются некритическими. Если же автомат перейдет в состояние, не предусмотренное его ГСА, то такие состязания называются критическими или гонками. Если при неизменном входном сигнале из полученных переходных неустойчивых состояний возможен переход в другие состояния, не соответствующие желаемому переключению, возникает неправильная работа автомата, т.е. сбой. Такая ситуация называется критическими состязаниями элементов памяти. В любом случае гонки - явление нежелательное и их следует избегать. Пример критических и некритических состязаний элементов памяти приведен на Рис.7.

Рисунок 7 Гонки в цифровом автомате

Если после воздействия на вход автомата сигнала х_i  автомат попадает в состояние, которое имеет код (0010), а затем на вход его поступает сигнал x_k,  который должен перевести автомат в состояние с кодом (1011), то во время этого перехода должны переключиться два элемента памяти. При этом возможны промежуточные переключения в состояния с кодами (1010) или (0011), не входящие в программу работы автомата. Избежать критических состязаний элементов памяти можно, кодируя состояния таким образом, чтобы все переходы совершались между состояниями, закодированными соседними кодами. Кодирование смежных состояний соседними кодами называется противогоночным кодированием. Такие коды, как правило, избыточны. Кроме того, для таких кодов существуют ограничения:

· невозможно использование противогоночного кодирования при наличии в графе автомата циклов нечетной длины;

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

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

Поэтому такой метод борьбы с гонками практически не применяется.

Аппаратные методы борьбы с гонками

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

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

⇐ Предыдущая78910111213141516Следующая ⇒

Поделиться: