Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Алгоритмы и модели трассировки проводных соединений в ЭА

Содержание

Лекция 7 АЛГОРИТМЫ И МОДЕЛИ ТРАССИРОВКИ ПРОВОДНЫХ СОЕДИНЕНИЙ В ЭА1 Классификация алгоритмов трассировки2 Формулировка задачи трассировки проводных соединений3 Алгоритм Краскала (Вайнберга – Лобермана)4 Алгоритм Прима5 Особенности трассировки проводов в каналах
Информационные технологии автоматизированного проектирования  Часть 1Лекция 7 Лекция 7  АЛГОРИТМЫ И МОДЕЛИ ТРАССИРОВКИ ПРОВОДНЫХ СОЕДИНЕНИЙ В ЭА1 Классификация Вопрос 1 Классификация алгоритмов трассировки Вопрос 2 Формулировка задачи трассировки проводных соединений Исходная информация для решения задач трассировки соединений1)	список цепей2)	параметры конструктивных элементов3)	параметры монтажного поля4)	данные 1)	Соединения должны соответствовать принципиальной схеме и быть кратчайшими;2)	Число пересечений трасс в монтажном Достоинства:-	простота выполнения-	высокая помехоустойчивость-	позволяет до минимума сократить общую длину проводников, в т.ч. протяженность 2.2 Трассировка проводных соединений с помощью жгутов (ленточных кабелей)Достоинства :1.	 более технологичен, В некоторой системе координат XYZ, связанной с коммутационным пространством модуля, задано местоположение Вопрос 3 Алгоритм Краскала АлгоритмВсе известные алгоритмы построения кратчайших связывающих сетей (КСС) основаны на последовательном выборе Алгоритм4.	Для построения дерева необходимо выбрать n-1 ребер из кортежа, которые не образуют АлгоритмВариант 2 (последовательный).На каждом шаге просматривают список ребер (начиная с первого) и Вопрос 4 Алгоритм Прима АлгоритмПозволяет организовать просмотр только тех ребер графа Gn(M, U), которые связывают вершины Шаги алгоритма2) На каждом последующем шаге к строящемуся поддереву присоединяют очередное ребро Детализация алгоритма1) составляем матрицу длин, общий элемент которой dij равен расстоянию между Детализация алгоритма3) Просматриваем первую и g-ю строки матрицы с оставшимися элементами. Из Детализация алгоритмаВыполнение ограничения на локальную степень вершин обеспечивается проверкой в каждой просматриваемой Пример использования алгоритма ПримаНа плоскости в декартовой системе координат задано местоположение девяти Пример использования алгоритма ПримаРешение. Составляем матрицу длин: Пример использования алгоритма Прима1) Просматриваем 1-ю строку матрицы и выбираем элемент d13, Пример использования алгоритма Прима4) Просматриваем 1-ю, 3-ю и 5-ю строки. Выбираем элемент Пример использования алгоритма ПримаСуммарная длина ребер построенного дерева равна  D = Вопрос 5 Особенности трассировки проводов в каналах В ЭА используется жгутовой монтаж (шлейфами), при котором проводники укладывают в нормализованные множество узлов A :A1 - подмножество узлов, соответствующих электрическим контактам модулей и Полный поток из AS в АTВ реальных конструкциях пропускные способности каналов ограничены, Вопросы по прочитанному материалу? Спасибо за внимание!
Слайды презентации

Слайд 2 Лекция 7 АЛГОРИТМЫ И МОДЕЛИ ТРАССИРОВКИ ПРОВОДНЫХ СОЕДИНЕНИЙ

Лекция 7 АЛГОРИТМЫ И МОДЕЛИ ТРАССИРОВКИ ПРОВОДНЫХ СОЕДИНЕНИЙ В ЭА1 Классификация

В ЭА
1 Классификация алгоритмов трассировки
2 Формулировка задачи трассировки проводных

соединений
3 Алгоритм Краскала (Вайнберга – Лобермана)
4 Алгоритм Прима
5 Особенности трассировки проводов в каналах



Слайд 3 Вопрос 1 Классификация алгоритмов трассировки

Вопрос 1 Классификация алгоритмов трассировки

Слайд 6 Вопрос 2 Формулировка задачи трассировки проводных соединений

Вопрос 2 Формулировка задачи трассировки проводных соединений

Слайд 7 Исходная информация для решения задач трассировки соединений
1) список цепей
2) параметры

Исходная информация для решения задач трассировки соединений1)	список цепей2)	параметры конструктивных элементов3)	параметры монтажного

конструктивных элементов
3) параметры монтажного поля
4) данные по размещению конструктивных элементов
5) координаты выводов

элемента

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

Слайд 8 1) Соединения должны соответствовать принципиальной схеме и быть кратчайшими;
2) Число

1)	Соединения должны соответствовать принципиальной схеме и быть кратчайшими;2)	Число пересечений трасс в

пересечений трасс в монтажном поле должно быть минимальным для

МПП, либо не допускается
3) Распределение цепей в монтажном поле должно приближаться к равномерному;
4) Минимум числа непроведенных соединений;
5) Минимальная протяженность параллельных участков соседних проводников;
6) Минимум числа изгибов проводников;
7) Минимум числа слоев металлизации и числа переходов из слоя в слой.

Требования к трассировке соединений


Слайд 9 Достоинства:
- простота выполнения
- высокая помехоустойчивость
- позволяет до минимума сократить общую длину

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

проводников, в т.ч. протяженность параллельных
- уровень паразитных наводок и время

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

2.1 Трассировка проводных соединений по прямым, соединяющим отдельные выводы модулей (монтаж внавал)


Слайд 10 2.2 Трассировка проводных соединений с помощью жгутов (ленточных

2.2 Трассировка проводных соединений с помощью жгутов (ленточных кабелей)Достоинства :1.	 более

кабелей)
Достоинства :
1. более технологичен, так как позволяет разделить операции

подготовки и монтажа жгутов,
2. проще процесс контроля и устранения ошибок, допущенных при монтаже

Недостатки :
практически неприемлем для создания высокочастотной и чувствительной к электрическим помехам аппаратуры

1. Получение списка соединений
2. Построение кратчайших связывающих деревьев (сетей)
3. Выполнение трассировки проводов в каналах


Слайд 11 В некоторой системе координат XYZ, связанной с коммутационным

В некоторой системе координат XYZ, связанной с коммутационным пространством модуля, задано

пространством модуля, задано местоположение множества выводов
М = {m1,

m2,..., mn}.
В соответствии с электрической схемой соединений разобьем множество М на непересекающиеся подмножества М(1), М(2),..., М(Р), каждое из которых включает в себя выводы, подлежащие электрическому объединению.
Для каждого подмножества требуется определить последовательность соединения выводов и конфигурацию проводников, обеспечивающих при заданных ограничениях минимальную суммарную длину соединений (возможен учет назначения цепей)

Формулировка задачи трассировки проводных соединений


Слайд 12 Вопрос 3 Алгоритм Краскала

Вопрос 3 Алгоритм Краскала      (Вайнберга – Лобермана)

(Вайнберга – Лобермана)


Слайд 13 Алгоритм
Все известные алгоритмы построения кратчайших связывающих сетей (КСС)

АлгоритмВсе известные алгоритмы построения кратчайших связывающих сетей (КСС) основаны на последовательном

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

циклов с ранее отобранными.
Пусть в некоторой системе координат XYZ задано местоположение множества точек.
М = {m1, m2,..., mn}.
1. Строим на множестве М полный граф Gn(M, U).
2. Вычисляем длину всех ребер графа Gn(M, U)
3. Упорядочиваем список ребер с точки зрения их длины так, чтобы выполнялось условие

- построения кортежа с возрастанием длины каждого очередного ребра.


Слайд 14 Алгоритм
4. Для построения дерева необходимо выбрать n-1 ребер из

Алгоритм4.	Для построения дерева необходимо выбрать n-1 ребер из кортежа, которые не

кортежа, которые не образуют циклов.

Существуют 2 процедуры для решения

п. 4

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

Недостатки алгоритма:
- необходимость наблюдения за различными компонентами связности,
- проверки при выборе каждого очередного ребра условия необразования цикла для всех параллельно строящихся поддеревьев.


Слайд 15 Алгоритм
Вариант 2 (последовательный).
На каждом шаге просматривают список ребер

АлгоритмВариант 2 (последовательный).На каждом шаге просматривают список ребер (начиная с первого)

(начиная с первого) и к строящемуся поддереву присоединяют то

ребро, которое:
а) еще не включено в решение;
б) присоединяет к поддереву новую вершину (один из концов ребра должен принадлежать вершине поддерева, другой —изолированной вершине)

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


Слайд 16 Вопрос 4 Алгоритм Прима

Вопрос 4 Алгоритм Прима

Слайд 17 Алгоритм
Позволяет организовать просмотр только тех ребер графа Gn(M,

АлгоритмПозволяет организовать просмотр только тех ребер графа Gn(M, U), которые связывают

U), которые связывают вершины строящегося поддерева с новыми, еще

не присоединенными вершинами.
Возможно дополнительное ограничение на локальные степени вершин связывающей сети:

Шаги алгоритма:
1) любая произвольная вершина m € M соединяется с ближайшей соседней, образуя исходное поддерево.
Для определенности построения КСС можно начинать с ребра, инцидентного вершине m1.


Слайд 18 Шаги алгоритма
2) На каждом последующем шаге к строящемуся

Шаги алгоритма2) На каждом последующем шаге к строящемуся поддереву присоединяют очередное

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

еще не присоединенную вершину mj с одной из вершин поддерева mi , локальная степень которой

- длина ребра, соединяющего вершины


Слайд 19 Детализация алгоритма
1) составляем матрицу длин, общий элемент которой

Детализация алгоритма1) составляем матрицу длин, общий элемент которой dij равен расстоянию

dij равен расстоянию между i-й и j-й точками (N

- число объединяемых вершин):

2) Просматриваем элементы первой строки матрицы D и находим минимальный из них. Пусть таким элементом оказался элемент g-гo столбца, тогда весь первый и g-й столбцы матрицы D исключаем из рассмотрения, а первое соединение проводим между точками m1 и mg.


Слайд 20 Детализация алгоритма
3) Просматриваем первую и g-ю строки матрицы

Детализация алгоритма3) Просматриваем первую и g-ю строки матрицы с оставшимися элементами.

с оставшимися элементами. Из элементов этих строк находим минимальный.

Предположим, что им оказался элемент, принадлежащий k-му столбцу. Если этот элемент находится на пересечении с первой строкой, то точку mk соединяем с mi, если же он находится на пересечении c g-й строкой, то точку mk соединяем с mg, после чего из матрицы D исключаем все элементы k-го столбца.
4) Просматриваем первую, g-ю и k-ю строки и т.д.


Слайд 21 Детализация алгоритма
Выполнение ограничения на локальную степень вершин обеспечивается

Детализация алгоритмаВыполнение ограничения на локальную степень вершин обеспечивается проверкой в каждой

проверкой в каждой просматриваемой i-й строке числа уже выбранных

для построения КСС элементов K(i). При K(i) = k все оставшиеся элементы i-й строки исключаются из рассмотрения.


Слайд 22 Пример использования алгоритма Прима
На плоскости в декартовой системе

Пример использования алгоритма ПримаНа плоскости в декартовой системе координат задано местоположение

координат задано местоположение девяти точек (рисунок). Расстояние между любыми

двумя точками mi и mj равно

Требуется для заданного множества точек М определить минимальное связывающее дерево при условии:


Слайд 23 Пример использования алгоритма Прима
Решение.
Составляем матрицу длин:

Пример использования алгоритма ПримаРешение. Составляем матрицу длин:

Слайд 24 Пример использования алгоритма Прима
1) Просматриваем 1-ю строку матрицы

Пример использования алгоритма Прима1) Просматриваем 1-ю строку матрицы и выбираем элемент

и выбираем элемент d13, являющийся минимальным в этой строке.


2) Помечаем элемент d13; К(1) = К(3) = 1.

Исключаем из рассмотрения все элементы 1-го и 3-го столбцов.
3) Просматриваем 1-ю и 3-ю строки. Выбираем элемент d35; К[3] = 2, К[5] = 1. Исключаем из рассмотрения элементы 5-го столбца.


Слайд 25 Пример использования алгоритма Прима
4) Просматриваем 1-ю, 3-ю и

Пример использования алгоритма Прима4) Просматриваем 1-ю, 3-ю и 5-ю строки. Выбираем

5-ю строки. Выбираем элемент d54; К(5) = 2, К(4)

= 1. Исключаем из рассмотрения элементы 4-го столбца.

5) Просматриваем 1-ю, 3-ю, 4-ю и 5-ю строки. Выбираем элемент d57; К(5) = 3, К(7) = 1. Так как К[5] = k, то исключаем из рассмотрения элементы 7-го столбца и 5-й строки.
6) Продолжая процесс построения КСС аналогичным образом, выбираем элементы d42, d26, d69, d98.



Слайд 26 Пример использования алгоритма Прима
Суммарная длина ребер построенного дерева

Пример использования алгоритма ПримаСуммарная длина ребер построенного дерева равна D =

равна D = 40.
Если локальная степень вершин не должна

превышать двух, то в результате решения будут выбраны элементы d13, d35, d54, d42, d26, d69, d98, d17. Суммарная длина ребер при этом равна 42.

Алгоритм Прима находит широкое применение в САПР проводных соединений ЭА.
Например, пакет E3


Слайд 27 Вопрос 5 Особенности трассировки проводов в каналах

Вопрос 5 Особенности трассировки проводов в каналах

Слайд 28 В ЭА используется жгутовой монтаж (шлейфами), при котором

В ЭА используется жгутовой монтаж (шлейфами), при котором проводники укладывают в

проводники укладывают в нормализованные каналы, расположенные в монтажном пространстве

во взаимно перпендикулярных направлениях.
Такую канальную конструкцию можно представить в виде ортогональной несимметрической сети G (A, В) со множеством узлов A и множеством дуг В.
Величина сij - пропускная способность дуги bij - максимальное число проводников, которое можно укладывать в соответствующем канале, интерпретируемом дугой bij.

где xij - дуговой поток или поток по дуге bij, равный числу проводников в канале, соединяющем точки i и j

(1)


Слайд 29 множество узлов A :
A1 - подмножество узлов, соответствующих

множество узлов A :A1 - подмножество узлов, соответствующих электрическим контактам модулей

электрическим контактам модулей и разъемов схемы;
А2 - подмножество

узлов, в которых допускается изменение направления прокладывания проводников (точки пересечения вертикальных и горизонтальных каналов).
A1: As - источники и Аt - стоки, определяющие, соответственно, электрические контакты модулей и разъемов

Для любого узла

сети G (А, В) должно выполняться условие

(2)


Слайд 30 Полный поток из AS в АT
В реальных конструкциях

Полный поток из AS в АTВ реальных конструкциях пропускные способности каналов

пропускные способности каналов ограничены, поэтому естественна постановка задачи отыскания

максимального потока в сети, которая сводится к нахождению такого распределения потоков (проводников) по отдельным каналам, которое максимизирует целевую функцию (3) при ограничениях (1) и (2).

Решаются данные задачи методами линейного целочисленного программирования.

(3)


Слайд 31 Вопросы по прочитанному материалу?

Вопросы по прочитанному материалу?

  • Имя файла: algoritmy-i-modeli-trassirovki-provodnyh-soedineniy-v-ea.pptx
  • Количество просмотров: 158
  • Количество скачиваний: 0