Противогоночное кодирование конечных автоматов

См. вопросы 9,10.

Существует ряд способов противогоночного кодирования, которые можно разбить на две группы:

1. Методы, позволяющие устранить все состязания. Используется “соседнее кодирование”, когда всем соседним внутренним состояниям приписывают соседние кодовые комбинации, отличающиеся значением только 1 разряда.

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

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

Задача кодирования состояний является одной из основных задач канонического метода структурного синтеза автоматов. Кодирование заключается в установлении взаимно-однозначного соответствия между множеством А = {а₁, . . . , а_М} состояний автомата и множеством R-компонентных векторов {К₁, . . . , К_М}, К_m = (е_m1, . . . , e_mR), где е_mr - состояние r-го элемента памяти, r = 1, . . . , R. Если е_mr {0, 1}, т.е алфавит состояний элементов памяти двоичный, R ] log₂M [. Далее ради простоты ограничимся использованием в качестве элементов памяти RS-триггеров, которые будем обозначать T₁, . . . , Т_R.

Переход автомата из одного состояния в другое осуществляется за счет изменения состояний элементов памяти. Так, если автомат переходит из состояния а_m с кодом 0101 в состояние а_s с кодом 1001, то это означает, что триггер Т₁ переходит из состояния 0 в состояние 1, триггер Т₂ - из состояния 1 в состояние 0, а состояния триггеров Т₃ и Т₄ не изменяются.

При функционировании автомата могут появиться так называемые состязания. Явление состязаний возникает вследствие того, что элементы памяти имеют различные, хотя и достаточно близкие, времена срабатывания. Кроме того, различны также задержки сигналов возбуждения, поступающих на входные каналы элементарных автоматов по логическим цепям неодинаковой длины. Если при переходе автомата из одного состояния в другое должны изменить свои состояния сразу несколько запоминающих элементов, то между ними начинаются состязания. Тот элемент, который выиграет эти состязания, т.е. изменить свое состояние ранее, чем другие элементы, может через цепь обратной связи изменить сигналы на входах некоторых запоминающих элементов до того, как другие участвующие в состязаниях элементы изменять свои состояния. Это может привести к переходу автомата в состояние, не предусмотренное его графом. Поэтому в процессе перехода из состояния а_m в состояние а_s под действием входного сигнала z_f (рис. 1, а) автомат может оказаться в некотором промежуточном состоянии а_k или а_l в зависимости от того, какой элемент памяти выиграет состязания. Если затем при том же входном сигнале автомат из a_k и a_l перейдет в состояние а_s, то такие состязания являются допустимыми, или некритическими. Если же в этом автомате есть переход, например, из а_k в a_j a_s под действием того же сигнала z_f (рис. 1, б), то автомат может перейти в a_j, а не в as и правильность его работы тем самым будет нарушена. Такие состязания называются критическими состязаниями или гонками. При кодировании состояний гонки должны быть устранены. Кодирование с устранением гонок называется противогоночным.

Одни из способов ликвидации гонок состоит в тактировании входных сигналов автомата импульсами определенной длительности. Предполагается, что кроме входных каналов x₁, . . . , x_L имеется еще один канал p от генератора синхроимпульсов (ГСИ), по которому поступает сигнал р = 1 в момент прихода импульса и р = 0 при его отсутствии. В связи с этим входным сигналом на переходе (a_m, a_s) будет не z_f, a pz_f. Тогда, если длительность импульса t_p меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационной схеме, то к моменту перехода в промежуточное состояние a_k (рис. 1, б) сигнал р равен нулю и, следовательно, pz_f = 0, что исключает гонки.

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

3.2. Противогоночное кодирование

3.2.1. Суть и алгоритм развязывания состояний

Пусть ( , ) и ( , ) - две пары двоичных кодов длины R. Эти пары будут называться развязанными, если при некотором I (1 i I) i-разряд кода принимает значение 1 на паре ( , ) и противоположное значение на паре ( , ). Если это не соблюдается, пары называются связанными.

Теорема. В автомате, состояние которого закодировано двоичными кодами конечной длины, гонки отсутствуют тогда и только тогда, когда для любых двух переходов (a_m, a_s) и (a_k, a_l) при a_s a_l, происходящие под действием одного и того же входного сигнала соответствующие пары развязаны.

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

Пусть (a_m, a_s) и (a_k, a_l) пары переходов автомата, а , , , - соответственно четверка кодов состояний a_m, a_s, a_k, a_l длины i.

Примечание. Четверка кодов , , , состоит из 0, 1 и Х.

Алгоритм развязывания пар:
1. Если при некотором r (1 r R) значения r-разряда четверки , , , образуют набор 0011, пара переходов считается развязанной и переходит к следующей паре.
2. Если при некотором r (1 r R) значение r-разряда четверки , , , образует один из наборов

следует доопределить неопределенные значения r-разряда четверки так, чтобы его значения образовали набор 0011. Переход к следующей паре.
3. Если при некотором r (1 r R) значение r-разряда четверки , , , образует набор 1100 , пара считается развязанной. Переход к следующей паре.
4. Если при некотором r (1 r R) значение r-разряда четверки , , , образует один из наборов

следует доопределить неопределенные значения r-разряда четверки так, чтобы его значения образовали набор 1100. Переход к следующей паре.

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

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

1. Развязывание пар переходов
Рассмотрим алгоритм противогоночного кодирования на примере автомата, функция переходов которого задана таблицей (Т. 3-1).

Пары переходов происходящих под действием сигналов z1, z2, z3 образуют массивы М1, М2, М3.
М1 = ((а1, а2), (а2, а2), (а3, а4), (а4, а4), (а5, а6), (а6, а6)).
М2 = ((а1, а1), (а2, а3), (а3, а3), (а4, а1), (а5, а3)).
М3 = ((а2, а5), (а3, а7), (а5, а5), (а7, а7)).

Начинаем развязывать пары из М1. Переход (а1, а2) с (а2, а2) развязывать не надо, т.к. состояние а2 и а2 совпадают. Пару переходов (а1, а2) и (а3, а4) будем развязывать введение переменной 1, такой как в (Т. 3-2).

Пара (а1, а2) и (а4, а4) оказываются развязанными, так как этой паре соответствует четверка 0011. Пара (а1, а2) и (а5, а6) образуют четверку 00ХХ, которую развязываем до 0011 по 2 пункту алгоритма - получаем таблицу Т. 3-3.

Теперь развязанными оказываются пары (а1, а2) и (а6, а6), (а2, а2) и (а3, а4), (а2, а2) и (а4, а4), (а2, а2) и (а5, а6), (а2, а2) и (а6, а6). Обратимся к паре (а3, а4) (а5, а6) - эта пара имеет четверку 1111. Пара неразвязанная. Введем дополнительную переменную 2.

Остальные переходы в массиве М1 оказываются развязанными.
Аналогично для М2 и М3 получим таблицы.

2. Минимизация кодов состояний
В таблице Т. 3-6 исключаем первый столбик и получаем таблицу Т. 3-7.

Начинаем повторно процесс развязывания. Оказывается, что по 2 не развязана пара (а1, а2) (а5, а6). Добавляем еще одну переменную 5.

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

В Т. 3-9 развязывание пар не требуется, так как после проверки устанавливается, что все пары оказываются развязаны. Дальнейшая минимизация невозможна, так как ]ld7[ = 3 (3 переменных, 7 состояний). После доопределения Х в таблице Т. 3-9 получаем таблицу Т. 3-10 противогоночного кодирования.

3.2.3. Соседнее кодирование состояний автомата

Существует 1 частный способ кодирования - соседнее кодирование. Условие отсутствия гонок при соседнем кодировании всегда выполняется. Суть этого кодирования состоит в том, что 2 состояния связанные дугой графа кодируются наборами, отличающимися лишь в 1 элементе памяти. Существует несколько алгоритмов, но они не всегда поддаются формализации.

Соседнее кодирование однако не всегда возможно. Требование к графу автомата, допускающего соседнее кодирование таково:
1) В графе не должно быть циклов с нечетными числом вершин.

2) 2 соседних состояния не должны иметь более двух состояний, лежащих между ними.

Дата добавления: 2015-07-26; просмотров: 209; Нарушение авторских прав

Мы поможем в написании ваших работ!