Выбор конфигурации соединения компонентов электронных схем до этапа размещения
Предложен метод построения деревьев соединений компонентов в многозвенных цепях с целью повышения качества автоматического размещения в САПР печатных плат и БИС....
Збережено в:
| Опубліковано в: : | Технология и конструирование в электронной аппаратуре |
|---|---|
| Дата: | 2001 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України
2001
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/70866 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Выбор конфигурации соединения компонентов электронных схем до этапа размещения / С.В. Зудин, С.Ю. Лузин, О.Б. Полубасов // Технология и конструирование в электронной аппаратуре. — 2001. — № 4-5. — С. 3-6. — Бібліогр.: 2 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859741955498442752 |
|---|---|
| author | Зудин, С.В. Лузин, С.Ю. Полубасов О.Б. |
| author_facet | Зудин, С.В. Лузин, С.Ю. Полубасов О.Б. |
| citation_txt | Выбор конфигурации соединения компонентов электронных схем до этапа размещения / С.В. Зудин, С.Ю. Лузин, О.Б. Полубасов // Технология и конструирование в электронной аппаратуре. — 2001. — № 4-5. — С. 3-6. — Бібліогр.: 2 назв. — рос. |
| collection | DSpace DC |
| container_title | Технология и конструирование в электронной аппаратуре |
| description | Предложен метод построения деревьев соединений компонентов в многозвенных цепях с целью повышения качества автоматического размещения в САПР печатных плат и БИС.
|
| first_indexed | 2025-12-01T19:13:25Z |
| format | Article |
| fulltext |
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 4�5 3
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
ÂÛÁÎÐ ÊÎÍÔÈÃÓÐÀÖÈÈ ÑÎÅÄÈÍÅÍÈß
ÊÎÌÏÎÍÅÍÒÎÂ ÝËÅÊÒÐÎÍÍÛÕ ÑÕÅÌ
ÄÎ ÝÒÀÏÀ ÐÀÇÌÅÙÅÍÈß
Ñ. Â. ÇÓÄÈÍ, ê. ò. í. Ñ. Þ. ËÓÇÈÍ, Î. Á. ÏÎËÓÁÀÑÎÂ
Ðîññèÿ, ã. Ñ.-Ïåòåðáóðã, Ãîñ. óí-ò òåëåêîììóíèêàöèé
èì. Ì. À. Áîí÷-Áðóåâè÷à, ÍÈÈ "Çâåçäà"
E-mail:luzin@spb.cityline.ru
Äàòà ïîñòóïëåíèÿ â ðåäàêöèþ
05.06 2001 ã.
Îïïîíåíò ê. ò. í. Â. Â. ÑÈÁÈÐßÊÎÂ
Ïðåäëîæåí ìåòîä ïîñòðîåíèÿ äåðåâü-
åâ ñîåäèíåíèé êîìïîíåíòîâ â ìíîãîçâåí-
íûõ öåïÿõ ñ öåëüþ ïîâûøåíèÿ êà÷åñòâà
àâòîìàòè÷åñêîãî ðàçìåùåíèÿ â ÑÀÏÐ
ïå÷àòíûõ ïëàò è ÁÈÑ.
Îäíîé èç îñíîâíûõ ïðè÷èí ñðàâíèòåëüíî íåâû-
ñîêîé ýôôåêòèâíîñòè èçâåñòíûõ ñèñòåì êîíñòðóê-
òîðñêîãî ñèíòåçà ðàäèîýëåêòðîííûõ ñðåäñòâ ÿâëÿåò-
ñÿ íåñîãëàñîâàííîñòü êðèòåðèåâ íà ýòàïàõ ðàçìåùå-
íèÿ ýëåìåíòîâ è òðàññèðîâêè èõ ñîåäèíåíèé. Ýòà
íåñîãëàñîâàííîñòü ñêàçûâàåòñÿ îñîáåííî îùóòèìî,
åñëè â ïðîåêòèðóåìîé ìîíòàæíîé ñõåìå åñòü ìíîãî-
çâåííûå öåïè (ñîåäèíÿþùèå áîëåå äâóõ ýëåìåíòîâ).
 òàêèõ ñëó÷àÿõ êîëè÷åñòâî ñâÿçåé ìåæäó ýëåìåí-
òàìè, ó÷èòûâàåìîå â òðàäèöèîííûõ àëãîðèòìàõ ðàç-
ìåùåíèÿ, îáû÷íî çíà÷èòåëüíî ïðåâûøàåò ÷èñëî ñî-
åäèíåíèé, äåéñòâèòåëüíî òðåáóþùèõ ó÷åòà äëÿ îáåñ-
ïå÷åíèÿ ìàêñèìàëüíî ïîëíîé ðàçâîäêè òðàññ.
Îáû÷íî çàäà÷à ðàçìåùåíèÿ ïðåäøåñòâóåò çàäà-
÷å òðàññèðîâêè, è íà ýòîì ýòàïå ïîðÿäîê ñîåäèíåíèÿ
ýëåìåíòîâ â öåïÿõ åùå íå îïðåäåëåí. Ïîýòîìó íà
ïðàêòèêå, êàê ïðàâèëî, ñõåìó ìîäåëèðóþò ìóëüòè-
ãðàôîì, ãäå îòäåëüíûå ýëåêòðè÷åñêèå öåïè ïðåäñòàâ-
ëÿþòñÿ ïîëíûìè ïîäãðàôàìè (âñå ýêâèïîòåíöèàëü-
íûå êîíòàêòû ïîïàðíî ñâÿçàíû), à êà÷åñòâî ðàçìå-
ùåíèÿ îöåíèâàåòñÿ ëèáî ïî ñóììàðíîé äëèíå ðåáåð
òàêèõ ïîäãðàôîâ, ëèáî ïî ñóììå ïîëóïåðèìåòðîâ
ïðÿìîóãîëüíèêîâ, îõâàòûâàþùèõ êîíòàêòû, ñâÿçàí-
íûå öåïüþ. Òàêîé ìóëüòèãðàô äàåò â îáùåì ñëó÷àå
ñóùåñòâåííî çàâûøåííóþ îöåíêó ðåàëüíîé äëèíû
ìåæñîåäèíåíèé, êîòîðàÿ â äàëüíåéøåì âõîäèò è â
îöåíêó êà÷åñòâà ðàçìåùåíèÿ ýëåìåíòîâ.
Ó÷åò ñâÿçåé, êîòîðûå íà ñàìîì äåëå òðàññèðî-
âàòü áóäåò íå íóæíî, è ïîïûòêà íà ýòàïå ðàçìåùå-
íèÿ ñîçäàòü óñëîâèÿ äëÿ èõ îïòèìàëüíîé ïðîêëàäêè
íåèçáåæíî óõóäøàþò óñëîâèÿ äëÿ ïðîêëàäêè ðåàëü-
íûõ ñâÿçåé.
Íåñîãëàñîâàííîñòü ïðèíÿòûõ ôîðìàëèçîâàííûõ
ðåøåíèé çàäà÷è ðàçìåùåíèÿ ñ óñëîâèåì ïîëíîé ðàç-
âîäêè òðàññ ìîæåò áûòü óñòðàíåíà íà ñòàäèè ïî-
ñòðîåíèÿ òåîðåòèêî-ãðàôîâîé ìîäåëè ïðèíöèïèàëü-
íîé ýëåêòðè÷åñêîé ñõåìû ïðîåêòèðóåìîãî óçëà, èñ-
ïîëüçóåìîé ïðè ðàçìåùåíèè. Äëÿ ýòîãî íåîáõîäèìî
ðàçðàáîòàòü òàêèå ìåòîäû óñòðàíåíèÿ èçáûòî÷íûõ
ñâÿçåé, êîòîðûå óëó÷øàþò ïîëåçíûå äëÿ òðàññèðîâ-
êè êðèòåðèè (ìèíèìóì ñðåäíåêâàäðàòè÷íîãî ðàçáðîñà
ñòåïåíåé âåðøèí, ìèíèìóì ÷èñëà ðåáåð ãðàôà, ìèíè-
ìóì òîëùèíû ñêåëåòíîãî ãðàôà, ìîäåëèðóþùåãî ñõå-
ìó, è ò. ä.).
 ðàáîòå [1, ñ. 95] áûëà îòìå÷åíà âûøåîïèñàí-
íàÿ íåñîãëàñîâàííîñòü è ïðåäïðèíÿòà ïîïûòêà åå
ïðåîäîëåíèÿ. Ïðåäëàãàåòñÿ èç ìíîæåñòâà êîíôèãó-
ðàöèé äåðåâüåâ âûáðàòü òå, êîòîðûå â îáúåäèíåíèè
äàþò ãðàô ñ ìèíèìàëüíûì ÷èñëîì ðåáåð. Îäíàêî
îïèñàííûé â [1] ìåòîä ñëèøêîì òðóäîåìîê.
 äàííîé ðàáîòå ïðåäëîæåí àëüòåðíàòèâíûé ïîä-
õîä, ðåøàþùèé òó æå çàäà÷ó, íî îáëàäàþùèé ñóùå-
ñòâåííî ìåíüøåé êîìáèíàòîðíîé ñëîæíîñòüþ è ïî-
òîìó ïðèãîäíûé äëÿ ïðàêòè÷åñêîãî èñïîëüçîâàíèÿ.
Ïîñòàíîâêà çàäà÷è [1]
Èç ìíîæåñòâà êîíôèãóðàöèé äåðåâüåâ âûáðàòü
òå, êîòîðûå â îáúåäèíåíèè äàþò ãðàô ñ ìèíè-
ìàëüíûì ÷èñëîì ðåáåð.
Ïóñòü Õ={x1, x2, ..., xn} � ìíîæåñòâî âåðøèí ãðà-
ôà ñõåìû, G={G1, G2, ..., Gl} � ìíîæåñòâî ïîäìíî-
æåñòâ Õ, ñîîòâåòñòâóþùèõ êàæäîé öåïè ïðèíöèïè-
àëüíîé ýëåêòðè÷åñêîé ñõåìû.
Ðàññìîòðèì n-âåðøèííûé ãðàô, â êîòîðîì ñìåæíà
ëþáàÿ ïàðà âåðøèí, èíöèäåíòíûõ íåêîòîðîé öåïè Gi.
Ìíîæåñòâî âåðøèí ãðàôà åñòü ìíîæåñòâî Õ, à
ìíîæåñòâî ðeáåð u={u1, u2, ..., um}. Îïèñàííûé ãðàô
ñîäåðæèò âñå âàðèàíòû äåðåâüåâ äëÿ ëþáîé èç öå-
ïåé.
Îòîæäåñòâèì ñèìâîëû ui ñ ïñåâäîáóëåâûìè ïåðå-
ìåííûìè:
=
.0
;,1
ñëó÷àåïðîòèâíîìâ
ñõåìûãðàôó òïðèíàäëåæèðåáðîóþùååñîîòâåòñòâåñëè
iu
Ïñåâäîáóëåâûìè ïåðåìåííûå íàçâàíû ïîòîìó, ÷òî íà
ñàìîì äåëå ui=0 èñïîëüçîâàòüñÿ íå áóäåò. Ñëåäîâàòåëü-
íî, ïðè îñóùåñòâëåíèè ïðåîáðàçîâàíèé ôóíêöèé èñïîëü-
çóþòñÿ òîëüêî äâà ïðàâèëà: a·a=a è a∨a·b=a.
Î÷åâèäíî, ÷òî íåîáõîäèìûì è äîñòàòî÷íûì óñ-
ëîâèåì ðåàëèçàöèè íåêîòîðîé öåïè i ÿâëÿåòñÿ ñóùå-
ñòâîâàíèå â ãðàôå ñõåìû ïîäìíîæåñòâà ðåáåð, îáðà-
çóþùèõ äåðåâî íà ìíîæåñòâå âåðøèí Gi.
Îïðåäåëèì áóëåâó ôóíêöèþ ñâÿçíîñòè Fi{u1, u2,
..., um} êàê ôóíêöèþ, ïðèíèìàþùóþ çíà÷åíèå 1 òîã-
äà è òîëüêî òîãäà, êîãäà ãðàô Hi (ïîäãðàô ãðàôà
Kn, ïîðîæäåííûé ìíîæåñòâîì âåðøèí Gi) ÿâëÿåòñÿ
ñâÿçíûì:
)(21
)(
1
... ijrjj
ik
j
i uuuF ⋅⋅⋅=∨
=
. (1)
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 4�5
4
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
×ëåíû âûðàæåíèÿ (1), îáúåäèíåííûå äèçúþíê-
öèåé, ïðåäñòàâëÿþò ñîáîé êîíúþíêöèþ ïåðåìåííûõ,
ñîîòâåòñòâóþùèõ ðåáðàì, äîñòàâëÿþùèì ñâÿçíîñòü
Hi. Ïîñêîëüêó èç âñÿêîãî ñâÿçíîãî ãðàôà, ñîäåðæà-
ùåãî öèêëû, ïîñëå óäàëåíèÿ íåêîòîðîãî íåïóñòîãî
ìíîæåñòâà ðåáåð ìîæíî ïîëó÷èòü äåðåâî, òî òåðìû
â âûðàæåíèè (1), ñîîòâåòñòâóþùèå ãðàôàì Hi ñ
öèêëàìè, ïîãëîùàþòñÿ òåðìàìè, ñîîòâåòñòâóþùèìè äå-
ðåâüÿì. Òàêèì îáðàçîì, ìîæíî ñ÷èòàòü, ÷òî Fi ñîîò-
âåòñòâóåò äèçúþíêöèè âñåâîçìîæíûõ äåðåâüåâ íà Gi.
Òàê êàê óñëîâèåì ðåàëèçàöèè èñõîäíîé ñõåìû
ÿâëÿåòñÿ ñâÿçíîñòü âñåõ ãðàôîâ Hi, òî åãî ìîæíî
çàïèñàòü â âèäå
.1&
1
=
=
i
l
i
F (2)
Ïîñëåäîâàòåëüíî âûïîëíÿÿ â âûðàæåíèè (2)
îïåðàöèè êîíúþíêöèè è ïîëüçóÿñü ïðàâèëîì ïîãëî-
ùåíèÿ, ïðèâåäåì ëåâóþ ÷àñòü ê âèäó
.... )(21
1
jjrij
p
j
uuu∨
=
(3)
Âûáèðàÿ â âûðàæåíèè (3) òåðì ñ ìèíèìàëüíûì
÷èñëîì áóêâ, îïðåäåëèì ñîâîêóïíîñòü ðåáåð èñêî-
ìîãî ãðàôà ñõåìû.
Ê ñîæàëåíèþ, òàêîé ñïîñîá ðåøåíèÿ ïðàêòè÷åñêè
íåðåàëèçóåì äëÿ ñõåì, ñîäåðæàùèõ áîëåå 20 êîìïî-
íåíòîâ.
Ïðåäëàãàåìûé ìåòîä
Ïîñêîëüêó êîíå÷íîé öåëüþ ÿâëÿåòñÿ ïîëó÷åíèå
òåðìà ìèíèìàëüíîé äëèíû, òî, ïî-âèäèìîìó, íåò íåîá-
õîäèìîñòè ïîëó÷àòü âñå òåðìû, âûïîëíÿÿ îãðîìíîå
êîëè÷åñòâî îïåðàöèé.  ðÿäå ñëó÷àåâ íà îñíîâå àíà-
ëèçà èñõîäíûõ äàííûõ ìîæíî óñòàíîâèòü ýêâèâà-
ëåíòíîñòü ÷àñòè÷íûõ ðåøåíèé ñ òî÷êè çðåíèÿ âûá-
ðàííîãî êðèòåðèÿ è âûáðàòü îäèí èç âàðèàíòîâ. Â
äðóãèõ ñëó÷àÿõ òîò æå àíàëèç èñõîäíûõ äàííûõ
ïîçâîëÿåò îñóùåñòâèòü äåêîìïîçèöèþ öåïåé. È â
òåõ, è â äðóãèõ ñëó÷àÿõ ñóùåñòâåííî ñíèæàåòñÿ ðàç-
ìåðíîñòü çàäà÷è.
Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî
âíóòðåííèå ñîåäèíåíèÿ êîìïîíåíòà (ôðàãìåíòû öå-
ïåé, ñîåäèíÿþùèå êîíòàêòû îäíîãî êîìïîíåíòà) îò-
ñóòñòâóþò.
1. Ïóñòü íåêîòîðàÿ öåïü Gk ñîåäèíÿåò òîëüêî
äâà ýëåìåíòà � xi è xj, òîãäà ðåáðî, ñîåäèíÿþùåå
ýëåìåíòû xi è xj, îáÿçàòåëüíî âîéäåò â ðåçóëüòèðóþ-
ùèé ãðàô.
2. Ïóñòü äëÿ ïàðû öåïåé i è j (1≤i≠j≤n)
| Gi ∩Gj | ≤1,
òîãäà â ãðàôå G'=Gi ∪Gj âñå ðåøåíèÿ, ñîäåðæàùèå
ïî îäíîìó äåðåâó äëÿ êàæäîé èç öåïåé, ýêâèâàëåíò-
íû ïî ÷èñëó ðåáåð.  ïîäîáíûõ ñëó÷àÿõ íåò íåîá-
õîäèìîñòè íè ãåíåðèðîâàòü âñå äåðåâüÿ äëÿ êàæäîé
èç öåïåé, íè ïîïàðíî ïåðåìíîæàòü òåðìû, ñîîòâåò-
ñòâóþùèå äåðåâüÿì. Äîñòàòî÷íî ïðîèçâîëüíî âûá-
ðàòü ïî îäíîìó äåðåâó äëÿ êàæäîé èç öåïåé.
3. Ïóñòü äëÿ ïàðû öåïåé i è j
2≥∩ ji GG ,
òîãäà ìèíèìàëüíîå äåðåâî â G'=Gi∪Gj áóäåò ñîäåð-
æàòü îäíî (ïðîèçâîëüíîå) äåðåâî èç Gi ∩ Gj, ïî
îäíîìó (ïðîèçâîëüíîìó) äåðåâó èç G³\Gi ∩Gj è
Gj\Gi ∩ Gj, à òàêæå äâà ïðîèçâîëüíûõ ðåáðà, äîñ-
òàâëÿþùèõ ñâÿçíîñòü òðåõ óêàçàííûõ ïîäãðàôîâ.
4. �Ïîãëîùåíèå�:
à) åñëè äëÿ ïàðû öåïåé i è j
Gi=Gj,
òî îäíó èç öåïåé ìîæíî èñêëþ÷èòü èç ðàññìîòðåíèÿ
(åñëè íåîáõîäèìî, óâåëè÷èâ âåñ ñîîòâåòñòâóþùèõ
ðåáåð);
á) åñëè äëÿ íåêîòîðîé öåïè m
U
P
k
mk GG
1=
= , (4)
è ïðè ýòîì
1,1, ≤∩∃∈∀ ji GGPji (5)
è
,1∑ −≥∩ PGG ji (6)
òî öåïü m ìîæíî èñêëþ÷èòü èç ðàññìîòðåíèÿ, ïî-
ñêîëüêó ëþáàÿ ñîâîêóïíîñòü äåðåâüåâ äëÿ ïîäãðà-
ôîâ ñîñòàâèò ñâÿçíûé ãðàô.
Åñëè æå óñëîâèå (6) íå âûïîëíÿåòñÿ, è ñîâîêóï-
íîñòü äåðåâüåâ äëÿ ïîäãðàôîâ ñîñòàâèò íåñâÿçíûé
ãðàô, òî öåïü m òàêæå ìîæíî èñêëþ÷èòü èç ðàññìîò-
ðåíèÿ, äîáàâèâ â ýòîì ñëó÷àå ðåáðà, äîñòàâëÿþùèå
ñâÿçíîñòü ãðàôà.
Íèæå ïðèâåäåí ðèñóíîê, èëëþñòðèðóþùèé ñëó-
÷àé, êîãäà ïðè âûïîëíåíèè (5) ñóììàðíàÿ ìîùíîñòü
ïåðåñå÷åíèÿ öåïåé áîëüøå èõ ÷èñëà.
Gi Gj
Gi ∩Gj ≤1
Gi Gj
Gi ∩Gj ≥2
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 4�5 5
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
Òàêèì îáðàçîì, èññëåäóÿ ïåðåñå÷åíèÿ ïîäìíîæåñòâ,
ïîðîæäåííûõ öåïÿìè, ìîæíî ñóùåñòâåííî óìåíüøèòü
ðàçìåðíîñòü çàäà÷è, îñóùåñòâèâ ñíà÷àëà ìàêñèìàëü-
íóþ äåêîìïîçèöèþ ýòèõ ïîäìíîæåñòâ, à çàòåì âûá-
ðàâ ïðîèçâîëüíî ïî îäíîìó èç äåðåâüåâ äëÿ êàæäîé
÷àñòè öåïè è ðåáðà äëÿ îáúåäèíåíèÿ ýòèõ ÷àñòåé â
ñâÿçíûé ãðàô.
Äëÿ ìàêñèìàëüíîé äåêîìïîçèöèè ñõåìû öåëåñî-
îáðàçíî âûáðàòü íàèáîëüøåå ÷èñëî öåïåé, íå èìåþ-
ùèõ îáùèõ ðåáåð.
×åì ìåíüøå ìîùíîñòü öåïè, òåì ìåíüøå âàðèàí-
òîâ ðåàëèçàöèè äåðåâüåâ. Î÷åâèäíî, ÷òî íà÷èíàòü
íóæíî ñ ïîäìíîæåñòâ íàèìåíüøåé ìîùíîñòè. Êðî-
ìå òîãî, öåëåñîîáðàçíî ïîëó÷èòü ñíà÷àëà èç òàêèõ
ïîäìíîæåñòâ ìàêñèìàëüíîå íåçàâèñèìîå ìíîæåñòâî,
ò. å. ìàêñèìàëüíîå ìíîæåñòâî öåïåé, ïîïàðíî íå èìå-
þùèõ îáùèõ ðåáåð:
,1||è1||,1, ∑ −≥∩≤∩∃∈∀ PGGGGPji jiji
.maxmin,
1
→=
=
PG
P
k
kU
Àëãîðèòì.
Íà÷àëüíûå óñòàíîâêè:
Âñå Gi óïîðÿäî÷åíû ïî âîçðàñòàíèþ | Gi|, ò. å.
.......,1 21 ni GGGGni ≤≤≤≤≤∃∈∀
.,1},{ niGB i ∈=
.\:;: 11 GBBGB ==
Ïîêà â B
_
åñòü Gi, äëÿ êîòîðûõ 1≤∩ iGB
{
âûáðàòü min;=∪ iGB
(ïðè ðàâåíñòâå îöåíîê ïðåäïî÷òåíèå ,∅≠∩ iGB ýòî
îáåñïå÷èâàåò ñâÿçíîñòü ãðàôà).
.\:;: ii GBBGBB =∪=
}
Ïîëó÷åííîå ìíîæåñòâî öåïåé áóäåò îáðàçîâûâàòü íå-
êîòîðûé áàçèñ. Ëó÷øå âñåãî, åñëè áàçèñ ïðåäñòàâëÿåò
ñîáîé ñâÿçíûé ãðàô, âêëþ÷àþùèé âñå âåðøèíû, ò. ê. èí-
ôîðìàöèÿ î äîñòèæèìîñòè âåðøèí ïîçâîëèò áîëåå îáî-
ñíîâàííî âûáèðàòü äåðåâüÿ.
Äåêîìïîçèöèÿ öåïåé áàçèñà.
Ïóñòü Xi � ìíîæåñòâî ýëåìåíòîâ, èíöèäåíòíûõ öå-
ïè Gi.
Ïóñòü âûäåëåíà ïîäñõåìà, ñîäåðæàùàÿ ìíîæåñòâî Xi,
è ñâÿçè ìåæäó íèìè, ò. å. ÷àñòè G'j âñåõ öåïåé Gj, äëÿ
êîòîðûõ
.2≥∩ ji GG
1. Åñëè i
GG
j GG
ji
=
≥∩
I
2
' , òî ïðè êðèòåðèè ìèíèìóìà
ðåáåð ãðàôà âûáîð äåðåâà ïðîèçâîëåí.
Ïðèìå÷àíèå. Îòìåòèì, ÷òî êðèòåðèé ìèíèìóìà ðåáåð
äàëåêî íå åäèíñòâåííûé, à âîçìîæíî, è íå ãëàâíûé,
ïîýòîìó ñëåäóåò îáðàòèòü âíèìàíèå íà äðóãèå êðèòå-
ðèè, íàïðèìåð, íà ìàêñèìóì äèàìåòðà ãðàôà. ×åì
áîëüøå äèàìåòð ãðàôà, òåì áîëüøå ñòåïåíåé ñâîáîäû
ó åãî âåðøèí, òåì áîëüøå ãèáêîñòü ïðè óêëàäêå åãî â
ìîíòàæíîå ïðîñòðàíñòâî, òåì áîëüøå âàðèàíòîâ óêëàä-
êè, îáåñïå÷èâàþùèõ ìèíèìóì äëèíû ñâÿçåé. Íàïðè-
ìåð, åñëè ñðåäè âåðøèí, èíöèäåíòíûõ Gi, ñóùåñòâóåò
òîëüêî ïàðà âåðøèí xj è xk, äëÿ êîòîðûõ âûïîëíÿþò-
ñÿ óñëîâèÿ
},{},{ kkijji xGGxGG =∩=∩
ò. å.
,1,1 =∩=∩ kiji GGGG
òî ôèêñèðóåòñÿ ïðîñòàÿ öåïü, â êîòîðîé xj è xk � âè-
ñÿ÷èå âåðøèíû, à ïîðÿäîê ñîåäèíåíèÿ îñòàëüíûõ âåð-
øèí ïðîèçâîëåí. Åñëè æå ïîäîáíûõ âåðøèí áîëüøå
äâóõ, òî öåëåñîîáðàçíî îòëîæèòü ôèêñàöèþ ðåáåð è
ïåðåéòè ê ðàññìîòðåíèþ äðóãèõ öåïåé, â êîòîðûõ, âîç-
ìîæíî, âûáîð áóäåò îäíîçíà÷íûì, è ïîÿâèòñÿ äîïîë-
íèòåëüíàÿ èíôîðìàöèÿ î ñòåïåíè áëèçîñòè âåðøèí,
ïðèíàäëåæàùèõ Gi.
2. Åñëè ,
2
i
GG
j GG
ji
≠′
≥∩
I òî Xi öåëåñîîáðàçíî ðàçáèòü
íà êëàññû, ñîîòâåòñòâóþùèå ïåðåñå÷åíèÿì ðàçëè÷íîé
êðàòíîñòè ìíîæåñòâ êîìïîíåíòîâ, èíöèäåíòíûõ ðàçëè÷-
íûì öåïÿì.  ýòîì ñëó÷àå âñå âûøåèçëîæåííîå ìîæíî
ïðèìåíèòü äëÿ ïîäñõåìû (èñêëþ÷èòü ïîãëîùàåìûå öåïè,
íàéòè áàçèñ è ò. ä.) äî òåõ ïîð, ïîêà äëÿ êàêîé-ëèáî
öåïè (÷àñòè öåïè) íå áóäóò ôèêñèðîâàíû äâóõêîíòàêò-
íûå ñîåäèíåíèÿ.
Ïîñëå äåêîìïîçèöèè öåïåé áàçèñà îñóùåñòâëÿåòñÿ
äåêîìïîçèöèÿ îñòàëüíûõ öåïåé â ïîðÿäêå âîçðàñòàíèÿ
èõ ìîùíîñòè.
Ïðèìåð
Ïðîäåìîíñòðèðóåì ïðåèìóùåñòâà ïðåäëàãàåìîãî
ïîäõîäà íà ïðèìåðå èç [1]. Ãðàô ñõåìû çàäàí ìàòðèöåé
èíöèäåíòíîñòè �öåïè�ìîäóëè�:
15
4
1
4
1
−>=∩∑∑
+==
PGG ji
iji
P=4,
G1
G2
G3
G4
Òåõíîëîãèÿ è êîíñòðóèðîâàíèå â ýëåêòðîííîé àïïàðàòóðå, 2001, ¹ 4�5
6
ÏÐÎÅÊÒÈÐÎÂÀÍÈÅ. ÊÎÍÑÒÐÓÈÐÎÂÀÍÈÅ
01110
11001
10011
10110
01101
11011
q
p
n
m
l
k
edcba
Çäåñü a, b, c, d, e � ìîäóëè; k, l, m, n, p, q � öåïè.
Ãðàô âàðèàíòîâ äëÿ òàêîé ñõåìû áóäåò ïðåäñòàâëÿòü
ñîáîé ïîëíûé ãðàô K5.
Ïîñêîëüêó pnk GGG ∪= è ïðè
ýòîì },{ eaGG pn =∩ , òî öåïü k èñ-
êëþ÷àåì � �ïîãëîùåíèå� á).
Öåïè p è q íå ìîãóò èìåòü îá-
ùèõ ðåáåð ),}{( dGG qp =∩ ò. å. â
ãðàôå qp GGG ∪=′ äëÿ êàæäîé èç
öåïåé äåðåâî ìîæíî âûáðàòü ïðî-
èçâîëüíî. Êðîìå òîãî, GGG qp =∪ , ò. å. },{ qp GG � áà-
çèñ. (Îòìåòèì, ÷òî ïîäîáíûìè ñâîéñòâàìè îáëàäàþò ïàðû
öåïåé l è m, n è q.)
Âûäåëèì ïîäñõåìó, ñîäåðæàùóþ ìíîæåñòâî êîìïî-
íåíòîâ, èíöèäåíòíûõ öåïè ð. Ïîñêîëüêó pkpk GGGG =∩=′ ,
G'k èñêëþ÷àåì èç ðàññìîòðåíèÿ. Îñòàâøèåñÿ G'n è G'l
èìåþò ïî îäíîìó ðåáðó:
};,{ eaGGG npn =∩=′
};,{ daGGG lpl =∩=′
111p
101
011
111
n
l
k
eda
Àíàëîãè÷íî, äëÿ öåïè q:
};,{
};,{
'
'
dcGGG
cbGGG
lql
mqm
=∩=
=∩=
111q
011
110
m
l
dcb
 öåïÿõ p, q è l äåðåâüÿ óæå îïðåäåëåíû. Êðîìå òîãî,
çàôèêñèðîâàíî ïî îäíîìó ðåáðó â öåïÿõ m è n.
Ïîñêîëüêó â öåïè m ðåáðî {b,c} óæå çàôèêñèðîâàíî,
òî îñòàåòñÿ òîëüêî ðåáðî {b,e}:
011
101
101
q
n
k
ecb
111m
}.,{'' ebGGGG nmkn =∩==
 ðåçóëüòàòå áóäåò ïîëó÷åí ãðàô, ïðåäñòàâëåí-
íûé íèæå.
Òàêèì îáðàçîì, îïðåäå-
ëåíà ïîñëåäîâàòåëüíîñòü ñî-
åäèíåíèé âî âñåõ öåïÿõ áåç
ïîñòðîåíèÿ âñåõ äåðåâüåâ
äëÿ êàæäîé èç öåïåé è áåç
ñðàâíåíèÿ âñåõ âîçìîæíûõ
êîíôèãóðàöèé, ñîäåðæàùèõ
ïî îäíîìó äåðåâó äëÿ êàæ-
äîé èç öåïåé.
Çàêëþ÷åíèå
Ïîñòàíîâêà [1] èíòåðåñíà, íî êîìáèíàòîðíàÿ ñëîæ-
íîñòü ìåòîäà ñëèøêîì âûñîêà.
Äåéñòâèòåëüíî, ÷èñëî ðàçëè÷íûõ äåðåâüåâ, êîòî-
ðûå ìîæíî ïîñòðîèòü íà n âåðøèíàõ, ðàâíî nn�2 [2,
ñ. 173], ïîýòîìó ÷èñëî âîçìîæíûõ âàðèàíòîâ ìîäå-
ëåé ñõåìû ñîñòàâèò
.
1
2∏
=
−=
m
i
n
i
inQ
Äàæå äëÿ ñðàâíèòåëüíî íåáîëüøèõ ñõåì ÷èñëî
Q îãðîìíî è èñêëþ÷àåò âîçìîæíîñòü ïîñòðîåíèÿ
ìîäåëè ïóòåì ïðÿìîãî ïåðåáîðà.
Äëÿ õðàíåíèÿ òåðìîâ íåîáõîäèì îáúåì ïàìÿòè
òîãî æå ïîðÿäêà.
Îöåíèì ñëîæíîñòü ïðåäëàãàåìîãî ìåòîäà.
Äëÿ ñîðòèðîâêè öåïåé â ïîðÿäêå âîçðàñòàíèÿ
÷èñëà èíöèäåíòíûõ èì êîìïîíåíòîâ íåîáõîäèìî
O(mlogm) îïåðàöèé.
Äëÿ ôîðìèðîâàíèÿ áàçèñà òðåáóåòñÿ îïðåäåëèòü
ìîùíîñòè ïåðåñå÷åíèé öåïè-ïðåòåíäåíòà ñ öåïÿìè,
âõîäÿùèìè â áàçèñ. Òî åñòü íóæíî ñðàâíèâàòü ñïèñ-
êè öåïåé. Åñëè êîìïîíåíòû â öåïÿõ îòñîðòèðîâàíû
â ïîðÿäêå âîçðàñòàíèÿ íîìåðîâ, òî äëÿ ïàðû öåïåé i
è j ñëîæíîñòü ñðàâíåíèÿ ðàâíà ñóììå êîëè÷åñòâ
èíöèäåíòíûõ èì êîìïîíåíòîâ:
.' ji nnQ +=
Òàêèì îáðàçîì, êîìáèíàòîðíàÿ ñëîæíîñòü ïîñò-
ðîåíèÿ áàçèñà íå âûøå )(
1
∑
=
m
i
inmO .
Óìíîæèâ ýòó îöåíêó íà êîëè÷åñòâî öåïåé, ïîëó-
÷èì îöåíêó îáùåé êîìáèíàòîðíîé ñëîæíîñòè ïðåä-
ëîæåííîãî ìåòîäà (ðàçìåðíîñòü îñòàëüíûõ ïîäçà-
äà÷ ñóùåñòâåííî ìåíüøå):
)(
1
2∑
=
m
i
inmO .
ÈÑÏÎËÜÇÎÂÀÍÍÛÅ ÈÑÒÎ×ÍÈÊÈ
1. Øðàì÷åíêî Á. Ë., Àáàêóìîâ Â. Ã. Îá îïðåäåëåíèè
ìàòðèöû ñìåæíîñòè ìîäóëåé // Â êí.: Àâòîìàòèçàöèÿ
ïðîåêòèðîâàíèÿ â ýëåêòðîíèêå. Âûï. 11.� Êèåâ: Òåõ-
íèêà, 1975.
2. Áåðæ Ê. Òåîðèÿ ãðàôîâ è åå ïðèìåíåíèÿ.� Ì.:
ÈË, 1962.
a
b
cd
e
a
b
cd
e
|
| id | nasplib_isofts_kiev_ua-123456789-70866 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 2225-5818 |
| language | Russian |
| last_indexed | 2025-12-01T19:13:25Z |
| publishDate | 2001 |
| publisher | Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України |
| record_format | dspace |
| spelling | Зудин, С.В. Лузин, С.Ю. Полубасов О.Б. 2014-11-15T16:25:45Z 2014-11-15T16:25:45Z 2001 Выбор конфигурации соединения компонентов электронных схем до этапа размещения / С.В. Зудин, С.Ю. Лузин, О.Б. Полубасов // Технология и конструирование в электронной аппаратуре. — 2001. — № 4-5. — С. 3-6. — Бібліогр.: 2 назв. — рос. 2225-5818 https://nasplib.isofts.kiev.ua/handle/123456789/70866 681.3 Предложен метод построения деревьев соединений компонентов в многозвенных цепях с целью повышения качества автоматического размещения в САПР печатных плат и БИС. ru Інститут фізики напівпровідників імені В.Є. Лашкарьова НАН України Технология и конструирование в электронной аппаратуре Проектирование. Конструирование Выбор конфигурации соединения компонентов электронных схем до этапа размещения Article published earlier |
| spellingShingle | Выбор конфигурации соединения компонентов электронных схем до этапа размещения Зудин, С.В. Лузин, С.Ю. Полубасов О.Б. Проектирование. Конструирование |
| title | Выбор конфигурации соединения компонентов электронных схем до этапа размещения |
| title_full | Выбор конфигурации соединения компонентов электронных схем до этапа размещения |
| title_fullStr | Выбор конфигурации соединения компонентов электронных схем до этапа размещения |
| title_full_unstemmed | Выбор конфигурации соединения компонентов электронных схем до этапа размещения |
| title_short | Выбор конфигурации соединения компонентов электронных схем до этапа размещения |
| title_sort | выбор конфигурации соединения компонентов электронных схем до этапа размещения |
| topic | Проектирование. Конструирование |
| topic_facet | Проектирование. Конструирование |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/70866 |
| work_keys_str_mv | AT zudinsv vyborkonfiguraciisoedineniâkomponentovélektronnyhshemdoétaparazmeŝeniâ AT luzinsû vyborkonfiguraciisoedineniâkomponentovélektronnyhshemdoétaparazmeŝeniâ AT polubasovob vyborkonfiguraciisoedineniâkomponentovélektronnyhshemdoétaparazmeŝeniâ |