Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов
Предложено использовать представление методов синтеза микропрограммного автомата с операционным автоматом переходов в виде структуры, блоки которой соответствуют элементам математической модели автомата. Разработаны пять структур, учитывающих различия в исходных данных и результатах методов синтеза....
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2019 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2019
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/180843 |
| 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: | Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов / Р.М. Бабаков, А.А. Баркалов // Кибернетика и системный анализ. — 2019. — Т. 55, № 2. — С. 3-9. — Бібліогр.: 12 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-180843 |
|---|---|
| record_format |
dspace |
| spelling |
Бабаков, Р.М. Баркалов, А.А. 2021-10-22T14:37:34Z 2021-10-22T14:37:34Z 2019 Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов / Р.М. Бабаков, А.А. Баркалов // Кибернетика и системный анализ. — 2019. — Т. 55, № 2. — С. 3-9. — Бібліогр.: 12 назв. — рос. 1019-5262 https://nasplib.isofts.kiev.ua/handle/123456789/180843 004.2 Предложено использовать представление методов синтеза микропрограммного автомата с операционным автоматом переходов в виде структуры, блоки которой соответствуют элементам математической модели автомата. Разработаны пять структур, учитывающих различия в исходных данных и результатах методов синтеза. Описанные и подобные структуры можно использовать для классификации существующих и разрабатываемых в будущем методов синтеза данного класса автоматов. Запропоновано використовувати представлення методів синтезу мікропрограмного автомата з операційним автоматом переходів у вигляді структури, блоки якої відповідають елементам математичної моделі автомата. Розроблено п’ять структур, що враховують відмінності у вхідних даних і результатах методів синтезу. Ці й подібні структури можуть бути використані для класифікації теперішніх та розроблюваних у майбутньому методів синтезу цього класу автоматів. The authors propose to use the representation of methods of synthesis of a microprogram finite-state machine with datapath of transitions in the form of a structure whose blocks correspond to elements of the mathematical model of the finite state machine. Five structures have been developed that take into account differences in the initial data and the results of the synthesis methods. These and similar structures can be used to classify the available and future methods of synthesis of this class of finite-state machines ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кібернетика Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов Структурна класифікація методів синтезу мікропрограмного автомата з операційним автоматом переходів Structural classification of the methods of synthesis of a microprogram finite-state machine with datapath of transitions Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов |
| spellingShingle |
Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов Бабаков, Р.М. Баркалов, А.А. Кібернетика |
| title_short |
Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов |
| title_full |
Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов |
| title_fullStr |
Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов |
| title_full_unstemmed |
Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов |
| title_sort |
структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов |
| author |
Бабаков, Р.М. Баркалов, А.А. |
| author_facet |
Бабаков, Р.М. Баркалов, А.А. |
| topic |
Кібернетика |
| topic_facet |
Кібернетика |
| publishDate |
2019 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Структурна класифікація методів синтезу мікропрограмного автомата з операційним автоматом переходів Structural classification of the methods of synthesis of a microprogram finite-state machine with datapath of transitions |
| description |
Предложено использовать представление методов синтеза микропрограммного автомата с операционным автоматом переходов в виде структуры, блоки которой соответствуют элементам математической модели автомата. Разработаны пять структур, учитывающих различия в исходных данных и результатах методов синтеза. Описанные и подобные структуры можно использовать для классификации существующих и разрабатываемых в будущем методов синтеза данного класса автоматов.
Запропоновано використовувати представлення методів синтезу мікропрограмного автомата з операційним автоматом переходів у вигляді структури, блоки якої відповідають елементам математичної моделі автомата. Розроблено п’ять структур, що враховують відмінності у вхідних даних і результатах методів синтезу. Ці й подібні структури можуть бути використані для класифікації теперішніх та розроблюваних у майбутньому методів синтезу цього класу автоматів.
The authors propose to use the representation of methods of synthesis of a microprogram finite-state machine with datapath of transitions in the form of a structure whose blocks correspond to elements of the mathematical model of the finite state machine. Five structures have been developed that take into account differences in the initial data and the results of the synthesis methods. These and similar structures can be used to classify the available and future methods of synthesis of this class of finite-state machines
|
| issn |
1019-5262 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/180843 |
| citation_txt |
Структурная классификация методов синтеза микропрограммного автомата с операционным автоматом переходов / Р.М. Бабаков, А.А. Баркалов // Кибернетика и системный анализ. — 2019. — Т. 55, № 2. — С. 3-9. — Бібліогр.: 12 назв. — рос. |
| work_keys_str_mv |
AT babakovrm strukturnaâklassifikaciâmetodovsintezamikroprogrammnogoavtomatasoperacionnymavtomatomperehodov AT barkalovaa strukturnaâklassifikaciâmetodovsintezamikroprogrammnogoavtomatasoperacionnymavtomatomperehodov AT babakovrm strukturnaklasifíkacíâmetodívsintezumíkroprogramnogoavtomatazoperacíinimavtomatomperehodív AT barkalovaa strukturnaklasifíkacíâmetodívsintezumíkroprogramnogoavtomatazoperacíinimavtomatomperehodív AT babakovrm structuralclassificationofthemethodsofsynthesisofamicroprogramfinitestatemachinewithdatapathoftransitions AT barkalovaa structuralclassificationofthemethodsofsynthesisofamicroprogramfinitestatemachinewithdatapathoftransitions |
| first_indexed |
2025-11-25T21:29:36Z |
| last_indexed |
2025-11-25T21:29:36Z |
| _version_ |
1850551665795530752 |
| fulltext |
Ð.Ì. ÁÀÁÀÊÎÂ, À.À. ÁÀÐÊÀËÎÂ
ÓÄÊ 004.2 ÑÒÐÓÊÒÓÐÍÀß ÊËÀÑÑÈÔÈÊÀÖÈß ÌÅÒÎÄÎÂ
ÑÈÍÒÅÇÀ ÌÈÊÐÎÏÐÎÃÐÀÌÌÍÎÃÎ ÀÂÒÎÌÀÒÀ
Ñ ÎÏÅÐÀÖÈÎÍÍÛÌ ÀÂÒÎÌÀÒÎÌ ÏÅÐÅÕÎÄÎÂ
Àííîòàöèÿ. Ïðåäëîæåíî èñïîëüçîâàòü ïðåäñòàâëåíèå ìåòîäîâ ñèíòåçà ìèê-
ðîïðîãðàììíîãî àâòîìàòà ñ îïåðàöèîííûì àâòîìàòîì ïåðåõîäîâ â âèäå
ñòðóêòóðû, áëîêè êîòîðîé ñîîòâåòñòâóþò ýëåìåíòàì ìàòåìàòè÷åñêîé ìîäåëè
àâòîìàòà. Ðàçðàáîòàíû ïÿòü ñòðóêòóð, ó÷èòûâàþùèõ ðàçëè÷èÿ â èñõîäíûõ
äàííûõ è ðåçóëüòàòàõ ìåòîäîâ ñèíòåçà. Îïèñàííûå è ïîäîáíûå ñòðóêòóðû
ìîæíî èñïîëüçîâàòü äëÿ êëàññèôèêàöèè ñóùåñòâóþùèõ è ðàçðàáàòûâàåìûõ
â áóäóùåì ìåòîäîâ ñèíòåçà äàííîãî êëàññà àâòîìàòîâ.
Êëþ÷åâûå ñëîâà: ìèêðîïðîãðàììíûé àâòîìàò, îïåðàöèîííûé àâòîìàò ïå-
ðåõîäîâ, ìåòîä ñèíòåçà, êëàññèôèêàöèÿ.
ÂÂÅÄÅÍÈÅ
Õàðàêòåðèñòèêè ñîâðåìåííûõ âû÷èñëèòåëüíûõ ñèñòåì âî ìíîãîì îïðåäåëÿþò-
ñÿ óñòðîéñòâîì óïðàâëåíèÿ (ÓÓ), êîîðäèíèðóþùèì ðàáîòó âñåõ óçëîâ ñèñòå-
ìû [1]. Ðåàëèçàöèÿ ÓÓ â âèäå ìèêðîïðîãðàììíîãî àâòîìàòà (ÌÏÀ) ïîçâîëÿåò
äîáèòüñÿ ìàêñèìàëüíîãî áûñòðîäåéñòâèÿ ñõåìû óñòðîéñòâà ïðè ìàêñèìàëüíûõ
àïïàðàòóðíûõ çàòðàòàõ [2, 3]. Ïðè ýòîì àêòóàëüíà çàäà÷à ìèíèìèçàöèè àïïà-
ðàòóðíûõ çàòðàò â ëîãè÷åñêîé ñõåìå ÌÏÀ, îäíèì èç ñïîñîáîâ ðåøåíèÿ êîòî-
ðîé ÿâëÿåòñÿ ðàçðàáîòêà íîâûõ ñòðóêòóð ÌÏÀ è ìåòîäîâ èõ ñèíòåçà [3–5].
ÌÏÀ ñ îïåðàöèîííûì àâòîìàòîì ïåðåõîäîâ (ÌÏÀ ñ ÎÀÏ) [6] — îäíà èç èçâåñ-
òíûõ ñòðóêòóð ÌÏÀ, ôóíêöèÿ ïåðåõîäîâ â êîòîðîé ðàçäåëÿåòñÿ íà ìíîæåñòâî ÷àñòè÷-
íûõ ôóíêöèé, ðåàëèçóþùèõ ñîáñòâåííîå ïîäìíîæåñòâî àâòîìàòíûõ ïåðåõîäîâ. Â îá-
ùåì ñëó÷àå êàæäàÿ ÷àñòè÷íàÿ ôóíêöèÿ èìïëåìåíòèðóåòñÿ îòäåëüíîé êîìáèíàöèîí-
íîé ñõåìîé, àïïàðàòóðíûå çàòðàòû â êîòîðîé íå çàâèñÿò èëè íåçíà÷èòåëüíî çàâèñÿò îò
êîëè÷åñòâà ðåàëèçóåìûõ åãî àâòîìàòíûõ ïåðåõîäîâ. Óìåíüøåíèå êîëè÷åñòâà ÷àñòè÷-
íûõ ôóíêöèé ñïîñîáñòâóåò ñíèæåíèþ àïïàðàòóðíûõ çàòðàò â ñõåìå ôîðìèðîâàíèÿ
ïåðåõîäîâ ÌÏÀ. Ñîâîêóïíîñòü êîìáèíàöèîííûõ ñõåì ÷àñòè÷íûõ ôóíêöèé ïåðåõî-
äîâ èìååò ñòðóêòóðíóþ îðãàíèçàöèþ, ñõîæóþ ñ îïåðàöèîííûì àâòîìàòîì.
 ðàáîòå [7] ðàññìîòðåíû îáùèå âîïðîñû ñèíòåçà ÌÏÀ ñ ÎÀÏ è îñîáîå
âíèìàíèå óäåëåíî ïîòåíöèàëüíîé âîçìîæíîñòè ðàçðàáîòêè ìíîæåñòâà ìåòîäîâ
ñèíòåçà, îòëè÷àþùèõñÿ èñõîäíûìè äàííûìè è ðåçóëüòàòàìè.  íàñòîÿùåé ðàáî-
òå ïðåäëîæåí ñïîñîá êëàññèôèêàöèè ìåòîäîâ ñèíòåçà ÌÏÀ ñ ÎÀÏ, îñíîâàííûé
íà ñòðóêòóðíîì ïðåäñòàâëåíèè ïðîöåññà ñèíòåçà.
ÌÈÊÐÎÏÐÎÃÐÀÌÌÍÛÉ ÀÂÒÎÌÀÒ Ñ ÎÏÅÐÀÖÈÎÍÍÛÌ ÀÂÒÎÌÀÒÎÌ ÏÅÐÅÕÎÄÎÂ
Ñòðóêòóðíàÿ ñõåìà ÌÏÀ ñ ÎÀÏ [6] ïðåäñòàâëåíà íà ðèñ. 1. Ðàññìîòðèì
îñíîâíûå åå áëîêè.
Áëîê ÎÀÏ (îïåðàöèîííûé àâòîìàò ïåðåõîäîâ) ðåàëèçóåò ìíîæåñòâî îïåðà-
öèé ïåðåõîäîâ (ÎÏ), èñïîëüçóåìûõ äëÿ ïðåîáðàçîâàíèÿ êîäîâ ñîñòîÿíèé àâòî-
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 3
� Ð.Ì. Áàáàêîâ, À.À. Áàðêàëîâ, 2019
ìàòà. Òåêóùåå ñîñòîÿíèå õðàíèòñÿ
â ðåãèñòðå ïàìÿòè (ÐÏ), êîòîðûé ÿâ-
ëÿåòñÿ ÷àñòüþ ÎÀÏ. Ëþáàÿ îïåðàöèÿ
â ÎÀÏ âûïîëíÿåòñÿ íàä ñîäåðæèìûì
ÐÏ è ïîìåùàåò ðåçóëüòàò â íåãî.
ÎÀÏ ðåàëèçóåò ôóíêöèþ ïåðåõîäîâ
d, êîòîðàÿ îïèñûâàåòñÿ âûðàæåíèåì
T d T X Z� ( , , ),
ãäå T — êîä ñîñòîÿíèÿ àâòîìàòà, X — ìíîæåñòâî âõîäíûõ ñèãíàëîâ, Z —
êîä ÎÏ.
Áëîê Z ïðåäíàçíà÷åí äëÿ ôîðìèðîâàíèÿ êîäà Z îïåðàöèè, âûïîëíÿåìîé
ÎÀÏ â òåêóùåì òàêòå ðàáîòû óñòðîéñòâà. Ôóíêöèÿ áëîêà Z îïèñûâàåòñÿ
âûðàæåíèåì:
Z Z T X� ( , ). (1)
 ñîîòâåòñòâèè ñ (1) îòäåëüíóþ ÎÏ ìîæíî ñîïîñòàâèòü êàæäîìó ïåðåõîäó àâòîìàòà.
Áëîê ÑÔÌÎ (ñõåìà ôîðìèðîâàíèÿ ìèêðîîïåðàöèé) ôîðìèðóåò ñèñòåìó
ìèêðîîïåðàöèé (âûõîäíûõ ñèãíàëîâ) àâòîìàòà, îïðåäåëÿåìóþ Y Y T X� ( , ) â ñëó-
÷àå àâòîìàòà Ìèëè è Y Y T� ( ) â ñëó÷àå àâòîìàòà Ìóðà. Íàëè÷èå â ñòðóêòóðå
ÌÏÀ ñ ÎÀÏ ñâÿçè, ïîêàçàííîé íà ðèñ. 1 ïóíêòèðîì, ïîçâîëÿåò ñ÷èòàòü äàííóþ
ñòðóêòóðó àâòîìàòîì Ìèëè, à åñëè ñâÿçè íå ñóùåñòâóåò — àâòîìàòîì Ìóðà.
 ðàáîòå [8] ïðåäëîæåíà ìàòåìàòè÷åñêàÿ ìîäåëü ÌÏÀ ñ ÎÀÏ, îñíîâàííàÿ
íà àëãåáðàè÷åñêîé èíòåðïðåòàöèè ÌÏÀ ñ ÎÀÏ [9] è ÿâëÿþùàÿñÿ ñèñòåìîé èçî-
ìîðôèçìîâ
G G G
G G G
G G G
G
I d
I d
I dNI NI NI
�
�
�
�
1 1 1
2 2 2
� �
� �
� �
�
;
;
;
��������
G
G G
d
l
;
.� �
�
�
�
�
�
�
�
�
�
(2)
 ñèñòåìå (2) ïåðâûå N I èçîìîðôèçìîâ âûðàæàþò ýêâèâàëåíòíîñòü ìåæäó
àáñòðàêòíûì, ïðîìåæóòî÷íûì è ñòðóêòóðíûì ïðåäñòàâëåíèÿìè ÷àñòè÷íûõ
ôóíêöèé ïåðåõîäîâ àâòîìàòà (àëãåáðû G
i� , GI i
è Gdi
ñîîòâåòñòâåííî). Ïðåä-
ïîñëåäíèé èçîìîðôèçì ìåæäó àáñòðàêòíûì (àëãåáðà G�) è ñòðóêòóðíûì (àëãåáðà
Gd ) ïðåäñòàâëåíèÿìè ôóíêöèè ïåðåõîäîâ àâòîìàòà îáåñïå÷èâàåò ýêâèâàëåíòíîñòü
ñòðóêòóðíûõ (äâîè÷íûõ) êîäîâ ñîñòîÿíèé íåçàâèñèìî îò êîëè÷åñòâà N I ÷àñòè÷-
íûõ ôóíêöèé ïåðåõîäîâ. Ïîñëåäíèé èçîìîðôèçì ìåæäó àáñòðàêòíûì (àëãåáðà G �)
è ñòðóêòóðíûì (àëãåáðà Gl ) ïðåäñòàâëåíèÿìè ôóíêöèè âûõîäîâ àâòîìàòà îáåñïå-
÷èâàåò èñïîëüçîâàíèå îäíèõ è òåõ æå ñòðóêòóðíûõ êîäîâ ñîñòîÿíèé â ôóíêöèÿõ
ïåðåõîäîâ è âûõîäîâ ÌÏÀ.
ÑÒÐÓÊÒÓÐÍÀß ÊËÀÑÑÈÔÈÊÀÖÈß ÌÅÒÎÄÎÂ ÑÈÍÒÅÇÀ ÌÏÀ Ñ ÎÀÏ
 ñîîòâåòñòâèè ñ [8, 9] â ñèñòåìå èçîìîðôèçìîâ (2) ìîæíî âûäåëèòü òðè àë-
ãåáðàè÷åñêèõ óðîâíÿ: àáñòðàêòíûõ, ïðîìåæóòî÷íûõ è ñòðóêòóðíûõ àëãåáð.
Íà óðîâíå àáñòðàêòíûõ àëãåáð ðàñïîëîæåíû ýëåìåíòû, îòíîñÿùèåñÿ
ê àáñòðàêòíîìó àâòîìàòó: àáñòðàêòíàÿ àëãåáðà ïåðåõîäîâ G A Z� ��
{ } { }, , è
àáñòðàêòíàÿ àëãåáðà âûõîäîâ G A Z W� ��
{ } { }, , , . Çäåñü è äàëåå ïåðâàÿ êîìïî-
íåíòà àëãåáðû ñîäåðæèò åå íîñèòåëè, âòîðàÿ — ñèãíàòóðó [9].
Ýëåìåíòàìè óðîâíÿ ïðîìåæóòî÷íûõ àëãåáð ÿâëÿþòñÿ ìíîæåñòâî
K A K A K AI I I I INI NI
( ) ( ), , ( )� { }
1 1
� ïðîìåæóòî÷íûõ êîäîâ ñîñòîÿíèé, ìíîæåñòâî
4 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2
X
YÑÔÌÎÎÀÏZ
T
T
Z
Ðèñ. 1. Ñòðóêòóðíàÿ ñõåìà ÌÏÀ ñ ÎÀÏ
O O O N I
� { }1, ,� îïåðàöèé ïåðåõîäîâ è ìíîæåñòâî K Z K Z
I I I( ) ( ),� {
1 1
�
� , ( )K ZI INI NI
} ïðîìåæóòî÷íûõ êîäîâ âõîäíûõ ñèãíàëîâ. Äàííûå ýëåìåíòû îá-
ðàçóþò ìíîæåñòâî ïðîìåæóòî÷íûõ àëãåáð ïåðåõîäîâ G G G
I I I NI
� { }
1
, ,� .
Ýëåìåíòàìè óðîâíÿ ñòðóêòóðíûõ àëãåáð ÿâëÿþòñÿ ìíîæåñòâî K AS ( ) ñòðóê-
òóðíûõ (äâîè÷íûõ) êîäîâ ñîñòîÿíèé, ìíîæåñòâî K ZS ( ) ñòðóêòóðíûõ (äâîè÷íûõ)
âõîäíûõ ñèãíàëîâ è ñòðóêòóðíàÿ ôóíêöèÿ ïåðåõîäîâ d, îáðàçóþùèå ñòðóêòóð-
íóþ àëãåáðó ïåðåõîäîâ G K A K Z dd S S�
{ } { }( ), ( ) , . Íà ýòîì æå óðîâíå íàõî-
äèòñÿ ñòðóêòóðíàÿ àëãåáðà âûõîäîâ G K A K Z K W ll S S S�
{ } { }( ), ( ), ( ) , .
Íåîäíîçíà÷íîñòü â ïîñëåäîâàòåëüíîñòè è ñïîñîáàõ ôîðìèðîâàíèÿ ýëåìåíòîâ
ñèñòåìû èçîìîðôèçìîâ (2) óñëîæíÿåò ïðîöåññ ðàçðàáîòêè ôîðìàëüíûõ ìåòîäîâ
ñèíòåçà ÌÏÀ ñ ÎÀÏ. Ïîíèìàíèþ ïðîöåññà ñèíòåçà ìîãóò ñïîñîáñòâîâàòü ïðèåìû,
çàèìñòâîâàííûå èç ñèñòåìíîãî àíàëèçà, íàïðèìåð êîãíèòèâíûé àíàëèç, ïðåäïîëàãà-
þùèé ïðåäñòàâëåíèå íåêîòîðîãî ïðîöåññà â ôîðìå òàê íàçûâàåìûõ êîãíèòèâíûõ
êàðò, îïèñûâàþùèõ ñòðóêòóðó âçàèìîñâÿçàííûõ ÿâëåíèé èññëåäóåìîé ñèòóàöèè
[10, 11]. Ñóòü äàííîãî ïîäõîäà ñâîäèòñÿ ê ïðåäñòàâëåíèþ íåêîòîðîé ñèñòåìû â âèäå
îðèåíòèðîâàííîãî ãðàôà, âåðøèíàìè êîòîðîãî ÿâëÿþòñÿ âûäåëÿåìûå ýëåìåíòû ñèñòå-
ìû, à ðåáðà âûðàæàþò ïðè÷èííî-ñëåäñòâåííûå ñâÿçè ìåæäó íèìè [12].
Ïóñòü â êà÷åñòâå èñõîäíûõ äàííûõ äëÿ ñèíòåçà ÌÏÀ ñ ÎÀÏ çàäàíî ìíîæåñòâî
O O O N I
� { }1, ,� îïåðàöèé ïåðåõîäîâ.  ýòîì ñëó÷àå ïðîìåæóòî÷íûå êîäû ñîñòîÿ-
íèé K AI ( ) è ïðîìåæóòî÷íûå êîäû âõîäíûõ ñèãíàëîâ K ZI ( ) ôîðìèðóþòñÿ íà îñíî-
âàíèè ìíîæåñòâà O è àáñòðàêòíîé àëãåáðû ïåðåõîäîâ G� . Âëèÿíèå ìíîæåñòâà O è
àëãåáðû G� íà ýëåìåíòû K AI ( ) è K ZI ( ) îòîáðàæåíî íà ðèñ. 2, à. Çäåñü ýëåìåíòû
ñèñòåìû (2) ïîêàçàíû â âèäå âåðøèí ãðàôà, ñîåäèíåííûõ äóãàìè. Êàæäàÿ äóãà ÿâëÿ-
åòñÿ ïðèçíàêîì òîãî, ÷òî ýëåìåíò ñèñòåìû (2) èç «èñõîäÿùåé» âåðøèíû èñïîëüçóåò-
ñÿ íåêîòîðûì îáðàçîì ïðè ôîðìèðîâàíèè ýëåìåíòà âî «âõîäÿùåé» âåðøèíå.
Åñëè ìíîæåñòâî O íå ÿâëÿåòñÿ «æåñòêî» çàäàííûì, îíî ôîðìèðóåòñÿ ñîãëàñ-
íî â òîì ÷èñëå çàäàííîìó àëãîðèòìó óïðàâëåíèÿ, èíòåðïðåòèðóåìîãî àâòîìàòîì.
 ñèñòåìå èçîìîðôèçìîâ (2) ñòðóêòóðà èíòåðïðåòèðóåìîãî àëãîðèòìà ôîðìàëü-
íî ïðåäñòàâëåíà àáñòðàêòíîé àëãåáðîé ïåðåõîäîâ. Åå âëèÿíèå íà ôîðìèðîâàíèå
ìíîæåñòâà îïåðàöèé ïåðåõîäîâ ìîæíî ïîêàçàòü, äîáàâèâ äóãó îò âåðøèíû G�
ê âåðøèíå O (ñì. ðèñ. 2, á).
Åñëè äëÿ èíòåðïðåòèðóåìîãî
àëãîðèòìà äîïóñòèìû êàêèå-ëèáî
ïðåîáðàçîâàíèÿ, èõ ìîæíî ãðàôè-
÷åñêè ïðåäñòàâèòü äóãàìè, íàïðàâ-
ëåííûìè ê âåðøèíå G� îò äðóãèõ
âåðøèí ãðàôà. Íàïðèìåð, ðåáðî îò
âåðøèíû O ê âåðøèíå G� îòðàæàåò
âëèÿíèå íà àáñòðàêòíóþ àëãåáðó
ìíîæåñòâà îïåðàöèé ïåðåõîäîâ (ñì.
ðèñ. 2, â), à îäíîâðåìåííîå ñóùåñ-
òâîâàíèå ðåáðà îò âåðøèíû G� ê
âåðøèíå O îçíà÷àåò, ÷òî ìíîæåñòâî
O íå ÿâëÿåòñÿ èçíà÷àëüíî çàäàííûì
è ôîðìèðóåòñÿ â ïðîöåññå ñèíòåçà
àâòîìàòà.  îáùåì ñëó÷àå íàëè÷èå ó
êàêîé-ëèáî âåðøèíû âõîäÿùåãî
ðåáðà ïîäòâåðæäàåò âîçìîæíîñòü
ìîäèôèêàöèè ýëåìåíòà, ñîîòâå-
òñòâóþùåãî äàííîé âåðøèíå, â ïðî-
öåññå ñèíòåçà ÌÏÀ ñ ÎÀÏ.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 5
Ðèñ. 2. Ïðèìåðû ãðàôè÷åñêîãî ïðåäñòàâëåíèÿ
âçàèìíîãî âëèÿíèÿ ýëåìåíòîâ ñèñòåìû èçîìîð-
ôèçìîâ (2) â ïðîöåññå ñèíòåçà ÌÏÀ ñ ÎÀÏ
K AI ( )
K AI ( )
K AI ( )
K ZI ( )
K ZI ( )
K ZI ( )
G
�
G
�
G
�
O
O
O
a
á
â
Òîïîëîãèÿ ãðàôà (ñì. ðèñ. 2, â)
ïîçâîëÿåò âûäåëèòü â íåì îïðåäå-
ëåííûå ðàíåå óðîâíè àáñòðàêòíûõ
àëãåáð (âåðøèíà G�) è ïðîìåæóòî÷-
íûõ àëãåáð (âåðøèíû K AI ( ), O è
K ZI ( )). Äîáàâèì â ãðàô óðîâåíü
ñòðóêòóðíûõ àëãåáð, ïðåäñòàâèâ
åãî âåðøèíàìè K AS ( ), � è K ZS ( ).
Äîáàâëåííûå âåðøèíû ñîåäèíèì ñ
îñòàëüíûìè âåðøèíàìè ãðàôà è
ìåæäó ñîáîé òàê, êàê ïîêàçàíî íà
ðèñ. 3. Ïîëó÷åííûé ãðàô ïîçâîëÿåò
óòâåðæäàòü ñëåäóþùåå:
1) íàëè÷èå ðåáðà, âõîäÿùåãî â âåðøèíó O, îçíà÷àåò, ÷òî ìíîæåñòâî îïåðàöèé ïå-
ðåõîäîâ O íå ÿâëÿåòñÿ «æåñòêî» çàäàííûì è ôîðìèðóåòñÿ â ïðîöåññå ñèíòåçà ÌÏÀ;
2) ðåáðà, âõîäÿùèå â ñîîòâåòñòâóþùèå âåðøèíû, îçíà÷àþò, ÷òî ïðîìåæó-
òî÷íûå è ñòðóêòóðíûå êîäû ñîñòîÿíèé è âõîäíûõ ñèãíàëîâ íå ÿâëÿþòñÿ «æåñ-
òêî» çàäàííûìè è ôîðìèðóþòñÿ â ïðîöåññå ñèíòåçà ÌÏÀ;
3) ðåáðî, âõîäÿùåå â âåðøèíó G� , äëÿ àëãîðèòìà, èìïëåìåíòèðóåìîãî ñèí-
òåçèðóåìûì ÌÏÀ, îçíà÷àåò, ÷òî äîïóñòèìû îïðåäåëåííûå ïðåîáðàçîâàíèÿ;
4) íåäîñòèæèìîñòü âåðøèíû O èç âåðøèí K AS ( ) è K ZS ( ) îçíà÷àåò, ÷òî ôîð-
ìèðîâàíèå ìíîæåñòâà îïåðàöèé ïåðåõîäîâ ÿâëÿåòñÿ ïåðâè÷íûì ïî îòíîøåíèþ
ê ôîðìèðîâàíèþ ìíîæåñòâ ñòðóêòóðíûõ êîäîâ ñîñòîÿíèé è âõîäíûõ ñèãíàëîâ;
5) åñëè ó âåðøèíû d íå èìååòñÿ èñõîäÿùèõ ðåáåð, òî êîíå÷íûì ýòàïîì ñèí-
òåçà ÿâëÿåòñÿ ôîðìèðîâàíèå ñòðóêòóðíîé ôóíêöèè ïåðåõîäîâ d.
Ãðàô, ïðèâåäåííûé íà ðèñ. 3, íå îòîáðàæàåò êîíêðåòíûé ìåòîä ñèíòåçà, ïî-
ñêîëüêó íå ñîäåðæèò èíôîðìàöèè îá ýòàïàõ ñèíòåçà, èõ ïîñëåäîâàòåëüíîñòè è
ðåàëèçàöèè. Îäíàêî äàííûé ãðàô ñîäåðæèò èíôîðìàöèþ î ñëåäóþùèõ ýëåìåí-
òàõ ñèñòåìû (2): íå ôîðìèðóþùèõñÿ â ïðîöåññå ñèíòåçà è ÿâëÿþùèõñÿ èñõîäíû-
ìè äàííûìè (ñîîòâåòñòâóþùèå âåðøèíû íå èìåþò âõîäÿùèõ äóã), ôîðìèðóþ-
ùèõñÿ â ïðîöåññå ñèíòåçà (ñîîòâåòñòâóþùèå èì âåðøèíû èìåþò õîòÿ áû îäíó
âõîäÿùóþ äóãó), à òàêæå èíôîðìàöèþ îá ýëåìåíòàõ, îêàçûâàþùèõ íåïîñðå-
äñòâåííîå âëèÿíèå íà ôîðìèðîâàíèå òîãî èëè èíîãî ýëåìåíòà ñèñòåìû (2) (îïðå-
äåëÿåòñÿ äóãàìè ãðàôà), îêàçûâàþùèõ îïîñðåäîâàííîå âëèÿíèå íà ôîðìèðîâà-
íèå òîãî èëè èíîãî ýëåìåíòà ñèñòåìû (2) (îïðåäåëÿåòñÿ äîñòèæèìîñòüþ ñîîòâå-
òñòâóþùåé âåðøèíû èç äðóãèõ âåðøèí) è èñïîëüçóåìûõ â çàêëþ÷èòåëüíîì
ýòàïå ñèíòåçà (ñîîòâåòñòâóþùèå èì âåðøèíû íå èìåþò èñõîäÿùèõ äóã).
Äàííóþ èíôîðìàöèþ ìîæíî èñïîëüçîâàòü ïðè ðàçðàáîòêå è êëàññèôèêàöèè
ìåòîäîâ ñèíòåçà ÌÏÀ ñ ÎÀÏ. Âàðèàòèâíîñòü â ïîäõîäàõ ê ôîðìèðîâàíèþ ìíî-
æåñòâà ýòàïîâ ñèíòåçà, èõ ïîñëåäîâàòåëüíîñòè è ðåàëèçàöèè ïîçâîëÿåò îòîæäåñ-
òâèòü ñ ðàññìàòðèâàåìûì ãðàôîì ìíîæåñòâî ìåòîäîâ ñèíòåçà.
Çàìåòèì, ÷òî ãðàô (ñì. ðèñ. 3) ñîäåðæèò íå âñå ýëåìåíòû ñèñòåìû èçîìîð-
ôèçìîâ (2). Äîáàâèì â ãðàô âåðøèíû, ñîîòâåòñòâóþùèå ýëåìåíòàì G � è Gl , ñîå-
äèíèâ èõ ñ îñòàëüíûìè âåðøèíàìè ãðàôà ñëåäóþùèì îáðàçîì:
1) äóãà, íàïðàâëåííàÿ îò âåðøèíû O ê âåðøèíå G� , äîïóñêàåò ìîäèôèêàöèþ
àáñòðàêòíîé àëãåáðû ïåðåõîäîâ G� . Ïîñêîëüêó íîñèòåëè A è Z àëãåáðû G� ÿâëÿ-
þòñÿ îäíîâðåìåííî íîñèòåëÿìè àáñòðàêòíîé àëãåáðû âûõîäîâ G �, èõ èçìåíåíèå
â ðàìêàõ àëãåáðû G� âëå÷åò ñîîòâåòñòâóþùèå èçìåíåíèÿ àëãåáðû G �. Äàííîå
ñâîéñòâî ìîæåò îòîáðàæàòüñÿ äóãîé, íàïðàâëåííîé îò âåðøèíû G� ê âåðøèíå G �;
2) ñòðóêòóðíàÿ àëãåáðà âûõîäîâ Gl ôîðìèðóåòñÿ â ñîîòâåòñòâèè ñ àáñòðàê-
òíîé àëãåáðîé âûõîäîâ G �. Òàêæå ïðè ôîðìèðîâàíèè Gl äîëæíû ó÷èòûâàòüñÿ
ñòðóêòóðíûå êîäû ñîñòîÿíèé K AS ( ), à â ñëó÷àå àâòîìàòà Ìèëè — è ñòðóêòóð-
íûå êîäû âõîäíûõ ñèãíàëîâ K ZS ( ). Âëèÿíèå äàííûõ ýëåìåíòîâ íà ýëåìåíò Gl
îòîáðàæåíî íà ãðàôå ñîîòâåòñòâóþùèìè äóãàìè.
6 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2
Ðèñ. 3. Ïðèìåð ãðàôè÷åñêîãî ïðåäñòàâëåíèÿ
âçàèìíîãî âëèÿíèÿ ýëåìåíòîâ òðåõ àëãåáðàè÷åñêèõ
óðîâíåé ñèñòåìû èçîìîðôèçìîâ (2)
K AI ( )
K AS ( )
K ZI ( )
K ZS ( )
G
�
O
d
Ïîëó÷åííûé â ðåçóëüòàòå ãðàô
ïîêàçàí íà ðèñ. 4. Îòìåòèì, ÷òî â
êîíòåêñòå ñèíòåçà ÌÏÀ ñ ÎÀÏ íå-
öåëåñîîáðàçíî ðàññìàòðèâàòü äàí-
íûé ãðàô êàê ìàòåìàòè÷åñêèé îáú-
åêò ââèäó íåïðèìåíåíèÿ ê íåìó êà-
êèõ-ëèáî ìåòîäîâ àíàëèçà èëè
ïðåîáðàçîâàíèÿ ãðàôîâ. Âûäåëåíèå
íà ãðàôå òðåõ àëãåáðàè÷åñêèõ óðîâ-
íåé ïîçâîëÿåò ðàññìàòðèâàòü åãî êàê
íåêîòîðóþ ñòðóêòóðó, ïîíèìàÿ ïîä
äàííûì òåðìèíîì ñîâîêóïíîñòü âçà-
èìîðàñïîëîæåíèÿ è óñòîé÷èâûõ ñâÿçåé ñâîèõ ñîñòàâíûõ ÷àñòåé (áëîêîâ ñòðóêòó-
ðû). Íàçîâåì ãðàô, èçîáðàæåííûé íà ðèñ. 4, ñòðóêòóðîé ïðîöåññà ñèíòåçà ÌÏÀ ñ
ÎÀÏ ñ èçìåíÿåìîé àáñòðàêòíîé àëãåáðîé ïåðåõîäîâ è îáîçíà÷èì åå M1.
Ìíîæåñòâî ìåòîäîâ, ïðåäñòàâëåííûõ ñòðóêòóðîé M1, èìåþò íåêîòîðûå îáùèå
ñâîéñòâà, îïðåäåëÿåìûå äàííîé ñòðóêòóðîé.  ðàññìàòðèâàåìîì ñëó÷àå, åñëè íå èìå-
åòñÿ áëîêîâ áåç âõîäÿùèõ ñâÿçåé, çíà÷èò, íè îäèí èç ýëåìåíòîâ ñèñòåìû (2) (â òîì
÷èñëå àáñòðàêòíûå àëãåáðû ïåðåõîäîâ è âûõîäîâ) íå ÿâëÿåòñÿ «æåñòêî» çàäàííûì è
ôîðìèðóåòñÿ â ïðîöåññå ñèíòåçà àâòîìàòà.
Òðåáîâàíèÿ ê ïðîöåññó ñèíòåçà, îïðåäåëÿåìûå ñòðóêòóðîé M1, íå ÿâëÿþòñÿ
åäèíñòâåííî âîçìîæíûìè. Ïóñòü îäíî èç òðåáîâàíèé — íåäîïóñòèìîñòü ëþáûõ
èçìåíåíèé àáñòðàêòíîé àëãåáðû ïåðåõîäîâ ïðè îäíîâðåìåííîì èçìåíåíèè
îñòàëüíûõ ýëåìåíòîâ ñèñòåìû (2).  ýòîì ñëó÷àå ñòðóêòóðà ïðîöåññà ñèíòåçà áó-
äåò ñîîòâåòñòâîâàòü ïîêàçàííîé íà ðèñ. 5. Â äàííîé ñòðóêòóðå áëîê G� íå èìååò
âõîäÿùèõ ñâÿçåé, ÷òî îçíà÷àåò íåâîçìîæíîñòü ìîäèôèêàöèè ñîîòâåòñòâóþùåé
àëãåáðû â ïðîöåññå ñèíòåçà. Íåèçìåíÿåìîñòü G� âëå÷åò íåèçìåííîñòü àáñòðàê-
òíîé àëãåáðû âûõîäîâ G �, âûðàæàþùóþñÿ â îòñóòñòâèè ñâÿçè îò áëîêà G� ê áëî-
êó G �. Â îñòàëüíîì ñòðóêòóðà ïðîöåññà ñèíòåçà ñõîæà ñî ñòðóêòóðîé M1. Íàçî-
âåì ñòðóêòóðó, èçîáðàæåííóþ íà ðèñ. 5, ñòðóêòóðîé ïðîöåññà ñèíòåçà ÌÏÀ
ñ ÎÀÏ ñ ôèêñèðîâàííîé àáñòðàêòíîé àëãåáðîé ïåðåõîäîâ è îáîçíà÷èì åå M 2 .
Íåîáõîäèìî, ÷òîáû â ïðîöåññå
ñèíòåçà ÌÏÀ ñ ÎÀÏ âûïîíÿëèñü
ñëåäóþùèå òðåáîâàíèÿ: ìíîæåñòâî
ìèêðîîïåðàöèé O çàäàíî è íåèçìå-
íÿåìî; ëþáûå èçìåíåíèÿ àëãîðèò-
ìà, èìïëåìåíòèðóåìîãî ÌÏÀ, íå-
äîïóñòèìû. Òîãäà ñòðóêòóðà ïðîöåñ-
ñà ñèíòåçà ïðèìåò âèä, êàê íà ðèñ. 6.
Íàçîâåì åå ñòðóêòóðîé ïðîöåññà ñèí-
òåçà ÌÏÀ ñ ÎÀÏ ñ ôèêñèðîâàííîé
àáñòðàêòíîé àëãåáðîé ïåðåõîäîâ è çà-
äàííûì ìíîæåñòâîì îïåðàöèé ïåðå-
õîäîâ è îáîçíà÷èì M 3 . Åäèíñòâåí-
íûì îòëè÷èåì äàííîé ñòðóêòóðû îò
ñòðóêòóðû M 2 ÿâëÿåòñÿ îòñóòñòâèå
ñâÿçè îò áëîêà G� ê áëîêó O. Â ðå-
çóëüòàòå â ñîñòàâå ìåòîäîâ ñèíòåçà,
îòíîñÿùèõñÿ ê äàííîé ñòðóêòóðå, íå
áóäåò ýòàïà ôîðìèðîâàíèÿ ìíîæåñòâà
îïåðàöèé ïåðåõîäîâ. Ñèíòåç àâòîìàòà
â äàííîì ñëó÷àå ñâåäåòñÿ ê âûáîðó
òàêèõ ïðîìåæóòî÷íûõ è ñòðóêòóðíûõ
êîäîâ ñîñòîÿíèé, ïðè êîòîðûõ ó ðå-
çóëüòèðóþùåé ñõåìû ÌÏÀ ñ ÎÀÏ
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 7
Ðèñ. 5. Ñòðóêòóðà M2 ïðîöåññà ñèíòåçà ÌÏÀ
ñ ÎÀÏ ñ ôèêñèðîâàííîé àáñòðàêòíîé àëãåáðîé
ïåðåõîäîâ
K AI ( )
K AS ( )
K ZI ( )
K ZS ( )
G
�
O
d
G
�
Gl
Ðèñ. 6. Ñòðóêòóðà M3 ïðîöåññà ñèíòåçà ÌÏÀ ñ ÎÀÏ
ñ ôèêñèðîâàííîé àáñòðàêòíîé àëãåáðîé ïåðåõîäîâ
è çàäàííûì ìíîæåñòâîì îïåðàöèé ïåðåõîäîâ
K AI ( )
K AS ( )
K ZI ( )
K ZS ( )
G
�
O
d
G
�
Gl
Ðèñ. 4. Ñòðóêòóðà M1 ïðîöåññà ñèíòåçà ÌÏÀ
ñ ÎÀÏ ñ èçìåíÿåìîé àáñòðàêòíîé àëãåáðîé
ïåðåõîäîâ
K AI ( )
K AS ( )
K ZI ( )
K ZS ( )
G
�
O
d
G
�
Gl
áóäåò ìåíüøå çàòðàò àïïàðàòóðû ïî
ñðàâíåíèþ ñ åå ðåàëèçàöèåé êàíîíè-
÷åñêèì ñïîñîáîì.
Äîïóñòèìîñòü ìîäèôèêàöèè àë-
ãåáðû G� ïðè ôèêñèðîâàííîì ìíî-
æåñòâå ÎÏ ïîðîæäàåò ñòðóêòóðó
ïðîöåññà àëãåáðàè÷åñêîãî ñèíòåçà,
â êîòîðîé ïî ñðàâíåíèþ ñî ñòðóêòó-
ðîé M 3 äîáàâëåíû ñâÿçè îò áëîêà O ê
áëîêó G� è îò áëîêà G� ê áëîêó G �
(ïî àíàëîãèè ñî ñòðóêòóðîé M1
(ñì. ðèñ. 4)). Îáîçíà÷èì M 4 ñòðóêòó-
ðó, èçîáðàæåííóþ íà ðèñ. 7, è íàçîâåì
åå ñòðóêòóðîé ïðîöåññà ñèíòåçà ÌÏÀ
ñ ÎÀÏ ñ èçìåíÿåìîé àáñòðàêòíîé àë-
ãåáðîé ïåðåõîäîâ è çàäàííûì ìíî-
æåñòâîì îïåðàöèé ïåðåõîäîâ.
Îòìåòèì, ÷òî ìåòîä ñèíòåçà
ÌÏÀ ñ ÎÀÏ, ïðåäëîæåííûé â [12],
ìîæíî ñðàâíèòü ñî ñòðóêòóðîé M 4 ,
ïîñêîëüêó îí ïðåäïîëàãàåò èñïîëü-
çîâàíèå ôèêñèðîâàííîãî ìíîæåñòâà
îïåðàöèé ïåðåõîäîâ è âîçìîæíîñòü
ïðåîáðàçîâàíèÿ àëãîðèòìà, èìïëå-
ìåíòèðóåìîãî àâòîìàòîì.
Ïóñòü â êà÷åñòâå èñõîäíûõ äàííûõ äëÿ ïðîöåññà ñèíòåçà èñïîëüçóþòñÿ
ñòðóêòóðíûå êîäû ñîñòîÿíèé è âõîäíûõ ñèãíàëîâ. Ïîäîáíîå òðåáîâàíèå èñêëþ-
÷àåò âîçìîæíîñòü ëþáûõ ìîäèôèêàöèé àëãîðèòìà, ïðèâîäÿùèõ ê èçìåíåíèþ êî-
ëè÷åñòâà ñîñòîÿíèé è âõîäíûõ ñèãíàëîâ. Ñòðóêòóðà ïðîöåññà ñèíòåçà, óäîâëåò-
âîðÿþùàÿ äàííûì òðåáîâàíèÿì, ïðèâåäåíà íà ðèñ. 8. Îáîçíà÷èì ýòó ñòðóêòóðó
M 5 è íàçîâåì åå ñòðóêòóðîé ïðîöåññà ñèíòåçà ñ çàäàííûìè ìíîæåñòâàìè
ñòðóêòóðíûõ êîäîâ ñîñòîÿíèé è âõîäíûõ ñèãíàëîâ.
Íàëè÷èå äâóíàïðàâëåííûõ ñâÿçåé ìåæäó áëîêàìè K AI ( ) è O, à òàêæå áëîêà-
ìè O è K ZI ( ) îçíà÷àåò äîïóñòèìîñòü âçàèìíîãî âëèÿíèÿ äàííûõ ýëåìåíòîâ
â ïðîöåññå èõ ôîðìèðîâàíèÿ. Íàïðèìåð, âîçìîæåí èòåðàöèîííûé ïðîöåññ ôîð-
ìèðîâàíèÿ ìíîæåñòâ K AI ( ) è O, ïðè êîòîðîì ÷àñòè÷íî ñôîðìèðîâàííîå ìíî-
æåñòâî O âëèÿåò íà ôîðìèðîâàíèå ÷àñòè ìíîæåñòâà K AI ( ), íà îñíîâàíèè êîòîðî-
ãî ôîðìèðóåòñÿ ñëåäóþùàÿ ÷àñòü ìíîæåñòâà O è ò.ä.
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåííûé ïîäõîä ê ïðåäñòàâëåíèþ ïðîöåññà ñèíòåçà ÌÏÀ ñ ÎÀÏ â âèäå
ñòðóêòóðû ïðåäíàçíà÷åí äëÿ ãðàôè÷åñêîãî ïðåäñòàâëåíèÿ ðàçäåëåíèÿ ýëåìåíòîâ ñèñ-
òåìû èçîìîðôèçìîâ (2) ïî àëãåáðàè÷åñêèì óðîâíÿì, îïðåäåëåíèÿ îòíîñèòåëüíîé ïî-
ñëåäîâàòåëüíîñòè ôîðìèðîâàíèÿ ýëåìåíòîâ ñèñòåìû (2) è èñïîëüçîâàíèÿ â êà÷åñòâå
îáîáùàþùåé ìîäåëè äëÿ íåêîòîðîãî ìíîæåñòâà ìåòîäîâ ñèíòåçà ÌÏÀ ñ ÎÀÏ.
Ñïîñîáû ñòðóêòóðíîãî ïðåäñòàâëåíèÿ ïðîöåññà ñèíòåçà ÌÏÀ ñ ÎÀÏ íå
îãðàíè÷èâàþòñÿ ñòðóêòóðàìè, ïðèâåäåííûìè íà ðèñ. 4–8. Åñëè êàêîé-ëèáî ìåòîä
àëãåáðàè÷åñêîãî ñèíòåçà íåëüçÿ êëàññèôèöèðîâàòü îäíîé èç ðàññìîòðåííûõ
ñòðóêòóð, âñåãäà èìååòñÿ âîçìîæíîñòü ïîñòðîåíèÿ íîâîé ñòðóêòóðû, îòðàæàþ-
ùåé ïðè÷èííî-ñëåäñòâåííûå ñâÿçè ìåæäó ýëåìåíòàìè ñèñòåìû èçîìîðôèçìîâ (2),
õàðàêòåðíûå äëÿ äàííîãî ìåòîäà.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ãëóøêîâ Â.Ì. Ñèíòåç öèôðîâûõ àâòîìàòîâ. Ìîñêâà: Ôèçìàòãèç, 1962. 476 ñ.
2. Áàðàíîâ Ñ.È. Ñèíòåç ìèêðîïðîãðàììíûõ àâòîìàòîâ. Ëåíèíãðàä: Ýíåðãèÿ, 1979. 232 ñ.
8 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2
Ðèñ. 7. Ñòðóêòóðà M4 ïðîöåññà ñèíòåçà ÌÏÀ
ñ ÎÀÏ ñ èçìåíÿåìîé àáñòðàêòíîé àëãåáðîé
ïåðåõîäîâ è çàäàííûì ìíîæåñòâîì îïåðàöèé
ïåðåõîäîâ
Ðèñ. 8. Ñòðóêòóðà M5 ïðîöåññà ñèíòåçà ÌÏÀ
ñ ÎÀÏ ñ çàäàííûìè ìíîæåñòâàìè ñòðóêòóðíûõ
êîäîâ ñîñòîÿíèé è âõîäíûõ ñèãíàëîâ
K AI ( )
K AS ( )
K ZI ( )
K ZS ( )
G
�
O
d
G
�
Gl
K AI ( )
K AS ( )
K ZI ( )
K ZS ( )
G
�
O
d
G
�
Gl
3. Áàðêàëîâ À.À. Ñèíòåç óñòðîéñòâ óïðàâëåíèÿ íà ïðîãðàììèðóåìûõ ëîãè÷åñêèõ óñòðîéñòâàõ.
Äîíåöê: ÄîíÍÒÓ, 2002. 262 ñ.
4. DeMicheli G. Synthesis and îptimization of digital circuits. New York: McGraw-Hill, 1994. 576 p.
5. Barkalov A., Titarenko L., Kolopienczyk M., Mielcarek K., Bazydlo G. Logic synthesis for
FPGA-based finite state machines. Cham: Springer, 2016. 280 p.
6. Barkalov A.A., Babakov R.M. Operational formation of state codes in microprogram automata.
Cybernetics and Systems Analysis. 2011. Vol. 47, N 2. P. 193–197.
7. Áàáàêîâ Ð.Ì. Àëãåáðàè÷åñêèé ñèíòåç ìèêðîïðîãðàììíîãî àâòîìàòà ñ îïåðàöèîííûì àâòîìàòîì
ïåðåõîäîâ. Èíôîðìàöèîííûå òåõíîëîãèè è êîìïüþòåðíàÿ èíæåíåðèÿ. 2017. Ò. 2, ¹ 39. Ñ. 35–41.
8. Áàáàêîâ Ð.Ì., ßðîø È.Â. Ìàòåìàòè÷åñêàÿ ìîäåëü ìèêðîïðîãðàììíîãî àâòîìàòà ñ îïåðàöèîí-
íûì àâòîìàòîì ïåðåõîäîâ. Ñá. íàó÷íûõ òðóäîâ ÄîíÍÒÓ. Ñåðèÿ «Èíôîðìàòèêà, êèáåðíåòèêà
è âû÷èñëèòåëüíàÿ òåõíèêà». 2016. Âûï. 1 (22). Ñ. 54–57.
9. Barkalov A.A., Babakov R.M. Algebraic interpretation of a microprogram finite-state machine with
datapath of transitions. Cybernetics and Systems Analysis. 2016. Vol. 52, N 2. P. 191–198.
10. Êàòàëåâñêèé Ä.Þ. Îñíîâû èìèòàöèîííîãî ìîäåëèðîâàíèÿ è ñèñòåìíîãî àíàëèçà â óïðàâëå-
íèè. Ìîñêâà: ÌÃÓ, 2011. 312 ñ.
11. Glykas M. Fuzzy cognitive maps: Advances in theory, methodologies. Tools and applications studies
in fuzziness and soft computing. Berlin; Heidelberg: Springer, 2010. Vol. 247. 200 p.
12. Axelford R. Structure of decision: The cognitive maps of political elites. New Jersey: Princeton
University Press, 1976. 400 p.
Íàä³éøëà äî ðåäàêö³¿ 02.04.2018
Ð.Ì. Áàáàêîâ, Î.Î. Áàðêàëîâ
ÑÒÐÓÊÒÓÐÍÀ ÊËÀÑÈÔ²ÊÀÖ²ß ÌÅÒÎIJ ÑÈÍÒÅÇÓ Ì²ÊÐÎÏÐÎÃÐÀÌÍÎÃÎ ÀÂÒÎÌÀÒÀ
Ç ÎÏÅÐÀÖ²ÉÍÈÌ ÀÂÒÎÌÀÒÎÌ ÏÅÐÅÕÎIJÂ
Àíîòàö³ÿ. Çàïðîïîíîâàíî âèêîðèñòîâóâàòè ïðåäñòàâëåííÿ ìåòîä³â ñèíòåçó
ì³êðîïðîãðàìíîãî àâòîìàòà ç îïåðàö³éíèì àâòîìàòîì ïåðåõîä³â ó âèãëÿä³
ñòðóêòóðè, áëîêè ÿêî¿ â³äïîâ³äàþòü åëåìåíòàì ìàòåìàòè÷íî¿ ìîäåë³ àâòîìà-
òà. Ðîçðîáëåíî ï’ÿòü ñòðóêòóð, ùî âðàõîâóþòü â³äì³ííîñò³ ó âõ³äíèõ äàíèõ
³ ðåçóëüòàòàõ ìåòîä³â ñèíòåçó. Ö³ é ïîä³áí³ ñòðóêòóðè ìîæóòü áóòè âèêî-
ðèñòàí³ äëÿ êëàñèô³êàö³¿ òåïåð³øí³õ òà ðîçðîáëþâàíèõ ó ìàéáóòíüîìó ìå-
òîä³â ñèíòåçó öüîãî êëàñó àâòîìàò³â.
Êëþ÷îâ³ ñëîâà: ì³êðîïðîãðàìíèé àâòîìàò, îïåðàö³éíèé àâòîìàò ïåðåõîä³â,
ìåòîä ñèíòåçó, ìàòåìàòè÷íà ìîäåëü, ñòðóêòóðà.
R.M. Babakov, A.A. Barkalov
SSTRUCTURAL CLASSIFICATION OF THE METHODS OF SYNTHESIS
OF A MICROPROGRAM FINITE-STATE MACHINE WITH DATAPATH OF TRANSITIONS
Abstract. The authors propose to use the representation of methods of synthesis
of a microprogram finite-state machine with datapath of transitions in the form
of a structure whose blocks correspond to elements of the mathematical model
of the finite state machine. Five structures have been developed that take into
account differences in the initial data and the results of the synthesis methods.
These and similar structures can be used to classify the available and future
methods of synthesis of this class of finite-state machines.
Keywords: microprogram finite-state machine, datapath of transitions, synthesis
method, mathematical model, structure.
Áàáàêîâ Ðîìàí Ìàðêîâè÷,
êàíäèäàò òåõí. íàóê, äîöåíò, äîöåíò êàôåäðû Äîíåöêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Âàñûëÿ
Ñòóñà, Âèííèöà, e-mail: r.babakov@donnu.edu.ua.
Áàðêàëîâ Àëåêñàíäð Àëåêñàíäðîâè÷,
äîêòîð òåõí. íàóê, ïðîôåññîð, Óíèâåðñèòåò Çåëåíîãóðñêèé, Ïîëüøà,
e-mail: a.barkalov@imei.uz.zgora.pl.
ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 2 9
|