Трассировка сигнальных цепей с помощью волновых алгоритмов

4. Трассировка сигнальных цепей с помощью волновых алгоритмов

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

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

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

 (10)

где  и - веса ячеек k – го и (k-1) –го фронтов;

φ – числовая характеристика, зависящая от выбранного критерия оптимизации;

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

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

Приведем два примера трассировки соединений с помощью волнового алгоритма ЛИ.

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

В приложении 5 представлена плата с проведенной трассировкой.

Литература

1.  Мельничук В.В. «Конспект лекций по АКИТ и ПРЭС» БГУИР Минск 2000г.

2.  Деньдобренько Б.Н. «Автоматизация конструирования РЭА» Москва 1980г.

3.  Методическое пособие к лабораторному практикуму по курсу «Математическое обеспечение конструкций и технологии проектирования с применением САПР» Минск 1987г.