Структурний синтез автомата Мілі
Наприклад структурна таблиця переходів-виходів автомата Мілі (табл.2). У даній таблиці в стовпцях до (аm) і до (as) указується код початкового стану і стану переходу відповідно. У стовпці функцій збудження ФВ указуються ті значення функцій збудження, які на даному переході обов'язково рівні 1. Інші (тобто рівні 0 або що приймають невизначені значення) не указуються. Це еквівалентно тому, що всім невизначеним значенням функцій збудження приписується значення 0, що в загальному випадку не дає мінімальної функції, проте в реальних автоматах мінімізація звичайно не робиться з причини її неефективності.
Таблиця 2. Структурна таблиця переходів-виходів автомата Мілі
аm |
K(am) |
as |
K (as) |
X |
Y |
ФВ |
a1 |
000 |
a2 a4 |
010 001 |
|
|
|
a2 |
010 |
a2 a5 a6 |
010 110 011 |
|
|
-
|
a3 |
101 |
a4 |
001 |
1 |
|
|
a4 |
001 |
a1 a3 |
000 101 |
|
|
|
a5 |
110 |
a1 |
000 |
1 |
|
|
a6 |
011 |
a1 a2 |
000 010 |
|
-
|
|
5.5. Запис та мінімізація ФВ та входів збудження елементарних автоматів
Для отримання функцій збудження поступаємо таким чином. Вираз для кожної функції виходить у вигляді логічної суми добутків виду а і Х, де а – початковий стан, Х – умова переходу.
Для спрощення одержаних виразів виконуємо всі можливі операції склеювання і поглинання:
Для отримання функцій виходів поступаємо аналогічно:
Побудова схеми керуючого автомата
Для побудови функціональної схеми автомата по одержаних виразах необхідно або замінити аі його значення через Q1 Q2 Q3 або одержати сигнал, відповідний аі. Звичайно використовують другий спосіб і для отримання сигналу аі застосовують так званий дешифратор станів, на вхід якого поступають сигнали з виходів елементів пам'яті Q1 Q2 Q3. Крім того, при побудові схеми прагнуть виділити загальні частини, що зустрічаються у функціях збудження або вихідних сигналах. В цьому випадку остаточна система рівнянь, по яких будується схема, матиме вигляд:
Функціональна схема автомата, побудована на підставі одержаних рівнянь, представлена на рис. 8.
Рис. 8. Функціональна схема мікропрограмного автомата.
Структурний синтез автомата Мура
Виконуємо структурний синтез мікропрограмного автомата Мура, заданого своєю таблицею переходів-виходів. Як приклад синтез виконуватимемо по зворотній таблиці (див п3)
1. У початковому автоматі кількість станів М=7, отже число елементів пам'яті m = ] log 2 M [ = ] log 2 7 [ = 3.
Нехай для синтезу використовуються D–тригери.
2. Кодуємо внутрішні стани автомата, використовуючи алгоритм кодування для D–тригерів. Кількість переходів в даний стан легко визначається із зворотньої таблиці:
а1 ~ 2, а2 ~ 3, а3 ~ 2, а4 ~ 1, а5 ~ 1, а6 ~ 1, а7 ~ 2.
Тому коди станів наступні:а2-000, а1-001, а3-010, а7-100, а4-011, а5-101, а6-110.
3. Будуємо структурну таблицю переходів-виходів автомата Мура, табл.3.
Таблиця 3. Структурна таблиця переходів-виходів автомата Мура
аm |
K(am) |
as(Y) |
K (as) |
X |
ФВ |
a6 a7 |
110 100 |
a1(-)
|
001 |
1 |
D3 D3 |
a1 a2 a6 |
001 000 110 |
a2(y1y2) |
000 |
|
- |
a1 a4 |
001 011 |
a3(y3y4) |
010 |
1 |
D2 D2 |
a3 |
010 |
a4(y1y4) |
011 |
|
D2 D3 |
a2 |
000 |
a5(y2y3) |
101 |
|
D1 D3 |
a2 |
000 |
a6(y4) |
110 |
|
D1 D2 |
a3 a5 |
010 101 |
a7(y2) |
100 |
1 |
D1 D1 |
Побудова таблиці виконується аналогічно автомату Мілі.
4. Вирази для функцій збудження виходять у вигляді суми творів а та х, де а – початковий стан, х – умова переходу.
або
5. Вирази для вихідних сигналів автомата Мура одержуємо, виходячи з того, що ці сигнали визначаються тільки внутрішнім станом автомата.
6. Для побудови функціональної схеми автомата як і у попередньому випадку використовуємо дешифратор станів. Схема представлена на рис. 8.