5.4 Переход к абстрактному автоматному описанию уа

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

Этап формализации завершают составлением таблиц переходов и выходов синтезируемого УА. Для этого каким-либо образом необходимо закодировать состояния автомата формальными переменными. Чаще всего это осуществляется путем, так называемой, разметки содержательной ГСА, в которой содержательные термины заменяют формальными переменными.

Ф

55

ункционирование абстрактного автомата может быть описано с помощью двух моделей - модели Мура и модели Мили, отличающихся принципами формирования выходных сигналов и числом внутренних состояний. Переход от алгоритмического описания к автоматному осуществляется путем разметки ГСА в соответствии с выбранной моделью абстрактного автомата [ 5,7,8].

Правило разметки ГСА при реализации автомата по модели Мили:

-символом начального состояния а₁ отмечается вход вершины, следующей за начальной, а также вход конечной вершины ГСА;

-входы всех вершин, следующих за операторными, отмечаются различными символами а₂ …а_i …а_n;

-входы вершин ГСА, следующих за операторными, должны быть отмечены только одним единственным символом а_i.

Правила разметки ГСА при реализации автомата по модели Мура:

-символом начального состояния а₁ отмечаются начальная и конечная операторные вершины;

-все операторные вершины отмечаются различными символами а₂ …а_i …а_n;

-каждая операторная вершина ГСА должна быть отмечена только одним индивидуальным символом а_i.

В результате разметки ГСА по указанным правилам удается определить множество внутренних состояний УА А = { а₁, …а_i ,…а_n }, а также мощность этого множества, которая равна IАI = n.

Указанные правила разметки сформулированы для однократно выполняемых алгоритмов, при этом конечное состояние УА отождествляется с начальным состоянием. Правильная работа такого автомата гарантируется только в том случае, если до подачи синхронизирующих сигналов элементы блока памяти будут приведены в определенные исходные (начальные) состояния специальным сигналом начальной установки (НУ). Такая разновидность управляющих автоматов называется инициальными автоматами.

Д

56

ля циклически выполняемых алгоритмов за начальное состояние автомата может быть взято любое его допустимое состояние, которое выбирают произвольным образом и отмечают символом а₁. Все последующие состояния такого (не инициального) автомата отмечаются символами а₂ …а_i …а_n. В не инициальных автоматах за начальное его состояние может быть взято любое из допустимых состояний автомата. Для установки УА в выбранное начальное состояние необходимо также привести сигналом НУ элементы блока памяти в определенные исходные (начальные) состояния.

После разметки ГСА выполняется описание УА с помощью расширенных таблиц переходов и выходов.

В процессе проектирования используют два типа таблиц - прямые и обратные. Оба типа таблиц содержат одинаковые переменные [5,7,8]:

а_m - состояние УА, из которого осуществляется переход за один такт автоматного времени;

а_s - состояние УА, в которое осуществляется переход за один такт автоматного времени;

X (а_m,а_s) - логическое условие перехода из а_m в а_s;

Y (а_m,а_s) - микрокоманда (подмножество микроопераций), выполняемая на переходе из а_m в а_s (для автомата типа Мили);

Y (а_m) - микрокоманда (подмножество микроопераций), выполняемая автоматом в состоянии а_m (для автомата типа Мура).

Каждая строка таблицы соответствует одному из путей перехода из одного состояния в другое, имеющемуся в ГСА.

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

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

Рассмотрению подлежат все пути переходов от отметок а _i к а _j.

Для автоматов допустимыми являются пути вида

a_i X(а_i, a_j) Y_k a_j (5.2)

a_i Y_k a_j (5.3)

a_i X(a_i, a_j) a_j . (5.4)

Каждому пути на ГСА вида (5.2) ставится переход УА из состояния а_i в состояние а_j под действием комбинации входных сигналов X(a_i,a_j) с выдачей выходного сигнала Y_k.

Д

57

ля пути перехода вида (5.3) считают, что X(a_i,a_j) = 1, т.е. реализуется безусловный переход. На переходе вида (5.4) выходной сигнал полагается равным Y_o (пустой оператор). Поскольку в автоматах Мура выходной сигнал определяется текущим состоянием автомата, то рассмотрению подлежат переходы вида:

a_i X(а_i, a_j) a_j , (5.5)

выполняемые под действием входных сигналов X(a_i,a_j), а также переходы, являющиеся частным случаем (5.5), при входном сигнале равном 1, переходы вида:

а_i, a_j . (5.6)

В соотношениях (5.2)…(5.6) i = {1, 2…n} и j = {1, 2…n }.

Структура прямых таблиц переходов и выходов представлены таблицей 5.1 (для автомата Мили) и таблицей 5.2 (для автомата Мура).

Таблица 5.1

аm	аs	X (аm,аs)	Y (аm,аs)
…	…	…	…

Таблица 5.2

аm, Y (аm)	аs	X (аm,аs)
…	…	…

5. Структурный синтез управляющего автомата с "жесткой логикой"

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

• выбор типа элементов памяти;

• кодирование состояний автомата, входных и выходных сигналов в структурном алфавите;

• детализация блока памяти;

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

• канонический синтез логического преобразователя;

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

58