Материал: Ковригин Теория автоматов Лабораторный практикум 2012

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

Рис. 2.1. Структура синхронного конечного автомата Мили

Память состояний автомата состоит из k запоминающих элементов (ЗЭ), каждый из которых под действием синхронизирующего сигнала С может устанавливаться в состояние 0 или 1. Состояние запоминающих элементов определяет текущее состояние автомата.

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

Выходные сигналы Y автомата определяются комбинационной схемой КС2 как функция входных сигналов X и текущего состояния автомата S.

16

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

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

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

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

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

17

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

Пример

Постановка задачи. Спроектировать синхронный конечный автомат Мили с одним входом X и одним выходом Y. При X = 0 автомат последовательно принимает состояния 0,1,2,4,5,0,1,…; при X = 1 0,1,5,6,4,7,0,1,… (последовательности циклические). Автомат на выходе Y формирует сигнал 1 при X = 0 в состоянии 5; при X = 1 в состоянии 4. В остальных состояниях автомата Y = 0.

В качестве элемента памяти использовать D-триггер. Автомат должен иметь вход установки в начальное состояние.

Составление кодированной таблицы переходов и в ыходов

Вначале необходимо определить, сколько потребуется двоичных переменных для представления состояний в таблице переходов. Из анализа исходных данных (условия задачи) следует, что автомат может принимать семь различных состояний: 0,1,2,4,5,6,7. Таким образом, минимальное число двоичных разрядов, необходимое для кодирования этого количества состояний, равно трем.

Далее необходимо присвоить конкретному состоянию двоичную комбинацию, которую назовем кодом состояния автомата. В нашем случае естественно сопоставить каждому номеру состояния его двоичный номер, 0 = 0002, 1 = 0012, 4 = 1002 и т.д. Обозначим двоичные разряды кода состояния через Q2, Q1, Q0.

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

Получить кодированную таблицу переходов автомата просто. Для этого необходимо в одном столбце записать значение входа X и соответствующие двоичные коды состояний автомата Q2, Q1, Q0. Эти состояния отнесем к моменту времени t и будем называть текущим состоянием автомата. Текущие состояния автомата записаны в колонках 1-4 табл. 2.1.

Затем в следующем столбце напротив каждого двоичного набора предыдущего столбца запишем новое состояние автомата, в ко-

18

торое он перейдет после поступления синхронизирующего сигнала. Например, если текущее состояние автомата при X = 0 равно Q2,Q1,Q0 = 100, то новое состояние автомата, в которое он должен перейти в соответствии с исходными условиями задачи, будет равно 101. Данные состояния отнесем к моменту времени t+1 и будем называть следующим (будущим) состоянием автомата. Следующие состояния автомата записаны в колонках 5-7 табл. 2.1. В восьмой колонке задано состояние выхода Y автомата в текущий момент времени t.

Кодированная таблица переходов опpeделяет зависимость состояний запоминающих элементов Q2(t+l), Q1(t+l) и Q0(t+l) в момент времени t+1 от значения входного сигнала и внутренних состояний запоминающих элементов в предыдущий момент времени. В кодированной таблице выходов выходной сигнал Y определен в зависимости от значения входного сигнала в момент времени t и внутренних состояний запоминающих элементов в этот же момент времени.

19

Составление таблицы возбужд ения автомата

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

В нашем случае тип триггера задан в условии задачи – это D-триггер. В библиотеке базовых элементов ПЛИС XC10PC84 синхронный D-триггер с асинхронной установкой в 0 имеет имя FDC. Условное графическое обозначения D-триггера FDС и его таблица переходов приведены на рис. 2.2.

Рис. 2.2. Условное графическое обозначение D-триггера FDС и его таблица переходов

В этом обозначении: С прямой синхронизирующий вход, CLR (Clear) – асинхронный вход установки триггера в 0, D – логический вход данных. В таблице переходов D-триггера: – произвольное значение, 0/1 – изменение синхросигнала из 0 в 1.

С помощью кодированной таблицы переходов можно определить для всех трех D-триггеров способ формирования входных сигналов D2, D1 и D0. Для формирования каждого из входных сигналов D2, D1 и D0 (выходов комбинационной схемы КС1) используются входной сигнал Х в момент времени t и выходные сигналы, определяемые состояниями триггеров в тот же момент времени t

(см. рис. 2.1).

20