ПРИМЕНЕНИЕ ЗАПРЕЩЕННЫХ ФИГУР В ЗАДАЧЕ РАСКРАСКИ ГРАФА ПРИ ПРОЕКТИРОВАНИИ ПЕЧАТНЫХ ПЛАТ

  • В. И. Потапов Филиал АО «РКЦ «Прогресс – ОКБ «Спектр»
Ключевые слова: Плоские структуры электронных средств, графо-теоретический подход, запрещенные фигуры, трассировка в одном слое, граф, ребро графа, планарность, алгоритм, анализ, синтез, электро-радиоэлемент

Аннотация

Проектирование конструкции печатных плат в виде плоских структур без перемы-
чек является одной из самых сложных задач на этапе схемотехнического проектирования.
Задача в такой постановке особенно актуальна микросборок и для электронных модулей
контрольно-проверочной, бортовой аппаратуры, выполненных по технологии поверхност-
ного монтажа, где, например, по причине металлического теплоотвода или керамического
основания, структура соединений возможна только в одном слое. В работе рассматрива-
ется задача проектирования печатных плат в виде синтеза плоских структур электрон-
ных схем. Целью является расположение соединений на печатной плате без пересечений,
что облегчает условия проведения трасс любому трассировщику современных программ
проектировании. Для её решения предложено большое число различных алгоритмов, основ-
ным недостатком которых является заложенный в них принцип последовательного и
фрагментарного просмотра коммутационного пространства. Сложность алгоритмов
синтеза подобных структур обусловлена также необходимостью учета большого числа
различных требований, связанных со спецификой их изготовления и особенностями разра-
батываемого конструктивно-технологического решения. В настоящей работе предлага-
ется выполнить проектирование печатной платы с высокой эффективностью трассиров-
ки соединений за счет решения задачи расслоения исходного графа-схемы и построения
плоского графа-схемы как на стороне установки ЭРЭ, так и на обратной стороне платы -
стороне пайки, исключая запрещенные фигуры по теореме Потрягина-Куратовского.
Критерием является минимизация переходных отверстий, а также минимизация провод-
ников (ребер) на одной стороне печатной платы. Задача расслоения представляет собой
задачу раскраски графа в два цвета с использованием принципов характеризационного
управления, решение которой базируется на теореме Кенига, определяющей запрещенную
фигуру в виде циклов нечетной длины. Для проектирования печатных плат разработаны
алгоритм и методика построения планарных графов и расслоения графа на две стороны
печатной платы с уменьшением количества неразведенных ребер. Точное решение прини-
мает вид полиномиальной зависимости не выше 5-й степени, позволяет получить резуль-
тат за приемлемое время и повысить эффективность трассировки на 5–15 %.

Литература

1. Alekseev O.V., Golovkov A.A., Pivovarov I.Yu. Avtomatizatsiya proektirovaniya
radioelektronnykh sredstv [Automation of design of radio-electronic means]. Moscow:
Vysshaya shkola, 2000, 479 p.
2. Gorbatov V.A. Fundamental'nye osnovy diskretnoy matematiki. Informatsionnaya matematika
[Fundamental foundations of discrete mathematics. Information Mathematics]. Moscow:
Nauka, Fizmatlit, 2000, 544 p.
3. Gorbatov V.A., Smirnov M.I., Khlytchiev I.S. Logicheskoe upravlenie raspredelennymi
sistemami [Logical management of distributed systems]. Moscow: Energoatomizdat, 1991,
287 p.
4. Shein A.B, Lazareva N.M. Metody proektirovaniya elektronnykh ustroystv [Design methods
for electronic devices]. Moscow: Infra-inzheneriya, 2011, 456 p.
5. Muromtsev D.Yu., Tyurin I.V., Belousov O.A., Kurnosov R.Yu. Proektirovanie funktsional'nykh
uzlov i moduley radioelektronnykh sredstv [Design of functional units and modules of radioelectronic
means]. Saint Petersburg: Lan', 2018, 251 p.
6. Berzh K. Teoriya grafov i ee primenenie [Graph theory and its application]. Moscow:
Inostrannaya literatura, 1962, 320 p.
7. Norenkov I.P. Osnovy avtomatizirovannogo proektirovaniya [Computer-aided design basics].
Moscow: MGTU im. Baumana, 2009, 430 p.
8. Yurkov N.K. Tekhnologiya radioelektronnykh sredstv [The technology of radio electronic
means]. Penza: PGU, 2012, 640 p.
9. Gladkov L.A., Kureychik V.V., Kureychik V.M. Diskretnaya matematika [Discrete Mathematics].
Moscow: Fizmatlit, 2014, 496 p.
10. Kureychik V.M., Lebedev O.B., Lebedev B.K. Poiskovaya adaptatsiya [Search adaptation].
Moscow: Fizmatlit, 2006, 270 p.
11. Petrov Yu.V. Metody matematicheskogo modelirovaniya radiotekhnicheskikh system
[Methods of mathematical modeling of radio engineering systems]. Saint Petersburg: Balt. gos.
tekhn. un-t, 2005, 111 p.
12. Pirogova E.V. Proektirovanie i tekhnologiya pechatnykh plat [Design and technology of printed
circuit boards]. Moscow: Forum, 2005, 559 p.
13. Muromtsev Yu.L., Muromtsev D.Yu., Tyurin I.V. Informatsionnye tekhnologii proektirovaniya
radioelektronnykh sredstv [Information technologies for designing radio-electronic equipment].
Moscow: Akademiya, 2010, 384 p.
14. Potapov V.I., Suskin V.V., Shevchenko V.F. Teoriya kharakterizatsionnogo upravleniya v
konstruirovanii ploskikh struktur radioelektronnykh sredstv [Theory of characterization control in
the design of flat structures of radioelectronic devices]. Ryazan': OOO «Eko-tekst», 2017, 92 p.
15. Potapov V.I., Suskin V.V. Ob odnom podkhode k sintezu ploskikh struktur elektronnykh
sredstv s zhestkoy logikoy funktsionirovaniya [About one approach to the synthesis of planar
structures of electronic devices with function of rigid logic], Vestnik Ryazanskogo
gosudarstvennogo radiotekhnicheskogo universiteta [Bulletin of the Ryazan State Radio Engineering
University], 2016, No. 56, pp. 83-89.
16. Potapov V.I., Suskin V.V. Modeli i algoritmy proektirovaniya ploskikh struktur elektronnykh
sredstv na osnove gibkoy elementnoy baze [Models and algorithms for designing flat structures
of electronic devices based on a flexible element base], Vestnik Ryazanskogo
gosudarstvennogo radiotekhnicheskogo universiteta [Bulletin of the Ryazan State Radio Engineering
University], 2017, No. 62, pp. 79-88.
17. Potapov V.I. Zadacha sinteza struktury elektronnykh moduley, postroennykh s ispol'zovaniem
printsipov kharakterizatsionnogo upravleniya [The task of synthesizing the structure of electronic
modules built using the principles of characterization management], Sb. statey
Vserossiyskoy nauchno-prakticheskoy konferentsii «Strategiya nauchno-tekhnologicheskogo
razvitiya Rossii: problemy i perspektivy realizatsii. MTSNP «Novaya nauka» [Collection of articles
of the all-russian scientific and practical conference " strategy of scientific and technological
development of Russia: problems and prospects of implementation. MCNP "New science"].
Petrozavodsk, 2020, pp. 18-30.
18. Potapov V.I., Suskin V.V., Filatkin S.V. Printsip postroeniya ploskikh konstruktsiy
elektronnykh skhem s uchetom zapreshchennykh figur [The principle of constructing flat
structures of electronic circuits taking into account forbidden figures], IOP Conference Series:
Materials Science and Engineering (MSE), 2020.
19. Potapov V.I. Zapreshchennye figury v proektirovanii konstruktsiy elektronnykh moduley
[Prohibited figures in the design of electronic module structures], XXV Yubileynaya
Vserossiyskaya nauchno-tekhnicheskaya konferentsiya studentov, molodykh uchenykh i
spetsialistov «Novye informatsionnye tekhnologii v nauchnykh issledovaniyakh (NIT-2020):
Tez. dokl. Ryazan. gos. radiotekhn. un-t. Ryazan', 2020 [XXV Anniversary All-Russian Scientific
and Technical Conference of Students, Young Scientists and Specialists " New Information
Technologies in Scientific Research (NIT-2020): Abstracts of reports of the Ryazan
State Radio Engineering University. Ryazan, 2020].
20. Gumennikova A.V., Emel'yanova M.N., Semenkin E.S., Sopov E.A. Ob evolyutsionnykh
algoritmakh resheniya slozhnykh zadach optimizatsii [On evolutionary algorithms for solving
complex optimization problems], Vestnik SibGAU [Vestnik. SibGAU], 2003, No. 4, pp. 14-23.
21. Onishchenko T.Yu, Marasanov V.V. Kharakterizatsionnyy analiz kak optimizatsionnyy metod
kontrolya i prognozirovanie rabotosposobnosti elektronnykh skhem [Characterization analysis
as an optimization method for monitoring and predicting the performance of electronic circuits],
Vestnik KhNTU [Vestnik HNTU], 2013, No. 3, pp. 12-19.
Опубликован
2021-01-19
Выпуск
Раздел
РАЗДЕЛ I. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ