Моделирование дискретного автомата

Размещено на http://www.allbest.ru/

Содержание

Введение

1 Абстрактный синтез дискретного автомата

2 Структурный синтез дискретных автоматов

3 Моделирование дискретного автомата

Заключение

Список использованных источников

Введение

Современные приборы и устройства сервиса представляют собой сложные технические системы, реализованные на базе средств вычислительной техники. Цифровые устройства и микропроцессоры являются важнейшей составной частью различных объектов бытовой техники: радиоэлектронной аппаратуры, стиральных и посудомоечных машин, холодильников и климат-систем, изделий оргтехники и других устройств.

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

Управляющие автоматы реализуются в виде "гибкой" или программируемой логики, на основе микропроцессоров, а также в виде "жесткой логики" - на основе последовательностных цифровых устройств. Математическими моделями, используемыми при анализе и синтезе последовательностных устройств. В последнее время интерес к конечным автоматам возрос, что связано с развитием интегральной программируемой электроники и др. В основе синтеза таких устройств лежат методы абстрактного (логического) и структурного синтеза конечных автоматов. Это обстоятельство делает необходимым приобретения знаний и навыков применения этих методов для анализа и синтеза цифровых устройств управления объектами и устройствами [2].

1 Абстрактный синтез дискретного автомата

Рассмотрим содержание и особенности определенных этапов синтеза на примере.

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

дискретный автомат сигнал триггер

.

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

Таблица 1.1 Первичная таблица переходов-выходов автомата Мура

х	Состояния S и выходные сигналы Y
			-	-	-	-	-	-	-
	-			-	-			-	-	-
	-	-			-	-
	-	-	-			-	-	-	-	-
	-	-	-	-			-			-

Задача минимизации автомата сводится возможности максимального уменьшения числа внутренних состояний без изменения закона их функционирования.

Решение этой задачи выполним методом Ауфенкампа и Хона основанного на понятии эквивалентных состояний.

Эквивалентным состоянием называется sn и sm такие состояния которым во-первых соответствуют одинаковые входные сигналы y(t) а во вторых переход из состояний sn и sm под воздействием любого символа приводит к одному и тому же эквивалентному состоянию [3].

Алгоритм минимизации:

1. Методом последовательного разбиения выделяем все попарно эквивалентные состояния.

2. Объединяем эквивалентные состояния в одиночные классы у1 у2 и выделяем в каждом классе по одному состоянию для выполнения последующих этапов при разбиении на классы пустые клетки во внимание не принимаются.

3. Строим вторичную таблицу переходов-выходов в которой каждый класс состояний представляем только одним эквивалентным состоянием.

Рисунок 1 - Первичный граф переходов-выходов автомата Мура

Первое разбиение состояний на классы выполняем по выходным сигналам как показано в таблице 2. Анализ показывает что в классе у1 состояние s1 не является эквивалентным основным состоянием этого класса так как при поступлении сигнала х1 автомат переходит из состояния s1 в класс состояний у2 в отличии от других состояний класса переводящих автомат под действием сигнала х1 в состояния класса у1 [4].

Таблица 2 - Разбиение на классы автомата Мура

х	Состояния S и выходные сигналы Y
			-	-	-	-	-		-	-
	-		-		-		-	-		-
	-	-	-			-
	-	-		-	-	-		-	-	-
	-	-		-			-	-	-
Кл.

Таблица 3 - Переходы-выходы автомата Мура

x	Состояния Г и выходные сигналы Y
		-		-	-	-
			-			-
	-			-
		-		-	-	-
			-		-

Таблица 4 - Первичная таблица возбуждения

x	Y0	Y1	Y2	Y2	Y1	Y2	Y3	Y3
	d1	d0	d1	d0	d1	d0	d1	d0	d1	d0	d1	d0	d1	d0	d1	d0
	0	0	0	1	1	0	1	0	0	1	1	0	1	1	1	1
	y0	y1	y2	y*2	y3	y4	y5	y*5
	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0
a2	a1	a0	0	1	1	1	0	1	0	1	0	1	1	0	0	1	0	0	0	0	1	1	0	0	0	1	1	0	0	1	1	1	0	1
0	0	0	0	1	1	1	-	-	-	-	0	1	1	1	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
0	0	1	0	1	0	1	0	1	0	1	-	-	-	-	-	-	-	-	0	0	0	1	0	0	0	1	-	-	-	-	-	-	-	-
0	1	0	-	-	-	-	0	1	0	0	0	1	1	0	0	1	1	0	-	-	-	-	1	0	0	1	1	0	0	1	-	-	-	-
0	1	1	0	1	1	1	-	-	-	-	0	1	1	1	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
1	0	0	0	0	1	1	0	1	0	1	-	-	-	-	-	-	-	-	0	0	1	1	-	-	-	-	1	1	0	1	0	1	0	1

Таблица 5 - Вторичная таблица возбуждения

x	Y0	Y1	Y2	Y2*
	d1	d0	d1	d0	d1	d0	d1	d0
	0	0	0	1	1	0	1	0
	y0	y1	y2	y*2
	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0
	0	1	1	1	0	1	0	1	0	1	1	0	0	1	0	0
a2	a1	a0	R3	S3	R2	S2	R1	S1	R0	S0	R3	S3	R2	S2	R1	S1	R0	S0	R3	S3	R2	S2	R1	S1	R0	S0	R3	S3	R2	S2	R1	S1	R0	S0
0	0	0	1	1	1	1	1	1	1	1	-	-	-	-	-	-	-	-	1	1	1	1	1	1	1	0	-	-	-	-	-	-	-	-
0	0	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
0	1	0	-	-	-	-	-	-	-		1	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	0	1	1
0	1	1	1	1	1	1	1	1	1	1	-	-	-	-	-	-	-	-	1	1	1	1	1	1	1	0	-	-	-	-	-	-	-	-
1	0	0	1	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-

Продолжение таблицы 5

x	Y1	Y2	Y3	Y3*
	d1	d0	d1	d0	d1	d0	d1	d0
	0	1	1	0	1	1	1	1
	y3	y4	y5	y*5
	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0	q3	q2	q1	q0
	0	0	1	1	0	0	0	1	1	0	0	1	1	1	0	1
a2	a1	a0	R3	S3	R2	S2	R1	S1	R0	S0	R3	S3	R2	S2	R1	S1	R0	S0	R3	S3	R2	S2	R1	S1	R0	S0	R3	S3	R2	S2	R1	S1	R0	S0
0	0	0	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
0	0	1	1	1	1	1	0	1	1	1	1	1	1	1	1	1	1	1	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
0	1	0	-	-	-	-	-	-	-	-	1	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	-	-	-	-	-	-	-	-
0	1	1	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-	-
1	0	0	1	1	1	1	1	1	1	1	-	-	-	-	-	-	-	-	1	1	1	0	1	1	1	1	0	1	1	1	1	1	1	1

2 Структурный синтез дискретных автоматов

Структурный синтез начинается с кодирования входного и выходного алфавита и состояний автомата.

Количество разрядов для входных выходных сигналов и состояний определяется в соответствии с формулой (1)

, (2.1)

где М-мощность множества соответствующего алфавита;

х-означает минимальное целое.

Рисунок 2 - Вторичный граф переходов-выходов автомата Мура

Для автомата Мура:

, (2.2)

, (2.3)

. (2.4)

Кодирование входных сигналов автомата Мура представлена как в таблице 4.

Таблица 4 - Кодирование входных сигналов автомата Мура

Входной сигнал	Коды
X0	0	0	0
X1	0	0	1
X2	0	1	0
X3	0	1	1
X4	1	0	0

Кодирование выходных сигналов автомата Мура представлена в таблице 5.

Таблица 5 - Кодирование выходных сигналов автомата Мура

Выходной сигнал	Коды
y0	0	0
y1	0	1
y2	1	0
y3	1	1

Одно из возможных вариантов кодирования состояний автомата Мура представлен в таблице 6.

Таблица 6 - Кодирования состояний автомата Мура

Состояния Q	Коды
	0	1	1	1
	0	1	0	1
	0	1	1	0
	0	1	0	0
	0	0	1	1
	0	0	0	1
	1	0	0	1
	1	1	0	1

Вторичный граф переходов-выходов автомата Мили представлен на рисунке 2.

Рисунок 3 - Структурный граф автомата Мура

На основании таблицы возбуждения формируем восемь функций возбуждения:

; (2.5)

; (2.6)

; (2.7)

; (2.8)

; (2.9)

; (2.10)

; (2.11)

. (2.12)

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

Таблица 7 - Таблица истинности выходных функций автомата Мура

Состояние автомата	Состояния триггеров	Выходные сигналы
					Y
	0	0	0	1
	0	0	1	1
	0	1	0	0
	0	1	0	1
	0	1	1	0
	0	1	1	1
	1	0	0	1
	1	1	0	1

В результате получим выражения:

; (2.13)

. (2.14)

3. Моделирование дискретного автомата

Функциональная схема автомата Мура на RS - триггерах и элементах И-НЕ представлена в соответствии с рисунком 4.

Для проверки соответствия синтезированной схемы заданным условиям функционирования автомата выполним функциональное моделирование полученной схемы при помощи программы моделирования Electronics Workbench [5].

Источником входных сигналов является генератор двоичных слов, а выходные сигналы модели автомата индицируется при помощи логического анализатора.

Рисунок 4 - Генератор слов



Рисунок 5 - Временные диаграммы функционирования

Рисунок 5 - Модель автомата Мура

Заключение

В ходе работы было проведено исследование дискретного автомата Мура, состоящее из :

1. Абстрактный синтез. В котором по вход-выходной последовательности и таблице соответствия были рассчитаны: первичная и вторичная таблица переходов-выходов; первичный и вторичный граф переходов-выходов; таблицы

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

3. Моделирование дискретного автомата. На этом этапе была построена функциональная модель автомата Мура в программе Electronic WorkBench , построенной по выходным функциям и функциям возбуждения. Запрограммировав генератор слов были получены временные диаграммы, которые соответствуют вход-выходной последовательности.

Список использованных источников

1. Соловьев В.В.Булатова И.Р.Стандартные программируемые логические устройства Зарубежная радиоэлектроника.2000 № 4.С.66-76.

2. Соловьев В.В.Булатова И.Р. Архитектуры сложных программируемых логических интегральных схем Зарубежная радиоэлектроника.2000 № 5.С.62-78.

3. Энциклопедия кибернетики Под ред. В.М.Глушакова. -Киев :Главная редакция украинской советской энциклопедии,1974.

4. Соловьев А.Я. Основы информатики :Учебник для вузов. -М.: Изд-во МГТУ им.Н.Э.Баумана,2001.

5. Трахтенберг Б.А .,Барадин Я.М .Конечные автоматы :Поведение и синтез.М.:Наука,1970

Размещено на Allbest.ru