Построение абстрактных автоматов по граф-схеме микропрограммы

4.1 Переход от ГСА МП к графу абстрактного автомата Мили

Переход осуществляется в два этапа. На первом этапе производится определение числа состояний путем разметки и отметки граф-схемы; на втором - определение графа автомата.

Правила разметки:

Символом $$а_1$$ помечаем вход вершины следующей за начальным оператором в ГСА и вход конечной вершины. (рис.4.1,а).

Символами $$а_2, а_3, а_4,\dots$$ - входы вершин, следующих за операторными вершинами (рис.4.1,б).

(рис 4.1)

Если в результате разметки оказалось, что в одну и ту же вершину граф-схемы входит несколько размеченных стрелок, то им присваивается один и тот же символ. В дальнейшем символ $$а_1$$ рассматривается как начальное состояние автомата, а символы $$а_j$$ - как промежуточные состояния автомата. Таким образом, число состояний автомата опреде-ляется числом различающихся символов $$a_1, a_j, \dots, a_k$$

Переход от отмеченных граф-схем к графу автомата осуществ-ляется в следующем порядке.

Вершинами графа изображаются все состояния автомата и внутри кружков записываются символы $$a_1, \dots, a_k$$, то есть существующие метки на ГСА.

На граф-схеме микропрограммы отыскивается путь между двумя соседними состояниями $$a_m$$ и $$a_s$$. Пути отображаются дугами. Возможно существование путей трех видов:

Если этот путь содержит логические условия, то дуга, связывающая вершины $$a_m$$ и $$a_s$$ графа автомата, отмечается логической функцией $$X(a_m,a_s)$$, значение которой определяет переход автомата из состояния $$a_m$$ в состояние $$a_s$$ и оператором $$Y_i,$$ находящимся на пути между $$a_m$$ и $$a_s$$ (рис 4.2(рис 4.2)

Если этот путь содержит логические условия, то дуга, связывающая вершины $$a_m$$ и $$a_s$$ графа автомата, отмечается логической функцией, значение которой определяет переход автомата из состояния $$a_m$$ в состояние as и если на пути между $$a_m$$ и $$a_s$$ отсутствует операторная вершина, то этот факт отмечается символом '-' или символом $$Y_0$$ ( пустой оператор, пропуск такта) (рис 4.3(рис 4.3)

Если этот путь не содержит логические условия, то есть существует безусловный переход, то это путь третьего вида. Такой переход обозначается "1" вместо логической функции и оператором $$Y_i,$$ находящимся на пути между $$a_m$$ и $$a_s$$ (рис.4.4).

(рис 4.4)

Построение графа автомата Мили по ГСА микропрограммы рассмотрим на примере ГСА, представленной на рис.4.5.

На первом этапе выполним разметку согласно указанным выше правилам. Получаем пять меток, выделенных красными крестиками на рис.4.5.

(рис 4.5)

На втором этапе строим граф автомата Мура. Имеем пять вершин графа соответствующих пяти состояниям.

По ГСА находим все пути между соседними метками. Так из метки $$а_1$$ в метку $$а_2$$ существует путь третьего типа, то есть безусловный переход. Этот путь проходит через операторную вершину, отмеченную сигналом $$Y_1$$, который выносится на дугу перехода из состояния $$а_1$$ в состояние $$а_2$$.

Рассмотрим пути, идущие от метки $$а_2$$. Всего их три. Первый путь из $$а_2$$ в $$а_3$$ проходит через условную вершину $$х_1$$ и операторную вершину $$Y_4$$, то есть это путь первого вида, соответствующий переходу из состояния $$а_2$$ в состояние $$а_3$$ по условию $$х_1$$ с выработкой выходного сигнала $$Y_4$$. Второй путь из $$а_2$$ в $$а_5$$ проходит через условные вершины $$х_1$$ и $$х_2$$ и операторную вершину $$Y_2$$, то есть это путь первого вида, соответствующий переходу из состояния $$а_2$$ в состояние $$а_5$$ по условию $$х_1х_2$$ с выработкой выходного сигнала $$Y_2$$.

Третий путь из $$а_2$$ в $$а_5$$ проходит через условные вершины $$х_1$$ и $$х_2$$, и не проходит ни через какую операторную вершину, то есть это путь второго вида, соответствующий переходу из состояния $$а_2$$ в состояние $$а_5$$ по условию $$х_1х_2$$ без выходного сигнала.

Рассмотрим пути, идущие от метки $$а_3$$. Всего их два. Первый путь из $$а_3$$ в $$а_4$$ проходит через условную вершину $$х_3$$ и операторную вершину $$Y_5$$, то есть это путь первого вида, соответствующий переходу автомата из состояния $$а_3$$ в состояние $$а_4$$ по условию $$х_3$$ с выработкой выходного сигнала $$Y_5$$. Второй путь из $$а_3$$ в $$а_1$$ проходит через ту же условную вершины $$х_1$$ и не проходит ни через какую операторную вершину, то есть это путь второго вида, соответствующий переходу из состояния $$а_3$$ в состояние $$а_1$$ по условию $$х_3$$ без выходного сигнала.

Из метки $$а_4$$ также существует два пути и оба второго типа без выходного сигнала: из $$а_4$$ в $$а_1$$ соответствующий переходу из состояния $$а_4$$ в состояние $$а_1$$ по условию $$х_4$$ ; из $$а4$$ в $$а5$$ соответствующий переходу из состояния $$а_4$$ в состояние $$а_5$$ по условию $$х_4$$.

Из $$а_5$$ существует один путь в $$а_4$$ третьего вида, проходящий через операторную вершину $$Y_3$$.

Результат построенного абстрактного автомата Мили показан на рис.4.6.

(рис 4.6)

Если мы переобозначим сигналы на дугах, например заменив $$Y_1$$ на $$w_1$$, $$Y_2$$ на $$w_2$$ и т.д., а $$x_1x_2$$ на $$z_1$$, $$x_1 x_2$$ на $$z_2$$, и т.п., то получим абстрактный автомат Мили в привычном виде.

4.2 Переход от ГСА МП к графу абстрактного автомата Мура

Переход осуществляется так же в два этапа. На первом этапе производится определение числа состояний путем разметки и отметки граф-схемы; на втором - определение графа автомата.

Правила разметки:

Символом $$а_1$$ помечаем начальную и конечную вершины ГСА микропрограммы.

Символами $$а_2, а_3, а_4,\dots$$ помечаем операторные вершины, (рис 4.7(рис 4.7)

Разные вершины ГСА должны быть помечены разными метками.

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

В результате анализа разметки видим, что между парами меток имеем пути второго и третьего вида. Каждому пути ставим соответствующий переход.

Построение автомата Мура рассмотрим на примере ГСА МП, представленной на рис.4.8.

(рис 4.8)

На первом этапе выполним разметку согласно указанным выше правилам. Получаем шесть меток (рис.4.8).

На втором этапе строим граф автомата Мили. Имеем шесть вершин графа соответствующих шести состояниям. Внутри каждой вершины записываем соответствующий выходной сигнал.

По ГСА находим все пути между соседними метками. Так из метки $$а_1$$ в метку $$а_2$$ существует один путь третьего типа, то есть безусловный переход. Этот путь изображается дугой перехода из состояния $$а_1$$ в состояние $$а_2$$.

Рассмотрим пути, идущие от метки $$а_2$$. Всего их три. Первый путь из $$а_2$$ в $$а_3$$ проходит через условную вершину $$х_1,$$ то есть это путь второго вида, соответствующий переходу из состояния $$а_2$$ в состояние $$а_3$$ по условию $$х_1$$. Второй путь проходит через условные вершины $$х_1$$ и $$х_2$$, то есть это тоже путь второго вида, соответствующий переходу из состояния $$а2$$ в состояние $$а_4$$ по условию $$х_1х_2$$. Третий путь из $$а_2$$ в $$а_5$$ проходит через условные вершины $$х_1$$ и $$х_2$$, то есть это путь второго вида, соответствующий переходу из состояния $$а_2$$ в состояние $$а_5$$ по условию $$х_1х_2$$. Результат построенного абстрактного автомата Мили показан на рис. рис.4.9/

(рис 4.9)

4.3 Абстрактный С-автомат (совмещенный автомат)

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

(рис 4.10) $$\lambda : A \times Z\to W (w_s= \lambda (a_m, z_i)/ a_s \in A, w \in W),$$

В автомате Мура выходной сигнал зависит только от состояния, и выдается все то время, когда автомат находится в этом состоянии (рис.4.10,б):

$$\lambda : A \to W (w_s= \lambda (a_m)/ a_s \in A, w \in W),$$

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

$$S=\lbrace A, Z, W, U, \delta, \lambda_1, \lambda_2, а_1 \rbrace,$$

где $$A=\{ a_1, a_2, a_3,\dots ,a_m\}$$ - множество состояний автомата;

$$Z=\{ z_1, z_2, z_3, \dots z_f\}$$ - множество входных сигналов;

$$W=\{ w_1, w_2, w_3, \dots w_g\}$$ - множество выходных сигналов 1 рода;

$$U=\{ u_1, u_2, u_3, \dots u_h\}$$ - множество выходных сигналов 2 рода;

$$\delta : A \times Z \to A ( a_s=\delta ( a_m, z_f) | a_s \in А );$$ $$\lambda_1 : A \times Z \to W ( w_g= \lambda_1( a_m, z_f) | a_s \in А, w_g \in W );$$ $$\lambda_2 : A \to U ( u_h= \lambda_2( a_m) | u_h \in U );$$ $$a1 \in А$$

При графическом задании $$C$$ - автомата на переходах указываются выходные сигналы 1 рода $$w_g$$, а в вершинах выходные сигналы 2 рода $$u_h$$ (рис.4.11).

(рис 4.11)

Явное задание $$С$$ - автомата требует описание всех составляющих и выполняется так же как и для автоматов Мили и Мура.

Табличное задание $$С$$ - автомата состоит в представлении работы автомата двумя таблицами: таблицей переходов (табл.4.1) и таблицей выходов (табл.4.2), в которой в отличие от автомата Мили в верхней строке добавляются сигналы второго рода.

z\a	a1	a2	a3
z1	a 3	a 1	a 1
z2	a1	a3	a2

\uh	u1	u3	u2
z\a	a1	a2	a3
z1	w1	w1	w2
z2	w1	w2	w1

Матричное задание $$С$$ - автомата состоит в описании двумя матрицами аналогично матричному представлению автоматов Мили и Мура.

$$C= \left|\left|\begin{array}{ccc} z_2/\omega_1 - z_1/\omega_1 \\ z_1/\omega_1 - z_2/\omega_2 \\ z_2/\omega_2 z_1/\omega_1 - \end{array}\right|\right|, W= \left|\left|\begin{array}{c} u_1 \\ u_3 \\ u_2 \end{array}\right|\right|$$