Абстрактный синтез автоматов

Пусть алгоритм управления ОУ задан рис. 57. При составлении ГСА проектировщик глубоко изучил структуру ОУ с учетом смысла сигналов и логических условий α ₁, α ₂, α ₃ для достижения цели управления (преобразования { x } в { y } согласно модели В.М. Глушкова). Для проектирования автомата управления можно абстрагироваться от смысла (семантики) элементов множеств { c } и { α } и переходить к построению формального описания функционирования автомата, реализующего ГСА. Общая схема системы будет иметь вид рис. 58, где обозначено:

X, Y – множества входных и выходных переменных ОУ;

с ₁, с ₂, …, с_к – сигналы управления для ОУ (выходы схемы СА);

СА – схема автомата;

Z₁, Z₂, …, Z _p – внутренние переменные автомата, формируемые схемой СА;

Z _i (t) и Z_i(t + 1) – значения переменных в момент t, и после подачи очередного импульса синхронизации, т.е. в момент времени t + 1;

ПА – память автомата;

СС – схема синхронизации;

τ – сигнал синхронизации;

– сигнал синхронизации, действующий после сигнала τ, т.е. Ø.

Заметим, что в отличие от ранее рассмотренного примера (рис. 58) выходные переменные операционного устройства (ОУ) на рис. 58 заданы множеством { α }. Это более распространенное обозначение для более общих моделей систем управления (рис. 32). В предыдущем примере рассмотрен частный случай автомата, когда часть множества {X} и есть { α } – см. рис. 32 в.

Рассмотрим вначале так называемый автомат Мура. В автоматах Мура следующее состояние а(t + 1) определяется как система булевых функций F₂, зависящая от номера (или кода) состояния автомата а(t) и множества логических сигналов { α }, а выходные сигналы с (t) задаются системой булевых функций F₁, зависящих только от состояния а(t) и не зависящих от { α }.

Рис. 57

Рис. 58

Определим формальное описание функционирования автомата в виде графа переходов и набора булевых функций, определяющих выходные сигналы { c }. Произведем разметку ГСА, выполнив несколько этапов формальных действий.

Этап 1.

1. Отметим все операторы действия (кроме логических) с помощью последовательно занумерованных меток а _i (i = 0, 1, 2, …). Справа рядом с отмеченным оператором на рис. 57 поставлен номер а _i в кружочке.

2. Будем расставлять метки a _i от оператора а₀ (начало) до конца а _к по наиболее длинному пути. Оператор окончания в ГСА также помечается меткой а₀. В данной схеме оба пути (как при α ₂= 0, так и при α ₂= 1) одинаковы по длине. Поэтому предпочтем путь α ₂= 0.

3. Далее так же отметим все не помеченные по пункту 2 операторы. На рис. 57 это метка а₉ при α ₂= 1.

Этап 2.

1. Отмеченные операторы соответствуют внутренним состояниям автомата α_i (здесь i = ), через которые в дальнейшем определяются переменные Z _j (j = 1, 2, …, p) в зависимости от выбранного проектировщиком способа кодирования множества состояний автомата {a}.

2. Выпишем систему булевых функций F₁, соответствующих правилу формирования выходных сигналов {c} как функций состояний. Для данного примера получим:

3. Обозначим каждое состояние а _i в виде вершины графа.

Рис. 59

4. Соединим i и j вершины графа направленной стрелкой в том случае, если на ГСА есть путь от a _i к a _j (i, j = ). Для данного примера получим граф переходов автомата из состояния a _i в другое a _j в виде рис. 59. Переход из состояния a _i в любое другое a _j согласно графу рис. 59 происходит в момент t после поступления импульса синхронизации (обозначим τ), т.е. состояние а(t) сменится на a(t +1).

5. Выпишем систему булевых функций F₂, определяющих переходы a(t)→a(t + 1). Тогда получим следующую запись по графу переходов:

Заметим, что на рис. 59 можно было бы не указывать сигнал τ, т.е. писать не τ а _j, а просто а _j или а _j совместно с неким логическим условием, например , т.к. и так ясно, что все переходы в автомате осуществляются при наличии сигнала синхронизации τ. Однако не принято опускать этот сигнал τ как признак наличия «автоматного времени».

Этапы 1 и 2 обозначили так называемый формальный синтез автомата, в результате которого определился граф переходов автомата и вид функций F₁ и F₂. Следует заметить, что формальный «закон» функционирования автомата Мура может быть задан не только графом переходов и системами F₁ и F₂. Зная граф переходов, можно составить таблицу переходов с одновременным отображением в ней как переходов, так и выходных сигналов. Нетрудно видеть, что графу рис. 59 соответствует таблица 24.

Таблица 24

a(t + 1) a(t)


	α₁
			α₂


		α₃

Иногда в такой таблице (напоминающей МСА) в каждой клетке при наличии перехода по условию (без условия ставится 1) через черточку ставится обозначения сигналов управления. Впрочем, для автоматов Мура в таком обозначении нет необходимости, т.к. функции выходов F₁ не зависят от α. Можно записать обобщенно правило функционирования автомата Мура в виде: