Минимизация конечных автоматов
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 с., ил.
Больше работ по теме:
Контрольная работа
Моделирование схем в программе Electronics Workbench
Контрольная работа
Нейро-нечёткие сети
Контрольная работа
Определение токов в ветвях электрической цепи c помощью ЭВМ и системы линейных уравнений
Контрольная работа
Организация корпоративного управления предприятием ГКУ ТО "Центр информационных технологий Тюменской области"
Контрольная работа
Предмет: Информационное обеспечение, программирование
Тип работы: Контрольная работа
Новости образования
22 Июля 2016 16:26
Более 70 представителей крупных вузов АСЕАН подтвердили участие в форуме во Владивостоке
22 Июля 2016 12:51
Абызов: публикация первичных статсведений снизит бюрократическую нагрузку на школы
22 Июля 2016 11:53
В Чечне свыше 200 школьников сдали ЕГЭ с результатом свыше 90 баллов - министр
22 Июля 2016 05:36
Замглавы Минобрнауки РФ: задача сократить число людей с высшим образованием не стоит
21 Июля 2016 20:19
КОНТАКТНЫЙ EMAIL: [email protected]
Скачать реферат © 2017 | Пользовательское соглашение
ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ