Математическое обеспечение конструкторского и технологического проектирования с применением САПР: методические указания по выполнению контрольных работ для студентов 4 курса специальности 23.03

Государственный комитет СССР по народному образованию 

ВСЕСОЮЗНЫЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ 
ЗАОЧНЫЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ 

Кафедра радиотехнических устройств и систем 

МАТЕМАТИЧЕСКОЕ1 ОБЕСПЕЧЕНИЕ КОНСТРУКТОРСКОГО ' 

И ТЖНОЛОШЧЕСКОГО ПРОЕКТИРОВАНИЯ 
. 

С ПРИМЕНЕНИЕМ САПР 

Методические указания по выполнению 
! 

контрольных работ 
| 

для студентов 17 курса 
j 

специальности 23,03 
• i 

Москва 
Издательство 
Всесоюзного заочного политехнического института 

УТВЕРВДЕНО 
проректором по учебной работе 

1990 

Составитель М.В.ГОЛОВИЦЫНА 

I 

©Всесоюзный заочный 
политехнический 
институт, 1990 

-г— 

- 3 
В В Е Д Е Н И Е 

Студентам, обучающимся во специальной** "Конотрунровадн» 
а технология радиоэлектронных средств1''(23.03), необходимо выполнять две контрольные радоты, которые предусмотрены программой дисциплины "Математическое проектирование о применением 
САПР" (индекс УМУ-Т-7/158), Указанная программа утверждена 
Учебно-методичесюш управление!! по высшее образовании 22 февраля 1984 г. 

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

В связи с эаш.! студенты выполняют первув контрольную работу но компоновке схем РЭА, вторую контрольную работу - по размещению элементов к узлов РЭА. Обе контрольные работа ВЫПОЛНЯЕТСЯ с использованием различных алгоритмов, которые предаагавтся 
| в соответствии с шифром студента в методических указаниях [ Q , 
] 
При выполнения контрольных работ необходимо преядв всего 
J четко уяснить себе: 
! 
сбщуь постановку задачи; 

I 
цель, которая- достигается в результате решения; 
j 
критерии.. по которым оценивается оптимальность ао-кучви! ного результата; 
I 
ограничения, которые закладываются к должны быть учгеш 
в процессе решения этой задачи. 

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

Так, разбиение (компоновка) электрической охемы осуществляется в соответствии с некоторым критерием оптимальности. 
Известно, что основным критерием оптимальности является критерий электромагнитотепловой совместимости элементов низшего 
уровня конструктивной иерархии РЭА [2]. 

В зависимости от характера критериев и ограничений различают два характерных класса задач компоновки узлов [2.]. 

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

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

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

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

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

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

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

Задача размещения элементов состоит Е определении оптимального пространственного расположения элементов на коммутационном поле. 

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

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

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

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

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

Первым этапом выполнения контрольных работ I в 2 является 
этап составления математических моделей, предлагаема! в "Методических указаниях" / I / схем, т.е. с абстрактного их представления. Этот этап необходим для разработки формализованного 
цредставления схемы, позволяадего перейти к реализации алгоритмов компоновки и размещения на ЭВМ. 

I . ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ СХЕМЫ 

Для математического описания схем используются основные 
понятия из теории графов. В частности, при решении задач конструирования применяют ненаправленные графы. 

Принципиальная электрическая схема интерпретируется графом Ь (Х, Ь), в котором каждому конструктивно^ элементу ставится в однозначное соответствие вершина графа Xi^-X 
, а 
электрическим соединениям элементов - ребра графа 
1/ / з | . 

Рассмотрим простую электрическую схему дифференциатора 
с R 0 - звеном на входе операционного усилителя 

- 6 
о 
С 

1 
'Ri 

/?2 

I 

Т 

I 

—О 

г 

Йко. I 

Обоаюгаш условно элвшктк схвмк через X i 

'Ai 

1 
Х2 

т 

L 

ф> 

.Хз 

• О 

Х5 

ХЧ 

-У, 

1 

У 

Рис. 2 

Представим "ту схему в виде полного произвольного неориентированного графа G ОС, Ъ'), у которого 

X = ( П , Х2, ХЗ, Х4, Х5} , 

а V - множество электрических связей элементов конструкции 
(в обще;; случае покажем и точки входа/внхода): 

- 7 
Из рис. 3 следует, что при переходе о» схемы к 

(дублирующие) ребра. Эти ребра 

СИУ избыточную информацию а в 

/41. 

у з е л V (рис, 2). Б это*.уем 
три элемента: XI, Х2, ХЗ. Овдащ в этом у ал® можно оп 
ко двумя ребрами графа» напримерг (XI, Х2>. Ш , 13) ю г 
(XI, 12) j. (12, 13), Такда образом, цикл ( И , 12, ХЗ) имеет «*• 
яу "дшввшю" связьр которую следует убрать. На 
те из дублирувди ребер, которне имеют макси 
ность юга большее число пересечений с другими ребрами (в зависимо с та от того, что зранимается за критерий оптимальности), 
Уберем, например, связь {XI, ХЗ). 
„ „ „ * 

Убираем еще две "лишние"связи," например, (ХЗ, Х5) в 
(ХЗ, 7) в узле VI. 

подграфа, соответствующего узлу 
(рис, 4,а) 

Г » 

Г а ) 

- 
8 

(б) 
(в) 

Pro. 4 

Соответствующий ему полный подграф 
С 
имеет вид, показанный на рис. 4,6. Устраняется в С 
в соответствии с Цикломатгюовш числом 
= 6 такие шесте ребер, чтобы в подучен
ном графе не осталось ни одного цикла * он был связан. Строится одно из возможных покрывающих деревьев (рис. 4,в). Бели ребра графа соединений не имеют весов, то все деревья, которые 
можно получить на данных вершинах, равноценны. 

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

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

г 

X/ 
X j 

V
X 

Рис. 5 

Х.5 
Ь 

- 9 
По исходному, графу составляется матрица омехвослг 
/? -HZijtist s 
• г д 0 
- »лемеет матрицы, стоящ* на пврао»чвнжи i. - строки и j 
- столбца. 

Строки и столбцы матрицы смежности соответствуют вервпнам 
графа, а ее (. i j 
) - элемент равен числу кратных ребер, овявявапцих вершины X t и 
XJ. 
№юем: 

П 
12 
13 
и 
15 

II 
0 
I 
I 
0 
0 

Х2 
I 
0 
0 
I 
0 

ХЗ 
I 
0 
0 
I 
0 

Х4 
0 
I 
I 
0 . • 
I 

Х5 
0 
0 
0 
I 
0 

Матрица смежности используется для решения задач разбиения устройств на конструктивно законченные части (контрольная 
работа I), а также для решения задачи размещения моментов 
(контрольная работа 2). 
„ 

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

Представим вершины графа, изображенного на рио. 5, в линейной последовательности в условной решетке с вагон, равны* Z 
(рис. 6). 

XI 
П 
Х5 

Рис. 6 

Матрица геометрии определяется следующим образом: 

.,b=tk)4lln, 

где t/, f - расстояние между вершинами X L, Xj в условной решетке. Для данного графа (рис. 6) матрица/J имеет вид: 

XI 
Х2 
ХЗ 
Х4 
Х5 

п 
0 
I 
2 
3 
4 

12 
I 
0 
I 
2 
3 

ХЗ 
2 
I 
О 
I 
2 

14 
3 
2 
I 
0 
I 

Х5 
4 
3 
2 
I 
0 

Перемножив поэлементно матрицы смежности R 
г геометрии 
J ) , получим матрицу расстояний & ; 

XI 
12 
ХЗ 
Х4 
Х5 

П 
0 
I 
2 
0 
0 

Х2 
I 
О 
0 
2 
0 

ХЗ 
2 
0 
0 
I 
0 

Х4 
0 
2 
I 
0 
I 

Х5 
О 
О 
О 
I 
0 

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

В этом случае в качестве модели электрической схемы рассматривается граф со взвешенными ребрами С - =(Х.~, U t 
где 
U 
- множество Еэбер, вес которых показывает степень связности элементов. В качестве меры связности элементов рассматривается число электрических цепей, общих для них. 

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

Матрицу цепей обозначают-через Т=/,' t LIhrxJ- 
, где 
Ж - число контактов элемента схемы, имеющего наибольшее число контактов; 
П - число элементов схемы; 
t L i - номер цепи в схеме, индидеятной 
J- -му контакт? i -го элемента. 
Следовательно, строки матрицы 7 соответствуй! номерам элементов схемы, столбцы - номерам контактов, а на пересечении (. -й 
строки и j- -го столбца ставится номер -электрической цепи, подключенной к j -му контакту 
' -го элемента.