Пример синтеза автомата с памятью

Задание. Синтезировать автомат с одним входом. На вход автомата поступает произвольная последовательность символов 0 и 1. Автомат должен выдать сигнал 1, если на его вход поступила последовательность символов 101.

Заданы:

тип ЦА — автомат Мура;

тип элементов памяти — D-триггеры;

тип логических элементов — элементы И, ИЛИ, НЕ.

Задание выполним в соответствии с п. 1.2.

Формализация задания. Количество входов автомата указано в задании. Так как автомат должен выдавать только сигналы 1 и 0, то можно использовать один выход. (Заметим, что можно принять унарное кодирование выходных сигналов, при котором для сигналов 1 и 0 назначаются отдельные выходы). Тогда обобщенная схема автомата может иметь вид, показанный на рис. 1.1.

Выбор типа автомата. В качестве типовой структуры задан автомат Мура.

??? ??? ???? ???

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

Составление таблицы переходов и выходов. Для графа, приведенного на рис. 1.2., таблица переходов и выходов имеет вид таблицы 1.1.

??? ??? ???? ???

Таблица 1.1.

Кодирование состояний. Определим количество элементов памяти:

n = log23­ =2.

Элементы памяти обозначим следующим образом:

q1 — первый элемент памяти;

q2 — второй элемент памяти.

Кодирование состояний проводится естественным способом:

??? ??? ???? ???

При таком кодировании считается, что, например, в состоянии автомата Q1 первый элемент памяти (q1) находится в состоянии 0, а второй -(q2) — в состоянии 1.

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

Таблица 1.2.

Выбор типа элементов памяти. В качестве элементов памяти заданы D-триггеры.

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

Запись функций возбуждения и функций выходов в СДНФ. Автомат имеет два элемента памяти (два D-триггера) и каждому триггеру соответствует одна функция возбуждения:

_ _ _.

Функции возбуждения: D1 = q1t+1 = xq1tq2t v xq1tq2t.

_ _ _ _.

D2 = q2t+1 = xq1tq2t v xq1tq2t v xq1tq2t v xq1tq2t.

Автомат имеет один выход и, соответственно, одну функцию выхода. Для автомата Мура выходной сигнал зависит только от текущего состояния. В данном примере сигнал Y принимает значение 1 только в случае, если автомат находится в состоянии Q3. Тогда функция выхода записывается в следующем виде:

Yt = q1tq2t .

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

??? ??? ???? ???

Функция выхода и функция D1 не минимизируются.

Минимизация функций возбуждения может быть проведена и методом Карно. Диаграммы Карно для функций D1 и D2 приведены на рис. 3.3. При этом результат минимизации получается тот же, что и при непосредственном преобразовании.

Выбор типа логических элементов. В качестве логических элементов заданы элементы И, ИЛИ, НЕ.

Преобразование функций возбуждения и функций выходов к виду, удобному для реализации на выбранных логических элементах. Для элементов И, ИЛИ, НЕ такое преобразование не выполняется.

Построение функциональной схемы автомата. С учетом общей структуры автомата Мура и наличия двух элементов памяти (D-триггеров) функциональная схема автомата может быть представлена в виде рис. 1.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.). Таким образом, при рассмотренном сочетании текущего состояния и входного сигнала автомат работает правильно.