Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов
Предложено использование известного метода уменьшения максисмльного количества существенных входных переменных для снижения аппаратурных затрат в логической схеме микропрограммного автомата с операционным автоматом переходов и заменой входных переменных....
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2018
|
| Schriftenreihe: | Управляющие системы и машины |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/144132 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов / Р.М. Бабаков, А.А. Баркалов // Управляющие системы и машины. — 2018. — № 2. — С. 42-51. — Бібліогр.: 14 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-144132 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1441322025-02-23T20:28:12Z Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов Зменшення максимальної кількості суттєвих вхідних в мікропрограмному автоматі з операційним автоматом переходів Reduction of the maximum mumber of significant input variables in the microprogram finite state machine with datapath of transitions Бабаков, Р.М. Баркалов, А.А. Технические средства информатики Предложено использование известного метода уменьшения максисмльного количества существенных входных переменных для снижения аппаратурных затрат в логической схеме микропрограммного автомата с операционным автоматом переходов и заменой входных переменных. Мета. Метою статті є дослідження нового способу оптимізації апаратурних витрат в мікропрограмному автоматі з операційним автоматом переходів та заміною вхідних змінних. Методи. Запропоновано використовувати метод зменшення максимальної кількості суттєвих вхідних змінних. Метод полягає у додаванні додаткових станів, що призводить до зменшення кількості вхідних сигналів, які аналізуються за один автоматний перехід. Результати. Запропонований підхід не призводить до зміни структури мікропрограмного автомата з операційним автоматом переходів та заміною вхідних змінних. Зменшення апаратурних витрат в операційному автоматі переходів може бути досягнуте завдяки зменшенню кількості операцій переходів. Також можливе додаткове зменшення витрат апаратури в деяких блоках структури за рахунок зменшення проміжних сигналів, що використовуються у структурі автомата для заміни вхідних змінних. Purpose. The purpose of this article is to research a new way for optimization of the hardware expenses in logical circuit of finite state machine with datapath of the input variables transitions and replacement. Methods. It is proposed to use the known method of decreasing the maximum number of significant input variables. The method consists of adding new states, which leads to a decrease in the number of input signals analyzed in one state machine transition. Results. The proposed approach does not lead to a change in the structure of the microprogram finite state machine with datapath of the input variables transitions and replacement. It can be achieved by reducing the number of transition operations used. It is also possible to cut hardware expenses simultaneously in other structure blocks by reducing the number of intermediate signals replacing the finite state machine input signals. 2018 Article Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов / Р.М. Бабаков, А.А. Баркалов // Управляющие системы и машины. — 2018. — № 2. — С. 42-51. — Бібліогр.: 14 назв. — рос. 0130-5395 DOI: https://doi.org/10.15407/usim.2018.02.042 https://nasplib.isofts.kiev.ua/handle/123456789/144132 004.2 ru Управляющие системы и машины application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Технические средства информатики Технические средства информатики |
| spellingShingle |
Технические средства информатики Технические средства информатики Бабаков, Р.М. Баркалов, А.А. Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов Управляющие системы и машины |
| description |
Предложено использование известного метода уменьшения максисмльного количества существенных входных переменных для снижения аппаратурных затрат в логической схеме микропрограммного автомата с операционным автоматом переходов и заменой входных переменных. |
| format |
Article |
| author |
Бабаков, Р.М. Баркалов, А.А. |
| author_facet |
Бабаков, Р.М. Баркалов, А.А. |
| author_sort |
Бабаков, Р.М. |
| title |
Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов |
| title_short |
Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов |
| title_full |
Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов |
| title_fullStr |
Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов |
| title_full_unstemmed |
Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов |
| title_sort |
уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2018 |
| topic_facet |
Технические средства информатики |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/144132 |
| citation_txt |
Уменьшение максимального количества существенных входных переменных в микропрограммном автомате с операционным автоматом переходов / Р.М. Бабаков, А.А. Баркалов // Управляющие системы и машины. — 2018. — № 2. — С. 42-51. — Бібліогр.: 14 назв. — рос. |
| series |
Управляющие системы и машины |
| work_keys_str_mv |
AT babakovrm umenʹšeniemaksimalʹnogokoličestvasuŝestvennyhvhodnyhperemennyhvmikroprogrammnomavtomatesoperacionnymavtomatomperehodov AT barkalovaa umenʹšeniemaksimalʹnogokoličestvasuŝestvennyhvhodnyhperemennyhvmikroprogrammnomavtomatesoperacionnymavtomatomperehodov AT babakovrm zmenšennâmaksimalʹnoíkílʹkostísuttêvihvhídnihvmíkroprogramnomuavtomatízoperacíjnimavtomatomperehodív AT barkalovaa zmenšennâmaksimalʹnoíkílʹkostísuttêvihvhídnihvmíkroprogramnomuavtomatízoperacíjnimavtomatomperehodív AT babakovrm reductionofthemaximummumberofsignificantinputvariablesinthemicroprogramfinitestatemachinewithdatapathoftransitions AT barkalovaa reductionofthemaximummumberofsignificantinputvariablesinthemicroprogramfinitestatemachinewithdatapathoftransitions |
| first_indexed |
2025-11-25T04:40:42Z |
| last_indexed |
2025-11-25T04:40:42Z |
| _version_ |
1849735925713600512 |
| fulltext |
42 ISSN 0130-5395, Control systems and computers, 2018, № 2
Технические средства
информатики
DOI https://doi.org/10.15407/usim.2018.02.042
УДК: 004.2
Р.М. БАБАКОВ, канд. техн. наук, доцент, Донецкий нац. ун-т имени Васыля Стуса (Украина),
ул. 600-летия, 21, Винница, 21021, Украина,
r.babakov@donnu.edu.ua
А.А. БАРКАЛОВ, д-р. техн. наук, профессор, Ун-т Зеленогурский (Польша),
ул. Подгорная, 50, 65-246, Зеленая Гура (Польша),
a.barkalov@imei.uz.zgora.pl
УМЕНЬШЕНИЕ МАКСИМАЛЬНОГО КОЛИЧЕСТВА
СУЩЕСТВЕННЫХ ВХОДНЫХ ПЕРЕМЕННЫХ
В МИКРОПРОГРАММНОМ АВТОМАТЕ
С ОПЕРАЦИОННЫМ АВТОМАТОМ ПЕРЕХОДОВ
Предложено использование известноãо метода óменьшения маêсисмльноãо êоличества сóщественных входных пере-
менных для снижения аппаратóрных затрат в лоãичесêой схеме миêропроãраммноãо автомата с операционным ав-
томатом переходов и заменой входных переменных.
Êлючевые слова: миêропроãраммный автомат, операционный автомат переходов, замена входных переменных, аппа-
ратóрные затраты.
Введение
Óстройство óправления — один из основных
блоêов современных вычислительных систем
[1]. Реализация óстройства óправления в виде
миêропроãраммноãо автомата (МПА) способ-
ствóет óвеличению быстродействия схемы
óстройства при относительно высоêих аппа-
ратóрных затратах [2]. В связи с наблюдаемым
сеãодня óвеличением сложности имплементи-
рóемых МПА алãоритмов óправления аêтó-
альна задача минимизации аппаратóрных за-
трат в лоãичесêой схеме МПА. Одно из реше-
ния данной задачи — разработêа новых стрóê-
тóр МПА с оптимизированными затратами
аппаратóры [3, 4]. Ê таêим стрóêтóрам отно-
сится, в частности, миêропроãраммный авто-
мат с операционным автоматом переходов
(МПА с ОАП), в êотором схема формирова-
ния переходов реализóется в виде операцион-
ноãо автомата [5].
Помимо стрóêтóрных решений, сóществóет
ряд подходов ê óменьшению аппаратóрных
затрат, не приводящих ê модифиêации стрóê-
тóры автомата [2, 3]. Возможность и целесо-
образность их использования в стрóêтóре
МПА с ОАП ê настоящемó моментó остается
неисследованной.
Анализ последних
исследований и публикаций
В работе [5] предложена стрóêтóра МПА с
ОАП, в êоторой фóнêция переходов реализó-
ется совместной работой операционноãо ав-
томата переходов и Z-подсхемы. ОАП пред-
ставляет собой операционный автомат, вы-
полняющий над êодом теêóщеãо состояния и
Óменьшение маêсимальноãо êоличества сóщественных входных переменных …
ISSN 0130-5395, УСиМ, 2018, № 2 43
входными сиãналами однó из операций пере-
ходов (ОП), определяемóю êодом Z:
T = T (X, T, Z ). (1)
Êаждая ОП реализóет неêоторое подмно-
жество переходов автомата в соответствии с
разбиением фóнêции переходов на множество
частичных фóнêций [6]. Êод теêóщеãо со-
стояния автомата хранится в реãистре памяти
(РП), êоторый в ОАП есть одновременно ре-
ãистром исходных данных и реãистром ре-
зóльтата.
Êод Z формирóется отдельным блоêом, на-
зываемым Z-подсхемой. В зависимости от
входных сиãналов отдельная ОП может быть
сопоставлена либо êаждомó состоянию, либо
êаждомó переходó автомата. В первом слóчае
на вход Z-подсхемы подается тольêо êод те-
êóщеãо состояния, во втором — êод теêóщеãо
состояния и множество входных сиãналов [7].
Таêже в стрóêтóре МПА с ОАП присóтствóет
схема формирования миêроопераций (СФМО),
êоторая формирóет множество выходных сиã-
налов автомата и синтезирóется по системе
бóлевых óравнений êаноничесêим способом
[2, 5, 6].
В работе [8] рассмотрены модифиêации
стрóêтóр МПА с ОАП, в êоторых использован
метод замены входных переменных. Данный
метод заêлючается в том, что множество
входных переменных X с помощью специаль-
ной M-подсхемы преобразóется во множество
промежóточных переменных P таêим обра-
зом, что | X | << | P |. Это позволяет óменьшить
êоличество сиãналов на входах Z-подсхемы,
ОАП и СФМО, снизив таêим образом затраты
аппаратóры на реализацию данных блоêов. Ме-
тод замены входных переменных эффеêтивен
в том слóчае, если óменьшение аппаратóрных
затрат в Z-подсхеме, ОАП и СФМО превыша-
ет затраты на реализацию M-подсхемы.
Уменьшение максимального
количества существенных
входных переменных
Одним из способов задания МПА слóжит
ãраф-схема алãоритма (ÃСА) [2]. Сеãодня из-
вестен ряд методов оптимизации лоãичесêой
схемы МПА, в основе êоторых лежат допóс-
тимые преобразования исходной ÃСА. При-
мер таêих преобразований — введение в ис-
ходнóю ÃСА дополнительных состояний [9,
10]. Данное действие сопровождается óвели-
чением времени выполнения алãоритма, а таê-
же возможным ростом аппаратóрных затрат,
вызванным óвеличением разрядности êода
состояния. Если последствия введения допол-
нительных состояний не противоречат êрите-
риям проеêтирования, данный подход может
быть использован для снижения затрат аппа-
ратóры в схеме миêропроãраммноãо автомата
с операционным автоматом переходов.
Пóсть G — маêсимальное êоличество вход-
ных переменных автомата, сóщественно вли-
яющих на автоматные переходы. Это значит,
что ни при одном автоматном переходе не
анализирóется более G лоãичесêих óсловий.
Дальнейшее снижение аппаратóрных затрат в
рассматриваемых стрóêтóрах МПА с ОАП,
возможно пóтем óменьшения величины G.
Для этоãо может быть использован известный
подход, заêлючающийся в следóющем [10]:
Пóстая операторная вершина может быть
добавлена в любóю ветвь, соединяющóю вы-
ход одной óсловной вершины со входом дрó-
ãой óсловной вершины.
Êоличество добавляемых вершин должно
быть минимально достаточным для снижения
величины G до требóемоãо значения.
В предельном слóчае G может быть равно
единице, т.е. любой автоматный переход за-
висит не более чем от одноãо лоãичесêоãо óс-
ловия.
Рассмотрим применение данноãо подхода ê
МПА с ОАП с заменой входных переменных [8].
Пóсть МПА задан ÃСА , отмеченной состояни-
ями автомата Мили, фраãмент êоторой приве-
ден на рис. 1 и определяет переходы из состоя-
ний a1 a4. Выполним заменó входных пере-
менных по методиêе, изложенной в [10], в со-
ответствии с табл. 1. После замены лоãичесêих
óсловий фраãмент ÃСА примет вид рис. 2.
Использование стрóêтóры МПА, рассмот-
ренной в работе [8], позволяет сопоставлять
Р.М. Бабаêов, А.А. Барêалов
44 ISSN 0130-5395, Control systems and computers, 2018, № 2
операции переходов отдельным состояниям
автомата. На рис. 2 переходы из состояний
a1 a4 зависят от разноãо êоличества входных
переменных. Это не позволяет в рамêах дан-
ноãо фраãмента сопоставить однó и тó же ОП
более чем одномó состоянию: состоянию a1
должна быть сопоставлена ОП, использóющая
в êачестве арãóментов три переменных p1 p3,
состоянию a2 – ОП, использóющая две пере-
менных p1 и p3, состоянию a3 – ОП, не ис-
пользóющая входные переменные в êачестве
арãóментов, состоянию a4 – ОП, использóю-
щая однó переменнóю p1 . Таêим образом, все
четыре ОП бóдóт различными независимо от
тоãо, êаêим образом бóдет происходить заме-
на переменных X переменными P.
Преобразóем фраãмент ÃСА, изображенный
на рис. 1, таêим образом, чтобы любой пере-
ход в рамêах фраãмента зависел не более чем
от одноãо лоãичесêоãо óсловия. Для этоãо до-
бавим пóстые операторные вершины в êаж-
дóю ветвь, соединяющóю óсловные вершины,
что приведет ê появлению трех дополнитель-
ных состояний a10 a12 . Замена входных пе-
ременных в полóченном фраãменте приводит
ê томó, что в êаждой óсловной вершине бóдет
записана переменная p1 (рис. 3).
Проведенные преобразования дают фор-
мальнóю возможность сопоставить состояни-
ям, выходы êоторых соединены с входом óс-
ловной вершины (состояниям a1, a2, a4, a10,
a11, a12 ) однó и тó же операцию переходов, ис-
пользóющóю в êачестве арãóментов êод теêó-
щеãо состояния и значение переменной p1.
При этом состоянию a3 по-прежнемó должна
быть сопоставлена отдельная ОП, реализóю-
щая безóсловный переход, не зависящий от
p1 . Таêим образом, минимально допóстимое
êоличество ОП для данноãо фраãмента равно
двóм.
Рассмотрим пример, демонстрирóющий воз-
можность использования двóх ОП для реали-
зации всех переходов в рамêах фраãмента,
изображенноãо на рис. 3, содержащеãо три
типа переходов: безóсловный переход, пере-
ход по óсловию p1 = 0 и переход по óсловию
p1 = 1. В абстраêтном автомате эти переходы
выполняются под воздействием абстраêтных
входных сиãналов z0 z2 , стрóêтóрные êоды
êоторых определяются значениями перемен-
ной p1 . Пóсть 0( )SK z , 1( )SK z 0 ,
2( ) 1SK z .
Проведем синтез для фраãмента ÃСА на
рис. 3. Зададим две абстраêтных подалãебры
переходов, определяемых выражениями (2) и
(3), первая из êоторых реализóет во фраãменте
все óсловные переходы, вторая — единствен-
ный безóсловный переход из состояния a3 в
состояние a7.
a1
a2
a3
a4
a5
x1
x2
x3 x3
1 0
1 0
1
0
0
a6
a7 a8
a9
x1
x4
1
1
0
0
1
Рис. 1. Фраãмент ÃСА
Таблица 1. Замена входных переменных (фраãмент ÃСА )
ai p1 p2 p3
a1 X1 x2 X3
a2 X4 X3
a3 – – –
a4 x1
a1
a2
a3
a4
a5
p1
p2
p3 p3
1 0
1 0
1
0
0
a6
a7 a8
a9
p1
p1
1
1
0
0
1
Рис. 2. Фраãмент ÃСА после замены входных пере-
менных
Óменьшение маêсимальноãо êоличества сóщественных входных переменных …
ISSN 0130-5395, УСиМ, 2018, № 2 45
1 1 1 1 1
1
1
1
1 12
1 2
1 1 1 10 1 2 2
2 1 9 2 2 12
10 1 11 10 2 3
11 1 5 11
, { } { } ;
{ , ..., };
{ , };
{ , , , , , ,
, , , , , ,
, , , , , ,
, , , ,
G A , Z ,
A a a
Z z z
a z a a z a
a z a a z a
a z a a z a
a z a a z
A F
2 4
12 1 8 12 2 7
4 1 7 4 2 6
, ,
, , , , , ,
, , , , , }.
a
a z a a z a
a z a a z a
(2)
2 2 2 2 2
2
2
2
3 7
0
2 3 0 7
, { } { } ;
{ , };
{ };
{ , , }.
G A , Z ,
A a a
Z z
a z a
A F
(3)
В системе (2) 1
G — абстраêтная подалãебра
переходов, носитель
1
A êоторой образован
множеством состояний 1
A и множеством
абстраêтных входных сиãналов
1
Z , а сиãна-
тóра
1
F образована единственной частичной
фóнêцией переходов 1 [7]. Фóнêция 1 пред-
ставлена множеством веêторов вида
, , i k ja z a , êаждый из êоторых соответствó-
ет переходó из состояния ia в состояние ja
под воздействием абстраêтноãо входноãо сиã-
нала kz . Аналоãичным образом орãанизована
абстраêтная подалãебра 2
G , задаваемая вы-
ражением (3).
Сформирóем промежóточнóю алãебрó пере-
ходов
1IG , изоморфнóю подалãебре 1
G . Про-
межóточные êоды состояний выберем из
множества натóральных чисел, промежóточ-
ные êоды входных сиãналов бóдем интерпре-
тировать êаê лоãичесêие величины, задавае-
мые на множестве {ИСТИНА, ЛОЖЬ}. Пóсть
1 1( )IK z ЛОЖЬ ,
1 2( ) ИСТИНАIK z .
Предположим, что общее êоличество со-
стояний в ÃСА таêово, что минимально
достаточная разрядность стрóêтóрноãо êода
состояния R = 5. Зададим промежóточные êо-
ды состояний в диапазоне [0; 31] таê, êаê по-
êазано в табл. 2.
Сопоставим состояниям a1, a2, a4, a10, a11, a12
следóющóю ОП:
Таблица 2. Êодирование состояний (фраãмент ÃСА )
ai KI(ai) ai KI(ai)
a1 21 a7 8
a2 6 a8 5
a3 28 a9 20
a4 18 a10 3
a5 15 a11 25
a6 11 a12 23
В данной интервальной фóнêции промежó-
точный êод теêóщеãо состояния
1
( )t
IK a сна-
чала приводится ê форме пятиразрядноãо дво-
ичноãо веêтора, над êоторым выполняется
поразрядная операция сложения по модóлю 2
с веêтором–êонстантой 101002. Полóченный
резóльтат интерпретирóется êаê двоичное це-
лое без знаêа и сóммирóется с целочисленной
êонстантой, значение êоторой зависит от зна-
чения переменной p1. Над резóльтатом сложе-
ния выполняется операция «mod 32», приво-
дящая резóльтат ОП ê диапазонó [0; 31].
Операция O1 позволяет реализовать все пе-
реходы из состояний a1, a2, a4, a10, a11, a12 при
O1:
1
1
1
2 10
1 1
2 10
1
( ( ) 10100 2 ) mod 32,
если 0;
( )
( ( ) 10100 5 ) mod 32,
если 1.
t
I
t
I t
I
K a
p
K a
K a
p
(4)
a1
a2
a3
a4
a5
p1
p1
p1
p1
1 0
1 0
1
0
0
a6
a7
a8
a9
p1
p1
1
1
0
0
1
a10
a11
a12
Рис. 3. Преобразованный фраãмент ÃСА
Р.М. Бабаêов, А.А. Барêалов
46 ISSN 0130-5395, Control systems and computers, 2018, № 2
óсловии использования промежóточных êодов
состояний из табл. 2. Например, переход из
состояния a10 по óсловию p1 = 0 выполняется
следóющим образом:
1 10 10 2( ) 3 00011IK a ;
000111 101002 = 101112;
101112 = 2310;
23 + 2 = 25;
25 mod 32 = 25 =
1 11( )IK a .
С óчетом табл. 2 и выражения (4), промежó-
точная алãебра
1IG есть следóющая система:
A F
1 1 1 1 1 1 1
1
1
1
1
, { ( ) ( )} { } ;
{3, 5, 6, 8, 11, 15, 18, 20, 21, 23, 25, 28};
{ЛОЖЬ,ИСТИНА}
{ 21,ЛОЖЬ,3 , 21,ИСТИНА,6 ,
6,ЛОЖЬ,20 , 6,ИСТИНА,23 ,
3,ЛОЖЬ,25 , 3,ИСТИНА,28 ,
25,ЛО
I I I I I
I
I
G K A , K Z , O
A
Z
O
ЖЬ,15 , 25,ИСТИНА,18 ,
23,ЛОЖЬ,5 , 23,ИСТИНА,8 ,
18,ЛОЖЬ,8 , 18,ИСТИНА,11 }.
(5)
Таêая сиãнатóра алãебры
1IG представлена
единственной операцией переходов O1, обра-
зованной веêторами вида
1 1
( ), ( ),I i I kK a K z
1
( )I jK a , êаждый из êоторых может быть по-
ставлен в соответствие одномó из веêторов
частичной абстраêтной фóнêции переходов 1.
Сформирóем стрóêтóрнóю подалãебрó пере-
ходов
1dG , изоморфнóю алãебрам (2) и (5) [11,
12]. Для это зададим состояниям из множе-
ства 1
A стрóêтóрные êоды, эêвивалентные
пятиразрядномó двоичномó представлению со-
ответствóющих промежóточных êодов из мно-
жества
1IA . Полóчаемая в резóльтате стрóê-
тóрная подалãебра имеет вид (6).
В данной системе d1 – частичная стрóêтóр-
ная фóнêция переходов, представляемая
множеством веêторов вида ( ), ( ),S i S kK a K z
( )S jK a , êаждый из êоторых может быть по-
ставлен в соответствие одномó из веêторов
частичной абстраêтной фóнêции переходов 1.
Таêим образом, можно ãоворить о сóществова-
нии взаимноãо изоморфизма 1
G
1IG
1dG .
Еãо сóть состоит в том, что все автоматные
переходы, определяемые абстраêтной фóнê-
цией переходов 1, рассматриваются êаê пре-
образования сêалярных величин (целых чи-
сел) с помощью ОП O1 и в стрóêтóрном (дво-
ичном) виде реализóются по заêонó, опреде-
ляемомó стрóêтóрной фóнêцией переходов d1.
A F
1 1 1 1 1
1
1
1
1 12
1 2
1
, { ( ) ( )} { } ;
( ) { ( ), ..., ( )}
{00011, 00101, 00110, 01000, 01011, 01111,
10010, 10100, 10101, 10111, 11001, 11100};
( ) { ( ), ( )} {0, 1};
d d d S d S d
S d S S
S d S S
G K A , K Z , d
K A K a K a
K Z K z K z
d
{ 10101, 0, 00011 , 10101, 1, 00110 ,
00110, 0, 10100 , 00110, 1, 10111 ,
00011, 0, 11001 , 00011, 1, 11100 ,
11001, 0, 01111 , 11001, 1, 10010 ,
10111, 0, 00101 , 10111,
1, 01000 ,
10010, 0, 01000 , 10010, 1, 01011 }.
(6)
Сформирóем промежóточнóю алãебрó пере-
ходов
2IG , изоморфнóю подалãебре 2
G . По-
сêольêó
2 13 7{ , }A a a A , стрóêтóрные êоды
3( )SK a и 7( )SK a в подалãебре
2dG должны
совпадать с соответствóющими стрóêтóрными
êодами в подалãебре
1dG . Зная стрóêтóрные
êоды состояний и входных сиãналов, можно
немедленно сформировать стрóêтóрнóю по-
далãебрó
2dG , изоморфнóю подалãебре (3):
2 2 2 2 2
2
2
2
3 7
0
2
, { ( ) ( )} { } ;
( ) { ( ), ( )} {11100, 01000};
( ) { ( )} { };
{ 11100, , 01000 }.
d d d S d S d
S d S S
S d S
G K A , K Z , d
K A K a K a
K Z K z
d
A F
(7)
Отметим, что в рассматриваемом примере
преобразование 3( )SK a =11100 в 7( )SK a = 01000,
определяемое частичной стрóêтóрной фóнê-
цией переходов фóнêцией d2, может быть реа-
лизовано пóтем выполнения поразрядной опе-
рации сложения по модóлю 2 êода 3( )SK a с
двоичным веêтором 10100. Это позволяет за-
дать операцию O2 промежóточной алãебры
2IG в следóющем виде:
Óменьшение маêсимальноãо êоличества сóщественных входных переменных …
ISSN 0130-5395, УСиМ, 2018, № 2 47
O2:
2 2
1
2( ) ( ) 10100 .t t
I IK a K a (8)
Исходя из (8), промежóточные êоды состоя-
ний, образóющие носитель 2 2
( )IK A алãебры
2IG , есть двоичные веêторы, совпадающие со
стрóêтóрными êодами соответствóющих со-
стояний подалãебры (7):
2 3( ) 11100IK a ,
2 7( ) 01000IK a . Посêольêó сиãнал z0 не óчаст-
вóет êаêим-либо образом в операции O2, для
промежóточной алãебры
2IG он формальный
и
2 2 2 0( ) { }IK Z Z z . Теперь промежóточ-
ная алãебра переходов
2IG может быть задана
следóющей системой:
2 2 2
2 2 2 2
2 2
2 2 2
2
0
2 0
,
{ ( ), ( )},{ } ;
( ) {11100, 01000};
( ) { };
{ 11100, , 01000 }.
I I I
I I
I
I
G
K A K Z O
K A
K Z Z z
O z
A F
(9)
Отметим, что промежóточная алãебра (9)
изоморфна подалãебрам (3) и (9). Сóще-
ствование изоморфизмов 1
G
1IG
1dG и
2
G
2IG
2dG подтверждает возможность
реализации всех переходов во фраãменте ÃСА
на рис. 3 с óчетом выбранных операций пере-
ходов [11, 12]. Ãрафичесêи это поêазано на
рис. 4, ãде в êаждой операторной вершине
óêазаны промежóточные и стрóêтóрные (дво-
ичные) êоды состояния, следóющеãо за дан-
ной вершиной, а êаждая дóãа ãрафа отмечена
операцией, реализóющей данный переход.
Таêим образом, óменьшение маêсимально-
ãо êоличества сóщественных входных пере-
менных при использовании стрóêтóры МПА с
ОАП и заменой входных переменных может в
неêоторых слóчаях приводить ê óменьшению
êоличества использóемых ОП. Следствием
этоãо есть óменьшение êоличества êомбина-
ционных схем в операционной части ОАП,
приводящее ê снижению аппаратóрных затрат
в схеме автомата [13]. В тех слóчаях, êоãда
óменьшение êоличества ОП сопровождается
óменьшением разрядности êода ОП, имеет
место дополнительное снижение аппаратóр-
ных затрат в схеме ОАП пóтем óпрощения
мóльтиплеêсора резóльтата, а таêже в Z-под-
схеме за счет óменьшения числа выходов.
Итаê, отметим, что операция поразрядноãо
сложения по модóлю 2 с êонстантой 101002 ,
являющаяся в выражении (4) внóтренней
фóнêцией по отношению ê ОП O1 , в точности
совпадает с ОП O2 , определяемой выражени-
ем (8). Это позволяет синтезировать êомбина-
ционные схемы данных ОП таê, êаê поêазано
на рис. 5. В данной схеме все линии связи, за
исêлючением одноразрядной линии, по êото-
рой подается сиãнал p1, пятиразрядные, а в
êачестве êонстант 210 и 510 на входы мóльтип-
леêсора MX подаются их двоичные целочис-
a1
a2
a3
a4
a5
p1
p1
p1
p1
10100 + 2
a6
a7
a8
a9
p1
p1
a10
a11
a12
2110 = 101012
310 = 000112 610 = 001102
2510 = 110012 2810 = 111002
2310 = 101112
2010 = 101002
1510 = 011112
1810 = 100102 1810 = 100102
1110 = 010112
810 = 010002
510 = 001012
10100 + 5
10100 + 2
10100 + 5
10100 + 2 10100 + 5
10100 + 5
10100 + 2
10100 + 2
10100 + 5
10100
10100 + 5
10100 + 2
Рис. 4. Ãрафичесêое представление резóльтатов синте-
за (фраãмент ÃСА )
p1
T 101002 210 510
MX
d1d2
2dКС
1dКС
Рис. 5. Фраãмент фóнêциональной схемы операцион-
ной части ОАП, соответствóющий операциям перехо-
дов O1 и O2
Р.М. Бабаêов, А.А. Барêалов
48 ISSN 0130-5395, Control systems and computers, 2018, № 2
ленные формы 000102 и 001012 соответственно.
В резóльтате êомбинационная схема
2
КСd , реа-
лизóющая ОП O2, — часть êомбинационной
схемы
1
КСd , реализóющей операцию O1. Без-
óсловно, даннóю особенность следóет рас-
сматривать êаê сóãóбо частный слóчай, однаêо
подобные ситóации необходимо всеãда иметь
в видó при оптимизации лоãичесêой схемы
операционноãо автомата переходов.
Помимо снижения аппаратóрных затрат в
схеме ОАП, óменьшение êоличества входных
переменных, сóщественно влияющих на ав-
томатные переходы, в слóчае автомата Мили
приводит ê дополнительномó óменьшению
числа входов блоêа СФМО. Отметим таêже,
что при использовании в МПА с ОАП метода
óменьшения êоличества сóщественных вход-
ных переменных следóет помнить, что óмень-
шение величины G неизбежно сопровождает-
ся óвеличением числа состояний автомата и в
неêоторых слóчаях может приводить ê óвели-
чению разрядности R êода состояния. Óвели-
чение R приводит ê ростó аппаратóрных за-
трат во всех блоêах лоãичесêой схемы МПА
независимо от еãо стрóêтóрной орãанизации.
Заключение
В статье предлаãается способ оптимизации
аппаратóрных затрат в стрóêтóре МПА с ОАП
и заменой входных переменных. Способ за-
êлючается в применении ê МПА с ОАП из-
вестноãо метода óменьшения êоличества сó-
щественных входных переменных. Данный
подход не приводит ê изменениям в стрóêтóре
автомата, однаêо позволяет в неêоторых слó-
чаях добиться óменьшения êоличества опера-
ций, использóемых в ОАП, а таêже снизить
аппаратóрные затраты в блоêе СФМО автома-
та Мили.
Вместе с тем, численные поêазатели эф-
феêтивности использования данноãо подхо-
да не являются очевидными из стрóêтóры
МПА и имплементирóемоãо им алãоритма
óправления, и требóют проведения дополни-
тельных исследований. Праêтичесêое приме-
нение рассмотренноãо подхода требóет разра-
ботêи соответствóющих формализованных
методов синтеза МПА с ОАП, ориентирован-
ных на использование современноãо эле-
ментноãо базиса проãраммирóемых инте-
ãральных схем [14].
СПИСОÊ ЛИТЕРАТÓРЫ
1. Ãлóшêов В.М. Синтез цифровых автоматов, М.: Физматãиз, 1962, 476 с.
2. Баранов С.И. Синтез миêропроãраммных автоматов, Л.: Энерãия, 1979, 232 с.
3. Logic Synthesis for FPGA-Based Finite State Machines / A. Barkalov, L. Titarenko, M. Kolopienczyk et al, Springer,
2016, 280 p.
4. DeMicheli G. Synthesis and Optimization of Digital Circuits, NY: McGraw-Hill, 1994, 576 p.
5. Барêалов А.А., Бабаêов Р.М. Реализация фóнêции переходов миêропроãраммноãо автомата на базе операци-
онноãо автомата // ÓСиМ, 2015, № 5, С. 22–29.
6. Barkalov A.A., Babakov R.M. Algebraic Interpretation of a Microprogram Finite-State Machine with Datapath of
Transitions, Cybernetics and Systems Analysis, 52, Issue 2, 2016, P. 191–198.
7. Бабаêов Р.М., Ярош И.В. Формирование êодов операций переходов в миêропроãраммном автомате с опера-
ционным автоматом переходов // Сб. наóч. трóдов ДонНТÓ. Серия «Информатиêа, êибернетиêа и вычисли-
тельная техниêа», Êрасноармейсê, ДонНТÓ, 2015, 1 (20), С. 11–16.
8. Бабаêов Р.М., Барêалов А.А. Модифиêация миêропроãраммноãо автомата с операционным автоматом пере-
ходов и заменой входных переменных // ÓСиМ, 2017, № 6, С. 35–40.
9. Сêляров В.А. Синтез автоматов на матричных БИС, Минсê: Наóêа и техниêа, 1984, 256 с.
10. Барêалов А.А. Синтез óстройств óправления на проãраммирóемых лоãичесêих óстройствах, Донецê, ДонНТÓ,
2002, 262 с.
11. Бабаêов Р.М. Промежóточная алãебра переходов в миêропроãраммном автомате // Радиотехниêа, информа-
тиêа, óправление, 2016, № 1, С. 64–73.
12. Бабаêов Р.М. Математичесêая модель миêропроãраммноãо автомата с операционным автоматом переходов
// Сб. наóч. трóдов ДонНТÓ. Серия «Информатиêа, êибернетиêа и вычислительная техниêа», Êрасноар-
мейсê, ДонНТÓ, 2016, 1 (22), С. 54–57.
13. Бабаêов Р.М., Ярош И.В. Операционный автомат переходов // Сб. наóч. трóдов ДонНТÓ. Серия: «Вычисли-
тельная техниêа и автоматизация», Там же, 2015, 1 (28), С. 33–40.
Óменьшение маêсимальноãо êоличества сóщественных входных переменных …
ISSN 0130-5395, УСиМ, 2018, № 2 49
14. Ãрóшвицêий Р.И., Мóрсаев А.Х., Óãрюмов Е.П. Проеêтирование систем на миêросхемах проãраммирóемой ло-
ãиêи, БХВ-Петербóрã, 2002, 608 с.
Постóпила 03.04.2018
REFERENCES
1. Glushkov V.M. Sintez tsifrovih avtomatov, Moscow, 1962, 476 p.
2. Baranov S.I. Sintez mikroprogrammnih avtomatov, Leningrad, 1979, 232 p.
3. Logic Synthesis for FPGA-Based Finite State Machines / A. Barkalov, L. Titarenko, M. Kolopienczyket al, Springer,
2016, 280 p.
4. DeMicheli G. Synthesis and Optimization of Digital Circuits, New York, 1994, 576 p.
5. Barkalov A.A., Babakov R.M. Upravlajushie sistemi i mashini, N 5, 2015, P. 22–29.
6. Barkalov A.A., Babakov R.M. Algebraic Interpretation of a Microprogram Finite-State Machine with Datapath of
Transitions, Cybernetics and Systems Analysis, Volume 52, Issue 2, 2016, P. 191–198.
7. Babakov R.M., Yarosh I.V. Sbornik nauchnih trudov DonNTU. Seriya: «Informatika, kibernetika i vichislitelnaya
tehnika», N 1, 2015, P. 11–16.
8. Barkalov A.A., Babakov R.M. Upravlajushie sistemi i mashini, N 6, 2016, P. 35–40.
9. Sklyarov V.A. Sintez avtomatov na matrichnih BIS, Minsk, 1984, 256 p.
10. Barkalov A.A. Sintez ustroystv upravleniya na programmiruemih logicheskih ustroystvah, Donetsk, 2002, 262 p.
11. Babakov R.M. Radiotehnika, informatika, upravlenie. N 1, 2016, P. 64–73.
12. Babakov R.M. Sbornik nauchnih trudov DonNTU. Seriya: «Informatika, kibernetika i vichislitelnaya tehnika», N 1,
2016, P. 54–57.
13. Babakov R.M., Yarosh I.V. Sbornik nauchnih trudov DonNTU. Seriya: «Vichislitelnaya tehnika i avtomatizatsiya»,
N 1, 2015, P. 33–40.
14. Grushvitskiy R.I., Mursaev A.X., Ugrumov E.P. Proektirovanie sistem na mikroshemah programmiruemoj logiki, St. Pe-
terburg, 2002, 608 p.
Received 03.04.2018
R.M. Babakov, PhD in Techn.Sciences, Associate Professor, Vasyl’ Stus Donetsk National University,
600-richa str., 21, Vinnitsya, 21021, Ukraine, (+380 50) 295-0650, r.babakov@donnu.edu.ua
A.A. Barkalov, Doctor in Techn. Sciences, Professor, University of Zielona Gora, Podgorna str., 50,
Zielona Gora, 65246, Poland, (+48 68) 326-2693, a.barkalov@imei.uz.zgora.pl
REDUCTION OF THE MAXIMUM MUMBER OF SIGNIFICANT INPUT VARIABLES
IN THE MICROPROGRAM FINITE STATE MACHINE WITH DATAPATH OF TRANSITIONS
Introduction. The object of research is the microprogram finite state machine with datapath of transitions with the input
variables replacement. In digital devices, microprogram finite state machine performs the functions of control unit and
coordinates the functionality of other system blocks. One of the current scientific and practical problems is the reduction
of hardware expenses in the logic circuit of the microprogram finite state machine. One way to solve this problem is the
development of new microprogram structures and methods for their synthesis. One of such structures is a microprogram
finite state machine with datapath of transitions. In this structure, the transition formation circuit is implemented in the
form of datapath consisting of a separate operational blocks. Each operational block implements the individual law of con-
verting state codes and input signals, realizing a disjoint subset of microprogram transitions. Herewith, the hardware ex-
penses in the operational block do not depend or depend insignificantly on the number of microprogram transitions it
implements. This allows to achieve the reducing of hardware expenses in comparison with the implementation of transi-
tion function of the finite state machine by the canonical method using the system of Boolean equations. The approach,
consisting of the circuit representation forming the transitions of the microprogram finite sate machine in the form of
datapath, is called the operational realization of the transition function of the finite state machine. The use of the input
variables replacement method makes it possible to further reduce the the hardware expenses in some blocks of the finite
state machine.
Purpose. The purpose of this article is to research a new way for optimization of the hardware expenses in logical cir-
cuit of finite state machine with datapath of the input variables transitions and replacement.
Р.М. Бабаêов, А.А. Барêалов
50 ISSN 0130-5395, Control systems and computers, 2018, № 2
Methods. It is proposed to use the known method of decreasing the maximum number of significant input variables.
The method consists of adding new states, which leads to a decrease in the number of input signals analyzed in one state
machine transition.
Results. The proposed approach does not lead to a change in the structure of the microprogram finite state machine
with datapath of the input variables transitions and replacement. It can be achieved by reducing the number of transition
operations used. It is also possible to cut hardware expenses simultaneously in other structure blocks by reducing the num-
ber of intermediate signals replacing the finite state machine input signals.
Conclusion. The reduction of the maximum number of significant input variables allows, under certain conditions, to
cut the amount of hardware expenses in the logic circuit of the microprogram finite state machine with datapath of transi-
tions and the input variables replacement. The disadvantage of this approach is the increase in the execution time of the
algorithm, interpreted by the finite state machine.
Keywords: microprogram finite state machine, datapath of transitions, replacement of input variables, hardware expenses.
Р.M. Бабаêов, êанд. техн. наóê, доцент, Донецьêий нац. óн-т ім. Василя Стóса (Óêраїна),
вóл. 600-річчя, 21, Вінниця, 21021, Óêраїна, (+380 50) 295-0650, r.babakov@donnu.edu.ua
О.О. Барêалов, д-р. техн. наóê, професор, Ó-т Зеленоãóрсьêий (Польща),
вóл. Підãірна, 50, Зелена Ãóра, 65246, Польща, (+48 68) 326-2693, a.barkalov@imei.uz.zgora.pl
ЗМЕНШЕННЯ МАÊСИМАЛЬНОЇ ÊІЛЬÊОСТІ СÓТТЄВИХ ВХІДНИХ
В МІÊРОПРОÃРАМНОМÓ АВТОМАТІ З ОПЕРАЦІЙНИМ АВТОМАТОМ ПЕРЕХОДІВ
Встóп. In this article, the object of research is the microprogram finite state machine with datapath of transitions with
replacement of input variables. In digital devices, microprogram finite state machine performs the functions of control
unit and coordinates the functionality of other blocks of the system. One of the topical scientific and practical problems is
the reduction of hardware expenses in the logic circuit of the microprogram finite state machine. One way to solve this
problem is the development of new microprogram finite state machine structures and methods for their synthesis. One of
such structures is a microprogram finite state machine with datapath of transitions. In this structure, the transition forma-
tion circuit is implemented in the form of an datapath consisting of a number of separate operational blocks. Each opera-
tional block implements individual law of converting state codes and input signals, realizing a disjoint subset of micropro-
gram transitions. Herewith, the hardware expenses in the operational block do not depend or depend insignificantly on the
number of microprogram transitions it implements. This allows under certain conditions to achieve reducing of hardware
expenses in comparison with the implementation of transition function of the finite state machine by the canonical
method using the system of Boolean equations. The approach, consisting in the representation of the circuit for forming
the transitions of the microprogram final-state machine in the form of an datapath, was called the operational realization
of the transition function of the finite state machine. The use of the method of replacement of input variables in this struc-
ture makes it possible to further reduce the hardware expenses in some blocks of the finite state machine.
Мета. The purpose of this article is to research a new way for optimization of hardware expenses in logical circuit of
finite state machine with datapath of transitions and replacement of input variables.
Методи. It is proposed to use the known method of decreasing the maximum number of significant input variables.
The method consists in adding new states, which leads to a decrease in the number of input signals analyzed in one state
machine transition.
Резóльтати. The proposed approach does not lead to a change in the structure of the microprogram finite state ma-
chine with datapath of transitions and the replacement of input variables. Reducing the hardware expenses in the datapath
of transitions can be achieved by reducing the number of transition operations used. It is also possible to simultaneously
reduce hardware expnses in other blocks of the structure by reducing the number of intermediate signals replacing the in-
put signals of the finite state machine.
Висновêи. Reduction of the maximum number of significant input variables allows under certain conditions to re-
duce the amount of hardware expenses in the logic circuit of the microprogram finite state machine with datapath of tran-
sitions and the replacement of input variables. The disadvantage of this approach is the increase in the execution time of
the algorithm, interpreted by the finite state machine.
Êлючовi слова: міêропроãрамний автомат, операційний автомат переходів, заміна вхідних змінних, апаратóрні ви-
трати.
|