Минимизация конечных автоматов

Минимизация конечных автоматов

Государственное Образовательное Учреждение Высшего Профессионального Образования

Московский Государственный Технологический Университет «СТАНКИН»

Кафедра «Компьютерные системы управления»

Учебный курс «Теория дискретных систем управления»

Контрольная работа

по теме: «Минимизация конечных автоматов»

Выполнила: студентка Богачев Д.С.

Принял: к.т.н., преп. Нежметдинов Р.А.

Москва, 2012 г.

Содержание

1.Исходные данные

. Составление треугольной таблицы

. Нахождение списка максимальных классов совместимости

. Составление списка простых классов совместимости

. Нахождение минимального замкнутого покрытия

. Таблица переходов и выходов минимального автомата

. Синтез конечного автомата

. Получение логических функций выходов конечного автомата

. Минимизация логических функций

. Синтез функциональной схемы

. Принципиальная электрическая схема

Список литературы

1. Исходные данные

Конечный автомат задан совмещенной таблицей переходов и выходов

	а1	a2	a3	a4	a5	a6	a7	a8	a9
z1	а5/-	-/-	а5/-	а5/w2	a2/-	a1/ w1	a6/-	-/-	а2/-
z2	a1/ w1	a6/-	-/ w1	-/-	a1/-	-/ w2	-/-	а8/-	а5/-
z3	-/-	-/-	-/-	-/-	-/-	a2/-	-/-	а7/-	a6/-
z4	-/-	-/-	a1/-	a2/-	а4/-	-/-	а1/-	-/-	a1/-

Тип элемента памяти - D-триггер.

2. Составление треугольной таблицы

2	х
3	V	V
4	V	V	х
5	х	х	х	х
6	х	V	х	х	х
7	х	V	х	х	2,6 1,4	х
8	1,8	6,8	V	V	1,8	2,7	V
9	х	х	х	х	х	х	2,6	х
	1	2	3	4	5	6	7	8

3. Нахождение списка максимальных классов совместимости

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

)        Ф=Х

)        7~8,9 Ф={7,8}{7,9}

3)      6~8 Ф={6,8}{7,8}{7,9}

4)      5~7,8 Ф={5,7,8}{6,8}{7,9}

5)      4~8 Ф={4,8}{5,7,8}{6,8}{7,9}

6)      3~8 Ф={3,8}{4,8}{5,7,8}{6,8}{7,9}

7)      2~8,7,6,4,3 Ф={2,3,8}{2,4,8}{5,7,8}{2,6,8}{7,9}{2,7}

8)      1~8,4,3 Ф={2,3,8}{2,4,8}{5,7,8}{2,6,8}{7,9}{2,7}{1,8,4}{1,8,3}

Ф={2,3,8}{2,4,8}{5,7,8}{2,6,8}{7,9}{2,7}{1,8,4}{1,8,3}

4. Составление списка простых классов совместимости

{5,7,8}	2,6; 1,4; 1,8
{2,6,8}	2,7; 6,8
{2,4,6}	6,8
{2,3,8}	6,8
{1,3,8}	1,8
{1,4,8}	1,8
{2,7}	Ø
{7,9}	2,6
{5,7}	2,6; 1,4
{7,8}	Ø
{5,8}	1,8
{2,6}	Ø
{2,8}	6,8
{6,8}	2,7
{2,4}	Ø
{4,8}	Ø
{2,3}	Ø
{3,8}	Ø
{1,4}	Ø
{1,8}	1,8
{1,3}	Ø
{1}	Ø
{2}	Ø
{3}	Ø
{4}	Ø
{5}	Ø
{6}	Ø
{7}	Ø
{8}	Ø
{9}	Ø

. Нахождение минимального замкнутого покрытия

Простые классы	Состояния									Порожденные множества
	1	2	3	4	5	6	7	8	9	1,4	1,8	2,6	2,7	6,8	5,6
5,7,8					x		x	x		o	o	o			0
2,6,8		x				x		x				x	o	x	0
2,4,8		x		x				x						o	х
2,3,8		x	x					x						o	0
1,4,8	x			x				x		x	x
1,3,8	x		x					x			x				0
2,7		x					x						x
7,9							x		x			o			0
7,8							x	x
2,6		x				x						x			0
2,4		x		x											0
4,8				x				x
2,3		x	x
3,8			x					x
1,4	x			x						x
1,3	x		x
5					x
9									x

Выбираем новые состояния:

{5,7,8} - b1

{1,4,8} - b2

{2,6} - b3

{1,3} - b4

{9} - b5

6. Таблица переходов и выходов минимального автомата

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

	b1	b2	b3	b4	b5
Z1	b3/-	b1/w2	b2(b4)/w1	b1/-	b3/-
Z2	b2/-	b2/w1	b3/w2	b2(b4)/w1	b1/-
Z3	b1/-	b1/-	b3/-	-/-	b3/-
Z4	b2/-	b3/-	-/-	b2(b4)/-	b2/-

7. Синтез конечного автомата

Производим кодирование входов, выходов и состояний:

Входы:

	Х1	Х2
Z1	0	0
Z2	0	1
Z3	1	0	1	1

Состояния:

	t1	t2	t3
b1	0	0	0
b2	0	0	1
b3	0	1	0
b4	0	1	1
b5	1	0	0

Выходы:

	y
w1	0
w2	1

Функции возбуждения памяти

D-триггера

Переходы:

	000	001	010	011	100
00	010	000	011	000	010
01	001	001	010	001	000
10	000	000	010	-	010
11	001	010	-	011	001

Выходы:

	000	001	010	011	100
00	-	1	0	-	-
01	-	0	1	0	-
10	-	-	-	-	-
11	-	-	-	-	-

Таблицу переходов автомата соответствует таблице возбуждения памяти синтезируемого автомата для D-триггера:

	000	001	010	011	100
00	010	000	011	000	010
01	001	001	010	001	000
10	000	000	010	-	010
11	001	010	-	011	001

8. Получение логических функций выходов конечного автомата

⁰= ;

¹=⁰

 ;

Используя таблицу функции возбуждения памяти D-триггера, получим следующие логические функции переходов конечного автомата:

φ₁⁰= ---------- φ ₂⁰=   

   ;

φ₃⁰=   

   ;

φ ₁¹= φ₁⁰ ;

φ ₂¹ = φ ₂⁰

φ ₃¹= φ ₃⁰

Минимизация логических функций

Для минимизации логических функций будем использовать карты Карно. Y₁()

	*	*	*		*		*
					*	*	1
		*	*		*	*
		*	1		*	*	*

y=   ;

		1	1				*
							1
					1	1	1
		*			1		1

φ ₂ =     ;

		1			1	1	*
			1			1
		1					1
		*

φ ₃=     ;

10. Синтез функциональной схемы

совместимость автомат логический конечный

11. Принципиальная электрическая схема

Список литературы

1. Никишечкин А.П. Теория дискретных систем управления. Учебное пособие. - М.: ИЦ ГОУ МГТУ «Станкин», 2006 - 242 с.

. Интегральные микросхемы: Справочник / Б.В. Тарабрин, Л.Ф. Лунин, Ю.Н. Смирнов и др.; Под ред. Б.В. Тарабрина. - М.: Радио и связь, 1983 - 528 с., ил.