Эффективный алгоритм синтеза многовыходных комбинационных автоматов
Предложен метод решения задачи минимизации системы булевых функций при создании аппаратуры на основе программируемых пользователем логических ИС.
Gespeichert in:
| Datum: | 1999 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
1999
|
| Schriftenreihe: | Технология и конструирование в электронной аппаратуре |
| Schlagworte: | |
| Online Zugang: | http://dspace.nbuv.gov.ua/handle/123456789/122686 |
| 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: | Эффективный алгоритм синтеза многовыходных комбинационных автоматов / А.В. Голов, С.Ю. Лузин // Технология и конструирование в электронной аппаратуре. — 1999. — № 1. — С. 39-40. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-122686 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1226862017-07-18T03:03:05Z Эффективный алгоритм синтеза многовыходных комбинационных автоматов Голов, А.В. Лузин, С.Ю. Электронная аппаратура: исследования, разработки Предложен метод решения задачи минимизации системы булевых функций при создании аппаратуры на основе программируемых пользователем логических ИС. The method for solving a problem of minimization of Boolian functions system in creation of equipment on base logic IC to be programed by user has been proposed. 1999 Article Эффективный алгоритм синтеза многовыходных комбинационных автоматов / А.В. Голов, С.Ю. Лузин // Технология и конструирование в электронной аппаратуре. — 1999. — № 1. — С. 39-40. — Бібліогр.: 4 назв. — рос. 2225-5818 http://dspace.nbuv.gov.ua/handle/123456789/122686 ru Технология и конструирование в электронной аппаратуре Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України |
| 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 |
1999 |
| topic_facet |
Электронная аппаратура: исследования, разработки |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/122686 |
| citation_txt |
Эффективный алгоритм синтеза многовыходных комбинационных автоматов / А.В. Голов, С.Ю. Лузин // Технология и конструирование в электронной аппаратуре. — 1999. — № 1. — С. 39-40. — Бібліогр.: 4 назв. — рос. |
| series |
Технология и конструирование в электронной аппаратуре |
| work_keys_str_mv |
AT golovav éffektivnyjalgoritmsintezamnogovyhodnyhkombinacionnyhavtomatov AT luzinsû éffektivnyjalgoritmsintezamnogovyhodnyhkombinacionnyhavtomatov |
| first_indexed |
2025-07-08T22:11:16Z |
| last_indexed |
2025-07-08T22:11:16Z |
| _version_ |
1837119087492202496 |
| fulltext |
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 1999, ¹ 1
ÝËÅÊÒÐÎÍÍÀß ÀÏÏÀÐÀÒÓÐÀ: ÈÑÑËÅÄÎÂÀÍÈß, ÐÀÇÐÀÁÎÒÊÈ
39
À. Â. ÃÎËÎÂ, ê. ò. í. Ñ. Þ. ËÓÇÈÍ
Ðîññèÿ, Ñ.-Ïåòåðáóðã, ÃÏ «Äàëüíÿÿ ñâÿçü»,
Ãîñ. óí-ò òåëåêîììóíèêàöèé èì. Ì. À. Áîí÷-Áðóåâè÷à
Äàòà ïîñòóïëåíèÿ â ðåäàêöèþ
14.09 1998 ã.
ÝÔÔÅÊÒÈÂÍÛÉ ÀËÃÎÐÈÒÌ ÑÈÍÒÅÇÀ
ÌÍÎÃÎÂÛÕÎÄÍÛÕ ÊÎÌÁÈÍÀÖÈÎÍÍÛÕ
ÀÂÒÎÌÀÒÎÂ
Îïïîíåíò ä. ò. í. Ë. Ñ. ËÓÒ×ÅÍÊÎÂ
Ïðåäëîæåí ìåòîä ðåøåíèÿ çàäà÷è ìè-
íèìèçàöèè ñèñòåìû áóëåâûõ ôóíêöèé
ïðè ñîçäàíèè àïïàðàòóðû íà îñíîâå
ïðîãðàììèðóåìûõ ïîëüçîâàòåëåì ëîãè-
÷åñêèõ ÈÑ.
The method for solving a problem of minimization
of Boolian functions system in creation of
equipment on base logic IC to be programed by
user has been proposed.
Ïðè ðàçðàáîòêå öèôðîâîé àïïàðàòóðû ðàçëè÷íî-
ãî íàçíà÷åíèÿ âñå áîëüøåå ïðèìåíåíèå íàõîäÿò ïðî-
ãðàììèðóåìûå ïîëüçîâàòåëåì ëîãè÷åñêèå èíòåãðàëü-
íûå ìèêðîñõåìû (ÏËÈÑ).
Áûñòðî ðàñòóùàÿ íîìåíêëàòóðà ýòèõ óñòðîéñòâ
íàðÿäó ñ óâåëè÷åíèåì èõ ôóíêöèîíàëüíûõ âîçìîæ-
íîñòåé ïðèâîäèò, ñ îäíîé ñòîðîíû, ê ïîñòîÿííîìó
ðàñøèðåíèþ ñôåðû èñïîëüçîâàíèÿ ïðîãðàììèðóå-
ìûõ ìèêðîñõåì, à ñ äðóãîé � ê ñóùåñòâåííîìó
óñëîæíåíèþ çàäà÷ ïðîåêòèðîâàíèÿ àïïàðàòóðû íà
èõ îñíîâå.
Ïðè ñîçäàíèè àïïàðàòóðû íà îñíîâå ÏËÈÑ êà-
÷åñòâî ðàçðàáîòêè âî ìíîãîì îïðåäåëÿåòñÿ ýôôåê-
òèâíîñòüþ àâòîìàòèçèðîâàííûõ ñðåäñòâ ëîãè÷åñêî-
ãî ñèíòåçà, ìîùíîñòüþ ìàòåìàòè÷åñêîãî è ïðîãðàì-
ìíîãî îáåñïå÷åíèÿ.
Áûñòðûé ðîñò ðàçìåðíîñòè ðåøàåìûõ íà ñîâðå-
ìåííîì ýòàïå çàäà÷ ïðèâîäèò ê íåîáõîäèìîñòè ïîñ-
òîÿííîãî ðàçâèòèÿ òåîðèè è ïðàêòèêè àâòîìàòèçè-
ðîâàííîãî ïðîåêòèðîâàíèÿ. Îäíèì èç íàèáîëåå òðó-
äîåìêèõ ýòàïîâ ïðîåêòèðîâàíèÿ öèôðîâîé àïïàðà-
òóðû ÿâëÿåòñÿ ýòàï ôóíêöèîíàëüíî-ëîãè÷åñêîãî
ïðîåêòèðîâàíèÿ, òåîðåòè÷åñêîé îñíîâîé êîòîðîãî
ÿâëÿåòñÿ çàäà÷à ìèíèìèçàöèè áóëåâûõ ôóíêöèé.
Èçâåñòíûå ïîäõîäû ê ðåøåíèþ äàííîé ïðîáëåìû
îòëè÷àþòñÿ âûñîêîé êîìáèíàòîðíîé ñëîæíîñòüþ.
 äàííîé ðàáîòå ïðèâîäèòñÿ äåêîìïîçèöèîííûé
ìåòîä ìèíèìèçàöèè ñèñòåìû áóëåâûõ ôóíêöèé, êîì-
áèíàòîðíàÿ ñëîæíîñòü êîòîðîãî íå ïðåâîñõîäèò
ñëîæíîñòè ìèíèìèçàöèè îäíîé ôóíêöèè.
Îáîçíà÷èì Ii
0, Ii
1, Ii
* ïîäìíîæåñòâà ýëåìåíòîâ
n-ìåðíîãî áóëåâîãî ïðîñòðàíñòâà I(n)={a0, ..., a2n�1},
íà êîòîðûõ áóëåâà ôóíêöèÿ f(X)∈F, X={x0, ..., xn�1}
èìååò ñîîòâåòñòâåííî íóëåâîå, åäèíè÷íîå è íåîï-
ðåäåëåííîå çíà÷åíèå. Ñèñòåìû áóëåâûõ ôóíêöèé
F(X)={f0, ..., fm�1}, ñðåäè êîòîðûõ ìîãóò áûòü
÷àñòè÷íûå, áóäåì çàäàâàòü â âèäå ìíîæåñòâà
Ψ0={(αj, βj)} (j=1, ..., p0) ïàð â îáùåì ñëó÷àå òðî-
è÷íûõ âåêòîðîâ. Ïàðó (αj, βj) áóäåì íàçûâàòü îáîá-
ùåííûì (íà ìíîæåñòâå ôóíêöèé) èíòåðâàëîì. ×àñòü
αj îáîáùåííîãî èíòåðâàëà íàçîâåì âõîäíîé, à ÷àñòü
βj � âûõîäíîé. Âõîäíàÿ ÷àñòü αj={αj
n�1,..., αj
0}
îáîáùåííîãî èíòåðâàëà ÿâëÿåòñÿ èíòåðâàëîì â ïðî-
ñòðàíñòâå áóëåâûõ ïåðåìåííûõ X={x0, ..., xn�1}. Âû-
õîäíàÿ ÷àñòü βj={βj
m�1,..., βj
0} îáîáùåííîãî èíòåðâà-
ëà ÿâëÿåòñÿ òðîè÷íûì âåêòîðîì çíà÷åíèé ôóíê-
öèé f0, ..., fi, ..., fm�1 íà èíòåðâàëå αj. Ïðè ýòîì βj
i=1,
åñëè Iαj
⊆ Ii
1; βj
i=0, åñëè Iαj
⊆Ii
0; βj
i=*, åñëè Iαj
⊆Ii
*.
Çàäà÷à ñîñòîèò â ïðèâåäåíèè èñõîäíîãî ìíîæåñ-
òâà îáîáùåííûõ èíòåðâàëîâ Ψ0, ïðåäñòàâëÿþùèõ
ñèñòåìó áóëåâûõ ôóíêöèé F, ê êðàò÷àéøåìó ìíî-
æåñòâó îáîáùåííûõ èíòåðâàëîâ.
Îäèí èç ñïîñîáîâ ìèíèìèçàöèè ìíîãîâûõîäíî-
ãî êîìáèíàöèîííîãî àâòîìàòà çàêëþ÷àåòñÿ â ñëåäó-
þùåì. Ïîëó÷àþò ïðîñòûå èìïëèêàíòû êàê äëÿ êàæ-
äîé ôóíêöèè â îòäåëüíîñòè, òàê è äëÿ âñåõ íåïóñ-
òûõ ïåðåñå÷åíèé ìíîæåñòâ èìïëèêàíò êàæäîé èç
ôóíêöèé (èõ ìîæåò áûòü 2m�1, ãäå m � ÷èñëî
ôóíêöèé). Â òàáëèöó Êâàéíà ïîìèìî ïðîñòûõ èì-
ïëèêàíò êàæäîé èç ôóíêöèé âêëþ÷àþòñÿ ìíîãîâû-
õîäíûå èìïëèêàíòû.
Äðóãîé ñïîñîá çàêëþ÷àåòñÿ â ñâåäåíèè çàäà÷è
ìèíèìèçàöèè ìíîãîâûõîäíîãî àâòîìàòà ê ìèíèìè-
çàöèè îäíîâûõîäíîãî ñ ïîìîùüþ êîäèðîâàíèÿ âû-
õîäîâ ïåðâîãî [1, c. 323].
 îáîèõ ñëó÷àÿõ ïî ñðàâíåíèþ ñ ìèíèìèçàöèåé
îäíîé ôóíêöèè êîìáèíàòîðíàÿ ñëîæíîñòü çàäà÷è
âîçðàñòàåò ïðèìåðíî â 2m ðàç.
Îáîçíà÷èì ÷åðåç Ij îáúåäèíåíèå èíòåðâàëîâ αi,
äëÿ êîòîðûõ βi=j:
(1)
Ðàçîáüåì ìíîæåñòâî îáîáùåííûõ èíòåðâàëîâ Ψ0
íà êëàññû �
(2)
è ïðîâåäåì ìèíèìèçàöèþ äëÿ êàæäîãî êëàññà â îò-
äåëüíîñòè.
Òàêèì îáðàçîì, èñõîäíàÿ çàäà÷à ìèíèìèçàöèè
ñèñòåìû ôóíêöèé ðàçáèâàåòñÿ íà 2m ïîäçàäà÷ ìè-
.U
j
i
i
IIj
=β
α=
U
12
0
0
−
=
=Ψ
m
j
jI
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 1999, ¹ 1
40
ÝËÅÊÒÐÎÍÍÀß ÀÏÏÀÐÀÒÓÐÀ: ÈÑÑËÅÄÎÂÀÍÈß, ÐÀÇÐÀÁÎÒÊÈ
 äàííîì ïðèìåðå ñîâîêóïíîñòü òåðìîâ êàæäîãî èç
êëàññîâ ïðåäñòàâëÿåò ñîáîé èíòåðâàë. Óìåíüøèòü ÷èñ-
ëî ïîêðûâàþùèõ èíòåðâàëîâ ïóòåì ðàñøèðåíèÿ òåðìîâ
íåêîòîðîãî êëàññà çà ñ÷åò òåðìîâ êëàññîâ ñ áî′ëüøèì
èíäåêñîì íåâîçìîæíî. Ïîýòîìó åäèíñòâåííàÿ âîçìîæ-
íîñòü �ïîïûòàòüñÿ «ðàçîáðàòü» íåêîòîðûé êëàññ, ò. å.
èñïîëüçîâàòü òåðìû íåêîòîðîãî êëàññà ñ áî′ëüøèì èí-
äåêñîì ïðè ðàñøèðåíèè èíòåðâàëîâ êëàññîâ ñ ìåíüøè-
ìè èíäåêñàìè. Åñëè ïðè ýòîì îáúåäèíåíèå êîäîâ êëàñ-
ñîâ ìåíüøèõ èíäåêñîâ äàåò êîä êëàññà ñ áî′ëüøèì èí-
äåêñîì, òî òåðìû ýòîãî êëàññà áóäóò ïîêðûòû.
Ðàñøèðåíèå èíòåðâàëà 11 ( êîä êëàññà 010) � 2, 3,
10, 11 è èíòåðâàëà 0, 8 (êîä êëàññà 101) � 0, 2, 8, 10
îñóùåñòâëÿåòñÿ ñ èñïîëüçîâàíèåì òåðìîâ 2 è 10 êëàññà ñ
êîäîì 111. Ïîñêîëüêó îáúåäèíåíèå êîäîâ 010 è 101 äàåò
êîä 111, òî òåðìû êëàññà 111 îêàçûâàþòñÿ ïîãëîùåííûìè.
Òàêèì îáðàçîì, êëàññû ðàññìàòðèâàþòñÿ â ïî-
ðÿäêå âîçðàñòàíèÿ åäèíèö â êîäå êëàññà è îñóùåñ-
òâëÿþòñÿ âîçìîæíûå ðàñøèðåíèÿ èíòåðâàëîâ êëàñ-
ñà çà ñ÷åò èíòåðâàëîâ èç êëàññîâ ñ áî′ëüøèì ÷èñëîì
åäèíèö. Ïðè ýòîì ïîìå÷àþòñÿ èñïîëüçóåìûå òåðìû.
Òîãäà ìèíèìèçàöèþ ñèñòåìû áóëåâûõ ìîæíî îñó-
ùåñòâèòü çà âðåìÿ, íå ïðåâîñõîäÿùåå âðåìÿ ìèíè-
ìèçàöèè îäíîé ôóíêöèè.
ÈÑÏÎËÜÇÎÂÀÍÍÛÅ ÈÑÒÎ×ÍÈÊÈ
1. Ãàâðèëîâ Ì. À., Äåâÿòêîâ Â. Â., Ïóïûðåâ Å. È. Ëî-
ãè÷åñêîå ïðîåêòèðîâàíèå äèñêðåòíûõ àâòîìàòîâ.� Ì. :
Íàóêà, 1977.
2. Ëóçèí Ñ. Þ., Ñîðîêèí Ñ. Â., Âàõàáîâ Ì. Ò.,
Òêà÷åâ Ä. Á. ÏÏÏ ñèíòåçà êîìáèíàöèîííûõ àâòîìàòîâ
// Âñåñîþç. íàó÷.-òåõí. êîíô. «Ñîâåðøåíñòâîâàíèå òåõ-
íè÷åñêèõ ñðåäñòâ ñâÿçè äëÿ ðåøåíèÿ ïðîáëåì èíôîðìà-
òèçàöèè îáùåñòâà â íîâûõ óñëîâèÿõ õîçÿéñòâîâàíèÿ».
Òåç. äîêë.�Ë. : 1991.� C. 90�91.
3. Ëóçèí Ñ. Þ. Ìèíèìèçàöèÿ áóëåâûõ ôóíêöèé íà
îñíîâå ñèíòåçà ðàñïðåäåëåíèÿ òåðìîâ ïî èíäåêñàì // Ñá.
íàó÷. òðóäîâ ó÷åáíûõ èíñòèòóòîâ ñâÿçè.� 1996.� Âûï.
162.� C. 27�30.
4. Ëóçèí Ñ. Þ., Ïîëóáàñîâ Î. Á. Ëîãè÷åñêèé ñèíòåç
ñ èñïîëüçîâàíèåì ïðîãðàììû PLAST // Ìåæäóíàð. êîíô.
«Ñîâðåìåííûå òåõíîëîãèè îáó÷åíèÿ». Òåç. äîêë.�
Ñ.-Ïá. : 1998.� C. 128.
íèìèçàöèè îäíîé ôóíêöèè [2�4]. Â ðåçóëüòàòå áó-
äåò ïîëó÷åíî íåêîòîðîå ðåøåíèå, â îáùåì ñëó÷àå
íå îïòèìàëüíîå. Îíî ìîæåò áûòü óëó÷øåíî, åñëè
ñóùåñòâóåò âîçìîæíîñòü èçìåíèòü îöåíêó äëÿ êà-
êèõ-ëèáî êëàññîâ.
Âåêòîðû βi, βj � âûõîäíûå ÷àñòè îáîáùåííûõ
èíòåðâàëîâ � áóäåì ñðàâíèâàòü ïîðàçðÿäíî, ÷òîáû
óñòàíîâèòü ìåæäó íèìè ñëåäóþùåå îòíîøåíèå:
åñëè òî βi ⊂ βj .
Äëÿ óìåíüøåíèÿ îöåíêè íåêîòîðîãî êëàññà ñó-
ùåñòâóåò äâå âîçìîæíîñòè.
1. Ðàñøèðåíèå èíòåðâàëîâ íåêîòîðîãî êëàññà Ij
çà ñ÷åò èñïîëüçîâàíèÿ òåðìîâ èç êëàññîâ ñ áî′ëüøèì
èíäåêñîì, äëÿ êîòîðûõ âûïîëíÿåòñÿ óñëîâèå βi ⊂ βk.
Äëÿ ýòîãî îïðåäåëÿåòñÿ ìèíèìàëüíûé èíòåðâàë,
âêëþ÷àþùèé âñå òåðìû êëàññà Ij, çàòåì äëÿ êàæäîãî
èç òåðìîâ, ïðèíàäëåæàùèõ äîïîëíåíèþ Ij äî íàéäåí-
íîãî èíòåðâàëà, îïðåäåëÿåòñÿ êëàññ, â êîòîðûé îí
âõîäèò. Ïðè âûïîëíåíèè óñëîâèÿ βj ⊂ βk îñóùåñ-
òâëÿåòñÿ ðàñøèðåíèå èíòåðâàëîâ êëàññà Ij. Î÷å-
âèäíî, ÷òî ïðè ýòîì îöåíêè äëÿ «ñòàðøèõ» êëàññîâ
íå èçìåíÿþòñÿ.
2. Ðàçáîðêà «ñòàðøèõ» êëàññîâ â ñëó÷àå ìíîãî-
êðàòíîãî èñïîëüçîâàíèÿ ïðèíàäëåæàùèõ èì òåð-
ìîâ: åñëè ñ ïîìîùüþ íåêîòîðîãî èíòåðâàëà α êëàññà
βp ìîæíî ðàñøèðèòü èíòåðâàëû k êëàññîâ βj ⊂ βk è
ïðè ýòîì òî α ìîæíî óäàëèòü èç êëàññà βp.
Ðàññìîòðèì ïðèìåð èç [1, ñ. 318]. Çàäàíà ñèñòåìà
ôóíêöèé òðåõâûõîäíîãî êîìáèíàöèîííîãî àâòîìàòà:
Äëÿ ñîêðàùåíèÿ çàïèñè âìåñòî áóêâåííûõ âûðàæå-
íèé áóäåì èñïîëüçîâàòü èõ äåñÿòè÷íûå ýòèêåòêè. Íà-
ïðèìåð, òåðìó x
_
1x2x
_
3x4 ñîîòâåòñòâóåò äâîè÷íàÿ ýòèêåòêà
1010 (ïîçèöèÿ ðàçðÿäà ñîîòâåòñòâóåò íîìåðó ïåðåìåííîé)
èëè äåñÿòè÷íàÿ ýòèêåòêà 10.
F1 = ∑ 0, 2, 4, 8, 10, 12, �
F1
= ∑ 1, 3, 5, 6, 7, 9, 11, 13, 14, 15;
F2= ∑ 2, 3, 4, 10, 11, 12,
�
F2= ∑ 0, 1, 5, 6, 7, 8, 9, 13, 14, 15;
F3 = ∑ 0, 2, 3, 6, 7, 8, 10, 14, 15,
�
F3= ∑ 1, 4, 5, 9, 11, 12, 13;
F1 ∪ F2 ∪ F3 =∑ 0, 2, 3, 4, 6, 7, 8, 10, 11, 12, 14, 15;
�
F1∪
�
F2∪
�
F3=1, 5, 9, 13.
 òàáëèöå òåðìû ðàçáèòû íà êëàññû ñ ðàçëè÷íûìè
êîäàìè ôóíêöèîíàëüíîé ïðèíàäëåæíîñòè.
110
3
111
2, 10
011
4, 12
101
0, 8
000
1, 5, 9, 13
001
010
11
100
6, 7, 14, 15
∀ ∈ − ≤k n
i
k
j
k02 1, ,β β
,
1
p
k
i
i β=β
=
U
;
,)(
3211
32311
xxxF
xxxxF
∨=
∨=
);(
,)(
3122
32321322
xxxF
xxxxxxxF
∨=
∨∨=
.)(
,)(
43141323
4332313
xxxxxxxF
xxxxxxF
∨∨=
∨∨=
|