Предыдущая страница реферата | 1  2  3  4  5  6

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

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

Оценим число ячеек, просматриваемых на этапе распространения волны, при использовании в качестве источников одной или двух объединяемых точек.
Пусть расстояние между этими точками R. Тогда для первого случая в момент достижения волной ячейки-приемника площадь просмотренной окрестности имеет величину [pic] (знак равенства соответствует отсутствию преград пути распространения волны). Для второго случая в момент встречи фронтов двух волн площадь просмотренной окрестности [pic].

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

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

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

В данном алгоритме, предложенным Л.Б. Абрайтисом, выбор ячеек для определения пути между соединяемыми точками A и B производят по заранее заданным направлениям, подобным лучам. Это позволяет сократить число просматриваемых алгоритмом ячеек, а следовательно, и время на анализ и кодировку их состояния, однако приводит к снижению вероятности нахождения пути сложной конфигурации, и усложняет учет конструктивных требований к технологии печатной платы.

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

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

[pic]

Лучи:
A(1): вверх, влево
A(2): влево, вверх
B(1): вниз, вправо
B(2): вправо, вниз
На втором шаге луч B(1) оказывается заблокированным, а на четвертом шаге блокируется и луч A(2). Лучи A(1) и B(2) встречаются в ячейке C на восьмом шаге.

Обычно с помощью лучевого алгоритма удается построить до 70-80% трасс, остальные проводят, используя волновой алгоритм или вручную. Его применение особенно выгодно при проектировании плат с невысокой плотностью монтажа.

ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА

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

Москва «Высшая школа» 1980.

2. В.М. Курейчик «Математическое обеспечение конструкторского и технологического проектирования с применением САПР»,

Москва «Радио и связь» 1990.

3. К.К. Морзов, В.Г. Одиноков, В.М. Курейчик «Автоматизированное проектирование конструкций радиоэлектронной аппаратуры», Москва «Радио и связь» 1983.

4. В.Н. Ильин, В.Т. Фролкин, А.И. Бутко и др.; «Автоматизация схемотехнического проектирования: Учебное пособие для вузов», Москва

«Радио и связь» 1987.

Скачали данный реферат: Дмитрий, Кушкин, Vidina, Salomeja, Gorislava, Эфиров, Милослава, Белоцерковский.
Последние просмотренные рефераты на тему: реферат на тему время, загадки с ответами, шпаргалки по менеджменту, мини сочинение.



Предыдущая страница реферата | 1  2  3  4  5  6

Поделитесь этой записью или добавьте в закладки