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

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

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

Перейти на страницу: 1 2 3

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

Проектирование дискретного устройства
На современном этапе развития транспорта наблюдается бурный рост темпов и объемов перевозок, особенно на железнодорожном транспорте в силу высокой скорости и невысокой стоимости грузопер ...

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

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

Основные разделы

Все права защищены! (с)2019 - www.generallytech.ru