Цель работы:

- Закрепление навыков структурного синтеза конечных автоматов (КА);

- понимание характеристик и режимов работы триггеров основных типов;

- получение практических навыков тестирования и управления конечными автоматами;

- получение навыков ввода проекта в графическом редакторе пакета Quartus II, тестирования и отладки проекта и анализа временных характеристик КА;

- ознакомление с редактором конечных автоматов пакета Quartus II и анализом результатов синтеза;

- получение навыков отладки цифровых устройств данного класса на физической модели: конфигурирование СБИС ПЛ и экспериментальная проверка работы типовых устройств с триггерами при использовании лабораторной платы DiLab.

4.1. Абстрактный конечный автомат

Абстрактный конечный автомат КА соответствует "пятерке" <A, B, R, d, l>, где A, B, R - множества состояний входа, выхода и внутренних, а d и l - функции переходов и выхода.

Для представления состояний автомата требуется память П, а реализация функций d и l осуществляется комбинационными схемами КС1 и КС2. Соответствующая структура КА представлена на рис.1. В ней обозначено: X - входные сигналы КА, A - множество значений вектора X; Y- выходные сигналы, B - множество значений вектора Y; R - множество внутренних состояний автомата (множество значений вектора Q); Ф - сигналы возбуждения элементов памяти.

Рис.1. Структура абстрактного КА.

Если показанная на рис.1 пунктирная связь входа X с комбинационной схемой КС2 присутствует, то такой КА называют автоматом Мили. Его особенностью является зависимость выходных сигналов Y непосредственно от X. Если пунктирная связь отсутствует, то имеем автомат Мура. Любой алгоритм может быть представлен как автоматом Мили, так и автоматом Мура.

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

При описании работы КА непрерывное время делят на такты. В течение одного такта t, длительность которого соответствует периоду следования синхронизирующих импульсов C, подаваемых на вход блока П, КА находится в одном состоянии. Моменты переходов КА из одного состояния в другое нумеруют числами 0, 1, 2, 3, ... натурального ряда. При этом говорят, что КА работает в дискретном времени. Для отсчета времени используется безразмерная переменная t, соответствующая номеру такта.

С учетом сделанного замечания алгебраическое представление работы КА можно привести к системе двух уравнений:

для автомата Мили

r ^t+1 = d(a^t, r^t); b^t = l(a^t, r^t);

для автомата Мура

r ^t+1 = d(a^t, r^t); b^t = l(r^t),

где a^t, b^t, r^t - состояния входа, выхода и внутреннее в такте t; r^t+1 - внутреннее состояние в следующем такте (состояние перехода КА); d, l - функции перехода и выхода.

Рассмотрим способы задания абстрактного КА.

Задать КА - это означает определить множества A, B, R и функции d, l. Функции d и l задают отображения: A*R® R и A*R® B соответственно. Таким образом, полным заданием КА являются таблицы переходов и выходов. Поле такой таблицы соответствует декартову произведению множеств A * R.

Рассмотрим пример задания автомата Мили.

d: A * R ® R l: A * R ® B

r^t+1 = d(a^t,r^t) b^t = l(a^t,r^t)

В рассматриваемом примере A={a₁, a₂}, B={b₁, b₂, b₃},

R = {r₁, r₂, r₃}.

Один вход в таблицу - имена столбцов - перечисление внутренних состояний r^t, другой вход - имена строк - перечисление состояний входа. Для упрощения записей в таблицах часто записываются только индексы соответствующих переменных.

У автомата Мура таблица выходов содержит всего одну строку, в которой приводятся значения b^t, соответствующие r^t. У не полностью определенного КА в клетках с неопределенным (безразличным) состоянием r^t либо b^t ставится "Н" либо "-".

Другим распространенным способом задания КА служит граф переходов. Это ориентированный граф, вершины которого соответствуют внутренним состояниям, а дуги - направлениям переходов. Дуги помечены условием перехода и состоянием выхода (у автомата Мили). У автомата Мура состояния выхода записывают у соответствующих вершин графа.

На рис.2. приведен граф переходов автомата Мили, заданный приведенными выше таблицами переходов и выхода.

Рис.2. Граф переходов автомата Мили.

4.2. Триггеры – элементы блока памяти конечного автомата

Для запоминания внутренних состояний КА используются триггеры. Моделью триггера является элементарный КА, имеющий два внутренних состояния и один или несколько входов. Этот элементарный автомат (ЭА) должен удовлетворять условию полноты системы переходов, то есть должны существовать входные сигналы, обеспечивающие возможные переходы четырех типов: 0®0, 0®1, 1®0, 1®1. ЭА также должен удовлетворять требованию полноты системы выходов, то есть мощность множества внутренних состояний должна совпадать с мощностью множества состояний выходов и должно быть взаимно-однозначное соответствие между элементами этих множеств.

Условиям функциональной полноты удовлетворяют одновходовые триггеры D и T-типа и двухвходовые RS и JK-типа. Условные обозначения таких синхронных триггеров приведены на рис.3.

Ниже для этих триггеров приведены таблицы функций возбуждения, то есть сигналов, которые должны быть поданы на их входы для перевода из исходного состояния Q(t) в состояние Q(t+1). Функции возбуждения однозначно определяются из таблиц переходов, полученных при исследовании триггеров в работе 3.

Рис.3. Условные обозначения синхронных триггеров.

Таблица управления триггерами (активные уровни – высокие).

Эта таблица используется при синтезе блока управления памятью КС1 (0).

Триггер D называют триггером-задержкой, так как следующее состояние Q(t+1) полностью определяется значением D(t), и функция возбуждения для D-триггера совпадает с состоянием Q(t+1).

Функция возбуждения для T-триггера (счетного триггера) определяется как T=1, если триггер должен изменить свое состояние на противоположное (0®1 или 1®0) и T=0, если триггер должен сохранить прежнее состояние (0®0 или 1®1).

RS-триггер имеет два входа (R - установка в 0, S - установка в 1), то есть, возможны четыре различные комбинации сигналов. Одна из комбинаций (R,S)=(1,1) запрещена, так как теоретически приводит к неопределенному состоянию. Однако, в практических реализациях триггеров состояние перехода, как правило, определено и известно в спецификации. Если триггер должен сохранить прежнее состояние, то необходимо обеспечить S=0 (хранение 0) или R=0 (хранение 1) при безразличном состоянии другого входа, что отмечено в таблице функций возбуждения символом "Н".

Универсальный JK-триггер совмещает функции RS и T-триггеров. При (J,K)=(0,0), (0,1), (1,0) он ведет себя аналогично RS-триггеру, если K=R, J=S. При (J,K)=(1,1) состояние триггера изменяется на противоположное, то есть он ведет себя как T-триггер. Соответственно изменяется и таблица функций возбуждения JK-триггера.

4.3. Метод структурного синтеза синхронных автоматов

При структурном синтезе решаются следующие задачи:

· определение необходимого объема памяти КА;

· выбор типа триггеров и кодирование внутренних состояний;

· определение системы функций переходов и выходов;

· минимизация системы функций;

· синтез комбинационных схем КС1 и КС2 и построение принципиальной схемы КА.

Минимальное количество триггеров m в памяти автомата определяется из числа его состояний R: m=E(log₂R), где E - функция округления до ближайшего целого большего числа.

Если при этом 2m > R, то КА следует доопределить, включив в него "лишние" 2m - R состояний. Их следует связать безусловным переходом с состоянием автомата, принятом за исходное. При нормальном функционировании КА "лишние" состояния не используются. Но либо в результате сбоя, либо при включении питания автомат случайно может оказаться в одном из этих состояний. Если не предусмотреть выход из них, то произойдет "зависание" автомата. В условиях лабораторной работы для выхода из этой ситуации целесообразно организовать начальную установку КА, используя асинхронные входы триггера.

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

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

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

П1. Те состояния r^t, из которых есть переход в одно и то же состояние r^t+1 при одном состоянии входа, следует кодировать соседними кодами.

П2. Те состояния r^t+1, переход в которые осуществляется из одного и того же состояния r^t, следует кодировать соседними кодами.

Если всем условиям удовлетворить нельзя, предпочтение следует отдать правилу П1. В примере синтеза проиллюстрировано применение этого алгоритма.

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

4.4. Пример структурного синтеза синхронного автомата

Пусть задан автомат Мура следующими таблицами переходов и выхода.

r^t+1 = d(a^t, r^t) y^t = l(r^t)

Соответствующий граф переходов приведен на рис.4.

Рис.4. Граф переходов синтезируемого автомата.

Входной алфавит состоит из четырех абстрактных состояний входа, которые уже закодированы двумя входными сигналами x₂ и x₁. Выходной алфавит из четырех состояний выхода также закодирован двумя выходными сигналами y₂ и y₁.

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

По правилу П1: (0, 3).

По правилу П2: (0, 2), (2, 3), (1, 0), (1, 3), (1,2).

Выберем вариант размещения номеров состояний, удовлетворяющий правилу П1 и, по возможности, правилу П2.

Следует отметить, что кодирование по приведенному алгоритму неоднозначно. Заслуживает внимания вариант кодирования внутренних состояний по таблице выходов, который не удовлетворяет правилу П1, однако исключает необходимость схемы КС2, так как в этом случае y₁ = Q₁, y₂ = Q₂.

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

(Q₂,Q₁)^t+1 = d((Q₂,Q₁)^t, (x₂,x₁)^t).

Для реализации памяти используем JK-триггеры, синхронизируемые перепадом потенциала. Далее задача синтеза КА сводится к синтезу двух комбинационных схем, реализующих логические функции возбуждения триггеров J₂, K₂, J₁, K₁, и логические функции выходов Y₂, Y₁.

Составим таблицу функций возбуждения памяти. Переходы триггеров памяти происходят под действием сигналов функций возбуждения, поступающих на их входы. Для определения того, что нужно подать на вход ЭА, чтобы перевести его из 0 в 1, обратимся к таблице функций возбуждения JK-триггера. Как видно из нее, на J-вход надо подать сигнал 1, на K-вход - безразлично какой. Аналогично определяются входные сигналы для других переходов и заносятся в соответствующие строки таблицы функций возбуждения. Например, если автомат находился в состоянии (1, 0), то при входном сигнале x₂=1, x₁=0 согласно таблице переходов он перейдет в состояние (0, 1), то есть оба триггера поменяют свои состояния на противоположные. Чтобы этот переход осуществился, согласно таблице управления JK-триггера, на его входы необходимо подать следующие сигналы управления я: J₂=Н, K₂=1, J₁=1, K₁=Н.

На основании закодированной таблицы переходов КА и функций управления JK-триггеров получим:

После составления таблицы функций управления проводится совместная минимизация этих функций (см. рис.5).

Рис. 5. Карты Карно для входов JK-триггеров.

Примечание. Функции J и K имеют общую часть и реализуются совместно.

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

Полученная принципиальная схема в графическом редакторе САПР Quartus II, реализующая синтезированный в примере конечный автомат, приведена на рис.6. Для реализации логики используются только элементы Шеффера.

Рис. 6. Принципиальная схема конечного автомата.

4.5. Проверка и наладка реализуемого КА

Проверку реализуемого КА осуществляют, заполняя в процессе экспериментального исследования схемы на имитационной (моделирование в Quartus II) и физической (лабораторный стенд DiLab) моделях экспериментальную таблицу переходов и выходов и сравнивая эту таблицу с теоретической. Для этого предварительно составляется тест, то есть последовательность входных сигналов, позволяющая последовательно, переходя из одного состояния в другое, осуществить полную проверку таблицы переходов. Переходы, которые не определены в исходной таблице, также исследуются, и в таблице отмечается, как они доопределены. При проверке очередного перехода сначала устанавливается входной сигнал (он может быть и тем же, что и в предыдущем такте), затем подается синхроимпульс и фиксируются состояния триггеров и выходов. Если экспериментальная и теоретическая таблицы переходов и выходов совпали, значит КА реализует заданный алгоритм работы; если хотя бы для одного перехода нет совпадения, необходимо осуществить наладку собранной схемы. Для наладки КА необходимо наблюдать при моделировании сигналы управления триггерами. Сформированные комбинационными схемами, они не входят в число представленных в Node Finder сигналов. Для наблюдения этих сигналов подключите их к выходам схемы, выполните анализ и синтез, чтобы выходы вошли в список сигналов и, локализовав выходы в редакторе назначений (Assignment Editor), задайте их как виртуальные выводы (см. рис.7).

Рис.7.

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

Выводим на индикацию сигналы управления триггеров.

Устанавливаем триггеры в состояние r_i, из которого осуществляется неправильный переход (если этих состояний несколько, то в любое из них).

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

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

o сигналы управления, полученные в эксперименте, совпали с сигналами, рассчитанными при синтезе. Проверяем теоретически для заданного типа триггеров, какие переходы инициализируют данные сигналы управления. Если теоретически данные сигналы возбуждения должны перевести триггеры в заданное состояние, то причина ошибки в неправильном включении триггера;

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

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

Если ошибка найдена, необходимо внести исправления и снова снять экспериментальную таблицу переходов. Процедура наладки повторяется до тех пор, пока не будет достигнуто полное соответствие теоретической и экспериментальной таблиц переходов.

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

4.6. Синтез КА средствами САПР Quartus II

Пакет Quartus II предоставляет пользователям средства для задания КА и его синтеза на одном из языков описания аппаратных средств. Устройства, введенные и синтезированные как конечные автоматы, при моделировании также рассматриваются в терминах введенного автомата, что упрощает контроль состояний отлаживаемой системы.

Для ввода конечных автоматов в Quartus II может использоваться редактор конечных автоматов, открываемый как новый файл с расширением .smf (см. рис.8).

Рис.8.

Щелкните ОК и откроется окно редактора ввода конечных автоматов, как показано на рис.9.

Рис.9.

На вертикальной панели инструментов открывшегося окна выберите State Machine Wizard. Следуя инструкциям, задайте состояния автомата, его входные и выходные сигналы. Задайте таблицы переходов и выходов, используя следующие обозначения логических операций: ~- инверсия; & - логическое «И»; | - логическое «ИЛИ». После окончания ввода на поле отображения редактора конечных автоматов появится граф переходов введенного автомата. Вид окна для рассматриваемого в работе примера приведен на рис.10.

Рис.10.

На вертикальной панели инструментов щелкните кнопку Generate HDL File. В появившемся окне выберите VHDL и нажмите ОК. Генерируется логический файл, описывающий конечный автомат. Имя создаваемого файла должно отличаться от уже существующих в папке проекта имен. Этот файл может компилироваться, для него может выполняться моделирование.

Для определения способа кодирования состояний КА, используемого компилятором, откройте Tools => Netlist Viewers => State Mashin Viewer. Способ кодирования состояний КА, используемый компилятором, можно задать в окне установок синтеза Assignments => Settings => Analysis & Synthesis Settings => More Settings => State Machine Processing.

При выборе с помощью Node Finder переменных для моделирования, кроме входных и выходных сигналов, выберите КА, установив Filter в положение Design Entry (All Names). На временной диаграмме КА будет отображаться его состояниями. Кроме того, выведите на временную диаграмму состояния триггеров памяти конечного автомата.

Программа работы

1. Выполните структурный синтез конечного автомата:

· Составьте по индивидуальному заданию таблицу переходов и выходов.

· Определите необходимое число триггеров.

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

· Осуществите совместную минимизацию логических функций возбуждения триггеров с помощью карт Карно, выберите один из минимальных вариантов и запишите полученные логические функции в базисе Шеффера с ограничениями (элементы 2И-НЕ; 3И-НЕ; 4И-НЕ).

· Осуществите минимизацию логических функций выхода КА и также запишите их в базисе Шеффера.

· Составьте принципиальную схему конечного автомата.

2. Выполните исследование синтезированного автомата при реализации на СБИС ПЛ EP2C8F256C-8.

· В пакете Quartus IIвведите схему КА.

· Определите системное окружение из состава стенда DiLab, необходимое для исследования КА на физической модели. Выполните назначение выводов СБИС ПЛ.

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

· Составьте полный тест. Используя симулятор Quartus II, проверьте таблицу переходов и выходов для всех переходов, указанных в задании, и переходов, дополненных при синтезе. При выявлении ошибок в работе КА, осуществите его настройку. По результатам эксперимента заполните экспериментальные таблицы переходов и выходов.

· Выполните программирование СБИС ПЛ и проверьте работоспособность на макете. По результатам эксперимента заполните экспериментальные таблицы переходов и выходов.

3. Выполните исследование заданного конечного автомата при его синтезе средствами пакета Quartus II.

· Создайте новый проект. Введите КА средствами State Machine Editor. Выполните генерацию VHDL файла для автомата и ознакомьтесь с полученным файлом. Выполните синтез на целевой СБИС ПЛ. Выполните анализ аппаратурных затрат и быстродействия.

· Откройте State Machine Viewer и ознакомьтесь с реализацией синтезированного автомата в State Machine Viewer. Определите используемый способ кодирования состояний автомата.

· Проведите моделирование работы КА по тесту, составленному для п.2. При выборе с помощью Node Finder переменных для моделирования, кроме входных и выходных сигналов, выберите КА, установив Filter в положение Design Entry (All Names). На временной диаграмме КА будет отображаться его состояниями. Кроме того, выведите на временную диаграмму состояния триггеров памяти конечного автомата.

· Сравните результаты моделирования с результатами, полученными в п.2, используя возможности редактора временных диаграмм.

4. По заданию преподавателя измените способ кодирования состояний автомата. Выполните компиляцию. Определите аппаратурные затраты и быстродействие. Сравните результаты моделирования с временными диаграммами п.2 и п.3.

5. Оформите отчет по проделанной работе.

Контрольные вопросы

1. Укажите особенности использования различных типов синхронных триггеров в конечных автоматах.

2. Как изменится функционирование КА, если вместо триггеров, синхронизируемых перепадом, использовать триггеры, синхронизируемые уровнем?

3. Чем отличается задание автомата Мили от предложенного Вам автомата Мура?

4. Чем ограничено быстродействие Вашей схемы? Укажите максимальную частоту синхроимпульсов.

Варианты заданий по синтезу синхронных КА

Дата добавления: 2015-07-26; просмотров: 670; Нарушение авторских прав

Мы поможем в написании ваших работ!