Краткая характеристика этапов синтеза

Как было показано в п. 1.1, типовая структура автомата с памятью состоит из двух комбинационных схем (КС1 и КС2), между которыми установлены элементы памяти. Поэтому синтез автомата с памятью сводится к синтезу двух комбинационных схем. Для этого необходимо построить таблицу переходов и выходов автомата, которая представляет собой перестроенную таблицу истинности функций переходов и выходов. Поскольку вид этой таблицы зависит от типа автомата и типа элементов памяти, исходная таблица подвергается некоторым преобразованиям. Рассмотрим содержание отдельных этапов синтеза.

Формализация задания включает определение числа входов и выходов автомата и их обозначение, определение алфавита входных и выходных сигналов и установление соответствия логических значений входных и выходных сигналов и их смысла в соответствии с заданием.

Выбор типа автомата заключается в том, что для разработки принимается одна из двух типовых структур — автомат Мура или Мили. Вообще схемы автоматов Мура и Мили, реализующих один и тот же алгоритм, отличаются друг от друга по сложности. Однако в настоящее время не существует способа определить заранее, какая из двух структур окажется проще. Поэтому для обоснованного выбора типа автомата необходимо построить схемы автоматов Мура и Мили и сравнить их сложность.

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

Например, если автомат с одним входом должен определить факт поступления на вход последовательности входных сигналов «1 0 1 «, то в начальном состоянии при поступлении символа «0 «автомат не меняет состояния, так как этот символ не является началом нужной последовательности. При поступлении же символа «1 «автомат должен запомнить, что первый символ последовательности уже поступил. Запоминание этого факта автомат выполняет, меняя свое состояние. Образно говоря, автомат в этом случае «настораживается» .

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

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

Составление таблицы переходов и выходов выполняется по графу состояний автомата. По существу таблица переходов и выходов является табличной формой представления графа. Вид таблицы переходов и выходов для автоматов Мили и Мура несколько отличается (см. п. 1.2).

Кодирование состояний заключается в том, что каждому состоянию автомата (Qi) ставится в соответствие состояние отдельных элементов памяти (qi). Например, для автомата с тремя элементами памяти за состояние Q0 может быть принято такое состояние, при котором все три элемента памяти находятся в состоянии «0» (в каждом элементе памяти записан «0»). Обычно кодирование состояний сводится к замене обозначения состояний вида Qi их двоичными номерами. Такой способ кодирования состояний называют естественным. Количество элементов памяти (n) определяется числом состояний автомата (N):

n = log2N­,.

где ­означает, что результат округляется в большую сторону.

Составление кодированной таблицы переходов и выходов означает замену обозначения состояний вида Qi их двоичными номерами. При этом обозначения выходных сигналов остаются без изменения.

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

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

Запись функций возбуждения и функций выходов в СДНФ выполняется по таблице функций возбуждения триггеров так же, как запись функций по таблице истинности.

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

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

Построение функциональной схемы автомата следует начинать с уточнения общей структуры (состава и расположения комбинационных схем КС1 и КС2). Далее в соответствии с функциями возбуждения и функциями выходов определяются типы и количество логических элементов, а также связи между элементами. Функциональная схема вычерчивается с использованием условно-графических обозначений (УГО) элементов в соответствии с требованиями ГОСТов.

Проверка правильности работы автомата выполняется для различных сочетаний текущего состояния и входных сигналов автомата. Для автомата Мили по заданному текущему состоянию (Qt) и входному сигналу (Xt) вначале определяется значение выходного сигнала (Yt), а затем определяется следующее состояние автомата (Qt+1). Для автомата Мура по значению Qt и Xt вначале определяется следующее состояние автомата (Qt+1) а затем по значению Qt+1 определяется значение выходного сигнала (Yt+1). Полученные значения Qt+1 и Yt сравниваются с данными таблицы переходов и выходов. При совпадении ожидаемых и полученных результатов делается вывод о правильности синтеза автомата.

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