Канонический метод структурного синтеза автоматов

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

На рис. 36, а и б, приведены обобщённые структурные схемы автоматов на D- и Т- триггерах, где КС – комбинационная схема.

Для обеспечения устойчивой работы автомата при практической реализации необходимо предусмотреть, например, удвоение элементов памяти. (рис. 37).

а) б)

Рис.36

Рис.37

Синтез состоит из двух этапов:

- Кодирование состояний, входных символов автомата;

- Синтез комбинационной части, обеспечивающей получение требуемой функции переходов и выходов.

Пример. Выполним структурный синтез автомата Мили

Продавец. Этот автомат имеет входной алфавит V=[v1,v2], выходной алфавит W=[w1, w2, w3, w4], алфавит состояний S=[s0, s1, s2] и характеризуется таблицей переходов (табл.1) и таблицей выходов (табл.2)

Для кодирования входных и выходных алфавитов и состояний автомата необходимо [log2|V|]=1, [log2|W|]=2, [log2|S|]=2 разрядов соответственно.

Обозначаем структурное представление входа автомата символом x, выходов y1 и y2, состояний символами q1 и q2.

Тогда можно предложить кодирование V, W и S, представленное в табл. 30, а, б и а.

Таблица 30.

а) б) в)

Y	X
y1 y2

W	y1 y2
w1 w2 w3 w4	0 0 0 1 1 0 1 1

S	q1 q2
s0 s1 s2	0 0 0 1 1 1

Используя эти коды построим таблицы переходов и выходов автомата (Табл. 31, а, б)

Табл. 31

а) б)

X	q1 q2
00 01 11
	01 11 00 11 00 00

S	q1 q2
00 01 11
	00 01 10 01 10 10

Общую закодированную таблицу выходов (табл. 31 б) можно расщепить на отдельные таблицы для каждого выходного символа структурного автомата, т.е. для у1 и у2 отдельно (табл. 32 и табл. 33)

Табл. 32 Табл. 33

X	q1 q2
00 01 11 10
0	0 0 1 - 0 1 1 -

X	q1 q2
00 01 11 10
0	0 1 0 - 1 0 1 -

Рассматривая эти таблицы как карты Карно-Вейча, получим

минимизированные выражения для у1 и у2:

y1=q1\ /x&q2;

_{_ __ __}

y2=x&q1&q2 \ / x&q2 \ / x&q1

Закодированную таблицу переходов используем для построения таблиц возбуждения элементов памяти автомата. Таблицы возбуждения должны содержать такие значения входных сигналов каждого триггера, которые бы обеспечивали переключение триггеров в соответствии с таблицей переходов автомата.

Для D-триггеров u_1(t) = q_1(t), т.е. таблица возбуждения совпадает с закодированной таблицей переходов автомата.

Для Т-триггеров u_1(t) = q_1(t) Å q_1(t+1), т.е. значение сигнала возбуждения получается суммированием по mod2 текущего состояния триггера и его требуемого нового состояния.

В нашем примере таблица возбуждения для Т-триггеров имеет вид Табл. 34.

Табл. 34

X	q1 q2
00 01 11
	01 10 11 11 01 11

Расщепим общую таблицу возбуждения на отдельные таблицы для каждой составляющей. (табл. 35 и 36)

X	q1 q2
00 01 11 10
0	0 1 1 - 1 0 1 -

X	q1 q2
00 01 11 10
0	1 0 1 - 1 1 1 -

Рассматривая эти таблицы как карты Карно-Вейча для частичных функций, получим минимизированные значения функций возбуждения q1 и q2:

_{_ __}

q1=x&q2 \ /x&q2\ / q1;

_{__}

q2=q2 \ / q1 \ /x

7.2 Асинхронные автоматы

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

Синхронный автомат может изменять своё состояние только в определённые моменты времени, а именно в моменты поступления синхронизирующих импульсов.

В отличие от синхронных, асинхронный автомат переключается в момент изменения логического значения входных сигналов.

Входные сигналы асинхронного автомата обладают следующими свойствами (рис.38):

-сигнал присутствует на входе автомата в каждый момент времени;

-длительность входного сигнала не ограничена и превышает некоторую минимальную величину.

- изменения входного сигнала могут происходить в произвольные моменты времени.

V(t)

1¹

0¹

t

Функционирование асинхронного автомата можно представить моделью Мура:

S(t+T_i ) = l[S(t), V(t)],

W(t) = m [S(t)],

Где S(t) – состояние автомата;

V(t) – входной символ автомата;

W(t) – выходной символ автомата;

t – непрерывное время;

T_i - время задержки выходного символа по отношению к моменту

изменения входного символа.

Пусть S(t+T_i) = l[S(t), V(1)]=S(1)=S_i при некотором V(1)=V. В этом случае состояние S_i называется устойчивым при входном сигнале V (рис.39 а)

а) б)

V

S_i V S_i S_j

Рис. 39

В противном случае, если S(t+T_i) = l [S(t), V(t)]=S_j, S(t)=S_i

Причём S_j =S_i при некоторой V(t)=V, состояние называется неустойчивым при входном сигнале V (рис 39 б)

При структурном синтезе асинхронных автоматов все полезные (запланированные) состояния должны быть устойчивыми.

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

Поэтому неустойчивые состояния называются транзитными.

На рисунке 40 показан граф иллюстрирующий появление транзитных состояний.

V¹ V¹

V S_i S_j S_k V¹

Рис. 40

Вначале автомат находится в устойчивом состоянии S_i Под действием входного символа V. При замене входного символа V на V¹ переходит в состояние S_k , устойчивое при действии V¹.

В асинхронных автоматах возможно явление, называемое генерацией (рис. 41)

V¹ V¹

V S_i S_j S_k

V¹

Рис. 41

Под действием замены входного сигнала V на V¹ автомат покидает устойчивое состояние и попадает в замкнутую цепочку (цикл) транзитных состояний S_i S_j S_k Вывести автомат из режима генерации можно только путём изменения входного символа.

Дата добавления: 2015-10-23