Таблиця переходів автомата

2.1.2. Таблиця переходів автомата

Для кожного стану a_i визначаю по ГСА всі шляхи, які ведуть в інші стани.

Я буду будувати зворотну таблицю переходів для автомата Мура, тому що я синтезую автомат на базі JK-тригера.

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

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

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

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

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

Кодування станів виконуємо за еврістичним алгоритмом. Для цього будуємо матрицю D.

║T║ =

 i │ j │ P(i,j)

 1 │ 2 │ 1

 1 │ 23 │ 1

 1 │ 24 │ 1

 2 │ 6 │ 1

 2 │ 7 │ 2

 2 │ 9 │ 1

 3 │ 4 │ 1

 3 │ 6 │ 1

 3 │ 7 │ 1

 3 │ 11 │ 1

 3 │ 12 │ 1

 4 │ 5 │ 1

 5 │ 8 │ 1

 6 │ 8 │ 1

 7 │ 9 │ 1

 8 │ 10 │ 1

 8 │ 12 │ 1

 8 │ 13 │ 1

 9 │ 12 │ 1

 9 │ 13 │ 2

 9 │ 14 │ 1

 10 │ 11 │ 1

 13 │ 14 │ 1

 14 │ 16 │ 1

 14 │ 18 │ 1

 14 │ 19 │ 1

 15 │ 18 │ 1

 15 │ 19 │ 2

 15 │ 21 │ 1

 15 │ 24 │ 1

 15 │ 25 │ 2

 16 │ 17 │ 1

 17 │ 20 │ 1

 18 │ 20 │ 1

 19 │ 21 │ 1

 20 │ 22 │ 1

 21 │ 22 │ 1

 21 │ 24 │ 1

 21 │ 25 │ 1

 22 │ 23 │ 1

 22 │ 24 │ 1

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

 i │ j │ P(i,j)

 18 │ 19 │ 2

 16 │ 18 │ 1

 3 │ 16 │ 1

 7 │ 18 │ 1

 5 │ 7 │ 1

 5 │ 14 │ 1

 14 │ 16 │ 1

 14 │ 18 │ 1

 3 │ 14 │ 1

 5 │ 19 │ 1

 16 │ 19 │ 1

 4 │ 5 │ 1

 5 │ 6 │ 1

 16 │ 17 │ 1

 17 │ 18 │ 1

 2 │ 3 │ 1

 3 │ 4 │ 1

 6 │ 7 │ 1

 7 │ 8 │ 1

 8 │ 9 │ 1

 9 │ 20 │ 1

 20 │ 22 │ 1

 22 │ 23 │ 2

 13 │ 22 │ 1

 11 │ 13 │ 1

 11 │ 15 │ 1

 15 │ 20 │ 1

 15 │ 22 │ 1

 9 │ 15 │ 1

 11 │ 23 │ 1

 20 │ 23 │ 1

 10 │ 11 │ 1

 11 │ 12 │ 1

 20 │ 21 │ 1

 21 │ 22 │ 1

 1 │ 13 │ 1

 9 │ 10 │ 1

 12 │ 13 │ 1

 1 │ 2 │ 1

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

R = ] log2 N [ = ] log2 23 [ = 5

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

 a1 10000

 a2 00000

 a3 01001

 a4 01101

 a5 01111

 a6 01000

 a7 00001

 a8 01010

 a9 00011

 a10 11010

 a11 11001

 a12 01011

 a13 00010

 a14 00111

 a15 00100

 a16 10111

 a17 10101

 a18 00101

 a19 00110

 a20 11101

 a21 01110

 a22 11100

 a23 11000

 a24 10100

 a25 01100

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

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

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

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

Wmin = E P(i,j) .Коефіціент ефективності кодування: 1.20

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

Am	Kam	As	X	Kas	Yamas	J1K1J2K2J3K3J4K4J5K5
A1	10000	A2	1	00000	Y5Y9	K1
A2	00000	A6 A7 A9 A7	X4,NX3 NX4,X1 NX4NX1 X4X3	01000 00001 00011 00001	Y3Y10 Y6 Y5Y9 Y6	J2  J5  J4 J5  J5
A3	01001	A4  A7  A6	X4 NX4X3 NX3NX4	01101 00001 01000	Y4 Y6 Y3Y10	J3  K2  K5
A4	01101	A5	1	01111	Y4Y5	J4
A5	01111	A8	1	01010	Y1Y8	K3 K5
A6	01000	A8	1	01010	Y1Y8	J4
A7	00001	A9	1	00011	Y5Y9	J4
A8	01010	A10 A13 A12	X4 NX4X3 NX4NX3	11010 00010 01011	Y4 Y6 Y3Y10	J1  K2  J5
A9	00011	A13 A12 A13 A14	X4X3 X4NX3 NX4X1 X4NX1	00010 01011 00010 00111	Y6 Y3Y10 Y6 Y1Y8	K5  J2  K5  J3
A10	11010	A11	1	11001	Y5Y4	K4J5
A11	11001	A3	1	01001	Y1Y8	J1
A12	01011	A3	1	01001	Y1Y8	K4
A13	00010	A14	1	00111	Y1Y8	J3 J5
A14	00111	A16 A19 A18	X4 NX4X3 NX4NX3	10111 00111 00101	Y4 Y6 Y3Y10	J1  K5  K4
A15	00100	A19 A18 A19 A21	X4X3 X4NX3 NX4X1 NX4NX1	00110 00101 00110 01110	Y6 Y3Y10 Y6 Y3Y6	J4  J5  J4  J2 J3
A16	10111	A17	1	10101	Y4Y5	K4
A17	10101	A20	1	11101	Y2Y5	J2
A18	00101	A20	1	11101	Y2Y5	K1 K2
A19	00110	A21	1	01110	Y3Y6	J2
A20	11101	A22	1	11100	Y7	K5
A21	01110	A22 A25 A24	X5 NX5X6 NX5NX6	11100 01100 10100	Y7 Y3 Y8	J1 K4  K4 J1 K4
A22	11100	A24 A23	X1 NX1	10100 11000	Y8 Y1Y3	K2  K3
A23	11000	A1	1	10000	-	K2
A24	10100	A1 A15	X2 NX2	10000 00100	- Y5Y9	J3  K1

2.1.4. Функції збудження тригерів та вихідних сигналів

Виписуємо з таблиці вирази для тригерів (та виконуємо необхідні перетворення для представлення їх в рамках потрібної серії):

Формуємо функції виходів автомата:

Ми отримали усі необхідні вирази для принципової схеми. Будуємо її, користуючись формулами для тригерів та вихідними станами (Лист 1).

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

 

2.2.1. Розмітка станів ГСА

На етапі одержання відміченої ГСА входи вершин, які слідують за операторними, відмічають символами a₁, a₂, ... за наступними правилами:

1) символом а₁ відмічають вхід вершини, яка слідує за початковою, а також вхід кінцевої вершини;

2) входи усіх вершин , які слідують за операторними, повинні бути відмічені;

3) входи різних вершин відмічаються різними символами;

4) якщо вхід вершини відмічається, то тільки одним символом.

За ціми правилами в мене вийшло 21 стани (а₂₁).