Математичне моделювання систем / Лекция 3

Лекция 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 элемента "не", три элемента "или", девять элементов "и" и два элемента памяти.