Порядок синтеза автомата с памятью 3. Порядок синтеза автоматов с памятью3.1. Последовательность синтеза автоматов с памятью лгоритм работы автомата с памятью вначале задается в виде словесного описания. В этом случае синтез автоматов с памятью состоит из следующих этапов: формализация задания; выбор типа автомата; составление графа состояний автомата; составление таблицы переходов и выходов; кодирование состояний; составление кодированной таблицы переходов и выходов; выбор типа элементов памяти; преобразование таблицы переходов и выходов в таблицу функций воз- буждения триггеров; запись функций возбуждения и функций выходов в СДНФ; минимизация функций возбуждения и функций выходов; выбор типа логических элементов; преобразование функций возбуждения и функций выходов к виду, удобному для реализации на выбранных логических элементах; построение функциональной схемы автомата; проверка правильности работы автомата.Приведенная последовательность соответствует самому общему случаю синтеза. В некоторых случаях в зависимости от способа задания автомата и других исходных данных некоторые этапы могут отсутствовать или совмещаться с другими этапами. 3.2. Краткая характеристика этапов синтезаКак было показано в п.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 сравниваются с данными таблицы переходов и выходов. При совпадении ожидаемых и полученных результатов делается вывод о правильности синтеза автомата. Для реальных автоматов с большим количеством состояний и входов выполнение проверки вручную становится затруднительным. Для этой цели в настоящее время используются специальные программы. 3.3. Пример синтеза автомата с памятьюЗадание. Синтезировать автомат с одним входом. На вход автомата поступает произвольная последовательность символов 0 и 1. Автомат должен выдать сигнал 1, если на его вход поступила последовательность символов 101. Заданы: тип ЦА - автомат Мура; тип элементов памяти - D-триггеры; тип логических элементов - элементы И, ИЛИ, НЕ. Задание выполним в соответствии с п.3.2.Формализация задания. Количество входов автомата указано в задании. Так как автомат должен выдавать только сигналы 1 и 0, то можно использовать один выход. (Заметим, что можно принять унарное кодирование выходных сигналов, при котором для сигналов 1 и 0 назначаются отдельные выходы). Тогда обобщенная схема автомата может иметь вид, показанный на рис. 3.1.Выбор типа автомата. В качестве типовой структуры задан автомат Мура.Составление графа состояний автомата. В соответствии с заданным алгоритмом работы граф состояний автомата может быть представлен в виде рис. 3.2. На рис.3.2. представлен вариант алгоритма, при котором анализ входной последовательности производится группами по три символа, т.е. конец одной последовательности не является началом другой последовательности.Составление таблицы переходов и выходов. Для графа, приведенного на рис. 3.2., таблица переходов и выходов имеет вид таблицы 3.1.Таблица 3.1 Входы Состояния и выходы Y=0 Y=0 Y=0 Y=1 X Qt = Q0 Qt = Q1 Qt = Q2 Qt = Q3 0 Q0 Q2 Q0 Q0 1 Q1 Q1 Q3 Q1 Кодирование состояний. Определим количество элементов памяти: n = log23 =2.Элементы памяти обозначим следующим образом: q1 - первый элемент памяти; q2 - второй элемент памяти.^ К одирование состояний проводится естественным способом: При таком кодировании считается, что, например, в состоянии автомата Q1 первый элемент памяти (q1) находится в состоянии 0, а второй -(q2) - в состоянии 1.Составление кодированной таблицы переходов и выходов выполним путем преобразования таблицы переходов и выходов с заменой состояний автомата Qi их двоичными номерами в соответствии с принятым вариантом кодирования состояний. Кодированная таблица переходов и выходов имеет вид табл. 3.2. Таблица 3.2 Входы Состояния и выходы Y=0 Y=0 Y=0 Y=1 X Qt = Q0 Qt = Q1 Qt = Q2 Qt = Q3 _ _q1q2 _ q1q2 _q1q2 q1q2 00 01 10 11 0 00 10 00 00 1 01 01 11 01 ^ Выбор типа элементов памяти. В качестве элементов памяти заданы D-триггеры. Преобразование кодированной таблицы переходов и выходов в таблицу функций возбуждения триггеров выполняется в случае, если в качестве элементов памяти используются триггеры любого типа, кроме D-триггеров. В данном случае такое преобразование не делается, так как функции переходов автомата являются одновременно и функциями возбуждения D-триггеров (см. логику работы D-триггера).Запись функций возбуждения и функций выходов в СДНФ. Автомат имеет два элемента памяти ( два D-триггера ) и каждому триггеру соответствует одна функция возбуждения: _ _ _ Функции возбуждения: D1 = q1t+1 = xq1tq2tv xq1tq2t _ _ _ _ D2 = q2t+1 = xq1tq2tv xq1tq2tv xq1tq2tv xq1tq2tАвтомат имеет один выход и, соответственно, одну функцию выхода. Для автомата Мура выходной сигнал зависит только от текущего состояния. В данном примере сигнал Y принимает значение 1 только в случае, если автомат находится в состоянии Q3. Тогда функция выхода записывается в следующем виде: Yt = q1tq2t .Минимизация функций возбуждения и функций выходов. При анализе вида функций D1, D2 и Yt можно установить, что функция D2 может быть минимизирована. При использовании метода непосредственных преобразований м _ _ _ _ _ _ _ _ D2 = xq1tq2t Ú xq1tq2t Ú xq1tq2t Ú xq1tq2t = ( xq1tq2t Ú xq1tq2t ) Ú ( xq1tq2t Ú _ _ _ _xq1tq2t )= xq1t ( q2t Ú q2t ) Ú xq1t (q2t Ú q2t ) = xq1t Ú xq1t = x .инимизация выполняется следующим образом: Функция выхода и функция D1 не минимизируются. Минимизация функций возбуждения может быть проведена и методом Карно. Диаграммы Карно для функций D1 и D2 приведены на рис. 3.3. При этом результат минимизации получается тот же, что и при непосредственном преобразовании. D1D2 1 1 1 1 1 1 Выбор типа логических элементов. В качестве логических элементов заданы элементы И, ИЛИ, НЕ.Преобразование функций возбуждения и функций выходов к виду, удобному для реализации на выбранных логических элементах. Для элементов И, ИЛИ, НЕ такое преобразование не выполняется.Построение функциональной схемы автомата. С учетом общей структуры автомата Мура и наличия двух элементов памяти (D-триггеров) функциональная схема автомата может быть представлена в виде рис.3.4.Проверка правильности работы автомата. Для проверки правильности работы автомата рассмотрим случай, когда автомат находится в состоянии Q1 и на его вход поступает сигнал х = 0. В этом случае:Qt = Q1, т.е. q t1 = 0 и q t2 = 1 (см. кодирование состояний), x = 0.Значения сигналов на входах элементов схемы для этого случая показаны на рис. 3.4. В соответствии с логикой работы элементов схемы на входы триггеров поступают сигналы, показанные на рис.3.4. При условии, что сигнал синхронизации принимает значение С = 1, оба триггера изменят свое состояние, т.е. q t+11 = 1 и q t+12 = 0. Тогда в соответствии с принятым кодированием состояний получим, что Qt+1 = Q2 , т.е. автомат из состояния Q1 перешел в состояние Q2 .После перехода в состояние Q2 на выходе схемы формируется сигнал Y = 0. При сравнении состояния Qt+1 и полученного выходного сигнала можно установить, что они совпадают с данными таблицы переходов и выходовавтомата (табл. 3.1.). Таким образом, при рассмотренном сочетании текущего состояния и входного сигнала автомат работает правильно.^ Контрольные вопросы Какие способы описания алгоритмов обычно используют при синтезе авто- матов с памятью?Перечислите основные этапы синтеза автоматов с памятью.От чего зависит множество входных сигналов автомата с памятью?В каких случаях меняется состояние автомата с памятью?Как определить число возможных состояний автомата с памятью, если из- вестно число элементов памяти?Как по таблице переходов записать функции переходов?Как проверить правильность работы автомата с памятью?Как влияет тип автомата с памятью на последовательность проверки его работоспособности?Какими уравнениями описывается логика работы комбинационной схемы, формирующей состояния автомата?