Курсовой проект - Автомат Мили

Агентство по образованию Российской Федерации

Северо-Западный государственный заочный технический университет

КУРСОВАЯ РАБОТА

По дисциплине «Математические основы теории систем»

Выполнила: Игонькина Н.С

Курс: 3

Факультет: САА и У

Форма обучения: заочная

Специальность: 220201

Шифр: 6420309032

Вариант: 2

Проверил: Пашкин В.Я.

Санкт-Петербург

2007 год

Задание на курсовой проект:

Абстрактный автомат Мили задан таблицей переходов/выходов

А) Минимизировать число состояний абстрактного автомата;

Б) Построить графы исходного минимизированного автомата;

В) Произвести структурный синтез автомата на элементах памяти для D-триггера.

Г) Вычертить логическую схему минимизированного автомата.

A) Автоматом называется дискретный преобразователь информации, способный принимать различные состояния, переходить под воздействием входных сигналов из одного состояния в другое и выдавать выходные сигналы. Если множество состояний автомата, а так же множества входных и выходных сигналов конечны, то автомат называется конечным автоматом.

Применяемые на практике автоматы принято разделять на два класса: - это автоматы Мили и автоматы Мура, названные так по имени американских ученых, которые впервые начали их изучать.

Закон функционирования автоматов Мили описывается следующей системой уравнений:

a(t + 1) = [a(t),x(t)] 

y(t) = [a(t),x(t)]  .

t = 0,1,2,3… 

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

Алгоритм минимизации заключается в следующем:

1. Все внутренние разбиваются на группы по числу выходных сигналов.

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

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

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

Таблица 1. Таблица переходов.

входные символы	Состояния
	S1	S2	S3	S4	S5	S6	S7	S8
X1	S3	S4	S4	S1	S7	S4	S4	S1
X2	S4	S5	S7	S7	S3	S7	S4	S6
X3	S5	S6	S2	S2	S8	S2	S6	S7

Таблица 2. Таблица выходов.

входные символы	Состояния
	S1	S2	S3	S4	S5	S6	S7	S8
X1	Y1	Y3	Y2	Y1	Y1	Y1	Y3	Y1
X2	Y1	Y1	Y2	Y2	Y2	Y2	Y1	Y2
X3	Y3	Y1	Y3	Y3	Y2	Y3	Y1	Y2

Таблица3.

входные символы	1-классы
	S1	S2	S3	S4	S5	S6	S7	S8
X1	Y1	Y3	Y2	Y1	Y1	Y1	Y3	Y1
X2	Y1	Y1	Y2	Y2	Y2	Y2	Y1	Y2
X3	Y3	Y1	Y3	Y3	Y2	Y3	Y1	Y2
1-классы	А1	A2	A3	A4	А5	А4	А2	А5

Таблица 4.

2-классы
входные символы	A1	A2		A3	A4		A5
	S1	S2	S7	S3	S4	S6	S5	S8
X1	A3	A4	A4	A4	A1	A4	A2	A1
X2	A4	A5	A4	A4	A2	A2	A3	A4
X3	A5	A4	A4	A2	A2	A2	A5	A2
2-классы	B1	B2	B3	B4	B5	B6	B7	B8

Таблица 5.

3-классы
входные символы	B1	B2	B3	B4	B5	B6	B7	B8
	S1	S2	S7	S3	S4	S6	S5	S8
X1	B4	B5	B5	B5	B1	B5	B3	B1
X2	B5	B7	B5	B3	B3	B3	B4	B6
X3	B7	B6	B6	B2	B2	B2	B8	B3
3-классы	C1	C2	C3	C4	C5	C4	C6	C7

Таблица 6.

4-классы
входные символы	C1	C2	C3	C4		C5	C6	C7
	S1	S2	S7	S3	S6	S4	S5	S8
X1	C4	C5	C5	C5	C5	C1	C3	C1
X2	C5	C6	C5	C3	C3	C4	C4	C4
X3	C6	C4	C4	C2	C2	C2	C7	C3
4-классы	D1	D2	D3	D4	D4	D5	D6	D7

Б) Граф минимизированного автомата представлен в Приложении 6.

D1 {S1},D2{S2},D3{S7},D4{S3,S6},D5{S4},D6{S5}D7{S8}.

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

Функции переходов элементарных двоичных автоматов Мура, которые будут использоваться в синтезе конечного автомата, приведены в таблице 12., где u-входной двоичный сигнал автомата, v-выходной двоичный сигнал , совпадающий с состоянием автомата. В таблице 12 элемент задержки выполнен в виде D-триггера.

Таблица 7. Таблица выходов.

входные символы	Состояния
	S1	S2	S3	S4	S5	S7	S8
X1	S3	S4	S4	S1	S7	S4	S3
X2	S4	S5	S7	S4	S3	S4	S4
X3	S5	S3	S2	S2	S8	S3	S7

Таблица 8. Таблица переходов.

входные символы	Состояния
	S1	S2	S3	S4	S5	S7	S8
X1	Y1	Y3	Y2	Y1	Y1	Y3	Y1
X2	Y1	Y1	Y2	Y2	Y2	Y1	Y2
X3	Y3	Y1	Y3	Y3	Y2	Y1	Y2

Закодируем входные и выходные символы и состояния автомата (см. таблица 9,10). Используя эти коды, построим закодированные таблицы переходов и выходов структурного автомата таблица 13,14.

Таблица 10.

Таблица 9.

входные символы	z1	z2
X1	0	0
X2	0	1
X3	1	1

входные символы	z1	z2
Y1	0	1
Y2	1	1
Y3	0	0

Таблица 11.

	V1	V2	V3
S1	0	0	0
S2	0	0	1
S3	0	1	1
S4	0	1	0
S5	1	0	0
S7	1	1	1
S8	1	1	0

u	V1
	0	1
0	0	1
1	1	0

Таблица 12.T -триггер

Таблица 13.

Входной ход  z1,z2	Код состояния v1,v2,v3
	000	001	011	010	100	101	111	110
00	-	-	-	-	-	-	-	-
01	011	010	010	000	101	-	010	011
11	010	100	101	010	011	-	010	010
10	100	011	001	011	111	-	011	111

Таблица 14.

	000	001	011	010	100	101	111	110
00	-	-	-	-	-	-	-	-
01	10	01	11	10	10	-	01	10
11	10	10	11	11	11	-	10	11
10	01	10	01	01	11	-	10	11

Находим функции возбуждения для D-триггеров.

Таблица V1.

z1z2	v1v2v3
	000	001	011	010	100	101	111	110
00	-	-	-	-	-	-	-	-
01	0	0	0	0	1	-	0	0
11	0	1	1	0	0	-	0	0
10	1	0	0	0	1	-	0	1

U1=

z1z2	v1v2v3
	000	001	011	010	100	101	111	110
00	-	-	-	-	-	-	-	-
01	1	1	1	0	0	-	1	1
11	1	0	0	1	1	-	1	1
10	0	1	0	1	1	-	1	1

Таблица V2.

U2=

z1z2	v1v2v3
	000	001	011	010	100	101	111	110
00	-	-	-	-	-	-	-	-
01	1	0	0	0	1	-	0	1
11	0	0	1	0	1	-	0	0
10	0	1	1	1	1	-	1	1

Таблица V3

U3=

z1z2	v1v2v3
	000	001	011	010	100	101	111	110
00	-	-	-	-	-	-	-	-
01	1	0	1	1	1	-	0	1
11	1	1	1	1	1	-	1	1
10	0	1	0	0	1	-	1	1