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

 

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

 

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

 

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

 

 

6. Структурный синтез управляющего автомата со схемной реализа­цией логики управления.