Структурний синтез автомата Мілі

2.2. Структурний синтез автомата Мілі

 

2.2.1. Кодування станів

Аналіз канонічного методу структурного синтезу автомата показує, що різні варіанти кодування станів автомата приводять до різних виражень функцій збудження пам'яті і функцій виходів, у результаті чого складність комбінаційної схеми істотно залежить від обраного кодування.

Мы повинні кодувати стани автомату з допомогою евристичного алгоритму кодування, тому що у мене Т-тригер.

Даний алгоритм мінімізує сумарне число переключень елементів пам'яті на всіх переходах автомата і використовується для кодування станів автомата при синтезі на базі T, RS, JK-тригерів. Для даних типів тригерів (на відміну від D-тригерів) на кожнім переході, де тригер змінює своє значення на протилежне, одна з функцій збудження обов'язково дорівнює 1. Зменшення числа переключень тригерів приводить до зменшення кількості одиниць відповідних функцій збудження, що при відсутності мінімізації однозначно приводить до спрощення комбінаційної схеми автомата.

Будую матрицю |T|, яка складається із всіх пар номерів (i, j), для яких P(i, j)  0, ij. Для кожної пари вказуємо її вагу.

║T║ =

 i │ j │ P(i,j)

 1 │ 2 │ 1

 1 │ 11 │ 1

 1 │ 12 │ 1

 1 │ 21 │ 1

 2 │ 3 │ 1

 3 │ 4 │ 1

 3 │ 13 │ 1

 3 │ 15 │ 1

 4 │ 5 │ 1

 5 │ 6 │ 1

 5 │ 7 │ 1

 5 │ 13 │ 1

 5 │ 18 │ 1

 6 │ 7 │ 1

 7 │ 8 │ 1

 7 │ 17 │ 1

 

 8 │ 9 │ 1

 9 │ 10 │ 1

 9 │ 14 │ 1

 9 │ 19 │ 1

 10 │ 11 │ 1

 11 │ 12 │ 1

 11 │ 14 │ 1

 11 │ 22 │ 1

 13 │ 15 │ 1

 13 │ 17 │ 1

 14 │ 19 │ 1

 14 │ 21 │ 1

 15 │ 16 │ 1

 15 │ 17 │ 1

 15 │ 18 │ 1

 16 │ 17 │ 1

 17 │ 18 │ 2

 19 │ 20 │ 1

 19 │ 21 │ 1

 19 │ 22 │ 1

 20 │ 21 │ 1

 21 │ 22 │ 2

Підраховуємо вагу всіх компонентів всіх пар

 P(1) = 4

P(2) = 2

P(3) = 4

P(4) = 2

P(5) = 5

P(6) = 2

P(7) = 4

P(8) = 2

P(9) = 4

P(10) = 2

P(11) = 5

P(12) = 2

P(13) = 4

P(14) = 4

P(15) = 5

P(16) = 2

P(17) = 5

P(18) = 3

P(19) = 5

P(20) = 2

 P(21) = 5

 P(22) = 3

Далі згідно правил алгоритму будуємо матрицю М

 i │ j │ P(i,j)

 17 │ 18 │ 2

 15 │ 17 │ 1

 3 │ 15 │ 1

 7 │ 17 │ 1

 5 │ 7 │ 1

 5 │ 13 │ 1

 13 │ 15 │ 1

 13 │ 17 │ 1

 3 │ 13 │ 1

 5 │ 18 │ 1

 15 │ 18 │ 1

 4 │ 5 │ 1

 5 │ 6 │ 1

 15 │ 16 │ 1

 16 │ 17 │ 1

 2 │ 3 │ 1

 1 │ 2 │ 1

 1 │ 11 │ 1

 1 │ 21 │ 1

 21 │ 22 │ 2

 19 │ 21 │ 1

 9 │ 19 │ 1

 11 │ 14 │ 1

 14 │ 19 │ 1

 14 │ 21 │ 1

 9 │ 14 │ 1

 11 │ 22 │ 1

 19 │ 22 │ 1

 10 │ 11 │ 1

 11 │ 12 │ 1

 19 │ 20 │ 1

 20 │ 21 │ 1

 1 │ 12 │ 1

 3 │ 4 │ 1

 6 │ 7 │ 1

 7 │ 8 │ 1

 8 │ 9 │ 1

 9 │ 10 │ 1

Визначемо розрядність кода для кодування станів автомата

R = ] log2 N [ = ] log2 22 [ = 5

Результати кодування:

 b1 01011

 b2 01111

 b3 00111

 b4 01101

 b5 00101

 b6 01100

 b7 00100

 b8 10100

 b9 10000

b10 11000

b11 11010

b12 01010

b13 00110

b14 11001

 b15 00011

b16 00010

b17 00000

b18 00001

b19 10001

b20 10101

b21 10011

b22 10010

Підрахунок ефективності кодування:

Кількість перемикань тригерів:

 W = E P(i,j)*d(i,j) = P(1,2)*d(1,2) + P(1,11)*d(1,11) + P(1,12)*d(1,12) + P(1,21)*d(1,21) + P(2,3)*d(2,3) + P(3,4)*d(3,4) + P(3,13)*d(3,13) + P(3,15)*d(3,15) + P(4,5)*d(4,5) + P(5,6)*d(5,6) + P(5,7)*d(5,7) + P(5,13)*d(5,13) + P(5,18)*d(5,18) + P(6,7)*d(6,7) + P(7,8)*d(7,8) + P(7,17)*d(7,17) + P(8,9)*d(8,9) + P(9,10)*d(9,10) + P(9,14)*d(9,14) + P(9,19)*d(9,19) + P(10,11)*d(10,11) + P(11,12)*d(11,12) + P(11,14)*d(11,14) + P(11,22)*d(11,22) + P(13,15)*d(13,15) + P(13,17)*d(13,17) + P(14,19)*d(14,19) + P(14,21)*d(14,21) + P(15,16)*d(15,16) + P(15,17)*d(15,17) + P(15,18)*d(15,18) + P(16,17)*d(16,17) + P(17,18)*d(17,18) + P(19,20)*d(19,20) +

 P(19,21)*d(19,21) + P(19,22)*d(19,22) + P(20,21)*d(20,21) + P(21,22)*d(21,22) =

 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*1 + 1*2 + 1*1 + 1*1 + 1*2 + 1*1 + 1*2 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 + 1*2 + 1*1 + 1*2 + 1*1 + 2*1 = 52

Мінімально можлива кількість перемикань тригерів

Wmin = E P(i,j) = 40

Коефіціент ефективності кодування: 1.30

Табл.3. Таблиця переходів Т-тригера

Am	Kam	As	Kas	X	Y	ФЗ
b1	01011	b2	01111	1	Y2Y4	T3
b2	01111	b3	00111	1	Y7	T2
b3	00111	b4 b13	01101 00110	NX1 X1	Y1Y9 Y8	T2 T4 T5
b4	01101	b5	00101	1	Y1Y8	T2
b5	00101	b6 b7 b18	01100 00100 00001	X4 NX4NX3 NX4X3	Y4 Y3Y10 Y6	T2 T5 T5 T3
b6	01100	b7	00100	1	Y4Y5	T2
b7	00100	b8	10100	1	Y2Y4	T1
b8	10100	b9	10000	1	Y7	T3
b9	10000	b10 b14	11000 11001	NX1 X1	Y1Y9 Y8	T2 T2 T5
b10	11000	b11	11010	1	Y1Y8	T4
b11	11010	b12 b1 b22	01010 01011 10010	X4 NX4NX3 NX4X3	Y4 Y3Y10 Y6	T1 T1 T5 T2
b12	01010	b1	01011	1	Y4Y5	T5
b13	00110	b5 b17	00101 00000	X2 NX2	Y1Y8 Y5Y9	T4T5 T3 T4
b14	11001	b11 b21	11010 10011	X2 NX2	Y3Y10 Y6	T4T5 T2 T4
b15	00011	b3 b13 b16	00111 00110 00010	X5 NX5NX6 NX5X6	Y7 Y8 Y3	T3 T3 T5 T5
b16	00010	b17	00000	1	Y5Y9	T4
b17	00000	b7 b18 b18 b15	00100 00001 00001 00011	X4NX3 X4X3 NX4X1 NX4NX1	Y3Y10 Y6 Y6 Y3Y6	T3 T5 T5 T4T5