Составные части абстрактного автомата. Способы задания автоматов. Синхронные и асинхронные автоматы. Минимизация полностью определенного автомата. Структурная теория. Канонический метод структурного синтеза автомата. Кодирование состояний автомата. Гонки в автомате. Противогоночное кодирование состояний автомата, страница 4

Один из способов ликвидации гонок – тактирование входного сигнала импульсами определенной длительности. Вводится вход синхронизации и подаются синхроимпульсы.

Другой способ – дублирование памяти. Для каждого элемента памяти вводится дублер.

Противогоночное кодирование состояний автомата

Устранение гонок в а автомате возможно на этапе кодирования состояний – противогоночное кодирование.

Группы способов противогоночного кодирования:

a.  устраняющие все состязания (используется соседнее кодирование состояний автомата, все соседние состояния отличаются друг от друга значением одного разряда кода состояния. Однако не для любого автомата может быть обеспечено соседнее кодирование. Оно возможно, если граф автомата является подграфом  - мерного куба. Если в графе автомата имеется контур нечетной длины, то закодировать состояния такого автомата соседним кодированием невозможно)

b.  осуществляющие кодирование, допускающее некритические состязания

Устранение критических состязаний

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

Теорема:

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

Если  и  пары переходов автомата, а  - наборы соответствующих состояний длины , то развязка происходит следующим образом:

1) 

2)  если , то переход к пункту 3), иначе к пункту 8)

3)  если при некотором  значение  - разряда наборов  образуют набор 0011 или 1100, то переход к пункту 10), иначе к пункту 4)

4)  если при некотором  значение  - разряда наборов  образуют один из наборов

то переход к пункту 5), иначе к пункту 6)

5)  доопределить неопределенные значения  - разряда  так, чтобы его значения образовали набор 0011 и перейти к пункту 10)

6)  если при некотором  значение  - разряда наборов  образуют один из наборов

-100

1-00

11-0

110то переход к пункту 7), иначе к пункту 8)

7)  доопределить неопределенные значения  - разряда  так, чтобы его значения образовали набор 1100 и перейти к пункту 10)

8)  дополнить коды состояний автомата одним неопределенным разрядом

9)  , переход к пункту 3)

10) Конец

Длина может быть не минимальной. Следовательно необходимо минимизировать длину кодов состояний. Исключаем один из разрядов кодов состояний, в результате некоторые пары переходов могут быть не развязаны. Применим алгоритм развязывания снова до тех пор, пока длина не перестанет уменьшаться.

Формирование функций выходов и функций возбуждения памяти автомата

§  для  – триггера