Реферат: Алгоритмы трассировки - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

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

Банк рефератов / Технологии

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 267 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!

Узнайте стоимость написания уникальной работы

В ведение В настоящее время используются различные варианты волнового алгоритма, в частности, лучевой и маршрутные. Простейшим видом волнового алгоритма является волновой алг оритм нахождения кратчайшего пут и без пересечения множества занятых и запрещенных элементов (участко в печатной платы). Его целесообразно использовать при трассировке сое динений в одной плоскости, когда недопустимо выходить из пределов это й плоскости. Определяются начальная и конечная точки и моделируется распространение волны от конечной точки к начальной в направлении во лны. Недостатком этого алгоритма является то, что он мало пригоден для трассировки многослойных печатных плат, проводники прокладываются п о краям платы, значительное число длинных параллельных проводников я вляются причиной большой взаимоиндуктивности. Более совершенным волновым алгоритмом является волновой алго ритм прокладки пути с минимальным числом пересечения. В этом случае ч исло пересечений ранее проложенных трасс должно быть минимальным. Дл я преодоления недостатка этого алгоритма, при котором трассы стремят ся к одной из границ платы и прижимаются друг к другу, был предложен ал горитм для проведения пути, минимально приближающихся к другим трасс ам. Основой алгоритма является условие, при котором элементы данного соединения должны иметь минимум соседних элементов, принадлежащих ра нее проложенным трассам. Если одним из условий является требование регулярности соед инений (один слой горизонтальные, другой – вертикальные и т.п.), то удоб нее использовать волновой алгоритм прокладки пути с минимальным чис лом изменений направления, который позволяет минимизировать количес тво межслойных соединений. В отличие от волновых и лучевых алгоритмов, в которых на начальной ста дии перебираются все возможные варианты трассы, в маршрутных алгорит мах прокладка трассы ведется сразу и по кратчайшему маршруту. 1. Маршрутный алгоритм трассировки Каждый слой платы представлен в памяти ЭВМ булевой матрицей , элементы которой имеют значение 0, если соответствующий элемент своб оден для прокладки пути, и имеют значение 1, если соответствующий элеме нт занят. Все элементы матрицы, которые принадлежат исходным препятст виям, задаются единичным значением. Алгоритм реализует следующие последовательно выполняемые этапы: 1) построение пути до вст речи с препятствием; 2) обход препятствий; 3) минимизация построенн ого пути. Этап 1. Пусть требуется проложить путь между элементами d a , булевой матрицы, описывающей модель платы. При отсутствии пр епятствий между элементами можно проложить конечное множество путей , имеющих минимальную длину в выбранной геометрии. Процесс построения Р-пути (Н-пути) сводится к тому, чтобы определить такую последовательно сть элементов L =< d a , d a +1 ,…, d k ,…, d b > , что любой эле мент d k принадлежит Р-ок рестности (Н-окрестности) элемента d k -1 . Если будем рассматривать Н-окрестность, то вектор пер ехода Z k от элемента d k к элемент у d к+1 возможен только в направлениях, параллельных координ атным осям. Для случая Р-окрестности вектор перехода может иметь диаг ональные направления. На каждом шаге построения пути направление вектора перехода Z k от элемента d k к элементу d к+1 определяе тся функциями sgn ( x b - x k ), sgn ( y b - y k ), где x b , y b - координаты элемента d b пути, x k , y k - координаты э лемента d k . Правило выбора направления построения пути до встречи с препятствие м в наилучшем направлении приведено в таблице 1. Таблица 1. Фун кция Z k 0 1 2 3 4 5 6 7 sgn(x b -x k ) 1 1 0 -1 -1 -1 0 1 sgn(y b -y k ) 0 1 1 1 1 -1 -1 -1 Наим енование направлений приведено на рисунке 1. 3 2 1 4 A 0 5 6 7 Рису нок 1. Наименование направлений вектора перемещения Z k . После каждого шага построения пути необходимо по вектору перехода Z k оп ределить состояние очередного элемента d k (свободный или занятый) булево м атрицы. Рассмотрим построение Н-пути. Для описания дискретного пространства, в котором строим путь, использ уем булеву матрицу С размером m n . Кроме того, для сокращения вычислений введ ем усеченную матрицу А размером m l . Число строк в матрице А определяется ширин ой прокладываемого проводника в дискретах. При прокладке проводников шириной в один дискрет матрица А будет матрицой-строкой, только один элемент которой принимает единичное значение. Номер этого элемента о пределяется координатой x k анализируемого э лемента d k . Состояние элементов описывается через булеву функцию , где c i , j – элемент мат рицы С; a i - элемент матрицы-сторки А. Здесь через индекс j обозначается номер строки матрицы С, котор ый определяется координатой y k элемента d k . Если V =1 , то элемент d k занят, и построение пути прекращается . Дальнейшее построение осуществляется путем обхода препятствий, нач иная с элемента d k -1 , который будем называть элементом в стречи с препятствием. При построении Р-пути распознавание состояния элемента выполняется в два этапа. На первом этапе определяем, принадлежит ли элемент d k какому-либ о объекту, записанному в матрице С. Если элемент d k не принадлеж ит никакому объекту, то переходим к выполнению второго этапа, суть кот орого сводится к следующему: определяем состояние элементов, которые принадлежат одновременно Н-окрестностям элементов d k , d k -1 . Таких элементов может быть только два, причем они расположе ны диагонально. Если оба элемента заняты, то построение пути из элемен та d k -1 в d k запрещено. При построении пути в диагональных направлениях состояния элементов описывается булевой функцией , i = 1, 3, 5, 7. (1) Булевы функции V i , V i -1 , V i +1 определяются при просмотре Р-окрестности элемента d k . Если функция (1) равна нулю, то выбранный элемент свободный; в противном случае – зан ятый. Если очередной элемент d k булевой матрицы С, через который долже н пройти путь занят, то из элемента d k -1 , который назове м элементом встречи с препятствием (на рисунке 2 это элемент 1), начинает ся обход препятствия. Этап 2. Переход от элемента встречи с препятствием к следующему свободному элементу пути выполняются согл асно правилу первого шага. Правило первого шага. Этап обхода пр епятствия начинается с элемента d k встречи с препятствием в направлении Z k , двоичный код которого определяется путем сложения кода пред шествующего направления ( Z ’ ) k -1 с кодом 001 по модулю 8 при отрицательном н аправлении обхода препятствий, а при положительном обходе – с кодом 111. Если выбранное направление запрещено, то принимаем первое возможное направление. При построении пути выполняется отрицательный (правый) и положительн ый (левый) обход всей группы препятствий, лежащих между конечными элем ентами пути. В этом случае у первого элемента встречи с препятствием п уть разветвляется на два. По одному пути осуществляется обход препятс твий справа, а по другому – слева. При построении Н-пути для обхода препятствий используется алгоритм Н- слежения, а при построении Р-пути – Р-слежение. При отрицательном направлении Р-слежения двоичный код приоритетного направления опреднляется соотношением , а при положительном . Если направление с высшим приоритетом запрещено, то выбираетс я первое возможное направление с низшим приоритетом. Определяемое со отношением , где n – двоичный код чи сел из последовательности 1, 2, …,8. Суммирование по модулю 8 выполняется при отрицательном направлении с лежения, вычитание – при положительном. Важным моментом является определение элемента, в котором заканчивает ся обход препятствий и начинается построение пути в оптимальном напр авлении (по прямой к элементу d b ). Если в нужный мом ент не прекратить обход препятствий, то неизбежно зацикливание пути в округ препятствий. Элемент пути, в котором прекращается обход препятс твий, назовем элементом спуска. На рисунке 2 элементом спуска является элемент 19. Здесь приведен путь в лабиринте, построенный согласно этой методике от элемента d a к элементу d b . От элемента d a до элемента 1, который является элементом встречи, выполн яется построение пути согласно этапу 1. Обход препятствий начинается от элемента встречи 1 в отрицательном направлении (этап 2) и заканчивае тся элементом спуска 19. От элемента спуска 19 до конечного элемента пути выполняется этап 1. Для определения элемента спуска пути предлагается следующий алгорит м: a) определяем двоичный к од угла поворота вектора перехода относительно вектора Z ’ из соотношения ; причем суммирование выполняется при отри цательном направлении обхода препятствий, вычитание – при положител ьном. b) В каждом элементе излома проверяем значение двоичного кода a k и направление построения пути в наилучшем направлени и. Если a k 0 и направление обхода препятствий совпадает с наилучшим направ лением построения пути, то элемент d k будет элементом спуска. В противном случае d k не является элементом спуска. Этап 3. Минимизация длинны пути сводится к постро ению выпуклого контура, описанного вокруг первоначального пути. Если нет возможности получить выпуклый контур из-за наличия препятствий, т о строится сглаженный контур, т.е. контур, имеющий меньшую длину, чем пе рвоначальный. Находим все элементы спуска первоначального пути и разбиваем его на отдельные участки, разграниченные элементами спуска. Последовательн о минимизируем все участки пути. 1) Находим все элементы и злома соответствующего участка пути, и если имеется не более одного и злома, то он не подлежит минимизации если элементов излома два и более , то минимизация заключается в том, что строится новый путь L н ( d a , d j ) пути L ( d a , d j ), где d j - элемент излома пути, самый близкий к конечному элементу. 2) Построенный вновь подп уть L н ( d a , d j ) сравнивается по длине с путем L ( d a , d j ) , и если новый путь меньше, то L ( d a , d j ) заменяется на L н ( d a , d j ) . 3) Минимизация повторяет ся для следующего элемента излома, самого близкого к d j , и до тех пор, пока на L н ( d a , d j ) или L ( d a , d j ) останется один элемент излома. Осуществляется минимизация обоих первоначально построенных путей, полученных при положительном (левом) и отрицательном (правом) об ходе группы препятствий, из которых выбирается минимальный (рисунок 3). 2. Волновой алгоритм трассировки. Дискретное поле платы разбивают на три множества, описываемых с помощью булевых матриц: С – множество элементов поля, требующих соединения между собой (на ри сунке 4 множество , где i = 0, 1, 2, 3); Р – множество элементов поля, запрещенных для трассировки (на рисунке 4,а(б) это множество закрашено черным); S – множество своб одных элементов поля платы. Требуется, используя элементы множества S , соединить элементы множества С в одну цепь, не пересекающую Р. Процесс нахождения минимального пути состоит из двух этапов: - Распространение волны от источника до встречи с одним из приемников; - Определение пути от источ ника к приемнику. В качестве источника в ыбирается один из элементов множества С, все остальные элементы являю тся приемниками. Обозначим через R k множество элементов вол ны на шаге k и назовем его k - фронтом волны, тогда R k +1 принадлежит Н-окрестности R k . На каждом шаге расширения делается проверка пересечения фонта волны с приемником. Как только какой-либо элемент приемника буд ет включен в волну, процесс распространения волны завершается, и от бл ижайшего к источнику элемента приемника начинается построение пути. Для построения волны используются матрицы распространения волн в го ризонтальном ( R k ’ ) , и вертикальном ( R k ) направлении и матрицы точек поворота с вертикального направления на горизонтальное ( M k ) и с горизонтального направления на вертикальное ( M k ’ ), где ; ; . На рисунке 5, а - г приведе ны соответственно матрицы R k , R k ’ , M k , M k ’ , построенные для k =12 . Источником является фрагмент С 0 . Для нагля дности в клетках, занятых волной, указывается номер шага, на котором до стигнута эта точка. На этапе построения пути определяется, каким фронтом достигнут прием ник: горизонтальным или вертикальным. От элемента пересечения волны с приемником в направлении, соответствующему последнему фронту волны, определяем элементы, не принадлежащие множеству Р. При встрече с перв ым же элементом множества точек поворота рассмотренного направления движение прекращается. Все пройденные элементы включаются в искомый путь. Элемент встречи принимается за исходный для движения по другому фронту волны. Направление чередуется таким образом до тех пор, пока не будет достиг нут элемент источника. На рисунке 5, д показан пример построения пути от приемника С 1 к источнику С 0 . Стрелкам и показано направление движения. В дальнейшем процесс распространени я волны повторяется с учетом построенного пути. Такой выбор источника обеспечивает ветвление цепи в любой ее точке. Процесс заканчивается, когда все элементы С будут связаны в единую це пь (рисунок 5, е), либо когда оставшиеся элементы этого множества уже не могут быть присоединены к источнику.

1Авиация и космонавтика
2Архитектура и строительство
3Астрономия
 
4Безопасность жизнедеятельности
5Биология
 
6Военная кафедра, гражданская оборона
 
7География, экономическая география
8Геология и геодезия
9Государственное регулирование и налоги
 
10Естествознание
 
11Журналистика
 
12Законодательство и право
13Адвокатура
14Административное право
15Арбитражное процессуальное право
16Банковское право
17Государство и право
18Гражданское право и процесс
19Жилищное право
20Законодательство зарубежных стран
21Земельное право
22Конституционное право
23Конституционное право зарубежных стран
24Международное право
25Муниципальное право
26Налоговое право
27Римское право
28Семейное право
29Таможенное право
30Трудовое право
31Уголовное право и процесс
32Финансовое право
33Хозяйственное право
34Экологическое право
35Юриспруденция
36Иностранные языки
37Информатика, информационные технологии
38Базы данных
39Компьютерные сети
40Программирование
41Искусство и культура
42Краеведение
43Культурология
44Музыка
45История
46Биографии
47Историческая личность
 
48Литература
 
49Маркетинг и реклама
50Математика
51Медицина и здоровье
52Менеджмент
53Антикризисное управление
54Делопроизводство и документооборот
55Логистика
 
56Педагогика
57Политология
58Правоохранительные органы
59Криминалистика и криминология
60Прочее
61Психология
62Юридическая психология
 
63Радиоэлектроника
64Религия
 
65Сельское хозяйство и землепользование
66Социология
67Страхование
 
68Технологии
69Материаловедение
70Машиностроение
71Металлургия
72Транспорт
73Туризм
 
74Физика
75Физкультура и спорт
76Философия
 
77Химия
 
78Экология, охрана природы
79Экономика и финансы
80Анализ хозяйственной деятельности
81Банковское дело и кредитование
82Биржевое дело
83Бухгалтерский учет и аудит
84История экономических учений
85Международные отношения
86Предпринимательство, бизнес, микроэкономика
87Финансы
88Ценные бумаги и фондовый рынок
89Экономика предприятия
90Экономико-математическое моделирование
91Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Они пока в айфоне штопор не сделают, покупать не буду. А то что это за техника такая?! 70 тыщ отдай, и даже штопора нет.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2017
Рейтинг@Mail.ru