Минимизация конечных автоматов
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Государственное Образовательное Учреждение Высшего Профессионального Образования
Московский Государственный Технологический Университет СТАНКИН
Кафедра Компьютерные системы управления
Учебный курс Теория дискретных систем управления
Контрольная работа
по теме: Минимизация конечных автоматов
Выполнила: студентка Богачев Д.С.
Принял: к.т.н., преп. Нежметдинов Р.А.
Москва, 2012 г.
Содержание
1.Исходные данные
. Составление треугольной таблицы
. Нахождение списка максимальных классов совместимости
. Составление списка простых классов совместимости
. Нахождение минимального замкнутого покрытия
. Таблица переходов и выходов минимального автомата
. Синтез конечного автомата
. Получение логических функций выходов конечного автомата
. Минимизация логических функций
. Синтез функциональной схемы
. Принципиальная электрическая схема
Список литературы
1. Исходные данные
Конечный автомат задан совмещенной таблицей переходов и выходов
а1a2a3a4a5a6a7a8a9z1а5/--/-а5/-а5/w2a2/-a1/ w1a6/--/-а2/-z2a1/ w1a6/--/ w1-/-a1/--/ w2-/-а8/-а5/-z3-/--/--/--/--/-a2/--/-а7/-a6/-z4-/--/-a1/-a2/-а4/--/-а1/--/-a1/-
Тип элемента памяти - D-триггер.
2. Составление треугольной таблицы
2х3VV4VVх5хххх6хVххх7хVхх2,6 1,4х81,86,8VV1,82,7V9хххххх2,6 х12345678
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}
. Нахождение минимального замкнутого покрытия
Простые классыСостоянияПорожденные множества1234567891,41,82,62,76,85,65,7,8xxxooo02,6,8xxxxox02,4,8xxxoх2,3,8xxxo01,4,8xxxxx1,3,8xxxx02,7xxx7,9xxo07,8xx2,6xxx02,4xx04,8xx2,3xx3,8xx1,4xxx1,3xx5x9x
Выбираем новые состояния:
{5,7,8} - b1
{1,4,8} - b2
{2,6} - b3
{1,3} - b4
{9} - b5
6. Таблица переходов и выходов минимального автомата
Используя замену простых классов на новые переменные из п.3, получаем следующую таблицу минимального автомата:
b1b2b3b4b5Z1b3/-b1/w2b2(b4)/w1b1/-b3/-Z2b2/-b2/w1b3/w2b2(b4)/w1b1/-Z3b1/-b1/-b3/--/-b3/-Z4b2/-b3/--/-b2(b4)/-b2/-
7. Синтез конечного автомата
Производим кодирование входов, выходов и состояний:
Входы:
Х1Х2Z100Z201Z310Z411
Состояния:
t1t2t3b1000b2001b3010b4011b5100
Выходы:
yw10w21
Функции возбуждения памяти
D-триггера
Переходы:
000001010011100000100000110000100100100101000100010000000010-01011001010-011001
Выходы:
00000101001110000-10--01-010-10-----11-----
Таблицу переходов автомата соответствует таблице возбуждения памяти синтезируемого автомата для D-триггера:
000001010011100000100000110000100100100101000100010000000010-01011001010-011001
8. Получение логических функций выходов конечного автомата
0= ;
1=0
;
Используя таблицу функции возбуждения памяти D-триггера, получим следующие логические функции переходов конечного автомата:
?10= ---------- ? 20=
;
?30=
;
? 11= ?10 ;
? 21 = ? 20
? 31= ? 30
Минимизация логических функций
Для минимизации логических функций будем использовать карты Карно. Y1()
*******1*****1***
y= ;
11*1111*11
? 2 = ;
111*1111*
? 3= ;
10. Синтез функциональной схемы
совместимость автомат логический конечный
11. Принципиальная электрическая схема
Список литературы
1. Никишечкин А.П. Теория дискретных систем управления. Учебное пособие. - М.: ИЦ ГОУ МГТУ Станкин, 2006 - 242 с.
. Интегральные микросхемы: Справочник / Б.В. Тарабрин, Л.Ф. Лунин, Ю.Н. Смирнов и др.; Под ред. Б.В. Тарабрина. - М.: Радио и связь, 1983 - 528 с., ил.