Минимизация конечных автоматов
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
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
. Нахождение списка максимальных классов совместимости
Используя треугольную таблицу, составляем список максимальных классов совместимости:
)Ф=Х
)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
. Получение логических функций выходов конечного автомата
0=;
1=0
;
Используя таблицу функции возбуждения памяти D-триггера, получим следующие логические функции переходов конечного автомата:
?10= - ? 20=
;
?30=
;
? 11= ?10 ;
? 21 = ? 20
? 31= ? 30
9. Минимизация логических функций
Для минимизации логических функций будем использовать карты Карно. Y1()
*******1*****1***
y= ;
11*1111*11
? 2 = ;
111*1111*
? 3= ;
Список литературы
автомат совместимость конечный электрический
1. Никишечкин А.П. Теория дискретных систем управления. Учебное пособие. - М.: ИЦ ГОУ МГТУ Станкин, 2006 - 242 с.
. Интегральные микросхемы: Справочник / Б.В. Тарабрин, Л.Ф. Лунин, Ю.Н. Смирнов и др.; Под ред. Б.В. Тарабрина. - М.: Радио и связь, 1983 - 528 с., ил.