Синтез микропрограммного автомата по граф-схеме алгоритма

Осуществим переход от частных ГСА к частным МСА
МСА по первой частной ГСА
Y1 Y2 Y3 Y4 Y9 Y10 Y11 Y13 Y14 Y15 Y16 Y17 Yk
Y0
x5
x5
Y1
Y2
Y3
x5
x5
Y4
x3x4
x3x4
Y9
1
Y10
x4
Y11
1
Y13
Y14
Y15
1
Y16
x2
Y17
x2
МСА по второй частной ГСА
Y1 Y2 Y3 Y4 Y9 Y10 Y11 Y13 Y14 Y15 Y16 Y17 Yk
Y0 x1
x1x5/x1x3x5
x1x3x5
Y1
x2
Y2
x5/x3x5
x3x5
Y3
x5/x3x5
x3x5
Y4
x3x4
x3x4
Y9
1
Y10
x4
Y11
1
Y13
1
Y14
1
Y15
Y16
Y17
МСА по третьей частной ГСА
Y1 Y2 Y3 Y4 Y9 Y10 Y11 Y13 Y14 Y15 Y16 Y17 Yk
Y0
x5x8
x8
x5x8
Y1
Y2
Y3
x5
x5
Y4
x2
Y9
1
Y10
x4
Y11
1
Y13
Y14
1
Y15
Y16
Y17
Определим коэффициент схожести между матрицами
B12=4
B13=3
B23=4
Кодируем МСА
МСА1 – 00, МСА2 – 01, МСА3 – 11
Каждой МСА поставим в соответствие конъюнкцию
МСА1→P1P2
МСА2→P1P2
МСА3→P1P2
Построим объединенную МСА
Y1 Y2 Y3 Y4 Y9 Y10 Y11 Y13 Y14 Y15 Y16 Y17 Yk
Y0 P1P2x1
P1P2x5
P1P2x1x5
P1P2x1x3x5
P1P2x5x8
P1P2x8
P1P2x1x3x5
P1P2x5x8
P1P2x5
Y1
P1P2x2
Y2
P1P2x5
P1P2x3x5
P1P2x3x5
Y3
P1P2x5
P1P2x5
P1P2x3x5
P1P2x5
P1P2x3x5
P1P2x5
P1P2x5
Y4
P1P2x3x4
P1P2x3x4
P1P2x2
P1P2x3x4
P1P2x3x4
Y9
P1P2
P1P2
P1P2
Y10
P1P2x4
P1P2x4
P1P2x4
Y11
P1P2
P1P2
P1P2
Y13
P1P2
Y14
P1P2
P1P2
Y15
P1P2
Y16
P1P2x2
Y17
P1P2x2
Осуществим минимизацию объединенной МСА
Y1 Y2 Y3 Y4 Y9 Y10 Y11 Y13 Y14 Y15 Y16 Y17 Yk
Y0 P1P2x1
P1P2x5
P1P2x1x5
P1P2x1x3x5
P1P2x5x8
P1P2x8
P1P2x1x3x5
P1P2x5x8
P1P2x5
Y1
P1P2x2
Y2
P1P2x5
P1P2x3x5
P1P2x3x5
Y3
P1x5
P1P2x3x5
P1P2x5
P1P2x3x5
P1P2x5
P1P2x5
Y4
P1x3x4
P1P2x2
P1P2x3x4
P1P2x3x4
Y9
1
Y10
P1P2x4
P1x4
Y11
1
Y13
P1P2
Y14
P2
Y15
P1P2
Y16
P1P2x2
Y17
P1P2x2
По объединенной МСА составим систему формул переходов
Y0=P1P2x1Y1∨P1P2x5∨P1P2x1x5∨P1P2x1x3x5∨P1P2x5x8Y4∨P1P2x8Y9∨(P1P2x1x3x5∨P1P2x5x8)Y14∨P1P2x5Y16
Y1=P1P2x2Y2
Y2=(P1P2x5∨P1P2x3x5)Y4∨P1P2x3x5Y14
Y3=P1x5∨P1P2x3x5∨P1P2x5Y4∨(P1P2x3x5∨
P1P2x5)Y14∨P1P2x5Y16
Y4=(P1x3x4∨P1x3x4∨P1P2x2)Y3∨P1P2x3x4Y13∨P1P2x3x4Y17
Y9=Y10
Y10=P1P2x4Y9∨(P1x4∨P1x4)Y11
Y11=Yk
Y13=P1P2Y9
Y14=P2Y10
Y15=P1P2Y9
Y16=P1P2x2Y15
Y17=P1P2x2Y15
Перейдем от СФП к системе скобочных формул перехода
Y0=P1P2x1Y1∨P1P2x5∨P1P2x1x5∨P1P2x1x3x5∨P1P2x5x8Y4∨P1P2x8Y9∨P1P2x1x3x5∨P1P2x5x8Y14∨P1P2x5Y16=P1P2x1Y1∨P2x5Y4∨P2x1x5Y4∨P2x1x3x5Y4∨P2x1x3x5Y14∨P2x5Y16∨P1P2x5x8Y4∨P2x8Y9∨P2x5x8Y14=P1P2(x5Y4∨x5Y16)∨P2(x1Y1∨x1x5Y4∨x1x3x5Y4∨x1x3x5Y14)∨P1P2x5x8Y4∨x8Y9∨x5x8Y14=P1P2(x5Y4∨x5Y16)∨P2(x1Y1∨x1x5Y4∨x3x5Y4∨x3x5Y14)∨P1P2x8(x5Y4∨x5Y14)∨x8Y9=P1P2(x5Y4∨x5Y16)∨P2(x1Y1∨x1x5Y4∨x5(x3Y4∨x3Y14))∨P1P2x8(x5Y4∨x5Y14)∨x8Y9==P1P2(x5Y4∨x5Y16)∨P2(x1Y1∨x1x5Y4∨x5(x3Y4∨x3Y14))∨P1x8(x5Y4∨x5Y14)∨x8Y9
Y1=P1P2x2Y2=x2Y2
Y2=P1P2x5∨P1P2x3x5Y4∨P1P2x3x5Y14=P1P2x5Y4∨x3x5Y4∨x3x5Y14=P1P2x5Y4∨x5x3Y4∨x3Y14=x5Y4∨x5(x3Y4∨x3Y14
Y3=P1x5∨P1P2x3x5∨P1P2x5Y4∨P1P2x3x5∨P1P2x5Y14∨P1P2x5Y16=P1x5Y4∨P2x3x5Y4∨P2x3x5Y14∨P2x5Y16∨P1P2x5Y4∨x5Y14=P1x5Y4∨x5P2x3Y4∨P2x3Y14∨P2Y16∨P1P2x5Y4∨x5Y14=P1(x5Y4∨x5(P2(x3Y4∨x3Y14)∨P2Y16))∨P1(x5Y4∨x5Y14)
Y4=P1x3x4∨P1P2x2Y3∨P1P2x3x4Y13∨P1P2x3x4Y17=P1x4x3Y3∨P2x3Y13∨P2x3Y17∨P1P2x2Y3=P1x4x3Y3∨x3(P2Y13∨P2Y17)∨P1P2x2Y3=P1x4x3Y3∨x3(P2Y13∨P2Y17)∨P1x2Y3
Y9=Y10
Y10=P1P2x4Y9∨P1x4Y11=x4P1P2Y9∨P1Y11=x4P1Y9∨P1Y11
Y11=Yk
Y13=P1P2Y9=Y9
Y14=P2Y10=Y10
Y15=P1P2Y9=Y9
Y16=P1P2x2Y15=x2Y15
Y17=P1P2x2Y15=x2Y15
По ССкФП строим подграфы
По подграфам получим объединенную ГСА.
Путем отметки объединенной ГСА в соответствии с законом функционирования автомата Мили получим набор путей переходов
a1p1p2x5(Y4)a4
a1p1p2x5(Y16)a6
a1p1p2x1(Y1)a2
a1p1p2x1x5(Y4)a4
a1p1p2x1x5x3(Y4)a4
a1p1p2x1x5x3(Y14)a8
a1p1x5x8(Y4)a4
a1p1x5x8(Y14)a8
a1p1x8a7
a2x2a2
a2x2(Y2)a3
a3x2(Y4)a4
a3x2x3(Y4)a4
a3x2x3(Y14)a8
a4p1a12
a4p1a11
a5p1x5(Y4)a4
a5p1x5p2(Y4)a6
a5p1x5p2x3(Y4)a4
a5p1x5p2x3(Y14)a8
a6x2a6
a6x2(Y15)a7
a7(Y9)a8
a8(Y10)a9
a9x4a9
a9x4p1a7
a9x4p1a10
a10(Y11)a1
a11x2a11
a11x2(Y3)a5
a12x4a12
a12x4x3(Y3)a5
a12x3x4p2(Y17)a6
a12x3x4p2(Y13)a7
Используя наборы переходов синтезируем автомат по общей ГСА в табличной форме (прямая структурная таблица переходов).
h
am
k(am) as
k(as) xh
Yh
Fh(RS)
1 a1
0000 a2
0001 p1p2x1
Y1
S4
2
a4
0010 p1p2x5
Y4
S3
3
a4
0010 p1p2x1x5
Y4
S3
4
a4
0010 p1p2x1x5x3
Y4
S3
5
a4
0010 p1x5x8
Y4
S3
6
a6
1000 p1p2x5
Y16
S1
7
a7
0100
p1x8
- S2
8
a8
0101 p1p2x1x5x3
Y14
S2S4
9
a8
0101 p1x5x8
Y14
S2S4
10 a2
0001 a2
0001 x2
- -
11
a3
0011 x2
Y2
S3
12 a3
0011 a4
0010 x2
Y4
S4
13
a4
0010 x2x3
Y4
S4
14
a8
0101 x2x3
Y14
S2R3
15 a4
0010 a11
0110 p1
- S2
16
a12
1011
p1
- S1S4
17 a5
1010 a4
0010 p1x5
Y4
R1
18
a4
0010 p1x5p2x3
Y4
R1
19
a6
1000 p1x5p2
Y4
R3
20
a8
0101 p1x5p2x3
Y14
S1R2S3R4
21 a6
1000 a6
1000 x2a6
- -
22
a7
0100 x2
Y15
R1S2
23 a7
0100 a8
0101 1 Y9
S4
24 a8
0101 a9
1101
1 Y10
S1
25 a9
1101 a9
1101
x4
- -
26
a7
0100 x4p1
- S1S4
27
a10
1100
x4
- R4
28 a10
1100 a1
0000
1 Y11
R1R2
29 a11
0110 a5
1010 x2
Y3
S1R2
30
a11
0110 x2
- -
31 a12
1011 a5
1010 x4x3
Y3
R4
32
a6
1000 x3x4p2
Y17
R3R4
33
a7
0100 x3x4p2
Y13
R1S2R3R4
34
a12
1011
x4
- -
По прямой структурной таблице построим обратную структурную таблицу переходов микропрограммного автомата.
h
am
k(am) as
k(as) xh
Yh
Fh(RS)
1 a10
1100 a1
0000
1 Y11
R1R2
2 a1
0000 a2
0001 p1p2x1
Y1
S4
3 a2
0001
x2
- -
4 a2
0001 a3
0011 x2
Y2
S3
5 a1
0000 a4
0010 p1p2x5
Y4
S3
6 a1
0000
p1p2x1x5
Y4
S3
7 a1
0000
p1p2x1x5x3
Y4
S3
8 a1
0000
p1x5x8
Y4
S3
9 a3
0011
x2
Y4
S4
10 a3
0011
x2x3
Y4
S4
11 a5
1010
p1x5
Y4
R1
12 a5
1010
p1x5p2x3
Y4
R1
13 a11
0110 a5
1010 x2
Y3
S1R2
14 a12
1011
x4x3
Y3
R4
15 a1
0000 a6
1000 p1p2x5
Y16
S1
16 a5
1010
p1x5p2
Y4
R3
17 a6
1000
x2a6
- -
18 a12
1011
x3x4p2
Y17
R3R4
19 a1
0000 a7
0100
p1x8
- S2
20 a6
1000
x2
Y15
R1S2
21 a9
1101
x4p1
- S1S4
22 a12
1011
x3x4p2
Y13
R1S2R3R4
23 a1
0000 a8
0101 p1p2x1x5x3
Y14
S2S4
24 a1
0000
p1x5x8
Y14
S2S4
25 a3
0011
x2x3
Y14
S2R3
26 a5
1010
p1x5p2x3
Y14
S1R2S3R4
27 a7
0100
1 Y9
S4
28 a8
0101 a9
1101
1 Y10
S1
29 a9
1101
x4
- -
30 a9
1101 a10
1100
x4
- R4
31 a4
0010 a11
0110 p1
- S2
32 a11
0110
x2
- -
33 a4
0010 a12
1011
p1
- S1S4
34 a12
1011
x4
- -
По обратной структурной таблице переходов строим функциональную схему автомата.