j1 = j1 (t1 , ... , tR , x1 , ... , xL)
j2 = j2 (t1 , ... , tR , x1 , ... , xL)
.
.
.
jR = jR (t1 , ... , tR , x1 , ... , xL)
Функция j =(j1, j2 , ...,jR ) называется функцией возбуждения памяти автомата. Метод получения функций возбуждения и функций выходов автомата рассматривается в разделе 3.4.
3.3 Противогоночное кодирование состояний автомата
При работе автомата могут появиться состязания. Состязания возникают вследствие того, что элементы памяти имеют различные времена срабатывания. Кроме того, различны также задержки сигналов возбуждения, поступающих на входные каналы элементарных автоматов по логическим цепям. Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания. Тот элемент, который выиграет эти состязания, то есть изменит свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие участвующие в состязаниях элементы изменят свои состояния. Это может привести к переходу автомата в непредусмотренное таблицей переходов состояние. Поэтому в процессе перехода из состояния am в состояние as под действием входного сигнала xi автомат может оказаться в некотором промежуточном состоянии ak или aL , в зависимости от того, какой элемент памяти выиграет состязания. Если затем, при том же входном сигнале xi , автомат из ak и aL перейдет в состояние as , то такие состязания являются допустимыми. Если же в этом автомате есть переход, например, из ak в aj ¹ as , под действием сигнала xi , то автомат может перейти в aj , а не в as , и правильность его работы тем самым будет нарушена. Такие состязания называются гонками. При кодировании состояний гонки должны быть устранены. Кодирование с устранением гонок называются противогоночным.
Рассмотрим алгоритм противогоночного кодирования состояний.
Пусть (a,b) и (g,d) - две пары двоичных кодов длины I. Пары (a,b) и (g,d) называются развязанными, если при некотором i (1≤ i≤ I) i-й разряд кода принимает одно значение на паре (a,b) и противоположное - на паре (g,d). В автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют тогда и только тогда, когда для любых переходов (an , as) и (ak , al) as¹ al , происходящих под действием одного и того же входного сигнала, соответствующие пары кодов состояний развязаны.
Алгоритм противогоночного кодирования заключается в последовательном развязывании пар переходов, для которых имеется хотя бы один общий входной сигнал, осуществляющий эти переходы. На промежуточных этапах алгоритма состояниям автомата будут соответствовать коды, значения некоторых разрядов которых могут быть не определены. Такие коды будем называть неполными. Неопределенные разряды будем отмечать черточкой.
Пусть (am,as), (ak,al) - пара переходов автомата S, а a, b, g, d - соответственно четверка кодов (возможно, неполных) состояний am, as, ak, al длины i. Операция развязывания пары переходов (am,as) , (ak,al) сводится к следующему:
1. Положить i=0.
2. Если i=0, то переход к п.8, иначе переход к п.3.
3. Если при некотором r (1≤ r < i) значения r-го разряда четверки a, b, g, dобразуют набор 0011 или набор 1100, то переход к п.9, иначе переход к п.4.
4. Если при некотором r (1≤ r ≤ i) значения r-го разряда четверки a, b, g, dобразуют один из наборов:
-011, - - 11, - - - 1, 0 - 11, 0 - - 1, 0 - - -, 00 - 1, 00 - - , - 0 - -,
001 - , - 0 - 1, - - 1 -, 01 - 0, 0 - 1 -, - - - -, то переход к п.5, иначе переход к п.6.
5. Доопределить неопределенные значения r-го разряда четверки a, b, g, d так, чтобы его значения образовали набор 0011. Переход к п.9.
6. Если при некотором r (1≤ r ≤i) значения r-го разряда четверки a, b, g, dобразуют один из наборов:
-100, - - 00, - - - 0, 1 - 00, 1 - - 0, 1 - - - , 11 - 0, 11 - - , - 1 - -, 110 -, - 1 - 0,
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.