Алгоритмы и модели трассировки печатных соединений

Лекция 9
АЛГОРИТМЫ И МОДЕЛИ ТРАССИРОВКИ ПЕЧАТНЫХ СОЕДИНЕНИЙ В ЭА (часть 2)
1 Модификация волнового алгоритма. Метод встречной волны
2 Метод соединения комплексами
3 Лучевой алгоритм трассировки
4 Эвристический алгоритм трассировки
5 Особенности автоматизированной трассировки соединений в многослойных печатных платах

Вопрос 1 Модификация волнового алгоритма. Метод встречной волны

Источниками волн являются обе ячейки, подлежащие электрическому объединению.
1) На каждом k-ом шаге поочередно строят соответствующие фронты первой и второй волн, распространяющихся из этих ячеек.
2) Процесс продолжается до тех пор, пока какая-либо ячейка из фронта первой волны не попадет во фронт второй волны или наоборот.
3) Проведение пути осуществляют из данной ячейки в направлении обоих источников по правилам, описанным в волновом алгоритме Ли.
Метод встречной волны

Метод встречной волны

Достоинства алгоритма:
- время, затрачиваемое на этапе распространения волны, уменьшаются примерно вдвое.
Недостатки алгоритма:
- необходимость выделения дополнительного разряда памяти на каждую рабочую ячейку поля для хранения информации о принадлежности ее к первой или второй волне.
- возможность построения лишь соединений типа «вывод – вывод»
Метод встречной волны

Вопрос 2 Модификация волнового алгоритма. Метод соединения комплексами

В качестве источника выбирают не только точку – источник волны, но и только что построенный проводник.
Достоинства алгоритма:
- возможность присоединения каждой очередной точки (начиная с третьей), к любой точке ранее построенных соединений,
- сокращение общей длины печатных проводников
- увеличение числа разводимых цепей
- возможность построения соединений типа «вывод - проводник» и «проводник - проводник».
Недостатки алгоритма:
- больший по сравнению с классическим требуемый объем памяти
Суть:

Вопрос 3 Модификация волнового алгоритма. Лучевой алгоритм трассировки

Лучевой алгоритм трассировки
Выбор ячеек для определения пути между соединяемыми точками А и В производят по заранее заданным направлениям, подобным лучам.
Достоинства алгоритма:
- Сокращение числа просматриваемых алгоритмом ячеек, а следовательно, и время на анализ и кодировку их состояния.
Недостатки алгоритма:
- приводит к снижению вероятности нахождения пути сложной конфигурации (Обычно с помощью лучевого алгоритма удается построить до (70-80)% трасс)
- усложняет учет конструктивных требований к технологии печатной платы.

Основные принципы построения
Задается число лучей, распространяемых из точек А и В, а также порядок присвоения путевых координат (обычно число лучей для каждой ячейки-источника принимается одинаковым).
Лучи А(1), А(2), ..., А(n) и В(1), В(2),..., В(n) считают одноименными, если они распространяются из одноименных источников А или В.
Лучи А(i) и В(i) являются разноименными по отношению друг к другу.
Распространение лучей производят одновременно из обоих источников до встречи двух разноименных лучей в некоторой ячейке С.
Путь проводится из ячейки С и проходит через ячейки, по которым распространялись лучи.

Лучевой алгоритм трассировки
Пример:

Лучевой алгоритм трассировки
1) На первом шаге просматривают ячейки с координатами (2,4), (5,2) и (6,3).
2) На втором шаге луч В(1) и луч А(2) оказываются заблокированными.
3) Лучи В(2) и А(1) встречаются в ячейке С с координатами (4,3) на четвертом шаге.
4) Проводим трассу.

Вопрос 4 Эвристический алгоритм трассировки

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

Эвристический алгоритм
3 – по волновому алгоритму
Общее направление движения должно происходить по ломаной линии минимальной длины или, если это возможно, по прямой, соединяющей объединяемые точки
Пример:

Вопрос 5 Особенности автоматизированной трассировки соединений в многослойных печатных платах

При трассировке учитывается технология изготовления печатной платы.
МПП с открытыми контактными площадками:
1) построение оптимальных связывающих деревьев;
2) разбиение ребер минимального леса на непересекающиеся подмножества, определение очередности построения соединений каждого слоя платы;
3) трассировка печатных проводников.
МПП со сквозными металлизированными отверстиями:
Используется ортогональный монтаж.
Переходы из слоя в слой осуществляются в местах пересечения магистралей.

Вопросы по прочитанному материалу?