В. Соловьев

Структурные модели конечных автоматов при их реализации на ПЛИС

Конечный автомат представляет собой наиболее общую математическую модель цифрового устройства или цифровой системы. Поэтому очень важно при разработке различных цифровых устройств и систем применять эффективные методы синтеза конечных автоматов. В то же время, реализованные в известных пакетах автоматизированного проектирования (фирм Altera, Xilinx и других) методы синтеза основаны на традиционных подходах, которые не позволяют эффективно использовать архитектурные возможности новой элементной базы.Данная статья является первой из серии статей, посвящённых новому подходу к синтезу конечных автоматов на ПЛИС. В рамках данной серии предполагается опубликовать следующие статьи: "Проектирование конечных автоматов на ПЛИС со структурой двух программируемых матриц"; "Использование выходных макроячеек ПЛИС в качестве элементов памяти конечных автоматов"; "Использование входных буферов ПЛИС в качестве элементов памяти конечных автоматов"; "Синтез на ПЛИС совмещённых моделей конечных автоматов"; "Верификация результатов синтеза конечных автоматов на ПЛИС"; "Пакет ZUBR автоматизированного проектирования конечных автоматов на ПЛИС".В статьях данной серии будут рассмотрены формальные методы синтеза конечных автоматов на ПЛИС, которые позволяют наиболее полно и эффективно использовать архитектурные возможности ПЛИС. Отличительной чертой всех методов синтеза является простота, что делает возможным их применение даже при ручном проектировании.Экспериментальные исследования показали, что предлагаемый подход позволяет сократить стоимость реализации и повысить быстродействие конечных автоматов, в среднем, в 2–3 раза, по сравнению с известными пакетами.

В настоящее время хорошо исследованы две модели автоматов: автомат Мили [1] и автомат Мура [2]. Известна также модель автомата [3,4], в которой наборы выходных сигналов совпадают с кодами внутренних состояний автомата. В отдельных работах предлагается использовать регистры на входах и выходах автомата для буферизации входных сигналов и согласования выходных сигналов с сигналами синхронизации [5].

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

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

Классы конечных автоматов

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

a_t+1 = (z_t,a_t); (1)
w_t = (z_t,a_t);

здесь функция переходов определяет следующее внутреннее состояние автомата (состояние перехода) a_t+1, а функция выходов - формируемый выходной набор w_t. Характерным для автомата Мили является то, что выходной набор wt зависит как от входного набора zt, так и от внутреннего состояния a_t

В автомате Мура функция выходов зависит только от состояния a_t и не зависит от входного набора, поэтому поведение автомата Мура описывается следующими уравнениями:

a_t+1 = (z_t,a_t); (2)
w_t = (a_t).

При построении конечных автоматов функции переходов и выходов реализуются с помощью комбинационных схем CL и CL, соответственно, а память автомата реализуется в виде регистра RG, где в каждый момент автоматного времени t~ хранится код внутреннего состояния a_t. Структурные схемы автоматов Мили и Мура показаны на рис. 1а и 1б, соответственно. Особенностью структуры автомата Мура является то, что комбинационная схема CLy, реализующая выходные функции, не имеет непосредственной связи со входами схемы.

Рисунок 1. Основные структуры конечных автоматов: а - Мили класса A; б - Мура класса B; в - Мура класса С; г - Мили класса D; д - Мили класса E; е - Мура класса F;

Если каждый выходной набор w_t автомата Мура совпадает с кодом его внутреннего состояния a_t, то поведение автомата можно описать следующим образом:

~a_t+1 = (z_t,a_t); (3)
w_t = a_t.

Данный тип автомата называют автоматом класса C [6], аналогично, автоматы Мили (рис. 1а) и Мура (рис. 1б) называют автоматами классов A и B, соответственно. Структура автомата Мура класса C показана на рис. 1в. Её особенностью является отсутствие комбинационной схемы CL, а также то, что все выходы автомата являются регистровыми, поскольку формируются на выходах регистра RG. Отметим, что данная структура легко реализуется на ПЛИС, поскольку все регистровые выходы имеют цепи обратной связи с комбинационной частью ПЛИС.

Если каждый выходной набор w_t автомата Мили совпадает с кодом его состояния перехода a_t+1, то имеем автомат класса D [7], поведение которого описывается следующими уравнениями:

~ a_t+1 = (z_t,a_t); (4)
w_t = a_t+1.

Структура автомата Мили класса D показана на рис. 1г. Её особенностью также является отсутствие комбинационной схемы CL, однако выходы автомата являются комбинационными, поскольку формируются на выходах комбинационной схемы CL . Отметим, что необходимым условием реализации автоматов класса D на ПЛИС является возможность такого конфигурирования выходных макроячеек, при котором триггеры выходных макроячеек включены в цепи обратных связей.

Различие между автоматами классов C и D заключается в том, что в автомате класса C выходной набор w_t совпадает с кодом настоящего внутреннего состояния a_t, а в автомате класса D выходной набор w_t определяет код следующего состояния a_t+1 (состояния перехода). Преимущество автоматов классов C и D, по сравнению с автоматами классов A и B, заключается в следующем:

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

Коды внутренних состояний конечного автомата могут определяться не только наборами значений выходных переменных, но также и наборами значений входных переменных [8]. Если каждый входной набор z_t автомата Мили совпадает с кодом следующего состояния a_t+1, то имеем автомат класса E, уравнения функционирования которого имеют вид:

a_t+1 = z_t; (5)
w_t = (z_t,a_t).

Аналогично, если каждый входной набор z_t автомата Мура совпадает с кодом следующего состояния a_t+1, то имеем автомат класса F, поведение которого можно описать следующим образом:

a_t+1 = z_t; (6)
w_t = (a_t).

Особенностью структур автоматов классов E (рис. 1д) и F (рис. 1е) является отсутствие комбинационной схемы CL. В автомате класса E комбинационная схема CL имеет два типа входов: прямые (комбинационные) и буферизированные (регистровые), а в автомате класса F - только один тип входов: буферизированные.

Необходимым условием реализации на ПЛИС автоматов классов E и F является возможность буферизации в регистрах входных сигналов. Кроме того, для построения автомата класса E входы ПЛИС должны иметь два типа связи с комбинационной частью ПЛИС: прямую и буферизированную. Буферизация входных сигналов для различных ПЛИС может осуществляться с помощью: ячеек ввода/вывода, скрытых макроячеек, выходных макроячеек и др. Для определённости любые макроячейки ПЛИС, используемые для буферизации входных сигналов, будем называть входными макроячейками ПЛИС.

Преимущество автоматов классов E и F, по сравнению с автоматами классов A и B, заключается в следующем:

• упрощается комбинационная часть автомата, поскольку отпадает необходимость в реализации комбинационной схемы CL, и
• сокращается число используемых скрытых (либо выходных, если скрытые отсутствуют) макроячеек, так как память автомата реализуется с помощью входных буферов ПЛИС.

Существенным различием между автоматами Мура классов C и F является то, что в автомате класса C выходы всегда регистровые, а в автомате класса F - комбинационные. На практике редко удаётся непосредственно реализовать автоматы классов C-F. Дело в том, что не всегда входные или выходные наборы определяют все коды внутренних состояний конечного автомата. Поэтому для построения автоматов классов C-F часто вводятся дополнительные элементы памяти путём задействования скрытых макроячеек ПЛИС.

Структурные модели конечных автоматов с регистрами на входах и выходах

Для устойчивой работы конечных автоматов входные наборы должны формироваться в заданные промежутки времени, определяемые сигналом синхронизации CLK. Если это не так, в структуры автоматов вводится входной буфер RG_I, построенный на триггерах (flip-flops) или защёлках (latchs). На рис. 2 представлены структуры моделей конечных автоматов с регистрами на входах AB_I, С_I, D_I и E_I, соответствующие автоматам классов A, B, C, D и E (модель AB_I является общей для автоматов классов А и В). Отметим, что автомат класса F уже имеет входной буфер и для него модель с регистром на входе совпадает с самой моделью автомата класса F.

Рисунок 2. Структуры конечных автоматов с регистрами на входах: а - объединённая модель ABB_I автоматов Мили и Мура; б - модель CB_I автомата класса C; в - модель DB_I автомата класса D; г - модель EB_I автомата класса E

Во всех моделях AB_I, С_I, D_I и E_I регистр RG_I реализуется на входных макроячейках ПЛИС. В структурах С_I и D_I регистр RG реализуется на выходных макроячейках ПЛИС, а в структурах AB_I и E_I - на скрытых, причём в структуре E_I передача сигналов с выходов регистра RGI на вход регистра RG осуществляется через комбинационную часть ПЛИС.

Для некоторых устройств важно, чтобы время формирования выходных наборов определялось сигналом синхронизации CLK. С этой целью используются модели автоматов, на выходах которых устанавливается дополнительный выходной регистр RG_O. На рис. 3 представлены структуры моделей конечных автоматов с регистрами на выходах AB_O, D_O, E_O и F_O, соответствующие автоматам классов A, B, D, E и F (модель AB_O является общей для автоматов классов А и В). Отметим, что автомат класса C уже имеет выходной буфер в виде регистра RG, на котором реализована память автомата.

Рисунок 3. Структуры конечных автоматов с регистрами на выходах: а - объединённая модель AB_O автоматов Мили и Мура; б - модель D_O автомата класса D; в - модель E_O автомата класса E; г - модель F_O автомата класса F

В моделях AB_O, D_O, E_O и F_O регистр RG_O реализуется на выходных макроячейках ПЛИС. В структурах AB_O и D_O регистр RG реализуется на скрытых макроячейках ПЛИС, а В структурах E_O и F_O - на входных макроячейках ПЛИС.

В некоторых случаях в структуры конечных автоматов приходится одновременно вводить как входные, так и выходные регистры. На рис. 4 представлены структуры моделей конечных автоматов с регистрами на входах и выходах AB_IO, D_IO и E_IO, соответствующие автоматам классов A, B, D и E (модель AB_IO является общей для автоматов классов А и В). Отметим, что для автомата класса C регистры на входе и выходе имеет модель C_I, а для автомата класса F - модель F_O. Во всех моделях AB_IO, D_IO и E_IO регистр RG_I реализуется на входных, RG_O - на выходных, а RG - на скрытых макроячейках ПЛИС.

Рисунок 4. Структуры конечных автоматов с регистрами на входах и на выходах: а - объединённая модель AB_IO автоматов Мили и Мура; б - модель D_IO автомата класса D; в - модель E_IO автомата класса E

Фактически все рассматриваемые модели определяются шестью классами автоматов A, B, C, D, E и F, поведение которых описывается уравнениями (3.1)–(3.6). Остальные модели (AB_I, C_I, D_I, E_I, AB_O, D_O, E_O, F_O, AB_IO, D_IO и E_IO) представляют собой различные модификации этих шести классов путём установки регистров на входах и выходах. Поэтому для построения любой модели достаточно иметь методы синтеза конечных автоматов классов A, B, C, D, E и F. Методы синтеза на ПЛИС указанных классов конечных автоматов приводятся в [9].

Сложность реализации различных моделей конечных автоматов

Пусть конечный автомат характеризуется числом L входных переменных множества X = {x₁,...,x_L}, числом N выходных переменных множества Y = {y₁,...,y_N} и числом R разрядов кода внутренних состояний, причём R может принимать значения от intlog₂M до M, где M - число внутренних состояний автомата.

На выбор модели конечного автомата при его реализации на современных ПЛИС наибольшее влияние оказывают значения следующих параметров:

• тип входа t_I и выхода t₀: регистровый (r) или комбинационный (c);
• число n_IB входных буферов;
• число n_BMC скрытых макроячеек;
• число n_FF триггеров;
• число n*_BMC скрытых макроячеек, когда буферизация входных сигналов осуществляется с помощью скрытых макроячеек;
• общее число n_MC скрытых и внутренних макроячеек;
• суммарное число n_P+BMC внешних выводов и скрытых макроячеек.

Нижние границы указанных параметров для различных моделей конечных автоматов и в зависимости от значения величин L, N и R приведены в табл. 1.

Таблица 1. Сложность реализации различных моделей конечных автоматов

Общее число требуемых триггеров n_FF является важным параметром при реализации конечного автомата на ПЛИС с небольшим числом триггеров, а также для ПЛИС, не имеющих входных и скрытых макроячеек (например, стандартных ПЛИС [10]). Наиболее универсальным параметром, позволяющим оценить сложность реализации различных моделей конечных автоматов и подходящим для широкого класса ПЛИС, является число n_BMC требуемых скрытых макроячеек ПЛИС. Если ячейки ввода/вывода ПЛИС не имеют входных буферов (то есть буферизация входных сигналов осуществляется с помощью скрытых или выходных макроячеек ПЛИС), то вместо параметра n_BMC следует использовать n*_BMC, n*_BMC = n_BMC + n_IB. При реализации конечного автомата на сложных ПЛИС [11], когда размер входного буфера не критичен, поскольку буферизация входных сигналов осуществляется с помощью ячеек ввода/вывода, стоимость реализации модели можно оценить по общему числу n_MC скрытых и выходных макроячеек, n_MC = n_BMC + N. Наоборот, при реализации конечного автомата на стандартных ПЛИС, когда наблюдается дефицит числа внешних выводов и скрытых макроячеек, в качестве оценки сложности реализации может выступать параметр n_P+BMC, n_P+BMC = n_BMC + L + N.

Анализ сложности реализации по универсальному параметру n_BMC показывает, что среди моделей конечных автоматов с комбинационными входами и комбинационными выходами наилучшими являются модели D и E; с комбинационными входами и регистровыми выходами - C и E_O; с регистровыми входами и комбинационными выходами - F и D_I; с регистровыми входами и регистровыми выходами - C_I и F_O.

Временной анализ основных моделей конечных автоматов

При временном анализе работы ПЛИС наиболее важными параметрами являются следующие:

• t_CO - время установки регистровых выходов ПЛИС;
• t_PD - время задержки на комбинационной части ПЛИС (время установки комбинационных выходов);
• t_S - время удержания;
• t_H - время задержки данных на входах триггеров.

Длительность минимального периода времени смены состояний автомата tP определяется величиной

t_P = t_S + t_CO, (7)

а максимальная частота функционирования конечного автомата fmax определяется из выражения:

f_max = 1/t_P. (8)

Временные диаграммы функционирования основных моделей конечных автоматов и моделей с регистрами на выходах показаны на рис. 5. Промежуток времени, в течение которого автомат находится в определённом состоянии, будем называть тактом автомата или просто тактом. Начало каждого такта на рис. 5 определяется установкой стабильного внутреннего состояния автомата. В каждом такте сигналы цепей обратных связей, определяющие код внутреннего состояния автомата, и входные сигналы должны быть стабильными на протяжении времени t_S до прихода переднего фронта импульса синхронизации CLK и должны оставаться стабильными время t_H после его прихода. Код следующего состояния появится на выходах триггеров через время t_CO после прихода синхроимпульса, причём этому моменту будет предшествовать короткий промежуток времени нестабильности регистровых выходов.

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

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

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

Выходные сигналы автоматов классов D и E формируются в те же моменты времени, что и в структуре А: через время t_PD после установки состояния - и остаются стабильными на протяжении времени, равном стабильности входных сигналов. Выходные сигналы автомата класса F формируются так же, как в автомате Мура класса B.

В структурах автоматов AB_O, D_O, E_O и F_O с регистрами на выходах выходные сигналы формируются так же, как в автомате класса С, но с задержкой на один такт.

Временные диаграммы функционирования автоматов структур моделей AB_I, C_I, D_I и E_I с регистрами на входах и структур моделей AB_IO, D_IO и E_IO с регистрами как на входах, так и на выходах, показаны на рис. 6. Для устойчивой работы входных регистров RG_I входные сигналы z_t должны оставаться стабильными время t_S до прихода синхроимпульса и время t_h после синхроимпульса. Входные сигналы набора z_t¹, снимаемые с выходов регистров RG_I, будут стабильными через время t_CO после синхроимпульса и останутся стабильными до начала следующего такта. Смене значений сигналов z_t¹ предшествует короткий промежуток времени нестабильности, объясняемый срабатыванием регистра RG_I.

Рисунок 6. Временные диаграммы функционирования структур конечных автоматов с регистрами на входах и регистрами на входах и выходах

Недостатком структур AB_I, C_I, D_I и E_I с регистрами на входах является то, что автоматы будут функционировать с запаздыванием на один такт. Кроме того, не достигнута главная цель: возможность изменения входных сигналов в произвольные моменты времени. Дело в том, что для корректной работы регистров RG_I сигналы z_t должны изменяться так же, как в рассмотренных ранее структурах: в строго определённый период времени в пределах каждого такта.

Структурам AB_IO, D_IO и E_IO (рис. 4) с регистрами одновременно на входах и выходах присущи все недостатки структур с регистрами на выходах и регистрами на входах. Регистры на входах вызывают запаздывание функционирования автомата на один такт, а регистры на выходах являются причиной задержки ещё на один такт формируемых выходных сигналов. Таким образом, в структурах AB_IO, D_IO и E_IO выходные сигналы формируются с запаздыванием на два такта.

Модели конечных автоматов с защелками на входах

Для буферизации входных сигналов, которые могут изменяться в произвольные моменты времени, применяются не триггеры (flip-flops), а защёлки (latches). При этом используются раздельные сигналы синхронизации: CLK_I - для входных защёлок и CLK - для остальных частей схемы. В ПЛИС защёлки пропускают входные сигналы без изменений при высоком значении сигнала синхронизации CLK_I и сохраняют последние значения входных сигналов при низком значении CLK_I. Если время t_WL низкого значения сигнала синхронизации CLK_I принять равным t_S + t_H, а время t_WH высокого значения сигнала синхронизации CLK_I принять равным t_CO – t_H, то получим структуру автомата с защёлками на входах, работающую на максимальной частоте и допускающую изменение входных сигналов в произвольные моменты времени (рис. 7).

Рисунок 7. Структура автомата с защёлками на входах (а) и временная диаграмма его работы (б)

Модели конечных автоматов с защёлками на входах AB_I’, C_I’, D_I’, E_I’, AB_IO’, D_IO’ и E_IO’ функционируют аналогично структурам AB_I, C_I, D_I, E_I, AB_IO, D_IO и E_IO с триггерами на входах, но на один такт быстрее.

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

Структуру многоуровневой цифровой системы S, состоящей из K уровней, можно представить в виде совокупности последовательно соединённых подсистем S₁,...,S_K (рис. 8а). Здесь обрабатываемые данные D_I поступают на входы первой подсистемы S₁, а выходные данные D_O формируются на выходах последней подсистемы S_K; выходы каждой подсистемы S_k (за исключением последней) подсоединены ко входам следующей подсистемы S_k+1, .

Рисунок 8. Общая структура многоуровневой цифровой системы (а) и временные диаграммы сигналов синхронизации (б)

Пусть каждая подсистема S_k тактируется отдельным сигналом синхронизации CLK_k, . Начало каждого такта следующего логического уровня k, , может начинаться не раньше установки стабильного состояния выходов предыдущего уровня k–1. Поэтому каждый сигнал CLK_k должен иметь фазовый сдвиг на время t_k, , от тактов синхронизации предыдущего уровня (рис. 8б). Отметим, что если быстродействие всех подсистем S₁,...,S_K-1 одно и то же, то величины t₂,...,t_K могут иметь одинаковые значения.

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

• T_POS - время задержки формирования выходных сигналов от начала такта, измеряемое в периодах;
• T_OS - время задержки формирования выходных сигналов в пределах такта;
• T_SD - время стабильного значения выходов в пределах такта.

На основании этих параметров можно определить полное время задержки выходных сигналов от начала такта Q:

Q = T_POS + T_OS. (9)

Значения параметров T_POS, T_OS, T_SD и Q для рассматриваемых моделей конечных автоматов приведены в табл. 2.

Таблица 2. Временные параметры моделей конечных автоматов

При выборе модели конечного автомата удобно пользоваться параметрами Q и T_SD. В зависимости от значений этих параметров, все модели конечных автоматов можно разделить на шесть групп M₁,...,M₆ (табл. 3).

Таблица 3. Группы моделей в зависимости, от временных параметровв

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

Рассмотрим два класса многоуровневых последовательных цифровых систем: с раздельной и общей синхронизацией.

В цифровой системе с раздельной синхрониза-цией каждая подсистема S_k (рис. 8) тактируется отдельным синхросигналом CLK_k, . Поскольку начало каждого такта следующего уровня должно начинаться не ранее установки стабильного состояния выходов предыдущего уровня, то быстродействие (время прохождения обрабатываемых данных со входа на выход системы) последовательной системы S определяется следующим образом:

(10)

где Q_k - максимальное значение параметра Q для моделей конечных автоматов, используемых на уровне.

В цифровой системе с общей синхронизацией все подсистемы S₁,...,S_K тактируются одним и тем же синхросигналом CLK. Для определения быстродействия такой системы будем считать, что на каждом уровне используются модели, содержащие только один регистр (то есть модели первых трёх групп). Если модель конечного автомата некоторого уровня , содержит несколько регистров, то её синхронизация должна осуществляться собственным внутренним синхросигналом, согласованным с сигналом CLK. Период синхросигнала CLK в цифровой системе с общей синхронизацией определяется по самой медленной модели. Поэтому быстродействие последовательной цифровой системы в случае общей синхронизации выражается следующим образом:

P₂ = K·(Q_max + t_P), (11)

где Q_max - максимальное значение параметра Q из всех используемых в цифровой системе моделей.

Из (3.11) и (3.12), а также табл. 3 следует, что быстродействие последовательных цифровых систем ухудшается с ростом номера группы моделей конечных автоматов.

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

Отметим некоторые необходимые условия для возможности построения конвейерной цифровой системы. На всех уровнях должны применяться модели с одинаковыми временными параметрами, то есть принадлежать одной из групп M₁,...,M₆ (табл. 3). Цифровая система S должна иметь общую синхронизацию, то есть все подсистемы тактируются одним и тем же синхросигналом CLK. Если значение параметра T_OS для используемых моделей равно нулю, то период t_C синхросигнала CLK принимается равным t_P; если T_OS = t_PD, то значение t_C принимается равным t_P + t_PD. На основании вышеизложенного быстродействие конвейерной многоуровневой цифровой системы можно выразить следующим образом:

G = (K – 1)·t_C + Q. (12)

Значения быстродействия G конвейерной многоуровневой цифровой системы для различных групп моделей приведены в табл. 4. На рис. 9 показаны графики быстродействия G₁,...,G₆ различных групп моделей в зависимости от значения числа K уровней цифровой системы.

Таблица 4. Быстродействие моделей a конвейерных цифровых системах

Рисунок 9. Быстродействие различных моделей конечных автоматов в многоуровневых конвейерных цифровых системах

Из анализа графиков на рис. 9 можно определить следующие неравенства:

~G₁ < G₄ < G₆;
G₁ < G₂(G₃) < G₅; (13)
G₄ < G₅.

Таким образом, самой быстродействующей группой моделей конечных автоматов является группа M₁. Модели групп M₂(M₃) и M₅ могут иметь преимущество, по сравнению с моделями M₄ и M₆, соответственно, только для малых значений K. С ростом числа уровней K преимущество моделей M₄ и M₆ становится очевидным.

Совмещенные модели конечных автоматов

При синтезе конечных автоматов, несмотря на свою эффективность, модели автоматов классов C, D, E и F редко используются "в чистом виде", а часто вместе с моделями A и B. Это объясняется тем, что не всегда выполняются необходимые условия возможности построения автоматов классов C-F. Поэтому на практике применяется совмещение различных моделей при построении одного и того же автомата [9].

Главным критерием возможности совмещения в одной структуре различных моделей конечных автоматов является согласование временных параметров формируемых выходных сигналов: T_POS, T_OS и T_SD. Модели, в которых эти параметры не совпадают (особенно T_POS), нельзя объединять в одной структуре конечного автомата, так как это ведёт к непредсказуемости значений формируемых выходных сигналов.

На рис. 10 показаны четыре возможные структуры совмещённых моделей. Первая структура соответствует автомату Мура класса C; вторая - автоматам Мура классов B и F; третья - автоматам Мили классов A, D и E; четвёртая - совмещённой модели всех классов автоматов (A-F) с регистрами на выходах. Отметим, что установка дополнительных регистров на выходах автомата позволяет совмещать любые модели автоматов, поскольку временные параметры выходных сигналов для всех моделей уравниваются. Все представленные на рис. 10 структуры могут модифицироваться путём установки на входах регистров и защёлок, а структуры на рис. 10б и 10в - ещё и регистров на выходах.

Рисунок 10. Структуры возможных совмещённых моделей конечных автоматов: а - автомата Мура класса C; б - автоматов Мура классов B и F; в - автоматов Мили классов A, D и E; г - общей совмещённой модели автоматов с регистрами на выходах

В общем случае, действительно совмещёнными моделями конечных автоматов являются модели ADE, AD, AE и BF (сочетание букв в обозначении совмещённой модели указывает на классы конечных автоматов, входящих в совмещённую модель).

Выбор моделей конечных автоматов на ПЛИС

В разделах "Классы конечных автоматов", "Структурные модели конечных автоматов с регистрами на входах и выходах" и "Модели конечных автоматов с защелками на входах" были определены 24 базовые модели конечных автоматов, которые могут быть реализованы на ПЛИС. Затем в разделе "Использование моделей конечных автоматов в цифровых системах" были введены совмещённые модели ADE, AD, AE и BF. Поскольку на входах совмещённых моделей также могут устанавливаться регистры или защёлки, а на выходах - регистры, общее число моделей конечных автоматов, которые допускают реализацию на ПЛИС, равняется 50. Поэтому выбор подходящих моделей для реализации на ПЛИС частей цифровой системы, представленных конечными автоматами, является не тривиальной задачей.

При обозначении моделей приняты следующие правила: нижний индекс I указывает на наличие дополнительного входного буфера, построенного на триггерах; апостроф (‘) вместе с нижним индексом I обозначает, что дополнительный входной буфер построен на защёлках; нижний индекс O указывает на наличие дополнительного выходного буфера на триггерах.

При выборе моделей конечных автоматов необходимо учитывать следующие факторы:

• довлетворение системным требованиям;
• архитектурные возможности ПЛИС для реализации моделей;
• временные параметры, влияющие на производительность цифровой системы;
• стоимость реализации моделей на ПЛИС.

Среди системных требований, предъявляемых к синтезируемым конечным автоматам, в первую очередь необходимо учитывать тип входов и выходов. Входы конечных автоматов, реализуемых на ПЛИС, могут быть комбинационными или буферизированными, причём в качестве буферов могут использоваться триггеры или защёлки; выходы могут быть комбинационными или регистровыми. Особенно внимательно следует относиться к использованию моделей с комбинационными входами и выходами, когда выходные функции конечного автомата непосредственно зависят от входных переменных. В таких моделях любые изменения на входах будут вызывать изменения значений выходов. Классификация моделей конечных автоматов по типам входов и выходов приведена в табл. 5.

Таблица 5. Группы моделей кон. автоматов, в зависимости от типа входов и выходов

Следующим важным моментом при выборе моделей является наличие архитектурных свойств используемой ПЛИС, достаточных для реализации выбранных моделей конечных автоматов. Для рассматриваемых моделей наиболее важными архитектурными свойствами ПЛИС, определяющими возможность реализации соответствующих моделей, является наличие триггера в цепях обратных связей (RG_F); наличие входного буфера (RG_I), по умолчанию построенного на триггерах; возможность построения входного буфера на защёлках (RG_I’); наличие двух связей входного буфера (прямой и буферизированной) с комбинационной частью ПЛИС (RG_I2). В табл. 6 приводятся различные возможные сочетания указанных архитектурных свойств ПЛИС и реализуемые при этом модели. Отметим, что модели A, B, C и AB_O предъявляют минимальные требования к архитектурным свойствам ПЛИС.

Таблица 6. Возможность реализации моделей конечных автоматов, в зависимости от свойств PLD.

Как было показано в разделе "Структурные модели конечных автоматов с регистрами на входах и выходах", временные параметры моделей конечных автоматов определяют максимальное быстродействие всей цифровой системы. Важнейшими временными параметрами моделей конечных автоматов являются T_POS, T_OS, T_SD и Q, определённые в разделе "Использование моделей конечных автоматов в цифровых системах". Временные параметры для различных групп моделей приведены в табл. 7, здесь t_PD, t_S, t_H и t_P - временные параметры ПЛИС, определённые в разделе "Временной анализ основных моделей конечных автоматов"; в скобках указаны модели автомата класса C, когда в начальном состоянии формируется ненулевой выходной набор.

Таблица 7. Группы моделей кон. автоматов, в зависимости от временных параметров

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

Для выбора минимальной по стоимости реализации на ПЛИС модели конечного автомата прежде всего необходимо определить критерий качества стоимости реализации, который определяется архитектурными свойствами используемого ПЛИС. Оценка стоимости реализации групп моделей конечных автоматов по минимальному числу nBMC скрытых макроячеек, требуемых для реализации, приведена в табл. 8. После определения критерия качества на основании параметров конкретного автомата (L, N и R) можно приблизительно оценить стоимость реализации каждой модели.

Таблица 8. Группы моделей, в зависимости от минимальной оценки стоимости реализации на PLD

Алгоритм (выбора моделей для реализации на ПЛИС конечных автоматов цифровой системы):

1. Для некоторого автомата A_f из всего множества M моделей конечных автоматов в соответствии с табл. 5 выбирается подмножество M*, удовлетворяющее типам входов и выходов конечного автомата. Полагается: M* := U_iG_i, где G_i - группа моделей конечных автоматов, определяемая по табл. 5, которая удовлетворяет требованиям к типам входов и выходов конечного автомата, .
2. Если конечный автомат A_f имеет комбинационные входы и выходы и имеется опасность изменения значений входных переменных в произвольные моменты времени, то полагается M* := M*\G₇, где группа моделей G₇ определяется из табл. 5.
3. На основании архитектурных свойств используемого ПЛИС определяются значения параметров RG_F, RG_I, RG_I’ и RG_I2. Согласно табл. 6, определяется группа моделей , которые могут быть реализованы на заданном ПЛИС. Полагается M* := M* (G_j G₁₀).
4. На основании типа цифровой системы (последовательная или конвейерная), способа синхронизации для по-следовательной системы (общая или раздельная) и временных параметров моделей в табл. 7 определяется группа моделей , обеспечивающая максимальное быстродействие цифровой системы. Полагается M* := M* G_k.
5. На основании архитектурных свойств ПЛИС определяется критерий оценки стоимости реализации моделей конечного автомата.
6. На основании выбранного в пункте "Временной анализ основных моделей конечных автоматов" критерия оценки стоимости реализации на ПЛИС и параметров конечного автомата A_f по табл. 8 определяется группа , моделей с минимальной стоимостью реализации. Полагается M* := M* З G_m.
7. Конец.

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

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

В данном примере с помощью алгоритма определяются подходящие модели для всех автоматов цифровой системы. Поскольку данные на вход цифровой системы поступают синхронно, нет необходимости буферизировать входные данные. Однако поскольку система является конвейерной, выходы каждого уровня, в том числе и последнего, удовлетворяющего условию синхронизации входов, должны быть синхронизированы. Поэтому в пункте 1 алгоритма выбираем группу моделей G₃ с комбинационными входами и регистровыми выходами, полагается M* = {C, AB_O, D_O, E_O, ADE_O, AD_O, AE_O, BF_O}. Выполнение пункта 2 не изменяет содержимое множества M*. Поскольку ПЛИС обладает только одним свойством RG_F, в результате выполнения пункта 3 множество M* пересекается с группами G₁ и G₁₀ из табл. 6, в результате получим M* = {C, AB_O, D_O, AD_O}. Для конвейерных цифровых систем важнейшими временными параметрами являются Q и TSD. Поскольку неизвестно, какие наборы формируются в начальном состоянии автоматов Мура, группа G₁ исключается из рассмотрения, а модель C принимается из группы G₄. Все элементы множества M* принадлежит группе моделей G₄, поэтому выполнение пункта 4 алгоритма не изменяет содержимое множества M*. Поскольку отсутствует какая-либо информация об архитектуре ПЛИС, в качестве критерия стоимости реализации моделей принимается минимальное число n_BMC скрытых макроячеек. В результате выполнения пункта 5 в табл. 8 выбирается группа моделей G₁, получаем M* := M* G₁ = {C}. Таким образом, для реализации конечных автоматов конвейерной цифровой системы на ПЛИС с указанными свойствами наиболее подходящей является модель автоматов Мура класса C.

Литература

1. Mealy G.H. A method for synthesizing sequential sircuits // Bell System Techn. J. Vol. 34. 1955. P. 1045–1079.
2. Moore E.F. Gedanhen-experiments on sequential machines // In C. Shannon and J. McCarthy editors. Automata Studies Princeton University Press. 1956. P. 129–153.
3. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. 476 с.
4. Соловьев В.В. Синтез микропрограммных автоматов на программируемых матрицах логики // Весцi Акадэмii Навук Беларусi. Сер. физ.-техн. наук. 1994. № 1. С. 68–72.
5. Pomeranz I., Cheng K.-T. STOIC: state assignment based on output/input functions // IEEE Transactions on CAD, August 1993. Vol. 12. № 8. P. 613–622.
6. Programmable Logic. Intel, 1994.
7. Solovjev V., Chyzy M. Models of thefinite state machines // Proc. of the Sixth Int. Conf. on Methods and Models in Automation and Robotics (MMAR 2000), 28-31 August 2000. Miedzyzdroje. Poland. Vol. 2. P. 909–914.
8. Solovjev V. Synthesis of Sequential Circuits on Programmable Logic Devices Based on New Models of Finite State Machines // Proc. of the EUROMICRO Symposium on DIGITAL SYSTEMS DESIGN (DSD’2001), September 4-6. 2001. Warsaw. Poland. P. 170–173.
9. Соловьев В.В. Проектирование цифровых систем на основе программируемых логических интегральных схем. М.: Горячая линия - Телеком, 2001. 636 с.
10. Соловьев В.В., Булатова И.Р. Стандартные программируемые логические устройства // Зарубежная радиоэлектроника. 2000. № 4. С. 66–76.
11. Соловьев В.В., Булатова И.Р. Архитектуры сложных программируемых логиче-ских интегральных схем // Зарубежная радиоэлектроника. 2000. № 5. С. 62–78.