Что такое цифровой автомат

ОСНОВНЫЕ ПОЛОЖЕНИЯ

Цифровой автомат (ЦА) – это условная, формальная модель любого информационного устройства дискретного действия. Модель предназначена для представления устройства на логическом уровне, т.е. в ней не допускается использование каких-либо физических характеристик процессов, происходящих при работе реального устройства.

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

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

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

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

В то же время можно дать и совершенно другое определение, вытекающее из назначения описываемого устройства.

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

Работа ЦА протекает во времени, но это особенное, автоматное время, представляющее смену последовательных дискретных моментов t = 0, 1, 2, 3. ЦА всегда начинает свою работу с момента t = 0, а время окончания может быть не определенным или бесконечным.

Теорию автоматов принято делить на две основные части: абстрактную и структурную.

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

Рис. 1.1. Схема абстрактного автомата

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

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

Выход У автомата определяется аналогично. Все выходные буквы принадлежат выходному алфавиту

Роль абстрактного автомата сводится к тому, что он последовательно, букву за буквой, преобразует входные слова в выходные. При этом, естественно, совпадает длина входных и выходных слов.

Каждая буква а означает одно определенное состояние ЦА. Все эти буквы в совокупности образуют внутренний алфавит или алфавит состояний.

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

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

Рис. 1.2. Структурная схема цифрового автомата

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

Аналогично определяются выходной вектор и вектор внутренних состояний, число компонент которого равно числу элементов памяти в схеме ЦА.

Ясно, что между буквами абстрактных алфавитов X, Y и А с одной стороны и буквами структурных алфавитов U, Z и Q – с другой должно существовать взаимно-однозначное отображение. И все же это – разные алфавиты. Переход от абстрактного алфавита к структурному называется кодированием автоматных алфавитов и представляет одну из важных задач структурной теории.

Анализ автоматовсчитается прямой задачей, как в абстрактной, так и в структурной теории. Анализ устанавливает основные свойства автоматов и сравнивает автоматы между собой, создает методы описания и пути преобразования автоматов.

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

Рассмотрим некоторые вопросы классификации автоматов. Все ЦА можно разделить на два основные класса: автоматы без памяти, или примитивные автоматы, и автоматы с памятью.

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

В структурном алфавите для автомата, имеющего несколько выходов, можно написать

,

что следует понимать как систему функций, число которых равно числу структурных выходов.

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

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

Цифровой автомат считается конечным, если конечны множества входных сигналов X, состояний S и выходных сигналов Y, то есть это автомат с ограниченной памятью состояний. Конечный автомат, в каждом состоянии которого существует функция перехода для всех возможных входных символов, называется полностью определенным конечным автоматом.

Работа ЦА осуществляется в автоматном времени, определяемом числом периодов поступления входных сигналов.

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

Рис. 1.3. Общее изображение Рис. 1.4. Структурное изображение

Источник

Описание цифровых автоматов на VHDL

Немного теории

Цифровой автомат (ЦА) — это устройство, которое осуществляет прием, хранение и преобразование дискретной информации по некоторому алгоритму и может находиться в одном из нескольких устойчивых состояний [7].

Рисунок 1 — Граф цифрового автомата

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

Цифровой автомат может быть описан с помощью таких представлений:

— в виде ориентированного графа,
— с помощью переходов и выходов.

Представление цифрового автомата в виде ориентированного графа показано на рис. 1. Здесь в кругах — вершинах графа — показаны состояния цифрового автомата, переходы между состояниями показаны дугами между вершинами, а переход в то же самое состояние — петлей.

Возле дуг и петель показаны значения входных сигналов, при которых происходит этот переход. Например, (a OR b) обозначает, что этот переход произойдет при a = 1 или b = 1.

Выходные сигналы для автомата Мура показаны около вершин графа, а для цифрового автомата Мили — на дугах возле входных сигналов. Т.о. на рис. 1 показан цифровой автомат Мура.

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

Таблица 1 — Таблица переходов цифрового автомата

Таблица выходов — показывает соответствие текущего состояния цифрового автомата и его выходных сигналов (табл. 2).

Таблица 2 — Таблица выходов цифрового автомата>

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

— комбинационный блок логики переходов;
— регистр для хранения состояний ЦА;
— комбинационный блок формирования выходных сигналов — разные для ЦА Мили и Мура.

Рисунок 2 — Схематическое изображение цифрового автомата с асинхронными выходами

Схема логики переходов на свой вход получает код текущего состояния цифрового автомата (present_st) и внешние сигналы (input_signal). Выходом этого блока будет код следующего состояния (next_st).

В регистр состояний входит три сигнала: тактовый (clk), сброса (reset) и код следующего состояния (next_st). Тактовый сигнал и сигнал сброса предназначены для управления триггерами, которые хранят состояние цифрового автомата. По переднему фронту тактового сигнала производится запись следующего состояния (next_st) в триггеры. Результаты записи в триггеры появляется на выходе регистра состояния в виде сигнала текущего состояния ЦА (present_st).

Блок формирования выходных сигналов в зависимости от состояния ЦА (и входных сигналов для автомата Мили) формирует асинхронные выходные сигналы. Для получения синхронных выходных сигналов в этот блок дополнительно встраивают регистр.

Использование VHDL для описания цифровых автоматов

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

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

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

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

Для описания логики выходных сигналов возможно использование оператора процесса или оператора параллельного условного присваивания.

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

Здесь в списке инициализации процесса используется только текущее состояние цифрового автомата present_st, значения которого анализируются с помощью оператора case.

Для автомата Мили этот же процесс будет выглядеть таким образом:

Этот процесс для инициализации использует текущее состояние ЦА (present_st) и входной сигнал (input_signal) так как изменения любого из этих сигналов должно запускать выполнение процесса.

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

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

При описании последовательностной части цифрового автомата в списке инициализаторов процесса должны содержатся сигналы clk и reset. При поступлении сигнала сброса reset цифровой автомат переходит в начальное состояние init, из которого начинается работа всего автомата. Передний фронт сигнала clk приводит к записи в триггеры ЦА его нового текущего состояния, т.е. сигнал next_st переписывается в сигнал present_st.

Фактически последовательностная часть представляет собой регистр со сбросом:

Сигнал сброса может быть синхронным или асинхронным. Выше в листинге описан вариант асинхронного сброса.

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

Использование синхронного сигнала сброса не позволяет определить в каком состоянии окажется автомат при включении питания. Возможно, что он > в одном из неописанных состояний. Т.о. при описании цифрового автомата необходимо описать все2^n комбинаций состояний триггеров вне зависимости от того являются они рабочими состояниями цифрового автомата или нет. Здесь n — количество триггеров, применяемых для кодирования цифрового автомата. Это, в свою очередь приведет, к увеличению схемы логики переходов.

Для того, чтобы избежать > ЦА в неописанных состояниях необходимо явно прописывать действия в таких ситуациях с помощью конструкции when… others. Например, возможно использование такого процесса для описания синхронного сброса и действий в неиспользуемых состояниях.

Три, два, один

Цифровой автомат можно описать с помощью одного, двух или трех операторов процесса. Эти варианты рассмотрим на примере цифрового автомата управления светофором.

Этот цифровой автомат имеет пять состояний: начальное (Init), красный ( R ), зеленый (G) и два желтых — один для перехода из красного к зеленому (RG), а второй — из зеленого к красному (GR). В том случае, когда вход cnt равняется нулю, никаких переходов не происходит, когда вход cnt равняется единице — происходит переход в следующее состояние. Граф цифрового автомата изображен на рис. 3.

Рисунок 3 — Граф цифрового автомата светофора

Этот же автомат может быть представлен с помощью таблицы переходов и таблицы выходов. Выходной сигнал представлен трехбитным вектором, в котором старший бит отвечает за красный, второй – за желтый и младший – за зеленый.

Таблица 3 — Таблица переходов

Таблица 4 — Таблица выходов

Для описания состояний ЦА необходимо описать перечислимый тип, в котором будут перечислены все состояния. В приведенном примере вводится тип state_type, который содержит пять значений: Init, R, RG, G, GR. Для работы конкретного экземпляра цифрового автомата нужно описать сигналы этого типа. В примере это сигналы next_st, present_st для хранения последующего и текущего состояний автомата соответственно. При выполнении процессов этот сигнал будет принимать значение текущего состояния цифрового автомата.

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

— комбинационная часть для логики переходов;

— комбинационная часть для выходных сигналов;

— последовательностная часть только для записи состояний цифрового автомата.

Рисунок 4 — Цифровой автомат с тремя процессами

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

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

Результирующий граф ЦА, полученный при компиляции в пакете Quartus II показан на рисунке 5 (меню Tools — Netlist Viewers — State Machine Viewer).

Рисунок 5 — Цифровой автомат с тремя процессами. Результат компиляции

Результат синтеза программы, приведенной в листинге выше, показан на рис. 6 (меню Tools — Netlist Viewers — Technology Map Viewer). Для облегчения понимания на рисунке элементы ввода-вывода обозначены как IO, триггеры как FF, а логические элементы — LE. Как видно в результате синтеза получится схема из 5 триггеров для хранения состояний цифрового автомата (в случае метода кодирования One Hot) и двух логических элементов для реализации схемы переходов и формирования выходных сигналов.

Рисунок 6 — Цифровой автомат с тремя процессами. Technology Map Viewer

Описание с помощью двух процессов (рис. 6) предполагает, что блок логики переходов и регистр состояний объединяются в один процесс, в котором с помощью оператора case производится выбор будущего значения состояния цифрового автомата. Поскольку нет необходимости разделять сигналы текущего и будущего состояний, то эти два сигнала заменены на один, state, в котором и хранится состояние цифрового автомата.

В листинге ниже показан пример описания ЦА с асинхронным сбросом. В результате компиляции будет получен такой же результат как и в предыдущем случае — рис.7.

Рисунок 7 — Цифровой автомат с двумя процессами

Рисунок 8 — Результат синтеза цифрового автомата с синхронным сбросом

Описание цифрового автомата с помощью одного процесса предполагает, что вся логика находится в одном процессе. Некоторые авторы [5] считают, что использование одного процесса для описания цифрового автомата является более простым и позволяет более просто описывать и отлаживать цифровой автомат. Данное утверждение справедливо для небольших цифровых автоматов. При увеличении количества состояний и использовании одного процесса ухудшается читабельность кода. Потому как еще древние римляне при описании цифровых автоматов пользовались правилом «Разделяй и властвуй».

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

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

Результат компиляции программы показан на рисунке \ref. Очевидно, что результат оказался таким же как и при описании с помощью двух процессов с единственным отличием – добавились триггеры для выходного регистра.

Рисунок 9 — Цифровой автомат с одним процессом

Подведем небольшие итоги наших изысканий.

Первое, и самое важное. Цифровой автомат существует! Мы его видели на картинке 5.
Второе. Описания с помощью двух и трех процессов дают одинаковый результат и выбор метода описания зависит от предпочтений разработчика.
Третье. Нужно очень внимательно относиться к начальному сбросу автомата и описанию неиспользуемых состояний.
Четвертое. Описание с помощью одного процесса приводит к появлению регистров для выходных сигналов цифрового автомата.

1. Altera. Quartus II Handbook Version 10.0 Volume 1: Design and Synthesis Vol. 1, 2010 — 1820 p.
2. B. Cohen. VHDL Coding style and Metodologies. Kluwer Academic Publishers.2002 — 454 p.
3. D. L. Perry. VHDL programming by example. New York: McGraw-Hill, 2002.- 476 p.
4. D. J. Smith. HDL chip design: a practical guide for designing, synthesizing, and simulating ASICs and FPGAs using VHDL or Verilog. Madison, AL: Doone Publications, 1996. — 448 p.
5. A. Taylor. How to Implement State Machines in Your FPGA. Xcell, 81(4), p. 52–57.
6. Xilinx. VHDL Reference Guide. XST User Guide.
7. К. Г. Самофалов. Прикладная теория цифровых автоматов. М. 1987. 375 с.

Источник