Математичне моделювання систем / Лекция 3
.docЛекция 3 Моделирование детерминированных объектов на основе теории конечных автоматов
Пусть конечный автомат задан совмещенной таблицей переходов - выходов.
Таблица переходов-выходов КA.
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
-
00
1
1
01
11
10
1
Для s2(n+1).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
-
00
01
1
1
1
11
10
1
Для y(n).
x1(n)x2(n)
s1(n)s2(n) 00 01 11 10
-
00
1
01
1
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
x1(n) 1 &
x2(n)
1 1 y(n)
& 1
&
1
&
s2
& 1 (n+1)
&
& s1
(n+1)
1
&
П2
s2(n)
П1 Память
s1(n)
Рис.3.15 - Схема конечного автомата
Таким образом, синтезированный конечный автомат содержит 4 элемента "не", три элемента "или", девять элементов "и" и два элемента памяти.