3.10. Приклад синтезу скінченного автомата
Нехай скінченний автомат заданий сполученою таблицею переходів- виходів.
Таблиця переходів-виходів скінченного автомата.
x(n) (стан / вихід)
y(m) 0 1 2 3
-
0
2/0
2/0
0/0
0/1
1
1/1
1/0
0/1
1/1
2
1/0
0/1
2/1
0/0
Перетворимо вихідну таблицю в спеціальну форму з виділенням вхідних-вихідних сигналів і внутрішніх станів.
Таблиця 3.11.
Проміжна таблиця
Входи |
x(n) |
000 111 222 333 |
Поточні стани |
s(n) |
012 012 012 012 |
Наступні стани |
s(n+1) |
211 210 002 010 |
Виходи |
y(n) |
010 001 011 110 |
Замінюючи десяткові числа на двійкові, одержимо таблицю істинності, в якій значення x(n), s(n), s(n+1), y(n) подані в двійковому коді.
Таблиця 3.12.
Таблиця істинності кінцевого автомата
x(n) |
s(n) |
s(n+1) |
y(n) |
|||
x1(n) |
x2(n) |
s1(n) |
s2(n) |
s1(n+1) |
s2(n+1) |
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
* |
* |
* |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
* |
* |
* |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
* |
* |
* |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
* |
* |
* |
Граф скінченного автомата буде мати вигляд, показаний на рис. 3.13.
0/1 1/0 3/1
2/1 1
0 1/1 3/0 0/0
2/0 3/1
0/0 0/1 2 2/1
Рис. 3.13. Граф синтезованого скінченного автомата
Вихідні функції для синтезу автомата за табл. 3.12 буде мати вигляд
s1(n+1) = x1(n)x2(n)s1(n)s2(n) x1(n) x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n);
s2(n+1) = x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n);
y(n) = x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n).
Мінімізуємо дані функції за допомогою карт Карно.
Для s1(n+1).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
-
001
1
01
11
10
1
Для s2(n+1).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
-
00
011
1
1
11
10
1
Для y(n).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
-
001
011
1
1
11
10
1
1
Результати мінімізації представимо у вигляді
s1(n+1) = x1(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n);
s2(n+1) = x1(n)s1(n)s2(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n);
y(n)=x2(n)s1(n)s2(n) x1(n)x2(n)s1(n) x1(n)x2(n)s1(n)s2(n)
x1(n)x2(n)s1(n)s2(n).
Структура автомата в загальному вигляді подана на рис. 3.14.
x1(n) Комб. y(n)
x2(n) схема
s1(n+1)
s1(n)
s2(n) s2(n+1)
П2
П1
Рис. 3.14. Структурна схема скінченного автомат
Комбінаційна схема автомата і її зв'язок з елементами пам'яті показані на рис. 3.15.
x1(n) x2(n) s1(n) s2(n)
s2(n)s1(n)x2(n)x1(n) KC
x
1(n)
1 &
x
2(n)
1 1 y(n)
& 1
&
1
&
s2
& 1 (n+1)
&
& s1
(n+1)
1
&
П2
s2(n)
П1 Пам'ять
s1(n)
Рис. 3.15. Схема скінченного автомата
Таким чином, синтезований скінченний автомат містить 4 елементи "НЕ", три елементи "АБО", дев'ять елементів "І" і два елементи пам'яті.
Скінченний автомат являє собою точну з функціональної точки зору модель дискретного обчислювального або керуючого пристрою. Вхідна буква - це вхідний сигнал (точніше - комбінація сигналів на усіх входах пристрою), вхідне слово - послідовність вхідних сигналів, що надходять в автомат у дискретні моменти часу.
Вихідне слово - послідовність вихідних сигналів, що видаються автоматом. Стани автомата - це комбінації станів елементів пристрою, що запам'ятовують.
Проте навіть із прикладної точки зору інтерпретація автомата як пристрою не є універсальною. Відомо, що довільний обчислювальний пристрій можна реалізувати як апаратно (у вигляді пристрою), так і програмно (у вигляді програми для ЕОМ). Це призводить до більш загального тлумачення автоматів як алгоритмів із скінченною пам'яттю, багато властивостей яких можна досліджувати иезалежно від способу їхньої реалізації.