Известия РАН. Теория и системы управления, 2022, № 3, стр. 69-80

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

В настоящее время в качестве элементной базы для построения цифровых систем широко используются программируемые логические интегральные схемы (ПЛИС). Среди множества архитектур ПЛИС широкое распространение получили два типа архитектур [1]: на основе двух программируемых матриц И и ИЛИ, а также на базе функциональных генераторов типа LUT (look up table). ПЛИС первого типа получили название сложные программируемые устройства (complex programmable logic devices – CPLD), а второго – программируемые пользователем вентильные матрицы (field programmable gate arrays – FPGA). Системы на кристалле (system on chip – SoC) также имеют в своей архитектуре конфигурируемую часть со структурой FPGA.

Архитектуру FPGA можно представить как совокупность большого количества функциональных генераторов LUT, объединяемых межсоединениями. Каждый элемент LUT позволяет реализовать произвольную булеву функцию от небольшого числа аргументов (4–6). Методы синтеза быстрых конечных автоматов на CPLD были рассмотрены в [1]. В данной работе приведен метод синтеза быстрых конечных автоматов на FPGA.

Проблемам проектирования быстрых конечных автоматов на ПЛИС посвящено достаточно много работ. В [2] представлен метод повышения производительности синхронных схем при их реализации на FPGA путем изменения расположения регистров. В [3] описан метод синтеза и оптимизации последовательностных схем на FPGA. Метод основан на концепции синтеза, управляемого информацией, общей декомпозиции и теории отношений информационных мер. В [4] предлагается метод оптимизации тактирования сложных конечных автоматов путем добавления в схему избыточного блока. В [5, 6] исследуются стили описания конечных автоматов на языке VHDL, а также известные способы кодирования внутренних состояний для реализации быстрых конечных автоматов. В [7] применяются эволюционные методы для минимизации площади кристалла и задержки выходных сигналов конечного автомата. В [8] рассматривается задача кодирования внутренних состояний и оптимизация комбинационной схемы при реализации на CPLD быстрых конечных автоматов. В [9] представлена новая архитектура программируемой логики, специально предназначенная для реализации конечных автоматов, которая позволяет сократить площадь кристалла, задержки сигналов и потребляемую мощность. В [10] предложена новая модель автомата, названная виртуальным конечным автоматом. Для реализации виртуального конечного автомата применяется архитектура, основанная на блоках памяти. В [11] рассматривается реализация конечных автоматов на FPGA с использованием встроенных блоков памяти, которая позволяет уменьшить площадь кристалла и увеличить быстродействие конечного автомата. В [12, 13] представлены методы минимизации внутренних состояний полностью и неполностью определенных конечных автоматов, которые также способствуют увеличению быстродействия конечного автомата. В [14] описывается архитектура конечного автомата с одним входом на основе бинарного дерева, для реализации которого используется модель виртуального конечного автомата [10]. В [15] рассматривается метод увеличения быстродействия микропрограммных автоматов типа Мура путем введения дополнительных внутренних состояний.

Анализ известных подходов для проектирования быстрых последовательностных схем и конечных автоматов показал следующее. Отдельные методы базируются на внесении изменений в схему устройства путем перестановки регистров [2] или добавления избыточных блоков [4], что не всегда допустимо и может привести к усложнению анализа и отладки схемы конечного автомата. Метод [3], основанный на теории отношений информационных мер, видится перспективным, однако нет сообщений о его практическом применении. Работы [5, 6] ничего нового в решение проблемы не вносят, это традиционный подход: выбор из имеющихся возможностей наиболее подходящего стиля описания конечного автомата и способа кодирования внутренних состояний. Генетические и эволюционные методы [7] не годятся для практического использования из-за своей большой вычислительной сложности. Методы синтеза быстрых конечных автоматов на CPLD [1, 8] не применимы при реализации конечного автомата на FPGA. Специальные архитектуры для реализации быстрых конечных автоматов [9, 10] существуют только в теории. Методы [11, 14] имеют существенные ограничения на условия применения. Методы [12, 13] незначительно увеличивают быстродействие конечных автоматов. Метод [15] годится для синтеза только микропрограммных автоматов, поведение которых описывается на языке граф-схем алгоритмов.

Таким образом, проведенный анализ показал, что отсутствуют эффективные методы логического синтеза быстрых конечных автоматов на FPGA. Поэтому открытым остается вопрос: как синтезировать и практически реализовать быстрый конечный автомат на реальных FPGA?

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

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

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

Статья организована следующим образом. В разд. 1 определяются ранги функций переходов и число уровней функциональных генераторов LUT, необходимых для их реализации. В разд. 2 описывается метод синтеза быстрых конечных автоматов. В разд. 3 рассматривается расщепление внутренних состояний для уменьшения числа уровней элементов LUT. В разд. 4 представлены результаты экспериментальных исследований. В заключениe обсуждаются результаты экспериментальных исследований и указываются перспективные направления проектирования быстрых конечных автоматов.

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

Для синтеза быстрых конечных автоматов на FPGA традиционно используется унарное кодирование (one-hot) внутренних состояний, при этом каждому внутреннему состоянию соответствует отдельный триггер памяти автомата, установка которого в значение 1 указывает, что автомат находится в данном состоянии. Вход каждого триггера управляется функцией переходов d_i, d_i ∈ D, i = $\overline {1,M} $, т.е. каждому внутреннему состоянию автомата соответствует своя функция переходов d_i.

Пусть A(a_i) – множество состояний, в которых оканчиваются переходы из состояния a_i; B(a_i) – множество состояний, переходы из которых оканчиваются в состоянии a_i; X(a_m, a_i) – множество входных переменных, значения которых инициируют переход из состояния a_m в состояние a_i; X(a_i) – множество входных переменных, значения которых инициируют переходы в состояние a_i:

Чтобы реализовать некоторый переход из состояния a_m в состояние a_i необходимо проверить значение выхода триггера активного состояния a_m (один бит) и значения переменных множества X(a_m, a_i), которые инициируют данный переход. Чтобы реализовать функцию перехода d_i в состояние a_i, необходимо проверить значения выходов триггеров всех состояний, переходы из которых оканчиваются в состоянии a_i, т.е. |B(a_i)| значений, где |A| – мощность множества A. Кроме того, необходимо проверить значения всех входных переменных, которые инициируют переходы в состояние a_i, т.е. |X(a_i)| значений.

Определим ранг функции переходов d_i в состояние a_i как число аргументов этой функции следующим образом:

Пусть n – число входов функциональных генераторов LUT. Если ранг r_i некоторой функции переходов d_i, I = $\overline {1,M} $, превысит n входов функционального генератора LUT, то возникает необходимость в декомпозиции функции переходов d_i и ее реализации на нескольких элементах LUT. Отметим, что путем расщепления внутренних состояний нельзя снизить ранг функций переходов ниже величины

Значение величины r* в предлагаемом методе используется в качестве верхней границы рангов функций переходов при расщеплении внутренних состояний.

Известно два основных подхода при декомпозиции булевых функций: последовательная (линейная) и параллельная [1]. При последовательной декомпозиции все функциональные генераторы LUT последовательно соединяются в цепочку. На вход первого генератора LUT поступает n аргументов реализуемой функции, а на входы всех остальных элементов LUT – на единицу меньше. Число $l_{i}^{s}$ уровней функциональных генераторов LUT при реализации функции переходов ранга r_i в случае последовательной декомпозиции определяется из выражения

где int(A) – наименьшее целое, большее или равное A.

В случае параллельной декомпозиции функциональные генераторы LUT соединяются в виде иерархической древовидной структуры. Значения аргументов функции поступают на входы элементов LUT первого уровня. На входы всех последующих уровней элементов LUT поступают значения промежуточных функций. Число $l_{i}^{p}$ уровней функциональных генераторов LUT при параллельной декомпозиции функции переходов ранга r_i определяется следующим выражением:

Какую декомпозицию, последовательную или параллельную, использует конкретный синтезатор, предсказать сложно. Предварительные исследования показали, что, например, в пакете Quartus Prime одновременно применяется как последовательная, так и параллельная декомпозиция. Число l_i  уровней функциональных генераторов LUT при реализации на FPGA функции переходов d_i с рангом r_i может находиться между значениями $l_{i}^{s}$ и $l_{i}^{p}$, i = $\overline {1,M} $.

Введем целочисленный коэффициент k, k ∈ [0, 10], который позволяет адаптировать предлагаемый алгоритм при определении числа уровней функциональных генераторов LUT к конкретному синтезатору. В этом случае число l_i уровней элементов LUT, необходимых для реализации функции переходов d_i ранга r_i, будет определяться следующим выражением:

Из (1.5) следует, что при k = 0 имеем l_i = $l_{i}^{p}$, т.е. число уровней соответствует самой быстрой параллельной декомпозиции, а при k = 10 имеем l_i = $l_{i}^{s}$, т.е. число уровней соответствует самой медленной последовательной декомпозиции. Конкретное значение коэффициента k зависит от архитектуры семейства ПЛИС и используемого синтезатора.

2. Метод синтеза быстрых конечных автоматов. Пусть для некоторой функции переходов d_i ранг r_i превышает значение r*, т.е. r_i > r*. В этом случае предлагается расщепить состояние a_i на H состояний a_{i_1}, …, a_{i_H} (рис. 1) таким образом, чтобы выполнялось r_{i_h} ≤ r* для всех h = $\overline {1,H} $.

Однако имеется опасность расхождения (выполнения до бесконечности) процесса расщепления внутренних состояний. Дело в том, что при расщеплении некоторого состояния a_i, i = $\overline {1,M} $, кроме увеличения числа состояний M, также увеличивается число переходов в состояния множества A(a_i). В результате расщепления состояния a_i для состояний множества A(a_i) увеличиваются мощности множеств B(a_m), a_m ∈ A(a_i). Поэтому для состояний множества A(a_i), согласно (1.1), возрастают ранги функций переходов, что может привести к увеличению значений $l_{i}^{s}$, $l_{i}^{p}$ и l_i.

В предлагаемом алгоритме процесс расщепления внутренних состояний прекращается при выполнении условия

где l_max – число уровней функциональных генераторов LUT, необходимых для реализации самой “плохой” функции, имеющей максимальный ранг; l_mid – среднеарифметическое значение числа уровней функциональных генераторов LUT для всех функций переходов; int(A) – наименьшее целое, большее или равное A. Процесс расщепления внутренних состояний также прекращается, если l_max > l*, где l* – значение l_max на предыдущей итерации выполнения алгоритма.

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

Алгоритм 1.

Ш а г 1. Определяется значение коэффициента k, k ∈ [0, 10], который отражает используемый средством проектирования способ декомпозиции булевых функций.

Ш а г 2. Согласно (1.1) определяются ранги r_i, i = $\overline {1,M} $, функций переходов конечного автомата.

Ш а г 3. На основании (1.3)–(1.5) для каждой функции переходов d_i определяется число l_i уровней функциональных генераторов LUT, необходимых для ее реализации.

Ш а г 4. Определяются значения l_max и l_mid. Если выполняются условия (2.1), то идти к шагу 9, иначе – к шагу 5.

Ш а г 5. Выбирается состояние a_i, для которого r_i  = max, если таких состояний несколько, среди них выбирается состояние, для которого |A(a_i)| = min (минимизируется увеличение рангов других состояний в результате расщепления состояния a_i).

Ш а г 6. Полагается l* = l_max.

Ш а г 7. С помощью алгоритма 2 (приведенного в разд. 3) выполняется пробное расщепление состояния a_i, выбранного на шаге 5.

Ш а г 8. Вновь вычисляется l_max. Если l_max > l*, то идти к шагу 9; иначе принимается расщепление состояния a_i, тогда идти к шагу 2.

Ш а г 9. Конец.

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

Значение коэффициента k, вводимого в шаге 1 алгоритма 1, определяется эмпирически путем синтеза тестовых примеров с помощью применяемого средства проектирования.

3. Расщепление внутренних состояний. Для расщепления некоторого состояния a_i, i = $\overline {1,M} $, выполняемого в шаге 6 алгоритма 1, строится булева матрица W следующим образом. Строки матрицы W соответствуют множеству переходов C(a_i), которые оканчиваются в состоянии a_i. Столбцы матрицы W делятся на две части в соответствии с типами аргументов функции переходов d_i. Первая часть столбцов матрицы W соответствует множеству B(a_i) состояний, переходы из которых оканчиваются в состоянии a_i, а вторая часть – множеству X(a_i) входных переменных, значения которых инициируют переходы в состояние a_i. На пересечении строки t, t = $\overline {1,T} $, T = |C(a_i)|, и столбца  j первой части матрицы W ставится единица, если переход c_t, c_t ∈ C(a_i), выполняется из состояния a_j, a_j ∈ B(a_i). На пересечении строки t и столбца  j второй части матрицы W ставится единица, если входная переменная x_j, x_j ∈ X(a_i), принимает значащее значение (0 или 1) на переходе c_t, c_t ∈ C(a_i).

Теперь задача сводится к разбиению матрицы W на минимальное число H строчных миноров W₁, …, W_H таким образом, чтобы число столбцов, содержащих единицы, в каждом миноре W_h, h = $\overline {1,H} $, не превышало величину r*, вычисляемую, согласно (1.2). Состояние a_i  разбивается на H состояний a_{i_1}, …, a_{i_H}, причем строки каждого минора W_h  определяют переходы в состояние a_{i_h}, h = $\overline {1,H} $.

Пусть w_t – некоторая строка матрицы W. Для расщепления некоторого состояния a_i, a_i ∈ A, может быть использован следующий алгоритм.

Алгоритм 2.

Ш а г 1. Строится булева матрица W для расщепления состояния a_i. Полагается H := 0.

Ш а г 2. Полагается H := H + 1. Начинается формирование минора W_H. В качестве опорной строки в минор W_H выбирается строка w_t  с максимальным числом единиц. Строка w_t включается в минор W_H и исключается из дальнейшего рассмотрения, полагается W_H := {w_t}, W := W\{w_t}.

Ш а г 3. Добавляются строки в минор W_H. Для этого среди строк матрицы W выбирается строка w_t, для которой выполняется неравенство

где ${\text{|}}{{W}_{H}} \cup \{ {{w}_{t}}\} {\text{|}}$ – суммарное число единиц в столбцах минора W_H и строки w_t после объединения их по ИЛИ. Если таких строк может быть выбрано несколько, то среди них выбирается строка w_t, имеющая максимальное число общих единиц с минором W_H, т.е.

где ${\text{|}}{{W}_{H}} \cap \{ {{w}_{t}}\} {\text{|}}$ – суммарное число единиц в столбцах минора W_H и строки w_t после объединения их по AND. Строка w_t включается в минор W_H  и исключается из дальнейшего рассмотрения, полагается W_H := ${{W}_{H}} \cup \{ {{w}_{t}}\} $, W := W\{w_t}.

Шаг 3 повторяется до тех пор, пока в минор W_H  может быть включена хотя бы одна строка.

Ш а г 4. Если в матрице W все строки распределены между минорами, то идти к шагу 5, иначе – к шагу 2.

Ш а г 5. Состояние a_i разбивается на H состояний a_{i_1}, …, a_{i_H} таким образом, что строки каждого минора W_h определяют переходы в состояние a_{i_h}, h = $\overline {1,H} $.

Ш а г 6. Конец.

Работу предлагаемого метода синтеза продемонстрируем на примере. Пусть необходимо синтезировать быстрый конечный автомат, граф которого показан на рис. 2 (здесь ! обозначает логическое отрицание). Данный автомат представляет собой автомат типа Мура, имеет шесть состояний a₁, …, a₆, десять входных переменных x₁, …, x ₁₀ и одну выходную переменную y, значение которой на рис. 2 показано возле каждого состояния. Переходы из состояний a₃, a₄ и a₅ являются безусловными, поэтому на этих переходах в качестве условия перехода записано логическое значение 1. Значения множеств B(a_i) и X(a_i), а также ранги r_i  функций переходов для данного конечного автомата приведены в табл. 1. Поскольку для нашего примера имеем max(|X(a_m, a_s)|) = 5, то, согласно (1.2), величина r* = 6. Пусть необходимо построить конечный автомат на FPGA, для которой максимальное число входов функциональных генераторов LUT равно 6, т.е. n = 6.

Согласно (1.3) и (1.4), определяем значения $l_{i}^{s}$ и $l_{i}^{p}$ для каждого состояния (приведены в соответствующих столбцах табл. 1). Предположим, что мы не знаем, по какому алгоритму компилятор выполняет декомпозицию булевых функций, поэтому принимаем наихудший вариант: последовательную декомпозицию. Поэтому значение коэффициента k в выражении (1.5) полагается равным 10. В результате число уровней элементов LUT, необходимых для реализации каждой функции переходов, определяется величиной l_i = $l_{i}^{s}$. Для нашего примера int(l_mid) = int(8/6) = 2. Другими словами, процесс расщепления внутренних состояний прекращается, как только каждая функция переходов может быть реализована на двух уровнях элементов LUT.

Для рассматриваемого примера, согласно табл. 1, имеем l_max = $l_{2}^{s}$ = 3 для состояния a₂, поэтому выполняется расщепление состояния a₂. Строится матрица W для расщепления состояния a₂ (рис. 3). Матрица W содержит две строки. Строка w₁ соответствует переходу из состояния a₁ в состояние a₂, а строка w₂ соответствует переходу из состояния a₆ в состояние a₂. Выполнение алгоритма 2 приводит к разбиению строк матрицы W на два подмножества: W₁ = {w₁} и W₂ = {w₂}. Поэтому состояние a₂ расщепляется на два состояния, как показано на рис. 4. Новые значения величин B(a_i), X(a_i), r_i, $l_{i}^{s}$ и $l_{i}^{p}$ приведены в табл. 2. Теперь имеем l_max = l_mid = 1, поэтому выполнение алгоритма 1 завершается.

Таким образом, для данного примера путем расщепления состояния a₂  удалось снизить максимальное число уровней элементов LUT, необходимых для реализации функций переходов конечного автомата, с 3 до 1 в случае последовательной декомпозиции и с 2 до 1 в случае параллельной декомпозиции.

4. Результаты экспериментальных исследований. Рассмотренный метод синтеза быстрых конечных автоматов исследовался при реализации на FPGA эталонных примеров конечных автоматов, разработанных в центре MCNC [17]. Для этого к каждому эталонному примеру конечного автомата применялся представленный метод синтеза. Оба конечных автомата, исходный и синтезированный, описывались на языке Verilog. Затем выполнялась стандартная реализация на FPGA конечных автоматов с помощью системы Quartus Prime версии 17.1. При этом использовались параметры синтеза системы Quartus, устанавливаемые по умолчанию. В качестве числа входов функциональных генераторов LUT было принято n = 4. Предлагаемый метод удалось применить к 21 эталонному примеру из 48, т.е. в 43.75% случаев. Для остальных примеров условия (2.1) не были нарушены и расщепление состояний не выполнялось.

Результаты применения рассмотренного метода синтеза быстрых конечных автоматов приведены в табл. 3, где FSM – имя эталонного примера; Ns – число расщеплений внутренних состояний; M и P – число состояний и число переходов конечного автомата до применения метода; M* и P* – число состояний и число переходов конечного автомата после применения метода; l_max и $l_{{\max }}^{*}$ – максимальный ранг функций переходов до и после применения метода; M*/M, P*/P и l_max/$l_{{\max }}^{*}$ – отношения соответствующих параметров; mid – среднее значение параметра; max – максимальное значение параметра.

Анализ табл. 3 показывает, что в синтезированных примерах конечных автоматов среднее число расщеплений составляет 3.00, а максимальное – 11. В результате применения метода число состояний конечных автоматов увеличилось в среднем в 1.68 раза, а максимально – в 3 раза; аналогично число переходов увеличилось в среднем в 1.63 раза, а максимально – в 3.36 раза. Применение данного метода позволило уменьшить максимальный ранг функций переходов в среднем в 2.40 раза, а максимально – в 6.33 раза. Таким образом, несмотря на увеличение числа состояний и числа переходов конечных автоматов, представленный метод позволяет значительно уменьшить максимальный ранг функций переходов. Однако открытым остается вопрос: на сколько увеличилось быстродействие конечных автоматов?

Для ответа на поставленный вопрос была выполнена реализация эталонных примеров на следующих семействах FPGA: Arria II, Cyclone V, MAX II и Stratix V. Результаты исследований приведены в табл. 4 и 5, где L и L* – число логических элементов FPGA (стоимость реализации), необходимых для реализации исходного и синтезированного конечных автоматов; F и F* – максимальная частота функционирования исходного и синтезированного конечных автоматов; L*/L и F*/F – отношения соответствующих параметров.

Анализ табл. 4 и 5 показывает, что предложенный метод позволяет для различных семейств FPGA увеличить быстродействие конечных автоматов в среднем от 1.08 до 1.19 раза, а максимально – от 1.52 до 1.73 раза (пример EX1 при реализации на FPGA семейства Cyclone V). Применение метода также увеличивает стоимость реализации конечных автоматов в среднем от 1.27 до 1.35 раза.

В табл. 6 приведено сравнение предложенного метода с известными университетскими программами кодирования внутренних состояний конечных автоматов JEDI [18] и NOVA [19], где FJ, FN и F* – максимальная частота функционирования конечного автомата при использовании программы JEDI, NOVA и данного метода соответственно.

Анализ табл. 6 показывает, что с помощью предложенного метода быстродействие конечных автоматов увеличивается в среднем в 2.03–2.33 раза по сравнению с программой JEDI и в 3.68–4.47 раза по сравнению с программой NOVA. При этом максимальное увеличение быстродействия составляет 3.11 раза по сравнению с программой JEDI и 8.31 раза по сравнению с программой NOVA. Такое большое преимущество рассмотренного метода с методами, реализованными в программах JEDI и NOVA, объясняется тем, что данный метод нацелен на увеличение быстродействия, а упомянутые методы – на уменьшение стоимости реализации конечных автоматов.

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

Предлагаемый метод может также применяться и при построении быстрых конечных автоматов на заказных микросхемах (application specific integrated circuit – ASIC). Для этого достаточно определить оценки числа уровней схемы (1.3) –(1.5) для конкретной архитектуры ASIC.

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