1.4 Последовательность синтеза синхронных управляющих автоматов

Любой автомат может быть реализован в виде автомата на жесткой или гибкой логике. Последовательность синтеза автоматов с жесткой логикой следующая:

• выбор типа элементов памяти;

• кодирование состояний автомата, входных и выходных сигналов в структурном алфавите;

• детализация блока памяти;

• составление расширенной структурной таблицы переходов и выходов;

• канонический синтез логического преобразователя;

• минимизация функций выходов и возбуждения блока памяти.

2 Анализ граф схемы алгоритма суа и детализация бп

2.1 Исходные данные и задание на курсовую работу

Требуется синтезировать управляющий автомат типа Мили. Работа автомата задана его ГСА. При проектировании,которого состояния кодируются первым эффективным способом. Блок памяти реализуется с использованием Т-триггеров.

Для применения общепринятых методов синтеза исходную постановку задачи необходимо формализовать, т.е. привести ее к каноническим формам описания управляющих автоматов. Обычно при проектировании используется методика синтеза микропрограммных управляющих автоматов, основанная на использовании граф-схем алгоритмов (ГСА). В задании на курсовой проект была предложена ГСА, представленная на Рисунке 4.

Рисунок 4 - ГСА синтезируемого автомата

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

Выходные сигналы, формирующиеся во время работы автомата имеют вид:

2.2 Разметка граф-схемы алгоритма

Функционирование абстрактного автомата может быть описано с помощью двух моделей - модели Мура и модели Мили, отличающихся принципами формирования выходных сигналов и числом внутренних состояний. Переход от алгоритмического описания к автоматному осуществляется путем разметки ГСА в соответствии с выбранной моделью абстрактного автомата. В задании на курсовой проект была предложена модель Мили.

Правила разметки ГСА при реализации автомата по модели Мили:

- символом начального состояния а₁отмечается вход вершины, следующей за начальной, а также вход конечной вершины ГСА;

-входы всех вершин, следующих за операторными, отмечаются различными символами а₂…а_i…а_n;

-входы вершин ГСА, следующих за операторными, должны быть отмечены только одним единственным символом а_i.

Для циклически выполняемых алгоритмов за начальное состояние автомата может быть взято любое его допустимое состояние, которое выбирают произвольным образом и отмечают символом а₁. Все последующие состояния такого (не инициального) автомата отмечаются символами а₂…а_i …а_n. В не инициальных автоматах за начальное его состояние может быть взято любое из допустимых состояний автомата

Разметка ГСА по указанным правилам показана на Рисунке 5.

В результате разметки ГСА по указанным правилам удается определить множество внутренних состояний УА (формула 1), определяющих мощность этого множества

(1)

Так, для данной ГСА мощность равна .

Рисунок 5 - Размеченная ГСА синтезируемого автомата