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

Реферат

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

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

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

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Microsoft Word, 267 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

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

В ведение В настоящее время используются различные варианты волнового алгоритма, в частности, лучевой и маршрутные. Простейшим видом волнового алгоритма является волновой алг оритм нахождения кратчайшего пут и без пересечения множества занятых и запрещенных элементов (участко в печатной платы). Его целесообразно использовать при трассировке сое динений в одной плоскости, когда недопустимо выходить из пределов это й плоскости. Определяются начальная и конечная точки и моделируется распространение волны от конечной точки к начальной в направлении во лны. Недостатком этого алгоритма является то, что он мало пригоден для трассировки многослойных печатных плат, проводники прокладываются п о краям платы, значительное число длинных параллельных проводников я вляются причиной большой взаимоиндуктивности. Более совершенным волновым алгоритмом является волновой алго ритм прокладки пути с минимальным числом пересечения. В этом случае ч исло пересечений ранее проложенных трасс должно быть минимальным. Дл я преодоления недостатка этого алгоритма, при котором трассы стремят ся к одной из границ платы и прижимаются друг к другу, был предложен ал горитм для проведения пути, минимально приближающихся к другим трасс ам. Основой алгоритма является условие, при котором элементы данного соединения должны иметь минимум соседних элементов, принадлежащих ра нее проложенным трассам. Если одним из условий является требование регулярности соед инений (один слой горизонтальные, другой – вертикальные и т.п.), то удоб нее использовать волновой алгоритм прокладки пути с минимальным чис лом изменений направления, который позволяет минимизировать количес тво межслойных соединений. В отличие от волновых и лучевых алгоритмов, в которых на начальной ста дии перебираются все возможные варианты трассы, в маршрутных алгорит мах прокладка трассы ведется сразу и по кратчайшему маршруту. 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Экономическая теория

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

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

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