Понятия теории множеств и теории графов. Переход от электрической схемы к графу. Разбиение электрической схемы с использованием итерационных алгоритмов. Разновидности задач трассировки. Размещение элементов РЭА с использованием конструктивного алгоритма.
Аннотация к работе
Радиотехнические средства применяются для решения различных задач автоматизации и управления производственными процессами, в средствах связи, при создании систем и устройств технической кибернетики, для решения задач радиолокации, навигации, приема и передачи информации на большие расстояния, для диагностики и контроля объектов различной природы и во многих других областях науки и техники.Под множеством понимают совокупность объектов любой природы, называемых элементами данного множества, обладающих каким-либо общим для множества свойством. Множество А считается заданным, если указано свойство ?, которым обладают все элементы, принадлежащие множеству А, и которым элементы, не принадлежащие множеству А, не обладают. Число элементов множества X = {x1, x2, … , xn} называют мощностью этого множества и обозначают прямыми скобками, например, |X| = n. Множество X равно множеству Y, если оба эти множества состоят из одних и тех же элементов. Если множество X полностью содержится во множестве Y и при этом |X| ? |Y|, то говорят, что множество X является подмножеством множества Y: |X| I |Y|.Следовательно, граф - это множество X всех вершин xi, связи между которыми определены множеством ребер U. Такие соединения вершин графа с указанием направления называют ориентированными ребрами или дугами и записывают так: = (xi, xj) ~ xi Tij xj . Граф, в котором все вершины соединены дугами, называют ориентированным, направленным или несимметрическим графом (Рис. Граф, в котором для любых двух вершин xi , xj I X справедливо выражение T i j = T j i , называют неориентированным, ненаправленным или симметрическим графом (Рис. Граф, состоящий только из изолированных вершин (u = ?), называют нуль - графом и обозначают G0 .Принципиальная электрическая схема интерпретируется графом, в котором каждому конструктивному элементу ставятся в однозначное соответствие вершины, а электрическим связям - ребра графа. Это позволяет абстрагироваться от конкретных схем и перейти к их математическим - графам, разрабатывать эффективные методы поиска оптимальных конструктивных решений. Рассмотрим принципиальную электрическую схему логического пробника, рисунок которого приведен ниже. Представим эту схему в виде произвольного, неориентированного графа G(Х,U), у которого Х={х1, х2, х3, х4, х5, х6, х7}, а U - множество электрических связей элементов конструкции рис.7. Строки и столбцы матрицы смежности соответствуют вершинам графа, а ее i,j - элемент равен числу кратных ребер, связывающих вершины xi, xj (табл.1).В первом случае осуществляется последовательная компоновка узлов возрастающей сложности (например: плат, панелей, стоек.), а во втором - узлы высшего уровня последовательно разбиваются на узлы меньшей сложности. Узлы составляют конструктивный базис устройства и, как правило, функционально унифицированы. К первому относятся задачи компоновки конструктивных узлов, в которых осуществляется разбиение схем на узлы с учетом таких ограничений, как количество элементов в узлах, число внешних выводов на узлах, суммарная площадь, занимаемая элементами и соединениями, и количество узлов. Главными критериями для такого разбиения являются: минимум числа образующихся узлов, минимум числа межузловых соединений или внешних выводов на узлах.В графе G (Х, U) находят вершину xi C с максимальной локальной степенью В нашем случае задача формулируется следующим образом: разбить полученный граф на 3 куска, таким образом, чтобы в первом куске было 3 вершины, во втором - две вершины, в третьем 2 вершины. Рассмотрим матрицу смежности, максимальную локальную степень имеет вершина х1, ее соответственно помещаем в первый кусок, кроме того в этот же кусок помещаем все вершины связанные с ней. Если количеств вершин в первом куске меньше заданного, то помещаем из оставшейся части графа ту вершину, которая связана с вершинами множества Х1, большим количеством связей. Если же мощность множества Х1 больше заданного, то удаляем из 1 куска те вершины, которые связаны с вершинами множества Х1 меньшим количеством связей.Сущность данной группы алгоритмов заключается в выборе некоторого начального разбиения (разрезания) графа и последующего его улучшения с помощью итерационного (группового) обмена вершин из различных кусков. При этом для итерации осуществляется перестановка тех вершин, которая обеспечивает максимальное уменьшение числа связей между кусками графа. Воспользуемся одним из итерационных алгоритмов - разбиение графа с использованием чисел связности. При этом порядок подматрицы R1 равен числу вершин, которые должны находиться в первом куске, а порядок подматрицы R2 - числу всех оставшихся вершин графа (табл. Задача разбиения заданного графа G с помощью итерационного алгоритма, заключается в том, чтобы переставить строки и столбцы таким образом, чтобы число ребер следующих кусков G1 и G2 были минимальным.Задачи размещения элементов и трассировки их соединений тесно связаны и при обычных, «ручных», методах конструирования решаются одновременно. В процессе размещения элементов уточн
План
Содержание
Введение
1. Математический аппарат, используемый для решения задач конструкторского проектирования
1.1 Понятия теории множеств
1.2 Понятия теории графов
1.3 Переход от электрической схемы к графу
2. Разбиение электрической схемы
2.1 Разбиение электрической схемы с использованием последовательного алгоритма
2.2 Разбиение электрической схемы с использованием итерационных алгоритмов
3. Размещение элементов узлов РЭС
3.1 Размещение элементов РЭА с использованием конструктивного алгоритма последовательного размещения по связности
3.2 Выбор элемента
3.3 Выбор позиции
3.4 Размещение элементов узлов РЭА с использованием итерационных алгоритмов
4.3 Трассировка печатного монтажа. Волновой алгоритм Ли 4.4 Лучевой алгоритм. Трассировка по магистралям
Заключение
Список литературы
Введение
Радиотехнические средства применяются для решения различных задач автоматизации и управления производственными процессами, в средствах связи, при создании систем и устройств технической кибернетики, для решения задач радиолокации, навигации, приема и передачи информации на большие расстояния, для диагностики и контроля объектов различной природы и во многих других областях науки и техники.
Именно для задач автоматизации, а точнее для задач системы автоматизированного проектирования САПР, предназначено выполнение данной работы, в ходе выполнения которой студенты должны освоить математический аппарат, который используется при конструкторском проектировании РЭС: при компоновке электронных схем, размещении элементов, проведении трасс между элементами. Изложенное выше можно отнести к основной цели выполнения курсового проекта.