33Состязания и гонки конечных автоматов.
Q1 Q2 Qn
………
q1 q2 q3
Особенности:
1)Разная длина линий комбинационной схемы, вызывающее неодинаковое поступление ф-ией возбуждения на входы.
2)Разное время срабатывания каждого из триггеров блока памяти.
Структурный автомат у которого изм. состояний его элементов памяти происходит в момент поступления на вход ф-ии возбуждения назыв.асинхронным автоматом.Фрагмент графа асинхронного автомата:
Zk
Zk
Km=1 0 1 1
Q1Q2Q3Q4
T1T2 T3 T4
T1
быстрееT2 =>
=0011-ложный
код;
T2
быстрееT1 =>
=1111-ложный
код;
Ситуации,когда из-за неодновременного срабатывания триггеров, вызванного выше указанными причинами автомат отказывается в непредусмотренные состоянияal вместо as и под действием присутствующего на входе сигналаZkпереходит в новое состояние, наз.cсостязаниями.
Состязания:
1)Критические (гонки)- состязания, когда из непредусмотренного состояния мы переходим далее по графу и не попадаем в состояниеas.
2)Не критические –состязания, в результате которых автомат всё таки оказывается в нужном состоянииasпосле изменения состояния последнего из самых медленных триггеров.
Меры по устранению гонок в структурном автомате.
1)Направленное кодирование состояний абстрактного автомата(Превращение критических состояний в некритические).
Способы превращения:
a)Не исп-ть ложные коды для кодирования состояния.
b)Ложными кодами кодировать из которых по сигналуZk переход был бы в состояниеas.
c)Ложными кодами кодировать состояния, устойчивые относительноZk.
Во всех этих ситуациях увеличение аппаратных затрат из-за ув. рразрядности кода, которое оказывается неизбежным.
2) Cоседние кодирование соседних состояний.
Соседними состояниями наз-ся сост-я соединённые между собой дугами.Соседними кодами наз коды у кот-ых расстояние по Хэммингу(tms=1) .Расстоянием по Хэммингу между двумя разрывными кодами наз-ся число,отличающееся друг от друга разрядов кода.Такое кодирование обычно влечёт за собой избыточность разрядности кодов и все вышеизложенные проблемы.
3)Синхронизация структурного автомата.
Q1 Q2
q1 q2
Cn-Вентель
(Коньюнктор)
Автомат, в кот-ом время срабатывания триггеров определяется моментом поступления синхронизирующих импульсов называется синхронизирующим. В такой схеме очень жёсткие требования к моменту поступления и длительности сигнала. Их цель- исключить не одновременность срабатывания триггеров из-за разной длины линии в комбинационной схеме.Использование такой не даёт 100%-ное избавление от гонок.