Реализация автомата Мура на FPGA в виде сети Петри
Предложен метод синтеза автоматов Мура в виде сети Петри на микросхемах FPGA. Метод основан на преобразовании исходной граф-схемы алгоритма к сети Петри с дальнейшей ее реализацией в виде принципиальной схемы. Рассмотрены особенности реализации схемы автомата на микросхемах FPGA. Предложена методика...
Saved in:
| Date: | 2006 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2006
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/6458 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Реализация автомата Мура на FPGA в виде сети Петри / А.А. Баркалов, А.А. Красичков, А.В. Матвиенко // Комп’ютерні засоби, мережі та системи. — 2006. — № 5. — С. 67-72. — Бібліогр.: 6 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859637967825403904 |
|---|---|
| author | Баркалов, А.А. Красичков, А.А. Матвиенко, А.В. |
| author_facet | Баркалов, А.А. Красичков, А.А. Матвиенко, А.В. |
| citation_txt | Реализация автомата Мура на FPGA в виде сети Петри / А.А. Баркалов, А.А. Красичков, А.В. Матвиенко // Комп’ютерні засоби, мережі та системи. — 2006. — № 5. — С. 67-72. — Бібліогр.: 6 назв. — рос. |
| collection | DSpace DC |
| description | Предложен метод синтеза автоматов Мура в виде сети Петри на микросхемах FPGA. Метод основан на преобразовании исходной граф-схемы алгоритма к сети Петри с дальнейшей ее реализацией в виде принципиальной схемы. Рассмотрены особенности реализации схемы автомата на микросхемах FPGA. Предложена методика ее синтеза по граф-схеме алгоритма. Приведен пример применения предложенного метода.
The method of Moore FSM as a Petri network on FPGA is offered. The method is based on the flow-chart transformation to a Petri network with its realization as principal circuit. The features of the Moore FSM circuit realization on FPGA are considered and the method of its synthesis on the base of flow-chart is offered. An example of proposed method application is given.
|
| first_indexed | 2025-12-07T13:18:14Z |
| format | Article |
| fulltext |
Комп’ютерні засоби, мережі та системи. 2006, № 5 67
A. A. Barkalov, A. A. Krasichkov,
A. V. Matvienko
THE REALIZATION OF THE
MOORE AUTOMATION ON
FPGA AS A PETRI NETWORK
The method of Moore FSM as a Pe-
tri network on FPGA is offered. The
method is based on the flow-chart
transformation to a Petri network
with its realization as principal cir-
cuit. The features of the Moore FSM
circuit realization on FPGA are
considered and the method of its
synthesis on the base of flow-chart is
offered. An example of proposed
method application is given.
Предложен метод синтеза авто-
матов Мура в виде сети Петри на
микросхемах FPGA. Метод осно-
ван на преобразовании исходной
граф-схемы алгоритма к сети
Петри с дальнейшей ее реализа-
цией в виде принципиальной схе-
мы. Рассмотрены особенности
реализации схемы автомата на
микросхемах FPGA. Предложена
методика ее синтеза по граф-
схеме алгоритма. Приведен при-
мер применения предложенного
метода.
А.А. Баркалов, А.А. Красичков,
А.В. Матвиенко, 2006
УДК 681.324
А.А. БАРКАЛОВ, А.А. КРАСИЧКОВ,
А.В. МАТВИЕНКО
РЕАЛИЗАЦИЯ АВТОМАТА МУРА
НА FPGA В ВИДЕ СЕТИ ПЕТРИ
В настоящее время для реализации схем
управляющих автоматов (УА) применяются
программируемые логические интегральные
схемы (ПЛИС) с архитектурой FPGA [1].
Ввиду особенностей функционального бази-
са FPGA, предпочтение отдается УА с жест-
кой логикой [2]. При этом актуальными яв-
ляются задачи минимизации логической
схемы и повышение быстродействия УА.
На рис. 1 показана базовая структура УА
Мура, в которую входят регистр состояния
(Рг), комбинационные схемы для формиро-
вания функций возбуждения (Р1) и выходных
сигналов (Р2).
P
1
Pr
P
2
{X}
{Y}
D
T
Reset
CLK
Start
РИС. 1. Структурная схема канонического автомата
Мура
А.А. БАРКАЛОВ, А.А. КРАСИЧКОВ, А.В. МАТВИЕНКО
Комп’ютерні засоби, мережі та системи. 2006, № 5 68
Традиционно синтез УА выполняется по указанной базовой структуре, а
оптимизация схемы достигается за счет ряда методов, таких как оптимальное
кодирование состояний, выделение подуровней в схемах Р1 и Р2, трансформация
кодов объектов [3,4].
Общая структура FPGA включает множество идентичных конфигурируе-
мых логических блоков (КЛБ) с R входами, которые могут реализовать произ-
вольную булеву функцию R переменных. В зависимости от модели микросхемы
FPGA 2,5R [2]. При реализации традиционных структур УА число перемен-
ных значительно больше, что приводит к невыгодно громоздкой схеме на вен-
тильном уровне и снижению быстродействия.
К выходу каждого КЛБ подключен DC-триггер, что позволяет наиболее оп-
тимально реализовывать на FPGA схемы с древовидной структурой и большим
числом состояний, в частности сети Петри [5].
Простой сетью Петри называется набор N = (S, T, M, P, F), где
1) S = {s1,…, sN} – множество мест;
2) T = {t1,…, tN} – множество переходов, таких, что S T = 0;
3) M = {m1,…, mN} – множество меток;
4) P = {p1,…, pN} – множество событий;
5) F STS – отношение инцидентности, такое, что
' " ' " ' " ' "
а) ( , , ), ( , , ) : ( , , ) ( , , ) ;
1 1 1 2 2 2 1 1 1 2 2 2 1 2
' "
б){ | , , } .
S t S S t S F S t S S t S t t
t S t S F T
Условия в п. 5 свидетельствуют о том, что для каждого перехода tT суще-
ствует единственный элемент
' "
, ,S t S F , задающий для него входное
множество мест
'S и выходное множество
"S .
Модель сети Петри является принципиально асинхронной, служит для ото-
бражения и анализа причинно-следственных связей в системе. Для привязки к
определенным моментам времени тех или иных переходов используются собы-
тия [6]. Сеть Петри имеет наглядную форму представления в виде графа, кото-
рый включает четыре базовых элемента: позиции (места), переходы, дуги и мет-
ки. На рис. 2 показан пример графа, задающего простую сеть Петри с тремя мес-
тами, тремя метками и двумя переходами.
Исходя из этого, любая граф-схема алгоритма (ГСА ) для УА является част-
ным случаем сети Петри. При этом существует только одна метка, соответст-
вующая текущему состоянию автомата. Множество мест S соответствует мно-
жеству состояний автомата, множество переходов t – множеству условных вер-
шин, множество событий – множеству наборов управляющих сигналов.
Таким образом, произвольный УА может быть представлен в виде сети Пет-
ри. В том случае, если события возникают при наличии метки в определенном
месте, сеть отображает поведение УА Мура. Если события формируются во
время перемещений меток между местами, в зависимости от переходов, то сеть
отображает поведение автомата Мили.
РЕАЛИЗАЦИЯ АВТОМАТА МУРА НА FPGA В ВИДЕ СЕТИ ПЕТРИ
Комп’ютерні засоби, мережі та системи. 2006, № 5 69
t
1
t
2
S
1
S
3
S
2
m
1
m
2
m
3
РИС. 2. Пример простой сети Петри
Рассмотрим реализацию УА Мура в виде сети Петри, заданного ГСАГ на
рис. 3.
Begin
Start
y
1
y
2
0
1
x
1
01
x
2
10
y
3
x
2
1
0
y
2
End
a
0
a
1
a
2
a
3
a
0
РИС. 3. Исходная граф-схема алгоритма Г
Start
А.А. БАРКАЛОВ, А.А. КРАСИЧКОВ, А.В. МАТВИЕНКО
Комп’ютерні засоби, мережі та системи. 2006, № 5 70
Данная ГСА соответствует сети Петри с четырьмя состояниями – a0-a3, че-
тырьмя переходами с тремя условиями – Start,x1,x2, и тремя событиями – y1-y3,
(рис. 4).
a
0
a
1
a
2
a
3
Start
x
1 x
2
x
2y
1,
y
2
y
3
y
2
0
1
0
1
1
0
1
0
РИС. 4. Сеть Петри для ГСАГ
Сеть функционирует следующим образом. В исходном состоянии метка на-
ходится в месте a0. При этом не формируется никаких событий. Данное место
является ждущей вершиной. Переход метки в место a1 осуществляется через
первый переход только после выполнения условия Start=1. Пока метка находит-
ся в месте a1, действительны события y1 и y2. Из a1, благодаря двум переходам
(по x1 и x2), возможны три варианта перемещений – в a1, a2 или a3. Месту a2 соот-
ветствует событие y3, а месту a3 – событие y2. Данная сеть не имеет тупиковых
состояний, поскольку соответствует замкнутому алгоритму УА.
Для реализации схемы данного автомата на FPGA необходимо заменить
компоненты сети (рис. 4) их функциональными аналогами. Если в качестве мес-
та (состояния) использовать DC-триггер, то меткой будет служить сигнал логи-
ческой единицы, записанной в триггер текущего состояния. Множество входов в
каждое состояние объединяется элементом “ИЛИ” и подается на соответствую-
щий триггер. Функцию перехода выполняет обычный демультиплексор на два
выхода, управляемый одним условием. События (управляющие сигналы) фор-
мируются как логическое “ИЛИ” выходов соответствующих им состояний
(триггеров). Дугам, соединяющим места и переходы, соответствуют обычные
электрические соединения. На рис. 5 показана функциональная схема УА, полу-
ченная из сети Петри для ГСАГ.
Start
РЕАЛИЗАЦИЯ АВТОМАТА МУРА НА FPGA В ВИДЕ СЕТИ ПЕТРИ
Комп’ютерні засоби, мережі та системи. 2006, № 5 71
1
1
D
C
R
T
Q
D
C
R
T
Q DMX
x
1
1
0
DMX
x
2
0
1 D
C
R
T
Q
1 D
C
R
T
Q DMX
x
2
0
1
CLK Reset CLK Reset
CLK Reset
CLK Reset
a
0 a
1 a
3
a
2
Start
y
1
1 y
2
y
3
РИС. 5. Функциональная схема УА Мура по ГСАГ
Схема работает следующим образом. По сигналу Reset = ”1” все триггеры
сбрасываются в “0”, что соответствует начальному состоянию автомата a0, по-
скольку при этом не вырабатывается никаких управляющих сигналов. При по-
явлении сигнала Start, в триггер a0 по переднему фронту синхросигнала CLK
записывается логическая “1”, что разрешает дальнейшее функционирование
схемы УА по заданному алгоритму. Такая реализация позволяет не использовать
демультиплексор, который соответствует на рис. 4 переходу с условием Start.
В каждом такте CLK в один из триггеров записывается “1”, что соответствует
переходу из одного состояние в другое. При этом в триггер, из которого проис-
ходит запись “1”, записывается “0”. Для обеспечения корректной работы схемы
сигнал Start должен иметь длительность не более одного такта и вырабатываться
один раз при запуске УА.
Далее полученная схема описывается на языке VHDL для последующего ав-
томатического синтеза и окончательной имплементации на FPGA [2].
Преимущества такой реализации УА на FPGA:
- идентичность блоков, регулярность структуры автомата;
- минимальная комбинационная часть, распределенная по всей схеме;
А.А. БАРКАЛОВ, А.А. КРАСИЧКОВ, А.В. МАТВИЕНКО
Комп’ютерні засоби, мережі та системи. 2006, № 5 72
- небольшое число входов комбинационных схем, не зависящее от числа со-
стояний автомата;
- высокое быстродействие автомата;
- отсутствие синтеза.
Удобство проектирования и исследования таких УА заключается в том, что
можно автоматизировать генерацию конечного VHDL-кода по исходной ГСА.
Синтез, оптимизация и оценка параметров полученной реализации выполняется
САПР. При имплементации данной схемы УА на FPGA серии Spartan-II исполь-
зовано 5 четырехвходовых КЛБ и 4 триггера (в составе КЛБ). Максимальная за-
держка сигналов в схеме составила 7,3 нс. При реализации данной логической
схемы УА на других семействах FPGA возможны другие показатели быстродей-
ствия и затрат.
1. Кнышев Д.А., Кузелин М.О. ПЛИС фирмы Xilinx: структура и применение. – М.: ДОДЭ-
КА, 2000. – 270 с.
2. Грушвицкий Р.И., Мурсаев А.Х., Угрюмов Е.П. Проектирование систем на микросхемах
программируемой логики. – СПб.: БХВ-Петербург, 2002. – 608 с.
3. Баркалов А.А., Палагин А.В. Синтез микропрограммных устройств управления. Киев:
Ин-т кибернетики им. В.М. Глушкова НАН Украины, 1997 – 135 с.
4. Баркалов А.А. Синтез устройств управления на программируемых логических устройст-
вах. – Донецк: ДонНТУ, 2002 – 262 с.
5. Питерсон Дж. Теория сетей Петри и моделирование систем. – М.: Мир, 1984 – 368 с.
6. Котов В.Е. Сети Петри. – М.: Наука, 1984 – 263 с.
Получено 28.02.2006
|
| id | nasplib_isofts_kiev_ua-123456789-6458 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1817-9908 |
| language | Russian |
| last_indexed | 2025-12-07T13:18:14Z |
| publishDate | 2006 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Баркалов, А.А. Красичков, А.А. Матвиенко, А.В. 2010-03-04T10:55:52Z 2010-03-04T10:55:52Z 2006 Реализация автомата Мура на FPGA в виде сети Петри / А.А. Баркалов, А.А. Красичков, А.В. Матвиенко // Комп’ютерні засоби, мережі та системи. — 2006. — № 5. — С. 67-72. — Бібліогр.: 6 назв. — рос. 1817-9908 https://nasplib.isofts.kiev.ua/handle/123456789/6458 681.324 Предложен метод синтеза автоматов Мура в виде сети Петри на микросхемах FPGA. Метод основан на преобразовании исходной граф-схемы алгоритма к сети Петри с дальнейшей ее реализацией в виде принципиальной схемы. Рассмотрены особенности реализации схемы автомата на микросхемах FPGA. Предложена методика ее синтеза по граф-схеме алгоритма. Приведен пример применения предложенного метода. The method of Moore FSM as a Petri network on FPGA is offered. The method is based on the flow-chart transformation to a Petri network with its realization as principal circuit. The features of the Moore FSM circuit realization on FPGA are considered and the method of its synthesis on the base of flow-chart is offered. An example of proposed method application is given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Реализация автомата Мура на FPGA в виде сети Петри The realization of the Moore automation on fpga as a Petri network Article published earlier |
| spellingShingle | Реализация автомата Мура на FPGA в виде сети Петри Баркалов, А.А. Красичков, А.А. Матвиенко, А.В. |
| title | Реализация автомата Мура на FPGA в виде сети Петри |
| title_alt | The realization of the Moore automation on fpga as a Petri network |
| title_full | Реализация автомата Мура на FPGA в виде сети Петри |
| title_fullStr | Реализация автомата Мура на FPGA в виде сети Петри |
| title_full_unstemmed | Реализация автомата Мура на FPGA в виде сети Петри |
| title_short | Реализация автомата Мура на FPGA в виде сети Петри |
| title_sort | реализация автомата мура на fpga в виде сети петри |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6458 |
| work_keys_str_mv | AT barkalovaa realizaciâavtomatamuranafpgavvidesetipetri AT krasičkovaa realizaciâavtomatamuranafpgavvidesetipetri AT matvienkoav realizaciâavtomatamuranafpgavvidesetipetri AT barkalovaa therealizationofthemooreautomationonfpgaasapetrinetwork AT krasičkovaa therealizationofthemooreautomationonfpgaasapetrinetwork AT matvienkoav therealizationofthemooreautomationonfpgaasapetrinetwork |