АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ РЭС С ПРИМЕНЕНИЕМ САПР; ТРАССИРОВКА МОНТАЖНЫХ ПЛАТ С ПРОВОДНЫМ И ПЕЧАТНЫМ МОНТАЖОМ

Министерство науки, высшей школы и технической 
политики Российской Федерации 

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ 

Кафедра радиотехнических устройств и систем 

УТВЕРЖДЕНО 

проректором по учебной работе 

АВТОМАТИЗАЦИЯ КОНСТРУКТОРСКОГО ПРОЕКТИРОВАНИЯ 
РЭС С ПРИМЕНЕНИЕМ САПР; ТРАССИРОВКА МОНТАЖНЫХ 
ПЛАТ С ПРОВОДНЫМ И ПЕЧАТНЫМ МОНТАЖОМ 

Методическое пособие по выполнению 
лабораторных работ для студентов 
1У курса специальности 23.03 

Москва 
Издательство МГОУ 
1993 

/ 

М.В. Головицына, С.А. Иншаков, Г.И. Гаврилко 

© 
МГОУ, 1993 

- 3 
I . ОБЩАЯ ПОСТАНОВКА ЗАДАЧИ ТРАССИРОВКИ. 
КРАТКАЯ ХАРАКТЕРИСТИКА АЛГОРИТМОВ 
ТРАССИРОВКИ ПРОВОДНОГО И ПЕЧАТНОГО 
МОНТАЖА 

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

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

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

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

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

- 4 - . 

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

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

Расстояние между каждой парой вершин полного подграфа для проводников, идущих по кратчайшему направлению 
• 
^ 

d y 
- 
( t i - t , - ) ' 

для ортогональной трассировки 

d ^ l S r ^ M t r t j l , 

где 
U 
j 
-соответствующие координа
ты 
i 
-й 
и 
J 
-ft 
вершины графа. 
п-Z 
На чЛ/ 
вершинах можно построить 
п — П 
различных деревьев. В связи с этим точное решение задачи построения мшимального дерева методом полного перебора нецелесообразно. Существую* приближенные алгоритмы 
решения этой задачи, дающие результаты, достаточно близкие к оптимальнда. 

Построение минимальных деревьев соединений мажет 
быть осуществлено при использовании процедур, основан

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

При печатном монтаже в пространстве, представляющем собой совокупность коммутационных плоскостей, определены координитц конструктивных элементов и их выводов 
заданы метрические параметры и топологические свойства 
монтажного пространства. Множество цепей принципиальной 
схемы В разбивают на непересекающиеся подмножества В I 
так, что 
В = / Ь j | 
i 
= f > . j 
, а 
В^ » {6/ 
,к]к 
в 17~к ^ } » где 
Иг 
- число цепей; к ^ 
число контактов, соединяемых 
l 
-й цепью. 

Необходимо реализовать множество В j 
в виде множества А [ 
таких областей, которые удовлетворяли бы 

следующим требованиям: 
иг 

I. .U Я I 
Е 
- 
цсе соединения должны быть вы 

полнены в монтажной области Е = £ ^r-! Г" = I, R 3 
» ГД® 
R. 
- число слоев. 

в каждом слое про 
* 
its' 

водники не должны иметь пересечения; 

V
- 
^ с т о я н и е между 
проводниками не должно быть меньше допустимого зазора 

4, & 
-> oLq 
- ширина проводника не должна 
бить меньше допустимой; 

b . f V i ^ k т, 
С Л i 
- нее контакты 
L -й 

цепи должны лежать на 
i 
-м проводнике; 

ь. (Vit 
е- £>)(V^ 
е Et)lAt<] 
Я- = 0 VA^A^Rk 
; 

£ г- , В i 
£ 
1 осли необходимо выполнить переход 
слоя 
Г" 
на слой 
t 
, пересечение ооластей. должно 
иметь размер, достаточный для конструктивной реализации 
межслоиниги перехода. 

- б 
Задача одновременной оптимизации всех соединений 
пока ие решена, поэтому трассировку сводят- к последовательному построение <5<етерекрестного дерева, каждое дерево которого реализует соответствующую электрическую 
цепь, и определению конфигураций соединения, Система 
покрывающих деревьев ?*олзша бить размещена в монтажном 
пространстве типовой конструкции» заданном своей математической моделью. 

Трассировка печатник соединений предполагает выполнение следующих этапов: 

1) определение порядка соединения выводов внутри 

цепи; 

2) распределение соединений по СЛОЯМ печатной ш и ты; 

3) нахождение последовательности проведения Соединений в каждом слое; 

4) получение конфигурации проводников, т . е . синтез 
их геометрии. 

При решении задачи трассировки используют следующий 
основные критерии: 

1) минимум суммарной длины всех проводников; 
2) минимум числа их пересечений; 
3) минимум изгибов проводников,' 
4) минимум числа слоев печатной платы и переходов 
со слоя на слой; 

5) минимальная длина параллельных участков соседних 
проводников; 

6) равномерное распределение проводников по монтажной области. 

Критерий I приводит к уменьшению задержки распространения сигналов по линиям связи, критерии 2, 3 и 4 повидают надежность и технологичность печатной платы, критерии 5 и 6 увеличивают помехоустойчивость конструктивной реализации схемы и вероятность цроведения всех трасе. 

- 7 - . 

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

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

1'ассмотрим первые две группы. 
Исторически первым алгоритмом трассировки печатного 
монтажа является алгоритм-Ли. Известны модификации его 
со значительно уменьшенным расходом машинного времени. 
Так известен лучевой алгоритм, работающий на матричной 
структуре данных, который осуществляет поиск и проведение пути трассировки путем исследования пространства 
магистралей, а не ячеек дискретного рабочего поля (ДРП), 
как в алгоритме Ли. 

Известны также красивые эвристические алгоритмы 
трассировки, работающие на матричной структуре данных. 
В отличие от волновых -алгоритмов последние не гарантируют 
обнаружение проводящего пути, даже если он существует и, 
следовательно, дают менее высокий процент реализации соединений на насыщенных платах. Следует особо отметить малоповорртмые эвристические алгоритмы, свободные от недостатка в виде лесенки. Малоповоротные алгоритмы минимизируют 
не длину ломаной, а количество изломов. Но часто такие 
алгоритмы конструируют трассу в БИде ломаной с заранее 
ограниченным числом звеньев (обычно пять - семь), возрас

- 8 
тание этого количества ведет к трудностям при программировании и резкому увеличению времени счета. 

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

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

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

описание данных в виде бесструктурного набора отрезков содержит избыточность. 

Сравнительно недавно опубликован второй малоповоротный алгоритм Эрара, который внёс значительный вклад в р а з витие методов автоматической трассировки. Основная идея 
Эрара - применение волнового процесса к специальному граф/, 
вершинами которого являотся свободные отрезки ДРП, а соединение двух вершин ребром означает возможность перехода 
с одной вершины на другую. Граф вычисляется с помощью матричных данных, которые в этом случае являются вспомогательньми. Все отрезки, проведенные волной, также должны запоминаться, впрочем, большую их часть нужно хранить на внешнем накопителе, а в оперативной памяти лишь текущий фонт 
волны. Алгоритм Эрара очень быстр, поскольку волна идет 
не отдельными дискретами, а целыми отрезками. Кроме того, 
соединение идей волнового процесса с малоповоротными критериями оптимизации дает высокий процент реализации и довольно технологичную конфигурацию соединений. Однако он 

- 9 
требует большого объема памяти, так как имеет матричную структуру. В нижеприведенной программе удалось 
объединить идеи- Эрара и Хабтауэра и создать быстрый 
волновой малоповоротный алгоритм трассировки. 

Основные отличительные особенности алгоритма следующие: 

трассировка производится по ДРП, данные о текущем 
состоянии которого хранятся в оперативной памяти; 

отсутствуют существенные ограничения на габариты 
проектируемой платы (при реализации предельные размеры 
трассировочной зоны принять равными 510 х 510 дискретов, при плане решетки 1,25 мм составляет около 637 х 
х 637 мм); 

алгоритм позволяет настройку на правила установки 
иехсдойных переходов. 

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

При этом необходимо учитывать различные конструктЫвно-технологич^ские ограничения (допускаются пересечения ила нет, возможен ли переход со слоя на слой, 
сколько слоев отводится яля трассировки, допустимые 
аирима проводников и расстояния между ними и т . д . ) . 
Алгоритмы трассировки существенно зависят от принятой 
конструкции к технологии изготовления РЭА. 

2. АЛГОРИТМЫ ПРОШКШАНШ ПРОВОДОГО Н Ш Ш 

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

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

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

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

Для определения минимального дерева можно построить на заданных 
И 
вершинах все возможные деревья 
и выбрать минимальное из них, но практически для РЭА 
(число цепей исчисляется сотнями) поиск всех деревьев 
нереален. 

Задача построения минимального дерева формулируется следующим образом. 

Пусть Р = { f p ^2» • • • » 
} 
~ множество точек плоскости, соответствующих выводам произвольной цегч. 

Рассмотрим полный граф 

( х - ( Х 1 и ) , 

вершины которого X 
G. JC 
соответствуют выводам 
цепи, а ребра U 
U 
с приписанная к ним весом 

р (U) 
характеризуют соединения между парами выводов. 
Значение 
p ( U ) 
может быть равно расстоянию меж
ду соответствующими точками множества Р. В общем случае 
Р (U) 
может представлять линейную комбинацию нескольких характеристик объекта.