Табличный метод структурного синтеза конечных автоматов

Структурный синтез конечных автоматов заключается в выборе типов элементарных автоматов, в составлении функции возбуждения каждого элементарного автомата и функций кодированных выходов заданного автомата. На этапе структурного синтеза выбираем также способ кодирования состояний и выходных сигналов заданного автомата через состояния и выходные сигналы элементарных автоматов, в результате чего составляют кодированные таблицы переходов и выходов. Функции возбуждения элементарных автоматов и функции выходов получаются на основе кодированной таблицы переходов и выходов. Рассмотрим примеры синтеза, которые позволяют сформулировать общий алгоритм структурного синтеза конечных автоматов.

Пример. Пусть необходимо синтезировать автомата Мили, заданный совмещенной таблицей переходов и выходов:

xj\ai	a0	a1	a2
x1	a1/y1	a1/y2	a1/y2
x2	a2/y3	a2/y3	a0/y1

В качестве элементарных автоматов будем использовать JK-триггера, а в качестве логических элементов – элементы И, ИЛИ, НЕ. Итак, имеем
A ={ a ₀, a ₁, a ₂}; X ={ x ₁, x ₂}; Y ={ y ₁, y ₂, y ₃}. Здесь n=2, n +1=3; m =2, k =3.

1. Перейдем от абстрактного автомата к структурному, для чего определим количество элементов памяти R и число входных L и выходных N каналов.

R = ] log₂(n+1) [ = 2

L = ] log₂ m [ = 1

N = ] log₂ k [ = 2

Таким образом, необходимо иметь два элементарных автомата Q ₁ и Q ₂ (так как R =2), один входной канал O₁ и два выходных канала Z ₁ и Z ₂.

2. Закодируем состояния автомата, входные и выходные сигналы совокупностью двоичных сигналов.

Таблицы

кодирования

состояний

входных

выходных

автомата

сигналов

сигналов

aj	Q1	Q2
a0
a1
a2

xj	O1
x1
x2

yg	z1	z2
y1
y2
y3

Поскольку автомат имеет три состояния, то комбинация состояний элементарных автоматов 11 не используется и является запрещенной (автомат в это состояние никогда не попадет). Здесь и в дальнейшем будем использовать естественное кодирование, когда наборы значений двоичных переменных расписываются в порядке возрастания их номеров. С учетом кодирования перерисуем совмещенную таблицу переходов и выходов абстрактного автомата.

Перерисованная совмещенная таблица переходов и выходов

xj\ai
	01/00	01/01	01/01
	10/10	10/10	00/00

В таблицах кодирования выходные каналы Z ₁ и Z ₂ называются физическими выходами автомата.

3. Пользуясь таблицами кодирования, можно на основе заданных переходов и выходов построить кодированные таблицы переходов и выходов. Кодированная таблица переходов определяет зависимость состояний
Q i(t +1) элементарных автоматов в момент времени (t +1) от значения входного сигнала и внутренних состояний автоматов в предшествующий момент времени t. То есть:

Qi(t+1)=fi[Q₁(t), Q₂(t),…,Q_R(t),O₁(t),…, O_L(t)]

В кодированной таблице выходов – выходные сигналы Z _l(t) определяются в зависимости от значения входных сигналов и внутренних состояний в момент времени t. То есть:

Z_l(t)=fi[Q₁(t),Q₂(t),…,Q_R(t),O₁(t),…,O_L(t)]

Кодированная таблица переходов и выходов (совмещенная) имеет следующий вид:

(t)	(t+1)
o1	Q1	Q2	Z1	Z2	Q1	Q2
			-	-	-	-
			-	-	-	-

В нашем случае:

Z_l(t) = fi₁[Q₁(t), Q₂(t), O ₁(t)], Z₂(t) = fi₂[Q₁(t), Q₂(t), O ₁(t)]

Эти функции являются переключательными, поскольку значения функции и ее аргументов определены в один и тот же момент времени t.

4. Основная задача, решаемая в процессе структурного синтеза – построение таблицы функций возбуждения элементарных автоматов, которая определяет значения сигналов на входах элементарных автоматов, необходимые для обеспечения переходов автомата из одного состояния в другое. При построении этой таблицы используется матрица переходов выбранных элементарных автоматов, в нашем случае JK -триггера:

J	K	Q(t)	Q(t+1)
	b1
	b2
b3
b4

С помощью матрицы переходов заполняются столбцы таблицы функций возбуждения. В строках этой таблицы записываются значения J и K, обеспечивающие нужный переход.

Таблица функций возбуждения:

(t)	(t+1)
o1	Q1	Q2	J1	K1	J2	K2	Q1	Q2
				b		b
				b	b
			b			b
			-	-	-	-	-	-
				b		b
				b	b
			b			b
			-	-	-	-	-	-

Таким образом, получим значения входных сигналов J и K элементарных автоматов, которые зависят как от значения входного сигнала, так и от состояния автомата в тот же момент времени, что и Q i.

Поскольку функции возбуждения J (t) и K (t) определенны в тот же момент времени, что и их аргументы Q ₁(t), Q ₂(t) и O₁(t), то эти функции являются переключательными. В результате мы получим систему переключательных функций Z ₁(t), Z ₂(t), J ₁(t), K ₁(t), J ₂(t) и K ₂(t) заданных в виде таблиц их истинности.

5. Следующий этап –синтез комбинационной части конечных автоматов. На этом этапе по полученным переключательным функциям синтезируются комбинационные схемы. Очевидно, задача комбинационного синтеза конечных автоматов полностью совпадает с задачей синтеза логических схем. Обычно полученные переключательные функции минимизируют и представляют в булевом базисе, а переход к заданному базису осуществляют после.

В нашем случае мы имеем шесть переключательных функций трёх аргументов, для каждой из которых построим диаграмму Вейча.

Дата добавления: 2014-10-31