3. Структурный синтез автомата

1. Кодирование состояний автомата с использованием «соседства»

Инверсная таблица переходов:

Pi Si	P0	P1	P2	P3	P4	P5	P6	P7
S0	-	S7/W3	-	S4/W4	S1/W3	S1/W3	S1/W3	S1/W3
S1	S7/W3	S0/W1	S1/W5	S1/W5	-	-	S4/W4	S0/W1
S4	-	-	S7/W2	S7/W2	-	-	S7/W2	-
S7	-	-	-	-	S0/W0	S0/W0	S0/W0	S0/W0

Соседи первого рода:

(S1, S7)

Соседи второго рода:

(S0, S4)

	q1	q2
S0	0	0
S1	1	1
S4	1	0
S7	0	1

Составим карту Карно:

q1

S0	S4
S q2 7	S1

3.1.1 Кодированная таблица переходов и выходов.

x1x2x3 q1q2	P0 000	P1 001	P2 010	P3 011	P4 100	P5 101	P6 110	P7 111
00	-	01/0001	-	10/0101	11/0001	11/0001	11/0001	11/0001
11	01/0001	00/0100	11/0110	11/0110	-	-	10/0101	00/0100
10	-	-	01/0010	01/0010	-	-	01/0010	-
01	-	-	-	-	00/1000	00/1000	00/1000	00/1000

3.1.2 Таблица функций возбуждения и выходов.

x1x2x3 q1q2	000	001	011	010	110	111	101	100
00	-	0*,1*/0001	1*,0*/0101	-	1*,1*/0001	1*,1*/0001	1*,1*/0001	1*,1*/0001
01	-	-	-	-	0*,*1/1000	0*,*1/1000	0*,*1/1000	0*,*1/1000
11	*1,*0/0001	*1,*1/0100	*0,*0/0110	*0,*0/0110	*0,*1/0101	*1,*1/0100	-	-
10	-	-	*1,1*/0010	*1,1*/0010	*1,1*/0010	-	-	-

3.1.3 Совместная минимизация функций возбуждения и выходов.

Y0

Y1

Y2

-	0	0	-	0	0	0	0
-	-	-	-	1	1	1	1
0	0	0	0	0	0	-	-
-	-	0	0	0	-	-	-

-	0	0	-	0	0	0	0
-	-	-	-	0	0	0	0
0	0	1	1	0	0	-	-
-	-	1	1	1	-	-	-

-	0	1	-	0	0	0	0
-	-	-	-	0	0	0	0
0	1	1	1	1	1	-	-
-	-	0	0	0	-	-	-

Y3

J1

K1

-	1	1	-	1	1	1	1
-	-	-	-	0	0	0	0
1	0	0	0	1	0	-	-
-	-	0	0	0	-	-	-

-	0	1	-	1	1	1	1
-	-	-	-	0	0	0	0
*	*	*	*	*	*	-	-
-	-	*	*	*	-	-	-

-	*	*	-	*	*	*	*
-	-	-	-	*	*	*	*
1	1	0	0	0	1	-	-
-	-	1	1	1	-	-	-

J2

K2

-	1	0	-	1	1	1	1
-	-	-	-	*	*	*	*
*	*	*	*	*	*	-	-
-	-	1	1	1	-	-	-

-	*	*	-	*	*	*	*
-	-	-	-	*	*	*	*
0	1	0	0	1	1	-	-
-	-	*	*	*	-	-	-

Результат совместной минимизации функций возбуждения и выходов сведен в обобщенную таблицу системы булевых функций:

№	X1	X2	X3	q1	q2	Y0	Y1	Y2	Y3	J1	K1	J2	K2
1	Z	Z	Z	0	1	V
2	0	Z	1	Z	1		V
3	0	1	Z	0	Z		V
4	Z	1	Z	1	1		V
5	0	1	Z	Z	1			V
6	Z	Z	Z	1	0			V			V	V
7	0	0	0	Z	Z				V
8	Z	Z	Z	0	0				V
9	1	1	0	1	1				V
10	0	1	Z	Z	Z					V
11	1	Z	Z	Z	0					V		V
12	0	0	Z	Z	Z						V
13	1	Z	1	Z	Z						V	V
14	0	0	1	Z	Z								V
15	Z	Z	Z	0	1								V
16	1	Z	Z	Z	Z								V

Предварительная сложность по критерию Квайна равна:

К =