Автоматизация проектирования изделий электронной техники — страница 6

  • Просмотров 3880
  • Скачиваний 53
  • Размер файла 116
    Кб

С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. Трассировка цепей питания и земли с использованием алгоритма построения кратчайших связывающих цепей Трассировка – прокладка электрических трасс, проводов (при проводном монтаже), дорожек. Трассировку соединений

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

привычную форму соединений. Размеры ячеек определяются конструктивно – технологическими требованиями, предъявляемыми к печатному монтажу. Так как в каждой ячейке обычно размещается только один вывод или печатный проводник, максимальные размеры ячеек определяются допустимой точностью воспроизведения проводников. Алгоритм Краскала (цепи земли) Строится кратчайшая связывающая сеть путем последовательного присоединения к

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

удовлетворяющих трем условиям, при этом формируется массив индексов ребер. Условием получения покрывающего дерева является вычерчивание всех номеров вершин в массиве номеров. Матрица расстояний 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 Алгоритм Прима (цепи питания) В алгоритме Прима производится манипуляция с матрицей расстояний. Например: выбирается произвольная вершина (строка матрицы), в ней просматриваются элементы и выбирается наименьший присоединяется ближайшая вершина после чего