Алгоритмы трассировки
РЕФЕРАТна тему: "Алгоритмы трассировки "ВведениеВ настоящее время используются различные варианты волнового алгоритма, в частности, лучевой и маршрутные.Простейшим видом волнового алгоритма является волновой алгоритм нахождения кратчайшего пути без пересечения множества занятых и запрещенных элементов (участков печатной платы). Его целесообразно использовать при трассировке соединений в одной плоскости, когда недопустимо выходить из пределов этой плоскости. Определяются начальная и конечная точки и моделируется распространение волны от конечной точки к начальной в направлении волны. Недостатком этого алгоритма является то, что он мало пригоден для трассировки многослойных печатных плат, проводники прокладываются по краям платы, значительное число длинных параллельных проводников являются причиной большой взаимоиндуктивности. Более совершенным волновым алгоритмом является волновой алгоритм прокладки пути с минимальным числом пересечения. В этом случае число пересечений ранее проложенных трасс должно быть минимальным. Для преодоления недостатка этого алгоритма, при котором трассы стремятся к одной из границ платы и прижимаются друг к другу, был предложен алгоритм для проведения пути, минимально приближающихся к другим трассам. Основой алгоритма является условие, при котором элементы данного соединения должны иметь минимум соседних элементов, принадлежащих ранее проложенным трассам. Если одним из условий является требование регулярности соединений (один слой горизонтальные, другой – вертикальные и т.п.), то удобнее использовать волновой алгоритм прокладки пути с минимальным числом изменений направления, который позволяет минимизировать количество межслойных соединений.В отличие от волновых и лучевых алгоритмов, в которых на начальной стадии перебираются все возможные варианты трассы, в маршрутных алгоритмах прокладка трассы ведется сразу и по кратчайшему маршруту.Маршрутный алгоритм трассировки Каждый слой платы представлен в памяти ЭВМ булевой матрицей, элементы которой имеют значение 0, если соответствующий элемент свободен для прокладки пути, и имеют значение 1, если соответствующий элемент занят. Все элементы матрицы, которые принадлежат исходным препятствиям, задаются единичным значением.Алгоритм реализует следующие последовательно выполняемые этапы:построение пути до встречи с препятствием; обход препятствий; минимизация построенного пути. Этап 1. Пусть требуется проложить путь между элементами da, булевой матрицы, описывающей модель платы. При отсутствии препятствий между элементами можно проложить конечное множество путей, имеющих минимальную длину в выбранной геометрии. Процесс построения Р-пути (Н-пути) сводится к тому, чтобы определить такую последовательность элементов L=<da, da+1,…, dk,…, db>, что любой элемент dk принадлежит Р-окрестности (Н-окрестности) элемента dk-1.Если будем рассматривать Н-окрестность, то вектор перехода Zk от элемента dk к элементу dк+1 возможен только в направлениях, параллельных координатным осям. Для случая Р-окрестности вектор перехода может иметь диагональные направления.На каждом шаге построения пути направление вектора перехода Zk от элемента dk к элементу dк+1 определяется функциями sgn(xb-xk), sgn(yb-yk), где xb, yb - координаты элемента db пути, xk, yk - координаты элемента dk. Правило выбора направления построения пути до встречи с препятствием в наилучшем направлении приведено в таблице 1.Таблица 1.Наименование направлений приведено на рисунке 1.Рисунок 1. Наименование направлений вектора перемещения Zk.После каждого шага построения пути необходимо по вектору перехода Zk определить состояние очередного элемента dk (свободный или занятый) булево матрицы. Рассмотрим построение Н-пути.Для описания дискретного пространства, в котором строим путь, используем булеву матрицу С размером mn. Кроме того, для сокращения вычислений введем усеченную матрицу А размером ml. Число строк в матрице А определяется шириной прокладываемого проводника в дискретах. При прокладке проводников шириной в один дискрет матрица А будет матрицой-строкой, только один элемент которой принимает единичное значение. Номер этого элемента определяется координатой xk анализируемого элемента dk. Состояние элементов описывается через булеву функцию,где ci,j – элемент матрицы С; ai - элемент матрицы-сторки А. Здесь через индекс j обозначается номер строки матрицы С, который определяется координатой yk элемента dk.Если V=1, то элемент
Другие файлы:
Реализация алгоритма обратной трассировки лучей для моделей с большим числом полигонов
Алгоритмы получения реалистических изображений. Применение алгоритма обратной трассировки лучей, ее математическая основа. Составление матрицы и прогр...
Засоби векторної трасировки растрових зображень в Corel Drow
Поняття трассировки та її значення в роботі комп'ютерного дизайнера. Розвиток інструментів трассировки в програмі Corel Drow. Способи та процеси векто...
Генетический алгоритм глобальной трассировки
Основной целью задачи глобальной трассировки является равномерное и целесообразное распределение ресурсов коммутационного поля для создания благоприят...
Алгоритм Краскала трассировки проводного монтажа
Создание программы, выполняющей трассировку проводного монтажа алгоритмом Краскала. Конфигурация программы для работы под управлением операционных сис...
Отрисовка сцены "Отражающиеся дорожки" алгоритмом обратной трассировки лучей
Разработка и практическая апробация программы для соответствия поставленным требованиям: реализация трассировки лучей с просчетом теней, освещения, от...
