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

Рисунок 2.1. Размеченная схема автомата типа Мили.

После разметки ГСА выполняется  описание УА с помощью расширенных таблиц переходов и выходов.

В процессе проектирования используют два типа таблиц - прямые и обратные. Оба типа таблиц содержат одинаковые переменные [5,7,8]:

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

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

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

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

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

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

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

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

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

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

a_i X(а_i, a_j) Y_k a_j                                           (2.1)

a_i Y_k a_j                                                  (2.2)

a_i X(a_i, a_j) a_j .                                             (2.3)

 

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

Для пути перехода вида (2.2) считают, что X(a_i,a_j) = 1, т.е. реализуется безусловный переход. На переходе вида (2.5) выходной сигнал полагается равным Y_o (пустой оператор). Поскольку в автоматах Мура выходной сигнал определяется текущим состоянием автомата, то рассмотрению подлежат переходы вида:

a_i X(а_i, a_j) a_j  ,                                                (2.4)

выполняемые под действием  входных сигналов X(a_i,a_j), а также переходы, являющиеся частным случаем , при входном сигнале равном 1, переходы вида:

а_i, a_j   .                                                       (2.5)

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

1. выбор типа элементов памяти;
2. кодирование состояний автомата, входных и выходных                                          сигналов в структурном алфавите;
3. детализация блока памяти;
4. составление расширенной структурной таблицы переходов и выходов;
5. канонический  синтез логического преобразователя;
6. минимизация функций выходов и возбуждения блока памяти.

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

 

 

 

 

 

 

 

Таблица 2.1 – Таблица переходов  и выходов

am	as	X(am,as)	Y(am,as)
a1	a2	x1	y1 y4 y6 y7
a1	a1	x1	y2 y3 y5 y7
a2	a7	x2	y1 y2 y4 y6 y7
a2	a3	x2x3	y2 y5 y7
a2	a4	x2x3x4	-
a3	a4	1	y2 y5 y7
a4	a5	x6	y1 y5 y6 y7
a4	a8	x6	y2 y4 y5
a5	a6	1	y3 y4 y6 y7
a6	a10	1	y1 y2 y4 y6 y7
a7	a8	x5	y2 y4 y5
a7	a3	x5x3	y2 y5 y7
a7	a4	x5x3x4	y2 y5 y7
a7	a8	x5x3x4	y2 y4 y5
a8	a8	x4	y2 y4 y5
a8	a9	x4	y2 y3 y5 y7
a9	a9	x6	y2 y3 y5 y7
a9	a6	x6	y1 y4 y6 y7

 

2. Структурное кодирование внутренних состояний УА.

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

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

b  = 1 + int ( log₂ (a -1)),                                                   

где a - мощность множества кодируемых символов абстрактного  алфавита;

   int (w) – целая часть (w).

В том случае, когда алгоритм функционирования синтезируемого автомата задан в виде граф-схемы алгоритма (ГСА), то структурного кодирования абстрактных символов входного и выходного алфавитов не производят. Это обусловлено тем, что при описании работы автомата в виде ГСА каждое логическое условие x_i = {1,0} и каждый выходной сигнал  y_j = {1,0}, то есть  уже имеют двоичное кодирование.

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

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

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

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

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

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

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

Закодированные при  помощи первого эффективного способа абстрактные символы представлены в таблице 2.2

Таблица 2.2 – Кодирование  внутренних состояний.

Абстрактные символы	Структурные коды
		d3	d2	d1	d0
	a1	0	1	1	0
	a2	1	0	1	0
	a3	0	0	1	0
	a4	0	1	0	0
	a5	0	1	0	1
	a6	1	0	0	0
	a7	0	0	1	1
	a8	0	0	0	1
	a9	1	0	0	1

 

 

3. Детализация блока памяти УА

 

Конечной целью данного  этапа является разработка схемы  электрической функциональной  блока памяти синтезируемого автомата, который должен быть реализован на выбранном (или заданном) типе триггерных схем. По сути, блок памяти представляет собой r триггеров, электрически соединённых определенным образом, или, иначе говоря, представляет одну r – разрядную ячейку памяти. В вычислительной технике такую организацию триггеров принято называть  r – разрядным регистром.

 

Для синхронных автоматов  с жесткой логикой блок памяти, как правило, строится на  комбинированных  синхронных двухтактных триггерах T, D, RS или JK. На рисунке 2.2 представлено УГО комбинированного

синхронного двухтактного D – триггера, при помощи которого нам предложено реализовывать блок памяти.

 

 

 

 

 

В таблице 2.2 представлена таблица истинности комбинированного

синхронного двухтактного D – триггера.

 

 

 

 

Таблица 2.3 – Таблица истинности комбинированного синхронного двухтактного D – триггера.

 

 

R	S	C	D	Q	Q+
0	0	0	*	0/1	0/1
0	0	­	0	0/1	0
0	0	­	1	0/1	1
0	1	*	*	0	1
0	1	*	*	1	1
1	0	*	*	0	0
1	0	*	*	1	0
1	1	*	*	0/1	*

 

 

 

 

 

 

 

 

 

 

 

В таблице 2.3 используемые символы обозначают следующее:

0/1 – нулевое или единичное  состояния входов и выходов;

* – безразличное состояние  входа или запрещенное состояние                                            выхода;

• – фронт сигнала синхронизации;

Q  – текущее состояние триггера;

Q⁺ – следующее состояние триггера. 

Особенностью комбинированных  триггерных схем является то, что наряду с наличием у них синхронно  управляемых информационных входов, присутствуют также и входы асинхронной установки S и R триггеров в единичное “1” и нулевое “0” состояния. Входы асинхронной установки триггеров обозначены на УГО отдельными от синхронных входов зонами. Входы асинхронной установки необходимы для приведения триггеров в некоторые исходные (начальные) состояния, которые в совокупности соответствуют начальному состоянию синтезируемого синхронного управляющего автомата. Сигнал, подаваемый на входы асинхронной установки триггеров для приведения их в начальные состояния, принято называть сигналом сброса (Reset) или начальной установки (Н.У.). Сигнал начальной установки должен воздействовать только на один из асинхронных входов (S или R) каждого триггера. Не задействованные для начальной установки входы триггеров должны быть подключены к дополнительному сигналу, который является постоянным и пассивным для данного типа триггера. Для представленных триггеров асинхронные сигналы S и R являются активными, если имеют уровень логической “1”, и пассивны - если имеют уровень логического “0”.