5.1 Структурный автомат
Процесс абстрактного проектирования заключается в переходе от исходной микропрограммы (или набора микропрограмм) к одной из традиционных форм задания автомата: матричной, табличной или графической (графу). Этап перехода к заданию автомата также является необходимым, т.к. обеспечивает реализацию процесса структурного проектирования путем использования достаточно, эффективного аппарата теории конечных автоматов.
Структурное проектирование представляет собой процесс перехода от указанных выше форм задания к его функциональной схеме.
Итак, абстрактный автомат на входе имеет некоторую последовательность входных сигналов, в зависимости от которых переходит из одного состояния в другое, выдавая некоторую последовательность выходных сигналов (рис.5.1).
(рис 5.1)
В структурном автомате учитывается структура входных и выходных сигналов, то есть их конкретное представление в виде двоичных векторов. Состояния автомата так же кодируются двоичными векторами.
Рассмотрим совмещенный автомат (рис.5.2). Каждое состояние $$a_m$$ абстрактного автомата кодируется двоичным вектором:
$$a_m=(e_{m1}, e_{m2}, e_{m3} , \dots , e_{mR}), где\ e_{mi} ={0, 1}$$,
$$R>=]Log2M[, скобки ] и [ показывают,\ что\ берется\ наибольшее\ целое$$ ;
$$М$$ - число состояний абстрактного автомата;
$$R$$ - число элементов памяти.
(рис 5.2)
Входной и выходные сигналы представляются также двоичными векторами:
$$z_f=(e_{f1}, e_{f2}, e_{f3} , \dots , e_{fL}), где\ e_{fi} ={0, 1}$$, $$L>=]Log2F[ $$, $$F$$ - число входных сигналов абстрактного автомата, $$L$$ - число входов структурного автомата ;
$$w_g=(e_{g1}, e_{g2}, \dots , e_{gN}), где\ e_{gi} ={0, 1}$$, $$N>=]Log2G[ , F$$ - число выходных сигналов 1 типа, $$N$$ -число выходов 1 типа структурного автомата ;
$$u_h=(e_{f1}, e_{f2}, e_{f3} , \dots , e_{fD}), где\ e_{fi}={0, 1}$$, $$D>=]Log_2H[ , H$$ - число выходных сигналов 2 типа, $$D$$ - число выходов 2 типа структурного автомата
5.2 Канонический метод структурного синтеза автоматов
Схема структурного $$С$$ -автомата при каноническом методе синтеза представляется, состоящей из трех частей: двух комбинационных схем и памяти автомата (рис.5.3). Комбинационная схема 1 предназначена для формирования функций возбуждения $$r,$$ поступающих на входы элементов памяти, и выходных сигналов 1 типа $$Y_n$$, зависящих от входных сигналов $$x_l$$ и сигналов с выходов элементов памяти $$R$$.
(рис 5.3)
Комбинационная схема 2 предназначена для формирования выходных сигналов 2 типа $$r_h$$ как функций с выходов элементов памяти $$R$$.
Так как в автомате Мили сигналы 2 типа отсутствуют, то, соответственно в структурной схеме отсутствует комбинационная схема 2. Схема структурного автомата Мили показана на рис.5.4.
(рис 5.4)
В автомате Мура сигналы 1 типа отсутствуют, следовательно, в структурной схеме в комбинационной схеме 1 отсутствуют выходные сигналы 1 типа $$Y_n$$. Схема структурного автомата Мура показана на рис.5.5.
(рис 5.5)
Таким образом для того, чтобы синтезировать структурный автомат, необходимо синтезировать две комбинационные схемы по системе канонических уравнений. Система канонических уравнений для $$С$$ -автомата выглядит следующим образом:
$$\phi_1= \phi_1(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L)$$ ;
$$\phi_2= \phi_2(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L) $$ ;
. . .
$$\phi_R= \phi_R(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L); $$
$$y_1= y_1(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L); $$
$$y_2= y_2(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L); $$
. . .
$$y_R= y_R(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L); $$
$$r_1= r_1(\tau_1, \tau_2, \dots, \tau_R); $$
$$r_2= r_2(\tau_1, \tau_2, \dots, \tau_R);$$
. . .
$$r_R= r_R(\tau_1, \tau_2, \dots, \tau_R);$$
5.4.Этапы синтеза
Находим количество элементов памяти $$R>=]Log2M[$$, ( $$М$$ - число состояний абстрактного автомата) и кодируем состояния абстрактного автомата (табл.5.1).| am\ $$\tau_1 \tau_2 \dots \tau_R$$ |
$$\tau_1 \tau_2 \dots \tau_R$$ |
|---|
| a1 |
|
| a2 |
|
| … |
|
| aM |
|
Кодируем входные и выходные сигналы, то естьнаходим количество входов структурного автомата $$L>=]Log2F[$$, ( $$F$$ - число входных сигналов абстрактного автомата);
количество выходов 1 типа $$N>=]Log2G[$$ ;
( $$G$$ - число выходных сигналов 1 типа);
количество выходов 2 типа $$D>=]Log2H[$$,
( $$H$$ - число выходных сигналов 2 типа) и кодируем входные (табл.5.2) и выходные сигналы (табл.5.3) и (табл.5.4) абстрактного автомата.| z f / x 1 |
xL x1x2…x1 |
|---|
| z |
|
| z |
|
| … |
|
| z |
|
| wf/y 1y2…yN |
y 1y2…yN |
|---|
| w1 |
|
| w2 |
|
| … |
|
| wG |
|
| uh/r 1 r2…rD |
r 1 r2…rD |
|---|
| u1 |
|
| u2 |
|
| … |
|
| uH |
|
Структурный автомат представляем обобщенной схемой (рис 5.6(рис 5.6)
Составляем закодированную таблицу выходов автомата и по ней записываем уравнения выходов.$$y_1= y_1(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L)$$ ;
$$y_2= y_2(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L)$$ ;
. . .
$$y_R= y_R(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L)$$ ;
$$r_1= r_1(\tau_1, \tau_2, \dots, \tau_R)$$ ;
$$r_2= r_2(\tau_1, \tau_2, \dots, \tau_R)$$ ;
. . .
$$r_R= r_R(\tau_1, \tau_2, \dots, \tau_R)$$ ;
. . .
Составляем закодированную таблицу переходов автомата и по ней записываем уравнения для функций возбуждения, используя таблицы переходов соответсвующих элементов памяти.$$\varphi_1= \varphi_1(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L)$$ ;
$$\varphi_2= \varphi_2(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L)$$ ;
. . .
$$\varphi_R= \varphi_R(\tau_1, \tau_2, \dots, \tau_R, x_1, x_2, \dots, x_L)$$ ;
Уравнения функций возбуждения и выходов минимизируются (по картам Карно, например) и по ним строится схема в заданном функционально - логическом базисе ({И, ИЛИ, НЕ}, {И-НЕ}, {ИЛИ-НЕ}).
