Технические аспекты построения управляющих автоматов при проектировании цифровых устройств на основе современных ПЛИС

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

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

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

К системным входам УКА относятся входы для подачи синхросигнала CLK и сигнала асинхронной (по отношению к синхросигналу CLK) начальной установки RST.

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

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

Обобщенное представление конечного автомата показано на рис. 1. В данном примере, помимо системных входов CLK и RST, автомат имеет n шт. управляющих входов A(n–1 : 0), m шт. выходов V(m–1 : 0) и k шт. линий внутренних состояний Q(k–1 : 0). Таким образом, на входы автомата в каждом такте работы может быть подана одна из 2ⁿ шт. входных комбинаций a_i, на выходы автомата в каждом такте может быть выставлена одна из 2^m шт. выходных комбинаций v₀, а максимальное количество внутренних состояний рассматриваемого автомата ограничено 2^k шт. комбинаций q_s.

Работу синхронного автомата поясняет временная диаграмма, изображенная на рис. 2.

Рис. 1. Обобщенное представление конечного автомата

Рис. 2. Временная диаграмма работы синхронного конечного автомата

В начале работы, а также после подачи аппаратного сброса системы генерируется асинхронный сигнал начальной установки RST, задающий интервал «сброса по включению питания» (Power-On-Reset, POR). В течение интервала POR состояние всех входов, кроме RST, игнорируется, а все регистры и триггеры устанавливаются в исходное состояние, задаваемое по усмотрению разработчика для корректного старта системы.

Многие производители ПЛИС, а также систем проектирования СБИС рекомендуют использовать синхронные сигналы начальной установки (сброса) (Synchronous Reset, SR). В ряде САПР имеется возможность автоматической замены асинхронных сигналов сброса на синхронные. Например, в системе Xilinx ISE 10.1 в настройках параметров синтеза проекта в разделе HDL Options для этой цели предусмотрена опция Asynchronous to Synchronous. Применение асинхронных сигналов начальной установки сложилось исторически, начиная с логических микросхем серий 74xxx. Так, в триггере 74xx74 (отечественный аналог — ТМ2) предусмотрены асинхронные сигналы установки в состояния «лог. 0» и «лог. 1». Асинхронная начальная установка поддерживается регистрами большинства семейств ПЛИС, как устаревших, так и современных. В то время как применение синхронных сбросов при проектировании в базисе элементов, где эта возможность аппаратно не поддерживается, потребует использования дополнительных комбинационных цепей обратной связи, что усложнит проект. Таким образом, модели устройств с асинхронной начальной установкой на данный момент более универсальны и могут быть преобразованы в полностью синхронные средствами САПР (при этом изменяется функциональность проекта относительно исходной модели, что может привести к сбоям или неработоспособности устройства).

Применение синхронных или асинхронных сигналов начальной установки не отражается на штатном функционировании УКА, вследствие чего ограничимся рассмотрением асинхронного сигнала.

По завершении интервала POR автомат начинает функционировать согласно заданному алгоритму, воспринимая входные управляющие сигналы A(i) по рабочим фронтам синхросигнала в моменты времени t₁, t₂, t₃, t₄ и т. д.

В зависимости от логической организации конечного автомата выходные сигналы могут отличаться формой, стабильностью переходного процесса и задержками относительно синхросигнала. На рассмотренной диаграмме приведены выходные сигналы, соответствующие наиболее общей организации автомата — модели Мили (Mealy) [2, 4, 5]. Выходные сигналы, вырабатываемые автоматом Мили, должны иметь устойчивое состояние только в окне стабильности для надежной фиксации внешними регистрами, работающими по единому с автоматом синхросигналу. За пределами окон стабильности выходные сигналы автомата Мили могут изменять состояние произвольно.

Состояния автомата, соответствующие комбинациям q_S, изменяются после рабочего фронта синхросигнала с задержкой T_CO (Clock-to-Output), вносимой триггерами и регистрами в силу особенностей их конструкции. Задержка T_CO также обеспечивает изменение сигналов, формируемых регистрами и триггерами, вне окон стабильности в объеме кристалла СБИС (данное свойство не распространяется на внешние по отношению к кристаллам синхронные интерфейсы PCI и SDRAM). Немаловажным фактом является стабильность переходного процесса сигналов, формируемых на триггерах и регистрах, обусловленная однократным изменением состояния этих сигналов, что отражено на диаграмме (рис. 2) применительно к состояниям автомата.

Математическая модель автомата [1] определяется тремя множествами и двумя функциями, осуществляющими отображения этих множеств.

Множество входных комбинаций a_i задано конечным входным алфавитом A:

Множество выходных комбинаций v₀ задано конечным выходным алфавитом V:

Множество состояний q_s задано конечным алфавитом состояний Q:

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

Функция выходов F осуществляет отображение элементов входного алфавита и алфавита состояний в выходной алфавит:

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

Функционирование автомата согласно требуемому алгоритму описывается тремя способами задания автомата:

• автоматной таблицей;
• каноническими уравнениями;
• графом переходов.

Рассмотрим способы задания автомата на примере модели Мили. Эта модель описывает наиболее общий вариант автомата, в котором текущая выходная комбинация зависит от текущей входной комбинации и текущего состояния. Структурная схема автомата Мили представлена на рис. 3.

Рис. 3. Структурная схема автомата Мили

Для фиксации текущего состояния автомата Q используется регистр состояния, имеющий системные сигналы, общие с внешними регистрами. Выходные сигналы V вырабатываются комбинационной логической схемой CL_F, реализующей функцию выходов F. Следующее состояние автомата Q_NXT формируется комбинационной логической схемой CL_G, реализующей функцию переходов G.

В теории автоматов выделяют автоматы первого и второго рода [9]. На рис. 3 представлен автомат первого рода. Автоматы второго рода отличаются функцией выходов, формирующей выходные значения на основе обновленного состояния, в котором автомат окажется на следующем такте.

Автоматная таблица для каждой пары из входной комбинации и состояния автомата задает текущую выходную комбинацию и следующее состояние. Столбцам таблицы соответствуют текущие состояния, а строкам — текущие входные комбинации. Формат автоматной таблицы показан на рис. 4б. В ячейках таблицы данные указываются в виде дроби: следующие состояния — в числителе и текущие выходные комбинации — в знаменателе.

Рис. 4. Способы задания автомата Мили: а) графом переходов; б) автоматной таблицей

Канонические уравнения автомата Мили представлены системой из двух уравнений, задающих функции выходов и переходов:

где q(t–1) — предыдущее состояние, q(t) — текущее состояние, q(t+1) — следующее состояние; a(t–1) — входная комбинация на предыдущем такте, a(t) — текущая входная комбинация; v(t) — текущая выходная комбинация.

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

Любой конечный автомат может быть задан в графическом виде с помощью графа переходов [2, 3]. Граф переходов, или диаграмма состояний (State Diagram), — это ориентированный граф, вершинам которого соответствуют состояния, а переходам — направленные дуги, соответствующие входным комбинациям.

Пример графа переходов для автомата Мили приведен на рис. 4а. Если сложно расположить все вершины графа и все соединяющие дуги на одном рисунке, можно представить его в виде отдельных графов, описывающих переходы из одной или нескольких вершин. Вершина RESET соответствует начальной установке автомата в исходное состояние в течение интервала POR. Дугам, для которых не указаны входные комбинации, соответствуют безусловные переходы, которые предопределены алгоритмом работы независимо от входных сигналов. Дугам графа с пометкой «иначе» (else) соответствуют переходы, выполняемые во всех случаях, кроме заданных явно путем указания входной комбинации. В графе переходов автомата Мили для каждой дуги указываются выходные комбинации, соответствующие текущему состоянию и входной комбинации. Подобно автоматной таблице, в графе переходов выходные комбинации указываются в знаменателе дроби.

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

Рис. 5. Распространение сигналов через автомат Мили

Второй по значимости недостаток автомата Мили обусловлен вероятностью нестабильного переходного процесса выходных сигналов. Эту особенность поясняет рис. 6. Нестабильный переходный процесс заключается в многократных изменениях выходных сигналов за пределами окон стабильности регистров и триггеров.

Рис. 6. Временная диаграмма переключения автомата Мили

На рис. 6 нестабильный переходный процесс продемонстрирован применительно к одному из выходов автомата — V(i). Такой выходной сигнал будет корректно воспринят регистрами и триггерами, работающими по единому с автоматом синхросигналу. Однако выходной сигнал автомата Мили невозможно использовать для непосредственного тактирования триггеров или управления триггерами-защелками, ибо многократные изменения выходных комбинаций вне окон стабильности могут вызвать ложные срабатывания управляемых таким способом узлов.

Следует отметить, что необходимость непосредственного управления входами синхронизации на практике возникает редко и в большинстве случаев связана с реализацией интерфейсов между кристаллом ПЛИС/СБИС и внешними микросхемами, например при взаимодействии с последовательной памятью типа EEPROM по интерфейсам SPI (серия 25xx) и Microwire (серия 93Cxx). В объеме кристалла подобное управление синхросигналом использовать не рекомендуется, и для его замещения предназначен механизм разрешения синхронизации CE (Clock Enable), основанный на введении мультиплексора на информационном входе D-триггера. Мультиплексор, управляемый сигналом CE, коммутирует на вход D-триггера данные для записи при CE = «1» либо коммутирует текущее состояние с выхода триггера, обеспечивая режим хранения при CE = «0». В большинстве современных ПЛИС механизм разрешения синхронизации реализован аппаратно во всех регистрах.

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

Второй вариант логической организации автомата представлен канонической моделью Мура (Moore) [2]. Модель Мура, или автомат типа состояние-выход, является частным случаем автомата Мили, в котором текущая выходная комбинация зависит исключительно от текущего состояния (рассмотрен автомат Мура первого рода). Структурная схема автомата Мура представлена на рис. 7.

Рис. 7. Структурная схема автомата Мура

Канонические уравнения для автомата Мура представляются в общем случае следующей системой:

В графе переходов автомата Мура (рис. 8а) выходные комбинации указываются не для дуг, а для вершин, ибо не зависят от текущих входных комбинаций.

Рис. 8. Способы задания автомата Мура: а) графом переходов; б) автоматной таблицей

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

Отметим следующие недостатки автомата Мура:

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

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

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

Рис. 9. Распространение сигналов в автомате Мура

Рис. 10. Временная диаграмма переключения автомата Мура

Наличие на выходе автомата Мура комбинационной схемы может вызвать нестабильность переходного процесса за пределами окон стабильности регистров и триггеров. Это явление объясняется вероятностью одновременного переключения двух и более разрядов состояния автомата, способного вызвать многократные переключения на выходах при распространении сигналов через каскады комбинационной схемы F. Таким образом, выходной сигнал автомата, построенного по канонической модели Мура, устойчиво фиксируется триггерами и регистрами, работающими по единому с автоматом синхросигналу. Тем не менее выходной сигнал такой формы невозможно использовать для непосредственного управления триггерами типа Flip-Flop по входам синхронизации CLK (C) или триггерами-защелками (Latch) по входам загрузки GATE (G) вследствие вероятности ложных срабатываний управляемых таким способом узлов.

Третий вариант логической организации автомата представлен моделью Мура с регистровым выходом (Look-ahead Moore Output, выход с предсказанием). Автомат Мура с регистровым выходом функционирует идентично канонической модели Мура, однако лишен наиболее существенных из ее недостатков [2]. Структурная схема такого автомата представлена на рис. 11.

Рис. 11. Структурная схема автомата Мура с регистровым выходом

Основное отличие от канонической модели Мура — наличие выходного регистра, имеющего задержку распространения сигналов, равную одному такту синхронизации. Для компенсации этой задержки комбинационная схема генератора выходов F подключена не к текущему состоянию автомата Q, а к выходам комбинационной схемы переходов G, вырабатывающей следующее состояние Q_NXT. Таким образом, на информационный вход выходного регистра поступает следующая выходная комбинация V_NXT, которая должна появиться на выходах в следующем такте.

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

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

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

Применение автомата Мура с выходным регистром увеличивает задержку распространения сигналов по входу, из-за переноса комбинационной схемы F на вход регистра. В то же время выходными сигналами такого автомата можно синхронизировать регистры, счетчики, прочие автоматы и защелки. Выходная задержка автомата с регистром на выходе минимальна и сводится к выходной задержке данного регистра относительно синхросигнала (параметр T_CO). Очевидно, что построить автомат Мура с меньшей задержкой по выходу относительно синхросигнала невозможно. Уменьшение выходной задержки позволяет сократить время распространения сигналов от регистров автомата до входов внешних регистров, что способствует повышению быстродействия. Пример распространения сигналов по входу и выходу автомата с выходным регистром приведен на рис. 12.

Рис. 12. Распространение сигналов в автомате Мура с выходным регистром

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

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

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

Таким образом, установка высокого логического уровня сигнала V(i) для стабильности переходного процесса требует выполнения условия:

а установка низкого логического уровня для стабильности переходного процесса требует выполнения условия:

Графически стабильность переходного процесса синхронизированного логического сигнала V(i) поясняет рис. 13. Вопросы стабильности переходных процессов при переключении триггеров типа Flip-Flop детально рассмотрены в работах [6–8].

Рис. 13. Стабильный переходный процесс синхронизированного логического сигнала

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

Рис. 14. Временная диаграмма переключения автомата с выходным регистром

Итак, недостатки автомата Мура с регистром на выходе следующие:

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

К преимуществам автоматов Мура с выходным регистром можно отнести:

• Наличие минимальной выходной задержки, связанной с переключением выходного регистра.
• Отсутствие нестабильности переходного процесса на выходе автомата.
• Отсутствие сквозного распространения сигнала через комбинационную схему от входа до выхода автомата.
• Простоту описания на языках описания аппаратуры — HDL (для описания автомата Мура с регистром на выходе достаточно одного блока process (CLK) для VHDL и always@ (posedge CLK) для Verilog).

Четвертый вариант логической организации автомата представлен конвейеризированной структурной схемой с регистровым выходом. Автомат с конвейеризированной структурой может функционировать подобно канонической модели Мура, однако в различных тактах одному внутреннему состоянию q_s могут соответствовать различные выходные комбинации v₀. Кроме того, автомат с конвейеризированной структурой имеет все преимущества автомата Мура с регистровым выходом. Структурная схема такого автомата показана на рис. 15.

Рис. 15. Конвейеризированная структурная схема автомата

В автомате с конвейеризированной структурой текущие выходные комбинации генерируются комбинационной схемой F на такт раньше своего появления на выходах V и зависят не от текущего состояния q(t) и текущей входной комбинации a(t), а от предыдущего состояния q(t–1) и предыдущей входной комбинации a(t–1), в некоторых же случаях — и от предыдущей выходной комбинации v(t–1).

Общий вид канонических уравнений для модели автомата с конвейеризированной структурой следующий:

Из структурной схемы и канонических уравнений ясно, что автомат с конвейеризированной структурой с технической точки зрения не может быть эквивалентным автомату Мили, так как в нем отсутствует зависимость текущих выходных значений v₀ от текущей входной комбинации a_i. Реакция такого автомата на текущие входные воздействия в отличие от модели Мили проявляется не в текущем такте (t), а в следующем такте (t+1), что принципиально при разработке цифровых устройств.

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

Конвейеризация рассматриваемой модели автомата заключается в добавлении к модели Мили выходного регистра, вносящего задержку выходного сигнала, а также возможность применения обратной связи по выходу, оказывающей воздействие на генерацию выходных комбинаций. Обратная связь по выходу образует выходной автомат, последовательно соединенный с автоматом состояний. Примером выходного автомата может служить синхронный триггер RS-типа или T-типа, управляемый генератором выходов F.

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

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

Пример графа переходов автомата с конвейеризированной структурой показан на рис. 16а, а пример фрагмента графа выходов — на рис. 16б.

Рис. 16. Графический способ задания автомата с конвейеризированной структурой с помощью: а) отдельных графов переходов; б) графов выходов

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

Подобно графам описания автоматов Мили и Мура, в графах, описывающих автомат с конвейеризированной структурой, дугам с пометкой «иначе», else или default соответствует переход под воздействием любой входной комбинации, не входящей в список указанных явно комбинаций для данной вершины графа. Дуги, выходящие из вершины в единственном числе и не имеющие пометок, описывают безусловные переходы автомата.

Для описания функционирования автомата с обратной связью по выходам с помощью графа в прямоугольных вершинах следует указывать условия смены состояний отдельных выходных сигналов V(i).

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

Рис. 17. Пример совмещенного графа для автомата с конвейеризированной структурой

Совмещенный граф структурирован по строкам, в соответствии с состояниями автомата, из которых осуществляются переходы, включая состояние асинхронной начальной установки — POR. Вершины, перечисляемые в одной строке совмещенного графа, обозначают одно состояние автомата при различных выходных комбинациях. Переходы в совмещенном графе могут быть указаны для группы вершин, описывающих одно внутреннее состояние, как показано для состояния q₀ на рис. 17. Переходы между вершинами совмещенного графа могут осуществляться в объеме одной строки, потому что в автомате с конвейеризированной структурой возможно изменение выходных комбинаций без изменения состояния.

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

Описание автомата с конвейеризированной структурой в табличной форме также удобно разделить на два этапа — составление таблицы переходов и заполнение таблицы выходов. Таблица переходов аналогична таблице автомата Мура без строки выходных значений (рис. 18а). Таблица выходов схожа с таблицей переходов, за исключением того, что в ее ячейках указываются следующие выходные комбинации вместо следующих состояний. Формат таблицы выходов показан на рис. 18б. При построении автомата с обратной связью по выходу в ячейках таблицы выходов для отдельных выходных сигналов V(i) указываются условия смены состояния.

Рис. 18. Табличный способ задания автомата с конвейеризированной структурой с помощью: а) отдельных графов переходов; б) графов выходов

Если все выходы в автомате управляются с использованием условий смены состояния (установки и сброса), то проще представить таблицу выходов в виде таблицы условий выходов. Пример такой таблицы приведен на рис. 19. В верхней строке таблицы условий выходов перечисляются выходные сигналы автомата, во второй и третьей строках — условия установки «лог. 0» и «лог. 1». В нижней строке таблицы приводится начальная выходная комбинация автомата, устанавливаемая вследствие асинхронного сброса или при включении питания. Ячейки таблицы могут заполняться формулами условий, HDL-кодами условий или формулами ДНФ, причем выполнение условия и «лог. 1» тождественны.

Рис. 19. Таблица условий выходов автомата с конвейеризированной структурой

Временные характеристики и форма выходных сигналов автомата с конвейеризированной структурой аналогичны оным для автомата Мура с выходным регистром.

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

Преимущества автомата с конвейеризированной структурой аналогичны автомату Мура с регистровым выходом, кроме последнего свойства:

• наличие минимальной выходной задержки, связанной с переключением выходного регистра;
• отсутствие нестабильности переходного процесса на выходе автомата;
• отсутствие сквозного распространения сигнала через комбинационную схему от входа до выхода автомата;
• простота описания на языках VHDL и Verilog;
• возможность изменения выходной комбинации в зависимости от входных воздействий в течение разных тактов для одного состояния автомата.

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

Литература

1. Алгебраическая теория автоматов, языков и полугрупп. Под ред. М. Арбиба. Пер. с англ. М.: Статистика, 1975.
2. Pong P. Chu. RTL Hardware Design Using VHDL: Coding for Efficiency, Portability, and Scalability. John Wiley & Sons, Inc., 2006.
3. Cummings C. E. The Fundamentals of Efficient Synthesizable Finite State Machine Design using NC-Verilog and BuildGates. Sunburst Design, Inc., 2002.
4. Cummings C. E. State Machine Coding Styles for Synthesis. Sunburst Design, Inc., 1998.
5. Golson S. State machine design techniques for Verilog and VHDL. Trilobyte Systems, 1994.
6. Stephenson J., Chen D., Fung R., Chromczak J. Understanding Metastability in FPGAs. Altera Corporation. March 2009.
7. Kelly R. IP Solutions for Synchronizing Signals that Cross Clock Domains. R&D Manager, Synopsys, Inc. Jan. 2009.
8. Narain P., Cummings C. E. Clock Domain Crossing Demystified: The Second Generation Solution for CDC Verification. Real Intent, Inc., Sunburst Design, Inc., 2001.
9. Поликарпова Н. И., Шалыто А. А. Автоматное программирование. СПб.: СПбГПУ. 2008.