Синтез абстрактного автомата

Автоматом называется дискретное устройство, способное принимать различные состояния, под воздействием входных сигналов переходить из одного состояния в другое и вырабатывать выходные сигналы [10].

Математической моделью устройства с памятью является абстрактный автомат, который представляет собой совокупность пяти конечных множеств:

где A={a0, a1, .aM} - множество состояний автомата;={Z1, Z2, .ZF} - множество входных сигналов;={W1, W2, .WC} - множество выходных сигналов;

d - функция переходов, обеспечивающая выработку последующего состояния as автомата в зависимости от существующего состояния aM и входного воздействия Zf;

l - функция выходов, обеспечивающая выработку выходного сигнала автомата в зависимости от его состояния aM и входного сигнала Zf.

Абстрактный автомат имеет один входной и один выходной каналы, и каждой букве входного алфавита Z ставит в соответствие букву или слово выходного алфавита W.

Наибольшее распространение получили автоматы Мура и Мили. Закон функционирования автомата Мили записывается следующим образом:

Работа автомата Мура определяется следующими уравнениями:

где t = 0, 1, 2

Автомат называется синхронным, если он описывается a(t) и W(t) как автомат Мили. Автомат называется асинхронным, если его функция переходов описывается выражением a(t+1) = d(a(t+1), Z(t)).

В синхронном автомате осуществляется синхронизация внешних и внутренних сигналов, в то время как в асинхронном этого нет, и для представления последовательности одинаковых букв вводится какая-либо разделяющая их буква, не несущая информации.

Наиболее распространенным способом задания автомата является таблица переходов и таблица выходов. На пересечении i-й строки и j-го столбца таблицы переходов указывается то внутренне состояние, в которое автомат перейдет из внутреннего состояния Si (i-я строка) под действием входных сигналов, соответствующих состоянию входа Xj (j-й столбец).

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

Автомат, предложенный для синтеза, задан таблицей переходов (табл. 2.1) и таблицей выходов (табл. 2.2).

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

Таблица 2.1 - Таблица переходов Таблица 2.2 - Таблица выходов

Следовательно, нам необходимо иметь три элемента памяти. Теперь закодируем состояния автомата (табл. 2.3) и в соответствии с полученной кодировкой перезапишем таблицу переходов (табл. 2.4) и таблицу выходов (табл. 2.5). Кодирование состояний заключается в сопоставлении каждому внутреннему состоянию автомата одной из двоичных комбинаций. Например, состоянию S0 поставим в соответствие двоичную комбинацию 000. Затем составляется кодированная таблица переходов, образующаяся из исходной путем замены символов, описывающих состояния, их двоичными комбинациями.

Таблица 2.3 Таблица 2.4 Таблица 2.5

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

Читайте также

Приемник многоканальной линии связи
Любое радиоприемное устройство включает в себя приемную антенну, радиоприемник и оконечное устройство, служащее для воспроизведения сигналов. Существует классификация радиоприемник ...

Оценка производительности каналов и мониторинг корпоративной сети
В последнее время всё чаще документооборот и передача корпоративной информации совершается в электронном виде тем или иным способом. Для этого уже существует множество протоколов и метод ...

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