2.2. Гонки в автомате

2.2.1. Кодирование состояний

Задача кодирования состояний является одной из первых задач канонического метода структурного синтеза автоматов. Напомним, что кодирование заключается в установлении взаимно однозначного соответствия между множеством А = {а₁,…,а_N} состояний автомата и множеством r-компонентных векторов {К₁,…, К_m), К_m= (е_m1,…,e_mr}, где е_mr - состояние r-го элемента памяти, r = 1,…,m.

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

2.2.2. Понятие о гонках. Противогоночное кодирование

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

Если затем при том же входном сигнале автомат из а_k и а_l перейдет в состояние а_{S ,} то такие состязания являются допустимыми, или некритическими. Если же в этом автомате есть переход, например, из а_k в а_j ≠ a_S, под действием того же сигнала Z, то автомат может перейти в а_j, а не в а_S, и правильность его работы тем самым будет нарушена. Такие состязания называются критическими состязаниями или гонками. При кодировании состояний гонки должны быть устранены. Кодирование с устранением гонок называется противогоночным.

Один из способов ликвидации гонок состоит в тактировании входных сигналов автомата импульсами определенной длительности. Предполагается, что кроме входных полюсов x₁,…,x_l имеется еще один полюс р от генератора синхроимпульсов (ГСИ), по которому поступает сигнал р = 1 в момент прихода импульса и р = 0 при его отсутствии. В связи с этим на переходе (а_m, а_S) входным сигналом будет не z, а рz. Тогда, если длительность импульса меньше самого короткого пути прохождения тактированного сигнала обратной связи по комбинационной схеме, то к моменту перехода в промежуточное состояние а_k сигнал р равен нулю и, следовательно, рz = 0, что и исключает гонки.

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

Таким образом, состязания могут возникнуть только между нижними триггерами, сигналы обратной связи не смогут измениться до тех пор, пока р не станет равным нулю. Но тогда входной сигнал рz_f также равен нулю, а потому гонок быть не может.

Наряду с аппаратурными способами для устранения гонок могут использоваться специальные методы кодирования, которым посвящено большое число работ. Например, предлагается метод противогоночного кодирования, основная идея которого сводится к следующему: пусть (a,b) и (c,d) - две пары двоичных кодов длиной m. Пары (a,b) и (c,d) называются развязанными, если при некотором 1 ≤ r ≤ m r-й разряд кода принимает одно значение на паре (a,b) и противоположное на паре (c,d). В противном случае пары двоичных кодов (a,b) и (c,d) называются связанными.

Доказана следующая теорема.

В автомате, состояния которого закодированы двоичными кодами конечной длины, гонки отсутствуют, если для любых двух переходов (аm,…,аs) и (аk,…,al), аs ≠ аl, происходящих под действием одного и того же входного сигнала, соответствующие пары кодов состояний развязаны.

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

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

Таким образом, имеются 4 способа устранения гонок:

• двойная память;

• рациональный выбор длительности синхроимпульса;

• развязывание пар переходов;

• соседнее кодирование.