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

После разметки ГСА выполняется описание СУА с помощью таблиц переходов и выходов. В процессе проектирования используют два типа таблиц - прямые и обратные. Оба типа таблиц содержат одинаковые переменные [5]:

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

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

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

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

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

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

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

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

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

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

ai X(аi, aj) Yk aj (2)

a_i Y_k a_j (3)

a_i X(a_i, a_j) a_j (4)

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

Для пути перехода вида (3) считают, что X(a_i,a_j) = 1, т.е. реализуется безусловный переход. На переходе вида (4) выходной сигнал полагается равным Y_o(пустой оператор).

Для заданного автомата по выполненной разметке построена прямая таблица переходов и выходов (Таблица 1).

Таблица 1 -Таблица переходов и выходов:

am	as	x	y			am	as	x	y
a1	a2		y3			a6	a6	x6	y1
	a3	x1	y6				a9		y2
a2	a3 a7	x2	y4 y2			a7	a3	x3	y4
a3	a1	x5	-				a8		y3
	a4		y7			a8	a6	x4	y5
a4	a5		y8				a7		-
	a4	x1	y7			a9	a1	1	y1
a5	a6	x2	y1
	a8		-

2.4 Структурное кодирование внутренних состояний суа

В настоящее время самым распространенным способом структурного кодирования является двоичное кодирование. Структурное кодирование проводится в два этапа: определяется количество () двоичных разрядов, необходимое и достаточное для двоичного представления некоторого множества абстрактных символов; осуществляется сопоставление каждому отдельному абстрактному символу- разрядного двоичного кода.

В самом простейшем случае величина находится на основе следующего соотношения:

(5)

где |А| - мощность множества кодируемых символов абстрактного алфавита; int– целая часть.

Для исходного СУА величина = 4. Это говорит о том, что для структурного кодирования каждого абстрактного символа потребуется четыре разряда.

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

- тривиальное кодирование;

- эффективное кодирование (1-й способ);

- эффективное кодирование (2-й способ).

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

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

При эффективном кодировании по первому количество двоичных разрядов, необходимое и достаточное для структурного кодирования состояний автомата, определяется соотношением (5). Затем по таблице переходов, графу автомата или расширенной таблице переходов определяется количество вхождений в каждое из состояний автомата (например, из графы а_s в Таблицах 5.1 и 5.2). Состояния автомата, т.е. соответствующие им символы абстрактного алфавита, упорядочиваются в порядке убывания числа вхождений в каждое состояние. То состояние автомата, в которое имеется максимальное число вхождений, кодируется двоичным кодом, содержащем одну единственную единицу в каком – либо двоичном разряде. Последующие состояния автомата кодируются кодами, также содержащими одну единственную единицу, но отличающимися между собой. По мере исчерпания таких кодов для кодирования используются структурные коды, содержащие по две единицы в каких – либо разрядах. Эти коды также должны быть различны между собой. Затем используются структурные коды, содержащие по 3, 4 … единицы, до тех пор, пока все состояния автомата не окажутся закодированными.

Найденный структурный код начального состояния автомата используется для определения соответствующих асинхронных входов RиS, которые должны быть объединены и подключены к сигналу начальной установки.

Закодированные по первому эффективному способу абстрактные символы представлены в Таблице 2.

Таблица 2 - Таблица кодирования состояния при использовании первого эффективного метода:

	d3	d2	d1	d0	кол-во вхождений
a3	0	0	0	1	3
a6	0	0	1	0	3
a1	0	1	0	0	2
a4	1	0	0	0	2
a7	0	0	1	1	2
a8	0	1	1	0	2
a2	0	1	0	1	1
a5	1	0	1	0	1
a9	1	1	0	0	1

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

Таблица 3 – Таблица кодирования состояния при тривиальном кодировании:

	d3	d2	d1	d0
a1	0	0	0	1
a2	0	0	1	0
a3	0	1	0	0
a4	1	0	0	0
a5	0	0	1	1
a6	0	1	1	0
a7	1	1	0	0
a8	1	0	0	1
a9	1	0	1	0