Минимизация конечных автоматов
8,9 ф={7,8} {7,9}. Ц10= — ц 20=. Ц 21 = ц 20. Ц 31= ц 30. Ц 11= ц10; Выходы. Выходы. 6; 1,4; 1,8. 5,7,8} — b1. 1,4,8} — b2. Входы. B2(b4)/w1. B2(b4)/w1. 2,6} — b3. 1,3} — b4. Ц 2 =; B2(b4)/; 9} — b5. Ц 3=; А5/w2. A1/ w1. A1/ w1. 7; 6,8. 6; 1,4. 5,7,8}. 2,6,8}. 2,4,6}. 2,3,8}. 1,4,8}. 1,3,8}. Ц30=. Ф=х. B3/w2. B2/w1. B1/w2. А8/; А7/; А5/; А5/; А5/; А4/; А2/; А1/; 7,9}. 7,8}. 6,8}. 5,8}. 5,7… Читать ещё >
Минимизация конечных автоматов (реферат, курсовая, диплом, контрольная)
??? ?? /
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. Составление треугольной таблицы
х | |||||||||
V | V | ||||||||
V | V | х | |||||||
х | х | х | х | ||||||
х | V | х | х | х | |||||
х | V | х | х | 2, 6 1,4 | х | ||||
1,8 | 6,8 | V | V | 1,8 | 2,7 | V | |||
х | х | х | х | х | х | 2,6 | х | ||
3. Нахождение списка максимальных классов совместимости
Используя треугольную таблицу, составляем список максимальных классов совместимости:
1) Ф=Х
2) 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} | Ш | |
5. Нахождение минимального замкнутого покрытия
Простые классы | Состояния | Порожденные множества | ||||||||||||||
1,4 | 1,8 | 2,6 | 2,7 | 6,8 | 5,6 | |||||||||||
5,7,8 | x | x | x | o | o | o | ||||||||||
2,6,8 | x | x | x | x | o | x | ||||||||||
2,4,8 | x | x | x | o | х | |||||||||||
2,3,8 | x | x | x | o | ||||||||||||
1,4,8 | x | x | x | x | x | |||||||||||
1,3,8 | x | x | x | x | ||||||||||||
2,7 | x | x | x | |||||||||||||
7,9 | x | x | o | |||||||||||||
7,8 | x | x | ||||||||||||||
2,6 | x | x | x | |||||||||||||
2,4 | x | x | ||||||||||||||
4,8 | x | x | ||||||||||||||
2,3 | x | x | ||||||||||||||
3,8 | x | x | ||||||||||||||
1,4 | x | x | x | |||||||||||||
1,3 | x | x | ||||||||||||||
x | ||||||||||||||||
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 | |||
Z2 | |||
Z3 | |||
Z4 | |||
Состояния
t1 | t2 | t3 | ||
b1 | ||||
b2 | ||||
b3 | ||||
b4 | ||||
b5 | ||||
Выходы
y | ||
w1 | ||
w2 | ||
Функции возбуждения памяти D-триггера Переходы
010 | 000 | 011 | 000 | |||
001 | 001 | 010 | 001 | 000 | ||
000 | 010 | 010 | ||||
001 | 010 | 011 | ||||
Выходы
Таблицу переходов автомата соответствует таблице возбуждения памяти синтезируемого автомата для D-триггера:
010 | 000 | 011 | 000 | |||
001 | 001 | 010 | 001 | 000 | ||
000 | 010 | 010 | ||||
001 | 010 | 011 | ||||
8. Получение логических функций выходов конечного автомата
0=;
1=0
;
Используя таблицу функции возбуждения памяти D-триггера, получим следующие логические функции переходов конечного автомата:
ц10= — ц 20=
;
ц30=
;
ц 11= ц10 ;
ц 21 = ц 20
ц 31= ц 30
9. Минимизация логических функций
Для минимизации логических функций будем использовать карты Карно. Y1()
* | * | * | * | * | |||||
* | * | ||||||||
* | * | * | * | ||||||
* | * | * | * | ||||||
y= ;
* | |||||||||
* | |||||||||
ц 2 = ;
* | |||||||||
* | |||||||||
ц 3= ;
автомат совместимость конечный электрический
1. Никишечкин А. П. Теория дискретных систем управления. Учебное пособие. — М.: ИЦ ГОУ МГТУ «Станкин», 2006 — 242 с.
2. Интегральные микросхемы: Справочник / Б. В. Тарабрин, Л. Ф. Лунин, Ю. Н. Смирнов и др.; Под ред. Б. В. Тарабрина. — М.: Радио и связь, 1983 — 528 с., ил.