Синтез синхронного управляющего автомата (стр. 3 из 7)

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

Описание автомата на абстрактном уровне позволяет осуществить анализ его функционирования без учёта конкретно реализуемых функций и V

условии.

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

состоянии.

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

Модель Мура.

Закон функционирования автомата типа Мура математически задается следующей системой уравнений (1):

(1)

где

a(t) – внутреннее состояние автомата в момент времени t (настоящий момент времени);

z (t) – входной сигнал в момент времени t;

w (t) – выходной сигнал в момент времени t;

a (t+1) - внутреннее состояние автомата в момент времени (t+1) (в следующий момент времени);

δ - функция переходов;

λ - функция выходов.

Первое уравнение в (1) отражает тот факт, что переход автомата в следующее состояние a(t+1) осуществляется только с приходом входного сигнала (входного символа) z(t) в момент времени t. При этом, то конкретное состояние, в которое перейдет автомат в момент времени (t+1), определятся парой (a_m, z_f), т.е. состоянием автомата a(t) и входным сигналом (символом) z(t) в момент времени t. Функция переходов в автомате типа Мура имеет такой же вид, как и для автомата типа Мили со всеми рассмотренными ранее особенностями математической и технической корректности модели.

Второе уравнение в (1) отражает закономерность формирования выходного сигнала (символа) автоматом типа Мура. Из уравнения видно, что выходной сигнал определяется только состоянием автомата в момент времени t и в явном виде не зависит от входного сигнала z(t). Соответствующий состоянию a(t) выходной сигнал в автомате Мура формируется на всем протяжении времени, пока автомат находится в состоянии a(t). В связи с данной особенностью автомата типа Мура говорят, что данный тип автомата формирует "длинные" выходные сигналы, которые однозначно определяются тем состоянием автомата, в котором он находится в данный момент времени.

Не смотря на то, что состояние выхода автомата Мура не зависит явно от состояния входа, его можно рассматривать как частный случай автоматов Мили. Действительно, так как для автоматов Мура справедливо

a(t) = δ (a(t-1), z(t-1)), (2)

то справедливо и следующее соотношение:

w(t) = λ (a(t)) = g (a(t-1), z(t-1)). (3)

Соотношение (2) показывает, что в автомате Мура выходной сигнал реально зависит от входного сигнала, но только действующего в предыдущий момент времени. Различие между автоматами Мура и Мили состоит в том, что в автоматах Мили выходной сигнал возникает одновременно с вызывающим его входным сигналом, а в автоматах Мура - с опозданием (задержкой) на один такт автоматного времени. Поэтому автоматы Мура можно рассматривать как автоматы Мили, имея в виду, что последовательность состояний выхода автомата Мили опережает на один такт последовательность состояний выхода автомата Мура.

В теории автоматов доказано, что между автоматами Мили и Мура существует взаимооднозначное соответствие: любой автомат Мили может быть преобразован в эквивалентный ему автомат Мура и наоборот.

При переходе от автомата Мура к автомату Мили число состояний автомата не меняется, тогда как при обратном переходе число состояний в автомате Мура, как правило, возрастает. Таким образом, эквивалентные между собой автоматы могут иметь различное число состояний, в связи с чем в теории автоматов возникает задача нахождения минимального (с наименьшим числом состояний) автомата в классе эквивалентных между собой автоматов.

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

5. Анализ граф _- схемы алгоритма синтезируемого управляющего .,

автомата и детализация его структурной схемы.

5.1 Анализ и разметка граф - схемы алгоритма.

Переход от алгоритмического описания к автоматному осуществляется путём разметки ГСА.

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

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

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

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

Указанные правила разметки сформулированы для однократно выполняемых алгоритмов, при этом конечное состояние УА отождествляется с начальным состоянием.

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

По приведённым выше правилам, произведём разметку заданной граф - схемы алгоритма (рисунок 6).

Рис. 6

В результате разметки ГСА определим множество внутренних

состояний управляющего автомата: А= {а₁...а₁₁}, а также мощность этого множества: |A|=n=11.

5.2 Описание управляющего автомата с помощью таблиц переходов и выходов.

По разметке ГСА (рисунок 6) составим прямую таблицу переходов и выходов.

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

Таблица содержит следующие переменные:

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

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

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

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

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

Структура прямой таблицы переходов и выходов представлена таблицей 2.

Таблица 2

am, Y(am)	as	X(am, as )
а1, Y2	а2	x1x2
а1, Y3	a4	х1 2
а1, Y8	a6	1
а2, Y4	а3	x4
а2, Y5	a5	x3 4
а2, Y8	а1	4 3x5x6
а2, Y7	a1	4 3x5 6
a2, Y6	a11	4 3 5
a3, Y8	a1	1
a4, Y5	a5	X3
a4, Y8	а1	3x5x6
a4, Y7	a1	3x5 6
a4, Y6	a11	3 5
a5, Y8	a1	1
a6, Y2	a7	x3
a6, Y3	a8	3
a7, Y4	a9	1
a8, Y4	a9	x2
a8, Y5	a10	2
a9, Y6	a11	1
a10, Y6	a11	1
a11, Y7	a1	1