Уменьшение аппаратурных затрат в устройстве управления с разделением кодов
Запропоновано метод зменшення апаратурних витрат у логічній схемі композиційного мікропрограмного пристрою керування при реалізації на CPLD. Метод базується на наявності псевдоеквівалентних операторних лінійних ланцюгів, великого коефіцієнта об’єднання за входом у макрочарунок PAL та вільних виходів...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2013 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/86239 |
| 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: | Уменьшение аппаратурных затрат в устройстве управления с разделением кодов / А.А. Баркалов, Л.А. Титаренко, А.С. Лаврик // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 113-123. — Бібліогр.: 11 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860258575562047488 |
|---|---|
| author | Баркалов, А.А. Титаренко, Л.А. Лаврик, А.С. |
| author_facet | Баркалов, А.А. Титаренко, Л.А. Лаврик, А.С. |
| citation_txt | Уменьшение аппаратурных затрат в устройстве управления с разделением кодов / А.А. Баркалов, Л.А. Титаренко, А.С. Лаврик // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 113-123. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано метод зменшення апаратурних витрат у логічній схемі композиційного мікропрограмного пристрою керування при реалізації на CPLD. Метод базується на наявності псевдоеквівалентних операторних лінійних ланцюгів, великого коефіцієнта об’єднання за входом у макрочарунок PAL та вільних виходів вбудованих блоків пам’яті мікросхем ПЛІС. Наведено приклад використання запропонованого методу. Проведені дослідження показали, що метод зменшує апаратурні витрати до 30 %.
A method for reducing hardware expenses in compositional microprogram control unit and CPLD chips is proposed. This method is based on the use of pseudoequivalent operational linear chains, wide fan-in of PAL macrocells and existence of free outputs of embedded memory block in CPLD chips. An example of applying the method is given. It is shown that the method reduces hardware expenses to 30%.
|
| first_indexed | 2025-12-07T18:52:13Z |
| format | Article |
| fulltext |
ÓÄÊ 004.3
À.À. ÁÀÐÊÀËÎÂ, Ë.À. ÒÈÒÀÐÅÍÊÎ, À.Ñ. ËÀÂÐÈÊ
ÓÌÅÍÜØÅÍÈÅ ÀÏÏÀÐÀÒÓÐÍÛÕ ÇÀÒÐÀÒ Â ÓÑÒÐÎÉÑÒÂÅ
ÓÏÐÀÂËÅÍÈß Ñ ÐÀÇÄÅËÅÍÈÅÌ ÊÎÄÎÂ
Êëþ÷åâûå ñëîâà: ãðàô-ñõåìà àëãîðèòìà, óïðàâëÿþùåå óñòðîéñòâî, êîìïîçè-
öèîííîå ìèêðîïðîãðàììíîå óñòðîéñòâî óïðàâëåíèÿ, ðàçäåëåíèå êîäîâ, ïðî-
ãðàììèðóåìûå ëîãè÷åñêèå èíòåãðàëüíûå ñõåìû òèïà CPLD, àäðåñàöèÿ ìèêðî-
êîìàíä.
ÂÂÅÄÅÍÈÅ
Ïðàêòè÷åñêè ëþáàÿ öèôðîâàÿ ñèñòåìà âêëþ÷àåò óñòðîéñòâî óïðàâëåíèÿ (ÓÓ),
êîîðäèíèðóþùåå âçàèìîäåéñòâèå ñèñòåìíûõ áëîêîâ [1]. Ôóíêöèîíèðîâàíèå ÓÓ
÷àñòî ìîæåò îïðåäåëÿòüñÿ ìîäåëüþ öèôðîâîãî àâòîìàòà [2]. Êàê ïðàâèëî, ïðè
ðåàëèçàöèè ñõåìû ÓÓ âîçíèêàåò çàäà÷à óìåíüøåíèÿ àïïàðàòóðíûõ çàòðàò [3].
Ìåòîäû ðåøåíèÿ ýòîé çàäà÷è çàâèñÿò îò îñîáåííîñòåé àëãîðèòìà óïðàâëåíèÿ
è ýëåìåíòíîãî áàçèñà. Òàê, ïðè ëèíåéíîì õàðàêòåðå àëãîðèòìà óïðàâëåíèÿ öå-
ëåñîîáðàçíî èñïîëüçîâàòü ìîäåëü êîìïîçèöèîííîãî ìèêðîïðîãðàììíîãî óñòðîé-
ñòâà óïðàâëåíèÿ (ÊÌÓÓ) [4, 5].  íàñòîÿùåé ðàáîòå ðàññìîòðåíà çàäà÷à ðåàëè-
çàöèè ñõåìû ÊÌÓÓ â áàçèñå ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì
(ÏËÈÑ) òèïà CPLD (Complex Programmable Logic Devices) [6, 7]. Ïîäîáíûå
ÏËÈÑ ñîñòîÿò èç ìàêðîÿ÷ååê òèïà ÏÌË (ïðîãðàììèðóåìàÿ ìàòðè÷íàÿ ëîãèêà)
è ìàòðèöû ìåæñîåäèíåíèé. Îñîáåííîñòüþ ÏÌË ÿâëÿåòñÿ äîñòàòî÷íî áîëüøîå
êîëè÷åñòâî âõîäîâ (íåñêîëüêî äåñÿòêîâ) è îãðàíè÷åííîå êîëè÷åñòâî òåðìîâ [8,
9]. Äëÿ óìåíüøåíèÿ êîëè÷åñòâà ìàêðîÿ÷ååê â ñõåìå ÓÓ íåîáõîäèìî óìåíüøèòü
êîëè÷åñòâî òåðìîâ â ðåàëèçóåìûõ ôóíêöèÿõ. Äëÿ ýòîãî ìîæíî èñïîëüçîâàòü íå-
ñêîëüêî èñòî÷íèêîâ êîäîâ ñîñòîÿíèé [10].
Äëÿ ÊÌÓÓ â êà÷åñòâå ñîñòîÿíèé èñïîëüçîâàíû îïåðàòîðíûå ëèíåéíûå öåïè
(ÎËÖ). Â íàñòîÿùåé ñòàòüå ïðåäëîæåíû ìåòîäû, îñíîâàííûå íà ïðèìåíåíèè íå-
ñêîëüêèõ èñòî÷íèêîâ êîäîâ ÎËÖ. Ïðè ýòîì àëãîðèòì óïðàâëåíèÿ öèôðîâîé ñèñ-
òåìû ïðåäñòàâëåí â âèäå ëèíåéíîé ãðàô-ñõåìû àëãîðèòìà (ÃÑÀ) [1]. Ñóùåñòâóåò
ìíîãî ðàçëè÷íûõ ìîäåëåé ÊÌÓÓ [4], èõ âûáîð îïðåäåëÿåòñÿ îñîáåííîñòÿìè
ÃÑÀ, ïî êîòîðîé ðåàëèçóåòñÿ ñõåìà ÓÓ. Äàëåå ðàññìîòðåíà ìîäåëü ÊÌÓÓ ñ ðàç-
äåëåíèåì êîäîâ [4]. Îòìåòèì, ÷òî ïðåäëàãàåìûå ìåòîäû ìîæíî èñïîëüçîâàòü äëÿ
ëþáîé ìîäåëè ÊÌÓÓ.
ÁÀÇÎÂÀß ÌÎÄÅËÜ ÊÌÓÓ Ñ ÐÀÇÄÅËÅÍÈÅÌ ÊÎÄÎÂ
Ïóñòü ÃÑÀ � ïðåäñòàâëåíà ìíîæåñòâàìè âåðøèí Â è äóã Å, ñîåäèíÿþùèõ
ýòè âåðøèíû. Ïðè ýòîì B b b B BE� � �{ }0 1 2, , ãäå b0 , bE — íà÷àëüíàÿ è êî-
íå÷íàÿ âåðøèíû ÃÑÀ ñîîòâåòñòâåííî; B1 — ìíîæåñòâî îïåðàòîðíûõ âåð-
øèí, | |B M1 � ; B2 — ìíîæåñòâî óñëîâíûõ âåðøèí. Â âåðøèíàõ b Bq � 1 çàïè-
ñàíû íàáîðû ìèêðîîïåðàöèé Y b Yq( ) � , ãäå Y y yN� { }1, ..., — ìíîæåñòâî
ìèêðîîïåðàöèé.  âåðøèíàõ b Bq � 2 çàïèñàíû ýëåìåíòû ìíîæåñòâà ëîãè÷åñ-
êèõ óñëîâèé X x xL� { }1, ..., . Ââåäåì îïðåäåëåíèÿ [4, 5], íåîáõîäèìûå äëÿ
äàëüíåéøåãî èçëîæåíèÿ.
Îïðåäåëåíèå 1. Îïåðàòîðíîé ëèíåéíîé öåïüþ ÃÑÀ � íàçûâàåòñÿ êîíå÷íàÿ ïî-
ñëåäîâàòåëüíîñòü îïåðàòîðíûõ âåðøèí � g g gFb b
g
� � �1 ,, � òàêàÿ, ÷òî äëÿ ëþáîé
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 113
© À.À. Áàðêàëîâ, Ë.À. Òèòàðåíêî, À.Ñ. Ëàâðèê, 2013
ïàðû ñîñåäíèõ êîìïîíåíòîâ êîðòåæà � g ñóùåñòâóåò äóãà � � � b b Egi gi, 1 , ãäå i —
íîìåð êîìïîíåíòà êîðòåæà � g (i Fg�
1 1, ,� ), G — ÷èñëî ÎËÖ â ÃÑÀ �.
Îïðåäåëåíèå 2. Îïåðàòîðíàÿ âåðøèíà b Dq
g� , ãäå D Bg � 1 — ìíîæåñòâî
îïåðàòîðíûõ âåðøèí, âõîäÿùèõ â ÎËÖ � g , íàçûâàåòñÿ âõîäîì ÎËÖ � g , åñëè
ñóùåñòâóåò äóãà � � �b b Et q, , ãäå b Dt
g� .
Îïðåäåëåíèå 3. Îïåðàòîðíàÿ âåðøèíà b Dq
g� íàçûâàåòñÿ âûõîäîì ÎËÖ � g ,
åñëè ñóùåñòâóåò äóãà � � �b b Eq t, , ãäå b Dt
g� .
Îïðåäåëåíèå 4. Îïåðàòîðíûå ëèíåéíûå öåïè � i , � j íàçûâàþòñÿ ïñåâäî-
ýêâèâàëåíòíûìè ÎËÖ (ÏÎËÖ), åñëè ñóùåñòâóþò äóãè � � � � �b b b b Ei t j t, , , , ãäå
bi , b j — ñîîòâåòñòâåííî âûõîäû ÎËÖ � i , � j .
Êàæäàÿ ÎËÖ � g èìååò ïðîèçâîëüíîå ÷èñëî âõîäîâ, îáðàçóþùèõ ìíîæåñòâî
I I Ig g g( ) , ,� � { }1 2
� , è òîëüêî îäèí âûõîä Og . Ïóñòü äëÿ ÃÑÀ � íàéäåíî ðàçáèå-
íèå C G� { }� �1, ,� ìíîæåñòâà B1 íà ÎËÖ è ìíîæåñòâî C âêëþ÷àåò ìèíèìàëü-
íî âîçìîæíîå ÷èñëî ÎËÖ, äëÿ ÷åãî èñïîëüçóåòñÿ ìåòîäèêà [4].
Îïðåäåëåíèå 5. Ãðàô-ñõåìà àëãîðèòìà � íàçûâàåòñÿ ëèíåéíîé, åñëè âûïîë-
íÿåòñÿ óñëîâèå
M
G
� 2 . (1)
Òàêèì îáðàçîì, ÃÑÀ ÿâëÿåòñÿ ëèíåéíîé, åñëè êîëè÷åñòâî åå îïåðàòîðíûõ âåð-
øèí õîòÿ áû â äâà ðàçà ïðåâûøàåò ìèíèìàëüíîå ÷èñëî åå ÎËÖ. Ïðè âûïîëíåíèè
óñëîâèÿ (1) äëÿ ðåàëèçàöèè ÓÓ öåëåñîîáðàçíî èñïîëüçîâàòü ìîäåëü ÊÌÓÓ [4].
Îòìåòèì, ÷òî êàæäàÿ âåðøèíà b Bq � 1 ñîîòâåòñòâóåò ìèêðîêîìàíäå MI q ,
õðàíèìîé â óïðàâëÿþùåé ïàìÿòè (ÓÏ) ïî àäðåñó A bq( ) . Äëÿ àäðåñàöèè
ìèêðîêîìàíä äîñòàòî÷íî
�R M� log 2 áèò. Ïóñòü êàæäàÿ ÎËÖ � g C� âêëþ-
÷àåò Fg êîìïîíåíòîâ è Q F FG� max ( , , )1 � . Çàêîäèðóåì êàæäóþ ÎËÖ � g C�
äâîè÷íûì êîäîì K g( )� ðàçðÿäíîñòè
�R G
1 2� log , à êàæäûé êîìïîíåíò
b Bq � 1 — äâîè÷íûì êîäîì K bq( ) ðàçðÿäíîñòè
�R Q2 2� log .
Èñïîëüçóåì äëÿ êîäèðîâàíèÿ ÎËÖ ïåðåìåííûå � �r � , à äëÿ êîäèðîâàíèÿ
êîìïîíåíòîâ — ïåðåìåííûå T Tr � , ãäå | |� � R1, | |T R� 2 . Êîäèðîâàíèå êîìïî-
íåíòîâ âûïîëíÿåòñÿ â åñòåñòâåííîì ïîðÿäêå, ò.å.
K b K bgi gi( ) ( ) � 1 1, (2)
ãäå g G�1, ,� , i Fg�1, ,� . Ïóñòü äëÿ ÃÑÀ � âûïîëíÿåòñÿ óñëîâèå
R R R1 2 � . (3)
 ýòîì ñëó÷àå äëÿ åå èíòåðïðåòàöèè ìîæíî èñïîëüçîâàòü ìîäåëü ÊÌÓÓ
ñ ðàçäåëåíèåì êîäîâ (ðèñ. 1), îáîçíà÷àåìóþ â äàëüíåéøåì U 1.
 ÊÌÓÓ U 1 ñõåìà àäðåñàöèè ìèêðîêîìàíä (ÑÀÌ) ðåàëèçóåò ñèñòåìó ôóíê-
öèé âîçáóæäåíèÿ òðèããåðîâ ñ÷åò÷èêà ÑÒ è ðåãèñòðà Ðã
� �
� �
�
�
( , ),
( , ).
�
�
X
X
Ïðè ýòîì àäðåñ ìèêðîêîìàíäû MI q ïðåäñòàâëÿåòñÿ â âèäå A b K K bq g q( ) ( )* ( )� � ,
ãäå âåðøèíà bq âõîäèò â ñîñòàâ ÎËÖ � g C� , * — çíàê îïåðàöèè êîíêàòåíàöèè.
Ïî ñèãíàëó Start â Ðã è ÑÒ çàíîñèòñÿ íà÷àëüíûé àäðåñ ìèêðîïðîãðàììû,
à òðèããåð âûáîðêè (ÒÂ) óñòàíàâëèâàåòñÿ â ñîñòîÿíèå ëîãè÷åñêîé åäèíèöû. Ïðè
ýòîì Fetch �1, ÷òî ðàçðåøàåò âûáîðêó êîìàíä èç ÓÏ. Åñëè ñ÷èòàííàÿ ìèêðîêî-
114 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
ìàíäà íå ñîîòâåòñòâóåò âûõîäó ÎËÖ, òî îäíîâðåìåííî ñ ìèêðîîïåðàöèÿìè
Y bq( ) ôîðìèðóåòñÿ ïåðåìåííàÿ y0 . Åñëè y0 1� , òî ê ñîäåðæèìîìó ÑÒ ïðèáàâ-
ëÿåòñÿ åäèíèöà è àäðåñóåòñÿ ñëåäóþùèé êîìïîíåíò òåêóùåé ÎËÖ. Åñëè âû-
õîä ÎËÖ äîñòèãíóò, òî y0 0� . Ïðè ýòîì ÑÀÌ ôîðìèðóåò àäðåñ âõîäà ñëåäóþ-
ùåé ÎËÖ. Ïî äîñòèæåíèþ îêîí÷àíèÿ ìèêðîïðîãðàììû ôîðìèðóåòñÿ ñèãíàë yE ,
òðèããåð ÒÂ îáíóëÿåòñÿ, è âûáîðêà ìèêðîêîìàíä ïðåêðàùàåòñÿ.
Âûõîäíûå ïåðåìåííûå y0 , yE è y Yn � çàâèñÿò òîëüêî îò ñîäåðæèìîãî ðå-
ãèñòðà è ñ÷åò÷èêà. Òàêèì îáðàçîì, ÊÌÓÓ U 1 ÿâëÿåòñÿ àâòîìàòîì Ìóðà [1], ïðè
ýòîì ÎËÖ � g C� — àíàëîã ñîñòîÿíèÿ àâòîìàòà. Ñëåäîâàòåëüíî, äëÿ îïòèìèçà-
öèè ñõåìû ÊÌÓÓ ìîæíî èñïîëüçîâàòü âñå èçâåñòíûå ìåòîäû îïòèìèçàöèè àâòî-
ìàòà Ìóðà [7, 10, 11]. Åñòåñòâåííî, îíè äîëæíû áûòü àäàïòèðîâàíû ê îñîáåííîñ-
òÿì ÊÌÓÓ.
Îñîáåííîñòü ÊÌÓÓ U 1 è çàêëþ÷àåòñÿ â îòñóòñòâèè çàâèñèìîñòè ìåæäó êî-
äàìè öåïåé è èõ êîìïîíåíòàìè. Êðîìå òîãî, ÃÑÀ � ìîæåò âêëþ÷àòü íåòðèâèàëü-
íûå êëàññû ÏÎËÖ. Ïðè ñèíòåçå ñõåìû ÊÌÓÓ U 1 áëîêè ÑÀÌ, ÑÒ, Ðã è ÒÂ ðåà-
ëèçóþòñÿ íà ìàêðîÿ÷åéêàõ ÏÌË. Äëÿ ôîðìèðîâàíèÿ ñõåìû ÓÏ íåîáõîäèìû
âíåøíèå áëîêè ïàìÿòè (ÂÁÏ). Îñîáåííîñòè ìàêðîÿ÷ååê ÏÌË óæå óïîìèíàëèñü
ðàíåå (áîëüøîå êîëè÷åñòâî âõîäîâ è îãðàíè÷åííîå êîëè÷åñòâî òåðìîâ). Îñîáåí-
íîñòÿìè ÂÁÏ ÿâëÿåòñÿ äèñêðåòíîñòü ÷èñëà èõ âûõîäîâ. Êàê ïðàâèëî, âûõîäû
ïðèíàäëåæàò ìíîæåñòâó Q t( ) , , , , ,� { }1 2 4 8 16 32 . Ñ ó÷åòîì îïèñàííûõ îñîáåííîñ-
òåé ìîæíî îïòèìèçèðîâàòü ÷èñëî ìàêðîÿ÷ååê â ñõåìå àäðåñàöèè.
ÎÑÍÎÂÍÀß ÈÄÅß ÏÐÅÄËÀÃÀÅÌÎÃÎ ÌÅÒÎÄÀ
Ïóñòü ÎËÖ � g C� 1, åñëè âûõîä Og íå ñâÿçàí ñ êîíå÷íîé âåðøèíîé ÃÑÀ �.
Íàéäåì ðàçáèåíèå �C ìíîæåñòâà C1 íà êëàññû ÏÎËÖ. Âûïîëíèì êîäèðîâà-
íèå ÎËÖ � g C� òàê, ÷òîáû ìàêñèìàëüíî âîçìîæíîå ÷èñëî êëàññîâ Bi C�� ,
ãäå | |�C I� , ïðåäñòàâëÿëîñü îäíèì îáîáùåííûì èíòåðâàëîì R1-ìåðíîãî áó-
ëåâà ïðîñòðàíñòâà. Ïóñòü ni — ÷èñëî îáîáùåííûõ èíòåðâàëîâ, ïðåäñòàâëÿþ-
ùèõ êëàññ Bi C�� . Ïðåäñòàâèì ìíîæåñòâî �C â âèäå � � �C A B� � . Ïðè
ýòîì ìíîæåñòâà �A è �B ñòðîÿòñÿ ñëåäóþùèì îáðàçîì:
( )n Bi i A� � �1 � ;
( )n Bi i B� � �1 � .
Èñòî÷íèêîì êîäîâ êëàññîâ Bi A�� ÿâëÿåòñÿ ðåãèñòð Ðã. Ïðè ýòîì êîä êëàñ-
ñà Bi A�� îïðåäåëÿåòñÿ ñîîòâåòñòâóþùèì èíòåðâàëîì R1-ìåðíîãî áóëåâà
ïðîñòðàíñòâà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 115
Ñõåìà
Àäðåñàöèè
Ìèêðîêîìàíä
ÑÒ
Ðã
Start
Clock
ÒÕ
Y
y0
+1
Start TB
S
R
E
Óïðàâëÿþùàÿ
Ïàìÿòü
Fetch
yE
y0
Ðèñ. 1. Ñòðóêòóðíàÿ ñõåìà ÊÌÓÓ U1
�
�
�
�
y0
y0
y0
Çàêîäèðóåì êëàññû Bi B�� äâîè÷íûìè êîäàìè C Bi( ) ðàçðÿäíîñòè
�R B3 2 1� log (| | )� , (4)
èñïîëüçóÿ ïåðåìåííûå èç ìíîæåñòâà Z z zR� { }1 3
, ,� . Äëÿ ôîðìèðîâàíèÿ êî-
äîâ C Bi( ) íåîáõîäèì áëîê ïðåîáðàçîâàòåëÿ êîäîâ (ÁÏÊ), êîòîðûé ðåàëèçóåò
ñèñòåìó ôóíêöèé
Z Z� ( )� . (5)
Ïóñòü äëÿ ðåàëèçàöèè ïàìÿòè èñïîëüçóþòñÿ áëîêè ÏÏÇÓ, èìåþùèå S âõî-
äîâ è t âûõîäîâ. Ïðèìåì äëÿ óïðîùåíèÿ, ÷òî R S� . Òîãäà äëÿ ðåàëèçàöèè
ïàìÿòè íåîáõîäèìî
m
N
t
1
2
�
��
�
��
(6)
ìèêðîñõåì ÏÏÇÓ. ×èñëèòåëü ôîðìóëû (6) îïðåäåëÿåòñÿ ÷èñëîì ìèêðîîïåðàöèé
y Yn � è äâóìÿ äîïîëíèòåëüíûìè ïåðåìåííûìè: y0 è yE . Î÷åâèäíî, ÷òî ÷àñòü
âûõîäîâ áëîêà ÓÏ ìîãóò áûòü èçáûòî÷íûìè è îïðåäåëÿþòñÿ ôîðìóëîé
R m t N4 1 2�
( ) . (7)
Ñâîáîäíûå âûõîäû ìîæíî èñïîëüçîâàòü äëÿ ðåàëèçàöèè ÷àñòè êîäà C Bi( ) .
Ïðè ýòîì ÁÏÊ äîëæåí ãåíåðèðîâàòü òîëüêî
R R R5 3 4�
(8)
ïåðåìåííûõ. Îòìåòèì, ÷òî â âûðàæåíèè (5) åäèíèöà äîáàâëÿåòñÿ, åñëè
Bi B�� .
Èòàê, â îáùåì ñëó÷àå äëÿ ïðåäñòàâëåíèÿ êîäîâ êëàññîâ ÏÎËÖ ìîæíî èñ-
ïîëüçîâàòü òðè èñòî÷íèêà: ðåãèñòð, ïðåîáðàçîâàòåëü êîäîâ è óïðàâëÿþùóþ ïà-
ìÿòü. Ýòîò ïîäõîä ïîðîæäàåò ÊÌÓÓ U 2 , ïðèâåäåííîå íà ðèñ. 2, ãäå ìíîæåñòâî
Z Z1 � ïðåäñòàâëÿåò ðàçðÿäû êîäà C Bi( ), ãåíåðèðóåìûå ïðåîáðàçîâàòåëåì êî-
äîâ. Àíàëîãè÷íî ìíîæåñòâî Z Z2 � ïðåäñòàâëÿåò ðàçðÿäû êîäà C Bi( ) , ãåíåðèðó-
åìûå ïàìÿòüþ. Î÷åâèäíî, ÷òî âûïîëíÿþòñÿ óñëîâèÿ Z Z1 2� �� è Z Z Z1 2� � .
116 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
Ñõåìà
Àäðåñàöèè
Ìèêðîêîìàíä
Õ
Y
y0
Start TB
S
R
E
Óïðàâëÿþùàÿ
Ïàìÿòü
Fetch
yE
Z 2
Ïðåîáðàçîâàòåëü
Êîäîâ
ÑÒ
Ðã
Start
Clock
Ò
+1
Z
1
Ðèñ. 2. Ñòðóêòóðíàÿ ñõåìà ÊÌÓÓ U2
�
�
�
y0
y0
y0
Ïðèíöèïû ôóíêöè-
îíèðîâàíèÿ ÊÌÓÓ U 1 è
U 2 ñîâïàäàþò. Îòìå-
òèì, ÷òî â çàâèñèìîñòè
îò ðàçëè÷íûõ óñëîâèé
ìîäåëü U 2 ìîæíî ïðå-
îáðàçîâàòü â îäíó èç
øåñòè ìîäåëåé, ïðèâå-
äåííûõ â òàáë. 1. Çäåñü â
ñòîëáöàõ Ðã, ÁÏÊ è ÓÏ
çàïèñàíû èñòî÷íèêè êî-
äîâ êëàññîâ ïñåâäîýêâè-
âàëåíòíûõ öåïåé. Îòìå-
òèì, ÷òî ìîäåëè U 1, U 3
è U 4 èçâåñòíû [4], à ìî-
äåëè U 2 , U 5– U 7 îðèãè-
íàëüíû. Â íàñòîÿùåé ðàáîòå ïðåäëîæåí ìåòîä ñèíòåçà ÊÌÓÓ U 2 . Ìåòîäû ñèí-
òåçà äëÿ ìîäåëåé U 5– U 7 ïîðîæäàþòñÿ èç ïðåäëàãàåìîãî ìåòîäà óäàëåíèåì íå-
êîòîðûõ ýòàïîâ.
Ïðåäëàãàåìûé ìåòîä âêëþ÷àåò ñëåäóþùèå ýòàïû:
1) ôîðìèðîâàíèå äëÿ ÃÑÀ � ìíîæåñòâ C, C1 è �C ;
2) îïòèìàëüíîå êîäèðîâàíèå ÎËÖ � g C� 1 è èõ êîìïîíåíòîâ;
3) ôîðìèðîâàíèå ìíîæåñòâ �A è �B ;
4) êîäèðîâàíèå êëàññîâ Bi B�� êîäàìè C Bi( ) ;
5) îïðåäåëåíèå ïàðàìåòðîâ R4 , R5 è èõ ñîîòíîøåíèé;
6) ôîðìèðîâàíèå ñîäåðæèìîãî ÓÏ;
7) ôîðìèðîâàíèå òàáëèöû ïåðåõîäîâ ÊÌÓÓ;
8) ôîðìèðîâàíèå òàáëèöû èñòèííîñòè ÁÏÊ;
9) ñèíòåç ñõåìû ÊÌÓÓ â çàäàííîì áàçèñå.
Íàïîìíèì, ÷òî ïðèìåíåíèå ìîäåëè U 1 èìååò ñìûñë òîëüêî ïðè âûïîëíåíèè
óñëîâèé (1) è (3). Åñëè óñëîâèå (1) íå âûïîëíÿåòñÿ, òî ÃÑÀ � íå ÿâëÿåòñÿ ëèíåé-
íîé è íåîáõîäèìî èñïîëüçîâàòü ìîäåëü àâòîìàòà Ìóðà [11]. Åñëè äëÿ ëèíåéíîé
ÃÑÀ óñëîâèå (3) íå âûïîëíÿåòñÿ, òî ýòî ïðèâîäèò ê ðåçêîìó ðîñòó ÷èñëà ÂÁÏ
â áëîêå ÓÏ ïî ñðàâíåíèþ ñ èçâåñòíûìè ìîäåëÿìè ÊÌÓÓ [4]. Ðàññìîòðèì íåêî-
òîðûå ýòàïû ïðåäëàãàåìîãî ìåòîäà.
Ýòàï 1 âûïîëíÿåòñÿ ïî èçâåñòíîé ìåòîäèêå [4], ïðè ýòîì ÷èñëî G öåïåé
� g C� ÿâëÿåòñÿ ìèíèìàëüíî âîçìîæíûì. Ðàçáèåíèå �C ôîðìèðóåòñÿ íà îñíîâå
îïðåäåëåíèÿ 4 òðèâèàëüíûì îáðàçîì.
Îïòèìàëüíîå êîäèðîâàíèå ÎËÖ � g C� 1 âûïîëíÿåòñÿ ïî ìåòîäèêå, àíàëîãè÷-
íîé îïòèìàëüíîìó êîäèðîâàíèþ ñîñòîÿíèé àâòîìàòà Ìóðà [11]. Äëÿ ðåøåíèÿ ýòîé
çàäà÷è ìîæíî èñïîëüçîâàòü èçâåñòíûå ìåòîäû ñèìâîëüíîé îïòèìèçàöèè [3]. Êîìïî-
íåíòû âñåõ öåïåé � g C� êîäèðóþòñÿ òðèâèàëüíûì îáðàçîì. Äåñÿòè÷íûé ýêâèâà-
ëåíò êîäà ïåðâîãî êîìïîíåíòà ðàâåí íóëþ, âòîðîãî — åäèíèöå, òðåòüåãî — äâóì
è ò.ä.. Òàêîå êîäèðîâàíèå óäîâëåòâîðÿåò óñëîâèþ (2).
Ìíîæåñòâà �A è �B ôîðìèðóþòñÿ òðèâèàëüíûì îáðàçîì íà îñíîâå ðåçóëü-
òàòà îïòèìàëüíîãî êîäèðîâàíèÿ ÎËÖ � g C� 1. Êëàññû Bi B�� öåëåñîîáðàçíî
êîäèðîâàòü òàê, ÷òîáû óìåíüøèòü êîëè÷åñòâî òåðìîâ â ôóíêöèÿõ z Zr � . Äëÿ
ýòîãî ìîæíî èñïîëüçîâàòü ïðîñòîå ïðàâèëî: ÷åì áîëüøå îáîáùåííûõ èíòåðâà-
ëîâ íåîáõîäèìî äëÿ ïðåäñòàâëåíèÿ êëàññà Bi B�� , òåì ìåíüøå åäèíèö äîëæåí
ñîäåðæàòü êîä C Bi( ) . Ýòî ïðàâèëî ÿâëÿåòñÿ àäàïòàöèåé èçâåñòíîãî ìåòîäà
êîäèðîâàíèÿ ñîñòîÿíèé, îðèåíòèðîâàííîãî íà D-òðèããåðû [1].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 117
Ò à á ë è ö à 1 . Ìîäåëè ÊÌÓÓ, ïîðîæäàåìûå
ÊÌÓÓ U 2
Ìîäåëü
Èñòî÷íèêè êîäîâ
êëàññîâ
ïñåâäîýêâèâàëåíòíûõ
öåïåé
Óñëîâèÿ ïðèìåíåíèÿ ìîäåëè
Ðã ÁÏÊ ÓÏ
U1 1 0 0 � �A C� ; �B � �.
U 2 1 1 1 � A � � ; �B � � ; 0 4 3� �R R .
U 3 0 1 0 � A � � ; � �B C� ; R4 0� .
U 4 0 0 1 � A � � ; � �B C� ; R R4 3� .
U 5 0 1 1 � A � � ; � �B C� ; 0 4 3� �R R .
U 6 1 0 1 � A � � ; �B � � ; R R4 3� .
U 7 1 1 0 � A � � ; �B � � ; R4 0� .
Ýòàï 5 ñâîäèòñÿ ê âûïîëíåíèþ ïðîñòåéøèõ àðèôìåòè÷åñêèõ îïåðàöèé. Ñî-
äåðæèìîå ÓÏ ïðåäñòàâëÿåòñÿ òàáëèöåé ñî ñòîëáöàìè A bq( ) , Y bq( ) , y0 , yE , q .
Ïåðåä ïîñòðîåíèåì òàáëèöû ïðîèñõîäèò ïðåîáðàçîâàíèå èñõîäíîé ÃÑÀ [4].
Åñëè âåðøèíà b Dq
g� è b Oq g� , òî â íåå ââîäèòñÿ ïåðåìåííàÿ y0 . Ïðè ýòîì
â ñòîëáöå y0 ñòðîêè q , q G�1, , òàáëèöû çàïèñûâàåòñÿ åäèíèöà. Åñëè
� � �b b Eq E, , òî â âåðøèíó b Bq � 1 ââîäèòñÿ ïåðåìåííàÿ yE . Ïðè ýòîì â ñòîëáöå
yE ñòðîêè q , q G�1, , òàáëèöû òàêæå çàïèñûâàåòñÿ åäèíèöà.
Òàáëèöà ïåðåõîäîâ ÊÌÓÓ ñòðîèòñÿ íà îñíîâå ñèñòåìû îáîáùåííûõ ôîðìóë
ïåðåõîäà [4], êàæäûé ýëåìåíò êîòîðîé èìååò âèä
B X b i Ii
h
H
h h
i
� �
�
�
1
1( , ) , (9)
ãäå X h — êîíúþíêöèÿ ëîãè÷åñêèõ óñëîâèé, îïðåäåëÿþùàÿ ïåðåõîä èç âûõîäà
ÎËÖ � g iB� â âåðøèíó bh , H i
— ÷èñëî ïåðåõîäîâ èç âûõîäà Og . Ñèñòå-
ìå (9) ñîîòâåòñòâóåò òàáëèöà ïåðåõîäîâ ÊÌÓÓ, èìåþùàÿ ñòîëáöû: Bi , K Bi( ) ,
C Bi( ) , bh , A bh( ) , X h , �h , �h , h . Â ýòîé òàáëèöå ñòîëáåö � �h h( ) ñîäåðæèò
ôóíêöèè âîçáóæäåíèÿ òðèããåðîâ ñ÷åò÷èêà (ðåãèñòðà), ñîîòâåòñòâóþùèå åäèíè-
öàì â êîäå êîìïîíåíòà (êîäå ÎËÖ) bh (� g iB� , ãäå b Dh
g� ). ×èñëî ñòðîê H
â òàáëèöå îïðåäåëÿåòñÿ ñóììîé:
H H i
i
I
�
�
�
1
. (10)
Òàáëèöà èñòèííîñòè ÁÏÊ èìååò ñòîëáöû: V Bi
j( ) , Bi , C Bi( ) , Z
k
1, k. Çäåñü
V Bi
j( ) ñîîòâåòñòâóåò j -ìó îáîáùåííîìó èíòåðâàëó, â êîòîðûé âõîäèò êëàññ
Bi B�� , j Bi� | | . Ìíîæåñòâî Z
k
1 ñîäåðæèò ïåðåìåííûå z Zr � , ðàâíûå åäèíèöå
â êîäå C Bi( ) äëÿ k-é ñòðîêè òàáëèöû (k K�1, ). Ïðè ðàçáèåíèè ìíîæåñòâà Z öå-
ëåñîîáðàçíî ïðîðàíæèðîâàòü ôóíêöèè (5) ïî âîçðàñòàíèþ ÷èñëà òåðìîâ. Çàòåì
ïåðâûå R5 ôóíêöèé îïðåäåëÿþò ïåðåìåííûå z Zr � 1. Îñòàâøèåñÿ ïåðåìåííûå
z Z Zr �( \ )1 äîëæíû ôîðìèðîâàòüñÿ áëîêîì ïàìÿòè. Äëÿ ýòîãî â òàáëèöó ÓÏ
ââîäèòñÿ ñòîëáåö Z bq( ) . Ïóñòü b Oq g� , ãäå � g iB� è Bi B�� . Òîãäà â ÿ÷åéêó
ïàìÿòè ñ àäðåñîì A bq( ) çàïèñûâàþòñÿ çíà÷åíèÿ ïåðåìåííûõ z Zr � 2 , êîòîðûå
îïðåäåëÿþòñÿ íà îñíîâå àíàëèçà êîäà C Bi( ) .
Äëÿ ðåàëèçàöèè ñõåìû ÊÌÓÓ íåîáõîäèìî èç òàáëèöû åãî ïåðåõîäîâ ïîëó-
÷èòü ñèñòåìó ôóíêöèé
� �� ( , , )� Z X ,
(11)
� �� ( , , )� Z X ,
à èç òàáëèöû èñòèííîñòè ÁÏÊ ïîëó÷èòü ôóíêöèè
Z Z1 1� ( )� . (12)
Äàëüíåéøàÿ ðåàëèçàöèÿ ñâîäèòñÿ ê èñïîëüçîâàíèþ ñòàíäàðòíûõ ïàêåòîâ [8, 9]
è âûõîäèò çà ðàìêè íàñòîÿùåé ñòàòüè.
ÏÐÈÌÅÐ ÏÐÈÌÅÍÅÍÈß ÏÐÅÄËÎÆÅÍÍÎÃÎ ÌÅÒÎÄÀ
Ïóñòü äëÿ íåêîòîðîé ÃÑÀ �1 ïîëó÷åíî ìíîæåñòâî ÎËÖ C � { }� �1 16, ,� ,
�16 1�C , è äàííàÿ ãðàô-ñõåìà âêëþ÷àåò M � 48 îïåðàòîðíûõ âåðøèí, ïðè
118 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
ýòîì L � 5 , N �13 . Ïóñòü ÎËÖ � g C� 1 îáðàçóþò ðàçáèåíèå �C B B� { }1 6, ,� ,
ãäå B1 1� { }� , B2 2 3 4� { }� � �, , , B3 5 6 7� { }� � �, , , B4 8 11� { }� �, ,� ,
B5 12 13 14� { }� � �, , , B6 15� { }� , è ìàêñèìàëüíîå ÷èñëî êîìïîíåíòîâ Q � 4 .
Òîãäà R2 2� , T T T� { }1 2, . Èòàê, M � 48 , G �16 , ñëåäîâàòåëüíî R � 6 , R1 4� ,
óñëîâèå (3) âûïîëíÿåòñÿ è èñïîëüçîâàíèå ìîäåëè U 1 èìååò ñìûñë.
Çàêîäèðóåì ÎËÖ � g C� êàê ïîêàçàíî íà ðèñ. 3. Â ýòîé êàðòå Êàðíî ÎËÖ
�16 1�C ðàññìîòðåíà êàê íåñóùåñòâåííàÿ, ÷òî ïîçâîëÿåò èñïîëüçîâàòü íàáîð 0110
äëÿ ìèíèìèçàöèè ÷èñëà îáîáùåííûõ èíòåðâàëîâ. Èç ðèñ. 3 èìååì: V B( )1 0000� ,
V B( ) **2 01� , V B( ) *
3
1 00 1� , V B( ) *
3
2 001� , V B( ) **4 10� , V B( ) *
5
1 110� , V B( )
5
2 �
�11 1* , V B( ) *6 110� . Òàêèì îáðàçîì, �A B B B B�{ }1 2 4 6, , , è �B B B�{ }3 5, . Ïîñ-
êîëüêó �A �� è �B ��, èç òàáë. 1
ñëåäóåò, ÷òî ìîæíî èñïîëüçîâàòü ìîäå-
ëè U 2 , U 6 è U 7 .
Ïîñêîëüêó êàæäûé êëàññ Bi B��
ïðåäñòàâëÿåòñÿ äâóìÿ îáîáùåííûìè
èíòåðâàëàìè, ýòè êëàññû êîäèðóþòñÿ
òðèâèàëüíûì îáðàçîì. Èç ôîðìóëû (4)
ñëåäóåò, ÷òî R3 2� , ò.å. Z z z� { }1 2, .
Ïóñòü C B( )3 01� , C B( )5 10� , à êîä 00
ñîîòâåòñòâóåò óñëîâèþ Bi A�� .
Ïóñòü äëÿ ðåàëèçàöèè ÓÏ èñïîëü-
çóþòñÿ ìèêðîñõåìû ÏÏÇÓ, ó êîòîðûõ
S � 6 , t � 8 . Ïîñêîëüêó N �13, èç ôîð-
ìóëû (7) èìååì R4 1� . Òàêèì îáðàçîì, äëÿ ðåàëèçàöèè ÊÌÓÓ íåîáõîäèìî âû-
áðàòü ìîäåëü U 2 . Èç (8) èìååì R5 1� . Ïóñòü Z z1
1� { } è Z z2
2� { }.
Ïðåäïîëîæèì, ÷òî ÎËÖ � 5 èìååò ÷åòûðå êîìïîíåíòà: � 5 15 16 17 18� � �b b b b, , , .
Î÷åâèäíî, K b( )15 00� , �, K b( )18 11� . Èç êàðòû Êàðíî (ñì. ðèñ. 3) ìîæíî ïîëó-
÷èòü ñëåäóþùèå àäðåñà: A b( )15 000100� , �, A b( )18 000111� . Òàê êàê � 5 3�B è
C B( )3 01� , òî z2 1� äëÿ ÿ÷åéêè ñ àäðåñîì 000111. Ïóñòü Y b y y( ) ,15 3 4� { },
Y b y y( ) ,16 2 6� { }, Y b y y( ) ,17 7 9� { } è
Y b y y( ) ,18 1 8� { }. Òîãäà ñîäåðæèìîå
ÓÏ äëÿ ÎËÖ � 5 �C áóäåò èìåòü âèä,
ïðèâåäåííûé â òàáë. 2.
Àíàëîãè÷íî ìîæíî ïîëó÷èòü ñîäåð-
æèìîå ÓÏ äëÿ îñòàëüíûõ ÎËÖ � g C� .
Îòìåòèì, ÷òî â ñòîëáöå Y bq( ) çàïèñàíû
ìèêðîîïåðàöèè y Yn � , êîòîðûå ïðè ðåà-
ëèçàöèè ñõåìû ÓÏ çàìåíÿþòñÿ ñâîèìè
êîäàìè [4].
Ïóñòü ñèñòåìà îáîáùåííûõ ôîðìóë ïåðåõîäà äëÿ ÃÑÀ �1 èìååò ñëåäóþùèé
âèä:
B x b x x b x x x b x x x b
B x b x x b
1 1 4 1 2 8 1 2 3 10 1 2 3 12
2 4 15 4 5 1
� � � �
� �
;
9 4 5 22
3 2 3 24 2 3 28 2 5 32 2 5 34
4 1
�
� � � �
�
x x b
B x x b x x b x x b x x b
B x
;
;
x b x x b x x b x x b
B b
B x b x b
2 17 1 2 37 1 4 39 1 4 41
5 44
6 4 38 4 4
� � �
�
� �
;
;
6 .
(13)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 119
00
00
01
11
10
01 11 10
�1
�3�4
�1�2
�2
�12
�8 �9 �10 �11
�15�14�13
�3 �4 �16
�5 �6 �7
Ðèñ. 3. Îïòèìàëüíûå êîäû ÎËÖ äëÿ ÃÑÀ �1
Ò à á ë è ö à 2. Ôðàãìåíò ñîäåðæèìîãî
ÓÏ äëÿ ÎËÖ � 5
A bq( ) Y bq( ) y0 yE Z
2 q
000100 y y3 4, 1 0 0 15
000101 y y2 6, 1 0 0 16
000110 y y7 9, 1 0 0 17
000111 y y1 8, 0 0 1 18
Ðàññìîòðèì ôðàãìåíò òàáëèöû ïåðåõîäîâ ÊÌÓÓ U 2 (òàáë. 3) äëÿ êëàññîâ
B B3 �� è B B4 �� . Ïóñòü b I24 8
1� , b I28 9
1� , b I32 10
1� , b I34 11
1� , b I17 5
2� è
K b( )17 10� , b I37 12
1� , b I39 13
1� è b I41 14
1� . Î÷åâèäíî, äëÿ âñåõ âåðøèí, êðîìå
b17 , âûïîëíÿåòñÿ óñëîâèå K bq( ) � 00 (äëÿ ðàññìàòðèâàåìûõ êëàññîâ
B B C3 4, �� ). Ôðàãìåíò òàáëèöû ïåðåõîäîâ ÊÌÓÓ U 2 èìååò âîñåìü ñòðîê. Òàê
êàê ôîðìóëû äëÿ B1 è B2 èç (13) ñîäåðæàò ñåìü òåðìîâ, òî ïåðâûé ïåðåõîä äëÿ
êëàññà B3 èìååò âîñüìîé íîìåð.
Î÷åâèäíà ñâÿçü òàáë. 3 ñ ñèñòåìîé (13) è ðèñ. 3, èç êîòîðîãî áåðóòñÿ êîäû
ÎËÖ � g C� . Òàáëèöà ïåðåõîäîâ ÿâëÿåòñÿ îñíîâîé äëÿ ôîðìèðîâàíèÿ ñèñòåì
(10), (11), êàæäàÿ ôóíêöèÿ êîòîðûõ ïðåäñòàâëÿåòñÿ â âèäå
D C z Xr
h
H
rh
r
R
r
l
r
R
r
mrh rh�
�
�
�
�
!
"
"
#
�
�
�
�
!
"
"
#
� � �
� # #
1 1 1
� h , (14)
ãäå áóëåâà ïåðåìåííàÿ Crh �1, åñëè è òîëüêî åñëè â h-é ñòðîêå òàáëèöû çàïè-
ñàíî D r Rr ( , )�1 . Âòîðîé ÷ëåí ôîðìóëû (14) ñîîòâåòñòâóåò êîäó K Bi( ), ãäå
lrh �{ }0 1, ,* — çíà÷åíèå r-ãî ðàçðÿäà êîäà ( , )r R�1 1 . Ïðè ýòîì � �r r
0 � ,
� �r r
1 � , �r
* �1. Òðåòèé ÷ëåí ôîðìóëû (14) ñîîòâåòñòâóåò êîäó C Bi( ) , ãäå
mrh �{ }0 1, — çíà÷åíèå r-ãî ðàçðÿäà êîäà ( , )r R�1 3 . Êîëè÷åñòâî ñòðîê â òàá-
ëèöå îïðåäåëÿåòñÿ ôîðìóëîé (10). Â ðàññìîòðåííîì ïðèìåðå H �18 .
Íàïðèìåð, ñ ó÷åòîì çàêîíà ñêëåèâàíèÿ [3], ìîæíî ïîëó÷èòü ñëåäóþùóþ
ôîðìóëó:
D z z z z x x z z x1 1 2 1 2 1 2 1 2 1 2 1 2 1� � �� � � � , (15)
ãäå ïåðâûé ÷ëåí ñîîòâåòñòâóåò h-ì ñòðîêàì 8–11 òàáë. 3, âòîðîé — h-é ñòðî-
êå 13, òðåòèé — h-ì ñòðîêàì 14, 15. Íàïîìíèì, ÷òî äëÿ ÏËÈÑ òèïà CPLD íåîá-
õîäèìî âûïîëíèòü ðàçäåëüíóþ ìèíèìèçàöèþ ðåàëèçóåìûõ ñèñòåì áóëåâûõ ôóíê-
öèé [7, 10].
Ðàññìîòðèì òàáëèöó èñòèííîñòè ÁÏÊ (òàáë. 4), èìåþùóþ äâå ñòðîêè. Èç
ýòîé òàáëèöû ôîðìèðóåòñÿ ñèñòåìà (12), êàæäàÿ ôóíêöèÿ êîòîðîé èìååò âèä
z Cr
k
K
rk
r
R
r
lrh�
�
�
�
�
!
"
"
� �
� #
1 1
� , (16)
ãäå áóëåâà ïåðåìåííàÿ Crk �1, åñëè è òîëüêî åñëè â k-é ñòðîêå òàáëèöû çàïè-
ñàíà ïåðåìåííàÿ z Zr � 1. Âòîðûå ÷ëåíû ôîðìóë (14) è (16) àíàëîãè÷íû. Íà
îñíîâàíèè òàáë. 4 ìîæíî ïîëó÷èòü ñëåäóþùóþ ôîðìóëó: z1 1 2 3 1 2 4� �� � � � � � .
120 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
Ò à á ë è ö à 3. Ôðàãìåíò òàáëèöû ïåðåõîäîâ ÊÌÓÓ U 2
Bi K Bi( ) C Bi( ) bh A bh( ) Xh �h �h h
B3 **** 01 b24 100000 x x2 3 — D1 8
b28 100100 x x2 3 — D D1 4 9
b32 101100 x x2 5 — D D D1 3 4 10
b34 101000 x x2 5 — D D1 3 11
B4 10** 00 b17 000110 x x1 2 D5 D4 12
b37 110000 x x1 2 — D D1 2 13
b39 110100 x x1 4 — D D D1 2 4 14
b41 111100 x x1 4 — D D D D1 2 3 4 15
Êàê óæå îòìå÷àëîñü, ýòàï ðåàëè-
çàöèè ñõåìû ÊÌÓÓ â äàííîé ñòàòüå
íå ðàññìîòðåí. Îäíàêî àâòîðàìè ðåà-
ëèçîâàíà ÑÀÏÐ, ïîçâîëÿþùàÿ ñîâ-
ìåñòíî ñ ïàêåòîì WebPack ôèðìû
Xilinx ñèíòåçèðîâàòü ñõåìû ÊÌÓÓ
U 1–U 7 .
ÐÅÇÓËÜÒÀÒÛ ÈÑÑËÅÄÎÂÀÍÈÉ
Äëÿ ïðîâåäåíèÿ èññëåäîâàíèé ñ öåëüþ îïðåäåëåíèÿ îáëàñòè ïðèìåíåíèÿ òîé
èëè èíîé ñòðóêòóðû áûë ðàçðàáîòàí ïðîãðàììíûé êîìïëåêñ (ðèñ. 4), ñîñòîÿ-
ùèé èç ñëåäóþùèõ ýëåìåíòîâ:
$ fsmEditor — ïðîãðàììà äëÿ ñîçäàíèÿ è ðåäàêòèðîâàíèÿ ÃÑÀ ñ ïîìîùüþ
ãðàôè÷åñêèõ ïðèìèòèâîâ (âñòðîåííûé ìîäóëü fsmGen ïîçâîëÿåò ïàêåòíî ãåíåðè-
ðîâàòü ÃÑÀ ñ çàäàííûìè ïàðàìåòðàìè);
$ VHDL Generator — ïðîãðàììà, ïîçâîëÿþùàÿ íà îñíîâå XML-îïèñàíèÿ àë-
ãîðèòìà è íåîáõîäèìûõ ïàðàìåòðîâ ñîçäàòü VHDL-ìîäåëü óïðàâëÿþùåãî àâòî-
ìàòà, ñèíòåçèðóåìîãî ïî ÃÑÀ;
$ ftclGen — óòèëèòà, íåîáõîäèìàÿ äëÿ ñîçäàíèÿ ñêðèïòà óïðàâëåíèÿ ðàáî-
òîé ñèñòåìû XST, âõîäÿùåé â Xilinx WebPack, íà îñíîâå äàííûõ, ïîëó÷åííûõ îò
VHDL Generator (âîçìîæíà ïàêåòíàÿ ãåíåðàöèÿ íà îñíîâå íàáîðà ñîçäàííûõ ðà-
íåå ôàéëîâ *.vhd);
$ Xilinx WebPack — ïðîãðàììíûé ïàêåò, ïðåäíàçíà÷åííûé äëÿ ïðîåêòèðî-
âàíèÿ óñòðîéñòâ íà ìèêðîñõåìàõ ÏËÈÑ ôèðìû Xilinx (âõîäÿùèé â ïàêåò ìîäóëü
XST íà îñíîâå âõîäíûõ ôàéëîâ *.vhd è *.mif ñîãëàñíî ñêðèïòó óïðàâëåíèÿ, ïåðå-
äàííîìó îò tclGen, ãåíåðèðóåò ôàéë ïðîøèâêè ìèêðîñõåìû, à òàêæå ìíîæåñòâî
ôàéëîâ îò÷åòà, ñðåäè êîòîðûõ íàõîäÿòñÿ äàííûå îá àïïàðàòóðíûõ çàòðàòàõ, òðå-
áóåìûõ äëÿ ðåàëèçàöèè àâòîìàòà íà äàííîé ìèêðîñõåìå);
$ rptAnlzr — óòèëèòà, ïàêåòíî îáðàáàòûâàþùàÿ íàáîðû ôàéëîâ *.rpt , ïîëó-
÷åííûõ îò Xilinx WebPack, è ôîðìèðóþùàÿ íà èõ îñíîâå òàáëèöû äàííûõ
â ôîðìàòå *.mat;
$ MathWorks MatLab — ïàêåò ïðèêëàäíûõ ïðîãðàìì äëÿ ðåøåíèÿ çàäà÷ òåõ-
íè÷åñêèõ âû÷èñëåíèé, ÿâëÿþùèéñÿ ìîùíûì ñðåäñòâîì ïîñòðîåíèÿ ãðàôèêîâ íà
îñíîâå äàííûõ, ïîëó÷åííûõ îò rptAnlzr.
Äëÿ ýêñïåðèìåíòà âûáðàíû ÃÑÀ ñî ñëåäóþùèìè ïàðàìåòðàìè:
$ êîëè÷åñòâî âåðøèí îò 10 äî 400 ñ øàãîì 10;
$ äîëÿ îïåðàòîðíûõ âåðøèí îò 50 äî 90 % ñ øàãîì 10 %;
$ êîëè÷åñòâî ìèêðîîïåðàöèé N �15 ;
$ êîëè÷åñòâî ëîãè÷åñêèõ óñëîâèé L � 5.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 121
MathWorks
MatLab
fsmEditor
fsmGen
tclGen
VHDL
Generator Xilinx
WebPack
rptAnlzr
*.mat
*.xml
*.tcl
*.vhd
*.mif
*.rpt
Ðèñ. 4. Ïðîãðàììíûé êîìïëåêñ äëÿ ïðîâåäåíèÿ èññëåäîâàíèé
Ò à á ë è ö à 4 . Òàáëèöà èñòèííîñòè
ÁÏÊ
V B
i
j( ) Bi C Bi( ) Z
k
1
lC
110* B5 10 z1 1
11*1 B5 10 z1 2
Äëÿ êàæäîé ÃÑÀ ñèíòåçèðîâàíà ñòðóêòóðà ÊÌÓÓ ñ ðàçäåëåíèåì êîäîâ U 1
(cmcu_cs), à òàêæå èññëåäóåìàÿ ñòðóêòóðà U 2 (cmcu_fcs). Äëÿ ñðàâíåíèÿ ñ êëàñ-
ñîì àâòîìàòîâ ñ æåñòêîé ëîãèêîé òàêæå ñèíòåçèðîâàíû àâòîìàòû Ìóðà (Moore).
Êàæäîå èçìåðåíèå, ïðåäñòàâëåííîå íà ãðàôèêàõ, ÿâëÿåòñÿ ñðåäíèì çíà÷åíèåì ðå-
çóëüòàòîâ ñèíòåçà äëÿ ïÿòè ðàçëè÷íûõ ÃÑÀ ñ îäèíàêîâûìè ïàðàìåòðàìè.
122 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3
Ðèñ. 5. Àïïàðàòóðíûå çàòðàòû ïðè ðåàëèçàöèè ñòðóêòóð ÊÌÓÓ U1 , U2 , è Ìóðà: ÃÑÀ ñîäåðæèò
70 % îïåðàòîðíûõ âåðøèí (à) è 90 % îïåðàòîðíûõ âåðøèí (á)
à
á
×èñëî âåðøèí ÃÑÀ
×èñëî âåðøèí ÃÑÀ
Àâòîìàò Ìóðà
Àâòîìàò Ìóðà
U1
U2
U1
U2
×
è
ñë
î
è
ñï
î
ë
ü
çî
â
àí
í
û
õ
ì
àê
ð
î
ÿ
÷
åå
ê
Èññëåäîâàíèå àïïàðàòóðíûõ çàòðàò ïîêàçàëî ýôôåêòèâíîñòü ïðèìåíåíèÿ
ïðåäëàãàåìûõ ìåòîäèê äëÿ âñåõ ÃÑÀ (ðèñ. 5). Òàê, ìîäåëü ÊÌÓÓ U 2 òðåáóåò
ìåíüøå àïïàðàòóðíûõ çàòðàò â ñðàâíåíèè ñ áàçîâûì ÊÌÓÓ U 1 è àâòîìàòîì
Ìóðà. Îòìåòèì, ÷òî ñ óâåëè÷åíèåì äîëè îïåðàòîðíûõ âåðøèí â ÃÑÀ àïïàðàòóð-
íûå çàòðàòû äëÿ ðåàëèçàöèè àâòîìàòà Ìóðà óâåëè÷èâàþòñÿ, à äëÿ ðåàëèçàöèè
óñòðîéñòâà êëàññà ÊÌÓÓ — óìåíüøàþòñÿ. Ìàêñèìàëüíûé âûèãðûø ïðè èñ-
ïîëüçîâàíèè ñòðóêòóðû U 2 ïî ñðàâíåíèþ ñ ïðèìåíåíèåì ñòðóêòóðû àâòîìàòà
Ìóðà äîñòèãàë ïðèáëèçèòåëüíî 40 ìàêðîÿ÷ååê äëÿ ÃÑÀ ñ 70 % îïåðàòîðíûõ âåð-
øèí è 55 ìàêðîÿ÷ååê äëÿ ÃÑÀ ñ 90 % îïåðàòîðíûõ âåðøèí.
ÇÀÊËÞ×ÅÍÈÅ
Ïðîâåäåííûå èññëåäîâàíèÿ ïîçâîëèëè âûÿâèòü óìåíüøåíèå àïïàðàòóðíûõ çà-
òðàò ïðè ðåàëèçàöèè ÊÌÓÓ ñ íåñêîëüêèìè èñòî÷íèêàìè êîäîâ â áàçèñå CPLD-
ìèêðîñõåì. Ýòî âîçìîæíî áëàãîäàðÿ òàêèì ãëàâíûì ôàêòîðàì, êàê áîëüøîé êî-
ýôôèöèåíò îáúåäèíåíèÿ ïî âõîäó ñîâðåìåííûõ ìàêðîÿ÷ååê ïðîãðàììèðóåìîé
ìàòðè÷íîé ëîãèêè, à òàêæå åñòåñòâåííàÿ èçáûòî÷íîñòü ìèêðîñõåì ÏÏÇÓ, îá-
óñëîâëåííàÿ òåì, ÷òî êîëè÷åñòâî èõ âûõîäîâ îãðàíè÷åíî îïðåäåëåííûì ìíî-
æåñòâîì ÷èñåë.
Îòìåòèì, ÷òî ìåòîä ïðèìåíèì òîëüêî äëÿ èíòåðïðåòàöèè ëèíåéíûõ ÃÑÀ.
Äàëüíåéøèå èññëåäîâàíèÿ ñâÿçàíû ñ àíàëèçîì ïðîöåññà ñèíòåçà äðóãèõ ìî-
äåëåé ÊÌÓÓ, ïðåäñòàâëåííûõ â òàáë. 1, ñ ñðàâíåíèåì ïàðàìåòðîâ ñèíòåçèðîâàí-
íûõ ñõåì, ñîñòàâëåíèåì àíàëèòè÷åñêèõ çàâèñèìîñòåé ìåæäó ïàðàìåòðàìè èñõîä-
íûõ ÃÑÀ è õàðàêòåðèñòèêàìè ïîëó÷àåìûõ ñõåì, êîòîðûå ïîçâîëÿò îïðåäåëÿòü
óñòðîéñòâî, íàèëó÷øèì îáðàçîì óäîâëåòâîðÿþùåå âûäâèãàåìûì òðåáîâàíèÿì.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. B a r a n o v S . Logic and system design of digital systems. — Tallinn: TUT press, 2008. — 266 p.
2. Ã ë ó ø ê î â Â . Ì . Ñèíòåç öèôðîâûõ àâòîìàòîâ. — Ì.: Ôèçìàòãèç, 1962. — 476 ñ.
3. D e M i c h e l i G . Synthesis and optimization of digital circuits. — New York: McGraw-Hill, 1994.
— 541 p.
4. B a r k a l o v A . , T i t a r e n k o L . Logiñ synthesis for compositional microprogram control units.
— Berlin: Springer, 2008. — 272 p.
5. Á à ð ê à ë î â À . À . , Ò è ò à ð å í ê î Ë . À . , Å ô è ì å í ê î Ê . Í . Îïòèìèçàöèÿ ñõåì êîìïîçè-
öèîííûõ ìèêðîïðîãðàììíûõ óñòðîéñòâ óïðàâëåíèÿ, ðåàëèçóåìûõ íà ÏËÈÑ // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2011. — ¹ 1. — Ñ. 179–188.
6. Ã ð ó ø â è ö ê è é Ð . È . , Ì ó ð ñ à å â À . Õ . , Ó ã ð þ ì î â Å . Ï . Ïðîåêòèðîâàíèå ñèñòåì íà
ìèêðîñõåìàõ ïðîãðàììèðóåìîé ëîãèêè. — CÏá: ÁÕÂ-Ïåòåðáóðã, 2002. — 636 ñ.
7. Ñ î ë î â ü ¸ â  .  . , Ê ë è ì î â è ÷ À . Ñ . Ëîãè÷åñêîå ïðîåêòèðîâàíèå öèôðîâûõ ñèñòåì íà
îñíîâå ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì. — Ì.: Ãîðÿ÷àÿ ëèíèÿ — Òåëåêîì,
2008. — 376 ñ.
8. A l t e r a devices overview. — http://www.altera.com/products/devices/common/dev-family_over-
view.html.
9. X i l i n x CPLDs. — http://www.xilinx.com/products/silicon_solutions/cplds/index.htm.
10. Á à ð ê à ë î â À . À . , Ò è ò à ð å í ê î Ë . À . , Ö î ë î ë î Ñ . À . Îïòèìèçàöèÿ ñõåìû àâòîìàòà
Ìóðà, ðåàëèçóåìîé â áàçèñå ÏËÈÑ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 5. —
Ñ. 180–186.
11. B a r k a l o v A . , T i t a r e n k o L . Logic synthesis for FSM-based control units. — Berlin:
Springer, 2009. — 233 p.
Ïîñòóïèëà 13.10.2011
Ïîñëå äîðàáîòêè 21.02.2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 3 123
|
| id | nasplib_isofts_kiev_ua-123456789-86239 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T18:52:13Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Баркалов, А.А. Титаренко, Л.А. Лаврик, А.С. 2015-09-10T18:59:00Z 2015-09-10T18:59:00Z 2013 Уменьшение аппаратурных затрат в устройстве управления с разделением кодов / А.А. Баркалов, Л.А. Титаренко, А.С. Лаврик // Кибернетика и системный анализ. — 2013. — Т. 49, № 3. — С. 113-123. — Бібліогр.: 11 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86239 004.3 Запропоновано метод зменшення апаратурних витрат у логічній схемі композиційного мікропрограмного пристрою керування при реалізації на CPLD. Метод базується на наявності псевдоеквівалентних операторних лінійних ланцюгів, великого коефіцієнта об’єднання за входом у макрочарунок PAL та вільних виходів вбудованих блоків пам’яті мікросхем ПЛІС. Наведено приклад використання запропонованого методу. Проведені дослідження показали, що метод зменшує апаратурні витрати до 30 %. A method for reducing hardware expenses in compositional microprogram control unit and CPLD chips is proposed. This method is based on the use of pseudoequivalent operational linear chains, wide fan-in of PAL macrocells and existence of free outputs of embedded memory block in CPLD chips. An example of applying the method is given. It is shown that the method reduces hardware expenses to 30%. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Уменьшение аппаратурных затрат в устройстве управления с разделением кодов Зменшення апаратурних витрат у пристрої керування з розділенням кодів Reduction of hardware expenses in control unit with code sharing Article published earlier |
| spellingShingle | Уменьшение аппаратурных затрат в устройстве управления с разделением кодов Баркалов, А.А. Титаренко, Л.А. Лаврик, А.С. Системный анализ |
| title | Уменьшение аппаратурных затрат в устройстве управления с разделением кодов |
| title_alt | Зменшення апаратурних витрат у пристрої керування з розділенням кодів Reduction of hardware expenses in control unit with code sharing |
| title_full | Уменьшение аппаратурных затрат в устройстве управления с разделением кодов |
| title_fullStr | Уменьшение аппаратурных затрат в устройстве управления с разделением кодов |
| title_full_unstemmed | Уменьшение аппаратурных затрат в устройстве управления с разделением кодов |
| title_short | Уменьшение аппаратурных затрат в устройстве управления с разделением кодов |
| title_sort | уменьшение аппаратурных затрат в устройстве управления с разделением кодов |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86239 |
| work_keys_str_mv | AT barkalovaa umenʹšenieapparaturnyhzatratvustroistveupravleniâsrazdeleniemkodov AT titarenkola umenʹšenieapparaturnyhzatratvustroistveupravleniâsrazdeleniemkodov AT lavrikas umenʹšenieapparaturnyhzatratvustroistveupravleniâsrazdeleniemkodov AT barkalovaa zmenšennâaparaturnihvitratupristroíkeruvannâzrozdílennâmkodív AT titarenkola zmenšennâaparaturnihvitratupristroíkeruvannâzrozdílennâmkodív AT lavrikas zmenšennâaparaturnihvitratupristroíkeruvannâzrozdílennâmkodív AT barkalovaa reductionofhardwareexpensesincontrolunitwithcodesharing AT titarenkola reductionofhardwareexpensesincontrolunitwithcodesharing AT lavrikas reductionofhardwareexpensesincontrolunitwithcodesharing |