12. Модификации алгоритма Ли.

Недостатки алгоритма Ли:

• Волна распространяется во все стороны одинаково, и в результате в процессе трассировки производится множество совсем ненужных действий.

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

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

Другой вариант сокращения объемов вычисления – запуск волны во встречных направлениях от источника и приемника. Если два фронта сталкиваются в какой-то точке, то путь найден. Метод дает существенную экономию про времени работы алгоритма.

Есть ещё лучевой алгоритм, его смысл в том, если в алгоритме Ли сначала исследуются клетки соседи, а затем клетки наследники, то в лучевом алгоритме сначала изучаются наследники одного из соседей (например, соседа с самого перспективного направления). Таким образом, первоначально вместо волны образуется направленный луч.

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

12. Сеточные модели дискретного рабочего поля печатной платы.

Еще один из способов ускорить работу волнового алгоритма – заставить волну распространяться неравномерно. Для этого вводится система штрафов за движение в неприоритетном направлении. На рис.2.9. и рис.2.10. представлены модели дискретного рабочего поля (ДРП) односторонней печатной платы с равнозначными и двусторонней ПП с неравнозначными стоимостями перемещения.

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

12. Этапы трассировки проводников на печатной плате. Алгоритмы, применяемые на разных этапах трассировки.

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

Принято выделять четыре основных этапа трассировки:

1. Составление списка соединений.

2. Распределение соединений по слоям (задача расслоения) или зонам (макротрассировка).

3. Определение порядка трассировки для всех соединений.

4. Трассировка проводников.

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