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

Ф_D1= 2/9 = 0,222, Ф_D2= 3/27 = 0,111, Ф_D3= 3/27 = 0,111, Ф_D4= 3/24 = 0,125,

Ф_D5= 3/26 = 0,115, Ф_D6= 4/23 = 0,174, Ф_D7= 4/27 = 0,148, Ф_D8= 1/8 = 0,125.

На данном этапе будем размещать элемент с максимальным значением

, т.е. элемент DD1.

Рассчитываем приращение функции цели для незанятых ячеек печатной платы по формуле (11)

DF₂ = 2*1 = 2, DF₃ = 2*1 = 2, DF₄ = 2*1 = 2, DF₅ = 2*2 = 4,

DF₆ = 2*2 = 4, DF₇ = 2*2 = 4,DF₈ = 2*3 = 6,DF₉ = 2*4 = 8,DF₁₀ = 2*3 = 6.

Выбираем минимальное значение из

. Это соответствует 2,3 и 4 позициям. Выбираем позицию с минимальным номером, т.е. вторую.

2.2.2 В качестве размещенных элементов принимаем разьем X1 (позиция 1) и DD1 (позиция 2). Рассчитываем коэффициенты относительной взвешенной связности по формуле (10)

Ф_D2= (2+3)/27 = 0,185, Ф_D3= (2+3)/27 = 0,185,

Ф_D4= (1+3)/24 = 0,167, Ф_D5= (2+3)/26 = 0,192, Ф_D6= (0+4)/23 = 0,174,

Ф_D7= (0+4)/27 = 0,148, Ф_D8= (0+1)/8 = 0,125.

На данном этапе будем размещать элемент с максимальным значением

, т.е. элемент DD5.

Рассчитываем приращение функции цели для незанятых ячеек печатной платы по формуле (11)

DF₃ = 3*1+2*1 = 5,

DF₄ = 3*1+2*2 = 7, DF₅ = 3*2+2*1 = 8, DF₆ = 3*2+2*2 = 10,

DF₇ = 3*2+2*3 = 12,DF₈ = 3*3+2*2 = 13, DF₉ = 3*4+2*3 = 18,

DF₁₀ = 3*3+2*4 = 17.

Выбираем минимальное значение из

. Это соответствует позиции 3.

2.2.3 В качестве размещенных элементов принимаем разьем X1 (позиция 1), DD1 (позиция 2) и DD5 (позиция 3). Рассчитываем коэффициенты относительной взвешенной связности по формуле (10)

Ф_D2= (2+3+3)/27 = 0,296, Ф_D3= (2+3+3)/27 = 0,296,

Ф_D4= (1+4+3)/24 = 0,333, Ф_D6= (0+4+4)/23 = 0,348,

Ф_D7= (0+4+5)/27 = 0,333, Ф_D8= (0+1+2)/8 = 0,375.

На данном этапе будем размещать элемент с максимальным значением

, т.е. элемент DD8.

Рассчитываем приращение функции цели для незанятых ячеек печатной платы по формуле (11)

DF₄ = 1*1+0*2+2*1 = 3, DF₅ = 1*2+0*1+2*2 = 6, DF₆ = 1*2+0*2+2*1 = 4,

DF₇ = 1*2+0*3+2*2 = 6,DF₈ = 1*3+0*2+2*3 = 9, DF₉ = 1*4+0*3+2*4 = 12,

DF₁₀ = 1*3+0*4+2*3 = 9.

Выбираем минимальное значение из

. Это соответствует позиции 4.

2.2.4 В качестве размещенных элементов принимаем разьем X1 (позиция 1), DD1 (позиция 2), DD5 (позиция 3), DD8 (позиция 4). Рассчитываем коэффициенты относительной взвешенной связности по формуле (10)

Ф_D2= (2+3+1+3)/27 = 0,333, Ф_D3= (2+3+1+3)/27 = 0,333,

Ф_D4= (1+4+1+3)/24 = 0,375, Ф_D6= (0+4+2+4)/23 = 0,435,

Ф_D7= (4+5)/27 = 0,333.

На данном этапе будем размещать элемент с максимальным значением

, т.е. элемент DD6.

Рассчитываем приращение функции цели для незанятых ячеек печатной платы по формуле (11)

DF₅ = 4*2+0*1+4*2+2*3 = 22, DF₆ = 4*2+0*2+4*1+2*2 = 16,

DF₇ = 4*2+0*3+4*2+2*1 = 18,DF₈ = 4*3+0*2+4*3+2*4 = 32,

DF₉ = 4*4+0*3+4*4+2*3 = 38, DF₁₀ = 4*3+0*4+4*3+2*2 = 28.

Выбираем минимальное значение из

. Это соответствует 6 и 7 позициям. Но позиция 6 запрещенная, поэтому выбираем позицию 7.

2.2.5 В качестве размещенных элементов принимаем разьем X1 (позиция 1), DD1 (позиция 2), DD5 (позиция 3), DD8 (позиция 4),

DD6 (позиция 7). Рассчитываем коэффициенты относительной взвешенной связности по формуле (10)

Ф_D2= (2+3+3+1+3)/27 = 0,444, Ф_D3= (2+3+6+1+3)/27 = 0,555,

Ф_D4= (1+4+2+1+3)/24 = 0,458,

Ф_D7= (5+2+4)/27 = 0,407.

На данном этапе будем размещать элемент с максимальным значением

, т.е. элемент DD3.

Рассчитываем приращение функции цели для незанятых ячеек печатной платы по формуле (11)

DF₅ = 3*2+2*1+3*2+1*3+6*4 = 41, DF₆ = 3*2+2*2+3*1+1*2+6*1 = 21,

DF₈ = 3*3+2*2+3*3+1*4+6*3 = 44, DF₉ = 3*4+2*3+3*4+1*3+6*2 = 45,

DF₁₀ = 3*3+2*4+3*3+1*2+6*1 = 34.

Выбираем минимальное значение из

. Это соответствует 6 и 10 позициям. Но позиция 6 запрещенная, поэтому выбираем позицию 10.

2.2.6 В качестве размещенных элементов принимаем разьем X1 (позиция 1), DD1 (позиция 2), DD5 (позиция 3), DD8 (позиция 4), DD6 (позиция 7), DD3 (позиция 10). Рассчитываем коэффициенты относительной взвешенной связности по формуле (10)

Ф_D2= (2+5+3+3+1+3)/27 = 0,63,

Ф_D4= (1+3+4+2+1+3)/24 = 0,583,

Ф_D7= (4+5+2+4)/27 = 0,555.

На данном этапе будем размещать элемент с максимальным значением

, т.е. элемент DD2.

Рассчитываем приращение функции цели для незанятых ячеек печатной платы по формуле (11)

DF₅ = 3*2+2*1+3*2+1*3+3*4+5*3 = 44,

DF₆ = 3*2+2*2+3*1+1*2+3*1+5*2 = 28,

DF₈ = 3*3+2*2+3*3+1*4+3*3+5*2 = 45,

DF₉ = 3*4+2*3+3*4+1*3+3*2+5*2 = 44.

Выбираем минимальное значение из

. Это соответствует 6 позиции. Но позиция 6 запрещенная, поэтому выбираем позицию 5.

2.2.7 В качестве размещенных элементов принимаем разьем X1 (позиция 1), DD1(позиция 2), DD5(позиция 3), DD8(позиция 4), DD6(позиция 7), DD3 (позиция 10), DD2 (позиция 5). Рассчитываем коэффициенты относительной взвешенной связности по формуле (10)

Ф_D4= (1+4+3+4+2+1+3)/24 = 0,75,

Ф_D7= (0+6+4+5+2+0+4)/27 = 0,778.

На данном этапе будем размещать элемент с максимальным значением

, т.е. элемент DD7.

Рассчитываем приращение функции цели для незанятых ячеек печатной платы по формуле (11)

DF₆ = 4*2+0*2+5*1+0*2+6*1+2*1+4*2 = 29,

DF₈ = 4*3+0*2+5*3+0*4+6*1+2*3+4*2 = 47,

DF₉ = 4*4+0*3+5*4+0*3+6*2+2*2+4*1 = 56.

Выбираем минимальное значение из

. Это соответствует 6 и 8 позициям. Но позиция 6 запрещенная, поэтому выбираем позицию 8.

2.2.8 В качестве размещенных элементов принимаем разьем X1 (позиция 1), DD1(позиция 2), DD5(позиция 3), DD8(позиция 4),

DD6(позиция 7), DD3(позиция 10), DD2(позиция 5), DD7(позиция 8).

DD4 ставим в позицию 9.

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

Таблица 12

Элемент	Номер посадочного места
X1	1
DD1	2
DD2	5
DD3	10
DD4	9
DD5	3
DD6	7
DD7	8
DD8	4

Рис.6

3. Трассировка цепей питания и земли

Трассировка – прокладка электрических трасс (проводов при проводном монтаже и печатных соединений при печатном монтаже), соответствующих принципиальной электрической схеме.

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

В алгоритме Краскала кратчайшую связывающую сеть (КСС) строят путем последовательного присоединения к ним ребер, удовлетворяющих следующим условиям:

1.Ребра должны быть кратчайшими.

2.Ребро не должно соединять изолированные вершины.

3.Ребро не должно образовывать циклы.

4.Присоединение рассматриваемого ребра не приводит к повышению степени вершины выше заданного числа.

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

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

Расположим расстояния между контактами в порядке возрастания, используя рисунок 5 и таблицу 11 для расстояния равного 1,2,3,4:

1: d_1-2, d_1-3, d_1-4, d_2-3, d_2-5, d_3-4, d_3-6, d_4-7, d_5-6, d_5-8, d_6-7, d_6-9, d_7-10, d_8-9, d_9-10;

2: d_1-5, d_1-6, d_1-7, d_2-4, d_2-6, d_2-8, d_3-5, d_3-7, d_4-6, d_4-10, d_5-9, d_6-8, d_6-10, d_7-9, d_8-10;

3: d_1-8, d_1-10, d_2-7, d_2-9, d_3-8, d_3-10, d_4-5, d_4-9, d_5-10, d_7-8;

4: d_1-9, d_2-10, d_3-9, d_4-8, d_5-7.

Рис.7

Выбираем ребра, отвечающие условиям алгоритма Краскала. Получаем:

d_1-2, d_1-3, d_1-4, d_2-5,d_4-7, d_5-8, d_7-10, d_8-9.

Рис. 8

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

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

Цепи питания будут размещаться в другом слое.

Фиксируем произвольную строку в таблице 11, например 1.Минимальное расстояние равное 1 в первой строке находится во 2,3,4 столбце. Минимальное расстояние между первым и вторым контактом. Выбираем минимальный по счёту столбец, – вычёркиваем второй столбец.