== ДИСКРЕТНЫЕ СИСТЕМЫ
УДК 681.3.14/21
МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ МИЛИ ПУТЕМ СКЛЕИВАНИЯ ДВУХ ВНУТРЕННИХ СОСТОЯНИЙ* © 2012 г. А. С. Климович, В. В. Соловьев
Белоруссия, Минск, Высший государственный колледж связи, Польша, Белосток, Белостокский технический ун-т Поступила в редакцию 28.12.10 г., после доработки 23.08.11 г.
Рассматривается задача минимизации конечных автоматов типа Мили, которая часто встречается при синтезе цифровых устройств на программируемых логических интегральных схемах. Особенностью предлагаемого подхода является использование операции склеивания двух состояний, а также представление конечного автомата в виде списка переходов. Описаны случаи образования состояний ожидания в результате склеивания двух состояний. Представлены алгоритмы минимизации числа внутренних состояний, числа переходов и входных переменных конечных автоматов типа Мили. Результаты экспериментальных исследований показали, что использование предлагаемого метода при реализации конечных автоматов на программируемых логических интегральных схемах позволяет уменьшить стоимость реализации в среднем в 1.31 раза, а в наилучшем случае — в 3 раза. В заключение указываются актуальные направления дальнейших исследований методов минимизации конечных автоматов.
Введение. Традиционные методы минимизации числа внутренних состояний конечных автоматов [1—7] в основном ориентированы на преобразование вручную автоматов небольшого размера. При построении сложных цифровых систем разработчики часто сталкиваются с необходимостью построения конечных автоматов достаточно большого размера: несколько десятков внутренних состояний и несколько сотен переходов между состояниями. В качестве исходного представления конечного автомата в традиционных подходах обычно используются таблицы переходов и выходов [8], которые весьма неудобны и громоздки при программной реализации, а также при рассмотрении автоматов большого размера.
Новым толчком к развитию теории конечных автоматов послужило появление современной элементной базы — программируемых логических интегральных схем (ПЛИС) [9]. Были разработаны новые структурные модели конечных автоматов и методы их синтеза [10—14], которые позволяют эффективно использовать архитектурные возможности современных ПЛИС. Однако необходимым условием применения новых методов синтеза является требование, чтобы конечный автомат относился к определенному типу: Мили [5] или Мура [6].
Известны методы минимизации отдельно для каждого типа конечных автоматов: для автоматов Мили и для автоматов Мура. Однако в большинстве известных программ минимизации числа внутренних состояний конечных автоматов (например, в программе STAMINA системы SIS [15]) не учитывается тип конечного автомата. Поэтому актуальной является задача разработки эффективных методов минимизации внутренних состояний конечного автомата большой размерности, которые не изменяют тип исходного конечного автомата.
В [16] приведен метод минимизации конечных автоматов типа Мура. В настоящей работе рассматривается метод минимизации числа внутренних состояний конечных автоматов типа Мили путем использования операции склеивания двух состояний. Операция склеивания внутренних состояний относится к операциям эквивалентного преобразования конечного автомата и не изменяет алгоритм его функционирования [17]. Отметим, что в данном методе осуществляется минимизация не только внутренних состояний, но также числа переходов и входных переменных конечного автомата. Кроме того, в качестве представления конечного автомата используется список переходов (а не таблицы переходов, как в традиционных методах), который широко применяется при описании поведения конечных автоматов в большинстве известных языков проектирования (например, VHDL, Verilog, AHDL, KISS2 и др.). Еще одной особенностью предлагае-
* Работа выполнена при частичной финансовой поддержке Белостокского технического университета (Польша), грант № W/WI/11/07.
мого подхода является то, что во всех алгоритмах последовательно рассматриваются только два внутренних состояния конечного автомата, что позволяет избежать построения структур данных большой размерности и, как следствие, позволяет работать с конечными автоматами достаточно большого размера.
1. Суть предлагаемого подхода. Конечный автомат будем характеризовать числом L входных переменных множества X= {xb ..., xL}, числом N выходных переменных множества Y= {y1, ..., yN}, числом M внутренних состояний множества A = {аъ ..., aM}, а также параметром R = intlog2M — минимальным числом разрядов двоичного кода, достаточных для кодирования внутренних состояний конечного автомата. Функционирование конечного автомата будем описывать с помощью списка переходов, который представляет собой таблицу, состоящую из четырех столбцов: am, X(am, as), as и Y(am, as). Каждая строка списка переходов соответствует одному переходу конечного автомата. В столбце am записывается состояние, в котором начинается переход (present state); в столбце X(am, as) — набор значений входных переменных, который инициирует данный переход (условие перехода), единица в столбце X(am, as) означает безусловный переход; в столбце as записывается состояние перехода (next state); в столбце Y(am, as) — набор выходных переменных, принимающих единичное значение на данном переходе.
Введем следующие обозначения: P(a,) — множество переходов из состояния a; C(a,) — множество переходов в состояние a; A(a) — множество состояний, в которых оканчиваются переходы из состояния a; Z(a,) — множество условий переходов из состояния a,, W(a) — множество наборов выходных переменных, принимающих единичные значения на переходах из состояния a,, a, е A.
Пусть zh — некоторое условие перехода из состояния a,, zh е Z(a,), a, е A. Под условием перехода zh будем понимать набор значений входных переменных, который инициирует данный переход. Условие перехода в виде конъюнкции входных переменных записывается в столбце X(am, as) списка переходов. Условие перехода принято обозначать троичным вектором, например 1-10-0, где 1 соответствует вхождению входной переменной в конъюнкцию в прямом виде, 0 — вхождению входной переменной в конъюнкцию в инверсном виде, а дефис (-) означает, что значение входной переменной не влияет на данный переход. Из требования детерминированности поведения конечного автомата следует, что условия переходов из каждого состояния конечного автомата должны быть взаимно ортогональны. Два условия перехода являются ортогональными, если хотя бы в одной позиции они имеют различные значащие (0 или 1) значения. Например, условия перехода z1 = "00-10-" и z2 = "11-10-" ортогональны, а z1 и z3 = "000101" не ортогональны. Безусловному переходу соответствует троичный вектор, состоящий из одних дефисов.
Два внутренних состояния a, и a, конечного автомата могут быть склеены, т.е. заменены одним состоянием a_, если они эквивалентны. Эквивалентность внутренних состояний автомата означает, что поведение конечного автомата не изменяется в результате объединения этих состояний в одно состояние. Поведение конечного автомата Мили при склеивании состояний a, и a, будет идентичным, если условия переходов из состояний a, и a, которые ведут в различные состояния, будут ортогональны. Если же имеются переходы, которые из состояний a, и a, ведут в одно и то же состояние, то условия переходов для таких переходов должны быть одинаковыми. Кроме того, должны совпадать значения выходных наборов, формируемых на переходах в одинаковые состояния. При склеивании двух состояний могут также образовываться состояния ожидания. Главная стратегия предлагаемого подхода заключается в склеивании всех возможных пар внутренних состояний конечного автомата.
2. Склеивание двух состояний. Рассмотрим более детально вопрос склеивания двух состояний конечного автомата типа Мили. Необходимым и достаточным условием возможности склеивания двух состояний a, и aj, a,, aj е A, является идентичность поведения конечного автомата до и после склеивания состояний a, и aj. Другими словами, по поведению конечного автомата нельзя различить, были состояния a, или a, склеены в одно состояние a_ или нет.
Рассмотрим следующие три возможные ситуации:
A(a,) n A(aj) = 0;
A(a,) = A(a); (2.1)
A(a,) Ф A(a,) и A(a,) n A(ay) Ф 0, где 0 — пустое множество.
МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ МИЛИ А(а)
>
А(а) А(а]) = А(ау)
А(а,)
=>
А(а)
Рис. 1. Возможные ситуации при склеивании двух состояний: а — А(а¡) п А(а,) = 0; б — А(а¡) = А(ау); в А(а ) Ф А(ау) и А(а) п А(ау) Ф 0
Первое условие в (2.1) соответствует ситуации, когда все переходы из состояний а! и ау ведут в различные состояния (рис. 1, а). В этом случае необходимым и достаточным условием возможности склеивания состояний а1 и а, является взаимная ортогональность элементов множества Z(a ¡) и Z(ay). Последнее условие можно выразить следующим образом: для любого Х(а ¡, аь), аь е А(а¡), и любого Х(ау, а), а{ е А(ау), выполняется
Х(а„ ан)±.Х(а, а), (2.2)
где знак "±" означает ортогональность условий переходов Х(а, аь) и Х(а, а). Действительно, поскольку при выполнении (2.2) все условия переходов множества Z(a¡j) = Z(a¡) и Z(aу) из вновь образованного состояния а_у ортогональны, то поведение конечного автомата в состоянии детерминировано, причем однозначно определяются состояния переходов и формируемые наборы значений выходных переменных. Отметим, что в (2.2) значения выходных наборов, формируемых на переходах из состояний аI и а, т.е. значения множеств Ж(а¡) и ^(ау), не влияют на условия возможности склеивания.
Второе условие в (2.1) соответствует ситуации, когда переходы из состояний а^ и а, ведут в одно и то же множество состояний А(а ¡) = А(ау) (рис. 1, б). В этом случае необходимым и достаточным условием возможности склеивания состояний а и ау является равенство условий переходов в
а
в
одинаковые состояния, а также совпадение формируемых выходных наборов на переходах в одни и те же состояния. Последнее требование можно выразить следующим образом:
для любого ак, ак е А(а) существует Х(а, ак) е Z(ay) такое, что
Х(а, ак) = Х(а,, ак) (2.3)
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.