4.1 Гонки в автомате

Переход автомата из одного состояния в другое осуществляется за счет изменения состояния элементов памяти Q₁, Q₂, ... , Q_I, которое производится сигналами возбуждения  ₁,  ₂, ... ,  _I (см. рис. 3.1), вырабатываемыми в комбинационной схеме КС1 и поступающими на входы триггеров. Сигналы возбуждения поступают на входы триггеров не одновременно, так как логические цепи их реализующие, возможно не идентичные по количеству используемых в них логических элементов, характеризуются различным временем задержки сигнала. К тому же триггеры имеют различное время переключения. Из-за различия во временных характеристиках триггеры изменяют свои состояния не одновременно.

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

Например, при переходе автомата a_m в состояние a_s под действием входного сигнала x (рис. 3.7,а), автомат может оказаться в некотором промежуточном состоянии a_k или a_l. Если затем при том же входном сигнале автомат из a_k и a_l перейдет в состояние a_s, то такие состязания являются допустимыми или некритическими. Если же в этом автомате есть переход, например из a_k в a_j  a_s под действием того же сигнала x (рис.3.7,б), то автомат может перейти в a_j, а не в a_s и правильность его работы тем самым будет нарушена. Гонки, приводящие автомат в устойчивое состояние, не соответствующее закону функционирования, называются критическими.

Рис. 3.7. Состязания между элементами памяти: а – некритические, б – критические

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

4.1.1 Методы устранения гонок

В схемах на рис. 3.4 и 3.6 гонки устраняются путем ограничения длительности сигнала С, поступающего в цепь синхронизации. Этот способ устранения гонок называется способом импульсной синхронизации. Если длительность импульса t_c меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационной схеме КС1, то к моменту перехода в промежуточное состояние a_k (рис.3.7,б) сигнал С равен нулю, что и исключает гонки. Естественно, что такой способ устранения гонок приемлем только в том случае, если элементы памяти могут переключаться под действием импульсов с длительностью t_c.

Другой способ ликвидации гонок заключается в разделении во времени процессов выработки сигналов возбуждения и процесса переключения состояний. Такого рода разделение достигается использованием двойной (двухступенчатой) памяти (рис. 3.8). При использовании двойной памяти синхронизация автомата производится с помощью двух последовательностей синхронизирующих импульсов C₁ и C₂, причем C₁  C₂ = 0.

Рис. 3.8. Организация двойной памяти

Первая ступень памяти состоит из триггеров Т1, связанных с комбинационной схемой КС1 автомата, и называется памятью возбуждений. Вторая ступень состоит из триггеров Т2, с выходов которых снимаются сигналы обратной связи, определяющие текущее состояние автомата. По сигналу С₁ в комбинационной части автомата вырабатываются сигналы возбуждения , которые устанавливают триггеры Т1 памяти возбуждений в состояние, соответствующее следующему состоянию автомата. Поскольку С₂ = 0, то состояние триггеров второй ступени при этом не изменяется. По сигналу С₂ = 1 состояние Т1 переписывается в Т2, и происходит тем самым переключение автомата в новое состояние. При этом С₁ = 0 и сигналы возбуждения принимают нужные значения, тем самым исключается возможность переключения триггеров памяти возбуждений при переключении сигналов в цепи обратной связи. Следующий синхроимпульс С₁ подается через время, достаточное для окончания переходных процессов в комбинационной схеме КС1. Далее процесс повторяется.

Такой способ позволяет полностью устранить эффект состязаний, чем объясняется широкое распространение этого метода.

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

Наряду с аппаратными способами для устранения гонок используются специальные методы противогоночного кодирования состояний автомата. Некоторые из них рассмотрены в [3]. Частным случаем противогоночного кодирования является соседнее кодирование.

Гонки в автомате исключаются, если при любых переходах изменяется состояние только одного элемента памяти. Способ кодирования состояний, при котором соседние состояния автомата кодируются наборами, различающимися состоянием только одного элемента памяти, называется соседним кодированием. Пример автомата с соседним кодированием состояний приведён на рис.3.9. на каждом переходе в автомате вырабатывается только один сигнал возбуждения [9].

Рис.3.9. Граф, допускающий соседнее кодирование

Соседнее кодирование не всегда возможно. На рис. 3.10 приведены два графа, которые не могут быть закодированы соседними кодами. Сформулируем требования к графу автомата, допускающему соседнее кодирование:

• в графе автомата не должно быть циклов с нечетным числом вершин (рис. 3.10,а);

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

При этом под состояниями второго порядка понимаются два состояния, путь между которыми по графу автомата состоит из двух ребер, независимо от ориентации (рис. 3.11,б).

Рис. 3.11. Графы, не допускающие соседнего кодирования

Для использования соседнего кодирования можно преобразовать закон функционирования автомата введением пустых состояний, то есть состояний, для которых выходной сигнал отсутствует. Один из возможных алгоритмов соседнего кодирования состояний изложен в [3]. При введении пустых состояний увеличивается время выполнения операций, осуществляемых под управлением автомата.