Логическое проектирование конечных автоматов

 

Под автоматом понимается устройство, самостоятельно производя­щее все операции. Автомат может быть представлен структурой, состоящей из элементов памяти и комбинационной схемы (рис. 9.1). Состояние выхода автомата в каждый, рассматриваемый момент времени определяется не только состоянием входов в данный момент времени, но и внутренним состоянием схемы в момент подачи входных сигналов. В свою очередь, внутреннее состояние схемы зависит от состояния её входов в предшествующий момент времени, а, следовательно, определяется последовательностью поступления входных сигналов. На входы комбинационной схемы поступают внешние сигналы , , …, , и внутренние сигналы , , …, , снимаемые с выхода, входящего в состав схемы, запоминающего устройства. Под воздействием сигналов , , …, и , , …, комбинационная схема формирует последовательность сигналов , , …, на выходе ДУ и внутренние сигналы , , …, , поступающие на входы запоминающего устройства.

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

Автоматы можно подразделить на синхронные и асинхронные [1–4, 6, 9]. В син­хронных автоматах переход из одного состояния в другое происходит под воздействием синхронизирующих сигналов. В асинхронных автоматах моменты перехода из одного состояния в другое заранее не определены и могут совершаться через неравные между собой промежутки времени.

Известны две модели синхронных элементарных автоматов: модель Мура и модель Мили, получивших названия по имени ученых, разрабо­тавших соответствующие разделы теории автоматов.

Моделью Мура называется автомат, описываемый уравнениями:

 

(9.1)

 

где S (t), S (t – 1) – состояния автомата в моменты времени t и t – 1;
X (t – 1), Z (t) – входные и выходные сигналы автомата в моменты времени t и t – 1.

Моделью Мили называется автомат, описываемый уравнениями:

(9.2)

 

Следовательно, состояние S (t) автомата, при его описании любой моделью, однозначно определяется его входными символами и внутренним состоянием в предшествующий момент времени: t – 1. Сигнал на выходе автомата у (t) в рассматриваемый момент времени t в модели Мура полностью определяется состоянием S (t) автомата в данный момент времени, а в модели Мили не только его внутренним состоянием S (t), но и состоянием входных сигналов.

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

Графический способ предусматривает задание автомата направленным графом, вершинами которого являются состояния автомата, а ребрами – комби­нации входных сигналов, вызывающие переход автомата из одного состояния в другое (рис. 9.2, а, б) [1–3, 6–9]. Петля при вершине графа свидетельствует о том, что данный входной сигнал не вызывает изменения состояния автомата. При задании автомата моделью Мура состояния выходов указываются непосредственно в узлах графа, так как полностью определяются внутренним состоянием автомата и не зависят от комбинации входных сигналов (рис. 9.2, а). В модели Мили выходные сигналы указываются над ребрами графа, рядом с комбинациями входных сигна­лов, так как определяются не только состоянием автомата, но и сигналами на его входе (рис. 9.2, б).

 

 

Рис. 9.2. Задание автомата графическим способом: а – при описании автомата моделью Мура; б – моделью Мили

Таблично-матричный способ предусматривает задание автомата путём записи всей необходимой информации о его функционировании в специальные автоматные таблицы, называемые таблицей переходов и таблицей выходов (рис. 9.3).

 

Рис. 9.3. Задание автомата графическим способом: а – при описании автомата моделью Мура; б – моделью Мили

 

На пересечении строк и столбцов автоматных таблиц соответствен­но указываются внутренние состояния, в которые переходит автомат под действием входных сигналов и выходные сигналы, которые он при этом выдает. Наряду с автоматными таблицами, при описании автоматов широко используются матрицы соединений. Число строк и столбцов данной мат­рицы соответствует числу состояний автомата, а на пересечении j -й строки и k -го столбца указываются комбинации входных сигналов, приводящие к переходу автомата из состояния j в состояние k.

Аналитический способ предусматривает задание автомата систе­мой секвенциальных уравнений, называемой секвенциальным описанием автомата и составляемой на основе графа или автоматных таблиц:

 

для модели Мура	для модели Мили
.	.

 

Каждое такое уравнение представляет со­бой запись вида , означающую, что истинность утверждения a одно­значно предопределяет истинность утверждения b. При составлении секвенциальных уравнений отдельно описываются совершаемые автоматом переходы и формируемые в каждом состоянии символы (сигналы) на выходе автомата.

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

Для модели Мура

Для модели Мили

^.

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

 

для модели Мура	для модели Мили
	.

 

В качестве примера рассмотрим реализацию в базисе «И–НЕ» автомата заданного моделью Мура (см. рис. 9.2, а). Полученные для рассматриваемого автомата сокращенные секвенции имеют вид:

 

;

;

;

; .

 

Для построения на основе полученного секвенциального описания структуры ав­томата необходимо наличие двух блоков: 1) реализации переходов, определяющих состояния автомата, и 2) реализации функций выхо­да. Для управления элементами памяти синтезируемого автомата функции , , необходимо использо­вать в качестве переключающих сигналов. С целью уменьшения тре­буемого объема памяти, любому состоянию автомата удобно поставить в соответствие некоторую кодовую комбинацию, определяемую состоянием всех триггеров автомата (табл. 9.1).

Таблица 9.1