Математический аппарат для конструкторского проектирования РЭС - Коммуникации, связь, цифровые приборы и радиоэлектроника курсовая работа

Главная

Коммуникации, связь, цифровые приборы и радиоэлектроника
Математический аппарат для конструкторского проектирования РЭС

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


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

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

1. Математический аппарат, используемый для решения задач конструкторского проектирования
1.3 Переход от электрической схемы к графу
2.1 Разбиение электрической схемы с использованием последовательного алгоритма
2.2 Разбиение электрической схемы с использованием итерационных алгоритмов
3.1 Размещение элементов РЭА с использованием конструктивного алгоритма последовательного размещения по связности
3.4 Размещение элементов узлов РЭА с использованием итерационных
4.1 Разновидности задач трассировки
4.2 Трассировка проводного монтажа. Алгоритм Прима
4.3 Трассировка печатного монтажа. Волновой алгоритм Ли
4.4 Лучевой алгоритм. Трассировка по магистралям
Радиотехнические средства применяются для решения различных задач автоматизации и управления производственными процессами, в средствах связи, при создании систем и устройств технической кибернетики, для решения задач радиолокации, навигации, приема и передачи информации на большие расстояния, для диагностики и контроля объектов различной природы и во многих других областях науки и техники.
Именно для задач автоматизации, а точнее для задач системы автоматизированного проектирования САПР, предназначено выполнение данной работы, в ходе выполнения которой студенты должны освоить математический аппарат, который используется при конструкторском проектировании РЭС: при компоновке электронных схем, размещении элементов, проведении трасс между элементами. Изложенное выше можно отнести к основной цели выполнения курсового проекта.
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 Y и, одновременно, Y X, имеет место равенство X = Y, т.е. множества X и Y совпадают.
Символическая запись X Y означает, что множество X не совпадает с множеством Y.
Над множествами, как и над другими математическими величинами, можно производить некоторые действия, например, выполнять пересечение множеств, их объединение, вычитание, находить дополнение, декартово произведение и прочее.
Пересечением множеств X и Y называют новое множество P, которое образуется из элементов, одновременно общих и множеству X, и множеству Y. Это можно показать так:

Пересечение множеств X и Y записывают следующим образом:
Это свойство носит название «конъюнкция» или «логическое умножение».
Если рассматривают пересечение нескольких множеств X1, X2, … Xi … … X r , то математическая запись имеет вид
где r - число пересекающихся множеств.
Операция пересечения множеств подчиняется переместительному закону, т.е. P = X Y = Y X.
Если множества X и Y не пересекаются, то P = X Y = .
С помощью операции пересечения множеств можно, например, выявить множество типоразмеров конструктивных элементов, общих печатным платам X и Y, или множество межплатных соединений для печатных плат X и Y, т.е. выявить любые множества, обладающие какими-либо общими свойствами.
Объединение множеств X и Y приводит к образованию нового множества Q, которое получается из всех тех и только тех элементов, которые принадлежат хотя бы одному из множеств X или Y.
На рисунке это можно представить так:

Заштрихованная область - множество Q.
Математически объединение множеств X и Y записывают следующим образом:
Это свойство носит название «дизъюнкция» или «логическое сложение».
Если рассматривать объединение нескольких множеств, то запись примет вид
где r - число объединяемых множеств.
Операция объединения множеств, также как и операция пересечения, подчиняется переместительному закону.
С помощью этой операции можно подсчитать, например, число типоразмеров конструктивных элементов для печатных плат X и Y или общее число внешних электрических соединений печатных плат X и Y.
Разность множеств X и Y есть новое множество R, которое образуется из элементов множества X за исключением элементов, принадлежащих одновременно множеству Y.
На рис. 1.3.1 R - заштрихованная область.

Математически разность множеств X и Y можно записать следующим образом:
С помощью этой операции можно выявить сугубо индивидуальные признаки объекта, например, число типоразмеров конструктивных элементов, принадлежащих только плате X.
Разбиением множества X называют такое множество множеств {Xj}, где j J, а J - некоторое множество индексов j, при котором:
Понятие графа 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. Такие соединения вершин графа с указанием направления называют ориентированными рёбрами или дугами и записывают так:
Граф, в котором все вершины соединены дугами, называют ориентированным, направленным или несимметрическим графом (Рис. 1.2.1.).
Аналитически любой ориентированный граф описывается системой алгебраических уравнений, связывающих параметры xi X, и наоборот, любая система алгебраических уравнений может быть представлена в виде направленного графа.
Граф, в котором для любых двух вершин xi , xj X справедливо выражение T i j = T j i , называют неориентированным, ненаправленным или симметрическим графом (Рис. 1.2.2.).
Вершина xi инцидентна ребру (дуге) uj , если она является началом или концом ребра (дуги). Аналогично утверждение, что ребро (дуга) uj инцидентно вершине xi , если оно входит или выходит из этой вершины.
Число рёбер (дуг), инцидентных некоторой вершине xi, называют локальной степенью вершины и обозначают (xi) .
Вершину, неинцидентную никакому ребру (дуге), называют изолированной.
Граф, состоящий только из изолированных вершин (u = ), называют нуль - графом и обозначают G0 .
При использовании графов для анализа радиоэлектронных устройств в отдельных случаях целесообразно введение связи вершины самой с собой, т.е.
Граф называют конечным, если число его рёбер конечно и бесконечным, если число его рёбер бесконечно.
Конечный граф, у которого отсутствуют петли и изолированные вершины, называют регулярным.
Граф называют однородным степени t, если степени всех его вершин равны t , т.е.
Число рёбер в однородном графе степени t равно
Граф, любая пара вершин которого связана, называют связным графом (Рис. 1.2.3.). В связном графе, перемещаясь по рёбрам из вершины в вершину, можно попасть в каждую вершину. Граф, состоящий из отдельных фрагментов, называют несвязным, состоящим из отдельных компонент связности.
Таким образом, несвязный граф представляет собой совокупность отдельных частей (подграфов), называемых компонентами связности.
Последовательность рёбер uk U , заданных парами вершин вида
в которой любые два соседних ребра смежные, называется маршрутом.
Число рёбер в маршруте определяет его длину. Если все рёбра в маршруте различны, то такой маршрут является цепью.
Два графа G и G/ изоморфны (Рис 1.2.4.), если они имеют одинаковое число вершин и если каждой паре вершин, соединённых ребром (дугой), в одном графе, соответствует такая же пара вершин, соединённых ребром (дугой), в другом графе.
Граф, у которого существует хотя бы одна пара вершин, соединённая m рёбрами (дугами в одном направлении), называют мультиграфом (Рис. 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). Полученные результаты запишем в нижнюю строку матрицы
Для этого же графа составим матицу инцидентности. Элементы этой матрицы определяются по следующему правилу: ij - элемент равен 1, если вершина xi инцидентна ребру ui и равен нулю, если xi и ui неинцидентны (табл. 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)
Разбиение электрической схемы с использованием последовательного алгоритма
В последовательных алгоритмах компоновки « разрезание» исходного графа G (Х, U) на « ? » частей G 1 , G 2 , …………..G ? c числом вершин в каждой, соответственно, n 1 , n 2 , ……… n ? (n 1 + n 2 + +…………… n ? = n) сводится к следующему.
В графе G (Х, U) находят вершину xi с максимальной локальной степенью
В нашем случае задача формулируется следующим образом: разбить полученный граф на 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).
Для полученного графа строим матрицу смежности (табл 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).
Задача разбиения заданного графа G с помощью итерационного алгоритма, заключается в том, чтобы переставить строки и столбцы таким образом, чтобы число ребер следующих кусков G1 и G2 были минимальным.
Построим дополнительную матрицу W, элементы которой определяются по формуле:
Отсюда для элементов 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.
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.
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)
Видим, что в матрице W0 нет положительных элементов, следовательно, делать перестановку столбцов и строк в матрице R0 не имеет смысла.
Проверим оставшиеся вершины. Для этого построим матрицу смежности для оставшихся вершин (табл.7).
Итак, применение итерационного алгоритма не улучшило значение критерия разбиения графа. Следующая задача - размещение элементов электрической схемы.
множество граф алгоритм итерационный
Задачи размещения элементов и трассировки их соединений тесно связаны и при обычных, «ручных», методах конструирования решаются одновременно. В процессе размещения элементов уточняются трассы соединений, после чего положение некоторых элементов может корректироваться. В зависимости от принятой конструктивно - технологической и схемотехнической базы при решении этих задач используются различные критерии и ограничения. Однако все конкретные разновидности упомянутых задач связаны с проблемой оптимизации схем соединений. В результате получается точное пространственное расположение отдельных элементов конструктивного узла и геометрически определенный способ соединений выводов этих элементов.
Критерии качества и ограничения, связанные с конкретными задачами размещения и трассировки, опираются на конкретные конструктивные и технологические особенности реализации коммутационной части узла. Всю совокупность критериев и ограничений можно разделить на две группы в соответствии с метрическими и топологическими параметрами конструкции узлов и схем.
К метрическим параметрам относятся размеры элементов и расстояния между ними, размеры коммутационного поля, расстояния между выводами элементов, допустимые длины соединений и т.д.
Топологические параметры в основном определяются принятым в конкретной конструкции способом устранения пересечений соединений и относительным расположением соединений на коммутационном поле. К ним относятся: число пространственных пересечений соединений, число межслойных переходов, близость расположения друг к другу тепловыделяющих элементов или несовместимых в электромагнитном отношении элементов и соединений.
В конкретных задачах указанные параметры в различных сочетаниях могут быть либо главными критериями оптимизации, либо выступать в качестве ограничений.
В связи с этим при алгоритмическом подходе к их решению они рассматриваются, как правило, раздельно. Сначала осуществляется размещение элементов, а затем - трассировка межсоединений. Если необходимо, этот процесс может быть повторен при другом расположении отдельных элементов.
Основной целью размещения считают создание наилучших условий для последующей трассировки соединений при удовлетворении основных требований, обеспечивающих работоспособность схем.
Критерием в большинстве случаев является критерий минимума взвешенной длины (МСВД) соединений, который интегральным образом учитывает многочисленные требования, предъявляемые к расположению элементов и трасс их соединений. Это обуславливается рядом факторов:
- уменьшение длин соединений улучшает электрические параметры схемы;
- чем меньше суммарная длина соединений, тем, в среднем, проще их реализация в процессе трассировки;
- уменьшение суммарной длины соединений снижает трудоёмкость изготовления монтажных схем, особенно схем проводного монтажа;
- данный критерий относительно прост с математической точки зрения и позволяет косвенным образом учитывать другие параметры схем путём присвоения весовых оценок отдельным соединениям.
3.1 Размещение элементов РЭА с использованием конструктивного алгоритма последовательного размещения по связности
Исходной информацией для размещения элементов является:
- параметры конструкции элементов и коммутационного поля.
Поскольку критерий минимума суммарной длины соединений наиболее распространен, он будет рассмотрен в качестве основного критерия.
Контактную площадку т.е элемент х0 будем рассматривать как фиксированный элемент, следовательно в нашес случае мы имеем следующие ограничения:
Любое правило выбора элемента для размещения основано на вычислении «меры связности» еще не размещенных элементов с уже размещенными элементами.
Мерой связности двух элементов хi и хj является количество соединений между ними, заданное в матрице соединений R = || r i j || n x n . Существуют различные способы расчёта значений r i j .
Существуют различные правила выбора очередного размещаемого элемента. Одно из них основано на оценке числа связей размещаемого элемента ei Ek как с размещёнными, так и с неразмещёнными элементами (характеристика абсолютной связности)
К этому же типу относится характеристика относительной связности
На очередном шаге алгоритма размещается элемент, имеющий максимальный коэффициент относительной связности.
Рассмотренные характеристики не зависят от положений элементов, поэтому в принципе может быть выполнено предварительное упорядочение всех элементов, а потом уже и их размещение.
Рассмотрим исходную матрицу смежности с элементом x0, который в нашем случае является уже фиксированным элементом, поэтому размещать остальные элементы будем по отношению к нему.
Первый шаг. Рассчитываем характеристику для каждого элемента
C1 = r10 / (r17+r13+r14+r14) = 1/4;
Максимальную характеристику имеет элемент x7, следовательно, его размещаем вторым. Имеем: x0; x7.
Второй шаг. Расчет проводим с учетом двух размещенных элементов:
C1 = (r10+r17) / (r13+r14+2r12) = 1/2;
C3 = (r30+r37) / (r31+2r35+r36) = 0;
C4 = (r40+r47) / (r42+r41+2r46) = 0;
Максимальную характеристику имеет элемент x1, поэтому его размещаем третьим. Имеем: x0; x7; x1.
Третий шаг. Произведем расчет с учетом уже трех размещенных элементов:
C3 = (r30+r37+2r31) / (2r35+r36) = 1/3;
C4 = (r40+r47+2r41) / (r42+2r46) = 1/3;
C6 = (r60+r67+2r61) / (r63+2r64) = 1/3;
Максимальную характеристику имеет элемент x2, следовательно, второй элемент размещаем четвёртым. Имеем: x0; x7; x1; x2.
Производим расчет с учетом четырех размещенных элементов:
C3 = (r30+r37+r31+r32) / (2r35+r36) = 1/3;
C5 = (r50+r57+r51+r52) / 2r53= 1/2;
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= 1/2;
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= 1/2;
Максимальную характеристику имеет элемент x3, следовательно, его размещаем седьмым.
Тогда последовательность размещения будет такой:
Выбранный для размещения элемент e i 0 должен быть установлен в одну из незанятых позиций из множества k . Эта позиция выбирается с учётом минимизации критерия размещения, в частности МСВД соединений. При последовательном процессе размещения может быть оценена лишь суммарная длина частичных монтажных соединений данного элемента e i 0 с уже размещёнными элементами Еk .
При установке элемента в позицию рассчитываются трассы соответствующих соединений. Длина этих соединений является критерием для выбора позиций. Однако большие затраты машинного времени делают этот подход нереальным, при конструировании узлов с печатными соединениями, и ограниченно применимым при конструировании монтажных схем проводных соединений.
Для выбора позиции Рj k необходимо применять приближённые методы оценки кратчайших монтажных соединений, т.е. рассчитывать псевдодлину реальных соединений. Одна из них имеет вид:
Fj = r i 0 i d p ( i 0 ) p ( i ). (3.3.1)
Выбирается та из позиций, для которой Fj минимальна.
Для экономии вычислений всегда целесообразно рассматривать не всё множество позиций k , а лишь часть.
Разместим x0 в позицию 4, считая что она уже занята
Шаг 1. Размещаем элемент x7 в каждую из позиций и считаем псевдодлину соединений.
Выбираем позицию №3 и размещаем в ней элемент x7.
Шаг 2. Размещаем элемент x1 в каждой позиции и считаем псевдодлину соединений.
Выбираем позицию №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 = r21d12+ r27d13 + r20d14+ r24d15+ r26d16+ r23d17+ r25d18+
+ r17d23+ r10d24+ r14d25+ r16d26+ r13d27+ r15d28+
+ r70d34+ r74d35+ r76d36+ r73d27+ r75d38+
3.4 Размещение элементов узлов РЭА с использованием итерационных алгоритмов
Алгоритмы данной группы используют общие идеи методов последовательных приближений и являются комбинаторными аналогами градиентных методов оптимизации. Уже имеепм начальный вариант размещения.
Итерационные алгоритмы применяются для решения задачи размещения с различными критериями оптимизации F (p): суммарная длина соединений, суммарное число пересечений соединений и т.д., в нашем случае это критерий МСВД.
В любом итерационном алгоритме исследуется подмножество размещений, в некотором смысле близких к начальному, для выделения в нём размещения с меньшим значением функции - критерия. Найденное размещение вновь принимается за начальное, и процесс повторяется. Алгоритм завершается при отыскании некоторого размещения, в окружности которого отсутствуют варианты с меньшим значением функции - критерия. В большинстве случаев такой процесс приводит к получению локального минимума функции F (p).
Пусть имеется некоторое размещение. Выбираются два элемента и меняются местами. Рассчитывается новое значение F(ij); если оно меньше прежнего, то соответствующие элементы меняются местами. Далее выбирается другая пара элементов и осуществляется аналогичная процедура. Процесс продолжается до тех пор, пока не будет применено используемое правило остановки. Расчет осуществляется относительно фиксированного элемента по формуле
Fi j = ( r i s - r j s ) ( d p(i) p (s) -
Математический аппарат для конструкторского проектирования РЭС курсовая работа. Коммуникации, связь, цифровые приборы и радиоэлектроника.
Практическая Работа Исследуем Свойства
Курсовая работа по теме Центральный банк Российской Федерации
Россия 19 Век Контрольная Работа
Профессия Моей Мечты Сочинение
Курсовая работа по теме Розробка моделі молодіжного жакета в умовах індивідуального виробництва
Курсовая работа по теме Стратегическое планирование в рамках TQM
Дипломная работа по теме Разработка методики повышения эффективности проведения занятий с использованием информационных технологий
Реферат по теме История информационной культуры как отрасли знаний
Реферат: Развитие личности детей с задержкой психического развития
Контрольная Работа На Тему Вода В Природе И Жизни Человека
Контрольная работа: О пользе бухучета. Скачать бесплатно и без регистрации
Сочинение На Тему Эпоха Дворцовых Переворотов
Контрольная Работа Механические Колебания 11 Класс Профиль
Реферат: Классификация автоматизированных систем управления. Скачать бесплатно и без регистрации
Взаимосвязь Наук Реферат
База Знаний Реферат
Реферат: Мерчандайзинг как эффективная маркетинговая технология. Скачать бесплатно и без регистрации
Реферат: Philosophy And Ethics Essay Research Paper Ron
Летом На Даче Сочинение 3 Класс
Реферат: Духовная культура старообрядцев Западного Забайкалья
Надзор как способ обеспечения законности деятельности органов исполнительной власти - Государство и право контрольная работа
Развитие и повышение качества системы контроля в сфере муниципального жилищно-коммунального хозяйства - Государство и право реферат
Нормы русского литературного языка - Иностранные языки и языкознание презентация