Страница: 8/10
Известные алгоритмы трассировки печатных плат можно условно разбить на три большие группы:
1) Волновые алгоритмы, основанные на идеях Ли и разработанные Ю.Л. Зиманом и Г.Г. Рябовым. Данные алгоритмы получили широкое распространение в существующих САПР, поскольку они позволяют легко учитывать технологическую специфику печатного монтажа со своей совокупностью конструктивных ограничений, Эти алгоритмы всегда гарантируют построение трассы, если путь для нее существует;
2) Ортогональные алгоритмы, обладающие большим быстродействием, чем алгоритмы первой группы. Реализация их на ЭВМ требует в 75-100 раз меньше вычислений по сравнению с волновыми алгоритмами. Такие алгоритмы применяют при проектировании печатных плат со сквозными металлизированными отверстиями. Недостатки этой группы алгоритмов связаны с получением большого числа переходов со слоя на слой, отсутствием 100%-ой гарантии проведения трасс, большим числом параллельно идущих проводников;
3) Алгоритмы эвристического типа. Эти алгоритмы частично основаны на эвристическом приеме поиска пути в лабиринте. При этом каждое соединение проводится по кратчайшему пути, обходя встречающиеся на пути препятствия.
Волновой алгоритм Ли
Данный алгоритм является классическим примером использования методов динамического программирования для решения задач трассировки печатных соединений. Основные принципы построения трасс с помощью динамического алгоритма сводятся к следующему.
Все ячейки монтажного поля подразделяют на занятые и свободные. Занятыми считаются ячейки, в которых уже расположены проводники, построенные на предыдущих шагах, или находятся монтажные выводы элементов, а также ячейки, соответствующие границе платы и запрещенным для прокладывания проводников участкам. Каждый раз при проведении новой трассы можно использовать лишь свободные ячейки, число которых по мере проведения трасс сокращается.
На множестве свободных ячеек коммутационного поля моделируют волну влияния из одной ячейки в другую, соединяемых впоследствии общим проводником. Первую ячейку, зарождается волна влияний, называют источником, а вторую – преемником волны. Чтобы иметь возможность следить за прохождением фронта волны влияний, его фрагментам на каждом этапе присваивают некоторые веса:
,
где Pk и Pk-1 - веса ячеек k-го и (k-1)-го фронтов; 
- весовая функция, являющаяся показателем качества проведения пути, каждый параметр которой 
характеризует путь с точки зрения одного из критериев качества (длины пути, числа пересечений и т.п.). На Pk накладывают одно ограничение – веса ячеек предыдущих фронтов не должны быть больше весов ячеек последующих фронтов. Фронт распространяется только на соседние ячейки, которые имеют с ячейками предыдущего фронта либо общую сторону, либо хотя бы одну общую точку. Процесс распространения волны продолжается до тех пор, пока её расширяющийся фронт не достигнет приемника или на Θ-ом шаге не найдется ни одной свободной ячейки, которая могла бы быть включена в очередной фронт, что соответствует случаю невозможности проведения трассы при заданных ограничениях.
Если в результате распространения волна достигла приемника, то осуществляют «проведение пути», которое заключается в движении от приемника к источнику про пройденным на этапе распространения волны ячейкам, следя за тем, чтобы значения Pk монотонно убывали. В результате получают путь, соединяющий эти две точки. Из описания алгоритма следует, что все условия, необходимые для проведения пути, закладываются в правила приписания веса ячейкам.
Реферат опубликован: 31/03/2010