Курсовая работа
Автоматизация проектирования изделий электронной техники
Введение
Основные задачи развития технологии электрического монтажа - это увеличение плотности компоновки элементов, обеспечение режима согласования линий связи и равномерного распределения потенциалов питания между активными элементами электронных устройств. Оптимальным средством решения этих задач является печатный монтаж благодаря таким его преимуществам перед другими методами монтажа, как компактность конструкций изделий на печатных платах, автоматизации проектирования соединений, что позволяет составлять программы управления технологическим и контрольным оборудованием.
Автоматизация проектирования изделий электронной техники, исходя из степени однородности задач и методов их решения в процессе проектирования изделия, подразделяется на следующие четыре этапа:
- системотехническое проектирование, при котором выбираются и формулируются цели проектирования, формируется структура будущего изделия, определяются его основные технико-экономические характеристики;
- функциональное (схемотехническое) проектирование, в ходе которого выбирается функционально-логическая база, разрабатываются принципиальные электрические схемы изделий электронной техники в целом и ее составных частей, оптимизируются ее параметры;
- техническое (конструкторское) проектирование, которое решает задачи синтеза конструкций изделия в целом, определяет компоновку и размещение, разрабатывает топологию электрических соединений;
- проектирование технологических процессов, которое предусматривает определение состава технологического оборудования для изготовления печатной платы, подготовку необходимых организационно-технических мероприятий, связанных с обеспечением функционирования технологических линий изготовления печатных плат, и разработки правил подготовки проекта печатной платы для ее изготовления в единичном, мелкосерийном и крупносерийном вариантах.
1.Разбиение функциональных элементов по корпусам микросхем
Общее описание алгоритма.
Общая схема процесса последовательной компановки по связности имеет следующий вид.
Пусть дана схема соединения элементовов множеств
.
Определим последовательный процесс назначения элементов
в узлы Br(),на каждом шаге которого выбирается один из неразделенных элементов и приписывается очередному узлу.
Узел считается завершенным, если число элементов в узле равно зачетному числу K.
После завершения очередного узла аналогичная процедура повторяется для следующего узла, причем кандидатами для назначения являются элементы не включенные в предыдущие узлы. Процесс заканчивается когда все элементы из множества E распределены.
Исходные данные являются:
-электрическая схема устройства.
-максимально допустимое число элементов в модуле.
Электрическую схему удобно представлять графом G=(E,V) , где множество вершин Е соответствует элементам эл-ой схемы, а множество ребер V –эл-ким связям между элементами. В таком виде задача компоновки может быть сформулирована как задача разрезания графа G=(E,V) на множество подграфов
Gr=(Er,Vr) ,где r=1,2,3….
В каждом подграфе число вершин соответственно Er должно не превосходить ранее заданного ограничения на число элементовов в узле К. Для любого разбиения должны выполняться следующие условия:
(1)
=Æ; (2)
(3)
При проведении компоновки без учета ограничения на кол-во внешних выводов в узле все модули, кроме последнего, будут иметь полное заполнение . и последнее условие примет вид
(4)
Пошаговое описание алгоритма.
Шаг 1.
Формирование очередного подграфа Gr(r=1,2,3…) начинается с выбора базовой вершины из множества нераспределенных вершин Ir . В начале процесса все вершины считаются нераспределенными, т.е. Ir=E.Критерием выбора вершины на роль базовой является ее степень () (под степенью вершины графа будем понимать кол-во ребер данного графа, инцидентных ей). Выбор происходит в соответствии со следующим условием:
(5)
Базовая вершина будет первой по порядку вершиной подграфа Gr(Er,Vr), а оставшиеся вершины, принадлежащие множеству , являются кандидатами для включения в подграф Gr на последующих шагах алгоритма.
Базовая вершина является, во-первых, как бы “центром” группирования, к которому прибавляются новые вершины, во-вторых, центром факторизации.
Шаг 2.
Из множества выделяется подмножество Г() вершин, связанных с .Шаг 3.
Для эл-та X введем функционал:
L(x)= (6)
определяющий число цепей , связывающих вершину X и вершины из множества Г и Ir.Для упрощения записей будем отождествлять элемент (множество элементов).для формального вычисления функционала будем пользоваться формулой:
(7)
где -число связей между вершинами и .
Шаг 4.
Из всех вершин выбирается такая, у которой значение функционала минимально. Очевидно,что вершина для которой это условие будет выполняться , максимально связана с . Эта вершина включается во множество Еr вершин Gr.
Множество вершин подграфа Gr приобретает следующий вид:
где , а верхний индекс в обозначении в общем случае указывает кол-во шагов выборки.
Шаг 5.
Происходит стягивание вершин подграфа Gr в вершину .Этот процесс далее будем называть факторизацией, вершину - центром факторизации, а кол-во вершин стянутых в ,кроме него самого, степенью факторизации.
Центр факторизации со степенью факторизации ,отличной от нуля, будем обозначать символом и называть гипервершиной степени .
После данного процесса множество преобразуют в одноэлементное множество
содержащее гипервершину степени .
В указанных обозначениях первый процесс факторизации запишется следующим образом:
.
В общем случае на ом шаге выборки все указанные преобразования будут иметь вид:
.
=1,2,3…,Кс-1 ,где Кс-допустимая мощность множества вершин формируемого подграфа (кол-во элементов в конструктивном узле).
Шаг 6.
Действия описанные в шагах 2,3,4,5, повторяются до полного заполнения формируемого модуля.
Далее весь процесс повторяется до тех пор, пока не будет сформирован (-1) модуль. Последний же -й полностью включает в себя множество , так как
.
Выполнение компоновки.
В данной электрической функциональной схеме элементы типа И-НЕ заменим элементами 2И-НЕ, в целях уменьшения количества микросхем и себестоимости платы. Данную электрическую функциональную схему разбиваем на 3 блока. Далее выполняем компоновку для каждого блока, для чего представляем их в виде графов, где множеству вершин соответствуют элементы электрической схемы блока, а множество ребер электрическим связям между этими элементами.
Расчеты для первого блока:
Чертим граф для элементов типа 3И-НЕ:
Рис.1
Составляем матрицу смежности
| Т1 |
Т2 |
Т3 |
Т4 |
Т5 |
Т6 |
Т7 |
Т8 |
Т9 |
Т10 |
Т11 |
p |
|
| Т1 |
0 |
0 |
2 |
0 |
0 |
1 |
2 |
0 |
0 |
1 |
0 |
6 |
| Т2 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
2 |
0 |
0 |
5 |
| Т3 |
2 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
5 |
| Т4 |
0 |
1 |
0 |
0 |
2 |
0 |
0 |
1 |
1 |
0 |
0 |
5 |
| Т5 |
0 |
1 |
0 |
2 |
0 |
1 |
0 |
1 |
2 |
0 |
0 |
7 |
| Т6 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
7 |
| Т7 |
2 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
6 |
| Т8 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
8 |
| Т9 |
0 |
2 |
0 |
1 |
2 |
0 |
0 |
1 |
0 |
1 |
0 |
7 |
| Т10 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
7 |
| Т11 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
3 |
За базисную принимаем максимально связанную вершину, т.е. Т8. Она связана с вершинами Т2, Т4, Т5, Т6, Т7, Т9, Т10, Т11.Считаем функционал:
F2
=5-1=4; F4
=5-1=4; F5
=7-1=6; F6
=7-1=6;
F7
=6-1=5; F9
=7-1=6; F10
=7-1=6; F11
=3-1=2.
Выбираем Т11 т.к.
F
11 минимально
| Т1 |
Т2 |
Т3 |
Т4 |
Т5 |
Т6 |
Т7 |
Т9 |
Т10 |
Т811
|
p |
|
| Т1 |
0 |
0 |
2 |
0 |
0 |
1 |
2 |
0 |
1 |
0 |
6 |
| Т2 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
2 |
0 |
1 |
5 |
| Т3 |
2 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
5 |
| Т4 |
0 |
1 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
1 |
5 |
| Т5 |
0 |
1 |
0 |
2 |
0 |
1 |
0 |
2 |
0 |
1 |
7 |
| Т6 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
2 |
7 |
| Т7 |
2 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
6 |
| Т9 |
0 |
2 |
0 |
1 |
2 |
0 |
0 |
0 |
1 |
1 |
7 |
| Т10 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
2 |
7 |
| Т811
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
2 |
11 |
За базисную принимаем максимально связанную вершину, т.е. Т811
. Она связана с вершинами Т2, Т4, Т5, Т6, Т7, Т9, Т10.Считаем функционал:
F2
=5-1=4; F4
=5-1=4; F5
=7-1=6; F6
=7-2=5;
F7
=6-1=5; F9
=7-1=6; F10
=7-2=5.
Выбираем Т2 т.к. F2
минимально и с минимальным порядковым номером.
| Т1 |
Т3 |
Т4 |
Т5 |
Т6 |
Т7 |
Т9 |
Т10 |
Т2811
|
p |
|
| Т1 |
0 |
2 |
0 |
0 |
1 |
2 |
0 |
1 |
0 |
6 |
| Т3 |
2 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
5 |
| Т4 |
0 |
0 |
0 |
2 |
0 |
0 |
1 |
0 |
2 |
5 |
| Т5 |
0 |
0 |
2 |
0 |
1 |
0 |
2 |
0 |
2 |
7 |
| Т6 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
2 |
7 |
| Т7 |
2 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
6 |
| Т9 |
0 |
0 |
1 |
2 |
0 |
0 |
0 |
1 |
3 |
7 |
| Т10 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
2 |
7 |
| Т2811
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
4 |
16 |
В результате проведения процесса последовательной компоновки конструктивных узлов РЭА, получили электрическую принципиальную схему состоящую из четырёх микросхем К155ЛА4 , DD1={2,8,11}, DD2={4,5,9}, DD3={1,3,6}, DD4={7,10};трёх К155ЛА3 DD5={3,7,8,9},DD6={1,2,4,6}, DD7={5,10}, четырёх К155ЛР1 DD8={4,6}, DD9={2,7}, DD10={3,5}, DD11={1}.
Схема электрическая принципиальная приведена в приложении 1. По этой схеме построим граф (рис. 2).
Рис.2
2. Размещение элементов на плате
2.1 Краткое описание алгоритма последовательной установки элементов РЭА
Алгоритм последовательной установки РЭА не требует первоначального размещения элементов. Сущность этого этапа состоит в последовательном закреплении элементов РЭА на монтажной плате относительно каких-либо ранее закрепленных элементов. При этом из числа не размещенных элементов выбирается тот элемент, для которого характеристика, связанная с длиной связи относительно ранее размещенных элементов, оказывается наилучшей. В качестве первоначально закрепленных на монтажной плоскости конструктивных элементов обычно выбирают разъемы. В связи с этим на монтажной плоте первыми размещаются элементы, имеющие максимальное количество связей с разъемами.
Вся площадь платы разбивается координатной сеткой на отдельные ячейки, линейные размеры которых больше или равны установочным размерам элементов. Вершины графа, соответствующие разъему, отображаются на подмножество мест, расположенных на одном из краев монтажной платы. Очередная вершина выбирается по максимальному количеству связей с уже размещенными вершинами, и помещаются в свободную соседнюю позицию или в такую позицию из числа свободных, которая обеспечивает минимальную длину связей между размещаемой вершиной и уже размещенными вершинами графа.
В качестве исходных данных необходимо ввести данные о модели монтажной платы.
Ограничения на расположения элементов, на расположение разъема, а так же данные о связях между размещенными элементами.
В качестве критерия выбора очередного элемента, подлежащего установке на плате, используется коэффициент относительной взвешенности связности:
, (8)
где -количество связей i-ого элемента с установленным ранее на плате j-ым элементом , порядковый номер которого-m;
g -количество уже закрепленных на плате элементов;
Vi –общее число связей I-ого элемента со всеми остальными элементами множества X.
Последовательность работы алгоритма:
Формируется массив номеров элементов и подготавливается (обнуляется) массив установочных мест.
Выбираем за исходное размещение местонахождение разъема и элементов, закрепляемых на установочных местах платы по требованию разработчика.
В множестве размещаемых элементов, обнуляем элементы размещенные по требованию разработчика.
Выбираем из множества N еще не размещенный элемент, для которого значение Ki максимально. Если ряд элементов имеет одинаковое значение Ki , то выбираем элемент с минимальным порядковым номером.
Для множества незанятых позиций ряда определяем позицию, закрепление которой элемента Ni приводит к минимальному приращению функции цели.
(9)
где dij – элемент матрицы расстояний.
Общее суммарное расстояние от закрепляемого элемента к закрепленным будет минимальным. Проверяем не является ли данная позиция областью, запрещенной для размещения элементов.
Производим закрепление элемента Ni за свободной позицией ряда, в которой обеспечивается минимальное приращение функции цели.
Проверяем все ли элементы размещены на плате, если нет, то переходим к пункту 4.
Выполнение размещения
| DD1
|
DD2
|
DD3
|
DD4
|
DD5
|
DD6
|
DD7
|
DD8
|
DD9
|
DD10
|
DD11
|
X1 |
p |
|
| DD1
|
0 |
7 |
2 |
3 |
7 |
3 |
2 |
2 |
2 |
1 |
3 |
3 |
35 |
| DD2
|
7 |
0 |
1 |
1 |
3 |
7 |
0 |
6 |
0 |
0 |
0 |
3 |
28 |
| DD3
|
2 |
1 |
0 |
7 |
2 |
6 |
2 |
2 |
0 |
0 |
1 |
3 |
26 |
| DD4
|
3 |
1 |
7 |
0 |
1 |
4 |
2 |
4 |
0 |
0 |
1 |
3 |
30 |
| DD5
|
7 |
3 |
2 |
1 |
0 |
12 |
5 |
0 |
2 |
0 |
0 |
3 |
35 |
| DD6
|
3 |
7 |
6 |
4 |
12 |
0 |
6 |
0 |
0 |
0 |
0 |
4 |
42 |
| DD7
|
2 |
0 |
2 |
2 |
5 |
6 |
0 |
0 |
0 |
1 |
0 |
1 |
19 |
| DD8
|
2 |
6 |
2 |
4 |
0 |
0 |
0 |
0 |
10 |
9 |
2 |
0 |
35 |
| DD9
|
2 |
0 |
0 |
0 |
2 |
0 |
0 |
10 |
0 |
9 |
0 |
0 |
23 |
| DD10
|
1 |
0 |
0 |
0 |
0 |
0 |
1 |
9 |
9 |
0 |
0 |
0 |
20 |
| DD11
|
3 |
0 |
1 |
1 |
0 |
0 |
0 |
2 |
0 |
0 |
0 |
2 |
9 |
| X1 |
3 |
3 |
3 |
3 |
3 |
4 |
1 |
0 |
0 |
0 |
2 |
0 |
21 |
По графу (рис.2) строим матрицу смежности и определяем степень каждой вершины.
Составляем модель монтажной платы:
| 1 |
2 |
5 |
8 |
11 |
|
| 3 |
6 |
9 |
12 |
||
| 4 |
7 |
10 |
13 |
Рис3
Затем по модели монтажной платы составляем матрицу расстояний.
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
p |
|
| 1 |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
3 |
3 |
3 |
4 |
4 |
4 |
30 |
| 2 |
1 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
4 |
3 |
4 |
5 |
31 |
| 3 |
1 |
1 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
4 |
3 |
4 |
27 |
| 4 |
1 |
2 |
1 |
0 |
3 |
2 |
1 |
4 |
3 |
2 |
5 |
4 |
3 |
31 |
| 5 |
2 |
1 |
2 |
3 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
4 |
26 |
| 6 |
2 |
2 |
1 |
2 |
1 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
22 |
| 7 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
3 |
2 |
1 |
4 |
3 |
2 |
26 |
| 8 |
3 |
2 |
3 |
4 |
1 |
2 |
3 |
0 |
1 |
2 |
1 |
2 |
3 |
27 |
| 9 |
3 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
1 |
2 |
1 |
2 |
23 |
| 10 |
3 |
4 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
3 |
2 |
1 |
27 |
| 11 |
4 |
3 |
4 |
5 |
2 |
3 |
4 |
1 |
2 |
3 |
0 |
1 |
2 |
29 |
| 12 |
4 |
4 |
3 |
4 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
1 |
30 |
| 13 |
4 |
5 |
4 |
3 |
4 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
34 |
2.2.1 В качестве первого размещённого элемента примем разъём Х1 (позиция 1)
Рассчитываем коэффициенты относительной внешней связанности по формуле (8).
.
На данном этапе будем размещать элемент с максисальным значением Фi
,
т. е. микросхему DD11.
Рассчитываем прирощение функции цели для незанятых ячеек печатной платы по формуле (9).
ΔF2
=2 ΔF3
=2 ΔF4
=2 ΔF5
=4 ΔF6
=4 ΔF7
=4 ΔF8
=6 ΔF9
=6 ΔF10
=6 ΔF11
=8 ΔF12
=8.
Выбираем минимальное значение Fi
,
т. е. вторую.
2.2.2.В качестве первого размещённого элемента примем разъём Х1 (позиция 1) и
DD
11 (позиция 2)
Рассчитываем коэффициенты относительной внешней связанности по формуле (8).
.
На данном этапе будем размещать элемент с максисальным значением Фi
,
т. е. микросхему DD1.
Рассчитываем прирощение функции цели для незанятых ячеек печатной платы по формуле (9).
ΔF3=С1х1d13+C111d23=3*1+3*1=6;
ΔF4= С1х1d14+C111d24=3*1+3*2=9;
ΔF5= С1х1d15+C111d25=3*2+3*1=9;
ΔF6= С1х1d16+C111d26=3*2+3*2=12;
ΔF7= С1х1d17+C111d27=3*2+3*3=15;
ΔF8= С1х1d18+C111d28=3*3+3*2=15;
ΔF9= С1х1d19+C111d29=3*3+3*3=18;
ΔF10= С1х1d110+C111d210=3*3+3*4=21;
ΔF12= С1х1d112+C111d212=3*4+3*4=24;
Выбираем минимальное значение Fi
,
т. е. третью.
Результаты размещения
| Микросхема |
Номер посадочного места |
| Х1 |
1 |
| DD1 |
3 |
| DD2 |
4 |
| DD3 |
8 |
| DD4 |
9 |
| DD5 |
5 |
| DD6 |
6 |
| DD7 |
7 |
| DD8 |
10 |
| DD9 |
11 |
| DD10 |
12 |
| DD11 |
2 |
3. Трассировка цепей питания и земли с использованием алгоритма построения кратчайших связывающих цепей
Трассировка – прокладка электрических трасс, проводов (при проводном монтаже), дорожек.
Трассировку соединений осуществляют с помощью алгоритмов, основанных на методах динамического программирования. Общим для этих алгоритмов является разбиение монтажного поля на ячейки, размер и форма которых определяют плотность и конфигурацию печатных проводников. Наибольшее распространение на практике получило разбиение рабочего поля на правильные квадраты, что обеспечивает простую адресацию ячеек в прямоугольной системе координат и привычную форму соединений. Размеры ячеек определяются конструктивно – технологическими требованиями, предъявляемыми к печатному монтажу. Так как в каждой ячейке обычно размещается только один вывод или печатный проводник, максимальные размеры ячеек определяются допустимой точностью воспроизведения проводников.
Алгоритм Краскала (цепи земли)
Строится кратчайшая связывающая сеть путем последовательного присоединения к ней ребер, удовлетворяющих следующим условиям:
- ребро минимально
- ребро инцидентно только по одной вершине
- присоединение рассматриваемого ребра не приводит к повышению степени любой вершины больше заданного числа
Последовательность:
- на множестве вершин строится полный граф, задаются матрица расстояний
- упорядочиваются ребра в порядке возрастания их длины
Построение КСС осуществляется путем последовательного выбора ребер удовлетворяющих трем условиям, при этом формируется массив индексов ребер. Условием получения покрывающего дерева является вычерчивание всех номеров вершин в массиве номеров.
1) Матрица расстояний
| x1 |
DD11 |
DD5 |
DD3 |
DD9 |
| DD1 |
DD6 |
DD4 |
DD10 |
|
| DD2 |
DD7 |
DD8 |
Рис.4
Матрица длин
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
p |
|
| 1 |
0 |
1 |
1 |
1 |
2 |
2 |
2 |
3 |
3 |
3 |
4 |
4 |
30 |
| 2 |
1 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
4 |
3 |
4 |
31 |
| 3 |
1 |
1 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
4 |
3 |
27 |
| 4 |
1 |
2 |
1 |
0 |
3 |
2 |
1 |
4 |
3 |
2 |
5 |
4 |
31 |
| 5 |
2 |
1 |
2 |
3 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
3 |
26 |
| 6 |
2 |
2 |
1 |
2 |
1 |
0 |
1 |
2 |
1 |
2 |
3 |
2 |
22 |
| 7 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
3 |
2 |
1 |
4 |
3 |
26 |
| 8 |
3 |
2 |
3 |
4 |
1 |
2 |
3 |
0 |
1 |
2 |
1 |
2 |
27 |
| 9 |
3 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
1 |
2 |
1 |
23 |
| 10 |
3 |
4 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
3 |
2 |
27 |
| 11 |
4 |
3 |
4 |
5 |
2 |
3 |
4 |
1 |
2 |
3 |
0 |
1 |
29 |
| 12 |
4 |
4 |
3 |
4 |
3 |
2 |
3 |
2 |
1 |
2 |
1 |
0 |
30 |
2) строки упорядочиваются по возрастанию массив ребер число ребер
В результате трассировки цепей земли будет иметь вид:
| x1 |
DD11 |
DD5 |
DD3 |
DD9 |
|
| DD1 |
DD6 |
DD4 |
DD10 |
||
| DD2 |
DD7 |
DD8 |
Рис.5
Алгоритм Прима (цепи питания)
В алгоритме Прима производится манипуляция с матрицей расстояний. Например: выбирается произвольная вершина (строка матрицы), в ней просматриваются элементы и выбирается наименьший присоединяется ближайшая вершина после чего обнуляется столбец, соответствующий присоединенной вершине. На следующем этапе просматриваются уже две строки и процедура повторяется. Проверка ограничения максимально допустимой степени вершины осуществляется аналогично алгоритму Краскала (анализируется массив индексов выбранных вершин)
1) матрица расстояний используется та же, что и в алгоритме Краскала (см. выше)
2) выбирается произвольно вершина (например № 1), где минимум элемент
В результате всех этих действий получаем трассировку цепей питания в следующем виде.
| x1 |
DD11 |
DD5 |
DD3 |
DD9 |
| DD1 |
DD6 |
DD4 |
DD10 |
|
| DD2 |
DD7 |
DD8 |
Рис.6
4. Трассировка сигнальных цепей с помощью волновых алгоритмов
Данный алгоритм является классическим примером использования методов динамического программирования для решения задачи трассировки печатных соединений. Основные принципы построения трасс с помощью волнового алгоритма сводятся к следующему.
Все ячейки монтажного поля подразделяют на занятые и свободные. Занятыми считаются ячейки, в которых уже расположены проводники, построенные на предыдущих шагах, или находятся монтажные выводы элементов, а также ячейки, соответствующие границе платы запрещенным для прокладывания проводников участкам. Каждый раз при проведении новой трассы можно использовать лишь свободные ячейки, число которых по мере проведения трасс сокращается.
На множестве ячеек (свободных) коммутационного поля моделируют волну влияния из одной ячейки в другую, соединяемых впоследствии одним проводником. Первую ячейку, в которой зарождается волна влияний называют источником, а вторую – приемником волны. Чтобы иметь возможность следить за прохождением фронта волны влияний, его фрагментом на каждом этапе присваивают некоторые веса:
(10)
где и - веса ячеек k – го и (k-1) –го фронтов;
φ – числовая характеристика, зависящая от выбранного критерия оптимизации;
На накладывают одно ограничение – веса ячеек предыдущих фронтов не должны быть больше весов ячеек последующих фронтов. Фронт распространяется только на соседние ячейки, которые имеют с ячейками предыдущего фронта либо общую сторону, либо хотя бы одну общую точку. Процесс распространения волны продолжается до тех пор, пока ее расширяющийся фронт не достигнет приемника или на θ шаге не найдется ни одной свободной ячейки, которая могла бы быть включена в очередной фронт, что соответствует случаю невозможности проведения трассы при заданных ограничениях.
Если в результате распространения волна достигла приемника, то осуществляют «проведение пути», которое заключается в движении от приемника к источнику по пройденным на этапе распространения волны ячейкам, следя за тем, чтобы значение монотонно убывали. В результате получают путь, соединяющий эти две точки. Из описания алгоритма следует, мято все условия, необходимые для проведения пути, закладываются в правила приписания веса ячейкам.
Приведем два примера трассировки соединений с помощью волнового алгоритма ЛИ.
Чтобы исключить неопределенность при проведении пути для случая, когда несколько ячеек имеют одинаковый минимальный вес, вводят понятие путевых координат задающих предпочтительность проведения трассы.
В приложении 5 представлена плата с проведенной трассировкой.
| 7 |
6 |
5 |
4 |
3 |
4 |
5 |
6 |
|||||||||
| 6 |
5 |
4 |
3 |
2 |
3 |
4 |
5 |
|||||||||
| 5 |
4 |
3 |
2 |
1 |
2 |
3 |
4 |
|||||||||
| 4 |
3 |
2 |
1 |
0 |
1 |
2 |
3 |
|||||||||
| 5 |
4 |
3 |
4 |
|||||||||||||
| 6 |
5 |
6 |
7 |
8 |
4 |
5 |
||||||||||
| 7 |
6 |
7 |
8 |
9 |
5 |
6 |
||||||||||
| 8 |
7 |
8 |
9 |
10 |
6 |
7 |
||||||||||
| 9 |
8 |
9 |
10 |
11 |
9 |
8 |
||||||||||
| 10 |
9 |
10 |
11 |
12 |
11 |
10 |
9 |
|||||||||
| 4 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
||||||||
| 10 |
9 |
8 |
7 |
6 |
5 |
3 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
||
| 11 |
4 |
2 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
||||||
| 12 |
13 |
14 |
17 |
3 |
2 |
1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
6 |
||
| 13 |
14 |
15 |
16 |
5 |
6 |
7 |
8 |
|||||||||
| 14 |
15 |
16 |
15 |
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
7 |
8 |
9 |
|
Литература
1. Мельничук В.В. «Конспект лекций по АКИТ и ПРЭС» БГУИР Минск 2000г.
2. Деньдобренько Б.Н. «Автоматизация конструирования РЭА» Москва 1980г.
3. Методическое пособие к лабораторному практикуму по курсу «Математическое обеспечение конструкций и технологии проектирования с применением САПР» Минск 1987г.