Разработка печатного модуля РЭС с использованием учебных алгоритмов САПР (стр. 1 из 5)

Министерство образования Республики Беларусь

Белорусский государственный университет информатики и радиоэлектроники

Факультет компьютерного проектирования

Кафедра радиоэлектронных средств

Пояснительная записка

к курсовому проекту

по предмету: «Автоматическое конструирование и технология проектирования РЭС»

на тему:

«Разработка печатного модуля РЭС с использованием учебных алгоритмов САПР»

Выполнил:

студент группы 810202

Воронович А.В.

Минск 2000

Содержание

Введение

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

1.1 Общее описание алгоритма

1.2 Пошаговое описание алгоритма

1.3 Выполнение компоновки

2. Размещение элементов в принципиальной электрической схеме с использованием последовательного алгоритма

2.1 Краткое описание алгоритма последовательной установки элементов РЭА

2.2 Выполнение размещения

2.3 Результаты размещения

3. Трассировка цепей питания и земли с использованием алгоритма построения кратчайших связывающих сетей и волнового алгоритма

3.1 Краткое описание алгоритма Краскала

3.2 Трассировка цепей земли по алгоритму Краскала

3.3 Трассировка цепей питания по алгоритму Прима

4. Трассировка сигнальных цепей с помощью волновых алгоритмов

Заключение

Список используемой литературы

Введение

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

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

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

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

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

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

Нам необходимо разработать печатный модуль РЭС с использованием учебных алгоритмов САПР.

1. Решение задачи компоновки

1.1 Общее описание алгоритма

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

Пусть дана схема соединения элементов из множества

. Определим последовательный процесс назначения элементов в узлы Br(

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

Узел считается завершенным, если число элементов в узле равно заданному числу K.

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

Исходные данные являются:

– электрическая схема устройства (Рис.1);

– максимально допустимое число элементов в модуле.

Электрическую схему удобно представлять графом G=(E,V), где множество вершин Е соответствует элементам электрической схемы, а множество ребер V –электрическим связям между элементами.

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

G=(E,V) на множество подграфов

Gr = (Er, Vr),

где r=1, 2, 3…

.

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

(1)

Рис.1

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

(2)

1.2 Пошаговое описание алгоритма

Шаг 1.

Формирование очередного подграфа Gr(r=1,2,3…

) начинается с выбора базовой вершины из множества нераспределенных вершин Ir. В начале процесса все вершины считаются нераспределенными, т.е. Ir=E.

Критерием выбора вершины на роль базовой является ее степень

(

) (под степенью вершины графа будем понимать кол-во ребер данного графа, инцидентных ей). Выбор происходит в соответствии со следующим условием:

(3)

Базовая вершина будет первой по порядку вершиной подграфа Gr(Er,Vr), а оставшиеся вершины, принадлежащие множеству

, являются кандидатами для включения в подграф Gr на последующих шагах алгоритма.

Базовая вершина

является, во-первых, как бы “центром” группирования, к которому прибавляются новые вершины, во-вторых, центром факторизации.

Шаг 2.

Из множества

выделяется подмножество Г ( ) вершин, связанных с .

Шаг 3.

Для элемента X

введем функционал:

L(x)=

(4)

определяющий число цепей, связывающих вершину X и вершины из множества Г и Ir\

.

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

(5)

где

– число связей между вершинами и .

Шаг 4.

Из всех вершин

выбирается такая, у которой значение функционала минимально. Очевидно, что вершина, для которой это условие будет выполняться, максимально связана с . Эта вершина включается во множество Еr вершин Gr.

Множество вершин подграфа Gr приобретает следующий вид:

(6)

где

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

Шаг 5.

Происходит стягивание вершин подграфа Gr в вершину

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

Центр факторизации со степенью факторизации

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