Проектирование конечных автоматов

Проектирование автоматов с памятью содержит следующие этапы:

1. исходное задание функционирования;

2. формализованное задание функционирования;

3. минимизация состояний;

4. определение минимально-необходимого числа внутренних элементов памяти;

5. кодирование состояний;

6. построение кодированных таблиц переходов и выходов;

7. определение функций возбуждения элементов памяти;

8. минимизация функций возбуждения триггеров и функций выходов;

9. переход к базису, выбранному для реализации автомата;

10. составление логической схемы автомата;

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

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

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

Рассмотрим аппаратную реализацию автоматов на примере автомата моделирующего умное поведение родителя.

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

Алгоритм поведения родителя: если сын получит одну двойку – отец его будет успокаивать, если две двойки подряд – ругать, если три двойки - возьмется за ремень. Если сын получит пятерку – отец его похвалит, если две пятерки подряд – сына ждет вознаграждение. Если сын получит двойку, а затем пятерку, т.е. 2, 5, отец выразит надежду, что в дальнейшем сын будет получать только хорошие оценки. Тоже самое сделает отец, если сын получит 2, 2, 5. Если сын получит сначала пятерку, а затем двойку, т.е. 5, 2 – отец будет успокаивать сына. Такое же поведение отца будет, если сын получит 2, 2, 5, 2.

Формализованное задание функционирования автомата. По словесному описанию алгоритма строим таблицу переходов (ТП) и таблицу выходов (ТВ). Этот автомат имеет два входных сигнала – оценки, полученные сыном в школе (2 и 5), следовательно, ТП и ТВ будут содержать две строки. Число столбцов неизвестно и его требуется определить. Введем начальное состояние автомата S 0. Начиная с начального состояния S 0, автомат под действием входных сигналов переходит из одного состояния в другое и выдает выходные сигналы – реакции на входы. Выходы автомата будем интерпретировать как действия родителя так:

Y0 – берет ремень;

Y1 - ругает сына;

Y2 – успокаивает сына;

Y3 – выражает надежду;

Y4 – хвалит сына

Y5 – дает вознаграждение.

В таблицах переходов и выходов появляется один столбик и две клетки, которые надо заполнить (табл.5.4, 5.5).

Таблица 5.4. Таблица переходов Таблица 5.5. Таблица выходов

Входной сигнал	Состояние автомата		Входной сигнал	Состояние автомата
	S 0	S 1	S 2	S 3			S 0	S 1	S 2	S 3
двойка	S 1	S 3	S 1	S 3		двойка	Y2	Y1	Y2	Y0
пятерка	S 2	S 0	S 2	S 0		пятерка	Y4	Y3	Y5	Y3

 

Рассмотрим клетку на пересечении столбца S 0 и строки «двойка». Так как сын получил двойку, то это состояние должно сохраняться до тех пор, пока не будет получена вторая оценка. Поэтому в этой клетке таблицы переходов проставляется устойчивое состояние S 1, а в таблице выходов - выходной сигнал Y2.

Рассмотрим теперь клетку на пересечении столбца S 0 и строки «пятерка». Сын получил пятерку и это состояние должно сохраняться до тех пор, пока не будет получена следующая оценка. Следовательно, в таблице переходов проставляется новое устойчивое состояние S 2, а в таблице выходов, соответственно, выходной сигнал – Y4.

Рассмотрим клетку на пересечении столбца S 1 и строки «двойка». Сын получил две двойки подряд и это состояние должно сохраняться до получения следующей оценки, следовательно, в эту клетку в таблице переходов проставляется новое устойчивое состояние S 3, а в таблице переходов Согласно алгоритму выходной сигнал Y1.

Рассмотрим клетку на пересечении столбца S 1 и строки «пятерка». Сын после двойки получает пятерку. Для запоминания этого факта можно ввести новое состояние автомата. Однако это состояние можно отождествить с начальным состоянием автомата, поэтому в соответствующую клетку таблицы переходов проставляется состояние S 0, а в таблице выходов - выходной сигнал Y3.

Рассмотрим клетку на пересечении столбца S 2 и строки «двойка». После пятерки сын получает двойку. В этом случае автомат из состояния S2 переходит в состояние S1. Поэтому в клетке таблицы переходов проставляется состояние S 1, а в таблице выходов – выходной сигнал Y2.

Рассмотрим клетку на пересечении столбца S 2 и строки «пятерка». Сын получил подряд две пятерки. Для запоминания этого факта можно ввести новое состояние автомата. Однако это состояние можно отождествить с существующим состоянием автомата S 2. Следовательно, в этом случае автомат из состояния S 2 переходит в состояние S 2. Поэтому в клетке таблицы переходов проставляется состояние S 2, а в таблице выходов – выходной сигнал Y5.

Рассмотрим клетку на пересечении столбца S 3 и строки «двойка». Сын получает третью двойку подряд. Для запоминания этого факта можно ввести новое состояние автомата. Однако это состояние можно отождествить с существующим состоянием автомата S 3. Следовательно, в этом случае автомат из состояния S 3 переходит в состояние S 3. Поэтому в клетке таблицы переходов проставляется состояние S 3, а в таблице выходов – выходной сигнал Y0.

Рассмотрим клетку на пересечении столбца S 3 и строки «пятерка». Сын после двух двоек получает пятерку. В этом случае автомат из состояния S 3 переходит в состояние S 0, т.к. возникшая ситуации эквивалентна ситуации 2,5. Поэтому в клетке таблицы переходов проставляется состояние S 0, а в таблице выходов – выходной сигнал Y3. На этом процесс построения ТП и ТВ заканчивается.

Процесс построения ТП и ТВ завершается, когда все новые состояния, которые вводятся при рассмотрении незаполненных еще клеток ТП, можно отождествить с ранее введенными. При этом необходимо стремиться к минимальному числу столбцов, так как от последних зависит число элементов памяти, необходимых для построения автомата.

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

Рисунок 5.5. Граф автомата, описывающий поведение отца

Определение минимально-необходимого числа внутренних элементов памяти. После того, как построена таблица переходов и установлено число ее столбцов (обозначим это число r), можно определить число элементов памяти, необходимое для построения автомата

,

где - обозначение ближайшего к a большего целого числа.

В нашем примере требуется внутренних элементов памяти.

Кодирование состояний. Автомат имеет два входных сигнала, закодируем их так:

«2» ® «0»;

«5» ® «1».

Выходных сигналов шесть, закодируем их

«Y0» ® «000»:

«Y1» ® «001»;

«Y2» ® «010»;

«Y3» ® «011»:

«Y4» ® «100»;

«Y5» ® «101».

Внутренних состояний у автомата четыре. Закодируем их

«S0» ® «00»;

«S1» ® «01»;

«S2» ® «10»;

«S3» ® «11».

Структурная схема этого автомата после двоичного кодирования имеет следующий вид (рис.5.6):

Рисунок 5.6 Структурная схема автомата

Построение кодированных таблиц переходов и выходов. Два входных сигнала кодирует один двоичный разряд X, пары разрядов q1, q2 и Q1, Q2 кодируют соответственно текущее и следующее состояния автомата, разряды Z1, Z2 и Z3 кодируют выходной сигнал. С учетом этого, получаем кодированные таблицы переходов и выходов (табл.5.6).

Таблица 5.6. Кодированная таблица переходов и выходов

Входной сигнал	Текущее состояние автомата	Следующее состояние автомата	Выходной сигнал
X	q1	q2	Q1	Q2	Z1	Z2	Z3

Определение функций возбуждения элементов памяти. Этот этап синтеза зависит от вида применяемого элемента памяти. Пусть в качестве элемента памяти используется RS -триггер, работа которого приведена в таблице истинности (табл.5.7).

Таблица 5.7. Таблица истинности RS-триггера

S	R	Q (t+1)	(t+1)
		Q (t) запрещен	(t)

Следует найти четыре функции S1, R1, S2, R2 трех переменных X, q1, q2. Для этого составим структурную таблицу (табл.5.8) по следующим правилам:

1. Сигналы, подаваемые на вход автомата для перевода его из одного состояния в другое, запишем в столбце «Входной сигнал».

2. В столбце «Текущее состояние» запишем двоичные коды текущего состояния автомата из кодированной таблицы переходов и выходов.

3. В столбце «Следующее состояние» запишем двоичный код состояния автомата, в которое он может перейти из данного текущего состояния из таблицы переходов и выходов.

4. В столбце «Сигнал возбуждения» запишем сигналы, подаваемые на вход элемента памяти для перевода его из «текущего состояния» в «следующее состояние».

Таблица 5.8. Структурная таблица определения функций возбуждения

Входной сигнал	Текущее состояние	Следующее состояние	Сигнал возбуждения
X	q1	q2	Q1	Q2	S1	R1	S2	R2
						*
							*
					*		*
								*
						*
					*			*

Минимизация функций возбуждения триггеров и функций выходов. Выполним минимизацию функций возбуждения триггеров и выходов, используя метод минимизирующих карт Карно. На рис.5.7 отражена минимизация полученных функций возбуждения триггеров.

Рисунок 5.7. Минимизация функций возбуждения триггеров

При минимизации проводилось доопределение не полностью определенных функций. Так же выполняется минимизация функций выходов. В результате получим аналитические выражения для всех функций синтезируемого автомата:

;

;

; ; .

Переход к заданному базису. Для перехода к заданному базису необходимо воспользоваться соотношениями де Моргана.

При реализации схемы на элементах ИЛИ-НЕ необходимо произвести двойную инверсию над каждой конъюнкцией, а также двойную инверсию над всей функцией и используя теорему де Моргана преобразовать инверсию конъюнкций в дизъюнкцию инверсий. В результате получаются выражения, содержащие только операцию ИЛИ-НЕ, которые непосредственно реализуются структурой соответствующим образом соединенных элементов ИЛИ-НЕ.

При реализации схемы на элементах И-НЕ необходимо произвести двойную инверсию над всей функцией и используя теорему де Моргана преобразовать инверсию дизъюнкций в конъюнкцию инверсий.

; ;

; ;

; ;

В результате получаются выражения, содержащие только операцию И-НЕ, которые непосредственно реализуются структурой соответствующим образом соединенных элементов И-НЕ.

Составление логической схемы автомата. По полученным логическим выражениям строим схему автомата (рис.5.8).