Постановка задачи трассировки печатных соединений

1) построению бесперекрестного минимального леса и

2) отысканию кратчайшего пути между его вершинами (трассировка соединений).

Обе эти задачи можно рассматривать как независимые, алгоритмически разрешимые.

1) Построение бесперекрестного минимального леса сводится к поиску таких связывающих деревьев G_l, для каждого из подмножеств С_l, которые минимизируют целевую функцию

где – длина n-й связи в выбранной метрике между точками i и j (контактами выводов), принадлежащими подмножеству С_l, объединяющему N_l контактов.

Применение алгоритмов Краскала (Вайнберга-Лобермана) и Прима позволяет найти минимальное связывающее дерево лишь относительно ранее проведенных цепей, поэтому при трассировке печатных соединений практически не

применяются.

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

Характерной особенностью печатного монтажа является возможность кроме соединений типа «вывод-вывод», применяемых в проводном монтаже, использовать соединения типа «вывод-проводник» и «проводник-проводник».

Оптимизация подобных цепей предполагает построение для каждого множества объединяемых вершин Мⁱ = {т₁⁽ⁱ⁾, т₂⁽ⁱ⁾, ..., m_n⁽ⁱ⁾} минимальных деревьев, допускающих введение произвольного числа дополнительных вершин, образующих множество D = {d1, d2, …, dk}. (т.е. точки соединения и разветвления печатных проводников).

Практически все методы построения минимальных связывающих деревьев не учитывают ограничения на размеры монтажного поля, толщину печатных проводников и величину зазора между ними. В результате значительную часть найденных деревьев оказывается невозможным реализовать в виде электрических цепей печатной платы.

Указанный недостаток, а также большое время, затрачиваемое на построение минимальных связывающих деревьев, привели к тому, что данные алгоритмы применяют лишь для отыскания пар контактов, подлежащих соединению.

2) Трассировку соединений осуществляют с помощью алгоритмов, основанных на методах динамического программирования.

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

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

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

Размеры ячеек определяются конструктивно-технологическими требованиями, предъявляемыми к печатному монтажу. Так как в каждой ячейке обычно один вывод или печатный проводник, максимальные размеры ячеек определяются допустимой точностью воспроизведения проводников.

Минимальные размеры ячеек обусловливаются возможностью ОЗУ ЭВМ и соотношением

где d - расстояние между центрами соседних ячеек; b_n - минимальная ширина печатного проводника; l - минимальное расстояние между соседними проводниками.

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

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

Известные алгоритмы трассировки печатных плат можно условно разбить на три большие группы:

1) волновые алгоритмы,

Основаны на идеях Ли. Получили широкое распространение в существующих САПР,

Достоинство:

– позволяют легко учитывать технологическую специфику печатного монтажа со всей совокупностью конструктивных ограничений.

– всегда гарантируют построение трассы, если путь для нее существует;

2) ортогональные алгоритмы,

Достоинство:

– обладают большим быстродействием, чем алгоритмы 1)

– реализация их на ЭВМ требует в 75—100 раз меньше вычислений по сравнению с волновыми алгоритмами.

Недостаток:

– получение большого числа переходов со слоя на слой,

– отсутствие 100%-ной гарантии проведения ряда трасс,

– большое число параллельно идущих проводников.

Такие алгоритмы применяют при проектировании печатных плат со сквозными металлизированными отверстиями.

3) алгоритмы эвристического типа,

В настоящее время широко распространены (критичны к объему памяти и быстродействию ЭВМ). Частично основаны на эвристическом приеме поиска пути в лабиринте. При этом каждое соединение - проводится по кратчайшему пути, обходя встречающиеся на пути препятствия.