Тема: Проектирование машин состояний

Цель работы:

Получение навыков синтеза и моделирования машин состояний в САПР Altera MAX+PLUS II.

Задачи:

Задать временными диаграммами работы машину состояний с заданными параметрами в САПР Altera Max+plus II в режиме редактора временных диаграмм (WaveForm Editor). Произвести исследование временных параметров полученной модели (Simulator).

Теоретические сведения:

Разработка описания проекта в редакторе временных диаграмм является альтернативой его созданию в графическом редакторе. Здесь можно графическим способом задавать комбинации входных логических уровней и требуемых выходов. Созданный таким образом файл (.wdf) может содержать как логические входы, так и входы цифрового автомата, а также выходы комбинаторной логики, счётчиков и цифровых автоматов. Способ разработки дизайна в редакторе временных диаграмм лучше подходит для цепей с чётко определёнными последовательными входами и выходами, то есть для цифровых автоматов, счётчиков и регистров.

Для формирования некоторой выходной последовательности сигналов Y, соответствующей некоторой входной последовательности сигналов X, часто используют последовательную схему, называемую конечным автоматом, или машиной состояний (state machine). Конечный автомат – это устройство с памятью, выходные сигналы которого зависят от предыстории поступления входных сигналов. При этом множество входных сигналов X={x₁…x_L}автомата определяется множеством логических условий, которые необходимо обработать, а множество выходных сигналов Y={y₁…y_L}автомата определяется множеством сигналов, являющихся результатом его работы.

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

В зависимости от способа формирования выходных сигналов выделяют два класса конечных автоматов:

· Автомат Мура – автомат, выходные сигналы которого зависят только от текущего состояния автомата;

· Автомат Мили – автомат, выходные сигналы которого зависят от текущего состояния автомата и от текущих входных сигналов.

Состояние автомата определяется состоянием его памяти. Т.к. память автомата строится на триггерах, соответственно состояние памяти характеризуется двоичным набором, отображающим состояние триггеров. Данный двоичный набор называется кодом состояния автомата. Число триггеров n, используемых для реализации памяти автомата, определяется числом состояний автомата N и способом их кодирования:

· Двоичное кодирование. При этом n=|log₂N|.

· Унитарное кодирование (одно состояние – один триггер). При этом n=N.

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

В данной работе, мы будем проектировать конечный автомат (машину состояний) Мура, имеющий 4 состояния:

1. Входными данными нашего автомата будет номер состояния, в которое мы хотим перейти из текущего состояния. При этом состояния кодируются следующим образом: State_A = 0, State_В = 1, State_C = 2, State_D = 3. Т.к. автомат имеет 4 состояния, нам понадобится 2 входа (log₂(4)=2).

2. Выходными данными нашего автомата будет номер его состояния. Т.е. когда автомат находится в состоянии State_A на его выходе будет 0, в состоянии State_B – 1 и т.д. Т.к. автомат имеет 4 состояния, нам понадобится 2 выхода (log₂(4)=2).

3. Алгоритм работы автомата задан таблицей переходов и состояний.

Выполнение работы:

Выполнение практической работы можно разделить на следующие этапы:

1) На основании кода переходов (Приложение 2, свой вариант), строится таблица переходов и состояний.

2) По таблице переходов и состояний строится граф переходов машины состояний.

3) По графу переходов определяется маршрут обхода графа, включающий все его ребра. В качестве начала маршрута (начальное состояние автомата) берется вершина А.

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

5) С использованием редактора временных диаграмм пакета MAX+PLUS (WaveForm Editor) создается сигнальный файл проекта (.wdf), который содержит временные диаграммы, описывающие логику работы машины состояний. Для этого:

· нажать кнопку открытия нового файла на панели инструментов, в открывшемся диалоговом окне «New» отметить пункт «Waveform Editor file», в соседнем окне выбрать расширение (.wdf) и нажать «ОК», после чего откроется окно редактора;

· задать временные диаграммы для входов Rst, Clk и входов IN[1..0], на которые подается последовательность управляющих воздействий, полученная в п.4, а также соответствующие временные диаграммы внутреннего состояния самой машины (использовать пункт «Insert Mode», в «I/O Type» указать «Buried Node», в «Node Type» указать «Machine» + «Secondary Inputs» «Clock: Clk, Reset: Rst») и временные диаграммы выходов (в нашем случае они совпадают с состояниями самой машины);

· создать символ машины состояний через подменю «Project», в котором следует выбрать пункт «Create Default Symbol». Созданный символ будет помещён в каталог проекта. Использование созданных символов, так же как и элементов других библиотек, производится через диалоговое окно «Enter Symbol».

6) С использованием графического редактора пакета MAX+PLUS (Graphic Editor) строится схема, состоящая из созданного символа машины состояний с присоединенными к нему элементами входов и выходов. ВНИМАНИЕ: Имя проекта ни в коем случае не должно совпадать с именем символа машины состояний!

7) Выполняется компилирование схемы (Compiler).

8) С помощью редактора WaveForm Editor задаются внешние воздействия, необходимые для проверки работоспособности схемы. В данном случае это может быть произвольная последовательность из 6 или более входных воздействий.

9) Запускается симулятор работы схемы (Simulator).

10) Измеряются временные задержки, возникающие при работе схемы. Измерение задержек можно проводить как вручную в WaveForm Editor, так и с помощью Timing Analyzer.

Требования к защите работы:

1) Демонстрация схемы дешифратора и результатов моделирования на компьютере.

2) Отчет по практической работе (оформленный в соответствии с Приложением 4).

3) Правильные ответы на вопросы преподавателя по теме работы.

Пример выполнения практической работы:

Задание:

Вариант №1. Необходимо синтезировать машину состояний по заданной таблице переходов.

Выполнение работы:

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

0x7D44 = 0111’1101’0100’0100

Первая тетрада кода соответствует строке таблицы переходов для состояния State_A, вторая тетрада соответствует строке таблицы переходов для состояния State_B и т.д.

 

Состояние	State_A	State_B	State_C	State_D
State_A
State_B
State_C
State_D

 

Для управления машиной необходим 2-разрядный вход IN[1..0].

Управляющее воздействие можно определить следующим образом: для перехода из текущего состояния в состояние State_A (если этот переход задан графом) необходимо подать на вход машины входное воздействие 0x0, для перехода из текущего состояния в состояние State_Bнеобходимо подать на вход машины входное воздействие 0x1 и т.д. Если же переход невозможен, то данное входное воздействие оставляет машину к прежнем состоянии. Для определения состояния машины необходим 2-разрядный выход OUT[1..0]. Информацию о состоянии машины можно определить по значению установленном на данном выходе:

State_A: OUT[1..0] = 0;

State_B: OUT[1..0] = 1;

State_C: OUT[1..0] = 2;

State_D: OUT[1..0] = 3.

По таблице переходов строим граф переходов заданной машины состояний.

 

 

Рис.2-1 Граф машины состояний

 

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

Т.к. работа нашей машины состояний начинается из состояния State_A, то для заданного графа маршрут будет следующим:

A->B->B->A->C->B->D->B->A->D

По данному маршруту, используя таблицу переходов и состояний, строим последовательность входных воздействий приводящих к прохождению всего маршрута. Причем последовательность должна включать в себя еще и воздействия не вызывающие изменение состояний. Это делается потому, что компилятор считает, что результат работы машины состояний для неуказанных входных воздействий нас не интересует и может при подаче неучтенных воздействий вывести на выход все что угодно. Чтобы этого не произошло необходимо для каждого состояния машины указать реакцию на все возможные входные воздействия. Таким образом, граф переходов заданной машины состояний приобретает следующий вид (цифрами указаны входные воздействия, приводящие к переходу в то или иное состояние):

 

Рис.2-2 Граф машины состояний

 

Итоговая последовательность входных воздействий, в таком случае, будет такова (в скобках указано состояние машины, к которому приводит воздействие):

0(A)->1(B)->1(B)->2(B)->0(A)->2(C)->2(C)->3(C)->0(C)->1(B)->3(D)->3(D)->2(D)->0(D)->

->1(B)->0(A)->3(D);

Строим диаграмму работы машины в редакторе Waveform Editor(Altera Max+II):

Рис.2-3. Диаграмма работы машины состояний (Waveform Editor)

 

Проверяем работу машины на произвольной последовательности входных воздействий (не менее 6): 1 – 3 – 2 – 0 – 2 – 1

В редакторе Waveform Editor строим диаграмму входных воздействий:

Рис.2-4. Отклик созданной машины на входное воздействие (Waveform Editor)

 

Отклик демонстрирует правильную реакцию созданной по диаграмме машины.

С помощью средств WaveForm Editor производим замер временных задержек на каждом переключении, относительно фронта сигнала CLK с указанием кода переключения (рис. 2-4).

T (State_A – State_B, clk) = 4.2 нс.

T (State_B – State_D, clk) = 4.6 нс.

Вопросы к работе:

1) Объяснить, как работает D-триггер.

2) Приведите пример машины состояний.

3) Почему переключение сигнала на выходах OUT не совпадает с переключением состояния машины?

4) Почему переключение состояния машины не совпадает с фронтом сигнала CLK?

5) Зачем необходимы входы CLK и RST ?

6) Какой из автоматов (Мили или Мура) синтезирован в работе?

7) Каким способом можно перейти из любого состояния в состояние State_A, не дожидаясь сигнала CLK?

 

Практические занятия №№ 3