Математический аппарат для конструкторского проектирования РЭС

Содержание Введение

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

1.1 Понятия теории множеств

1.2 Понятия теории графов

1.3 Переход от электрической схемы к графу

2. Разбиение электрической схемы

2.1 Разбиение электрической схемы с использованием последовательного алгоритма

2.2 Разбиение электрической схемы с использованием итерационных алгоритмов

3. Размещение элементов узлов РЭС

3.1 Размещение элементов РЭА с использованием конструктивного алгоритма последовательного размещения по связности

3.2 Выбор элемента

3.3 Выбор позиции

3.4 Размещение элементов узлов РЭА с использованием итерационных алгоритмов

4. Решение задач трассировки

4.1 Разновидности задач трассировки

4.2 Трассировка проводного монтажа. Алгоритм Прима

4.3 Трассировка печатного монтажа. Волновой алгоритм Ли

4.4 Лучевой алгоритм. Трассировка по магистралям Заключение Список литературы

Введение

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

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

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

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

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

Существует два основных способа задания множеств: перечисление и описание.

Первый способ состоит в том, что задаётся и перечисляется полный список элементов, входящих в множество. Например, множество элементов схемы РЭС определяется их списком. Данный способ удобно применять только к ограниченному числу конечных множеств.

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

Множество, А считается заданным, если указано свойство ?, которым обладают все элементы, принадлежащие множеству А, и которым элементы, не принадлежащие множеству А, не обладают.

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

Множества обозначают заглавными буквами латинского алфавита: X, Y, Z и т. д., а элементы множества — соответствующими строчными буквами того же алфавита: x, y, z … или строчными буквами с индексами: x1, x2, …; y1, y2, … и т. д.

Равенство X = { x1, x2, …, xn } свидетельствует о том, что элементы x1, x2, …, xn являются элементами множества X.

Число элементов множества X = x1, x2, …, xn называют мощностью этого множества и обозначают прямыми скобками, например, X = n.

Если число элементов множества X конечно, то такое множество называют конечным. В противном случае множество будет бесконечным.

В теории множеств существует понятие пустого множества, в котором не содержится ни одного элемента.

Пустое множество обозначают специальным символом. Например, если множество X пусто, то пишут X = .

Последовательность из n элементов множества называют n — строкой. В отличие от обычного множества, где порядок элементов безразличен, в n — строке обязательно задаётся их определённая последовательность.

Множество X равно множеству Y, если оба эти множества состоят из одних и тех же элементов.

Если множество X полностью содержится во множестве Y и при этом X Y, то говорят, что множество X является подмножеством множества Y: X Y.

Следовательно, мы рассмотрели два соотношения:

— принадлежность x X;

— включение X Y.

Первое определяет связь между множеством и его элементами, а второе — между двумя множествами.

В случае, когда X Y и, одновременно, Y X, имеет место равенство X = Y, т. е. множества X и Y совпадают.

Символическая запись X Y означает, что множество X не совпадает с множеством Y.

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

Пересечением множеств X и Y называют новое множество P, которое образуется из элементов, одновременно общих и множеству X, и множеству Y. Это можно показать так:

Рис. 1.1.1. Пересечение множеств Пересечение множеств X и Y записывают следующим образом:

P = X Y.

Это свойство носит название «конъюнкция» или «логическое умножение».

Если рассматривают пересечение нескольких множеств X1, X2, … Xi … … X r, то математическая запись имеет вид

r

P = X i ,

i=1

где r — число пересекающихся множеств.

Операция пересечения множеств подчиняется переместительному закону, т. е. P = X Y = Y X.

Если множества X и Y не пересекаются, то P = X Y = .

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

Объединение множеств X и Y приводит к образованию нового множества Q, которое получается из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X или Y.

На рисунке это можно представить так:

Рис. 1.1.2. Объединение множеств Заштрихованная область — множество Q.

Математически объединение множеств X и Y записывают следующим образом:

Q = X Y.

Это свойство носит название «дизъюнкция» или «логическое сложение».

Если рассматривать объединение нескольких множеств, то запись примет вид

r

Q = Xi ,

i=1

где r — число объединяемых множеств.

Операция объединения множеств, также как и операция пересечения, подчиняется переместительному закону.

С помощью этой операции можно подсчитать, например, число типоразмеров конструктивных элементов для печатных плат X и Y или общее число внешних электрических соединений печатных плат X и Y.

Разность множеств X и Y есть новое множество R, которое образуется из элементов множества X за исключением элементов, принадлежащих одновременно множеству Y.

На рис. 1.3.1 R — заштрихованная область.

Рис. 1.1.3. Разность множеств Математически разность множеств X и Y можно записать следующим образом:

R = X / Y .

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

Разбиением множества X называют такое множество множеств {Xj}, где j J, а J — некоторое множество индексов j, при котором:

— Xj X при всех j J;

— Xj при всех j J;

— Xj Xi = при i j;

— Xj = X.

jJ

1.2 Понятия теории графов Понятие графа G (X, U) опирается на понятие множества.

Под абстрактным графом или просто графом G (X, U) понимают совокупность непустого множества X и изолированного от него подмножества U (возможно, пустого), представляющего собой множество всех упорядоченных пар (xi, xj), где xi, xj X. Элементы множеств X и U называют, соответственно, вершинами и дугами графа. Следовательно, граф — это множество X всех вершин xi, связи между которыми определены множеством рёбер U.

То, что элемент xj X находится в отношении Ti j к элементу xj X, отображается на графе соединением элементов xi и xj линией со стрелкой в направлении от xi к xj. Такие соединения вершин графа с указанием направления называют ориентированными рёбрами или дугами и записывают так:

= (xi, xj) xi Tij xj. (1.2.1)

Граф, в котором все вершины соединены дугами, называют ориентированным, направленным или несимметрическим графом (Рис. 1.2.1.).

Рис. 1.2.1. Ориентированный граф Аналитически любой ориентированный граф описывается системой алгебраических уравнений, связывающих параметры xi X, и наоборот, любая система алгебраических уравнений может быть представлена в виде направленного графа.

Граф, в котором для любых двух вершин xi, xj X справедливо выражение T i j = T j i, называют неориентированным, ненаправленным или симметрическим графом (Рис. 1.2.2.).

Рис. 1.2.2. Неориентированный граф Вершина xi инцидентна ребру (дуге) uj, если она является началом или концом ребра (дуги). Аналогично утверждение, что ребро (дуга) uj инцидентно вершине xi, если оно входит или выходит из этой вершины.

Число рёбер (дуг), инцидентных некоторой вершине xi, называют локальной степенью вершины и обозначают (xi) .

Вершину, неинцидентную никакому ребру (дуге), называют изолированной.

Граф, состоящий только из изолированных вершин (u =), называют нуль — графом и обозначают G0 .

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

u = (xi, xi) xi Ti i xi .

Такую связь называют петлёй.

Граф называют конечным, если число его рёбер конечно и бесконечным, если число его рёбер бесконечно.

Конечный граф, у которого отсутствуют петли и изолированные вершины, называют регулярным.

Граф называют однородным степени t, если степени всех его вершин равны t, т. е.

(x1) = (x2) = … = (xn) = t .

Число рёбер в однородном графе степени t равно

U = 0,5Xt .

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

Рис. 1.2.3. Связный граф Таким образом, несвязный граф представляет собой совокупность отдельных частей (подграфов), называемых компонентами связности.

Последовательность рёбер uk U, заданных парами вершин вида

(x0, x1) (x1, x2)…(xl-1, xl) ,

в которой любые два соседних ребра смежные, называется маршрутом.

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

Два графа G и G/ изоморфны (Рис 1.2.4.), если они имеют одинаковое число вершин и если каждой паре вершин, соединённых ребром (дугой), в одном графе, соответствует такая же пара вершин, соединённых ребром (дугой), в другом графе.

Граф, у которого существует хотя бы одна пара вершин, соединённая m рёбрами (дугами в одном направлении), называют мультиграфом (Рис. 1.2.5.).

Рис. 1.2.4. Изоморфные графы Рис. 1.2.5. Мультиграф Граф G/ = (X/, U/) является частью графа G (X, U), если X/ X и U/ U, т. е. граф содержит все вершины и рёбра любой его части (Рис 1.2.6 б).

Часть, которая наряду с некоторым подмножеством рёбер графа содержит и все инцидентные им вершины, называется подграфом (Рис. 1.2.6 в).

Часть, которая наряду с некоторым подмножеством рёбер графа содержит все вершины графа (X/ = X, U/ U), называется суграфом (Рис. 1.2.6 г).

Исходный граф по отношению к его подграфу называют надграфом, а по отношению к суграфу — сверхграфом.

Совокупность всех рёбер графа, не принадлежащих его подграфу (вместе с инцидентными вершинами), образует дополнение подграфа.

Связный неориентированный граф, не содержащий циклов, называют деревом.

Несвязный граф без циклов, отдельные компоненты связности которого являются деревьями, называют лесом.

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

Рассмотрим принципиальную электрическую схему логического пробника, рисунок которого приведен ниже.

Рис. 1.3.1. Принципиальная электрическая схема логического пробника Обозначим условно элементы схемы через xi. Представим эту схему в виде произвольного, неориентированного графа G (Х, U), у которого Х={х1, х2, х3, х4, х5, х6, х7}, а U — множество электрических связей элементов конструкции рис. 7. На этом рисунке клеммы схемы обозначены К1, К2, К3, К4, К5 соответственно. Их разместим условно на плату х0.

Рис. 1.3.2. Произвольный неориентированный граф По исходному графу составляем матрицу смежности,, где — элемент матрицы, состоящий из пересечения i-ой строки и j-го столбца. Строки и столбцы матрицы смежности соответствуют вершинам графа, а ее i, j — элемент равен числу кратных ребер, связывающих вершины xi, xj (табл.1). Матрица смежности R неориентированного графа всегда симметрична.

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

Для этого же графа составим матицу инцидентности. Элементы этой матрицы определяются по следующему правилу: ij — элемент равен 1, если вершина xi инцидентна ребру ui и равен нулю, если xi и ui неинцидентны (табл. 2)

Таблица 2. Матрица инцидентности

2. Разбиение электрической схемы

2.1 Разбиение электрической схемы с использованием последовательного алгоритма Многоуровневый процесс компоновки может выполняться «снизу вверх» или «сверху вниз».

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

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

Узлы составляют конструктивный базис устройства и, как правило, функционально унифицированы.

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

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

Главными критериями для такого разбиения являются: минимум числа образующихся узлов, минимум числа межузловых соединений или внешних выводов на узлах.

Основными критериями при компоновке схем типовыми модулями являются:

— минимум числа модулей, необходимых для покрытия исходной схемы;

— минимум количества межмодульных соединений;

— минимум числа типов используемых модулей;

— и другие.

В качестве ограничений принимают конструктивные и функциональные характеристики типовых модулей.

После проведения компоновки узлов электронного устройства решаются задачи размещения элементов в конструктивном объёме этих узлов и трассировки межсоединений.

Отношение суммарного числа внутренних рёбер (рёбер подмножеств Ui i) к суммарному числу соединяющих рёбер (рёбер подмножеств U i j) называется коэффициентом разбиения (G) графа G:

?? ? ?

G = U i i 0,5 U i j = U i i / K. (2.1.1)

i=1 i=1 j=1 i=1

Разбиение электрической схемы с использованием последовательного алгоритма В последовательных алгоритмах компоновки «разрезание» исходного графа G (Х, U) на "? «частей G 1, G 2, …G? c числом вершин в каждой, соответственно, n 1, n 2, … n? (n 1 + n 2 + +… n? = n) сводится к следующему.

В графе G (Х, U) находят вершину xi с максимальной локальной степенью

(х i) = max (х f).

x f .

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

Рассмотрим матрицу смежности, максимальную локальную степень имеет вершина х1, ее соответственно помещаем в первый кусок, кроме того в этот же кусок помещаем все вершины связанные с ней. Получаем множество Х1 = х1, х2, х3, х4, х7. Если полученное количество вершин в первом куске равно заданному числу — 3, то первый кусок образован.

Если количеств вершин в первом куске меньше заданного, то помещаем из оставшейся части графа ту вершину, которая связана с вершинами множества Х1, большим количеством связей.

Если же мощность множества Х1 больше заданного, то удаляем из 1 куска те вершины, которые связаны с вершинами множества Х1 меньшим количеством связей.

Окончательно получаем Х1 = х1, х2, х7

Далее удаляем эти три вершины из нашего исходного графа и запишем G* = G — G1, тогда Х* = Х — Х1. Соответсвенно строим новый граф, без удаленных вершин (рис. 2.2.1).

Рис. 2.2.1. Граф G*

Для полученного графа строим матрицу смежности (табл 3)

Таблица 3.

По изложенному выше алгоритму выбираем вершину X3 и соответственно связанные с ней остальные вершины, составим множество X2= х3, х5, х6,. Из полученного множества удаляем наименее связанную с X3 вершину — т. е. Х6.

Из полученных вычислений видно, что во второй кусок войдут вершины х3 и х5. Одновременно с этим в последний третий кусок, войдут последние две вершины — х4 и х6.

Графически разбиение графа приведено на рис. 2.2.2.

Рис. 2.2.2. Графическое разбиение графа Рассчитаем коэффициент разбиения по формуле 2.1.1. Имеется четыре внешних и семь внутренних связей вершин.

.

Для улучшения разбиения используются итерационные алгоритмы.

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

Воспользуемся одним из итерационных алгоритмов — разбиение графа с использованием чисел связности.

С этой целью в матрице R выделяем по главной диагонали две подматрицы: R1 и R2. При этом порядок подматрицы R1 равен числу вершин, которые должны находиться в первом куске, а порядок подматрицы R2 — числу всех оставшихся вершин графа (табл. 4).

Таблица 4. Матрица смежности R0

Задача разбиения заданного графа G с помощью итерационного алгоритма, заключается в том, чтобы переставить строки и столбцы таким образом, чтобы число ребер следующих кусков G1 и G2 были минимальным.

Построим дополнительную матрицу W, элементы которой определяются по формуле:

wkq = ?k+?q — 2rkq (2.2.1)

Отсюда для элементов 1-й строки матрицы:

W73 = ?7 + ?3 — 2r73 = -1 — 2 — 2 • 0 = -3;

W74 = ?7 + ?4 — 2r74 = -1 + 0 — 2 •0 = -3;

W75 = ?7 + ?5 — 2r75 = -1 — 2 -2 • 0 = -3;

W76 = ?7 + ?6 — 2r76 = -1 — 3 -2 • 0 = -4.

Для элементов 2-й строки матрицы:

W13 = ?1 + ?3 — 2r13 = -1 — 2 — 2 = -5;

W14 = ?1 + ?4 — 2r14 = -1 + 0 — 2 = -3;

W15 = ?1 + ?5 — 2r15 = -1 — 2 — 0 = -3;

W16 = ?1 + ?6 — 2r16 = -1 — 3 — 0 = -4.

Для элементов 3-й строки матрицы:

W23 = ?2 + ?3 — 2r23 = -1 — 2 — 0 = -3;

W24 = ?2 + ?4 — 2r24 = -1 + 0 — 2 = -3;

W25 = ?2 + ?5 — 2r25 = -1 — 2 — 0 = -3;

W26 = ?2 + ?6 — 2r26 = -1 — 3 — 0 = -4.

Построим дополнительную матрицу W (табл.5,табл.6)

Таблица 5

W0 =

Таблица 6

W0 =

Видим, что в матрице W0 нет положительных элементов, следовательно, делать перестановку столбцов и строк в матрице R0 не имеет смысла.

Проверим оставшиеся вершины. Для этого построим матрицу смежности для оставшихся вершин (табл.7).

Таблица 7

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

3. Размещение элементов узлов РЭС множество граф алгоритм итерационный Задачи размещения элементов и трассировки их соединений тесно связаны и при обычных, «ручных», методах конструирования решаются одновременно. В процессе размещения элементов уточняются трассы соединений, после чего положение некоторых элементов может корректироваться. В зависимости от принятой конструктивно — технологической и схемотехнической базы при решении этих задач используются различные критерии и ограничения. Однако все конкретные разновидности упомянутых задач связаны с проблемой оптимизации схем соединений. В результате получается точное пространственное расположение отдельных элементов конструктивного узла и геометрически определенный способ соединений выводов этих элементов.

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

К метрическим параметрам относятся размеры элементов и расстояния между ними, размеры коммутационного поля, расстояния между выводами элементов, допустимые длины соединений и т. д.

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

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

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

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

Критерием в большинстве случаев является критерий минимума взвешенной длины (МСВД) соединений, который интегральным образом учитывает многочисленные требования, предъявляемые к расположению элементов и трасс их соединений. Это обуславливается рядом факторов:

— уменьшение длин соединений улучшает электрические параметры схемы;

— чем меньше суммарная длина соединений, тем, в среднем, проще их реализация в процессе трассировки;

— уменьшение суммарной длины соединений снижает трудоёмкость изготовления монтажных схем, особенно схем проводного монтажа;

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

3.1 Размещение элементов РЭА с использованием конструктивного алгоритма последовательного размещения по связности Исходной информацией для размещения элементов является:

— схема соединений;

— параметры конструкции элементов и коммутационного поля.

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

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

— количество элементов

— количество позиций

— фиксированный элемент

3.2 Выбор элемента Любое правило выбора элемента для размещения основано на вычислении «меры связности» еще не размещенных элементов с уже размещенными элементами.

Мерой связности двух элементов хi и хj является количество соединений между ними, заданное в матрице соединений R = || r i j || n x n. Существуют различные способы расчёта значений r i j .

Существуют различные правила выбора очередного размещаемого элемента. Одно из них основано на оценке числа связей размещаемого элемента ei Ek как с размещёнными, так и с неразмещёнными элементами (характеристика абсолютной связности) Сi =r i j — r i j. (3.2.1)

ejEk ej k

К этому же типу относится характеристика относительной связности Сi = r i j / r i j. (3.2.2)

ej Ek ejk

На очередном шаге алгоритма размещается элемент, имеющий максимальный коэффициент относительной связности.

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

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

Первый шаг. Рассчитываем характеристику для каждого элемента

C1 = r10 / (r17+r13+r14+r14) = ¼;

C2 = r20 / (2r21+r24) = 1/3;

C3 = r30 / (r31+2r35+r36) = 0;

C4 = r40 / (r41+r42+2r46) = 0;

C5 = r50/ (2r53) = ½;

C6 = r60/ (2r64+r63) = 1/3;

C7 = r70 / r71 = 1.

Максимальную характеристику имеет элемент x7, следовательно, его размещаем вторым. Имеем: x0; x7.

Второй шаг. Расчет проводим с учетом двух размещенных элементов:

C1 = (r10+r17) / (r13+r14+2r12) = ½;

C2 = (r20+r27) / (2r21+r24) = 1/3;

C3 = (r30+r37) / (r31+2r35+r36) = 0;

C4 = (r40+r47) / (r42+r41+2r46) = 0;

C5 = (r50+r57) / 2r53 = ½;

C6 = (r60+r67) / (2r64+r63) = 1/3;

Максимальную характеристику имеет элемент x1, поэтому его размещаем третьим. Имеем: x0; x7; x1.

Третий шаг. Произведем расчет с учетом уже трех размещенных элементов:

C2 = (r20+r27+2r21) / (r24) = 3;

C3 = (r30+r37+2r31) / (2r35+r36) = 1/3;

C4 = (r40+r47+2r41) / (r42+2r46) = 1/3;

C5 = (r50+r57+2r51) / 2r53 = ½;

C6 = (r60+r67+2r61) / (r63+2r64) = 1/3;

Максимальную характеристику имеет элемент x2, следовательно, второй элемент размещаем четвёртым. Имеем: x0; x7; x1; x2.

Четвертый шаг.

Производим расчет с учетом четырех размещенных элементов:

C3 = (r30+r37+r31+r32) / (2r35+r36) = 1/3;

C4 = (r40+r47+r41+r42) / 2r46 = 1;

C5 = (r50+r57+r51+r52) / 2r53= ½;

C6 = (r60+r67+r61+r62) / (r63+2r64) = 1/3;

Максимальную характеристику имеет элемент x4, его размещаем пятым. Имеем: x0; x7; x1; x2; х4.

Пятый шаг.

Производим расчет с учетом уже пяти размещенных элементов.

C3 = (r30+r37+r31+r32+r34) / (2r35+r36) = 1/3;

C5 = (r50+r57+r51+r52+r54) / 2r35= ½;

C6 = (r60+r67+r61+r62+2r64) / r63 = 3;

Максимальную характеристику имеет элемент x6, следовательно, шестой элемент размещаем шестым. Имеем: x0; x7; x1; x2; х4; x6.

Шестой шаг.

Производим расчет с учетом уже шести размещенных элементов.

C3 = (r30+r37+r31+r32+r34+r36) / 2r35= 1;

C5 = (r50+r57+r51+r52+r54+r56) / 2r53= ½;

Максимальную характеристику имеет элемент x3, следовательно, его размещаем седьмым.

Тогда последовательность размещения будет такой:

x0; x7; x1; x2; х4; x6; х3; х5.

3.3 Выбор позиции Выбранный для размещения элемент e i 0 должен быть установлен в одну из незанятых позиций из множества k. Эта позиция выбирается с учётом минимизации критерия размещения, в частности МСВД соединений. При последовательном процессе размещения может быть оценена лишь суммарная длина частичных монтажных соединений данного элемента e i 0 с уже размещёнными элементами Еk .

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

Для выбора позиции Рj k необходимо применять приближённые методы оценки кратчайших монтажных соединений, т. е. рассчитывать псевдодлину реальных соединений. Одна из них имеет вид:

Fj = r i 0 i d p (i 0) p (i). (3.3.1)

ejEk

Выбирается та из позиций, для которой Fj минимальна.

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

Разместим x0 в позицию 4, считая что она уже занята

Шаг 1. Размещаем элемент x7 в каждую из позиций и считаем псевдодлину соединений.

F1 = r70d14 = 13 = 3;

F2 = r70d24 = 12 = 2;

F3 = r70d34 = 11 = 1;

F5 = r70d54 = 11 = 1;

F6 = r70d64 = 12 = 2;

F7 = r70d74 = 13 = 3;

F8 = r70d84 = 14= 4;

Выбираем позицию № 3 и размещаем в ней элемент x7.

Шаг 2. Размещаем элемент x1 в каждой позиции и считаем псевдодлину соединений.

F1 = r10d14+ r17d13 = 13+12 = 5;

F2 = r10d24+ r17d23 = 12+11 = 5;

F5 = r10d54+ r17d53 = 11+12 = 3;

F6 = r10d64+ r17d63 = 12+13 = 5;

F7 = r10d74+ r17d73 = 13+14= 7;

F8 = r10d84+ r17d83 = 14+15 = 9;

Выбираем позицию № 2 и размещаем в ней элемент x1.

Шаг 3. Размещаем элемент x2 в каждой позиции и считаем псевдодлину соединений.

F1 = r20d14+ r27d13 + r21d12= 13+02 +21 = 5;

F5 = r20d54+ r27d53 + r21d52= 11+02 +23 = 7;

F6 = r20d64+ r27d63 + r21d62= 12+03 +24 = 10;

F7 = r20d74+ r27d73 + r21d72= 13+04 +25 = 13;

F8 = r20d84+ r27d83 + r21d82= 14+05 +26 = 16;

Выбираем позицию № 1 и размещаем в ней элемент x2.

Шаг 4. Размещаем элемент x4 в каждой позиции и считаем псевдодлину соединений.

F5 = r40d54+ r47d53 + r41d52+ r42d51= 01+02 +13 +14 = 7;

F6 = r40d64+ r47d63 + r41d62+ r42d61= 02+03 +14 +15 = 9;

F7 = r40d74+ r47d73 + r41d72+ r42d71= 03+04 +15 +16 = 11;

F8 = r40d84+ r47d83 + r41d82+ r42d81= 04+05 +16 +17 = 13;

Выбираем позицию № 5 и размещаем в ней элемент x4.

Шаг 5. Размещаем элемент x6 в каждой позиции и считаем псевдодлину соединений.

F6 = r60d64+ r67d63 + r61d62+ r62d61+ r64d65= 12+03 +04 +05 +21 = 4;

F7 = r60d74+ r67d73 + r61d72+ r62d71+ r64d75= 13+04 +05 +06 +22 = 7;

F8 = r60d84+ r67d83 + r61d82+ r62d81+ r64d85= 14+05 +06 +07 +23 = 10;

Выбираем позицию № 6 и размещаем в ней элемент x6.

Шаг 6. Размещаем элемент x3 в каждой позиции и считаем псевдодлину соединений.

F7 = r30d74+ r37d73 + r31d72+ r32d71+ r34d75+ r36d76= 03+04 +15 +06 +02 +11 = 6;

F8 = r30d84+ r37d83 + r31d82+ r32d81+ r34d85+ r36d86= 04+05 +16 +07 +03 +12 = 8;

Выбираем позицию № 7 и размещаем в ней элемент x3.

Оставшийся элемент x5 размещаем позиции № 8.

В результате получается следующее размещение элементов.

Рассчитаем минимальную суммарную взвешенную длину связей между позициями по формуле

L = rijdp (i)p (j) (3.3.2)

L = r21d12+ r27d13 + r20d14+ r24d15+ r26d16+ r23d17+ r25d18+

+ r17d23+ r10d24+ r14d25+ r16d26+ r13d27+ r15d28+

+ r70d34+ r74d35+ r76d36+ r73d27+ r75d38+

+ r04d45+ r06d46+ r03d47+ r05d48+

+ r46d56+ r43d57+ r45d58+

+ r63d67+ r65d68+

+ r35d78 =

= 21+ 02 + 13+ 14+ 05+ 06+ 07+

+ 11+ 12+ 13+ 04+ 15+ 06+

+ 11+ 02+ 03+ 05+ 05+

+ 01+ 12+ 03+ 14+

+ 21+ 02+ 03+

+ 11+ 02+

+ 21 = 32

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

Итерационные алгоритмы применяются для решения задачи размещения с различными критериями оптимизации F (p): суммарная длина соединений, суммарное число пересечений соединений и т. д., в нашем случае это критерий МСВД.

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

Алгоритмы парных перестановок Пусть имеется некоторое размещение. Выбираются два элемента и меняются местами. Рассчитывается новое значение F (ij); если оно меньше прежнего, то соответствующие элементы меняются местами. Далее выбирается другая пара элементов и осуществляется аналогичная процедура. Процесс продолжается до тех пор, пока не будет применено используемое правило остановки. Расчет осуществляется относительно фиксированного элемента по формуле

Fi j = (r i s — r j s) (d p (i) p (s) — d p (j) p (s)), s / i, j, где (3.4.1)

r i s — количество связей i-го элемента с фиксированным (х0);

r j s — количество связей j-го элемента с фиксированным (х0);

d p (i) p (s) — расстояние между позициями, которые занимают i-й и фиксированный элементы;

d p (j) p (s) — расстояние между позициями, которые занимают j-й и фиксированный элементы.

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

После расчёта всех характеристик выбирается максимально положительное значение? Fij. Соответствующие i-ой и j-ой позиции элементы меняются местами, и рассчитывается новое значение? Fij. Если для данного элемента отсутствует положительное приращение, он остается на своем месте и осуществляется переход к отысканию наилучшего места для следующего элемента с учётом уже двух фиксированных. Процесс итеративно продолжается до тех пор, пока не будет применено используемое в алгоритме правило остановки.

Первый шаг:

?F12 = (r20 — r10)(d14 — d24) = (1 — 1)(3 — 2) =0;

?F13 = (r20 — r70)(d14 — d34) = (1 — 1)(3 — 1) =0;

?F15 = (r20 — r40)(d14 — d54) = (1 — 0)(3 — 1) =2;

?F16 = (r20 — r60)(d14 — d64) = (1 — 1)(3 — 2) =0;

?F17 = (r20 — r30)(d14 — d74) = (1 — 0)(3 — 3) =0;

?F18 = (r20 — r50)(d14 — d84) = (1 — 1)(3 — 4) =0;

Так как? F15 получилось положительным, то меняем местами х2 и х4.

.

Второй шаг

?F23 = (r10 — r70)(d24 — d34)+ (r14 — r74)(d21 — d31) = (1 — 1)(2 — 1)+ (1 — 0)(1 — 2) =-1;

?F25 = (r10 — r20)(d24 — d54)+ (r14 — r24)(d21 — d51) = (1 — 1)(2 — 3)+ (1 — 1)(1 — 4) =0;

?F26 = (r10 — r60)(d24 — d64)+ (r14 — r64)(d21 — d61) = (1 — 1)(2 — 2)+ (1 — 2)(1 — 5) =4;

?F27 = (r10 — r30)(d24 — d74)+ (r14 — r34)(d21 — d71) = (1 — 0)(2 — 5)+ (1 — 0)(1 — 6) =-8;

?F28 = (r10 — r50)(d24 — d84)+ (r14 — r54)(d21 — d81) = (1 — 1)(2 — 6)+ (1 — 0)(1 — 7) =-6;

Так как? F26 получилось положительным, то меняем местами х1 и х6.

Третий шаг

?F35 = (r70 — r20)(d34 — d54)+ (r74 — r24)(d31 — d51) + (r76 — r26)(d32 — d52) = (1 — 1)(1 — 1)+ (0 — 1)(2 — 4)+ (0 — 0)(1 — 3)=2;

?F36 = (r70 — r10)(d34 — d64)+ (r74 — r14)(d31 — d61) + (r76 — r16)(d32 — d62) = (1 — 1)(1 — 2)+ (0 — 1)(2 — 5)+ (0 — 0)(1 — 4)=3;

?F37 = (r70 — r30)(d34 — d74)+ (r74 — r34)(d31 — d71) + (r76 — r36)(d32 — d72) = (1 — 0)(1 — 3)+ (0 — 0)(2 — 6)+ (0 — 1)(1 — 5)=2;

?F38 = (r70 — r50)(d34 — d84)+ (r74 — r54)(d31 — d81) + (r76 — r56)(d32 — d82) = (1 — 1)(1 — 4)+ (0 — 0)(2 — 7)+ (0 — 0)(1 — 6)=0;

Так как? F36 получилось положительным, то меняем местами х7 и х1.

Четвертый шаг

?F56 = (r20 — r70)(d54 — d64)+ (r24 — r74)(d51 — d61) + (r26 — r76)(d52 — d62) + (r21 — r71)(d53 — d63)= (1 — 1)(1 — 2)+ (1 — 0)(4 — 5)+ (0 — 0)(3 — 4) + (2 — 1)(2 — 3)=-2;

?F57 = (r20 — r30)(d54 — d74)+ (r24 — r34)(d51 — d71) + (r26 — r36)(d52 — d72) + (r21 — r31)(d53 — d73)= (1 — 0)(1 — 2)+ (1 — 0)(4 — 6)+ (0 — 1)(3 — 5) + (2 — 1)(2 — 4)=-3;

?F58 = (r20 — r50)(d54 — d84)+ (r24 — r54)(d51 — d81) + (r26 — r56)(d52 — d82) + (r21 — r51)(d53 — d83)= (1 — 1)(1 — 4)+ (1 — 0)(4 — 7)+ (0 — 0)(3 — 6) + (2 — 0)(2 — 5)=-9;

Элемент х2, остаётся неизменным.

Пятый шаг

?F67 = (r70 — r30)(d64 — d74)+ (r74 — r34)(d61 — d71) + (r76 — r36)(d62 — d72) + (r71 — r31)(d63 — d73) + (r72 — r32)(d65 — d75)= (1 — 0)(2 — 3)+ (0 — 0)(5 — 6)+ (0 — 1)(4 — 5) + (1 — 1)(3 — 4) + (0 — 0)(1 — 2)=0;

?F68 = (r70 — r50)(d64 — d84)+ (r74 — r54)(d61 — d81) + (r76 — r56)(d62 — d82) + (r71 — r51)(d63 — d83) + (r72 — r52)(d65 — d85)= (1 — 1)(2 — 4)+ (0 — 0)(5 — 7)+ (0 — 0)(4 — 6) + (1 — 0)(3 — 5) + (0 — 0)(1 — 3)=-2;

Элемент х7, остаётся неизменным.

Шестой шаг

?F78 = (r30 — r50)(d74 — d84)+ (r34 — r54)(d71 — d81) + (r36 — r56)(d72 — d82) + (r31 — r51)(d73 — d83) + (r32 — r52)(d75 — d85) + (r37 — r57)(d76 — d86)= (0 — 1)(3 — 4)+ (0 — 0)(6 — 7)+ (1 — 0)(5 — 6) + (1 — 0)(4 — 5) + (0 — 0)(2 — 3))+ (0 — 0)(1 — 2) = -1.

Элемент х3, х5 остаётся неизменным.

В результате получили следующее размещение

1 2 3 4 5 6 7 8

Рассчитаем критерий размещения после использования итерационного алгоритма

L' = ½ rijdp (i)p (j) (3.4.2)

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

L' = r46d12+ r41d13 + r40d14+ r42d15+ r47d16+ r43d17+ r45d18+

+ r61d23+ r60d24+ r62d25+ r67d26+ r63d27+ r65d28+

+ r10d34+ r12d35+ r17d36+ r13d27+ r15d38+

+ r02d45+ r07d46+ r03d47+ r05d48+

+ r27d56+ r23d57+ r25d58+

+ r73d67+ r75d68+

+ r35d78

L' = 21+ 12 + 03+ 14+ 05+ 06+ 07+

+ 01+ 12+ 03+ 04+ 05+ 06+

+ 11+ 22+ 13+ 05+ 05+

+ 11+ 12+ 03+ 14+

+ 01+ 02+ 03+

+ 01+ 02+

+ 21 = 27

Значение МСВД уменьшилось. Это свидетельствует о том, что данный метод помог улучшить расстановку элементов.

4. Решение задач трассировки

4.1 Разновидности задач трассировки Трассировка монтажных соединений — это задача геометрического построения на КП всех цепей данной конструкции, координаты начала и конца которых определены при размещении элементов. Следовательно, задача трассировки состоит в отыскании геометрически определённого способа соединений эквипотенциальных выводов схемы.

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

Алгоритмы трассировки существенно зависят от принятой конструкции и технологии изготовления РЭС.

Задачи трассировки можно разделить на две группы: трассировка проводных соединений и трассировка печатных (плёночных) соединений.

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

Трассировка печатных и плёночных соединений непосредственно связана с согласованием метрических и топологических параметров схемы соединений и соответствующих параметров коммутационного поля (КП).

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

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

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

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

Алгоритмические методы проводных и печатных соединений существенно различаются.

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

4.2Трассировка проводного монтажа. Алгоритм Прима Монтажные соединения для цепей схемы представляют собой деревья.

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

Такое дерево называется минимальным покрывающим деревом или минимальным связывающим деревом.

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

— всякая изолированная вершина соединяется с ближайшей;

— всякий изолированный фрагмент (связанная группа вершин) соединяется с ближайшей вершиной кратчайшим ребром.

Построенное таким образом дерево будет иметь минимальную суммарную длину соединений.

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

Основу всех модификаций алгоритма Ли составляет процедура построения оптимального в заданном смысле пути между двумя известными ячейками ДРП. Процедура состоит из двух этапов: поиска пути и проведения пути.

На первом этапе из одной из заданных ячеек ДРП — источника моделируется распространение числовой волны до тех пор, пока её фронт не достигнет второй отмеченной ячейки ДРП. В первом случае искомый путь существует, во втором — нет.

На втором этапе алгоритма осуществляется проведение пути. Для этого следует, начиная от ячейки — цели двигаться в направлении, противоположном направлению распространения волны, переходя последовательно от ячейки с большим весом к соседней ячейке с меньшим весом до тех пор, пока не будет достигнута ячейка — источник. Ячейки ДРП, выделенные в ходе указанного процесса, и определяют искомую оптимальную трассу.

4.4 Лучевой алгоритм. Трассировка по магистралям Волновой алгоритм в той или иной модификации является основой большинства развитых программ машинной трассировки ввиду его универсальности.

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

Алгоритмы построения соединений с малым числом поворотов (лучевой алгоритм). Это такой алгоритм трассировки, в котором основные процедуры поиска и проведения пути осуществляются путем исследования пространства магистралей (линий), а не ячеек ДРП, как в классическом алгоритме Ли.

Осуществим трассировку схемы (рис. 1.3.1) с использованием волнового и лучевого алгоритмов

Рис. 4. 4.1 Трассировка схемы по магистралям Итак, в ходе трассировки монтажных соединений заданной схемы была решена задача геометрического построения на коммутационном поле всех цепей конструкции. Однако исключить все пересечения не удалось. Использовать двухслойный монтаж для этой схемы не имеет смысла, так как он будет очень объёмным и дорогостоящим при больших объёмах производства. Целесообразнее показанное пунктиром соединение сделать проводным, впаяв перемычку в отверстия с контактными площадками.

Заключение

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

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

1. Головицына М. В., Данилова Т. А. Информационные технологии проектирования РЭС. Математическое обеспечение САПР для решения задач конструкторского проектирования. М.: МГОУ, 2008, — 154с.

2. Головицына М. В. Математическое обеспечение конструкторского и технологического проектирования. М.: МГОУ, — 1990.

3. Головицына М. В. Информационные технологии проектирования РЭС: электронное пособие. МГОУ, 2003. — 114с.

4. Головицына М. В. Информационные технологии проектирования РЭС. М.: Изд-во Интернет — Университета информационных технологий. 2008, — 431с.

5. Деньдобренько Б. Н. Автоматизация конструирования РЭА: Учебник для вузов. М: Высшая школа, 1980. — 384с.

6. Методы разбиения схем РЭА. Под. Ред. К. К. Морозова. М: Сов. Радио, 1978, — 136с.

7. Морозов К. К, Одиноков В. Г. Курейчик В.М. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры: Учеб. Пособие для вузов М.: Радио и связь, 1983, — 280с.

8. Яншин А. А. Теоретические основы конструирования, технология и надежность ЭВА: Учебник для вузов. М.: Радио и связь 1983, — 312с.