Смешанное кодирование наборов микроопераций в микропрограммном автомате
Предложен метод уменьшения количества LUT в схеме микропрограммного
 автомата Мили, реализуемого в базисе FPGA. Метод основан
 на удалении из наборов микроопераций некоторых элементов для реализации
 на блоке памяти EMB. Такой подход позволяет уменьшить число
 уровней...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2020 |
| Автори: | , , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2020
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/190375 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Смешанное кодирование наборов микроопераций в микропрограммном автомате / А.А. Баркалов, Л.А. Титаренко, А.В. Баев, А.В. Матвиенко // Кибернетика и системный анализ. — 2020. — Т. 56, № 3. — С. 3–16. — Бібліогр.: 27 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860252789290041344 |
|---|---|
| author | Баркалов, А.А. Титаренко, Л.А. Баев, А.В. Матвиенко, А.В. |
| author_facet | Баркалов, А.А. Титаренко, Л.А. Баев, А.В. Матвиенко, А.В. |
| citation_txt | Смешанное кодирование наборов микроопераций в микропрограммном автомате / А.А. Баркалов, Л.А. Титаренко, А.В. Баев, А.В. Матвиенко // Кибернетика и системный анализ. — 2020. — Т. 56, № 3. — С. 3–16. — Бібліогр.: 27 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Предложен метод уменьшения количества LUT в схеме микропрограммного
автомата Мили, реализуемого в базисе FPGA. Метод основан
на удалении из наборов микроопераций некоторых элементов для реализации
на блоке памяти EMB. Такой подход позволяет уменьшить число
уровней логики и межсоединений в схеме, реализуемой на элементах LUT.
Предложен алгоритм разбиения множества микроопераций. Приведен пример
синтеза и показаны результаты проведенных исследований.
Запропоновано метод зменшення кількості LUT у схемі мікропрограмного автомата Мілі, який реалізується в базисі FPGA. Метод ґрунтується на вилученні з наборів мікрооперацій деяких елементів для реалізації на блоці пам'яті EMB. Такий підхід дає змогу зменшити кількість рівнів логіки і міжз'єднань у схемі, яка реалізується на елементах LUT. Запропоновано алгоритм розбиття множини мікрооперацій. Наведено приклад синтезу і результати проведених досліджень.
A method is proposed for reducing the number of LUTs in the circuit of a microprogrammed Mealy FSM. The method is based on elimination of some elements from the sets of microoperations for their implementation by EMB. This approach reduces logic levels and interconnections for a circuit implemented with LUTs. An algorithm is proposed for searching a partition of the set of micro-operations. An example of synthesis is given as well as results of the investigations.
|
| first_indexed | 2025-12-07T18:45:02Z |
| format | Article |
| fulltext |
À.À. ÁÀÐÊÀËÎÂ, Ë.À. ÒÈÒÀÐÅÍÊÎ, À.Â. ÁÀÅÂ, À.Â. ÌÀÒÂÈÅÍÊÎ
ÓÄÊ 004.274 ÑÌÅØÀÍÍÎÅ ÊÎÄÈÐÎÂÀÍÈÅ
ÍÀÁÎÐÎÂ ÌÈÊÐÎÎÏÅÐÀÖÈÉ
 ÌÈÊÐÎÏÐÎÃÐÀÌÌÍÎÌ ÀÂÒÎÌÀÒÅ
Àííîòàöèÿ. Ïðåäëîæåí ìåòîä óìåíüøåíèÿ êîëè÷åñòâà LUT â ñõåìå ìèê-
ðîïðîãðàììíîãî àâòîìàòà Ìèëè, ðåàëèçóåìîãî â áàçèñå FPGA. Ìåòîä îñíî-
âàí íà óäàëåíèè èç íàáîðîâ ìèêðîîïåðàöèé íåêîòîðûõ ýëåìåíòîâ äëÿ ðåà-
ëèçàöèè íà áëîêå ïàìÿòè EMB. Òàêîé ïîäõîä ïîçâîëÿåò óìåíüøèòü ÷èñëî
óðîâíåé ëîãèêè è ìåæñîåäèíåíèé â ñõåìå, ðåàëèçóåìîé íà ýëåìåíòàõ LUT.
Ïðåäëîæåí àëãîðèòì ðàçáèåíèÿ ìíîæåñòâà ìèêðîîïåðàöèé. Ïðèâåäåí ïðè-
ìåð ñèíòåçà è ïîêàçàíû ðåçóëüòàòû ïðîâåäåííûõ èññëåäîâàíèé.
Êëþ÷åâûå ñëîâà: àâòîìàò Ìèëè, ñèíòåç, FPGA, LUT, EMB, êîäèðîâàíèå
íàáîðîâ ìèêðîîïåðàöèé.
ÂÂÅÄÅÍÈÅ
Ïðè ïðîåêòèðîâàíèè öèôðîâûõ ñèñòåì íà ÑÁÈÑ àêòóàëüíîé çàäà÷åé ÿâëÿåòñÿ
óìåíüøåíèå ïëîùàäè êðèñòàëëà, çàíèìàåìîé ñõåìîé óñòðîéñòâà óïðàâëåíèÿ
(ÓÓ) [1, 2]. Ðåøåíèå ýòîé çàäà÷è ïîçâîëÿåò óëó÷øèòü òàêèå õàðàêòåðèñòèêè
ÓÓ, êàê áûñòðîäåéñòâèå è ïîòðåáëåíèå ýíåðãèè [3]. Ìåòîäû åå ðåøåíèÿ çàâè-
ñÿò îò ìîäåëè ÓÓ è èñïîëüçóåìîãî ýëåìåíòíîãî áàçèñà [4, 5].
Ïðè ïðîåêòèðîâàíèè ÓÓ [6] ÷àñòî ïðèìåíÿþò ìîäåëü ìèêðîïðîãðàììíîãî àâ-
òîìàòà (ÌÏÀ) Ìèëè, â êîòîðîì âûõîäíûå ïåðåìåííûå (ìèêðîîïåðàöèè) çàâèñÿò îò
âõîäíûõ (ëîãè÷åñêèõ óñëîâèé) è âíóòðåííèõ ïåðåìåííûõ, êîäèðóþùèõ ñîñòîÿ-
íèÿ [7]. Ýòî ïðèâîäèò ê ìíîãîóðîâíåâûì ñõåìàì ñ áîëüøèì êîëè÷åñòâîì ìåæñîå-
äèíåíèé, ÷òî îòðèöàòåëüíî âëèÿåò íà áûñòðîäåéñòâèå è ýíåðãîïîòðåáëåíèå, îñîáåí-
íî ïðè ðåàëèçàöèè ñõåì ÌÏÀ â áàçèñå FPGA (field programmable gate arrays) [8, 9].
Ìèêðîñõåìû FPGA øèðîêî èñïîëüçóþòñÿ ïðè ïðîåêòèðîâàíèè ñîâðåìåí-
íûõ öèôðîâûõ ñèñòåì [10]. Ïîýòîìó àêòóàëüíà ðàçðàáîòêà ìåòîäîâ ñèíòåçà, îðè-
åíòèðîâàííûõ íà ýòîò áàçèñ, îñîáåííî ìåòîäîâ ñèíòåçà ÌÏÀ ñ íåðåãóëÿðíîé
ñòðóêòóðîé ñõåì [7, 11], è îòëè÷àþùèõñÿ îò ìåòîäîâ, îðèåíòèðîâàííûõ íà ðåãó-
ëÿðíûå ñõåìû ñóììàòîðîâ, ñ÷åò÷èêîâ, óìíîæèòåëåé è ò.ä. [6].
 íàñòîÿùåé ðàáîòå ïðåäëîæåí ìåòîä óìåíüøåíèÿ àïïàðàòóðíûõ çàòðàò
â ñõåìå ÌÏÀ Ìèëè, ðåàëèçóåìîé â áàçèñå FPGA. Äëÿ çàäàíèÿ àâòîìàòà èñïîëü-
çóåòñÿ ÿçûê ãðàô-ñõåì àëãîðèòìîâ (ÃÑÀ) [7].
1. ÑÈÍÒÅÇ ÑÕÅÌÛ ÌÏÀ ÌÈËÈ ÏÎ ÃÑÀ
Ðàññìîòðèì ïðèìåð àâòîìàòà, îïèñàííîãî ÃÑÀ �1, êîòîðàÿ íà ðèñ. 1 îòìå÷åíà
ñîñòîÿíèÿìè àâòîìàòà Ìèëè ïî ïðàâèëàì [7]. Èç ÃÑÀ �1 ìîæíî ïîëó÷èòü ìíî-
æåñòâà âíóòðåííèõ ñîñòîÿíèé A a a M� { }1, ,� , M � 7, ëîãè÷åñêèõ óñëîâèé
X x xL� { }1, ,� , L � 5, è ìèêðîîïåðàöèé Y y yN� { }1, ,� , N � 9.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 3
© À.À. Áàðêàëîâ, Ë.À. Òèòàðåíêî, À.Â. Áàåâ, À.Â. Ìàòâèåíêî, 2020
Äëÿ ñèíòåçà ñõåìû ÌÏÀ íåîáõîäèìî ïîëó÷èòü íåêîòîðûå ñèñòåìû áóëåâûõ
ôóíêöèé [6, 7]. Äëÿ ýòîãî ñëåäóåò çàêîäèðîâàòü ñîñòîÿíèÿ a Am � äâîè÷íûìè êî-
äàìè K am( ) ðàçðÿäíîñòè R . Ïðè ýòîì èñïîëüçóþòñÿ âíóòðåííèå ïåðåìåííûå, îá-
ðàçóþùèå ìíîæåñòâî T T TR� { }1, ,� . Êîäû K am( ) õðàíÿòñÿ â ñïåöèàëüíîì ðå-
ãèñòðå RG , ñîäåðæèìîå êîòîðîãî ìîæíî èçìåíèòü ñ ïîìîùüþ ôóíêöèé âîçáóæäå-
íèÿ ïàìÿòè � � { }D DR1, ,� . Êàê ïðàâèëî, òðèããåðû RG èìåþò èíôîðìàöèîííûå
âõîäû òèïà D [10]. Âî ìíîãèõ ïðàêòè÷åñêèõ ñëó÷àÿõ ïàðàìåòð R M� � �log 2 .
Çäåñü âûðàæåíèå � �a îáîçíà÷àåò áëèæàéøåå öåëîå, ðàâíîå a , åñëè a öåëîå èëè
áîëüøåå, ÷åì a , åñëè a äðîáíîå. Äëÿ ÃÑÀ �1 èìååì R � 3 è ìíîæåñòâà
T T T T� { }1 2 3, , è � � { }D D D1 2 3, , .
Ñõåìà ÌÏÀ Ìèëè çàäàåòñÿ äâóìÿ ñèñòåìàìè ôóíêöèé:
� �� ( , )T X , (1)
Y Y T X� ( , ). (2)
4 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
Start
End
1
x1
x2
1 0
0
x2
1 0
x3
1 0
x4
1 0
a1
a2
y3 y4 y6y1 y2 y3 y2 y7 y4 y8
y3 y5 y6y1 y4 y6
y3 y5 y9
a3
x1
1 0
x4
1 0
y1 y2 y7
y2 y3 y6
a5
x5
1 0
y2 y3y1 y4 y8
a4
y2 y7 y6
1
x3
x4
1
0
x5
1
a1
x1
1
00
a7
a6
y1 y3 y4
y1 y4
y1 y6y1 y6
y3 y5 y6 y9
0
Ðèñ. 1. Èñõîäíàÿ ÃÑÀ �1
—
Äëÿ ïîëó÷åíèÿ ñèñòåì (1), (2) íåîáõîäèìî ïîñòðîèòü ïðÿìóþ ñòðóêòóðíóþ
òàáëèöó (ÏÑÒ) àâòîìàòà Ìèëè [7] (òàáë. 1), ãäå am — èñõîäíîå ñîñòîÿíèå;
K am( ) — êîä ñîñòîÿíèÿ a Am � ; as — ñîñòîÿíèå ïåðåõîäà; K as( ) — êîä ñîñòîÿ-
íèÿ a As � ; X h — êîíúþíêöèÿ ëîãè÷åñêèõ óñëîâèé, îïðåäåëÿþùàÿ ïåðåõîä
� �a am s, ; Yh — íàáîð ìèêðîîïåðàöèé (ÍÌÎ), ôîðìèðóåìûé íà ïåðåõîäå
� �a am s, ; �h — íàáîð ôóíêöèé âîçáóæäåíèÿ ïàìÿòè, ïðèíèìàþùèõ çíà÷åíèå 1
äëÿ çàïèñè â RG êîäà K as( ) ; h — íîìåð ïåðåõîäà, h H�{ }1, ,� , H �19. Äëÿ áå-
çóñëîâíûõ ïåðåõîäîâ X h �1.
Çàêîäèðóåì ñîñòîÿíèÿ äëÿ îïèñûâàåìîãî ïðèìåðà òðèâèàëüíûì îáðàçîì:
K a K a( ) , , ( )1 7000 110� �� . Ýòè êîäû ïðèâåäåíû â ÏÑÒ ÌÏÀ Ìèëè (ñì. òàáë. 1).
Ôóíêöèè (1), (2) çàâèñÿò îò òåðìîâ Fh , ñîîòâåòñòâóþùèõ ñòðîêàì ÏÑÒ.
Òåðì Fh îïðåäåëÿåòñÿ ôîðìóëîé F A Xh m h� , h H�{ , , }1 � , ãäå Am — êîíúþí-
êöèÿ âíóòðåííèõ ïåðåìåííûõ êîäà K am( ) èç ñòðîêè ÏÑÒ.
Èç òàáë. 1 ìîæíî, íàïðèìåð, ïîëó÷èòü ñëåäóþùèå ìèíèìèçèðîâàííûå
ôóíêöèè:
D T T T x T T T T T T1 1 2 3 1 1 2 3 1 2 3� � � ; y T T T x T T T9 1 2 3 2 1 2 3� � .
Ñèñòåìû (1), (2) îïðåäåëÿþò
ñòðóêòóðíóþ ñõåìó ÌÏÀ Ìèëè U 1
(ðèñ. 2). Çäåñü áëîê ôóíêöèé âîçáóæ-
äåíèÿ ïàìÿòè ðåàëèçóåò ôóíêöèè (1),
à áëîê ìèêðîîïåðàöèé — ñèñòåìó (2).
Ïî èìïóëüñó Start â ðåãèñòð RG çàïè-
ñûâàåòñÿ êîä íà÷àëüíîãî ñîñòîÿíèÿ
a A1 � . Èìïóëüñ Clock ðàçðåøàåò èç-
ìåíåíèå ñîäåðæèìîãî RG.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 5
Ò à á ë è ö à 1. Ïðÿìàÿ ñòðóêòóðíàÿ òàáëèöà ÌÏÀ Ìèëè
am K am( ) as K as( ) Xh Yh Ôh h
a1 000
a2 001 x x1 2 y y y1 2 3 D3 1
a2 001 x x1 2 y y y3 4 6 D3 2
a2 001 x x1 3 y y2 7 D3 3
a2 001 x x1 3 y y4 8 D3 4
a2 001
a3 010 x2 y y y3 5 9 D2 5
a3 010 x x3 4 y y y1 4 6 D2 6
a3 010 x x3 4 y y y3 5 6 D2 7
a3 010
a4 011 x1 y y y2 3 6 D D2 3 8
a5 100 x x1 4 y y y1 2 7 D1 9
a5 100 x x x1 4 5 y y y2 6 7 D1 10
a5 100 x x x1 4 5 y y2 3 D1 11
a4 011 a5 100 1 y y y1 4 8 D1 12
a5 100
a7 110 x x3 4 y y1 4 D D1 2 13
a6 101 x x3 4 y1 D D1 3 14
a6 101 x x3 5 y6 D D1 3 15
a6 101 x x x3 5 1 y y1 6 D D1 3 16
a6 101 x x x3 5 1 — D D1 3 17
a6 101 a1 000 1 y y y1 3 4 — 18
a7 110 a1 000 1 y y y y3 5 6 9 — 19
X
Start
Clock
T
Ô
Y
Áëîê ôóíêöèé
âîçáóæäåíèÿ ïàìÿòè
Áëîê
ìèêðîîïåðàöèé
RG
Ðèñ. 2. Ñòðóêòóðíàÿ ñõåìà ÌÏÀ Ìèëè U1
2. ÐÅÀËÈÇÀÖÈß ÑÕÅÌÛ ÌÏÀ Â ÁÀÇÈÑÅ FPGA
Äëÿ ðåàëèçàöèè ÌÏÀ ìîæíî èñïîëüçîâàòü ñëåäóþùèå êîìïîíåíòû FPGA:
ýëåìåíòû òàáëè÷íîãî òèïà LUT (look-up table); âñòðîåííûå áëîêè ïàìÿòè EMB
(embedded memory blocks); ïðîãðàììèðóåìûå òðèããåðû; ìàòðèöó ïðîãðàììèðó-
åìûõ ìåæñîåäèíåíèé [12, 13]. Ýëåìåíòû LUT — ýòî ÎÇÓ, èìåþùèå S L âõî-
äîâ è îäèí âûõîä. Îäèí LUT ìîæåò ðåàëèçîâàòü ïðîèçâîëüíóþ áóëåâó ôóíê-
öèþ îò S L àðãóìåíòîâ. Âûõîäû LUT ëèáî ñâÿçàíû ñ âõîäàìè òðèããåðîâ ñ ïî-
ìîùüþ ñïåöèàëüíûõ ìóëüòèïëåêñîðîâ [14], ëèáî íå ñâÿçàíû ñ íèìè.
Áëîê EMB — ýòî ðåêîíôèãóðèðóåìîå ÎÇÓ, èìåþùåå S A âõîäîâ è tF âûõî-
äîâ. Åìêîñòü V0 áëîêà EMB ÿâëÿåòñÿ êîíñòàíòîé, V t
S
F
A
0 2� . Êîíôèãóðàöèè
áëîêà EMB îïðåäåëÿþòñÿ ïàðàìè � �S tA F, . Îáû÷íî V0 32� Ê, è äëÿ òàêîé åì-
êîñòè âîçìîæíû ñëåäóþùèå êîíôèãóðàöèè: 32Ê 1, 16Ê 2, 8Ê 4, 4Ê 8, 2Ê 16,
1Ê 32 è 512 64 [15].
Äëÿ ðåàëèçàöèè ñõåì ðåãèñòðîâ â áàçèñå FPGA èñïîëüçóþòñÿ ïðîãðàììèðóå-
ìûå òðèããåðû. Ìàòðèöà ìåæñîåäèíåíèé ïðåäíàçíà÷åíà äëÿ îðãàíèçàöèè ñâÿçåé
ìåæäó ýëåìåíòàìè ñõåìû ÌÏÀ.
Îáîçíà÷èì LUTer ñõåìó, ñîñòîÿùóþ èç ýëåìåíòîâ LUT, à EMBer — ñõåìó, ñî-
ñòîÿùóþ èç áëîêîâ EMB. Ñóùåñòâóþò äâå òðèâèàëüíûå ñõåìû àâòîìàòàU 1 (ðèñ. 3).
Íà ðèñ. 3, à ñèñòåìû (1), (2) ðåàëèçóþòñÿ íà ýëå-
ìåíòàõ LUT. Ðåãèñòð RG ðàñïðåäåëåí ìåæäó ýòèìè
ýëåìåíòàìè. Îäíàêî LUT èìåþò îãðàíè÷åííîå ÷èñëî
âõîäîâ (S L
6) [14]. Àíàëèç áèáëèîòåêè [16] ïîêàçû-
âàåò, ÷òî ôóíêöèè (1), (2) ìîãóò çàâèñåòü îò 20 è áîëåå
àðãóìåíòîâ. Òàêîé äèñáàëàíñ ïðèâîäèò ê íåîáõîäè-
ìîñòè ïðèìåíÿòü ìåòîäû ôóíêöèîíàëüíîé äåêîìïîçè-
öèè [17, 18], â ðåçóëüòàòå ÷åãî óâåëè÷èâàåòñÿ ÷èñëî
ýëåìåíòîâ, êîëè÷åñòâî óðîâíåé ëîãèêè è ìåæñîåäèíå-
íèé (ïî ñðàâíåíèþ ñ îäíîóðîâíåâûìè ñõåìàìè).
Íà ðèñ. 3, á ñèñòåìû (1), (2) ðåàëèçóþòñÿ íà áëî-
êàõ EMB. Ýòè áëîêè äîïóñêàþò âîçìîæíîñòü ñèíõðî-
íèçàöèè [14], ïîýòîìó ðåãèñòðà RG â ÿâíîì âèäå çäåñü
íå ñóùåñòâóåò. Àíàëèç áèáëèîòåêè [16] ïîêàçàë, ÷òî
äëÿ 82 % âñåõ ïðèìåðîâ äîñòàòî÷íî îäíîãî áëîêà
EMB.  îñòàëüíûõ ñëó÷àÿõ ýòî ÷èñëî âàðüèðóåòñÿ îò
äâóõ äî âîñüìè. Êàê îòìå÷àåòñÿ â [19, 20], áëîêè EMB
øèðîêî èñïîëüçóþòñÿ äëÿ ðåàëèçàöèè ñõåì ðàçëè÷íûõ
áëîêîâ öèôðîâûõ ñèñòåì è äëÿ ðåàëèçàöèè ÓÓ ìîæåò áûòü âûäåëåí òîëüêî îäèí
áëîê EMB [13]. Ïîýòîìó äëÿ äîñòàòî÷íî ñëîæíûõ ÌÏÀ öåëåñîîáðàçíî ñîâìåñòíîå
èñïîëüçîâàíèå LUT è EMB. Êàê ïðàâèëî, LUT ïðèìåíÿþòñÿ äëÿ ðåàëèçàöèè ñõå-
ìû çàìåíû ëîãè÷åñêèõ óñëîâèé [7, 17]. Ýòî ïðèâîäèò ê ÌÏÀ U 2 (ðèñ. 4).
 àâòîìàòå U 2 (ñì. ðèñ. 4) áëîê LUTer ðåàëèçóåò ñèñòåìó ôóíêöèé
P P T X� ( , ). Ïåðåìåííûå p Pg � çàìåíÿþò ëîãè÷åñêèå óñëîâèÿ x Xi � . Ïðè ýòîì
| |P L�� , ÷òî ïîçâîëÿåò óìåíüøèòü êîëè÷åñ-
òâî áëîêîâ EMB ïî ñðàâíåíèþ ñ ýêâèâàëåí-
òíûì àâòîìàòîìU 1. Áóäåì íàçûâàòü àâòîìàòû
ýêâèâàëåíòíûìè, åñëè îíè ñèíòåçèðóþòñÿ ïî
îäíîé è òîé æå ÃÑÀ �.
Îòìåòèì, ÷òî äëÿ ðåàëèçàöèè ñõåìû
LUTer ìîæåò ïîíàäîáèòüñÿ ïðèìåíåíèå ôóíê-
öèîíàëüíîé äåêîìïîçèöèè. Êðîìå òîãî, ïðè
6 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
Ðèñ. 3. Òðèâèàëüíûå ðåàëèçà-
öèè àâòîìàòà U1
Start
Clock
T
X
Y
LUTer
Start
Clock
T
X
Y
EMBer
à
á
X
Start
Clock
T
EMBer
YLUTer
P
Ðèñ. 4. Ñòðóêòóðíàÿ ñõåìà àâòîìàòà U2
îãðàíè÷åííîì êîëè÷åñòâå EMB, äîñòóïíûõ äëÿ ðåàëèçàöèè ñõåìû ÌÏÀ, ÷àñòü
ôóíêöèé y Yn � è Dr �� íåîáõîäèìî ðåàëèçîâàòü íà ýëåìåíòàõ LUT.
Ìåòîä çàìåíû ëîãè÷åñêèõ óñëîâèé îòíîñèòñÿ ê ìåòîäàì ñòðóêòóðíîé äåêîì-
ïîçèöèè [18]. Â íàñòîÿùåé ðàáîòå äëÿ ðåàëèçàöèè ñõåìû ÌÏÀ ïðåäëàãàåòñÿ èñ-
ïîëüçîâàòü ìåòîä êîäèðîâàíèÿ ÍÌÎ è ìîäèôèöèðîâàòü èçâåñòíûé ïîäõîä [17]
äëÿ óìåíüøåíèÿ ÷èñëà ýëåìåíòîâ LUT â ñõåìå àâòîìàòà.
3. ÎÑÍÎÂÍÀß ÈÄÅß ÏÐÅÄËÀÃÀÅÌÎÃÎ ÌÅÒÎÄÀ
Ïîñòàâèì â ñîîòâåòñòâèå êàæäîìó èç Q íàáîðîâ ìèêðîîïåðàöèé Y Yq � äâîè÷-
íûé êîä K Yq( ) ðàçðÿäíîñòè R QQ � � �log 2 . Äëÿ êîäèðîâàíèÿ ÍÌÎ èñïîëüçóåì
ïåðåìåííûå z Zr � , ãäå | |Z RQ� . Òîãäà ìèêðîîïåðàöèè y Yn � ïðåäñòàâëÿþòñÿ
ñèñòåìîé ôóíêöèé, çàâèñÿùèõ îò ïåðåìåííûõ z Zr � :
Y Y Z� ( ) . (3)
Êàê ïðàâèëî, âûïîëíÿåòñÿ íåðàâåíñòâî Q L R��
, èç ÷åãî ñëåäóåò, ÷òî äëÿ
ðåàëèçàöèè ñèñòåìû (3) òðåáóåòñÿ ãîðàçäî ìåíüøå ýëåìåíòîâ LUT, ÷åì äëÿ ðåà-
ëèçàöèè ñèñòåìû (2). Îäíàêî ïðè ýòîì
íåêîòîðûå ðåñóðñû FPGA íåîáõîäèìî
èñïîëüçîâàòü äëÿ ðåàëèçàöèè ñèñòåìû
Z Z T X� ( , ).
Ïðè êîäèðîâàíèè ÍÌÎ óñòðîéñòâî
óïðàâëåíèÿ ìîæíî ïðåäñòàâèòü êàê
ÌÏÀ U 3 (ðèñ. 5), â êîòîðîì áëîê EMBer
ðåàëèçóåò ôóíêöèè z Zr � è Dr �� (âû-
õîäû áëîêà EMBer ñîîòâåòñòâóþò âíóò-
ðåííèì ïåðåìåííûì ÌÏÀ). Áëîê LUTer
ðåàëèçóåò ñèñòåìó ôóíêöèé (3).
Ïóñòü ðàçðàáîò÷èê ñõåìû ÓÓ èñïîëüçóåò òîëüêî îäèí áëîê EMB.  ýòîì
ñëó÷àå äëÿ ðåàëèçàöèè ìîäåëè U 1 äîëæíî âûïîëíÿòüñÿ óñëîâèå
2 0
L R R N V
( ) , (4)
äëÿ ìîäåëè U 2 — óñëîâèå
2 0
G R R N V
( ) , (5)
à äëÿ ìîäåëè U 3 — óñëîâèå
2 0
L R
QR R V
( ) . (6)
Ðàññìîòðèì ñëó÷àé, êîãäà óñëîâèÿ (4), (5) íàðóøàþòñÿ, à óñëîâèå (6) âûïîë-
íÿåòñÿ. Åñëè, êðîìå òîãî, âûïîëíÿåòñÿ óñëîâèå R SQ L� , òî ìîæíî èñïîëüçîâàòü
ìîäåëü U 3 . Îäíàêî áëîê LUTer ÿâëÿåòñÿ ìíîãîóðîâíåâîé ñõåìîé. Îòìåòèì, ÷òî
ïðè R SQ L� áëîê LUTer ñîñòîèò èç N ýëåìåíòîâ LUT.
Ðàññìîòðèì ñëó÷àé, êîãäà áëîê EMBer ðåàëèçóåòñÿ íà îäíîì áëîêå EMB.
Ïóñòü ïðè âûïîëíåíèè óñëîâèÿ (6) áëîê EMB èìååò êîíôèãóðàöèþ t tF � 1.
Ïóñòü âûïîëíÿåòñÿ ñëåäóþùåå óñëîâèå:
� t Qt R R� �
�1 0( ) . (7)
Îáîçíà÷èì V ìíîæåñòâî ÍÌÎ, êîòîðîå âêëþ÷àåò Yi è Y j òàêèå, ÷òî
Y Y yi j n� �{ }. Òîãäà óäàëåíèå yn èç Yi ïðèâîäèò ê ðàâåíñòâó Y Yi j� , à ÷èñëî
ÍÌÎ ìíîæåñòâà V óìåíüøàåòñÿ íà åäèíèöó. Åñëè I yn( ) — ÷èñëî ïàð ÍÌÎ
� �Y Yj i, òàêèõ, ÷òî óäàëåíèå ÌÎ yn èç íàáîðîâ Y Yi � âåäåò ê ðàâåíñòâó Y Yi j� ,
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 7
X
Start
Clock
T
EMBer YLUTer
Z
Ðèñ. 5. Ñòðóêòóðíàÿ ñõåìà ÌÏÀ U3
òî ýòî ïîçâîëÿåò óìåíüøèòü êîëè÷åñòâî ÍÌÎ
íà I yn( ) . Âñëåäñòâèå óäàëåíèÿ yn ìíîæåñòâî
V ïðåîáðàçóåòñÿ âî ìíîæåñòâî V1, èìåþùåå
Q1 ýëåìåíòîâ, Q Q I yn1 � � ( ) . Äëÿ êîäèðîâà-
íèÿ ÍÌÎ Y Vq � 1 íåîáõîäèìî R1 áèò,
R Q1 2 1� � �log .
Óäàëåíèå yn ìîæåò ïðèâåñòè ê âûïîë-
íåíèþ óñëîâèÿ
R RQ1 � . (8)
Ïðè ýòîì â áëîêå EMB ïîÿâëÿåòñÿ ñâîáîäíûé âûõîä, êîòîðûé èñïîëüçóåòñÿ
äëÿ ãåíåðàöèè ÌÎ yn .
Äàëåå ñëåäóåò íàéòè ÌÎ ym , óäàëåíèå êîòîðîé èç ÍÌÎ Y Vq � 1 ïðèâîäèò
ê ìíîæåñòâó V2 , èìåþùåìó Q2 íàáîðîâ. Äëÿ èõ êîäèðîâàíèÿ íåîáõîäèìî R2 áèò,
R Q2 2 2� � �log .
Âûïîëíåíèå óñëîâèÿ R R1 2� îçíà÷àåò, ÷òî âñëåäñòâèå óäàëåíèÿ ym ïðîèñ-
õîäèò äàëüíåéøåå óìåíüøåíèå ðàçðÿäíîñòè êîäîâ ÍÌÎ. Ýòîò ïðîöåññ ìîæíî
ïðîäîëæàòü äî òåõ ïîð, ïîêà óäàëåíèå ëþáîé èç îñòàâøèõñÿ ÌÎ íå áóäåò ïðèâî-
äèòü ê óìåíüøåíèþ ðàçðÿäíîñòè êîäîâ ÍÌÎ.
Ïóñòü óäàëåííûå ÌÎ îáðàçóþò ìíîæåñòâî YE . Î÷åâèäíî, ÷òî îíè ðåàëèçó-
þòñÿ áëîêîì EMB. Îñòàëüíûå ÌÎ îáðàçóþò ìíîæåñòâî Y Y YL E� \ { } è ãåíåðè-
ðóþòñÿ áëîêîì LUTer.
Ïðåäëàãàåìûé ïîäõîä ïîçâîëÿåò ïîëó÷èòü äâà âèäà êîäîâ. Áëîê EMB ãåíå-
ðèðóåò óíèòàðíûå êîäû ÌÎ y Yn E� , à áëîê LUTer — ìàêñèìàëüíûå êîäû [6, 10]
ÍÌÎ Y Vq L� , ãäå VL — ìíîæåñòâî íàáîðîâ ÌÎ, ñîñòîÿùèõ èç y Yn L� . Íàçîâåì
òàêîå êîäèðîâàíèå ñìåøàííûì.
Ðàññìîòðåííàÿ ñòðóêòóðà ïîðîæäàåò ÌÏÀ U 4 (ðèñ. 6).
 àâòîìàòå U 4 èñïîëüçóåòñÿ òîëüêî îäèí áëîê EMB, ôóíêöèè y Yn E� ïðåä-
ñòàâëÿþòñÿ â âèäå (2), à ôóíêöèè y Yn L� — â âèäå (3).
Ìíîæåñòâî YL îáðàçóåò VL íàáîðîâ ÌÎ. Äëÿ èõ êîäèðîâàíèÿ íåîáõîäèìî
RL ïåðåìåííûõ, R QL L� � �log 2 , à ïàðàìåòð QL îïðåäåëÿåòñÿ êàê Q VL L� | | .
Ïðèâåäåííûé ïîäõîä äàåò íàèëó÷øèå ðåçóëüòàòû ïðè âûïîëíåíèè óñëîâèÿ
R SL L
. (9)
 ýòîì ñëó÷àå äëÿ ðåàëèçàöèè êàæäîé ÌÎ y Yn L� äîñòàòî÷íî îäíîãî ýëå-
ìåíòà LUT.
Ïðåäëàãàåìûé ìåòîä ñèíòåçà àâòîìàòà U 4 âêëþ÷àåò ñëåäóþùèå ýòàïû:
1) ôîðìèðîâàíèå ìíîæåñòâà ñîñòîÿíèé A ïî ÃÑÀ �;
2) êîäèðîâàíèå ñîñòîÿíèé a Am � ;
3) ôîðìèðîâàíèå ìíîæåñòâà ÍÌÎ V ;
4) ôîðìèðîâàíèå ìíîæåñòâ YE è YL;
5) êîäèðîâàíèå íàáîðîâ ìèêðîîïåðàöèé;
6) ôîðìèðîâàíèå òàáëèö áëîêîâ EMB è LUTer;
7) ðåàëèçàöèÿ ñõåìû àâòîìàòà â çàäàííîì áàçèñå.
Äàëåå ïðåäëàãàåòñÿ ìåòîä ðàçáèåíèÿ ìíîæåñòâà Y (ï. 4 ìåòîäà ñèíòåçà àâòî-
ìàòà U 4), ïðèâîäèòñÿ ïðèìåð ñèíòåçà è ðåçóëüòàòû èññëåäîâàíèé.
4. ÐÀÇÁÈÅÍÈÅ ÌÍÎÆÅÑÒÂÀ ÌÈÊÐÎÎÏÅÐÀÖÈÉ
Íà ðèñ. 7 ïðåäñòàâëåíà áëîê-ñõåìà ïðåäëàãàåìîãî àëãîðèòìà ðàçáèåíèÿ ìíî-
æåñòâà Y . Íà ïåðâîì ýòàïå âñå ÌÎ íàõîäÿòñÿ âî ìíîæåñòâå YL, à âñå ÍÌÎ —
â VL (âåðøèíà 1). Àëãîðèòì èìååò íå áîëåå N øàãîâ (ïàðàìåòð k), à êàæäûé
øàã — íå áîëåå N öèêëîâ (ïàðàìåòð i ).
8 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
X
Start
Clock
T
EMB
YLLUTer
Z
YE
Ðèñ. 6. Ñòðóêòóðíàÿ ñõåìà ÌÏÀ U4
Îñíîâíàÿ èäåÿ ìåòîäà — ïîèñê ìèêðîîïåðàöèé y Yn L� , âêëþ÷åíèå êîòîðûõ
âî ìíîæåñòâî YE ìàêñèìàëüíî óìåíüøàåò êîëè÷åñòâî ÍÌÎ, îñòàþùèõñÿ âî
ìíîæåñòâå YL. Äëÿ ýòîãî íà êàæäîì øàãå àëãîðèòìà ôîðìèðóåòñÿ î÷åðåäü � ìèê-
ðîîïåðàöèé y Yn L� . Ýëåìåíòû î÷åðåäè óïîðÿäî÷èâàþòñÿ â ïîðÿäêå óìåíüøåíèÿ
ïàðàìåòðà Q yn( ), êîòîðûé ðàâåí êîëè÷åñòâó ÍÌÎ Y Vq L� , ñîäåðæàùèõ ÌÎ
y Yn L� . Êîëè÷åñòâî ýëåìåíòîâ â î÷åðåäè (âåðøèíà 3) îïðåäåëÿåò ìàêñèìàëüíîå
÷èñëî öèêëîâ íà øàãå k, k N�{ }1, ,� .
 êàæäîì öèêëå âûïîëíÿåòñÿ âûáîð òîãî ýëåìåíòà î÷åðåäè (âåðøèíà 5),
äëÿ êîòîðîãî îïðåäåëÿåòñÿ âåëè÷èíà �Qi , ðàâíàÿ êîëè÷åñòâó ÍÌÎ, èñêëþ÷àåìûõ
èçVL âñëåäñòâèå âêëþ÷åíèÿ ÌÎ y Yn L� âî ìíîæåñòâî YE . Äàëåå îïðåäåëÿåòñÿ ÷èñ-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 9
1
2
3
4
5
6
7
8
10
11
9
12
13
Ðèñ. 7. Áëîê-ñõåìà àëãîðèòìà ðàçáèåíèÿ ìíîæåñòâà ÌÎ
Start
Y Y Y
V V R R
L E
L Q
: , : ;
: , :
� � �
� �0
k :� 1
Ñîçäàíèå î÷åðåäè � , èìåþùåé
I YL� | | ýëåìåíòîâ
R Q Qk L i: ( )� �� �log2 �
Âûáîð i -ãî ýëåìåíòà î÷åðåäè � .
Îïðåäåëåíèå âåëè÷èíû � Qi
i :� 1
R Rk k� �1
Äà
Äà Äà
Íåò
Íåò
Íåò End
i i:�
1
i I�
k k:�
1
k N�
Y Y y
Y Y y
L L i
E E i
: \ { };
: { }
�
� �
Êîððåêöèÿ ìíîæåñòâà VL
ëî ïåðåìåííûõ Rk , äîñòàòî÷íîå äëÿ êîäèðîâàíèÿ ÍÌÎ Y Vq L� (âåðøèíà 6):
R Q Qk L i� �� �log ( )2 � . (10)
Åñëè èñêëþ÷åíèå i-ãî ýëåìåíòà î÷åðåäè � íå ïðèâîäèò ê óìåíüøåíèþ ðàç-
ðÿäíîñòè êîäà K Yq( ) (âûõîä «Íåò» èç áëîêà 7), òî îñóùåñòâëÿåòñÿ ïåðåõîä ê ñëå-
äóþùåìó ýëåìåíòó î÷åðåäè (âåðøèíà 9). Åñëè î÷åðåäü èñ÷åðïàíà (âûõîä «Äà»
èç áëîêà 11), òî àëãîðèòì çàâåðøàåòñÿ.  ïðîòèâíîì ñëó÷àå (âûõîä «Íåò» èç áëî-
êà 11) âûáèðàåòñÿ ñëåäóþùèé ýëåìåíò î÷åðåäè �.
Åñëè ðàçðÿäíîñòü êîäà K Yq( ) óìåíüøàåòñÿ (âûõîä «Äà» èç áëîêà 7), òî i-é
ýëåìåíò î÷åðåäè âêëþ÷àåòñÿ â YE è èñêëþ÷àåòñÿ èç YL (âåðøèíà 8). Ïàðàìåòð k
óâåëè÷èâàåòñÿ íà 1 (âåðøèíà 10). Åñëè âñå ÌÎ yn ïðîâåðåíû (âûõîä «Äà» èç
áëîêà 12), òî àëãîðèòì çàâåðøàåòñÿ.  ïðîòèâíîì ñëó÷àå îñóùåñòâëÿåòñÿ êîððåê-
öèÿ ìíîæåñòâàVL (âåðøèíà 13) è ñîçäàåòñÿ íîâàÿ î÷åðåäü (ïåðåõîä ê âåðøèíå 3).
Ïðîèëëþñòðèðóåì ýòîò àëãîðèòì íà ïðèìåðå ÃÑÀ �1, àíàëèç êîòîðîé ïîêà-
çûâàåò, ÷òî åå îïåðàòîðíûå âåðøèíû ñîäåðæàò 18 ÍÌÎ (òàáë. 2). Èìååì
V Y Y� { }1 18, ,� , Q �18, RQ � 5, ÷òî îïðåäåëÿåò ìíîæåñòâî Z z z� { }1 5, ,� .
Ðàçáèåíèå ìíîæåñòâà Y ïðèâåäåíî â òàáë. 3. Çäåñü â ñòîëáöå yn ïîêàçàíû
ìèêðîîïåðàöèè y Yn � , â ñòîëáöàõ Q yn( ) è �Qi — âåëè÷èíû, èñïîëüçóåìûå
â áëîê-ñõåìå àëãîðèòìà (ñì. ðèñ. 7), çíàêè
, � è � îáîçíà÷àþò ñîîòâåòñòâåííî,
÷òî ÌÎ yn âûáðàíà äëÿ àíàëèçà, âêëþ÷åíà âî ìíîæåñòâî YE , â äàëüíåéøåì íå
ðàññìàòðèâàåòñÿ.  ñòðîêå Y 1 ïðèâåäåíû ÌÎ y Yn E� â ïîðÿäêå èõ âêëþ÷åíèÿ âî
ìíîæåñòâî YE . Èíôîðìàöèÿ èç ñòîëáöà Q yn( ) ïîçâîëÿåò ñîçäàòü î÷åðåäü
� � { }y y y y y y y y y6 1 2 3 4 5 7 8 9, , , , , , , , . Âêëþ÷åíèå y6 â YE óìåíüøàåò êîëè÷åñòâî
ÍÌÎ íà � Qi � 6 . Èç (10) èìååì R1 4� . Óñëîâèå (8) âûïîëíÿåòñÿ è ÌÎ y6 âêëþ-
÷àåòñÿ â YE .
10 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
Ò à á ë è ö à 2. Íàáîðû ìèêðîîïåðàöèé äëÿ ÃÑÀ �1
q Yq q Yq q Yq
1 — 7 y y y1 4 6 13 y y y1 4 8
2 y y y1 2 3 8 y y y3 5 6 14 y y1 4
3 y y y3 4 6 9 y y y2 3 6 15 y1
4 y y2 7 10 y y y1 2 7 16 y6
5 y y4 8 11 y y y2 7 6 17 y y1 6
6 y y y3 5 9 12 y y2 3 18 y y y y3 5 6 9
Ò à á ë è ö à 3. Ðàçáèåíèå ìíîæåñòâà ìèêðîîïåðàöèé
yn Q yn( ) �Qi R1 Q yn( ) �Qi R2 Q yn( ) �Qi R3
y1 7 5
4 3 � � � �
y2 7 4 2
0 3 �
y3 6 5 4
0 3 �
y4 5 4 3
1 3 �
y5 3 2 2
0 3 �
y6 8
6 4 � � � � � � �
y7 3 2 1
0 3 �
y8 2 2 1
1 3 �
y9 2 1 1
1 3 �
Y1 y6 y1 –
Ðàññìîòðèì ìíîæåñòâî V Y YL � { }1 12, ..., . Ïîëó÷åííûå ÍÌÎ Y Vq L� ïðèâå-
äåíû â òàáë. 4. Äàëåå ôîðìèðóåòñÿ î÷åðåäü � � { }y y y y y y y y1 2 3 4 5 7 8 9, , , , , , , .
Âêëþ÷åíèå ÌÎ y1 â YE ïîçâîëÿåò èñêëþ÷èòü ÷åòûðå ÍÌÎ èçVL, ÷òî äàåò R2 3� .
Ñëåäîâàòåëüíî, óñëîâèå (7) âûïîëíÿåòñÿ è ÌÎ y1 âêëþ÷àåòñÿ â YE .
Ðàññìîòðè ìíîæåñòâî V Y YL � { }1 8, ,� . Ïîëó÷åííûå ÍÌÎ Y Vq L� ïîêàçàíû
â òàáë. 5.
Ïîñëåäíèå òðè ñòîëáöà òàáë. 3: Q yn( ), �Qi , R3 , ïîêàçûâàþò, ÷òî ðàçðÿä-
íîñòü êîäîâ ÍÌÎ Y Vq L� íå èçìåíÿåòñÿ, ïîýòîìó àëãîðèòì çàâåðøàåò ñâîþ ðà-
áîòó. Â ðåçóëüòàòå ïðèìåíåíèÿ ïðåäëîæåííîãî àëãîðèòìà èìååì Y y yE � { }1 6, ,
Y y y y y y y yL � { }2 3 4 5 7 8 9, , , , , , , Qi � 8, RL � 3, Z z z z� { }1 2 3, , . Ñëåäîâàòåëüíî,
ðàçðÿäíîñòü êîäîâ ÍÌÎ óìåíüøåíà íà 2.
5. ÏÐÈÌÅÐ ÑÈÍÒÅÇÀ ÀÂÒÎÌÀÒÀ ÑÎ ÑÌÅØÀÍÍÛÌ ÊÎÄÈÐÎÂÀÍÈÅÌ ÌÎ
Ðàññìîòðèì ïðèìåð ñèíòåçà ÌÏÀ U 4 ïî ÃÑÀ �1.
Ïóñòü â èñïîëüçóåìîé ìèêðîñõåìå FPGA èìååòñÿ òîëüêî òðè âõîäà S L ýëå-
ìåíòîâ LUT, à ñðåäè êîíôèãóðàöèé áëîêîâ EMB — êîíôèãóðàöèÿ S A � 8 è
tF � 8.
Êàê ñëåäóåò èç ÃÑÀ �1, àâòîìàò Ìèëè õàðàêòåðèçóåòñÿ ñëåäóþùèìè ïàðà-
ìåòðàìè: L � 5, R � 3, N � 9, RQ � 5. Ïîñêîëüêó S A � 8 è tF � 8, òî
V0
82 8 2048� � áèò.
Äëÿ àâòîìàòàU 1 1( )� èìååì 2 2 12 30728L R N R
� �( ) áèò. Äëÿ àâòîìà-
òà U 2 1( )� èìååì G � 4 (ýòî ñëåäóåò èç [10] è â íàñòîÿùåé ñòàòüå ïîäðîáíî íå
îáúÿñíÿåòñÿ). Èòàê, 2 2 12 15367G R
QR R
� �( ) áèò. Òàê êàê RQ � 5, òî
2 2 8 20488L R
QR R
� �( ) áèò. Î÷åâèäíî, â äàííîì ñëó÷àå ìîæíî èñïîëüçî-
âàòü ìîäåëè U 2 è U 3 . Ýòî ñëåäóåò èç óñëîâèé (4)–(6).
Ïîñêîëüêó t tL F� � 8, R RQ� �3 5, , óñëîâèå (7) âûïîëíÿåòñÿ, ñëåäîâàòåëü-
íî, ìîäåëü U 4 1( )� ìîæíî èñïîëüçîâàòü.
Ýòàïû 1–4 ïðåäëîæåííîãî ìåòîäà ñèíòåçà äëÿ ÌÏÀ U 4 âûïîëíåíû. Êîäû
ñîñòîÿíèé K am( ) ïîêàçàíû â ÏÑÒ (ñì. òàáë. 1). Ìíîæåñòâà YE è YL íàéäåíû
â ðàçä. 4.
Óñëîâèå (9) âûïîëíÿåòñÿ, ïîýòîìó êîäèðîâàíèå ÍÌÎ Y Vq L� ìîæíî ïðîâåñ-
òè ïðîèçâîëüíî. Ïðèìåíèâ àëãîðèòì êîäèðîâàíèÿ [19], ïîëó÷èì êîäû K Yq( )
(ðèñ. 8).
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 11
Ò à á ë è ö à 4. Íàáîðû ÌÎ ïîñëå èñêëþ÷åíèÿ y6
q Yq q Yq q Yq
1 — 5 y y4 8 9 y y2 3
2 y y y1 2 3 6 y y y3 5 9 10 y y y1 2 7
3 y y3 4 7 y y1 4 11 y y y1 4 8
4 y y2 7 8 y y3 5 12 y1
Ò à á ë è ö à 5. Íàáîðû ÌÎ ïîñëå èñêëþ÷åíèÿ y1
q Yq q Yq q Yq q Yq
1 — 3 y y3 4 5 y y4 8 7 y4
2 y y2 3 4 y y2 7 6 y y y3 5 9 8 y y3 5
Êàê ñëåäóåò èç êàðòû Êàðíî (ðèñ. 8),
y z3 1� , çíà÷èò, ÌÎ y YL3 � ãåíåðèðóåòñÿ
áëîêîì EMB. Òàêèì îáðàçîì, áëîê LUTer â äàí-
íîì ñëó÷àå ñîñòîèò èç | |YL � �1 6 ýëåìåíòîâ
LUT. Îòìåòèì, ÷òî áëîê LUTer àâòîìàòàU 4 1( )�
èìååò îäèí óðîâåíü ëîãèêè.
Òàáëèöà áëîêà EMB àâòîìàòà Ìèëè U 4 1( )�
ñòðîèòñÿ íà îñíîâå ÏÑÒ àâòîìàòà Ìèëè (ñì. òàáë. 1)
è èìååò ñëåäóþùèå ñòîëáöû (òàáë. 6): K am( ), X
— àäðåñà ÿ÷åéêè ïàìÿòè, YE , Z, � — ñîäåðæàíèå ñîîòâåòñòâóþùèõ ÿ÷ååê ïàìÿòè, g
— íîìåð ÿ÷åéêè ïàìÿòè, h — íîìåð ïåðåõîäà.  îáùåì ñëó÷àå òàáëèöà èìååò GEMB
ñòðîê, GEMB
L R�
2 , à ïåðåõîäû èç ñîñòîÿíèÿ a Am � îïèñûâàþòñÿ ñ ïîìîùüþ
H am( ) ñòðîê, H am
L( ) � 2 . Â ðàññìàòðèâàåìîì ïðèìåðå èìååì GEMB � 256 è
H am( ) � 32.
 ñòîëáöå YE óêàçûâàþòñÿ ÌÎ y Yn E� , ôîðìèðóåìûå íà ïåðåõîäå � �a am s, .
 ñòîëáöå Z óêàçûâàþòñÿ êîäû K Yq( ) ÍÌÎ Y Vq L� , ôîðìèðóåìûõ íà ïåðåõîäå
� �a am s, . Â ýòîì ïðèìåðå íîìåðà ÍÌÎ âûáèðàþòñÿ èç òàáë. 5, à èõ êîäû — èç
êàðòû Êàðíî (ðèñ. 8).
Ïîÿñíèì çàïîëíåíèå òàáë. 6. Çäåñü ñòðîêà g �1 ñîîòâåòñòâóåò ñòðîêå h � 4 èç
òàáë. 1, ãäå â ñòîëáöå Yh çàïèñàí íàáîð y y4 8 , ñîîòâåòñòâóþùèé ÍÌÎ Y5 èç
òàáë. 5. Ïîýòîìó ñòîëáåö Z äëÿ g �1 ñîäåðæèò êîä 001 èç ðèñ. 8. Ñòðîêà g � 4 ñî-
îòâåòñòâóåò ñòðîêå h �1, â êîòîðîé çàïèñàí ÍÌÎ y y y1 2 3 (ñì. òàáë. 1). Òàê êàê
y YE1 � , ñòîëáåö YE ñîäåðæèò êîä 10 (ñòðîêà g � 4). Ïîñëå èñêëþ÷åíèÿ y1 èìååì
íàáîð y y Y2 3 2� (ñì. ðèñ. 8) ñ êîäîì K Y( )2 100� , êîòîðûé íàõîäèòñÿ â ñòîëáöå Z
(ñòðîêà g � 4). Ïðè âñåõ ïåðåõîäàõ èç a A1 � ôîðìèðóåòñÿ D3 1� . Ïîýòîìó
â ñòîëáöå � íàõîäèòñÿ êîä 001 (ñòðîêè g îò 1 äî 8). Àíàëîãè÷íî çàïîëíÿþòñÿ âñå
256 ñòðîê òàáëèöû áëîêà EMB àâòîìàòà U 4 1( )� .
Òàáëèöà áëîêà LUTer (òàáë. 7) ñîäåðæèò ñòîëáöû K Yq( ), YL è q, à òàêæå
èìååò êîëè÷åñòâî ñòðîê Q � 8. Êîäû ÍÌÎ Y Vq L� âûáèðàþò èç ðèñ. 8, à ñîäåð-
æèìîå ñòðîêè äëÿ ñòîëáöà YL — èç òàáë. 5. Îòìåòèì, ÷òî ÌÎ y3 â òàáë. 7 íå ñó-
ùåñòâóåò, òàê êàê y z3 1� .
Íà ïîñëåäíåì ýòàïå 7 ïðåäëàãàåìîãî ìåòîäà ïðèìåíÿþòñÿ ñòàíäàðòíûå
ñðåäñòâà ÑÀÏÐ äëÿ ðåøåíèÿ çàäà÷ ðàçìåùåíèÿ, òðàññèðîâêè è ôîðìèðîâàíèÿ ïî-
òîêîâ «bit-stream» [10]. (Â íàñòîÿùåé ñòàòüå ýòîò ýòàï íå ðàññìàòðèâàåòñÿ.)
12 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
00 01 11 10
Y1 Y4 Y2
Y7 Y3
0
1 Y8
Y6
Y5
z1 z2
z3
Ðèñ. 8. Êîäèðîâàíèå íàáîðîâ ìèêðî-
îïåðàöèé ÌÏÀ U4 1( )�
Ò à á ë è ö à 6. Ôðàãìåíò òàáëèöû áëîêà EMB àâòîìàòà U 4 1( )�
K am( ) X YE Z Ô
g h
T T T1 2 3 x x x x x5 4 3 2 1 y y1 6 z z z1 2 3 D D D1 2 3
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 4
0 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 2 2
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 3 4
0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 1 4 1
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 5 3
0 0 0 0 0 1 0 1 0 1 1 0 1 0 0 1 6 2
0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 7 3
0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 1 8 1
6. ÈÑÑËÅÄÎÂÀÍÈÅ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÏÐÅÄËÎÆÅÍÍÎÃÎ ÌÅÒÎÄÀ
Äëÿ àíàëèçà ýôôåêòèâíîñòè ïðåäëîæåííîãî ìåòîäà èñïîëüçîâàíû ñòàíäàðòíûå
òåñòîâûå ïðèìåðû (ÑÒÏ) èç áèáëèîòåêè LGSynth 93 [16]. Áèáëèîòåêà âêëþ÷à-
åò 48 ÑÒÏ, çàäàííûõ â ôîðìàòå KISS2.
Èññëåäîâàíèÿ ïðîâîäèëèñü ñ ïîìîùüþ ÑÀÏÐ K2F [20], DEMAIN [21]
è SIS [6]. Èç ñèñòåìû SIS èñïîëüçîâàí àëãîðèòì êîäèðîâàíèÿ ñîñòîÿíèé JEDI,
ïðèçíàííûé îäíèì èç ëó÷øèõ â íàñòîÿùåå âðåìÿ [5, 10].
Äëÿ ñèíòåçà ñõåìû ÌÏÀ, îðèåíòèðîâàííîãî íà ìèêðîñõåìó XC5VLX30FF324
ôèðìû Xilinx, ïðèìåíÿëàñü ÑÀÏÐ ISE14.1 ýòîé ôèðìû [15]. Òàêîé âûáîð îá-
óñëîâëåí òåì, ÷òî ñ ïîìîùüþ óêàçàííîé ìèêðîñõåìû ïðîâîäèëèñü èññëåäîâàíèÿ
â [8, 20], ÷òî ïîçâîëÿåò ñðàâíèòü ðåçóëüòàòû, ïîëó÷åííûå â íàñòîÿùåé ñòàòüå,
ñ ðåçóëüòàòàìè èñïîëüçîâàíèÿ äðóãèõ ìåòîäîâ.
Èññëåäîâàëèñü ìîäåëè U 1–U 4 èç áèáëèîòåêè [16]. Äëÿ ðåàëèçàöèè ñõåì
U j1 ( )� ïðèìåíÿëñÿ àëãîðèòì JEDI ( )U 1J è ñèñòåìà DEMAIN ( )U 1D , îñíîâàííàÿ
íà ñáàëàíñèðîâàííîé ôóíêöèîíàëüíîé äåêîìïîçèöèè [11]. Äëÿ àâòîìàòîâU 2 ,U 3
ðåçóëüòàòû âûáèðàëèñü èç [17]. Âî âñåõ ñëó÷àÿõ ñðàâíèâàëîñü ÷èñëî ýëåìåíòîâ
LUT â ñõåìå, òðåáóåìîå äëÿ ðåàëèçàöèè áëîêà LUTer.
Îòìåòèì, ÷òî ìèêðîñõåìà XC5VLX30FF324 îòíîñèòñÿ ê ñåìåéñòâó Virtex-5.
Îíà âêëþ÷àåò 32 áëîêà ïàìÿòè, èç êîòîðûõ èñïîëüçîâàëñÿ òîëüêî îäèí. Ýëåìåí-
òû LUT èìåþò S L � 5 âõîäîâ.
Êàê óæå îòìå÷àëîñü, 82 % ÑÒÏ ðåàëèçóþòñÿ íà îäíîì áëîêå EMB.  òàáë. 8
ïðèâåäåíû õàðàêòåðèñòèêè ÑÒÏ, äëÿ ðåàëèçàöèè ñõåì êîòîðûõ íåîáõîäèìî ñîâ-
ìåñòíîå èñïîëüçîâàíèå LUT è EMB.
 òàáë. 9 ïîêàçàíû ýëåìåíòû LUT, íåîáõîäèìûå äëÿ ðåàëèçàöèè áëîêà
LUTer â ÑÒÏ èç òàáë. 8.  ñòðîêå � ïðèâåäåíî ñóììàðíîå êîëè÷åñòâî ýëåìåíòîâ
â áëîêå LUTer äëÿ êàæäîé ìîäåëè, à â ñòðîêå % — ïðîöåíòíîå ñîîòíîøåíèå êî-
ëè÷åñòâà LUT äëÿ ðàçëè÷íûõ ìîäåëåé ÌÏÀ. Ïðè ýòîì ñóììàðíîå êîëè÷åñòâî
LUT äëÿ ìîäåëè U 4 ïðèíÿòî ðàâíûì 100 %.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 13
Ò à á ë è ö à 7. Áëîê LUTer àâòîìàòà U 4 1( )�
K Yq( ) YL
q
K Yq( ) YL
q
z z z1 2 3 y y y y y y2 4 5 7 8 9 z z z1 2 3 y y y y y y2 4 5 7 8 9
0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 2
0 0 1 0 1 0 0 1 0 5 0 0 1 0 1 0 0 0 0 3
0 1 0 1 0 0 1 0 0 4 0 1 0 0 0 1 0 0 1 6
0 1 1 0 1 0 0 0 0 7 0 1 1 0 0 1 0 0 0 8
Ò à á ë è ö à 8. Õàðàêòåðèñòèêè ñòàíäàðòíûõ òåñòîâûõ ïðèìåðîâ
ÑÒÏ L N M R RQ G
ex1 9 19 20 5 7 5
planet 17 19 48 6 7 5
planet1 17 19 48 6 7 5
S1488 12 22 61 6 8 4
S1494 14 24 68 7 8 4
sand 11 27 32 5 6 3
styr 14 31 42 6 7 4
kirkman 12 16 16 4 8 5
Êàê âèäíî èç òàáë. 9, äëÿ äàííûõ ÑÒÏ íàèëó÷øèå õàðàêòåðèñòèêè èìååò àâ-
òîìàò U 4 , çàòåì ìîäåëüU 1, áàçèðóþùàÿñÿ íà àëãîðèòìå JEDI. Íàèõóäøèå ïîêà-
çàòåëè ó ìîäåëè U 3 , îñíîâàííîé íà êîäèðîâàíèè ÍÌÎ.
Ñðàâíåíèå ñòîëáöîâ N (ñì. òàáë. 8) èU 4 (ñì. òàáë. 9) ïîçâîëÿåò ñäåëàòü ñëå-
äóþùèå âûâîäû. Êîëè÷åñòâî ýëåìåíòîâ LUT â áëîêå LUTer ìåíüøå ÷èñëà ìèê-
ðîîïåðàöèé â ÑÒÏ. Ýòî îçíà÷àåò, ÷òî ÷àñòü ìèêðîîïåðàöèé ðåàëèçîâàíà íà áëîêå
EMB. Ñõåìû áëîêà LUTer äëÿ U 4 îäíîóðîâíåâûå, ò.å. ñìåøàííîå êîäèðîâàíèå
ÍÌÎ ïîçâîëèëî óìåíüøèòü ÷èñëî ðàçðÿäîâ êîäà K Yq( ) äî S L � 5.
Äëÿ âñåõ îñòàëüíûõ ìîäåëåé áëîê LUTer ñîäåðæèò áîëåå îäíîãî óðîâíÿ ëî-
ãèêè. Ñëåäîâàòåëüíî, ïðåäëîæåííûé ïîäõîä ïîçâîëÿåò óìåíüøèòü ÷èñëî ýëåìåí-
òîâ LUT, èõ óðîâíåé è ìåæñîåäèíåíèé â áëîêå LUTer ïî ñðàâíåíèþ ñ äðóãèìè
èññëåäóåìûìè ìîäåëÿìè. Êàê èçâåñòíî [8, 22], ïðèáëèçèòåëüíî 60 % ýíåðãèè èñ-
ïîëüçóþò ìåæñîåäèíåíèÿ. Ïîýòîìó ñëåäóåò îæèäàòü, ÷òî ñõåìû, îñíîâàííûå íà
ìîäåëè U 4 , áóäóò ïîòðåáëÿòü ìåíüøå ýíåðãèè, ÷åì ñõåìû, áàçèðóþùèåñÿ íà ìî-
äåëÿõ U 1–U 3 . Ïîñêîëüêó áëîê LUTer â U 4 èìååò òîëüêî îäèí óðîâåíü, ïðåäëî-
æåííûé ìåòîä ïîçâîëÿåò ïîëó÷àòü ñõåìû ñ áîëåå âûñîêèì áûñòðîäåéñòâèåì, ÷åì
äëÿ ìîäåëåé U 1–U 3 .
Åñòåñòâåííî, ÷òî ýòè âûâîäû ñïðàâåäëèâû òîëüêî äëÿ äàííîé ìèêðîñõåìû FPGA
è àâòîìàòîâ èç [16]. Îäíàêî ðåçóëüòàòû èññëåäîâàíèé ïîêàçûâàþò, ÷òî ïðåäëîæåííûé
ïîäõîä ìîæåò óëó÷øèòü îñíîâíûå õàðàêòåðèñòèêè óñòðîéñòâ óïðàâëåíèÿ.
ÇÀÊËÞ×ÅÍÈÅ
Îïèñàííûé â ðàáîòå ìåòîä îòíîñèòñÿ ê ìåòîäàì ñòðóêòóðíîé äåêîìïîçèöèè ñõåì
ÌÏÀ [10] è ÿâëÿåòñÿ ðàçâèòèåì èäåé, ïðåäëîæåííûõ â [17]. Ìåòîä ïîçâîëÿåò
óëó÷øèòü õàðàêòåðèñòèêè ñõåìû ÌÏÀ, îñíîâàííîé íà êîäèðîâàíèè íàáîðîâ ìèê-
ðîîïåðàöèé. Óìåíüøåíèå àïïàðàòóðíûõ çàòðàò îáåñïå÷èâàåòñÿ ðåàëèçàöèåé íåêîòî-
ðûõ ìèêðîîïåðàöèé áëîêîì EMB. Ýòî äàåò âîçìîæíîñòü óìåíüøèòü êîëè÷åñòâî
íàáîðîâ, èñïîëüçóåìûõ áëîêîì LUTer äëÿ ðåàëèçàöèè îñòàëüíûõ ìèêðîîïåðàöèé.
Ìåòîä ìîæíî ïðèìåíÿòü, åñëè ðàçðàáîò÷èê ñõåìû óñòðîéñòâà óïðàâëåíèÿ
èñïîëüçóåò îãðàíè÷åííîå êîëè÷åñòâî áëîêîâ âñòðîåííîé ïàìÿòè.  ðàáîòå ðàñ-
ñìîòðåí ñëó÷àé, êîãäà äëÿ ýòîãî èìååòñÿ òîëüêî îäèí áëîê EMB.
Êàê ïîêàçàëè èññëåäîâàíèÿ, ïðåäëîæåííûé ìåòîä ïîçâîëÿåò ïîëó÷àòü îäíî-
óðîâíåâûå ñõåìû áëîêîâ LUTer äëÿ ñòàíäàðòíûõ ïðèìåðîâ [16], ÷òî ïðèâîäèò
ê óìåíüøåíèþ ÷èñëà ýëåìåíòîâ LUT è èõ ìåæñîåäèíåíèé ïî ñðàâíåíèþ ñ ìåòî-
äàìè, ïðèìåíåíèå êîòîðûõ âåäåò ê ìíîãîóðîâíåâûì ñõåìàì LUTer. Òàêèì îáðà-
çîì, ñìåøàííîå êîäèðîâàíèå íàáîðîâ ìèêðîîïåðàöèé ìîæåò ðàññìàòðèâàòüñÿ
14 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
Ò à á ë è ö à 9. Ñóììàðíîå êîëè÷åñòâî ýëåìåíòîâ â áëîêå LUTer
ÑÒÏ U 1J U 1D U 2 U 3 U 4
ex1 20 24 22 36 16
planet 32 38 34 38 14
planet1 32 38 34 38 14
S1488 24 32 28 42 18
S1494 26 36 30 44 21
sand 30 38 32 52 22
styr 31 42 34 60 26
kirkman 26 36 28 34 12
� 221 282 242 344 143
% 154 197 169 240 100
êàê àëüòåðíàòèâà èçâåñòíûì ìåòîäàì ñèíòåçà ñõåì ìèêðîïðîãðàììíûõ àâòîìà-
òîâ â áàçèñå FPGA.
 ðàáîòàõ [23–27] ïðåäëàãàþòñÿ ðàçëè÷íûå ìåòîäû ñèíòåçà ñõåì ñîâìåùåííûõ
ÌÏÀ. Êàê èçâåñòíî [7], ïîñëåäíèå èìåþò âûõîäíûå ñèãíàëû òèïà Ìóðà è Ìèëè.
Ïîýòîìó äàëüíåéøèì íàïðàâëåíèåì èññëåäîâàíèé áóäåò ðàçðàáîòêà ìåòîäîâ ñèíòå-
çà ñîâìåùåííûõ ÌÏÀ ñî ñìåøàííûì êîäèðîâàíèåì íàáîðîâ ìèêðîîïåðàöèé.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ñîëîâüåâ Â.Â. Ïðîåêòèðîâàíèå öèôðîâûõ ñõåì íà îñíîâå ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èí-
òåãðàëüíûõ ñõåì. Ìîñêâà: Ãîðÿ÷àÿ ëèíèÿ — ÒÅËÅÊÎÌ, 2001. 636 ñ.
2. Ãðóøíèöêèé Ð.È., Ìóðñàåâ À.Õ., Óãðþìîâ Å.Ï. Ïðîåêòèðîâàíèå ñèñòåì ñ èñïîëüçîâàíèåì
ìèêðîñõåì ïðîãðàììèðóåìîé ëîãèêè. ÑÏá: ÁÕÂ-Ïåòåðáóðã, 2002. 608 ñ.
3. Tiwari A., Tomko K. Saving power by mapping finite state machines into embedded memory blocks
in FPGAs. Proc. Design, Automation and Test in Europe Conference and Exhibition (Paris, France,
6–20 Feb. 2004). 2004. Vol. 2. P. 916–921.
4. Skliarova I., Sklyarov V., Sudnitson A. Design of FPGA-based circuits using hierarchical finite state
machines. Tallinn: TUT Press, 2012. 240 p.
5. Czerwinski R., Kania D. Finite state machines logic synthesis for complex programmable logic
devices. Berlin: Springer, 2013. 172 p.
6. DeMicheli G. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 1994. 576 p.
7. Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p.
8. Garcia-Vargas I., Senhadji-Navarro R., Jim�nez-Moreno G., Civit-Balcells A., Guerra-Gutierrezz P.
ROM-based finite state machines implementation in low cost FPGAs. IEEE Intern. Simp. on
Industrial Electronics (ISIE’07) (Vigo, 2007). 2007. P. 2342–2347.
9. Rawski M., Tomaszewicz P., Borowski G., �Luba T. Logic synthesis method of digital circuits designed
for implementation with embedded memory blocks on FPGAs. In: Design of Digital Systems and
Devises. Lecture Notes in Electrical Engineering. Adamski M., Barkalov A., Wegrzyn M. (Eds.).
Vol. 79. Berlin: Springer, 2011. P. 121–144.
10. Sklyarov V., Skliarova I., Barkalov A., Titarenko L. Synthesis and optimization of FPGA-based
systems. Berlin: Springer, 2014. 432 p.
11. Rawski M., Selvaraj H., �Luba T. An application of functional decomposition in ROM-based FSM
implementation in FPGA devices. Journal of System Architecture. 2005. Vol. 51, Iss. 6–7.
P. 424–434.
12. Maxfield C. The design warrior’s guide to FPGAs. Orlando: Academic Press, 2004. 542 p.
13. Grout I. Digital systems design with FPGAs and CPLDs. Amsterdam: Elsevier, 2008. 784 p.
14. White paper FPGA architecture. URL: www.altera.com.
15. UG473 (v1.14) July 3, 2019. URL: www.xilinx.com.
16. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Techn. Rep.
Microelectronics Center of North Carolina, 1991. 43 p.
17. Barkalov A., Titarenko L., Chmielewski S. Mixed encoding of collections of output variables for
LUT-based FSMs. Journal of Circuits, Systems and Computers. 2019. Vol. 28, N 8. P. 1–21.
18. Nowicka M., �Luba T., Rawski M. FPGA-based decomposition of boolean functions: Algorithms and
implementations. Proc. of the 6th International Conference on Advanced Computer Systems
(Szczecin, 1999). P. 502–509.
19. Barkalov A., Titarenko L. Logic synthesis for FSM-based control units. Berlin: Springer, 2009.
233 p.
20. Kolopienczyk M., Titarenko L., Barkalov A. Design of EMB-based Moore FSMs. Journal of
Circuits, Systems and Computers. 2017. Vol. 26, N 7. P. 1–23.
21. DEMAIN. URL: www.zpt.tele.pw.edu.pl/oprogramowanie/demain.html.
22. Garcia-Vargas L., Senhaji-Navarro R. Finite state machines with input multiplexing: A performance
study. IEEE Transactions on CAD of Integrated Circuits and Systems. 2015. Vol. 34, Iss. 5.
P. 867–871.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3 15
23. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Åôèìåíêî Ê.Í. Îïòèìèçàöèÿ ñõåì êîìïîçèöèîííûõ ìèêðî-
ïðîãðàììíûõ óñòðîéñòâ óïðàâëåíèÿ, ðåàëèçóåìûõ íà ÏËÈÑ. Êèáåðíåòèêà è ñèñòåìíûé àíà-
ëèç. 2011. ¹ 1. C. 179–188.
24. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À. Ïðåîáðàçîâàíèå êîäîâ â êîìïîçèöèîííûõ ìèêðîïðîãðàììíûõ
óñòðîéñòâàõ óïðàâëåíèÿ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2011. ¹ 5. C. 107–118.
25. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Âèçîð ß.Å., Ìàòâèåíêî À.Â. Îïòèìàëüíîå êîäèðîâàíèå ñîñòî-
ÿíèé â ñîâìåùåííîì àâòîìàòå. Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. 2016. ¹ 6. C. 34–39.
26. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Âèçîð ß.Å., Ìàòâèåíêî À.Â. Óìåíüøåíèå ÷èñëà LUT ýëåìåí-
òîâ â ñõåìå ñîâìåùåííîãî àâòîìàòà. Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. 2016. ¹ 3. C. 16–22.
27. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Âèçîð ß.Å., Ìàòâèåíêî À.Â. Óìåíüøåíèå àïïàðàòóðíûõ çà-
òðàò â ñîâìåùåííûõ àâòîìàòàõ. Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. 2017. ¹ 4. C. 43–50.
Íàä³éøëà äî ðåäàêö³¿ 11.06.2019
Î.Î. Áàðêàëîâ, Ë.Î. Ò³òàðåíêî, À.Â. Áàºâ, Î.Â. Ìàò⳺íêî
Ç̲ØÀÍÅ ÊÎÄÓÂÀÍÍß ÍÀÁÎв ̲ÊÐÎÎÏÅÐÀÖ²É Ó Ì²ÊÐÎÏÐÎÃÐÀÌÍÎÌÓ
ÀÂÒÎÌÀÒ²
Àíîòàö³ÿ. Çàïðîïîíîâàíî ìåòîä çìåíøåííÿ ê³ëüêîñò³ LUT ó ñõåì³ ì³êðîïðîã-
ðàìíîãî àâòîìàòà ̳ë³, ÿêèé ðåàë³çóºòüñÿ â áàçèñ³ FPGA. Ìåòîä �ðóíòóºòüñÿ
íà âèëó÷åíí³ ç íàáîð³â ì³êðîîïåðàö³é äåÿêèõ åëåìåíò³â äëÿ ðåàë³çàö³¿ íà
áëîö³ ïàì’ÿò³ EMB. Òàêèé ï³äõ³ä äຠçìîãó çìåíøèòè ê³ëüê³ñòü ð³âí³â ëîã³êè
³ ì³æç’ºäíàíü ó ñõåì³, ÿêà ðåàë³çóºòüñÿ íà åëåìåíòàõ LUT. Çàïðîïîíîâàíî àë-
ãîðèòì ðîçáèòòÿ ìíîæèíè ì³êðîîïåðàö³é. Íàâåäåíî ïðèêëàä ñèíòåçó ³ ðåçóëü-
òàòè ïðîâåäåíèõ äîñë³äæåíü.
Êëþ÷îâ³ ñëîâà: àâòîìàò ̳ë³, ñèíòåç, FPGA, LUT, EMB, êîäóâàííÿ íàáîð³â
ì³êðîîïåðàö³é.
A.A. Barkalov, L.A. Titarenko, A.V. Baiev, A.V. Matviienko
MIXED ENCODING OF COLLECTIONS OF MICROOPERATIONS
FOR MICROPROGRAMMED AUTOMATA
Abstract. A method is proposed for reducing the number of LUTs in the circuit
of a microprogrammed Mealy FSM. The method is based on elimination of
some elements from the sets of microoperations for their implementation by
EMB. This approach reduces logic levels and interconnections for a circuit
implemented with LUTs. An algorithm is proposed for searching a partition of
the set of micro-operations. An example of synthesis is given as well as results
of the investigations.
Keywords: Mealy FSM, synthesis, FPGA, LUT, EMB, encoding of collections
of micro-operations.
Áàðêàëîâ Àëåêñàíäð Àëåêñàíäðîâè÷,
äîêòîð òåõí. íàóê, ïðîôåññîð Óíèâåðñèòåòà Çåëåíîãóðñêîãî (Ïîëüøà); ïðîôåññîð Äîíåöêîãî
íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Âàñèëèÿ Ñòóñà, Âèííèöà, e-mail: A.Barkalov@iie.uz.zgora.pl.
Òèòàðåíêî Ëàðèñà Àëåêñàíäðîâíà,
äîêòîð òåõí. íàóê, ïðîôåññîð Óíèâåðñèòåòà Çåëåíîãóðñêîãî (Ïîëüøà); ïðîôåññîð Õàðüêîâñêîãî
íàöèîíàëüíîãî óíèâåðñèòåòà ðàäèîýëåêòðîíèêè, e-mail: L.Titarenko@iie.uz.zgora.pl.
Áàåâ Àðòåì Âèêòîðîâè÷,
êàíäèäàò ôèç.-ìàò. íàóê, âåäóùèé íàó÷íûé ñîòðóäíèê Äîíåöêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè
Âàñèëèÿ Ñòóñà, Âèííèöà; ðóêîâîäèòåëü íàïðàâëåíèÿ ïî èñêóññòâåííîìó èíòåëëåêòó, ôèðìà Peoly,
Âèííèöà, e-mail: a.baev@donnu.edu.ua.
Ìàòâèåíêî Àëåêñàíäð Âëàäèìèðîâè÷,
íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, Êèåâ,
e-mail: avmatv@ukr.net.
16 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 3
|
| id | nasplib_isofts_kiev_ua-123456789-190375 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1019-5262 |
| language | Russian |
| last_indexed | 2025-12-07T18:45:02Z |
| publishDate | 2020 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Баркалов, А.А. Титаренко, Л.А. Баев, А.В. Матвиенко, А.В. 2023-06-04T16:24:05Z 2023-06-04T16:24:05Z 2020 Смешанное кодирование наборов микроопераций в микропрограммном автомате / А.А. Баркалов, Л.А. Титаренко, А.В. Баев, А.В. Матвиенко // Кибернетика и системный анализ. — 2020. — Т. 56, № 3. — С. 3–16. — Бібліогр.: 27 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/190375 004.274 Предложен метод уменьшения количества LUT в схеме микропрограммного
 автомата Мили, реализуемого в базисе FPGA. Метод основан
 на удалении из наборов микроопераций некоторых элементов для реализации
 на блоке памяти EMB. Такой подход позволяет уменьшить число
 уровней логики и межсоединений в схеме, реализуемой на элементах LUT.
 Предложен алгоритм разбиения множества микроопераций. Приведен пример
 синтеза и показаны результаты проведенных исследований. Запропоновано метод зменшення кількості LUT у схемі мікропрограмного автомата Мілі, який реалізується в базисі FPGA. Метод ґрунтується на вилученні з наборів мікрооперацій деяких елементів для реалізації на блоці пам'яті EMB. Такий підхід дає змогу зменшити кількість рівнів логіки і міжз'єднань у схемі, яка реалізується на елементах LUT. Запропоновано алгоритм розбиття множини мікрооперацій. Наведено приклад синтезу і результати проведених досліджень. A method is proposed for reducing the number of LUTs in the circuit of a microprogrammed Mealy FSM. The method is based on elimination of some elements from the sets of microoperations for their implementation by EMB. This approach reduces logic levels and interconnections for a circuit implemented with LUTs. An algorithm is proposed for searching a partition of the set of micro-operations. An example of synthesis is given as well as results of the investigations. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кібернетика Смешанное кодирование наборов микроопераций в микропрограммном автомате Змішане кодування наборів мікрооперацій у мікропрограмному автоматі Mixed encoding of collections of microoperations for microprogrammed automata Article published earlier |
| spellingShingle | Смешанное кодирование наборов микроопераций в микропрограммном автомате Баркалов, А.А. Титаренко, Л.А. Баев, А.В. Матвиенко, А.В. Кібернетика |
| title | Смешанное кодирование наборов микроопераций в микропрограммном автомате |
| title_alt | Змішане кодування наборів мікрооперацій у мікропрограмному автоматі Mixed encoding of collections of microoperations for microprogrammed automata |
| title_full | Смешанное кодирование наборов микроопераций в микропрограммном автомате |
| title_fullStr | Смешанное кодирование наборов микроопераций в микропрограммном автомате |
| title_full_unstemmed | Смешанное кодирование наборов микроопераций в микропрограммном автомате |
| title_short | Смешанное кодирование наборов микроопераций в микропрограммном автомате |
| title_sort | смешанное кодирование наборов микроопераций в микропрограммном автомате |
| topic | Кібернетика |
| topic_facet | Кібернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/190375 |
| work_keys_str_mv | AT barkalovaa smešannoekodirovanienaborovmikrooperaciivmikroprogrammnomavtomate AT titarenkola smešannoekodirovanienaborovmikrooperaciivmikroprogrammnomavtomate AT baevav smešannoekodirovanienaborovmikrooperaciivmikroprogrammnomavtomate AT matvienkoav smešannoekodirovanienaborovmikrooperaciivmikroprogrammnomavtomate AT barkalovaa zmíšanekoduvannânaborívmíkrooperacíiumíkroprogramnomuavtomatí AT titarenkola zmíšanekoduvannânaborívmíkrooperacíiumíkroprogramnomuavtomatí AT baevav zmíšanekoduvannânaborívmíkrooperacíiumíkroprogramnomuavtomatí AT matvienkoav zmíšanekoduvannânaborívmíkrooperacíiumíkroprogramnomuavtomatí AT barkalovaa mixedencodingofcollectionsofmicrooperationsformicroprogrammedautomata AT titarenkola mixedencodingofcollectionsofmicrooperationsformicroprogrammedautomata AT baevav mixedencodingofcollectionsofmicrooperationsformicroprogrammedautomata AT matvienkoav mixedencodingofcollectionsofmicrooperationsformicroprogrammedautomata |