2.2.1 В качестве первого размещенного элемента принимаем разьем X1 (позиция 1). Рассчитываем коэффициенты относительной взвешенной связности по формуле (10)
Ф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)
F2 = 2*1 = 2, F3 = 2*1 = 2, F4 = 2*1 = 2, F5 = 2*2 = 4,
F6 = 2*2 = 4, F7 = 2*2 = 4,F8 = 2*3 = 6,F9 = 2*4 = 8,F10 = 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.
F3 = 3*1+2*1 = 5,
F4 = 3*1+2*2 = 7, F5 = 3*2+2*1 = 8, F6 = 3*2+2*2 = 10,
F7 = 3*2+2*3 = 12,F8 = 3*3+2*2 = 13, F9 = 3*4+2*3 = 18,
F10 = 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.
F4 = 1*1+0*2+2*1 = 3, F5 = 1*2+0*1+2*2 = 6, F6 = 1*2+0*2+2*1 = 4,
F7 = 1*2+0*3+2*2 = 6,F8 = 1*3+0*2+2*3 = 9, F9 = 1*4+0*3+2*4 = 12,
F10 = 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.
F5 = 4*2+0*1+4*2+2*3 = 22, F6 = 4*2+0*2+4*1+2*2 = 16,
F7 = 4*2+0*3+4*2+2*1 = 18,F8 = 4*3+0*2+4*3+2*4 = 32,
F9 = 4*4+0*3+4*4+2*3 = 38, F10 = 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.
F5 = 3*2+2*1+3*2+1*3+6*4 = 41, F6 = 3*2+2*2+3*1+1*2+6*1 = 21,
F8 = 3*3+2*2+3*3+1*4+6*3 = 44, F9 = 3*4+2*3+3*4+1*3+6*2 = 45,
F10 = 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.
F5 = 3*2+2*1+3*2+1*3+3*4+5*3 = 44,
F6 = 3*2+2*2+3*1+1*2+3*1+5*2 = 28,
F8 = 3*3+2*2+3*3+1*4+3*3+5*2 = 45,
F9 = 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.
F6 = 4*2+0*2+5*1+0*2+6*1+2*1+4*2 = 29,
F8 = 4*3+0*2+5*3+0*4+6*1+2*3+4*2 = 47,
F9 = 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
Трассировка – прокладка электрических трасс (проводов при проводном монтаже и печатных соединений при печатном монтаже), соответствующих принципиальной электрической схеме.
В алгоритме Краскала кратчайшую связывающую сеть (КСС) строят путем последовательного присоединения к ним ребер, удовлетворяющих следующим условиям:
1.Ребра должны быть кратчайшими.
2.Ребро не должно соединять изолированные вершины.
3.Ребро не должно образовывать циклы.
4.Присоединение рассматриваемого ребра не приводит к повышению степени вершины выше заданного числа.
На первом этапе в данном множестве вершин строится полный граф и задается матрица расстояния. На втором этапе упорядочиваются ребра в порядке возрастания их длины, и на последнем этапе построение КСС осуществляется последовательным выбором ребер, удовлетворяющим 4-м условиям, при этом формируется массив индексов ребер, которые анализируются по этим 4-м условиям.
Расположим расстояния между контактами в порядке возрастания, используя рисунок 5 и таблицу 11 для расстояния равного 1,2,3,4:
1: d1-2, d1-3, d1-4, d2-3, d2-5, d3-4, d3-6, d4-7, d5-6, d5-8, d6-7, d6-9, d7-10, d8-9, d9-10;
2: d1-5, d1-6, d1-7, d2-4, d2-6, d2-8, d3-5, d3-7, d4-6, d4-10, d5-9, d6-8, d6-10, d7-9, d8-10;
3: d1-8, d1-10, d2-7, d2-9, d3-8, d3-10, d4-5, d4-9, d5-10, d7-8;
4: d1-9, d2-10, d3-9, d4-8, d5-7.
Рис.7
Выбираем ребра, отвечающие условиям алгоритма Краскала. Получаем:
d1-2, d1-3, d1-4, d2-5,d4-7, d5-8, d7-10, d8-9.
Рис. 8
В алгоритме Прима, в отличие от алгоритма Краскала, построение КСС ведется путем присоединения ближайших изолированных вершин, при этом все манипуляции проводятся лишь с матрицей расстояний.
Цепи питания будут размещаться в другом слое.
Фиксируем произвольную строку в таблице 11, например 1.Минимальное расстояние равное 1 в первой строке находится во 2,3,4 столбце. Минимальное расстояние между первым и вторым контактом. Выбираем минимальный по счёту столбец, – вычёркиваем второй столбец.
Далее фиксируем вторую строку. Минимальное расстояние равное 1 в первой и второй строке находится во 3,4 столбце первой строки. Выбираем минимальный по счёту столбец, – вычёркиваем третий столбец.
Далее аналогично.
Фиксируем строку 3. Минимальное расстояние в строке 1 в столбце 4. Вычёркиваем столбец 4.
Фиксируем строку 4. Минимальное расстояние в строке 2 в столбце 5. Вычёркиваем столбец 5.
Фиксируем строку 5. Минимальное расстояние в строке 3 в столбце 6, но т.к. 6 –запрещённое место, выбираем следующее минимальное значение в строке 4 в столбце 7. Вычёркиваем столбец 7.
Фиксируем строку 7. Минимальное расстояние в строке 5 в столбце 8. Вычёркиваем столбец 8.
Фиксируем строку 8. Минимальное расстояние в строке 7 в столбце 10. Вычёркиваем столбец 10.
Фиксируем строку 10. Минимальное расстояние в строке 8 в столбце 9. Вычёркиваем столбец 9.
В результате получаем следующую цепь d1-2, d1-3, d1-4, d2-5,d4-7, d5-8, d7-10, d8-9. (рис.9).
Основные принципы построение трасс с помощью волнового алгоритма сводятся к следующему.
Все ячейки монтажного поля подразделяются на занятые и свободные. Занятыми считаются ячейки, в которых уже расположены проводники, построенные на предыдущих шагах, или находятся монтажные выводы элементов, а также ячейки, соответствующие границе плат и запрещенным для прокладывания проводников участкам. Каждый раз при проведении новой трассы можно использовать лишь свободные ячейки, число которых по мере проведения трасс сокращается.
На множестве свободных ячеек коммутационного поля моделируют волну влияния из одной ячейки в другую, соединяемых впоследствии общим проводником. Первую ячейку, в которой зарождается волна, называют источником, а вторую - приемником волны. Чтоюы иметь возможность следить за прохождением фронта волны влияний, его фрагментом на кождом этапе присваивают некоторые веса:
Рк = Рк-1 + Р, (12)
где Рк и Рк-1 –веса ячеек К-го и (К-1)-го фронтов;
Р–числовая характеристика, зависящая от выбранного критерия
отимизации.
На Рк накладывают одно ограничение – веса ячеек предыдущих фронтов не должны быть больше весов ячеек последующих фронтов. Фронт распространяется только на соседние ячейки, которые имеют с ячейками предыдущего фронта либо общую сторону, либо хотя бы одну общую точку. Процесс распространения волны продолжается до тех пор, пока её расширяющийся фронт не достигнет приемника или на iом шаге не найдётся ни одной свободной ячейки, которая могла бы быть включена в очередной фронт, что соответствует случаю невозможности проведения трассы при заданных ограничениях.
Если в результате распространения волна достигла приемника, то осуществляют ‘проведение пути’, которое заключается в движении от приемника к источнику по пройденным на этапе распространения волны ячейкам, следя за тем, чтобы значение волны монотонно убывало. В результате получают путь, соединяющий эти две точки. Из описания алгоритма следует, что все условия необходимые для проведения пути закладываются в правило приписания веса ячейкам.
Пример трассировки сигнальных цепей по волновому алгоритму.
Требуется соединить контакты 1,2,3 и 4. Волну будем распространять из первого контакта рис.10.
В результате получаем цепь, изображенную на рис.11.
Рис.11
Результаты трассировки всех цепей представлены в приложении 3.
В результате выполнения курсового проекта был разработан печатный модуль РЭС с использованием учебных алгоритмов САПР.
Также по исходным данным была выполнена задача компоновки для функциональной схемы с использованием последовательного алгоритма. Была выполнено размещение элементов в принципиальной электрической схеме с использованием последовательного алгоритма. Была выполнена трассировка цепей питания и земли с использованием алгоритма построения кратчайших связывающих сетей и волнового алгоритма, т.е. трассировка цепей земли по алгоритму Краскала и трассировка цепей питания по алгоритму Прима, а также трассировка сигнальных цепей с помощью волновых алгоритмов.
1. Деньдобренко Б.Н., Малика А.С. Автоматизация конструирования РЭА: Учебник для вузов. - М., Высш. школа,1980.
2. Основы проектирования микроэлектронной аппаратуры./Под ред. Б.Ф. Высоцкого. М., 1977.
3. Теория и методы автоматизации проектирования вычислительных систем./Под ред. М. Брейера. М., 1977.
Страницы: 1, 2, 3, 4, 5, 6
