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