Перечень проводников

Задача трассировки

Главная цель задачи размещения

Главной целью задачи размещения является облегчение следующей за ней трассировки соединений. Если связи между элементами осущест­вляются проводным монтажом, то наилучшим критерием оптимальности размещения будет суммарная взвешенная длина соединений. Ограничения для задачи размещения связаны с конкретными кон­структивно-технологическими особенностями узла и составляющих его элементов, а также с требованиями помехоустойчивости и тепло­обмена в конструкции, например ограничения на максимальную длину проводников, наличие определенных разъемов, положение которых в монтажном пространстве фиксировано, и т. п.

11.4.1. Исходные данные для решения задач трас­сировки

Исходными данными для решения задач трас­сировки межэлементных соединений некоторого узла являются:

- параметры коммутационного поля узла (например, размеры ком­мутационного поля, координаты всех контактных площадок и внеш­них выводов печатной платы, координаты контактов разъемов для па­нелей ЭВМ и т. д.);

- координаты контактов каждого конструктивного элемента на ком­мутационном поле, определенные по результатам размещения элемен­тов в узле;

- список всех электрических цепей и перечень контактов элементов, относящихся к каждой отдельной цепи, составленные по схеме соеди­нений элементов.

Необходимо соединить печатными, пленочными или навесными проводниками все контакты элементов согласно схеме соединений с учетом определенных требований и ограничений.

В зависимости от способа реализации соединений критериями оп­тимальности трассировки могут быть: минимальная суммарная дли­на соединений; минимальное число слоев монтажа; минимальное чис­ло переходов из слоя в слой; минимальные наводки в цепях связи элементов и др.

Первый критерий — основной и применяется во всех алгоритмах трассировки, остальные критерии относятся к частным показателям качества трассировки и используются в основном для многослойных печатных плат (МПП).

Ограничения для задачи трассировки тесно связаны с техноло­гией получения межэлементных соединений и конструктивными тре­бованиями к монтажу:

1) К технологическим ограничениям относятся: для проводного мон­тажа — максимальное число накруток на один контакт; тип монтажа («в навал» или жгутовой); минимальная длина проводов и т. п.; для печатного монтажа — ширина проводников и расстояние между ними; число проводников, подводимых к одному контакту; максимальное число слоев; наличие одного слоя для шин питания и т. п.

2) К конструктивным ограничениям относятся: размеры коммутацион­ного поля; наличие проводников, трассы которых заданы; максималь­ная длина проводников и максимальная длина параллельно идущих проводников в двух соседних слоях и т. п.

Рассмотрим основные методы и алгоритмы на примере решения от­дельных этапов задачи трассиров­ки соединений многослойной пе­чатной платы, так как эти методы в той или иной модификации ис­пользуются для решения любых других задач трассировки.

Конструкция многослойной пе­чатной платы (МПП) представляет собой совокупность монтажных слоев, расположенных один под дру­гим. Монтажный слой — плоскость ограниченных размеров, на ко­торую условно нанесена координатная сетка линий, определяющая места прокладки печатных проводников. Предполагается, что контакт­ные ножки микросхем, размещенных на плате, проходят через все слои так, что соединение двух любых ножек можно выполнить в. любом слое. Шаг координатной сетки определяет ограничения на ши­рину проводников и минимальное расстояние между ними.

Решение задачи трассировки соединений в МПП предполагает выполнение следующих основных этапов (см. [1]):

1. Определение перечня (списка) всех проводников, которые должны быть проложены между парами различных контактов.

2. Распределение проводников по слоям.

3. Определение последовательности трассировки проводников в. каждом слое.

4. Собственно трассировка проводников.

В исходных данных заданы электрические цепи и перечень кон­тактов, которые они объединяют.

На этапе 1 необходимо решить, в какой последовательности сле­дует соединять контакты одной цепи (т. е. установить перечень проводников одной цепи для каждой пары контактов), чтобы суммарная длина всех соединений цепи была минимальна. Эта задача сводится к задаче построения минимального связывающего дерева.

Пусть Х — множество точек на плоскости, соответствующих контактам одной электрической цепи. Рассмотрим полный граф G = = (X, А), в котором множество ребер с приписанным им весом d_ij характеризуют все возможные соединения электрической цепи между парами контактов. Граф G определяется матрицей расстояний D = [ d_ij ] _nxn, где п — число контактов цепи (n > 3). Необходимо определить в графе G дерево G', включающее все его вершины и имеющее минимальный суммарный вес ребер. Число ребер графа G' равно n — 1. На рис.14, а приведен пример минимального связывающего дерева для семи контактов.

Рис.14. Минимальные связываю­щие деревья:

1— кратчайшее ребро

Наибольшее распространение для решения этой задачи на ЭВМ получил алгоритм Прима. На первом шаге алгоритма для произволь­ного контакта находится ближайшая вершина и соединяется ребром. На остальных п — 2 шагах из множества не подсоединенных контак­тов выбирается тот, который находится ближе всего к группе уже Связанных контактов и соединяется кратчайшим ребром. На рис.17, 6 показаны фрагмент дерева (x₁, x₂, x₃, x₄, x₅) после четвертого шага ал­горитма, ближайший контакт х₆ и кратчайшее ребро (x_s, x₆), имеющее минимальное значение d_ij среди всех возможных, ребер, показанных пунктиром. В результате перечень проводников для трассировки цепи на рис.17, а будет [(x₁, х₂) (х₂, x_з) (x₃, x₄₎ (х₄, х₅) (x₅, х₆) (x₆, x₇)].

Для печатного монтажа лучшие результаты будут получены, если искать минимальное дерево в координатной сетке; такое дерево называется минимальным ортогональным деревом (рис.17, е). Осо­бенность этой задачи заключается в том, что при получении дерева допускается введение дополнительных вершин х’₁ и х’₂., а такое де­рево называется деревом Штейнера. Для решения задачи в данной постановке применяется ортогональная метрика (для расчета d_ij) и разработаны различные точные и приближенные алгоритмы, ана­логичные алгоритму Прима (см. [2, 3]).

Дата добавления: 2013-12-12