2. Вычисление координат множества элементов {Фк}- Для множества {Фу} это будут элементы с координатами (Ха+ь Уа),

(Ха-Ь а), (Л:а, «/a+l), (Ла, «/а-О- ДлЯ МНОЖССТВ {Фн} ЭЛСМеНТЫ

определяются согласно рассмотренному ранее правилу. Отметим, что для принятой геометрии пространства координаты двух соседних элементов отличаются на ±1 по одной из координат.

3. Проверка условия {Fk}¥=0. В процессе этой проверки выясняется, входит ли в множество элементов /С-фронта хотя бы один свободный элемент. Если все элементы заняты или запрещены, то распространение волны прекращается и трасса АВ заносится в список непроведенных.

15 П 13 12 11 10 9 8 7 6 5

/ 2 л 4 5 Б 7 8 9 ID 11 12 13 П 15 1Б 17.18 19 20

Рис. 1.18, Пример выполнения трассировки печатного монтажа с помощью волнового алгоритма

4. Присвоение путевых координат элементам {Fj. Эта процедура необходима для определения наикратчайшего пути от элемента /С-фронта к исходному элементу А.

Путевой координатой элемента /С-фронта называется номер одного из соседних ему элементов (/С-1)-фронта, выбранный по Одному из приоритетных порядков.

На рис. 1.18 приведен пример выполнения трассировки с помощью описываемого алгоритма. Заштрихованными областями показаны занятые (запрещенные) элементы. Полученное соединение АВ обозначено очерченной контуром областью. В примере в Качестве приоритетного принят порядок: верхний, левый, нижний, правый элемент (/С-1)-фронта. Это означает, "что для некоторого элемента /С-фронта путевой координатой является номер соседнего элемента (./С1)-фронта, имеющего ту же -абсциссу, а

ординату на 1 больше. Е&пи такой элемент в составе (/С-1)-фронта отсутствует, то нрисваивается номер элемента, имеющего ту же ординату, а абсциссу на 1 меньше. При отсутствии и такого элемента, путевая координата определяется по номеру элемента (К-1)-фронта с той же абсциссой, а ординатой на 1 меньше м т. д.

На рис. 1.18 путевые координаты каждого элемента, попавшего во фронты распространения волны, обозначены стрелками, показывающими на тот элемент, номер которого служит путевой координатой. . •

5. Проверка условия: Бе{/к}- Определяется: достиг ли фронт распространения волны элемента В. Если нет, то создается (/(-1-1) =фронт; если условие выполняется, то этап моделирования волны оканчивается, трасса АВ может быть построена. На рис. 1.18 фронт достиг элемента Б на 17 шаге распространения волны.

6. Запись координат трассы АВ. Выполняется, начиная с конечного элемента В.

По путевой координате элемента В находят координаты со-ответатвующего элемента предыдущего фронта; затем по путевой координате этого элемента находят координаты последующего элемента и т. д.

Полученный путь является кратчайшим в выбранной геомет--рии. На рис. 1.18 длина трассы АВ.

С?ЛВ = ка-в1 + г/а-г/в 1=17.

Если бы между элементами Л и Б находилось препятствие (некоторое множество занятых или запрещенных элементов), то алгоритм провел бы трассу по пути кратчайшего обхода. Рассмотренный алгоритм Является наиболее простым в реализации модификацией волнового алгоритма, но обладает рядом недо,-етатков:

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

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

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

а) создание случайного приоритета, т. е. из нескольких приоритетных порядков для каждой трассы случайным образом выбирается один. Недостаток этого способа - усложнение алгоритма;

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

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

в) применение модификации волнового алгоритма для проведения пути, минимально приближающегося к другим проводникам. Этот алгоритм будет рассмотрен.

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

В основу алгоритма положен следующий критерий качества: число пересечений ранее проложенных трасс должно быть ми-мимальным.

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

Структурная схема алгоритма приведена на рис. 1.19.

1. Ввод данных. В оперативное запоминающее устройство вводятся координаты исходного и конечного элементов трассы

.1 -а. УА и \х, yj.

2. Вычисление координат множества элементов {Фк}- Эта операция выполняется так же, как и в предыдущем алгоритме.

3. Проверка выполнения условия {Fk}0. Если в состав "Элементов /С-фронта входят незанятые элементы, то распространение волны осуществляется так же, как и в предыдущем алгоритме. В случае, когда множество незанятых элементов /С-фрон-1"а равно нулю, т. е. когда дальнейшее распространение волны оез пересечения ранее шроложенных траос невозможно, делается Переход к выполнению блока 4.