КТОП теория
.pdf
Определение порядка соединения выводов внутри цепи. Задача сводится к построению минимального связывающего дерева (рис. 10.3). При печатном монтаже соединения можно выполнять по выводам и в любой точке проводника. Последнее сводится к задаче
Штейнера, в которой вершины сопоставлены выводам цепи, а дополнительные точки представляют собой места соединения типа проводник-проводник (рис.10.3, в).
Рис. 10.3. Минимальные связывающие деревья:
а− минимальное,
б− цепь,
в− дерево Штейнера, x s− вершина, где создано Т – образное
соединение проводников
Виды монтажных соединений печатных проводников даны на рис. 10.4, а преобразование минимального связывающего дерева – рис. 10.5.
Определение порядка трассировки проводников на слое. Это связано с тем, что успех трассировки очередного проводника существенно зависит от конфигурации уже проведенных трасс. Часто применяется простой метод упорядочения, основанный на оценке длины проводников:
1)соединение проводников в порядке возрастания длины отдельных проводников. Этот метод основан на том соображении, что короткие проводники вносят меньше конфликтных ситуаций;
2)соединения проводятся в порядке убывания длины проводников,
т.к. более длинные проводники труднее трассировать.
Распределение соединений по слоям.
В результате выполнения первого этапа трассировки электрическую цепь представляют минимальным покрывающим деревом, являющимся плоским графом. Однако совокупность минимальных деревьев (лес) может иметь пересечения между ребрами, принадлежащими разным деревьям, так как последние строят на фиксированных вершинах и существуют ограничения на размер монтажного поля, ширину проводников и зазор между ними. В то же время в каждом слое проводники не должны пересекаться.
Применяют общие два способа трассировки:
1) последовательно проводят соединения до заполнения очередного слоя, после чего переходят к заполнению следующего слоя; 2) Подсчитывают возможное число пересечений проводников, совмещенных в одном слое, а затем проводят распределение
проводников по слоям.
При ортогональной трассировке возможно распределение соединений по двум слоям. Каждую цепь представляют в виде ортогонального покрывающего дерева, вертикальные ветви которого проводят в одном слое, горизонтальные – в другом. На рис. 10.5 показаны минимальное (а) и ортогональное штейнеровы деревья (в). В узлах дерева необходимо делать межслойные переходы. Количество переходов обычно оказывается весьма большим, что ухудшает механические параметры ПП и снижает надежность схемы.
При трассировке по произвольным направлениям можно поставить задачу разбиения графа схемы на минимальное число плоских подграфов, каждый из которых реализуется в своем слое. Основная трудность при такой постановке заключается в построении модели схемы, точно отображающей связность элементов и их топологические свойства. В современных алгоритмах предусмотрены процедуры для устранения пересечения проводников и распределения их по слоям. На рис.10.6 даны пояснения по взаимному расположению проводников.
Распределение соединений по слоям можно сформулировать как задачу правильной раскраски вершин графа пересечений. Предположим, что соединение полностью выполняется на одном слое. При ортогональной трассировке на вершинах каждой цепи строят минимальный охватывающий прямоугольник (рис.10.6, а). Два соединения пересекаются, если пересекаются соответствующие им прямоугольники.
При представлении цепи минимальным покрывающим деревом необходимо определять, пересекается ли каждая пара ветвей этих деревьев. Для пары ветвей при известных координатах вершин составляют уравнения прямых линий. Исследуя эти уравнения аналитической геометрии, определяют возможность пересечения соответствующих соединений.
Вершины графа пересечений сопоставляются соединениям, ребра устанавливают возможность их пересечения. Раскраска вершин графа будет правильной, если никакие смежные вершины не окрашены одним цветом. Минимальное количество цветов, которое необходимо для правильной раскраски, определяет число слоев МПП.
Перекрытие прямоугольников, построенных на вершинах цепей, или пересечение минимальных покрывающих деревьев еще не означает, что соответствующие цепи нельзя трассировать на одном слое без пересечений. На рис. 10.6. показаны перекрывающиеся прямоугольники (а) и непересекающиеся цепи (г), соединяющие охватываемые ими вершины; пересекающиеся минимальные деревья
(в) и непересекающиеся трассы (г), соединяющие те же вершины. При учете возможности проведения “конфликтующих” проводников без пересечения за счет огибания, распределение соединений по слоям может быть сделано путем объединения проводников в группы и трансляции ее в своем слое.
11