В. Соловьев

Использование выходных макроячеек ПЛИС в качестве элементов памяти конечных автоматов

В статье рассматривается новый подход к проектированию конечных автоматов на ПЛИС, когда выходные макроячейки ПЛИС используются одновременно для реализации выходных функций и функций переходов. Конечные автоматы типа Мура, допускающие такую реализацию, получили название автоматов класса С, а конечные автоматы типа Мили - автоматов класса D. Описываются формальные методы синтеза автоматов классов С и D. Результаты экспериментальных исследований предложенных методов в сравнении с традиционным подходом, реализованном в пакете MAX+PLUSII, показали высокую эффективность новых методов синтеза, которые позволяют уменьшить число используемых макроячеек ПЛИС, в среднем, в 2√3 раза, а для отдельных примеров - в 10√20 раз.

Введение

В [1] рассмотрено 50 структурных моделей конечных автоматов на ПЛИС, среди которых 9 моделей (C, D, C_I, D_I, D_O, D_IO, C_I▓, D_I▓, D_IO▓) используют триггеры выходных макроячеек ПЛИС в качестве элементов памяти конечных автоматов. Для реализации этих моделей достаточно располагать только двумя методами синтеза: автоматов класса С и D. Другие модели строятся на основании автоматов классов С и D пут╦м установки регистров на входе (C_I, D_I), регистров на выходе (D_O), регистров одновременно на входе и выходе (D_IO), защ╦лок на входе (C_I▓, D_I▓), а также защ╦лок на входе и регистров на выходе (D_IO▓).

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

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

Метод синтеза автоматов класса С

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

Конечный автомат будем характеризовать числом L входных переменных множества X = {x₁,...,x_L}, числом N выходных функций множества Y = {y₁,...,y_N}, числом M внутренних состояний множества A = {a₁,...,a_M}, а также числом R функций возбуждения элементов памяти (функций переходов) множества D = {d₁,...,d_R} и переменных обратной связи E = {e₁,...,e_R}.

Пусть для возможности синтеза автомата класса С введено R дополнительных элементов памяти, управляемых функциями возбуждения d_N+1,...,d_N+R, прич╦м на выходах элементов памяти формируются значения переменных обратной связи e_N+1,...,e_N+R. Фактически, синтез автомата класса С сводится к специальному кодированию внутренних состояний конечного автомата. Отметим, что в автомате класса С в качестве кода состояния выступает не конституента единицы (полная конъюнкция [2]) переменных обратных связей, как при традиционном подходе, а элементарная конъюнкция [2] переменных множества E = {e₁,...,e_N+R}.

Алгоритм 1

(кодирования состояний автомата класса С ).

1. Для каждого внутреннего состояния автомата a_i, a_i € A, определяется выходной набор, который может быть кодом или частью кода данного состояния. Для этого строится булева матрица W. Строки матрицы соответствуют состояниям автомата, а столбцы - выходным функциям. Вначале полагается, что все клетки матрицы W имеют неопредел╦нные значения. На пересечении строки i и столбца j ставится единица, если выходная функция y_j € Y(a_i), где Y(a_i) - подмножество выходных функций, принимающих единичное значение в состоянии a_i, a_i € A. Строку матрицы W, соответствующую состоянию a_i, будем обозначать W(a_i), a_i € A.
2. Вводятся дополнительные разряды кода для различия кодов состояний между собой.

   2.1. В матрице W находятся подмножества строк W₁,...,W_H, имеющих одинаковое содержимое, то есть если W(a_i) € W_h и W(a_j) € W_h, то W(a_i) = W(a_j), h = ¯1,H.

   2.2. Вводится R дополнительных внутренних переменных автомата d_N+1,...,d_N+R, где R = intlog₂ (max(|W₁|,...,|W_H|)). В матрицу W дописывается R столбцов.

   2.3. В строки каждого подмножества W_h, h = ¯1,H дописываются двоичные коды длины R, разряды которых соответствуют переменным d_N+1,...,d_N+R. При этом коды с наименьшим числом единиц необходимо в первую очередь приписывать строкам W(a_i), для которых |C(a_i)| = max, где C(a_i) - множество переходов, оканчивающихся в состоянии a_i, a_i “ A.

3. Выполняется доопределение кодов состояний для удовлетворения условию ортогональности пут╦м дописывания в клетки матрицы W с неопредел╦нными значениями нулей для столбцов, соответствующих выходным функциям y₁,...,y_N, и нулей или единиц для столбцов, соответствующих функциям возбуждения элементов памяти d_N+1,...,d_N+R. При этом необходимо минимизировать число значащих значений. Тривиальное решение заключается в дописывании нулей во все клетки матрицы W с неопредел╦нными значениями.

   Поскольку в большинстве ПЛИС при включении питания триггеры переходят в нулевые состояния, то строку W(a₁), соответствующую начальному состоянию, можно доопределять только нулевыми значениями.

4. Определяются коды состояний автомата. Каждому состоянию a_i, a_i € A, ставится в соответствие элементарная конъюнкция переменных множества Е следующим образом. Если в столбце j строки W(a_i) записана единица, то переменная e_i входит в конъюнкцию в сво╦м прямом значении, если ноль, то - в инверсном, если неопредел╦нное значение, то переменная e_i в конъюнкцию не входит.
5. Конец.

Дальнейший синтез автомата Мура класса С заключается в назначении для реализации функций возбуждения элементов памяти d₁,...,d_N+R макроячейкам ПЛИС, прич╦м функции d₁,...,d_N назначаются выходным макроячейкам ПЛИС, а функции d_N+1,...,d_N+R могут назначаться как выходным, так и скрытым (не связанным с внешними выводами) макроячейкам ПЛИС. На выходах триггеров, управляемых функциями d₁,...,d_N, будут формироваться значения как переменных обратных связей e₁,...,e_N, так и выходных функций y₁,...,y_N. Последнее возможно всегда, поскольку все регистровые выходы ПЛИС имеют цепи обратных связей. На выходах триггеров, управляемых функциями d_N+1,...,d_N+R, будут формироваться значения только переменных обратных связей e_N+1,...,e_N+R.

Пример 1. Рассмотрим работу алгоритма 1 при синтезе автомата Мура, таблица переходов которого представлена в табл. 1. Построенная по таблице переходов булева матрица W приведена в табл. 2 (безразличные значения в матрице W обозначены символом "√"). В матрице W имеется три пары одинаковых строк, поэтому W₁ = {W(a₁), W(a₆)}, W₂ = {W(a₃), W(a₅)} и W₃ = {W(a₄), W(a₇)}. Поскольку максимальная мощность множеств W₁,...,W₃ равна двум, достаточно одной переменной d₆ для кодирования строк каждого из подмножеств W₁,...,W₃. Отметим, что нулевой код приписывается строкам W(a₃) и W(a₇), поскольку |C(a₃)| > |C(a₅)| и |C(a₇)| > |C(a₄)|. При выполнении пункта 3 в отдельные клетки матрицы W вместо безразличных значений дописываются нули. Матрица W после ортогонализации строк представлена в табл. 3. Таким образом, коды внутренних состояний определяются элементарными конъюнкциями шести переменных e₁,...,e₆. На основании доопредел╦нной матрицы W можно записать следующие коды внутренних состояний автомата:

K(a₁) = ¯e₁·¯e₃·¯e₄·¯e₆;
K(a₂) = e₁·e₂;
K(a₃) = ¯e₁·e₂·e₃·¯e₄·¯e₆;
K(a₄) = ¯e₁·¯e₂·e₄·e₅·e₆;
K(a₅) = ¯e₁·e₂·e₃·¯e₄·e₆;
K(a₆) = ¯e₁·¯e₃·¯e₄·e₆;
K(a₇) = ¯e₁·e₄·e₅·¯e₆;
K(a₈) = ¯e₁·e₄·¯e₅.

Структурная таблица переходов автомата приведена в табл. 4. Логические уравнения функций возбуждения элементов памяти имеют вид:

d₁ = ¯e₁·¯e₃·¯e₄·¯e₆;
d₂ = ¯e₁·¯e₃·¯e₄·¯e₆ + e₁·e₂·¯x₁ + ¯e₁·¯e₃·e₄·e₅·e₆ + ¯e₁·e₄·e₅·¯e₆·¯x₅;
d₃ = ¯e₁·e₂·¯x₁ + ¯e₁·¯e₂·e₄·e₅·e₆ + ¯e₁·e₄·e₅·¯e₆·¯x₅;
d₄ = ¯e₁·e₂·e₃·¯e₄·¯e₆ + ¯e₁·¯e₃·¯e₄·e₆·x₄ + ¯e₁·e₄·e₅·¯e₆·x5;
d₅ = ¯e₁·e₂·e₃·¯e₄·¯e₆ + ¯e₁·¯e₃·¯e₄·e₆·x₄;
d₆ = e₁·e₂·x₁ + ¯e₁·e₂·e₃·¯e₄·¯e₆·x₂ + + ¯e₁·¯e₂·e₄·e₅·e₆·x₃ + ¯e₁·¯e₃·¯e₄·e₆·¯x₄ + + ¯e₁·e₄·e₅·¯e₆·¯x₅·x₃.

Таблица 1. Таблица переходов исходного автомата Мура

Таблица 4. Структурная таблица переходов автомата класса С

Окончательная реализация автомата класса С показана на рисунке. Отметим, что для реализации автомата класса С потребовалось на две макроячейки ПЛИС меньше, чем при использовании традиционной модели автомата Мура класса В.

Реализация автомата класса С

Приведение конечных автоматов типа Мили к автоматам типа Мура

Как было указано выше, конечный автомат класса С является автоматом типа Мура. Однако может оказаться, что исходный конечный автомат является автоматом типа Мили. Поэтому возникает необходимость приведения пут╦м эквивалентных преобразований автомата Мили к автомату типа Мура. Известно (например [3]) достаточно много способов перехода от автомата типа Мили к автомату типа Мура, и наоборот. В данной статье предлагается метод приведения автомата Мили к автомату Мура с помощью операции расщепления внутренних состояний конечного автомата.

Пусть А(a_m) - множество состояний, в которых оканчиваются переходы из состояния a_m, a_m € A. Конечный автомат является автоматом типа Мура, если для всех a_m, a_m € A, выполняются условия:

Y(a_m,a_h) = Y(a_m,a_t), (1)
для всех a_h,a_t € A(a_m), h t, где Y(a_m,a_s) - множество выходных переменных, принимающих единичные значения на переходе из состояния a_m в состояние a_s, Y(a_m,a_s) Y, a_m,a_s € A.

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

Обозначим через P(a_m) - множество всех переходов из состояния a_m, a_m € A; P_k(a_m) - некоторое подмножество переходов из состояния a_m, P_k(a_m) P(a_m); Y_k(a_m) - подмножество выходных переменных, принимающих единичные значения на каждом переходе подмножества P_k(a_m), Y_k(a_m) Y, прич╦м никакая другая выходная переменная не принимает единичного значения на переходах подмножества P_k(a_m). Тогда алгоритм расщепления внутренних состояний конечного автомата Мили для приведения к эквивалентному автомату Мура можно описать следующим образом.

Алгоритм 2

1. Если для всех состояний a_m, a_m € A, справедливы условия (1), то выполняется переход к пункту 5.
2. Находится состояние a_m, a_m € A, для которого нарушены условия (1). Определяются подмножества переходов P₁(a_m),...,P_K(a_m) из состояния am, на которых формируются различные выходные наборы Y₁(a_m),...,Y_K(a_m), соответственно, Y_k(a_m) Yh(a_m) при k h, k,h = ¯1,K.
3. Выполняется расщепление состояния am, выбранного в пункте 3.

   3.1. Вводится K новых состояний a_M+1,...,a_M+K.

   3.2. Определяются подмножества P(a_M+1),...,P(a_M+K) переходов из состояний a_M+1,...,a_M+K, для этого полагается P(a_M+k) := P_k(a_m), k = ¯1,K.

   3.3. Определяются подмножества C(a_M+1),...,C(a_M+K) переходов в состояния a_M+1,...,a_M+K, для этого полагается С(a_M+k):= С(a_m), k = ¯1,K.

   3.4. Полагается A := A\{a_m} и A := A {a_M+1,...,a_M+K}.

   3.5. Выполняется соответствующая корректировка таблицы переходов.

4. Выполняется переход к пункту 1.
5. Конец.

Метод синтеза автоматов класса D

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

Пусть B(a_s) - множество состояний, переходы из которых оканчиваются в состоянии a_s, a_s € A. Основная идея метода синтеза автомата Мили класса D заключается в выполнении расщепления "плохих" состояний с тем, чтобы для каждого состояния a_s, a_s € A, выполнялись условия:

Y(a_h,a_s) = Y(a_t,a_s), (2)
для всех a_h,a_t € B(a_s), h t

то есть чтобы для каждого состояния a_s, a_s € A, на всех переходах в данное состояние должны формироваться одинаковые наборы выходных переменных. Дальнейшие действия по синтезу автоматов класса D во многом совпадают с действиями при синтезе автоматов класса С.

Обозначим через С_k(a_s) некоторое подмножество переходов, оканчивающихся в состоянии a_s, С_k(a_s) С(a_s); Z_k(a_s) - подмножество выходных переменных, принимающих единичные значения на каждом переходе подмножества C_k(a_s), Z_k(a_s) Y, прич╦м никакая другая выходная переменная не принимает единичного значения на переходах подмножества C_k(a_s). Тогда алгоритм расщепления состояний для приведения любого автомата класса A к автомату класса D, то есть для выполнения условий (2), можно описать следующим образом.

Алгоритм 3

1. Если для всех состояний множества A выполняются условия (2), то осуществляется переход к пункту 5.
2. Находится состояние a_s, a_s € A, для которого нарушены условия (2). Определяются подмножества переходов C₁(a_s),...,C_K(a_s) в состояние as, на которых формируются различные выходные наборы Z₁(a_s),...,Z_K(a_s), соответственно, Z_k(a_s) Z_h(a_s) при k h, k,h = ¯1,K.
3. Выполняется расщепление состояния as, найденного в пункте 2.

   3.1. Вводится K новых состояний aM+1,...,a_M+K.

   3.2. Определяются подмножества P(aM+1),...,P(aM+K) переходов из состояний aM+1,...,a_M+K, для этого полагается P(a_M+K) := P(a_s), k = ¯1,K.

   3.3. Определяются подмножества C(aM+1),...,C(a_M+K) переходов в состояния aM+1,...,a_M+K, для этого полагается C(a_M+K) := := С_k(a_s), k = ¯1,K.

   3.4. Полагается A := A\{a_s} и A := A {aM+1,...,a_M+K}.

   3.5. Выполняется соответствующая корректировка таблицы переходов.

4. 4. Выполняется переход к пункту 1.
5. 5. Конец.

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

Алгоритм 4

1. Для каждого внутреннего состояния автомата a_i, a_i € A, определяется выходной набор, который может быть кодом или частью кода данного состояния. Для этого строится булева матрица W. Строки матрицы соответствуют состояниям автомата, а столбцы - выходным функциям. Вначале полагается, что все клетки матрицы W имеют неопредел╦нные значения. На пересечении строки i и столбца j матрицы W ставится единица, если a_m € B(a_i), а y_j € Y(a_m,a_i).
2. Выполняются пункты 2√4 алгоритма 1.
3. Конец.

Пример использования алгоритмов 3 и 4 при синтезе автоматов класса D приводится в [4].

Программная реализация методов синтеза автоматов классов С и D

Рассмотренные методы синтеза конечных автоматов классов С и D реализованы программно в пакете ZUBR, при этом производится следующая последовательность действий:

1. Выполняется минимизация внутренних состояний исходного конечного автомата одним из известных методов.
2. Если при синтезе автомата класса С нарушены условия (1), то выполняется алгоритм 1; если при синтезе автомата класса D нарушены условия (2), то выполняется алгоритм 3.
3. Выполняется кодирование внутренних состояний конечного автомата: для автомата класса С с помощью алгоритма 1, а для автомата класса D с помощью алгоритма 4.
4. Строится система булевых функций, соответствующая комбинационной части конечного автомата.
5. Построенная в пункте 4 система булевых функций реализуется на выбранной ПЛИС одним из методов синтеза комбинационных схем.

Программа ZUBR позволяет пользователю задавать следующие режимы и параметры синтеза:

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

Дальнейшее проектирование конечного автомата может выполняется с помощью индустриального пакета. Для этого программа ZUBR позволяет представлять результаты синтеза на следующих языках проектирования: VHDL, Verilog, AHDL, Abel и других.

Результаты экспериментальных исследований методов синтеза автоматов классов С и D

Для проверки эффективности предложенных методов в качестве исходных данных использовались эталонные примеры конечных автоматов, разработанные в центре MCNC (Microelectronics Center of North Carolina) [5]. Рассматриваемые методы синтеза сравнивались с методами синтеза конечных автоматов пакета MAX+PLUSII фирмы Altera.

Метод синтеза конечных автоматов класса С сравнивался с методом синтеза пакета MAX+PLUSII для ПЛИС семейств CLASSIC (q = 8, где q - число промежуточных шин, подсоединяемых к одной макроячейке) и MAX 5000 (q = 4). Результаты сравнения приведены в табл. 5, где Name - имя файла эталонного примера; L и N - числа входов и выходов конечного автомата, соответственно; C_A1 и C_A2 - числа используемых макроячеек ПЛИС при синтезе конечного автомата с помощью метода синтеза пакета MAX+PLUSII для семейства CLASSIC и для семейства MAX 5000, соответственно; C_C1 и C_C2 - числа используемых макроячеек ПЛИС при синтезе конечного автомата с помощью предложенного метода синтеза автоматов класса С для q = 8 и q = 4, соответственно; Type - тип конечного автомата.

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

Name	L	N	CAL	CCL	CAL/CCL	CA2	CC2	CA2/CC2	Type
bbsse	7	7	41	19	2,16	22	19	1,16	A
beecount	3	4	8	6	1,33	8	6	1,33	A
dk16	2	3	-	-	-	33	14	2,36	A
dk17	2	3	11	9	1,22	12	6	2	A
donfile	2	1	-	-	-	17	1	17	C
ex4	6	9	15	12	1,25	14	12	1,17	~B
mark1	5	16	35	20	1,75	-	-	-	A
mc	3	5	8	5	1,6	8	5	1,6	C
s386	7	7	49	20	2,45	22	20	1,1	A
s8	4	1	-	-	-	4	1	4	C
shiftreg	1	1	4	3	1,33	4	2	2	B
					13,09			31,23
mid					1,64			3,12

Анализ табл. 5 показывает, что для привед╦нных примеров применение метода синтеза автоматов класса С позволяет снизить число используемых макроячеек ПЛИС для семейства CLASSIC, в среднем, в 1,64 раза (для отдельных примеров - в 2,45 раза), а для семейства MAX 5000, в среднем, в 3,12 раза (для отдельных примеров - в 17 раз).

Аналогично, метод синтеза конечных автоматов класса D сравнивался с методом синтеза пакета MAX+PLUSII для ПЛИС семейств MAX 9000 (q = 4) и FLEX 10K (q = 5). Отметим, что семейства MAX 9000 и FLEX 10K позволяют конфигурировать макроячейки (логические элементы) с триггерами в цепях обратных связей. Результаты сравнения приведены в табл. 6, где C_A3 и C_A4 - числа используемых макроячеек ПЛИС при синтезе конечного автомата с помощью метода синтеза пакета MAX+PLUSII для семейства MAX 9000 и для семейства FLEX 10K, соответственно; C_C1 и C_C2 - числа используемых макроячеек ПЛИС при синтезе конечного автомата с помощью предложенного метода синтеза автоматов класса D для q = 4 и q = 5, соответственно.

Таблица 6. Результаты экспериментальных исследований метода синтеза автоматов класса D

Name	L	N	CA3	CDI	CA3/CDI	CA4	CD2	CA4/CD2	Type
beecount	3	4	9	6	1,5	36	10	3,6	A
ex4	6	9	13	13	1	29	14	2,07	~B
keyb	7	2	31	16	1,94	103	20	5,15	~D
lion9	2	1	6	4	1,5	24	4	6	A
opus	5	6	10	7	1,43	27	8	3,38	~D
s1	8	6	52	14	3,71	141	15	9,8	D
s27	4	1	4	4	1	43	4	10,75	D
s386	7	7	16	16	1	59	20	2,95	A
s8	4	1	5	1	5	23	1	23	C
train11	2	1	7	3	2,33	25	3	8,33	A
					20,41			75,03
mid					2,04			7,50

Анализ табл. 6 показывает, что для привед╦нных примеров применение метода синтеза автоматов класса D позволяет снизить число используемых макроячеек ПЛИС для семейства MAX 9000, в среднем, в 2,04 раза (для отдельных примеров - в 5 раз), а для семейства FLEX 10K, в среднем, в 7,5 раз (для отдельных примеров - в 23 раза).

Отметим, что методы синтеза конечных автоматов классов С и D позволяют строить в 2√3 раза более быстродействующие конечные автоматы, чем традиционные методы синтеза конечных автоматов типа Мили и Мура.

Выводы

1. Методы синтеза конечных автоматов классов С и D позволяют значительно снизить стоимость реализации и одновременно повысить быстродействие реализуемого конечного автомата.
2. Снижение стоимости реализации автоматов классов C и D, по сравнению с традиционными автоматами классов A и B, осуществляется за сч╦т упрощения комбинационной части автомата, поскольку отпадает необходимость в реализации функций возбуждения элементов памяти, а также уменьшения числа используемых выходных макроячеек ПЛИС, так как память автомата и выходные функции реализуются на одних и тех же макроячейках ПЛИС.
3. Снижению стоимости реализации автоматов классов С и D также способствует то, что в качестве кодов внутренних состояний для этих автоматов выступают элементарные конъюнкции, а не полные конъюнкции, как в традиционных моделях автоматов классов A и B.
4. Повышение быстродействия автоматов классов C и D, по сравнению с традиционными автоматами классов A и B, обусловлено тем, что для этих автоматов реализуются преимущественно выходные функции, которые, как правило, значительно проще функций возбуждения элементов памяти.
5. Методы синтеза, реализованные в индустриальных пакетах автоматизированного проектирования на ПЛИС (например, MAX+PLUSII фирмы Altera), различны для различных семейств ПЛИС, это подтверждается провед╦нными экспериментальными исследованиями.
6. Для реализации автоматов класса С не требуется никаких дополнительных архитектурных свойств ПЛИС, однако для построения автоматов класса D ПЛИС должны допускать конфигурацию макроячеек с триггерами в цепях обратных связей.
7. Выходы автоматов класса С всегда регистровые, а автоматов класса D - комбинационные.
8. Автомат класса С является автоматом типа Мура, а автомат класса D - Мили, поэтому при синтезе автоматов класса С иногда приходится приводить исходный автомат Мили к эквивалентному автомату Мура, что в некоторых случаях может заметно увеличить число внутренних состояний и число переходов конечного автомата.
9. Наибольшая эффективность методов синтеза автоматов классов С или D достигается тогда, когда исходный конечный автомат является автоматом класса С (выполняются условия (1)) или D (выполняются условия (2)).
10. Для автоматов класса С также эффективны методы синтеза автоматов класса D (подтверждением служит пример s8 из табл. 6).
11. Методы синтеза автоматов классов С и D могут эффективно применяться как при синтезе конечных автоматов на ПЛИС со структурой двух программируемых матриц, так и со структурой типа FPGA (это подтверждается экспериментальными исследованиями семейства FLEX 10K).
12. Эффективность метода синтеза автомата класса D позволяет рекомендовать разработчикам архитектур ПЛИС предусматривать возможность конфигурирования выходных макроячеек ПЛИС с триггерами в цепях обратных связей.

Заключение

Отметим некоторые возможные пути совершенствования предложенного подхода к синтезу на ПЛИС конечных автоматов классов С и D.

Поскольку эффективность кодирования внутренних состояний (а следовательно, и методов синтеза автоматов классов С и D в целом) во многом определяется качеством выполнения пункта 3 алгоритма 1, то следует разработать эффективный алгоритм решения задачи ортогонализации строк троичной матрицы пут╦м доопределения безразличных значений.

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

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

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

Литература

1. Соловьев В.В. Структурные модели конечных автоматов при их реализации на ПЛИС // Chip News. ╧ 9. С. 4√14.
2. Закревский А.Д. Логический синтез каскадных схем. М.: Наука, 1981. 416 с.
3. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз, 1962. 476 с.
4. Соловьев В.В. Проектирование цифровых систем на основе программируемых логических интегральных схем. М.: Горячая линия - Телеком, 2001. 636 с.
5. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Technical Report, Microelectronics Centre of North Carolina, 1991. 43 p.