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

Аннотация

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