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

Автоматом называется дискретное устройство, способное принимать различные состояния, под воздействием входных сигналов переходить из одного состояния в другое и вырабатывать выходные сигналы [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

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

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

Поверка электронного вольтметра В7-26 по напряжению постоянного тока
Считается, что первый вольтметр изобрел М. Фарадей, причем в 1830 году, ещё за год до того, как он же открыл явление электромагнитной индукции, на котором основано действие целого класса ...

Принцип работы оптоволоконных сканеров отпечатков пальцев
Идентификация по отпечаткам пальцев - на сегодня самая распространенная биометрическая технология. По данным International Biometric Group, доля систем распознавания по отпечаткам пальце ...

Проект оконечной ОС на базе системы DX200
Современное состояние и перспективные планы развития Единой Сети Электросвязи (ЕСЭ) Российской Федерации характеризуются широким внедрением цифровых технологий и оборудования цифровых си ...