РАДИОТЕХНИКА И ЭЛЕКТРОНИКА, 2013, том 58, № 2, с. 192-198
ФИЗИЧЕСКИЕ ПРОЦЕССЫ В ЭЛЕКТРОННЫХ ПРИБОРАХ
УДК 004.312.4
ИСПОЛЬЗОВАНИЕ СОВМЕЩЕННОЙ МОДЕЛИ АВТОМАТОВ МИЛИ И МУРА ПРИ РЕАЛИЗАЦИИ КОНЕЧНЫХ АВТОМАТОВ НА ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ ИНТЕГРАЛЬНЫХ СХЕМАХ
© 2013 г. В. В. Соловьев
Белостокский технологический университет, 15-351 Белосток, Республика Польша, ул. Вейска 45А Поступила в редакцию 03.09.2010 г.
Рассмотрена задача синтеза конечных автоматов на программируемых логических интегральных схемах (ПЛИС), особенностью которой является использование значений выходных переменных в качестве кода или части кода внутренних состояний. Для решения поставленной задачи использована совмещенная модель автоматов Мили и Мура. Главным отличием предлагаемого подхода от известных является то, что исходный конечный автомат не подвергается никаким преобразованиям, связанным с увеличением числа внутренних состояний и числа переходов конечного автомата. Приведены необходимые условия для возможности использования значений выходных переменных в качестве кода внутренних состояний конечного автомата. Представлен метод синтеза совмещенной модели АС автоматов Мили и Мура. Отражены основные результаты исследований, а также указано на возможные направления дальнейших исследований в области разработки новых структурных моделей конечных автоматов.
DOI: 10.7868/S003384941302006X
ВВЕДЕНИЕ
Проблема использования наборов значений входных и/или выходных переменных конечных автоматов в качестве части кода внутренних состояний давно интересует разработчиков цифровых систем [1—7]. Подобные подходы в ряде случаев позволяют значительно снизить стоимость реализации и повысить быстродействие конечного автомата. С появлением программируемых логических интегральных схем (ПЛИС) [8], таких как Complex Programmable Logic Devices (CPLDs) и Field Programmable Gate Arrays (FPGAs), применяемых в качестве элементной базы цифровых систем, актуальной становится задача нахождения эффективных методов синтеза конечных автоматов на ПЛИС. С этой целью в работе [7] предложены шесть структурных моделей конечных автоматов, названные автоматами классов A, B, C, D, E и F, которые легко реализуются на современных ПЛИС.
Модель автомата класса A представляет собой классическую модель автомата типа Мили [9], в которой в каждый момент автоматного времени выходной набор зависит как от входного набора, так и от внутреннего состояния конечного автомата. Модель автомата класса B совпадает с классической моделью автомата типа Мура [10], когда каждый выходной набор зависит только от внутреннего состояния конечного автомата. Модели
автоматов классов С, Б, Е и Е представляют собой частные случаи автоматов А и В. В модели автомата класса С каждый выходной набор автомата Мура совпадает с кодом соответствующего внутреннего состояния. В модели автомата класса Б каждый выходной набор автомата Мили совпадает с кодом следующего внутреннего состояния. В модели автомата класса Е каждый входной набор автомата Мили совпадает с кодом следующего состояния. Аналогично, в модели автомата класса Е каждый входной набор автомата Мура совпадает с кодом следующего состояния. Модели автоматов классов С и Б позволяют в качестве элементов памяти конечного автомата использовать триггеры макроячеек (для СРЬЭ) или логических элементов (для БРОЛ), на которых реализуются выходные функции конечного автомата. Модели автоматов классов Е и Е позволяют в качестве элементов памяти конечного автомата использовать входные буферы ПЛИС.
В работе [7] также был выполнен временной анализ моделей для случая максимального быстродействия конечного автомата, определена минимальная длительность такта автомата (минимальный период синхронизации) и максимальная частота функционирования конечного автомата. На основании результатов временного анализа предложены [7] четыре совмещенные модели конечных автоматов: АБЕ, АБ, АЕ и ВЕ.
(а)
(б)
(в)
сьл
а,+1 ЯО
ськ
си
а,+1 ЯО
ськ
си,
сьф а,+1 ЯО а, сьу
1 ськ
Рис. 1. Структуры основных моделей конечных автоматов класса А (а), класса В (б) и класса С (в).
а
а
Главным условием возможности совмещения в одной модели конечных автоматов различных классов является совпадение временных диаграмм выходных сигналов для совмещаемых моделей. Последнее условие значительно сокращает возможности совмещения различных моделей. В то же время на практике часто встречаются конечные автоматы, которые частично обладают свойствами различных моделей. Однако из-за указанного выше ограничения приходится использовать наиболее общие модели конечных автоматов Мили [9] и Мура [10].
В данной работе для реализации конечных автоматов на ПЛИС предлагается отступить от условия абсолютного совпадения временных диаграмм выходных сигналов для совмещаемых моделей. Достаточно, чтобы выходные сигналы в совмещаемых моделях формировались в пределах одного и того же такта автомата. Такое ослабление условия возможности совмещения моделей, по сравнению с [7], позволяет совместить модели конечных автоматов класса А и с, что в ряде случаев приводит к значительному уменьшению стоимости реализации без снижения быстродействия конечного автомата.
1. ОСНОВНЫЕ СТРУКТУРНЫЕ МОДЕЛИ
На практике при проектировании последовательных схем наибольшее распространение получили два типа конечных автоматов: автомат Мили и автомат Мура. Поведение автомата Мили можно описать с помощью следующих уравнений:
а,+1 = ф(г,, а); Щ = ^(1,, а,);
где ф — функция переходов; у — функция выходов; Zt — входной набор в момент автоматного времени ,(,= 1, 2, 3, ...); V , — формируемый выходной набор; а, — настоящее состояние автомата; а, +1 — следующее состояние автомата.
Поведение автомата Мура описывается следующими уравнениями:
(2)
а(+1 = фг,, а(); Щ, = у(а,).
Отличительной чертой автомата Мили является то, что выходной набор V , зависит как от входного набора zt, так и от внутреннего состояния а,, а в автомате Мура выходной набор зависит только от внутреннего состояния а,. На рис. 1а и 1б приведены структурные модели автоматов Мили и Мура, где комбинационная схема сьф реализует функцию переходов, комбинационная схема сьу реализует функцию выходов, а регистр ЯО, управляемый сигналом синхронизации ськ, реализует память конечного автомата.
Если каждый выходной набор автомата Мура совпадает с кодом его внутреннего состояния а , то поведение автомата можно описать следующим образом:
а,+1 =ф (I,, а,);
(3)
щ , =а,.
(1)
Данный тип автомата называют автоматом класса с [11], аналогично автоматы Мили (рис. 1а) и Мура (рис. 1б) называют автоматами класса А и В соответственно. Структура автомата Мура класса с показана на рис. 1в. Ее особенностью является отсутствие комбинационной схемы сь^, а также то, что все выходы автомата являются регистро-
выми, поскольку формируются на выходах регистра ЯО. Отметим, что данная структура легко реализуется на ПЛИС, поскольку все ПЛИС допускают конфигурацию выходных макроячеек с регистровым выходом и цепью обратной связи.
2. ПРЕДЛАГАЕМЫЙ ПОДХОД
Пусть X = {хь..., х£} — множество входных переменных, У = {у1, ..., ум} — множество выходных переменных, А = {аь ..., ам} — множество внутренних состояний конечного автомата.
В практике проектирования конечных автоматов часто встречается ситуация, когда на всех переходах из некоторого состояния а,, а, е А, формируется один и тот же набор значений выходных переменных. Пусть выходной набор м, является кодом или частью кода состояния а,. Тогда при переходе конечного автомата в состояние а, в регистре ЯО будет установлен код состояния а,, при этом на выходах регистра ЯО будет сформирован выходной набор м>. Это позволяет выходы элементов памяти, которые соответствуют единичным значениям набора м>, использовать в качестве выходов конечного автомата. Для этого достаточно выходные макроячейки ПЛИС, которые реализуют данные элементы памяти, сконфигурировать в режиме регистровых выходов. Таким образом, на одних и тех же макроячейках ПЛИС будут реализованы выходные переменные и переменные обратной связи.
Поскольку выходной набор формируется на всех переходах из состояния а, то выходной набор м, не зависит от входных переменных, а зависит только от внутреннего состояния а,, т.е. выходной набор фактически является выходным набором автомата типа Мура. Более того, поскольку код (или часть кода) состояния а, совпадает с выходным набором м>, то выходной набор м, является выходным набором автомата класса С. Таким образом, мы имеем совмещенную модель автомата класса АС.
Теорема 1. Использование выходного набора м, в качестве кода (или части кода) состояния а, требует выполнения следующих необходимых условий:
1) выходной набор не должен формироваться на других переходах конечного автомата, кроме переходов из состояния а,;
2) все выходные переменные, принимающие единичные значения в наборе м>, должны быть выходными переменными автомата типа Мура, т.е. не зависеть от входных переменных.
Доказательство. Нарушение условия 1 может привести к непредусмотренному переходу конечного автомата в состояние а,, т.е. нарушению детерминированности поведения конечного
автомата. Нарушение условия 2 делает невозможным изменение значений выходных переменных автомата типа Мили при изменении значений входных переменных, т.е. приводит к нарушению алгоритма функционирования конечного автомата.
Суть предлагаемого подхода заключается в нахождении таких наборов значений выходных переменных, которые формируются на всех переходах из соответствующих состояний и удовлетворяют условиям теоремы 1, а также в специальном кодировании внутренних состояний конечного автомата, при котором найденные ранее выходные наборы используются в качестве кода или части кода внутренних состояний.
Отметим некоторые особенности предлагаемого подхода от аналогичных известных методов синтеза конечных автоматов. В [7] предлагается метод синтеза автомата класса С, причем в [7] совмещение автоматов классов А и С считается недопустимым, поскольку для автоматов классов А и С не совпадают вр
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.