ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2015, № 2, с. 68-80
^ ДИСКРЕТНЫЕ
СИСТЕМЫ
УДК 004.312.4
СТРУКТУРНЫЕ МОДЕЛИ КОНЕЧНЫХ АВТОМАТОВ ПРИ ИХ РЕАЛИЗАЦИИ НА ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ ИНТЕГРАЛЬНЫХ СХЕМАХ И СИСТЕМАХ НА КРИСТАЛЛЕ* © 2015 г. А. С. Климович, В. В. Соловьев
Польша, Белосток, Белостокский технологический ун-т Поступила в редакцию 11.03.14 г., после доработки 22.08.14 г.
В проектах цифровых систем на программируемых логических интегральных схемах и системах на кристалле при передаче сигналов между функциональными блоками часто используются регистровые буферы. В настоящей работе рассматриваются структурные модели конечных автоматов, которые позволяют триггеры входных и выходных буферов применять в качестве элементов памяти конечного автомата. С этой целью предложена новая классификация структурных моделей конечных автоматов, согласно которой все конечные автоматы делятся на шесть классов: А, В, С, В, Е и Г. В моделях автоматов классов С и В в качестве элементов памяти автомата используются триггеры выходных буферов, а в моделях автоматов классов Е и Г — входных буферов. В настоящей работе дается определение множества внутренних состояний каждого класса и предлагаются методы синтеза автоматов классов С—Г. Результаты экспериментальных исследований показали, что применение моделей автоматов классов С—Г позволяет уменьшить число внутренних элементов памяти в среднем от 2.22 до 25.83%, а для отдельных примеров — на 100%.
DOI: 10.7868/S0002338815010072
Введение. В связи с широким использованием программируемых логических интегральных схем (ПЛИС), таких, как CPLD (Complex Programmable Logic Device) и FPGA (Field Programmable Gate Array), а также при проектировании разнообразных последовательных схем в системах на кристалле SoC (System on Chip) возникла острая необходимость в поиске новых структурных моделей конечных автоматов, которые эффективно используют архитектурные возможности современных ПЛИС.
В настоящее время хорошо исследованы две модели конечных автоматов: автомат типа Мили [1] и автомат типа Мура [2]. Архитектуры современных ПЛИС обычно включают разнообразные блоки памяти, а также элементы распределенной памяти. Поэтому большое число публикаций посвящено разработке структурных моделей конечных автоматов на основе или с помощью памяти FPGA. Так, в [3] предлагаются структурные модели конечных автоматов при их реализации на массиве ячеек памяти. В [4] исследуется структура конечных автоматов на основе памяти FPGA.
Изучались иерархические структурные модели конечных автоматов. Так, в работе [5] рассматривается структура для реализации иерархических конечных автоматов (Hierarchical finite-state machine), которая состоит из комбинационной схемы, стековой памяти и преобразователя кодов. В [6] предлагается структурная модель для реализации параллельных иерархических конечных автоматов, которая включает комбинационную схему и две стековые памяти: для конечных автоматов и для внутренних состояний.
Некоторые публикации посвящены разработке структурных моделей конечных автоматов типа Мура при их реализации на CPLD и FPGA. В [7] предложены структурные модели для реализации конечных автоматов Мура на макроячейках CPLD. В [8] исследуется структура микропрограммного автомата типа Мура при его реализации на логических элементах FPGA типа LUT (Look Up Table). В [9] рассматривается структура и предлагается метод синтеза автомата Мура на FPGA с целью минимизации логических элементов LUT и блоков памяти.
Структуры конечных автоматов для реализации рекурсивных вычислений рассматривались в [10—12]. В [10] предложена структура при реализации рекурсивных алгоритмов для микропро-
* Работа выполнена при финансовой поддержке Белостокского технологического университета (Польша) (грант № S/WI/1/2013).
граммных автоматов, которая состоит из комбинационной схемы и двух блоков стековой памяти: конечных автоматов и модулей. В [11] приводится общая структура конечного автомата для реализации рекурсивных алгоритмов, которая состоит из комбинационной схемы, и трех блоков стековой памяти: модулей, состояний и данных. В [12] рассматриваются две структуры конечных автоматов для реализации рекурсивных алгоритмов: с явными и неявными модулями.
Отметим еще несколько интересных структурных моделей конечных автоматов. В [13] описываются структуры асинхронного конечного автомата и конвейерного асинхронного конечного автомата с сигналами разрешения для определения момента стабилизации внутреннего состояния. В [14] предложена структура реконфигурируемого конечного автомата, которая, кроме двух комбинационных схем, реализующих функции переходов и выходов, содержит три дополнительные комбинационные схемы. В [15] рассматривается структура конечного автомата вместе с блоком обработки данных, названная FSM with data path (FSMD).
В цифровых системах на базе ПЛИС и SoC при передаче сигналов между блоками часто используются входные и выходные буферы, которые представляют собой обычные регистры, состоящие из триггеров. Возможность индивидуального управления каждым триггером или группой триггеров в архитектурах современных ПЛИС и SoC позволяет в качестве элементов памяти конечных автоматов применять триггеры входных, выходных, а также одновременно входных и выходных буферов отдельных функциональных блоков. Поскольку входные и выходные буферы устанавливаются независимо от способа реализации конечных автоматов, находящихся внутри блоков, то реализация элементов памяти конечного автомата на триггерах входных и (или) выходных буферов не требует использования дополнительных ресурсов ПЛИС.
Возможность применения значений входных или выходных сигналов (векторов) в качестве кодов внутренних состояний конечных автоматов исследовалась в [16—18]. В [16] задача решается для полностью определенных конечных автоматов, а также с неопределенными значениями входных и выходных векторов. В [17] в качестве части кода внутренних состояний используются выходные сигналы автомата Мура, в [18] в качестве части кода внутренних состояний — выходные векторы с неопределенными значениями.
В [19] предложены структурные модели конечных автоматов на ПЛИС, в которых в качестве элементов памяти используются триггеры на выходах и в цепях обратных связей макроячеек CPLD и логических элементов FPGA, выступающие как триггеры выходных буферов. В [20, 21] предложена классификация структурных моделей конечных автоматов, в соответствии с которой можно выделить шесть основных и четыре совмещенных структурных модели конечных автоматов, где в качестве элементов памяти конечных автоматов выступают триггеры входных и выходных буферов. В [22] рассматриваются совмещенные структурные модели конечных автоматов. В [23] исследуются методы синтеза основных и совмещенных структурных моделей конечных автоматов на ПЛИС. В [24, 25] описывается совмещенная модель конечных автоматов Мили и Мура.
В настоящей работе исследуются различные структурные модели конечных автоматов, в которых в качестве элементов памяти могут использоваться триггеры буферов входных и выходных сигналов. В статье впервые дано определение внутренних состояний каждого класса конечных автоматов. Представлен алгоритм синтеза автоматов класса C, на основе которого строятся методы синтеза автоматов классов D, E и F. Экспериментальные исследования посвящены проверке возможности уменьшения числа внутренних состояний для конечных автоматов каждого класса.
1. Классы конечных автоматов. В практике инженерного проектирования наибольшее распространение получили два типа конечных автоматов: автомат Мили и автомат Мура. Поведение автомата Мили описывается с помощью следующих уравнений:
a+i = , at);
wt = y(zt, at),
где ф — функция переходов; у — функция выходов; t — моменты автоматного времени (t = 1, 2, 3, ...); zt — входной вектор в момент времени t; wt — формируемый выходной вектор; at — настоящее состояние автомата; at +1 — следующее состояние автомата.
Поведение автомата Мура описывается следующими уравнениями:
at+i = , at);
Wt = y(at).
V
СЬф
Ч + 1
RG
1ськ
СЬЧ
V
сЬф а,+1 RG А а Ч сЬу
1ськ
сЬф а,+1 RG А
Г"»
1ськ
сЬф 1 , RG Л
а, + 1
1ськ
+ 1
RG
1ськ
СЬЧ
а + 1
RG
-Л-
1ськ
си
Рис. 1. Структуры моделей конечных автоматов: а — класса А; б — класса В; в — класса С; г — класса В; д — класса Е; е — класса Ж
а
а
в
а
г
а
д
а
е
а
Структурные модели автоматов Мили и Мура представлены на рис. 1, а и б, где комбинационная схема сЬф реализует функцию переходов, комбинационная схема сЬу — функцию выходов, регистр RG — память конечного автомата, сЬК — сигнал синхронизации конечного автомата.
Если каждый выходной вектор автомата Мура совпадает с кодом его внутреннего состояния а, то поведение автомата можно описать следующим образом:
а,+1 = Ф(г,, а,);
^ = а,.
Данный тип автомата называют автоматом класса С [26], аналогично автоматы Мили и Мура называют автоматами классов А и В соответственно. Структура автомата класса С показана на рис.1, в. Ее особенностью является отсутствие комбинационной схемы сЬ^, а также то, что все выходы автомата являются регистровыми, поскольку формируются на выходах регистра RG.
Если каждый выходной вектор V, автомата Мили совпадает с кодом его следующего состояния а, +1, то имеем автомат класса В (рис. 1, г), поведение которого описывается следующими уравнениями:
а,+1 = Ф(г,, а,); Щ = а(+1.
Особенность структуры автомата класса В — отсутствие комбинационной схемы сЬу, однако выходы автомата являются комбинационными, поскольку формируются на выходах комбинационной схемы сЬф. Различие между автоматами классов С и В заключается в том, что в автомате класса С выходной вектор совпадает с кодом настоящего состояния автомата а, а в автомате класса В выходной вектор определяет код следующего состояния а, +1.
Отметим, что для реализации автомата класса С на ПЛИС достаточно сконфигурировать выходы логических элементов, на которых реализуются выходные переменные, как регистровые, а для реализации автомата класса В достаточно сконфигурироват
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.