Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат

Столичный муниципальный институт электроники и арифметики

(Технический институт)

Кафедра ИТАС

РЕФЕРАТ

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

Выполнил:

Проверил:

Принял:

МОСКВА 2003

ОГЛАВЛЕНИЕ

1. Введение

2. Методы сборка

3. Методы размещения

4. Методы трассировки


    ВВЕДЕНИЕ

При конструкторском Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат проектировании РЭА (радиоэлектронной аппаратуры) решаются задачки, связанные с поиском лучшего варианта конструкции, удовлетворяющего требованиям технического задания и очень учитывающего способности технологической базы производства. Тесноватая взаимосвязанность задач и большая размерность каждой из их обычно не позволяет предложить способ поиска рационального конструктивного решения в едином цикле в связи с трудностями сотворения общей математической модели Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат, комплексно учитывающей особенности конструкторско-технологической базы производства. Потому разработка и реализация алгоритмов и способов решения отдельных задач шага конструкторского проектирования: сборки, размещения и трассировки,- до сего времени остаются животрепещущими неуввязками, решение которых неотъемлемо связано с развитием систем автоматизации проектирования.

2. Методы Сборки

На шаге конструкторского проектирования решаются вопросы, связанные Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат с сборкой частей логической схемы в модули, модулей в ячейки, ячеек в панели и т. д. Эти задачки в общем случае плотно сплетены меж собой, и их решение позволяет существенно уменьшить издержки и трудозатратность обозначенного шага в САПР. Обычно задачки сборки рассматриваются как процесс принятия решений в определенных либо Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат неопределенных критериях, в итоге выполнения которого части логической схемы размещаются в конструктивных элементах i-го уровня, а эти элементы располагаются в конструктивных элементах (i+1) –го уровня и т. д., при этом размещение производится с оптимизацией по избранному аспекту.

Сборкой электронной схемы РЭА на конструктивно законченные части именуется процесс рассредотачивания частей Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат низшего конструктивного уровня в высший в согласовании с избранным аспектом. Главным для сборки является аспект электромагнитотепловой сопоставимости частей низшего уровня. Данный аспект определяет область допустимых разбиений схемы, на которой формулируются другие аспекты. Такими аспектами могут быть: минимум типов конструктивно законченных частей, плотность сборки, минимум соединений меж устройствами Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат, простота диагностирования и др. Разумеется, что наружные соединения меж частями схем являются одним из важных причин, определяющих надежность РЭА. Потому более всераспространенным аспектом является аспект минимума числа наружных связей. Выполнение этого аспекта обеспечивает минимизацию обоюдных наводок, упрощение конструкции, увеличение надежности и т. д.

Для построения формальной математической модели компоновочных Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат задач комфортно использовать теорию графов. При всем этом электронную схему интерпретируют ненаправленным мультиграфом, в каком каждому конструктивному элементу (модулю) ставят в соответствие верхушку мультиграфа, а электронным связям схемы – его ребра. Тогда задачка сборки формулируется последующим образом, Задан мультиграф G(X,U). Требуется “разрезать” его на отдельные кусочки G1 (X1 ,U Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат1 ), G2 (X2 ,U2 ),…, Gk (Xk ,Uk ) так, чтоб число ребер, соединяющих эти кусочки, было наименьшим, т.е.

минимизировать i ≠ j

при i,j = 1,2,…,k,

где Uij – огромное количество ребер, соединяющих кусочки Gi (Xi ,Ui ) и Gj (Xj ,Uj ).

Другими словами разбиениями частей совокупы G на графы числятся, если неважно какая часть Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат из этой совокупы не пустая; для всех 2-ух частей скрещение огромного количества ребер может быть не пустым; объединение всех частей в точности равно графу G.

Известные методы сборки можно условно разбить на 5 групп:

1. методы, использующие способы целочисленного программирования.

2. поочередные методы

3. итерационные методы

4. смешанные методы

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

Поочередные алгоритмыкомпоновки

В поочередных методах сборки «разрезание» начального графа G(X,U) на кусочки G1 (X1 ,U1 ), G2 (X2 ,U Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат2 ),…, Gk (Xk ,Uk ) сводится к последующему. В графе G(X,U) находят верхушку xi Xс малой локальной степенью .

Если таких вершин несколько, то предпочтение отдают верхушке с наибольшим числом кратных ребер. Из огромного количества вершин, смежных с верхушками создаваемого кусочка графа G1 (X1 ,U1 ), выбирают ту, которая обеспечивает Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат малое приращение связей кусочка с еще нераспределенными верхушками. Данную верхушку xi X \ X1 включают в G1 (X1 ,U1 ), если не происходит нарушения ограничения по числу наружных связей кусочка, т.е.

,

где αjε – элемент матрицы смежности начально графа G(X,U); δ(xg ) – относительный вес верхушки xg , , равный приращению числа наружных Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат ребер кусочка G1 (X1 ,U1 ) при включении верхушки xg во огромное количество X1 ; E – огромное количество индексов вершин, включенных в создаваемый кусочек графа на прошлых шагах метода; m – очень допустимое число наружных связей раздельно взятого кусочка со всеми оставшимися.

Обозначенный процесс длится до того времени, пока огромное количество X Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат1 не будет содержать nэлементов или присоединение очередной нераспределенной верхушки xj к кусочку G1 (X1 ,U1 ) не приведет к нарушению ограничения по числу наружных соединений кусочка, равному

Необходимо подчеркнуть, что величина не является однотонной функцией |X1 |, потому, для того чтоб удостоверится в невозможности предстоящего формирования кусочка вследствие нарушения последнего ограничения, нужно Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат проверить его невыполнимость на следующих шагах роста огромного количества X1 прямо до n. В качестве окончательного варианта выбирают кусочек G1 0 (X1 0 ,U1 0 ), содержащий очень вероятное число вершин графа G(X,U), для которого производятся ограничения на число наружных связей и входящих в него вершин (nmin -nmax ).

После преобразования кусочка Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат G1 0 (X1 0 ,U1 0 ) процесс повторяют для формирования второго, третьего и т.д. кусков начального графа с той только различием, что рассмотрению подлежат верхушки, не вошедшие в прошлые кусочки.

Сформулируем метод поочередной сборки конструктивных частей.

1) t:0

2) Xf = Xt = Ø; t=t+1; Θ=1; α=nmax ,

Где t, Θ – порядковые номера создаваемого кусочка и присоединяемой Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат верхушки; α – ограничение на число вершин в кусочке.

3) По матрице смежности начального графа | αhp |NxN , где N– число вершин начального графа (при большенном значении N для сокращения объема оперативки ЭВМ используем не саму матрицу смежности, а её кодовую реализацию), определяем локальные степени вершин .

4) Из огромного количества нераспределенных вершин Xвыбираем верхушку xj с Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат ρ(xj ) = . Перебегаем к п.6. Если таких вершин несколько, то перебегаем к п.5

5) Из подмножества вершин Xl с схожей локальной степенью выбирают верхушку xj с наибольшим числом кратных ребер (наименьшим числом смежных вершин), т.е. |Гxj | = .

6) Запоминаем начальную верхушку создаваемого кусочка графа . Перебегаем к п.10

7) По матрице смежности строим огромное количество Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат Xs = и определяем относительные веса вершин :

.

8) Из огромного количества XS избираем верхушку . Перебегаем к п.10. Если таких вершин несколько, то перебегаем к п.9.

9) Из подмножества вершин Xv с схожим относительным весом избираем верхушку xj с наибольшей локальной степенью, т.е. .

10) .

11) Если >m , то перебегаем к п Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат.13.

12) Рассмотренные верхушки включаем в создаваемый кусочек Xf = Xt .

13)Θ = Θ + 1.

14) Если Θ> α, то перебегаем к п.15, а неприятном случае – к п.7.

15) Если |Xf |

16) Избираем окончательный вариант сформированного кусочка графа:

Xt = Xf ; X = X \ Xt ; α = nmax .

17)Если |X|> nmax , то Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат перебегаем к п.20.

18) Если |X|< nmin , то перебегаем к п.21.

19) Определяем число наружных связей последнего кусочка графа:

,

где F – огромное количество индексов вершин, входящих в X. Если , то перебегаем к п.21, в неприятном случае – к п.24.

20) Если t

21) Предшествующий цикл «разрезания» считаем недействительным. Если t>1, т.е. имеется как минимум один ранее сформированный кусочек, то перебегаем к п.22. в неприятном случае – к п.23.

22) Ищем другой допустимый вариант формирования предшествующего кусочка с наименьшим числом вершин: t = t – 1; .

Перебегаем кп.7.

23) Задачка при данных ограничениях не Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат имеет решения.

24) Конец работы метода.

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

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

Итерационные методы сборки

Суть данной группы алгоритмов заключается в выборе некого исходного «разрезания» начального графа на кусочки (вручную либо при помощи поочередного способа сборки) и следующего его улучшения при помощи итерационного парного Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат либо группового обмена вершин из разных кусков. При всем этом для каждой итерации осуществляется перестановка тех вершин, которая обеспечивает наибольшее уменьшение числа связей меж кусочками графа либо наибольшее улучшение другого избранного показателя свойства с учетом применяемых ограничений (к примеру, на наибольшее число наружных ребер хоть какого раздельно взятого кусочка).

Разглядим Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат основную идею итерационного метода разбиения графа G, данного матрицей смежности, с минимизацией числа соединительных ребер. Разбиение графа G = (X,U) на l подграфов G1 = (X1 ,U1 ), G2 = (X2 ,U2 ),…,Gl = (Xl ,Ul ) сведем к разбиению на два подграфа. С этой целью в матрице смежности Rвыделим по главной диагонали Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат две подматрицы R1 и R2 . При всем этом порядок подматрицы R1 равен числу вершин, которые должны находится в G1 , а порядок подматрицы R2 – числу всех оставшихся вершин графа. Нужно так переставить строчки и столбцы матрицы R, чтоб число ребер меж G1 и оставшейся частью графа Gбыло наименьшим. После чего Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат подматрицу R1 из матрицы R исключаем, вычеркнув из Rстроки и столбцы, надлежащие элементам R1 . Дальше подматрицу R1 ’ разбиваем опять на две подматрицы R2 и R2 ’ , при этом порядок R2 соответствует числу вершин второго выделяемого подграфа, а порядок R2 – числу оставшихся вершин графа. Переставляем строчки и столбцы R1 ’ с Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат целью минимизации числа соединительных ребер. После чего подматрица R2 ’ исключается и процесс повторяется до того времени, пока не будет выполнено разбиение графа Gна l подграфов.

Основная мысль метода заключается в выборе таких строк и столбцов, перестановка которых приводит к сосредоточению в диагональных клеточках матрицы Rмаксимального числа частей. Построим прямоугольную матрицу W Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат = ||wi , j || n i x(n - ni ), в какой строчки определяются верхушками из огромного количества I , а столбцы – из огромного количества V , . На скрещении k строчки ( и q столбца находится элемент

,

где rk , q – элемент матрицы смежности R.

Элемент wk , q матрицы W охарактеризовывает изменение числа соединительных ребер меж Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат Gi и Gj при перестановке вершин и . Используя матрицу W , можно отыскать подстановку, которая прирастит число частей в подматрицах R1 и R1 ’ . Таковой процесс повторяется до того времени, пока в подматрице R1 не сосредоточится наибольшее число единиц.

В итерационных методах предусмотрена возможность поиска рационального варианта для разных исходных разбиений. Это Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат связано с тем, что при использовании итерационных алгоритмов оптимальность решения в значимой мере находится в зависимости от того, как успешно было произведено изначальное разбиение графа G(X,U).

Итерационные методы сборки обеспечивают высочайшее качество решения задачки, но требуют огромных издержек машинного времени, чем поочередные методы. Для Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат сокращения числа итераций обмена вершин меж кусочками в смешанных методах для получения исходного «разрезания» графа используют поочередные способы формирования его кусков. С этой целью в неких итерационных методах употребляют процесс групповой перестановки взаимно непересекающихся пар вершин.

3. Методы РАЗМЕЩЕНИЯ

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

Основная сложность в постановке задач размещения заключается в выборе мотивированной функции. Связано это с тем, что одной из основных целей размещения является создание лучших критерий для предстоящей трассировки соединений, что Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат нереально проверить без проведения самой трассировки. Любые другие методы оценки свойства размещения (минимум числа пересечений ребер графа, интерпретирующего электронную схему соединений, разбиение графа на малое число плоских суграфов и т.д.), хотя и позволяют сделать подходящие для трассировки условия, но не гарантируют получение рационального результата, так как печатные Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат проводники представляют собой криволинейные отрезки конечной ширины, конфигурация которых определяется в процессе их построения и находится в зависимости от порядка проведения соединений. Как следует, если для оценки свойства размещения частей избрать аспект, конкретно связанный с получением рационального рисунка металлизации печатной платы, то конечный итог может быть найден только при совместном Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат решении задач размещения, выбора очередности проведения соединений и трассировки, что фактически нереально вследствие большущих издержек машинного времени.

Потому все используемые в текущее время методы размещения употребляют промежные аспекты, которые только отменно содействуют решению основной задачки: получению хорошей трассировки соединений. К таким аспектам относятся: 1) минимум суммарной взвешенной длины соединений Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат; 2) минимум числа соединений, длина которых больше данной; 3) минимум числа скрещение проводников; 4) наибольшее число соединений меж элементами, находящимися в примыкающих позициях или в позициях, обозначенных разработчиком; 5) максимум числа цепей обычный конфигурации.

Наибольшее распространение в методах размещения получил 1-ый аспект, что разъясняется последующими причинами: уменьшение длин соединений улучшает электронные свойства Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат устройства, упрощает трассировку печатных плат; не считая того, он сравнимо прост в реализации.

Зависимо от конструкции коммутационной платы и методов выполнения соединений расстояние меж позициями установки частей подсчитывается по одной из последующих формул:

, ,

В общем виде задачка размещения конструктивных частей на коммутационной плате формулируется последующим образом. Задано огромное количество конструктивных частей R Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат={r 1 , r 2 ,…, rn } и огромное количество связей меж этими элементами V = {v 1 , v 2 ,…, vp }, также огромное количество установочных мест (позиций) на коммутационной плате T = {t 1 , t 2 ,…, tk }. Отыскать такое отображение огромного количества Rна огромном количестве T , которое обеспечивает экстремум мотивированной функции

, где cij – коэффициент взвешенной связности.

Силовые методы Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат размещения

В базу этой группы алгоритмов положен динамический способ В.С. Линского. Процесс размещения частей на плате представляется как движение к состоянию равновесия системы вещественных точек (частей), на каждую из которых действуют силы притяжения и отталкивания, интерпретирующие связи меж размещаемыми элементами. Если силы притяжения, действующие меж хоть какими 2-мя вещественными Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат точками ri и rj пропорциональны числу электронных связей меж данными конструктивными элементами, то состояние равновесия таковой системы соответствует минимуму суммарной длины всех соединений. Введение сил отталкивания вещественных точек друг от друга и от границ платы исключает возможность слияния 2-ух всех точек и содействует их равномерному рассредотачиванию по поверхности Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат монтажного поля. Чтоб убрать появление в системе незатухающих колебаний, вводят силы сопротивления среды, пропорциональные скорости движения вещественных точек.

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

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

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

Итерационные методы размещения

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

В случае минимизации суммарной взвешенной длины соединений формула для расчета конфигурации значения мотивированной функции при перестановке местами частей ri и rj , закрепленных в позициях tf и Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат tg , имеет вид:

,

где p и h ( p ) – порядковый номер и позиция закрепления недвижного элемента rp . Если , то производят перестановку ri и rj , приводящую к уменьшению мотивированной функции на , после этого создают поиск и перестановку последующей пары частей и т.д. Процесс завершается получением такового варианта размещения, для Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат которого предстоящее улучшение за счет парных перестановок частей нереально.

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

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

Поочередные методы размещения

Поочередные методы основаны на допущении, что для получения рационального размещения нужно в примыкающих позициях располагать элементы, очень связанные вместе. Суть этих алгоритмов состоит в поочередном закреплении данного набора конструктивных частей на коммутационной плате Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат относительно ранее установленных. В качестве сначало закрепленных на плате частей обычно выбирают разъемы, которые искусственно «раздвигают» до краев платы. При всем этом все контакты разъемов умеренно распределяются по секциям (столбцам и строчкам координатной сетки). На каждом l -ом шаге (l =1,2,…,n ) для установки на коммутационную плату выбирают элемент из числа еще Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат не размещенных, имеющий наивысшую степень связности с ранее закрепленными элементами Rl -1 . В большинстве применяемых в текущее время алгоритмов оценку степени связности создают по одной из последующих формул:

;

,

где cij – коэффициент взвешенной связности частей i и j ; Jl -1 – огромное количество индексов частей, закрепленных на прошлых l -1 шагах; n Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат – общее число размещенных частей.

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

,

где dfj – расстояние Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат меж f -ой позицией установки элемента и позицией расположенного ранее элемента rj ; Tl -1 – огромное количество позиций, занятых элементами после (l -1 )-го шага метода.

Процесс размещения метода завершается после выполнения n шагов метода.

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

4. Методы ТРАССИРОВКИ

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

Задачка трассировки – одна из более трудозатратных в Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат общей дилемме автоматизации проектирования РЭА. Это связано с несколькими факторами, а именно с разнообразием методов конструктивно-технологической реализации соединений, для каждого из которых при алгоритмическом решении задачки используются специальные аспекты оптимизации и ограничения. С математической точки зрения трассировка – наисложнейшая задачка выбора из большущего числа вариантов рационального решения.

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

Основная задачка трассировки формулируется последующим образом: по данной схеме соединений проложить нужные проводники на плоскости (плате Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат, кристалле и т.д.), чтоб воплотить данные технические соединения с учетом заблаговременно данных ограничений. Основными являются ограничения на ширину проводников и малые расстояния меж ними.

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

, где F – аддитивный аспект; λ i – весовой коэффициент; fi – личный аспект; p – число личных критериев.

Известные методы трассировки печатных плат можно условно разбить на три огромные группы:

1) Волновые методы, основанные на идеях Ли и разработанные Ю.Л. Зиманом и Г Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат.Г. Рябовым. Данные методы получили обширное распространение в имеющихся САПР, так как они позволяют просто учесть технологическую специфику печатного монтажа со собственной совокупой конструктивных ограничений, Эти методы всегда гарантируют построение трассы, если путь для нее существует;

2) Ортогональные методы, владеющие огромным быстродействием, чем методы первой группы. Реализация их на ЭВМ Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат просит в 75-100 раз меньше вычислений по сопоставлению с волновыми методами. Такие методы используют при проектировании печатных плат со сквозными металлизированными отверстиями. Недочеты этой группы алгоритмов связаны с получением огромного числа переходов со слоя на слой, отсутствием 100%-ой гарантии проведения трасс, огромным числом параллельно идущих проводников;

3) Методы эвристического типа. Эти методы Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат отчасти основаны на эвристическом приеме поиска пути в лабиринте. При всем этом каждое соединение проводится по кратчайшему пути, обходя встречающиеся на пути препятствия.

Волновой метод Ли

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

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

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

,

где Pk и Pk -1 - веса ячеек k -го и (k -1 )-го фронтов; - весовая функция, являющаяся показателем свойства проведения пути, каждый параметр которой охарактеризовывает путь исходя из убеждений 1-го из критериев свойства (длины пути, числа пересечений и т.п.). На Pk накладывают одно ограничение Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат – веса ячеек прошлых фронтов не должны быть больше весов ячеек следующих фронтов. Фронт распространяется лишь на примыкающие ячейки, которые имеют с ячейками предшествующего фронта или общую сторону, или хотя бы одну общую точку. Процесс распространения волны длится до того времени, пока её расширяющийся фронт не достигнет приемника либо Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат на Θ-ом шаге не найдется ни одной свободной ячейки, которая могла бы быть включена в очередной фронт, что соответствует случаю невозможности проведения трассы при данных ограничениях.

Если в итоге распространения волна достигнула приемника, то производят «проведение пути», которое заключается в движении от приемника к источнику про пройденным на шаге распространения волны Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат ячейкам, следя за тем, чтоб значения Pk однообразно убывали. В итоге получают путь, соединяющий эти две точки. Из описания метода следует, что все условия, нужные для проведения пути, закладываются в правила приписания веса ячейкам.

Чтоб исключить неопределенность при проведении пути для варианта, когда несколько ячеек имеют однообразный малый Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат вес, вводят понятие путных координат , задающих предпочтительность проведения трассы. Каждое направление кодируют двоичным числом по modq , где q – число просматриваемых примыкающих ячеек. При всем этом чем более желательно то либо другое направление, тем наименьший числовой код оно имеет. К примеру, если задаться приоритетным порядком проведения пути сверху, справа, снизу и Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат слева, то коды соответственных путных координат будут 00, 01, 10, и 11. Приписание путных координат создают на шаге распространения волны. При проведении пути движение от ячейки к ячейке производят по путным координатам.

Существенными недочетами волнового метода являются маленькое быстродействие и большой объем оперативки ЭВМ, нужный для хранения инфы о текущем состоянии всех Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат ячеек коммутационного поля, возможность построения только соединений типа «ввод-вывод». Пробы убрать обозначенные недочеты привели к созданию ряда модификаций волнового метода.

Модификации метода Ли

Способ встречной волны

В данном способе источниками волн являются обе ячейки, подлежащие электронному объединению. При всем этом на каждом k -ом шаге попеременно Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат строят надлежащие фронты первой и 2-ой волн, распространяющихся из этих ячеек. Процесс длится до того времени, пока какая-либо ячейка из фронта первой волны не попадет на фронт 2-ой волны либо напротив. Проведение пути производят из данной ячейки в направлении обоих источников по правилам, описанным в волновом методе Ли Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат.

Оценим число ячеек, просматриваемых на шаге распространения волны, при использовании в качестве источников одной либо 2-ух объединяемых точек. Пусть расстояние меж этими точками R . Тогда для первого варианта в момент заслуги волной ячейки-приемника площадь просмотренной округи имеет величину (символ равенства соответствует отсутствию препядствий пути распространения волны). Для второго Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат варианта в момент встречи фронтов 2-ух волн площадь просмотренной округи .

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

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

Лучевой метод трассировки

В данном методе, предложенным Л.Б. Абрайтисом, выбор ячеек для определения пути меж соединяемыми точками Aи Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат Bпроизводят по заблаговременно данным фронтам, схожим лучам. Это позволяет уменьшить число просматриваемых методом ячеек, а как следует, и время на анализ и шифровку их состояния, но приводит к понижению вероятности нахождения пути сложной конфигурации, и усложняет учет конструктивных требований к технологии печатной платы.

Работа метода заключается в последующем. Задается Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат число лучей, распространяемых из точек Aи B, также порядок присвоения путных координат (обычно число лучей для каждой ячейки-источника принимается схожим). Лучи A(1) , A(2) ,…, A( n ) и B(1) , B(2) ,…, B( n ) считают одноименными, если они распространяются из одноименных источников Aили B. Лучи A( i ) и B( i ) являются разноименными по отношению Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат друг к другу. Распространение лучей создают сразу из обоих источников до встречи 2-ух разноименных лучей в некой ячейке C. Путь проводится из ячейки Cи проходит через ячейки, по которым распространялись лучи.

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

Лучи:

A(1) : ввысь, на лево

A(2) : на лево, ввысь

B(1) : вниз, на право

B(2) : на право, вниз

На втором шаге луч B(1) оказывается заблокированным, а на четвертом шаге блокируется и луч A(2) . Лучи A(1) и B(2) встречаются в ячейке Cна восьмом шаге.

Обычно при помощи лучевого метода удается выстроить до Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат 70-80% трасс, другие проводят, используя волновой метод либо вручную. Его применение в особенности прибыльно при проектировании плат с низкой плотностью монтажа.

Применяемая ЛИТЕРАТУРА

    Б.Н. Деньдобренко, А.С. Малика «Автоматизация конструирования РЭА»,

Москва «Высшая школа» 1980.

    В.М. Курейчик «Математическое обеспечение конструкторского и технологического проектирования с применением САПР»,

Москва «Радио и связь Методы и алгоритмы компоновки, размещения и трассировки печатных плат - реферат» 1990.

  1. К.К. Морзов, В.Г. Одиноков, В.М. Курейчик «Автоматизированное проектирование конструкций радиоэлектронной аппаратуры», Москва «Радио и связь» 1983.
  2. В.Н. Ильин, В.Т. Фролкин, А.И. Бутко и др.; «Автоматизация схемотехнического проектирования: Учебное пособие для вузов», Москва «Радио и связь» 1987.

metodi-i-sposobi-perelivaniya-krovi.html
metodi-i-sredstva-erotetiki.html
metodi-i-sredstva-izmerenij.html