Оптимизация схемы автомата Мура на однородных ПЛИС
Запропоновано метод оптимізації логічної схеми автомата Мура, заснований на використанні трьох різних способів кодування станів автомата. Наведено алгоритм вибору оптимальної структури для конкретного автомата. Предлагается метод оптимизации логической схемы автомата Мура, основанный на использовани...
Збережено в:
| Дата: | 2009 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/6530 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оптимизация схемы автомата Мура на однородных ПЛИС / А.А. Баркалов, А.В. Матвиенко, С.А. Цололо // Комп’ютерні засоби, мережі та системи. — 2009. — № 8. — С. 45-51. — Бібліогр.: 13 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859985299326631936 |
|---|---|
| author | Баркалов, А.А. Матвиенко, А.В. Цололо, С.А. |
| author_facet | Баркалов, А.А. Матвиенко, А.В. Цололо, С.А. |
| citation_txt | Оптимизация схемы автомата Мура на однородных ПЛИС / А.А. Баркалов, А.В. Матвиенко, С.А. Цололо // Комп’ютерні засоби, мережі та системи. — 2009. — № 8. — С. 45-51. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| description | Запропоновано метод оптимізації логічної схеми автомата Мура, заснований на використанні трьох різних способів кодування станів автомата. Наведено алгоритм вибору оптимальної структури для конкретного автомата.
Предлагается метод оптимизации логической схемы автомата Мура, основанный на использовании трех различных способов кодирования состояний автомата. Приведен алгоритм выбора оптимальной структуры для конкретного автомата.
The method of Moore FSM logic circuit optimization is proposed. The method is based on three different approaches for FSM state encoding. The common algorithm is proposed for choice of the best FSM model for given conditions.
|
| first_indexed | 2025-12-07T16:28:36Z |
| format | Article |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2009, № 8 45
A.A. Barkalov, A.V. Matvienko,
S.A. Tsololo
OPTIMIZATION OF MOORE
FSM LOGIC CIRCUIT WITH
HOMOGENEOUS CPLD
The method of Moore FSM logic cir-
cuit optimization is proposed. The
method is based on three different
approaches for FSM state encoding.
The common algorithm is proposed
for choice of the best FSM model for
given conditions.
Запропоновано метод оптиміза-
ції логічної схеми автомата Му-
ра, заснований на використанні
трьох різних способів кодування
станів автомата. Наведено алго-
ритм вибору оптимальної струк-
тури для конкретного автомата.
Предлагается метод оптимиза-
ции логической схемы автомата
Мура, основанный на использова-
нии трех различных способов ко-
дирования состояний автомата.
Приведен алгоритм выбора оп-
тимальной структуры для кон-
кретного автомата.
А.А. Баркалов, А.В. Матвиенко,
С.А. Цололо, 2009
УДК 681.324
А.А. БАРКАЛОВ, А.В. МАТВИЕНКО,
С.А. ЦОЛОЛО
ОПТИМИЗАЦИЯ СХЕМЫ АВТОМАТА
МУРА НА ОДНОРОДНЫХ ПЛИС
Введение. При синтезе схем устройств
управления часто используется модель мик-
ропрограммного автомата (МПА) Мура [1].
Одним из современных базисов, используе-
мых для реализации схем МПА, являются
программируемые логические интегральные
схемы (ПЛИС) [2, 3]. Для уменьшения аппа-
ратурных затрат в схеме МПА необходимо
учитывать как особенности его модели, так
и особенности элементного базиса [4]. В на-
стоящей работе рассматривается задача реа-
лизации схемы МПА Мура в базисе ПЛИС,
в основе которых находятся макроячейки
программируемой матричной логики (ПМЛ).
Назовем такие ПЛИС однородными в отли-
чие от микросхем, в состав которых входят
и макроячейки ПМЛ, и встроенные блоки
памяти [5]. Для оптимизации схемы МПА
Мура предлагается использовать следующие
особенности модели и базиса: наличие клас-
сов псевдоэквивалентных состояний МПА
Мура; зависимость выходных сигналов толь-
ко от состояний МПА; большой коэффици-
ент объединения по входу макроячеек ПМЛ.
Характеристика автомата Мура. Пусть
автомат Мура задан прямой структурной
таблицей (ПСТ) [1] со столбцами: ma – ис-
ходное состояние, входящее в множество со-
стояний 1 MA {a ,...,a }= ; ( )mK a – код состояния
ma A∈ разрядности 2logR M= ; sa – со-
стояние перехода; ( )sK a – код состояния
sa A∈ ; hX – конъюнкция входных сигналов
(логических условий), входящих в множест-
во 1{ ,..., }LX x x= , которая определяет переход
А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, С.А. ЦОЛОЛО
Комп’ютерні засоби, мережі та системи. 2009 , № 8 46
,m sa a< > ; hΦ – набор функций возбуждения памяти, входящих во множество
1{ ,..., }RD DΦ = и принимающих единичное значение для переключения памяти из
( )mK a в ( )sK a ; 1,...,h H= – номер перехода. Кроме того, в столбце ma записыва-
ется выходной набор ( )mY a Y⊆ , формируемый в состоянии ma . Здесь
1{ ,..., }NY y y= – множество микроопераций. Эта таблица является основой для
формирования систем булевых функций:
( ),T XΦ = Φ , (1)
( )Y Y T= . (2)
В системах (1)−(2) множество 1{ ,..., }RT T T= включает внутренние перемен-
ные, используемые для кодирования состояний МПА. Системы (1)−(2) опреде-
ляют структурную схему МПА Мура 1U (рис. 1).
Блок
переходов Рг
Блок
микро-
операций
Start
Clock
X
T YΦ
РИС. 1. Структурная схема автомата Мура 1U
В МПА 1U блок переходов (БП) реализует систему (1), а блок микроопера-
ций (БМО) − систему (2). Схемы обоих блоков реализуются на макроячейках
ПМЛ. Память состояний МПА реализуется на регистре Рг, имеющем R тригге-
ров. По сигналу Start регистр обнуляется, при этом МПА переходит в начальное
состояние. По сигналу Clock в Рг записывается код состояния перехода.
Основной недостаток модели 1U − число строк ПСТ 1( )H превышает число
0H строк ПСТ эквивалентного автомата Мили [1]. При этом для реализации сис-
темы (1) требуется больше макроячеек, чем в эквивалентном МПА Мили. Для
устранения этого недостатка можно использовать оптимальное кодирование со-
стояний либо преобразование кодов состояний в коды классов псевдоэквива-
лентных состояний [6]. Оба метода основаны на наличии классов псевдоэкви-
валентных состояний i AB ∈Π с мощностью, большей двух [7, 8]. Состояния
,m pa a A∈ называются псевдоэквивалентными, если ими отмечены операторные
вершины алгоритма управления [1], выходы которых соединены со входом од-
ОПТИМИЗАЦИЯ СХЕМЫ АВТОМАТА МУРА НА ОДНОРОДНЫХ ПЛИС
Комп’ютерні засоби, мережі та системи. 2009, № 8 47
ной и той же вершины алгоритма. Такие состояния относятся к одному классу
разбиения 1{ ,..., }A IB BΠ = множества состояний, основанному на отношении
псевдоэквивалентности [6]. При оптимальном кодировании каждый класс
i AB ∈Π представляется минимально возможным числом обобщенных интервалов
R-мерного булева пространства, а в пределе − одним. При этом длина ПСТ (чис-
ло строк в ней) может быть уменьшена до величины 0H .
Следует отметить, что такой подход не гарантирует уменьшения числа тер-
мов в системе (2) и число макроячеек в блоке БМО может быть далеко от опти-
мального. Для уменьшения аппаратурных затрат в блоке БМО можно использо-
вать метод специального кодирования состояний, ориентированный на умень-
шение числа термов ( )nQ y в каждой из функций ny Y∈ [9]. При этом возможно
уменьшение числа уровней в комбинационной схеме блока БМО, что уменьшает
длительность такта работы МПА. В предельном случае общее число макроячеек
в блоке БМО равняется числу микроопераций N .
Этот подход не гарантирует уменьшения числа термов в системе (1). При
этом увеличивается число макроячеек в блоке БП по сравнению с этой характе-
ристикой для метода оптимального кодирования. В настоящей работе для реше-
ния этой задачи предлагается использовать большой коэффициент объединения
по входу макроячеек ПМЛ. Вначале рассматривается решение этой задачи при
оптимальном и специальном кодировании состояний, а затем предлагается ме-
тод комбинированного кодирования состояний.
Уменьшение аппаратурных затрат при оптимальном кодировании со-
стояний. Закодируем состояния ma A∈ оптимальным образом, для чего может
быть использован, например, алгоритм ESPRESSO [10]. При этом множество AΠ
разбивается на множества BΠ и CΠ . Пусть ( )iI B – число обобщенных интерва-
лов булевого пространства, представляющее код ( )iK B класса i AB ∈Π . Множе-
ства BΠ и CΠ формируются следующим образом:
( ) 1i i BI B B= → ∈Π ;
( ) 1i i CI B B> → ∈Π .
Если CΠ =∅ , то автомат Мура реализуется в виде модели 1U . Однако в этой
модели число строк ПСТ равно 0H . Этим параметром определяется суммарное
число уникальных термов в системе (1). Если BΠ =∅ , то автомат реализуется
в виде модели 2U (рис. 2).
В МПА 2U используется кодирование классов iСB ∈Π кодами ( )iK B раз-
рядности 1 2R log CI= , где C CI = Π . Для автомата 2U CI I= , так как A CΠ =Π .
Для кодирования классов используются переменные τ τr ∈ , где 1τ R= .
А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, С.А. ЦОЛОЛО
Комп’ютерні засоби, мережі та системи. 2009 , № 8 48
Блок
переходов Рг
Блок
микро-
операций
Start
Clock
X
T
Y
Φ
Блок
преобразователя
кодов
τ
РИС. 2. Структурная схема автомата Мура 2U
Блок преобразователя кодов (БПК) используется для преобразования кодов
( )mK a в коды ( )iK B . Блок БП реализует систему функций ( )τ, XΦ =Φ , блок БПК
– систему функций τ τ( )T= , а блок БМО – систему (2). Такой подход гарантиру-
ет уменьшение параметра 1H до 0H , но связан с введением блока БПК, который
потребляет ресурсы ПЛИС.
В общем случае B CΠ ≠ Π ≠∅ для реализации автомата Мура предлагается
модель 3U (рис. 3).
Блок
переходов Рг
Блок
микро-
операций
Start
Clock
X T
Y
Φ
Блок
преобразователя
кодов
τ
РИС. 3. Структурная схема автомата Мура 3U
В автомате 3U используется два источника кодов классов i AB ∈Π , что воз-
можно благодаря большому коэффициенту объединения по входу макроячеек
ПМЛ [11, 12]. Коды классов i BB ∈Π поступают из регистра Рг и представляются
переменными rT T∈ . Коды классов i CB ∈Π поступают из БПК и представляются
переменными τ τr ∈ . При этом параметр 1R определяется как 1 2R log ( 1)CI= + .
Здесь единица добавляется для учета необходимости кодирования ситуации
iСB ∉Π . При этом блок БП реализует функции ( ),τ,T XΦ =Φ .
ОПТИМИЗАЦИЯ СХЕМЫ АВТОМАТА МУРА НА ОДНОРОДНЫХ ПЛИС
Комп’ютерні засоби, мережі та системи. 2009, № 8 49
Такой подход гарантирует уменьшение параметра 1H до 0H , при этом число
макроячеек в схеме БПК будет меньше, чем для модели 2U . Однако данный
подход не гарантирует уменьшение сложности блока БМО.
Уменьшение аппаратурных затрат при специальном кодировании со-
стояний. Как уже отмечалось, специальное кодирование состояний ориентиро-
вано на оптимизацию блока БМО. Возможны три ситуации для классов :i AB ∈Π
– CΠ =∅ , A BΠ =Π . Автомат представляется моделью 1U , в которой 1 0H H= .
Такой случай соответствует схеме с минимальными аппаратурными затратами,
но его вероятность очень мала;
– BΠ =∅ , A CΠ =Π . Используется модель 2U , где блок БПК потребляет мак-
симальное количество ресурсов. Этот случай также маловероятен;
– BΠ ≠∅ , CΠ ≠∅ . Используется модель 3U , где аппаратурные затраты в
схеме БМО минимальны. Общие затраты зависят от того, какая часть классов
i AB ∈Π представлена блоком БПК. Это наиболее общий случай.
Отметим, что для специального кодирования состояний можно использо-
вать метод ESPRESSO [10].
Комбинированное кодирование состояний. Оптимальное кодирование со-
стояний ориентировано на оптимизацию только блока БП. Специальное кодиро-
вание состояний ориентировано на оптимизацию только блока БМО. Назовем
комбинированным кодированием состояний подход, ориентированный на опти-
мизацию схемы автомата Мура в целом.
Построим систему функций ( ),B B A= которую можно представить в виде
1
a ( 1,..., )
M
i mi mm
B C i I
=
= ∨ = . (3)
Здесь булевская переменная 1miC = , если и только если m ia B∈ . Аналогично мо-
жет быть представлена и система микроопераций:
1
a ( 1,..., )
M
n mn mm
y C n N
=
= ∨ = , (4)
где булевская переменная 1mnC = , если и только если микрооперация ny Y∈ фор-
мируется в состоянии ma A∈ . Закодируем состояния ma A∈ таким образом, что-
бы системы (3) и (4) имели минимально возможное число термов. Для этой цели
может быть использован алгоритм ESPRESSO [10].
Пусть q – число термов, реализуемых одной макроячейкой ПМЛ. Очевид-
но, что число ( )nQ y q= будет оптимальным. Нет смысла в дальнейшем уменьше-
нии ( )nQ y , так как это не ведет к уменьшению аппаратурных затрат. Этот пара-
метр ( )q можно использовать в качестве ограничения для системы (4). Оптима-
льным результатом для системы (3) является такой, когда все ее функции пред-
ставляются в виде одной конъюнкции внутренних переменных .rT T∈ Отметим,
что в настоящее время такой алгоритм нам неизвестен.
А.А. БАРКАЛОВ, А.В. МАТВИЕНКО, С.А. ЦОЛОЛО
Комп’ютерні засоби, мережі та системи. 2009 , № 8 50
Как и для предыдущих методов кодирования, возможны три ситуации
( BΠ =∅ , CΠ =∅ , B CΠ ≠ Π ≠∅ ). При этом для реализации схемы используются
модели 1 3U U− , в которых все блоки имеют некоторые усредненные затраты.
Общий метод синтеза автомата Мура. Поскольку заранее неизвестно, ка-
кой из методов кодирования состояний даст оптимальные результаты для кон-
кретного автомата 1S , необходимо использовать все методы и выбрать из них
лучший. Для каждого из методов необходимо выбрать лучшую модель, для чего
используется следующая процедура P:
1. Кодирование состояний ma A∈ .
2. Формирование множеств BΠ и CΠ .
3. Если CΠ =∅ , то синтезируется модель 1U .
4. Если BΠ =∅ , то синтезируется модель 2U .
5. Если B CΠ ≠ Π ≠∅ , то синтезируется модель 3U .
Синтез схемы для модели jU ( 1, 2, 3j = ) предполагает построение таблиц,
задающих отдельные блоки модели, формирование систем булевых функций для
этих блоков и реализация схемы с использованием стандартных промышленных
пакетов типа WebPack [11].
Заключение. Предлагаемый метод реализации автомата Мура в базисе
ПЛИС с ячейками ПМЛ основан на использовании трех методов кодирования
состояний. Метод оптимального кодирования ориентирован на уменьшение
числа макроячеек в схеме, формирующей функции возбуждения памяти автома-
та. Метод специального кодирования состояний ориентирован на уменьшение
аппаратурных затрат в схеме формирования микроопераций. При комбиниро-
ванном кодировании состояний упрощаются схемы обоих блоков.
В зависимости от характеристик автомата и ПЛИС в каждом случае воз-
можно применение одной из трех моделей автомата. Эти модели отличаются
источниками кодов классов псевдоэквивалентных состояний, в качестве кото-
рых может использоваться регистр памяти или преобразователь кодов состоя-
ний. Большой коэффициент объединения по входу макроячеек ПМЛ позволяет
использовать оба этих источника одновременно.
Необходимо отметить, что лучшая модель не может быть выбрана априор-
но. Поэтому в работе предлагается общий алгоритм, основанный на использова-
нии всех трех методов кодирования состояний. Отметим, что разные модели ав-
томатов могут иметь разное число уровней в их логических схемах. При этом
чем меньше макроячеек используется в схеме, тем меньше уровней она включа-
ет. Таким образом, лучшая из моделей обладает и минимальным временем такта
для всех существующих девяти вариантов схемы.
Дальнейшие направления наших исследований связаны с адаптацией алго-
ритма ESPRESSO к условиям базиса однородных ПЛИС, а также с возможно-
стью применения этих методов для реализации схем автомата в базисах, отлич-
ных от ПЛИС [13].
ОПТИМИЗАЦИЯ СХЕМЫ АВТОМАТА МУРА НА ОДНОРОДНЫХ ПЛИС
Комп’ютерні засоби, мережі та системи. 2009, № 8 51
1. Baranov S. Logic Synthesis for Control Automata. – Dordrecht: Kluwer Academic Publishers,
1994. – 312 p.
2. Соловьев В.В. Проектирование цифровых схем на основе программируемых логических
интегральных схем. – М.: Горячая линия-ТЕЛЕКОМ, 2001. – 636 с.
3. Грушницкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем с использованием
микросхем программируемой логики. – СПб: БХВ. – Петербург, 2002. – 608 с.
4. Баркалов А.А., Цололо С.А. Оптимизация автомата Мура, реализуемого в базисе CPLD //
Управляющие системы и машины. – 2008. – № 4. – C. 43−48.
5. Cypress Semiconductor– http://www.cypress.com.
6. Баркалов А.А. Принципы оптимизации логической схемы микропрограммного автомата
Мура // Кибернетика и системный анализ. – 1998. – № 1. – C. 65–72.
7. Баркалов А.А., Цололо С.А. Оптимизация схемы автомата Мура в составе системы на
кристалле // Радиоэлектроника и информатика. – 2007. – № 1. – C. 35–39.
8. Баркалов А.А., Матвиенко А.В., Цололо С.А. Оптимизация логической схемы автомата
Мура на CPLD // Комп’ютернi системи, засоби та мережi. – 2007. – № 6. – C. 46–51.
9. Barkalov A.., Wegrzyn M. Design of Control Units with Programmable Logic – Zielona
Gora:University of Zielona Gora Press, 2006. – 150 p.
10. DeMicheli G. Synthesis and Optimization of Digital Circuits. – New York: McGraw-Hill,
1994. – 636 p.
11. Xilinx – www.xilinx.com.
12. Altera – www.altera.com.
13. Maxfield C. The Design Warrior’s Guide to FPGAs. – Amsterdam: Elseveir, 2004. – 541 p.
Получено 07.09.2009
http://www.xilinx.com/�
http://www.altera.com/�
|
| id | nasplib_isofts_kiev_ua-123456789-6530 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1817-9908 |
| language | Russian |
| last_indexed | 2025-12-07T16:28:36Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Баркалов, А.А. Матвиенко, А.В. Цололо, С.А. 2010-03-05T15:15:36Z 2010-03-05T15:15:36Z 2009 Оптимизация схемы автомата Мура на однородных ПЛИС / А.А. Баркалов, А.В. Матвиенко, С.А. Цололо // Комп’ютерні засоби, мережі та системи. — 2009. — № 8. — С. 45-51. — Бібліогр.: 13 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/6530 681.324 Запропоновано метод оптимізації логічної схеми автомата Мура, заснований на використанні трьох різних способів кодування станів автомата. Наведено алгоритм вибору оптимальної структури для конкретного автомата. Предлагается метод оптимизации логической схемы автомата Мура, основанный на использовании трех различных способов кодирования состояний автомата. Приведен алгоритм выбора оптимальной структуры для конкретного автомата. The method of Moore FSM logic circuit optimization is proposed. The method is based on three different approaches for FSM state encoding. The common algorithm is proposed for choice of the best FSM model for given conditions. ru Інститут кібернетики ім. В.М. Глушкова НАН України Оптимизация схемы автомата Мура на однородных ПЛИС Optimization of Moore FSM Logic circuit with homogeneous CPLD Article published earlier |
| spellingShingle | Оптимизация схемы автомата Мура на однородных ПЛИС Баркалов, А.А. Матвиенко, А.В. Цололо, С.А. |
| title | Оптимизация схемы автомата Мура на однородных ПЛИС |
| title_alt | Optimization of Moore FSM Logic circuit with homogeneous CPLD |
| title_full | Оптимизация схемы автомата Мура на однородных ПЛИС |
| title_fullStr | Оптимизация схемы автомата Мура на однородных ПЛИС |
| title_full_unstemmed | Оптимизация схемы автомата Мура на однородных ПЛИС |
| title_short | Оптимизация схемы автомата Мура на однородных ПЛИС |
| title_sort | оптимизация схемы автомата мура на однородных плис |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6530 |
| work_keys_str_mv | AT barkalovaa optimizaciâshemyavtomatamuranaodnorodnyhplis AT matvienkoav optimizaciâshemyavtomatamuranaodnorodnyhplis AT cololosa optimizaciâshemyavtomatamuranaodnorodnyhplis AT barkalovaa optimizationofmoorefsmlogiccircuitwithhomogeneouscpld AT matvienkoav optimizationofmoorefsmlogiccircuitwithhomogeneouscpld AT cololosa optimizationofmoorefsmlogiccircuitwithhomogeneouscpld |