Алгоритмы трассировки

| Категория реферата: Рефераты по радиоэлектронике
| Теги реферата: акт, диплом
| Добавил(а) на сайт: Werbina.

Рисунок 1. Наименование направлений вектора перемещения Zk.

После каждого шага построения пути необходимо по вектору перехода Zk определить состояние очередного элемента dk (свободный или занятый) булево матрицы. Рассмотрим построение Н-пути.

Для описания дискретного пространства, в котором строим путь, используем булеву матрицу С размером m(n. Кроме того, для сокращения вычислений введем усеченную матрицу А размером m(l.
Число строк в матрице А определяется шириной прокладываемого проводника в дискретах. При прокладке проводников шириной в один дискрет матрица А будет матрицой-строкой, только один элемент которой принимает единичное значение. Номер этого элемента определяется координатой xk анализируемого элемента dk.

Состояние элементов описывается через булеву функцию

[pic], где ci,j – элемент матрицы С; ai - элемент матрицы-сторки А.

Здесь через индекс j обозначается номер строки матрицы С, который определяется координатой yk элемента dk.

Если V=1, то элемент dk занят, и построение пути прекращается.
Дальнейшее построение осуществляется путем обхода препятствий, начиная с элемента dk-1, который будем называть элементом встречи с препятствием.

При построении Р-пути распознавание состояния элемента выполняется в два этапа. На первом этапе определяем, принадлежит ли элемент dk какому-либо объекту, записанному в матрице С. Если элемент dk не принадлежит никакому объекту, то переходим к выполнению второго этапа, суть которого сводится к следующему: определяем состояние элементов, которые принадлежат одновременно Н- окрестностям элементов dk, dk-1. Таких элементов может быть только два, причем они расположены диагонально. Если оба элемента заняты, то построение пути из элемента dk-1 в dk запрещено.

При построении пути в диагональных направлениях состояния элементов описывается булевой функцией

[pic], i=1, 3, 5, 7. (1)

Булевы функции Vi, Vi-1, Vi+1 определяются при просмотре

Р-окрестности элемента dk. Если функция (1) равна нулю, то выбранный элемент свободный; в противном случае – занятый.

Если очередной элемент dk булевой матрицы С, через который должен пройти путь занят, то из элемента dk-1, который назовем элементом встречи с препятствием (на рисунке 2 это элемент 1), начинается обход препятствия.

Этап 2. Переход от элемента встречи с препятствием к следующему свободному элементу пути выполняются согласно правилу первого шага.

Правило первого шага. Этап обхода препятствия начинается с элемента dk встречи с препятствием в направлении Zk, двоичный код которого определяется путем сложения кода предшествующего направления
(Z’)k-1 с кодом 001 по модулю 8 при отрицательном направлении обхода препятствий, а при положительном обходе – с кодом 111.

Если выбранное направление запрещено, то принимаем первое возможное направление.

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

При построении Н-пути для обхода препятствий используется алгоритм Н-слежения, а при построении Р-пути – Р-слежение.

При отрицательном направлении Р-слежения двоичный код приоритетного направления опреднляется соотношением

[pic],

а при положительном

[pic].

Если направление с высшим приоритетом запрещено, то выбирается первое возможное направление с низшим приоритетом. Определяемое соотношением

[pic], где n – двоичный код чисел из последовательности 1, 2, …,8.

Суммирование по модулю 8 выполняется при отрицательном направлении слежения, вычитание – при положительном.