Реализация

Пример реализации автомата с жесткой логической структурой

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

Задача синтеза конечных автоматов разбивается на несколько этапов:

a) на первом этапе синтеза формулируются условия работы автомата, т.е. определяются условия его взаимодействия с объектом управления;

б) на втором этапе синтеза выявляется закон функционирования автомата, осуществляется его описание на одном из принятых формальных языков.

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

в) на третьем этапе осуществляют минимизацию внутренних состояний автомата;

г) на четвертом этапе осуществляется кодирование (размещение) внутренних состояний;

д) на пятом этапе осуществляется выписывание (в общем случае не полностью определенных) функций возбуждения автомата, их доопределение и минимизация;

е) шестой этап - построение ЛП на реальных логических элементах;

ж) последний этап - это соединение ЛП с ЭП и анализ работоспособности получившегося устройства.

Дано:

1 Диаграмма переходов – рисунок 2;

2 Коды входных сигналов: p1=000, p2=101, p3=011, p4=010, p5=111;

3 Коды выходных сигналов: y1=101001, y2=011011, y3=111010, y4=101011, y5=001001, y6=000011, y7=100100;

4 Коды внутренних состояний автомата: h1 =00, h2 =10,h3 =01, h4 =11.

Задание:

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

1 Исходя из диаграммы переходов, построим таблицу значений функции переходов и функции выходов (таблица 6).

2 Подставив соответствующие коды в таблицу 6, получим таблицу переходов (таблица 7) для системы функций возбуждения автомата.

Таблица 6 - Значения функций переходов и функции выхода автомата

№ п/п	H(t_i)	P(t)	H(t_i +1)	Y

	h1 h1 h1 h1 h2 h2 h2 h2 h3 h3 h3 h3 h4 h4 h4 h4 h4	p1 p4 p2 p3 p1 p4 p2 p3 p1 p5 p4 p2 p1 p2 p4 p5 p3	h1 h1 h2 h4 h2 h2 h3 h4 h3 h4 h2 h1 h4 h4 h3 h2 h1	y1 y2 y3 y4 y1 y2 y5 y7 y2 y6 y1 y3 y1 y2 y5 y6 y7

Таблица 7 – Таблица переходов возбуждений автомата

№ п/п	Адрес	Данные
H(t_i)	P(t)	H(t_i +1)	Y

3. Из полученной таблицы 7 видно, что:

- для восприятия входных кодов и оценки внутренних состояний в момент времени t_i и формирования выходных откликов, автомат должен состоять структурно из комбинационной схемы, которую можно построить, например, на ППЗУ типа К573РФ2;

- для хранения внутренних состояний автомат должен содержать элементы памяти, допустим, на D-триггерах типа К155ТМ2 или К561ТМ2.

Рисунок 3 – Функциональная схема синтезируемого автомата Мили

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

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

Комбинационная часть схемы автомата реализуется на ППЗУ путем непосредственной прошивки в ячейках памяти содержимого таблицы переходов (коды Н(t+1) и Y) по адресам, определяемым кодами Р(t ) и H(t). Элементы памяти на двух триггерах могут хранить два бита информации о внутреннем состоянии автомата после перехода в очередное состояние.

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

8 Получение кодов прошивки

Так как таблица 7 имеет всего 17 строк (т.е. в ПЗУ необходимо запомнить только 17 байт), а в ППЗУ К573РФ2 имеется возможность записать 2048 байт, то не все адресное пространство микросхемы необходимо занимать реализуемым автоматом. Поскольку комбинационная часть имеет только 5 входов, то можно выделить для данного автомата любую непрерывную область адресного пространства микросхемы емкостью в 32 байта. Для этого необходимо на 6 из 11 адресных входов микросхемы ППЗУ подать какие-либо константы. В выделенную таким образом область ППЗУ необходимо записать содержимое таблицы 7 в соответствии с выбранным вариантом обозначения оставшихся адресных входов микросхемы входными переменными комбинационной части автомата.

Разместим комбинационную часть в области ППЗУ, начинающуюся с адреса 00H. Следовательно, на старшие разряды адресных входов микросхемы необходимо при этом подать константу 000000B. В таблице 8. приведена полученная прошивка ППЗУ.

Таблица 8 – Адреса и данные, записанные в ППЗУ

Адрес	Данные	Адрес	Данные	Адрес	Данные	Адрес	Данные
			5B		A9		E9
	**		**		**		**
	1B	0А	A9		9B	1A
	EB	0В	**		E4	1B
	**	0С	**		**	1C	**
	BA	0D	3A			1D	DB
	**	0E	**		**	1E	**
	**	0F	C3		**	1F

В таблице 8 знаком ** помечены безразличные состояния функций возбуждения автомата. Входные сигналы, соответствующие этим состояниям не должны подаваться согласно диаграмме переходов автомата и должны быть запрещены. Соответствующие ячейки ППЗУ могут оставаться не запрограммированными, т.е. иметь содержимое FF.