Трассировка шин «земля» и «питание» с использованием алгоритма по- строения КСС
Автор работы: Пользователь скрыл имя, 05 Декабря 2013 в 19:28, курсовая работа
Описание работы
Современные достижения науки и техники, возрастающая функцио-
нальность современных изделий требуют выполнения проектных работ
большого объѐма. Требования к качеству проектов, срокам их выполнения
оказываются всѐ более жѐсткими в условиях конкурентной борьбы за потре-
бителя. Удовлетворить эти требования, количественно увеличивая проекти-
ровщиков, невозможно, так как распараллеливание проектных работ не без-
гранично.
Решить проблему можно, внедряя в практику инженерного проекти-
рования методы и средства автоматизированного проектирования.
Цель автоматизации проектирования – повышение качества, снижение
материальных затрат, сокращение сроков проектирования и повышение про-
изводительности труда проектировщиков.
Содержание работы
Введение.................................................................................................................. 5
1 Покрытие электрической схемы и компоновка модулей микросхем при по-
мощи последовательного алгоритма компоновки................................................. 7
1.1 Покрытие электрической схемы..................................................................... 7
1.2 Общее описание алгоритма............................................................................. 7
1.3 Пошаговое описание алгоритма ..................................................................... 8
2 Размещение микросхем на плате....................................................................... 28
2.1 Обще описание алгоритма............................................................................... 28
2.2 Пошаговая работа алгоритма.......................................................................... 29
2.3 Расчет площади печатной платы .................................................................... 39
3 Трассировка шин «земля» и «питание» с использованием алгоритма по-
строения КСС ...................................................................................................... 41
3.1 Трассировка шины «земля» с помощью алгоритма Краскала..................... 41
3.2 Трассировка шины «питание» с помощью алгоритма Прима..................... 42
4 Алгоритмы трассировки печатного монтажа................................................... 48
4.1 Волновой алгоритм Ли .................................................................................... 49
Заключение ................................................................................................................ 54
Список использованной литературы..................
Файлы: 1 файл
4
СОДЕРЖАНИЕ
Введение.................................................................................................................. 5
1 Покрытие электрической схемы и компоновка модулей микросхем при по-
мощи последовательного алгоритма компоновки................................................. 7
1.1 Покрытие электрической схемы..................................................................... 7
1.2 Общее описание алгоритма............................................................................. 7
1.3 Пошаговое описание алгоритма ..................................................................... 8
2 Размещение микросхем на плате....................................................................... 28
2.1 Обще описание алгоритма............................................................................... 28
2.2 Пошаговая работа алгоритма.......................................................................... 29
2.3 Расчет площади печатной платы .................................................................... 39
3 Трассировка шин «земля» и «питание» с использованием алгоритма по-
строения КСС ...................................................................................................... 41
3.1 Трассировка шины «земля» с помощью алгоритма Краскала..................... 41
3.2 Трассировка шины «питание» с помощью алгоритма Прима..................... 42
4 Алгоритмы трассировки печатного монтажа................................................... 48
4.1 Волновой алгоритм Ли .................................................................................... 49
Заключение ................................................................................................................ 54
Список использованной литературы....................................................................... 55
Приложение ............................................................................................................... 56
5
ВВЕДЕНИЕ
Современные достижения науки и техники, возрастающая функцио-
нальность современных изделий требуют выполнения проектных работ
большого объѐма. Требования к качеству проектов, срокам их выполнения
оказываются всѐ более жѐсткими в условиях конкурентной борьбы за потре-
бителя. Удовлетворить эти требования, количественно увеличивая проекти-
ровщиков, невозможно, так как распараллеливание проектных работ не без-
гранично.
Решить проблему можно, внедряя в практику инженерного проекти-
рования методы и средства автоматизированного проектирования.
Цель автоматизации проектирования – повышение качества, снижение
материальных затрат, сокращение сроков проектирования и повышение про-
изводительности труда проектировщиков.
Под автоматизацией проектирования понимается такой способ проек-
тирования, при котором весь цикл проектных работ осуществляется рацио-
нально распределѐнным взаимодействием человека и ЭВМ. В настоящее
время термин автоматизация проектирования характеризует целое научно-
техническое направление, базирующееся на современных достижениях фи-
зики, математики, вычислительной техники и теории проектирования.
Предметом автоматизации проектирования являются формализация
проектных процедур, структурирование и типизация процессов проектирова-
ния, постановки, модели, методы и алгоритмы, информационная поддержка
решения проектных задач, а также технические средства и способы их объе-
динения в единую проектирующую систему.
Целью преподавания дисциплины является изучение методологии ав-
томатизированного проектирования РЭС, методов получения и анализа мо-
делей конструкций и технологических процессов изготовления РЭС в целом
и основных конструктивных модулей. А также изучение способов построе-
ния и реализации САПР и особенностей используемых при этом технических
средств и программного обеспечения, получение навыков конструирования
РЭС и проектирования технологий с помощью систем автоматизированного
проектирования.
В результате изучения дисциплины студенты пишут курсовую работу.
Задачи курсовой работы:
- уметь разрабатывать и анализировать математические модели раз-
личных иерархических уровней РЭС;
- знать архитектуру САПР, методы и средства формализованного опи-
сания конструктивных модулей РЭС с учѐтом заданных моделей технологи-
ческих процессов при производстве РЭС, методы и средства автоматизиро-
ванного проектирования конструкций и технологий РЭС, способы анализа и
проверки конструктивных узлов;
- уметь разрабатывать формальные процедуры решения основных за-
6
дач конструкторского проектирования: компоновки РЭС, размещения элек-
трорадиоэлементов (ЭРЭ) в монтажном пространстве, трассировки соедине-
ний, моделирования полей в конструкциях РЭС; автоматизированного вы-
пуска технической документации;
- иметь представление о современных САПР, методах и средствах со-
пряжения различных подсистем между собой.
7
1 ПОКРЫТИЕ ЭЛЕКТРИЧЕСКОЙ СХЕМЫ И
КОМПОНОВКА МОДУЛЕЙ МИКРОСХЕМ ПРИ
ПОМОЩИ ПОСЛЕДОВАТЕЛЬНОГО АЛГОРИТМА
КОМПОНОВКИ
1. 1 Покрытие электрической схемы
При переходе от функциональной схемы к электрической принципи-
альной необходимо решать задачи покрытия схемы. При решении этой зада-
чи учитывается назначение модулей на схеме, вид и серии используемых
микросхем.
Основными критериями покрытия схем являются:
1. Число типов модулей, используемых в схеме;
2. Число однотипных модулей, входящих в микросхему;
3. Число микросхем, необходимых для покрытия исходной схемы.
1.2 Общее описание алгоритма
Компоновкой электрической схемы на конструктивно законченные
части называется процесс распределения элементов низшего конструктивно-
го уровня в высший в соответствии с выбранным критерием.
В общем виде при описании алгоритма компоновки удобно использо-
вать теорию графов. При этом электрическая схема представляется нена-
правленным мультиграфом, вершинами которого являются отдельные моду-
ли, а рѐбрами – связи между модулями. Тогда задача компоновки формули-
руется следующим образом: задан мультиграф G(x, U), требуется разбить его
на подграфы (микросхемы) G
1
(x
1
, U
1
), G
2
(x
2
, U
2
),…, G
n
(x
n
, U
n
), так, чтобы
число рѐбер, соединяющих эти подграфы, было минимальным. Т.е. скомпо-
новать модули в микросхему таким образом, чтобы наиболее связанные мо-
дули были в одной микросхеме, а связи между микросхемами, минимизиро-
вать.
В общем виде задача разбиения графа на подграфы записывается сле-
дующим образом
G
i
= (x
i
,U
i
)
(1.1)
В каждом подграфе число вершин не должно превосходить ранее за-
данного ограничения на число модулей в микросхеме.
Для любого разбиения должны выполняться следующие условия
G
G
n
i
i
1
8
n
i
i
G
1
Ø
(1.2)
n
i
i
X
X
1
1.3 Пошаговое описание алгоритма
1-ый шаг. Проанализировав функциональную схему, разбиваем еѐ на
отдельные узлы, содержащие однотипные модули. Причѐм, сохраняются
электрические связи между модулями данного узла. Связи к другим узлам не
учитываются.
2-й шаг. Составляем граф-схему, принимая за вершину графа каждый
модуль, входящий в узел.
3-й шаг. По граф-схеме составляем матрицу смежности, обнуляя ее по
главной диагонали и подсчитываем степени вершин.
4-й шаг. Формирование отдельных подграфов узла начинаем с выбора
базовой вершины. Такой вершиной является вершина, имеющая максималь-
ную степень:
)
(
max
)
(*
x
p
x
p
x
x
i
i
(1.3)
Если несколько вершин имеют одинаковую максимальную степень, то
за базовую принимается вершина с максимальным числом кратных рѐбер.
Если нет вершин, имеющих кратные рѐбра, то за базовую принимает-
ся вершина, имеющая максимальную степень и наименьший индекс.
5-й шаг. Из множества вершин x
i
выделяем подмножество вершин,
связанных с базовой вершиной, т.е. находим отображение базовой вершины
Гx
i
.
6-й шаг. Вычисляем функционалы для всех вершин, связанных с базо-
вой
L
j
= p
*
(x
i
) – a
ij
(1.4)
где p
*
(x
i
) – степень базовой вершины;
a
ij
– число связей базовой вершины x
i
с вершиной x
j
.
7-й шаг. Выбираем вершину, имеющую минимальный функционал и
связываем еѐ с базовой. Если таких вершин несколько, то выбираем вершину
с наименьшим индексом.
8-й шаг. Составляем матрицу смежности, заменяя вершины x
i
и x
j
од-
ной вершиной x
ij
(суммируя связи). И базовой вершиной считаем x
ij
.
9-й шаг. Повторяем шаги 5,6,7 и 8 до тех пор, пока не будет скомпо-
9
нована микросхема.
10-й шаг. Приступаем к формированию нового подграфа со 2-го шага,
убрав из общего графа, сформированный подграф.
11-й шаг. Повторяем алгоритм компоновки до тех пор, пока все моду-
ли узла не будут скомпонованы в микросхемы.
Рисунок 1.1 – Схема электрическая функциональная
На схеме (рис.1.1) имеется три типа модулей (рис.1.2).
а)
б)
Рисунок 1.2 – Типы модулей:
На рис.1.3 приведено условное графическое изображение (УГО) мик-
росхем.
10
Рисунок 1.3 – УГО микросхем:
1-ый шаг. Разбиваем схему электрическую функциональную на от-
дельные узлы, содержащие однотипные модули, оставляя связи внутри узлов
(рис.1.4).
Рисунок 1.4 – Функциональный узлы.
11
2-ой шаг. Составляем граф-схему (рис.1.5) для первого функциональ-
ного узла К155ЛР1, петли не учитываем.
Рисунок 1.5 – Граф-схема
12
3-ий шаг. Составляем по граф-схеме матрицу смежности и подсчиты-
ваем степени вершин (рис.1.6).
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x*
9
x
10
x
11
x
12
x
13
x
14
x
15
x
16
x
17
x
18
x
19
x
20
P
i
x
1
0
2
1
1
1
2
2
1
2
1
1
1
1
1
2
1
2
1
1
1
25
x
2
2
0
0
0
3
1
0
1
0
1
0
0
0
0
0
1
0
1
0
0
10
x
3
1
0
0
5
0
1
3
2
2
1
1
1
1
1
1
1
3
2
1
1
28
x
4
1
0
5
0
0
1
2
3
2
1
1
1
1
1
1
1
3
2
1
1
28
x
5
1
3
0
0
0
4
0
0
2
1
0
0
0
0
0
0
0
0
0
0
11
x
6
2
1
1
1
4
0
1
1
3
3
1
1
1
1
1
1
2
1
1
1
28
x
7
2
0
3
2
0
1
0
3
2
1
2
2
1
1
2
1
2
1
1
1
28
x
8
1
1
2
3
0
1
3
0
2
2
2
2
1
1
1
2
2
2
1
1
30
x*
9
2
0
2
2
2
3
2
2
0
4
2
2
3
3
2
2
4
2
2
2
43
x
10
1
1
1
1
1
3
1
2
4
0
1
1
2
2
1
2
2
2
1
1
30
x
11
1
0
1
1
0
1
2
2
2
1
0
5
1
1
2
2
2
1
1
1
27
x
12
1
0
1
1
0
1
2
2
2
1
5
0
1
1
3
3
2
1
1
1
29
x
13
1
0
1
1
0
1
1
1
3
2
1
1
0
5
1
1
4
3
1
1
29
x
14
1
0
1
1
0
1
1
1
3
2
1
1
5
0
1
1
3
2
1
1
27
x
15
2
0
1
1
0
1
2
1
2
1
2
3
1
1
0
3
2
1
2
2
28
x
16
1
1
1
1
0
1
1
2
2
2
2
3
1
1
3
0
2
2
2
2
30
x
17
2
0
3
3
0
2
2
2
4
2
2
2
4
3
2
2
0
4
2
2
43
x
18
1
1
2
2
0
1
1
2
2
2
1
1
3
2
1
2
4
0
1
1
30
x
19
1
0
1
1
0
1
1
1
2
1
1
1
1
1
2
2
2
1
0
5
25
x
20
1
0
1
1
0
1
1
1
2
1
1
1
1
1
2
2
2
1
5
0
25
Рисунок 1.6 – Матрица смежности
4-ый шаг. За базовую принимаем вершину, имеющую максимальную
степень. Так как таких вершин 4 имеют степень , то принимаем за базовую
принимаем вершину которая в таблице стоит на первом, т.е. вершину x
9
(от-
мечена знаком «*» на рис.1.6).
5-ый шаг. Вершина x
9
имеет отображение Гx
9
= { x
1
, x
3
, x
4
, x
5
, x
6
, x
7
, x
8
,
x
10
, x
11
, x
12
, x
13
, x
14
, x
15
, x
16
, x
17
, x
18
, x
19
, x
20
}.
6-ой шаг. Вычисляем функционалы по формуле (1.4).
Lx
1
=25 –2= 23;
Lx
3
=28 –2 = 26;
Lx
4
= 28 – 2 = 26;
Lx
5
= 11 – 2 = 9min;
Lx
6
= 28 –3 = 25;
Lx
7
=28 – 2 =26;
Lx
8
= 30 –2 = 28;
Lx
10
= 30 –4 = 26;
Lx
11
= 27–2 = 25; Lx
12
= 29 –2 = 27;
13
Lx
13
= 29 – 3 =26;
Lx
14
= 27 – 3 =24;
Lx
15
= 28 –2 = 26;
Lx
16
= 30 –2 = 28;
Lx
17
= 43 –4 = 39;
Lx
18
= 30 –2 = 28;
Lx
19
= 25 –2 = 23;
Lx
20
=25 – 2 = 23.
7-ой шаг. Вершина x
5
имеет минимальный функционал .
8-ой шаг. Стягиваем вершину x
5
с базовой вершиной x
9
. Так как мик-
росхема К155ЛР1 состоит из 2 модулей, то она уже скомпонована .
Из графа (рис.1.5) убираем скомпонованные вершины с инцидентны-
ми рѐбрами, получаем подграф (риc.1.7) для не скомпонованных вершин.
Рисунок 1.7 – Подграф
14
Составляем матрицу смежности для подграфа (рис.1.7) и подсчитываем
степени вершин (рис.1.8).
x
1
x
2
x
3
x
4
x
6
x
7
x
8
x
10
x
11
x
12
x
13
x
14
x
15
x
16
x*
17
x
18
x
19
x
20
P
i
x
1
0
2
1
1
2
2
1
1
1
1
1
1
2
1
2
1
1
1
22
x
2
2
0
0
0
1
0
1
1
0
0
0
0
0
1
0
1
0
0
7
x
3
1
0
0
5
1
3
2
1
1
1
1
1
1
1
3
2
1
1
26
x
4
1
0
5
0
1
2
3
1
1
1
1
1
1
1
3
2
1
1
26
x
6
2
1
1
1
0
1
1
3
1
1
1
1
1
1
2
1
1
1
21
x
7
2
0
3
2
1
0
3
1
2
2
1
1
2
1
2
1
1
1
26
x
8
1
1
2
3
1
3
0
2
2
2
1
1
1
2
2
2
1
1
28
x
10
1
1
1
1
3
1
2
0
1
1
2
2
1
2
2
2
1
1
25
x
11
1
0
1
1
1
2
2
1
0
5
1
1
2
2
2
1
1
1
25
x
12
1
0
1
1
1
2
2
1
5
0
1
1
3
3
2
1
1
1
27
x
13
1
0
1
1
1
1
1
2
1
1
0
5
1
1
4
3
1
1
26
x
14
1
0
1
1
1
1
1
2
1
1
5
0
1
1
3
2
1
1
24
x
15
2
0
1
1
1
2
1
1
2
3
1
1
0
3
2
1
2
2
26
x
16
1
1
1
1
1
1
2
2
2
3
1
1
3
0
2
2
2
2
28
x*
17
2
0
3
3
2
2
2
2
2
2
4
3
2
2
0
4
2
2
39
x
18
1
1
2
2
1
1
2
2
1
1
3
2
1
2
4
0
1
1
28
x
19
1
0
1
1
1
1
1
1
1
1
1
1
2
2
2
1
0
5
23
x
20
1
0
1
1
1
1
1
1
1
1
1
1
2
2
2
1
5
0
23
Рисунок 1.8 – Матрица смежности
За базовую принимаем вершину, имеющую максимальную степень.
Так как таких вершины несколько, то принимаем за базовую принимаем
вершину которая в таблице стоит на первом, т.е. вершину x
17
(отмечена зна-
ком «*» на рис.1.8).
9-ый шаг. Повторяем шаги 5, 6, 7.
Вершина x
17
имеет отображение Гx
17
= { x
1
, x
3
, x
4
, x
6
, x
7
, x
8
, x
10
, x
11
, x
12
,
x
13
, x
14
, x
15
, x
16
, x
18
, x
19
, x
20
}.
Функционалы:
Lx
1
=22 –2= 20; Lx
3
=26 –3 = 23;
Lx
4
= 26 – 3 = 23;Lx
6
= 21 –2 = 19 min;
Lx
7
=26 – 2 =24; Lx
8
= 28 –2 = 26;
Lx
10
= 25 –2 = 23;Lx
11
= 25–2 = 23;
Lx
12
= 27 –2 = 25;Lx
13
= 26 – 4 =22;
Lx
14
= 24 – 3 =21;Lx
15
= 26 –2 = 24;
Lx
16
= 28 –2 = 26;Lx
18
= 28 –4 = 24;
Lx
19
= 23 –2 = 21; Lx
20
=23 – 2 = 21.
15
Вершина x
6
имеет минимальный функционал .
Стягиваем вершину x
6
с вершиной x
17
. Так как микросхема К155ЛР1
состоит из 2 модулей, то она уже скомпонована .
Из графа (рис.1.5) убираем скомпонованные вершины с инцидентны-
ми рѐбрами, получаем подграф (риc.1.9) для не скомпонованных вершин.
Рисунок 1.9 – Подграф
Составляем матрицу смежности для подграфа (рис.1.9) и подсчитываем
степени вершин (рис.1.10).
16
x
1
x
2
x
3
x
4
x
7
x
8*
x
10
x
11
x
12
x
13
x
14
x
15
x
16
x
18
x
19
x
20
P
i
x
1
0
2
1
1
2
1
1
1
1
1
1
2
1
1
1
1
18
x
2
2
0
0
0
0
1
1
0
0
0
0
0
1
1
0
0
6
x
3
1
0
0
5
3
2
1
1
1
1
1
1
1
2
1
1
22
x
4
1
0
5
0
2
3
1
1
1
1
1
1
1
2
1
1
22
x
7
2
0
3
2
0
3
1
2
2
1
1
2
1
1
1
1
23
x
8
1
1
2
3
3
0
2
2
2
1
1
1
2
2
1
1
25*
x
10
1
1
1
1
1
2
0
1
1
2
2
1
2
2
1
1
20
x
11
1
0
1
1
2
2
1
0
5
1
1
2
2
1
1
1
22
x
12
1
0
1
1
2
2
1
5
0
1
1
3
3
1
1
1
24
x
13
1
0
1
1
1
1
2
1
1
0
5
1
1
3
1
1
21
x
14
1
0
1
1
1
1
2
1
1
5
0
1
1
2
1
1
20
x
15
2
0
1
1
2
1
1
2
3
1
1
0
3
1
2
2
23
x
16
1
1
1
1
1
2
2
2
3
1
1
3
0
2
2
2
25
x
18
1
1
2
2
1
2
2
1
1
3
2
1
2
0
1
1
23
x
19
1
0
1
1
1
1
1
1
1
1
1
2
2
1
0
5
20
x
20
1
0
1
1
1
1
1
1
1
1
1
2
2
1
5
0
20
Рисунок 1.10 – Матрица смежности
За базовую принимаем вершину x
8
, имеющую максимальную степень.
9-ый шаг. Повторяем шаги 5, 6, 7.
Вершина x
8
имеет отображение Гx
8
= { x
1
, x
2
, x
3
, x
4
, x
7
, x
10
, x
11
, x
12
, x
13
,
x
14
, x
15
, x
16
, x
18
, x
19
, x
20
}.
Функционалы:
Lx
1
=18 –1= 17;
Lx
2
=6 –1 = 5 min;
Lx
3
=22 –2 = 20;
Lx
4
= 22 – 3 = 19;
Lx
7
=23 – 3 =20;
Lx
10
= 20 –2 = 18;
Lx
11
= 22–2 = 20;
Lx
12
= 24 –2 = 22;
Lx
13
= 21 – 1 =20;
Lx
14
= 20 – 1 =19;
Lx
15
= 23 –1 = 22;
Lx
16
= 25 –2 = 23;
Lx
18
= 23 –2 = 21;
Lx
19
= 20 –1 = 19;
17
Lx
20
=20 – 1 = 19.
Вершина x
2
имеет минимальный функционал .
Стягиваем вершину x
2
с вершиной x
8
. Так как микросхема К155ЛР1
состоит из 2 модулей, то она уже скомпонована .
Из графа (рис.1.5) убираем скомпонованные вершины с инцидентны-
ми рѐбрами, получаем подграф (риc.1.11) для не скомпонованных вершин.
Рисунок 1.11 – Подграф
18
Составляем матрицу смежности для подграфа (рис.1.11) и подсчитыва-
ем степени вершин (рис.1.12).
x
1
x
3
x
4
x
7
x
10
x
11
x
12
x
13
x
14
x
15
x
16
x
18
x
19
x
20
P
i
x
1
0
1
1
2
1
1
1
1
1
2
1
1
1
1
15
x
3
1
0
5
3
1
1
1
1
1
1
1
2
1
1
20
x
4
1
5
0
2
1
1
1
1
1
1
1
2
1
1
19
x
7
2
3
2
0
1
2
2
1
1
2
1
1
1
1
20
x
10
1
1
1
1
0
1
1
2
2
1
2
2
1
1
17
x
11
1
1
1
2
1
0
5
1
1
2
2
1
1
1
20
x
12
1
1
1
2
1
5
0
1
1
3
3
1
1
1
22*
x
13
1
1
1
1
2
1
1
0
5
1
1
3
1
1
20
x
14
1
1
1
1
2
1
1
5
0
1
1
2
1
1
19
x
15
2
1
1
2
1
2
3
1
1
0
3
1
2
2
22
x
16
1
1
1
1
2
2
3
1
1
3
0
2
2
2
22
x
18
1
2
2
1
2
1
1
3
2
1
2
0
1
1
20
x
19
1
1
1
1
1
1
1
1
1
2
2
1
0
5
19
x
20
1
1
1
1
1
1
1
1
1
2
2
1
5
0
19
Рисунок 1.12 – Матрица смежности
За базовую принимаем вершину x
12
, имеющую максимальную сте-
пень.
9-ый шаг. Повторяем шаги 5, 6, 7.
Вершина x
12
имеет отображение Гx
12
= { x
1
, x
3
, x
4
, x
7
, x
10
, x
11
, x
13
, x
14
,
x
15
, x
16
, x
18
, x
19
, x
20
}.
Функционалы:
Lx
1
=15 –1= 14 min;
Lx
3
=20 –1 = 19;
Lx
4
= 19 – 1 = 18;
Lx
7
=20 – 2 =18;
Lx
10
= 17 –1 = 16;
Lx
11
= 20–5= 15;
Lx
13
= 20 – 1 =19;
Lx
14
= 19 – 1 =18;
Lx
15
= 22 –3 = 19;
Lx
16
= 22 –3 = 19;
Lx
18
= 20 –1 = 19;
Lx
19
= 19 –1 = 18;
Lx
20
=19 – 1 = 18.
19
Вершина x
1
имеет минимальный функционал .
Стягиваем вершину x
1
с вершиной x
12
. Так как микросхема К155ЛР1
состоит из 2 модулей, то она уже скомпонована .
Из графа (рис.1.5) убираем скомпонованные вершины с инцидентны-
ми рѐбрами, получаем подграф (риc.1.13) для не скомпонованных вершин.
Рисунок 1.13 – Подграф
Составляем матрицу смежности для подграфа (рис.1.13) и подсчитыва-
ем степени вершин (рис.1.14).
20
x
3
x
4
x
7
x
10
x
11
x
13
x
14
x
15
x
16
x
18
x
19
x
20
P
i
x
3
0
5
3
1
1
1
1
1
1
2
1
1
18
x
4
5
0
2
1
1
1
1
1
1
2
1
1
17
x
7
3
2
0
1
2
1
1
2
1
1
1
1
16
x
10
1
1
1
0
1
2
2
1
2
2
1
1
15
x
11
1
1
2
1
0
1
1
2
2
1
1
1
14
x
13
1
1
1
2
1
0
5
1
1
3
1
1
18
x
14
1
1
1
2
1
5
0
1
1
2
1
1
17
x
15
1
1
2
1
2
1
1
0
3
1
2
2
17
x
16
1
1
1
2
2
1
1
3
0
2
2
2
18
x
18
2
2
1
2
1
3
2
1
2
0
1
1
18
x
19
1
1
1
1
1
1
1
2
2
1
0
5
17
x
20
1
1
1
1
1
1
1
2
2
1
5
0
17
Рисунок 1.14 – Матрица смежности
За базовую принимаем вершину x
3
, имеющую максимальную степень.
9-ый шаг. Повторяем шаги 5, 6, 7.
Вершина x
3
имеет отображение Гx
3
= {x
4
, x
7
, x
10
, x
11
, x
13
, x
14
, x
15
, x
16
, x
18
,
x
19
, x
20
}.
Функционалы:
Lx
4
= 17 – 5 = 12 min;
Lx
7
=16 – 3 =13;
Lx
10
= 15 –1 = 14;
Lx
11
= 14–1= 13;
Lx
13
= 18 – 1 =17;
Lx
14
= 17 – 1 =16;
Lx
15
= 17 –1 = 16;
Lx
16
= 18 –1 = 17;
Lx
18
= 18 –2 = 16;
Lx
19
= 17 –1 = 16;
Lx
20
=17 – 1 = 16.
Вершина x
4
имеет минимальный функционал .
Стягиваем вершину x
4
с вершиной x
3
. Так как микросхема К155ЛР1
состоит из 2 модулей, то она уже скомпонована .
Из графа (рис.1.5) убираем скомпонованные вершины с инцидентны-
ми рѐбрами, получаем подграф (риc.1.15) для не скомпонованных вершин.
21
Рисунок 1.15 – Подграф
Составляем матрицу смежности для подграфа (рис.1.15) и подсчитыва-
ем степени вершин (рис.1.16).
x
7
x
10
x
11
x
13
x
14
x
15
x
16
x
18
x
19
x
20
P
i
x
7
0
1
2
1
1
2
1
1
1
1
11
x
10
1
0
1
2
2
1
2
2
1
1
13
x
11
2
1
0
1
1
2
2
1
1
1
12
x
13
1
2
1
0
5
1
1
3
1
1
16
x
14
1
2
1
5
0
1
1
2
1
1
15
x
15
2
1
2
1
1
0
3
1
2
2
15
x
16
1
2
2
1
1
3
0
2
2
2
16
x
18
1
2
1
3
2
1
2
0
1
1
14
x
19
1
1
1
1
1
2
2
1
0
5
15
x
20
1
1
1
1
1
2
2
1
5
0
15
Рисунок 1.16 – Матрица смежности
22
За базовую принимаем вершину x
13
, имеющую максимальную сте-
пень.
9-ый шаг. Повторяем шаги 5, 6, 7.
Вершина x
13
имеет отображение Гx
13
= { x
7
, x
10
, x
11
, x
14
, x
15
, x
16
, x
18
, x
19
,
x
20
}.
Функционалы:
Lx
7
=11 – 1 =10 min;
Lx
10
= 13 –2 = 11; Lx
11
= 12–1= 11;
Lx
14
= 15 – 5 =10; Lx
15
= 15 –1 = 14;
Lx
16
= 16 –1 = 15; Lx
18
= 14 –3 = 11;
Lx
19
= 15 –1 = 14; Lx
20
=15– 1 = 14.
Вершина x
7
имеет минимальный функционал .
Стягиваем вершину x
7
с вершиной x
13
. Так как микросхема К155ЛР1
состоит из 2 модулей, то она уже скомпонована .
Из графа (рис.1.5) убираем скомпонованные вершины с инцидентны-
ми рѐбрами, получаем подграф (риc.1.17) для не скомпонованных вершин.
Рисунок 1.17 – Подграф
23
Составляем матрицу смежности для подграфа (рис.1.17) и подсчитыва-
ем степени вершин (рис.1.18).
x10 x11 x14 x15 x16 x18 x19 x20
P
i
x10
0
1
2
1
2
2
1
1
10
x11
1
0
1
2
2
1
1
1
9
x14
2
1
0
1
1
2
1
1
9
x15
1
2
1
0
3
1
2
2
12
x16
2
2
1
3
0
2
2
2
14
x18
2
1
2
1
2
0
1
1
10
x19
1
1
1
2
2
1
0
5
13
x20
1
1
1
2
2
1
5
0
13
Рисунок 1.18 – Матрица смежности
За базовую принимаем вершину x
16
, имеющую максимальную сте-
пень.
9-ый шаг. Повторяем шаги 5, 6, 7.
Вершина x
16
имеет отображение Гx
16
= {x
10
, x
11
, x
14
, x
15
, x
18
, x
19
, x
20
}.
Функционалы:
Lx
10
= 10 –2 = 9;
Lx
11
= 9–2=7 min;
Lx
14
= 9 – 1 =8;
Lx
15
= 12 –3 = 9;
Lx
18
= 10 –2 = 8;
Lx
19
= 13 –2 = 11;
Lx
20
=13– 2 = 11.
Вершина x
11
имеет минимальный функционал .
Стягиваем вершину x
11
с вершиной x
16
. Так как микросхема К155ЛР1
состоит из 2 модулей, то она уже скомпонована .
Из графа (рис.1.5) убираем скомпонованные вершины с инцидентны-
ми рѐбрами, получаем подграф (риc.1.19) для не скомпонованных вершин.
24
Рисунок 1.19 – Подграф
Составляем матрицу смежности для подграфа (рис.1.19) и подсчитыва-
ем степени вершин (рис.1.20).
x
10
x
14
x
15
x
18
x
19
x
20
P
i
x
10
0
2
1
2
1
1
7
x
14
2
0
1
2
1
1
7
x
15
1
1
0
1
2
2
7
x
18
2
2
1
0
1
1
7
x
19
1
1
2
1
0
5
10
x
20
1
1
2
1
5
0
10
Рисунок 1.20 – Матрица смежности
За базовую принимаем вершину x
19
, имеющую максимальную сте-
пень.
9-ый шаг. Повторяем шаги 5, 6, 7.
Вершина x
19
имеет отображение Гx
19
= {x
10
, x
14
, x
15
, x
18
, x
20
}.
Функционалы:
Lx
10
= 7 –1 = 6;
25
Lx
14
= 7 – 1 =6;
Lx
15
= 7 –2 = 5 min;
Lx
18
= 7 –1 = 6;
Lx
20
=10– 5 = 5.
Вершина x
15
имеет минимальный функционал .
Стягиваем вершину x
15
с вершиной x
19
. Так как микросхема К155ЛР1
состоит из 2 модулей, то она уже скомпонована .
Из графа (рис.1.5) убираем скомпонованные вершины с инцидентны-
ми рѐбрами, получаем подграф (риc.1.21) для не скомпонованных вершин.
Рисунок 1.21 – Подграф
Составляем матрицу смежности для подграфа (рис.1.21) и подсчитыва-
ем степени вершин (рис.1.22).
x
10
x
14
x
18
x
20
P
i
x
10
0
2
2
1
5
x
14
2
0
2
1
5
x
18
2
2
0
1
5
x
20
1
1
1
0
3
Рисунок 1.22 – Матрица смежности
26
За базовую принимаем вершину x
10
, имеющую максимальную сте-
пень.
9-ый шаг. Повторяем шаги 5, 6, 7.
Вершина x
10
имеет отображение Гx
10
= {x
14
, x
18
, x
20
}.
Функционалы:
Lx
14
= 5 – 2 =3;
Lx
18
= 5 –2 = 3;
Lx
20
=3– 1 = 2 min.
Вершина x
20
имеет минимальный функционал .
Стягиваем вершину x
20
с вершиной x
10
. Так как микросхема К155ЛР1
состоит из 2 модулей, то она уже скомпонована .
Из графа (рис.1.5) убираем скомпонованные вершины с инцидентны-
ми рѐбрами, получаем подграф (риc.1.23) для не скомпонованных вершин.
Рисунок 1.23 – Подграф
27
Составляем матрицу смежности для подграфа (рис.1.23) и подсчитыва-
ем степени вершин (рис.1.24).
x
14
x
18
P
i
x
14
0
2
2
x
18
2
0
2
Рисунок 1.24 – Матрица смежности
Оставшийся два модуля будет составлять четвертую микросхему.
Для второго функционального узла (рис.1.2б) выбираем микросхемы
К155ЛА3. Так как эта микросхема состоит из четырех модулей (рис.1.3б), то
компоновку производить не следует так как на схеме три модуля данной
микросхемы микросхемой.
Так как оформление схем электрических принципиальных должно со-
ответствовать [4], то окончательный вариант схемы электрической принци-
пиальной приведѐн в приложении. В этом варианте нумерация микросхем
учитывалась в соответствии с [4]. К схеме электрической принципиальной
составляется перечень элементов, также приведенный в приложении.
28
2 РАЗМЕЩЕНИЕ МИКРОСХЕМ НА ПЛАТЕ
2.1 Общее описание алгоритма
После распределения конструктивных элементов РЭА по коммутаци-
онным пространствам различного уровня иерархии для каждой полученной в
результате компоновки сборочной единицы производят размещение вклю-
чѐнных в его состав элементов предыдущего уровня, т.е. выбирают такое их
взаимное расположение, при котором наилучшим образом учитываются
предъявляемые к аппаратуре требования.
Исходной информацией, при решении задач размещения являются
данные о конфигурации и размерах коммутационного пространства, опреде-
ляемые требованиями установки и крепления данной сборочной единицы в
аппаратуре. Количество и геометрические размеры конструктивных элемен-
тов, подлежащих размещению, схема соединений, а также ряд ограничений
на взаимное расположение отдельных элементов, учитывающие особенности
разрабатываемой конструкции.
Задача сводится к отысканию для каждого размещаемого элемента та-
ких позиций, при которых оптимизируется выбранный показатель качества и
обеспечиваются наиболее благоприятные условия для последующего эле-
ментного монтажа
Следовательно, если для оценки качества размещения элементов вы-
брать критерий непосредственно связанный с получением оптимального ри-
сунка металлизации печатной платы, то конечный результат может быть
найден только при совместном решении задачи размещения, выбора очеред-
ности проведения соединения и трассировки, что практически невозможно
уже для схем средней сложности вследствие огромных затрат машинного
времени. Поэтому все применяемые в настоящее время алгоритмы размеще-
ния используют промежуточные критерии, которые лишь качественно спо-
собствуют решению основной задачи, получению оптимальной трассировки
соединений. К таким критериям относятся:
1) Минимум суммарной взвешенной длины соединений.
2) Минимальное число соединений, длина которых больше задан-
ной.
3) Минимальное число пересечений проводников.
4) Максимальное число соединений между элементами, находящи-
мися в соседних позициях, либо в позициях указанных разработчиком.
5) Максимальное число цепей простой конфигурации.
Наибольшее распространение в алгоритме размещения получил пер-
вый критерий, что объясняется следующими причинами:
1) Уменьшение длин соединений улучшает электрические характе-
ристики устройства.
2) Упрощает трассировку печатных проводников.
29
3) Снижает трудоѐмкость изготовления печатных плат.
4) Сравнительно простой в реализации.
Наиболее распространѐнным алгоритмом размещения является после-
довательный алгоритм. Он основан на допущении, что для получения опти-
мального размещения необходимо в соседних позициях располагать элемен-
ты максимально связанные друг с другом.
Сущность этих алгоритмов состоит в последовательном закреплении
заданного набора конструктивных элементов на коммутационной плате от-
носительно ранее установленной. В качестве первоначально закреплѐнных на
плате элементов обычно выбирают разъѐмы, которые, как правило, устанав-
ливаются на каком-либо краю платы. При этом все контакты разъѐмов рав-
номерно распределяют по секциям (столбцам и строкам) координатной сет-
ки. Процесс размещения элементов заканчивается после выполнения L ша-
гов, когда все элементы будут размещены на коммутационном поле.
2.2 Пошаговая работа алгоритма
1) Формируем матрицу расстояний для коммутационного поля с
учѐтом ранее закреплѐнного элемента (разъѐм ХS1).
2) Формируем матрицу смежности по графу, составленному по по-
лученной схеме электрической принципиальной, считая за вершины, ском-
понованные микросхемы и разъѐм. Матрицу обнуляем по главной диагонали.
3) Выбираем из множества неразмещѐнных микросхем, ту микро-
схему, для которой коэффициент взвешенной связности максимальный. Ко-
эффициент взвешенной связности рассчитываем по формуле:
m
j
j
ij
j
p
a
Ф
1
,
(2.1)
где a
ij
– количество связей j-ой вершины с ранее закрепленной верши-
ной x
i
;
p
j
– степень j-ой вершины;
m – количество вершин, связанных с j-ой вершиной.
4) Для вершины, у которой коэффициент взвешенной связности
максимальный, находим посадочное место на коммутационном поле из усло-
вия, что коэффициент размещения минимален. Коэффициент размещения
определяется по формуле:
fl
n
f
ij
f
d
a
F
1
,
(2.2)
где d
fl
– количество связей ячейки f с ранее закрепленной ячейкой l, в
которой размещена вершина x
i
;
30
n – количество не занятых посадочных мест.
5) Шаги 3, 4 повторяются до тех пор, пока все элементы не будут
размещены на плате.
DD1 DD2 DD3 DD4 DD5 DD6 DD7 DD8 DD9 DD10 DD11 XS1 pi
DD1
0
5
4
2
5
7
6
4
10
4
7
5
0
DD2
5
0
5
6
5
4
4
4
5
4
2
4
5
DD3
4
5
0
0
4
8
7
4
4
6
4
5
4
DD4
2
6
0
0
2
0
0
1
1
1
0
3
2
DD5
5
5
4
2
0
11
5
7
4
5
4
3
5
DD6
7
4
8
0
11
0
8
8
6
9
6
5
7
DD7
6
4
7
0
5
8
0
5
5
10
5
4
6
DD8
4
4
4
1
7
8
5
0
6
6
9
6
4
DD9
10
5
4
1
4
6
5
6
0
5
8
5
10
DD10
4
4
6
1
5
9
10
6
5
0
4
5
4
DD11
7
2
4
0
4
6
5
9
8
4
0
4
7
XS1
5
4
5
3
3
5
4
6
5
5
4
0
5
Рисунок 2.1 – Матрица смежности
1
2
5
8 11 14
3
6
9 12 15
4
7 10 13 16
Рисунок 2.2 – Коммутационное поле платы
1.По рисунку 2.2 составим матрицу расстояний (рис.2.3).
31
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16
1
0 1 1 1 2 3 2 5 4 3 6 5 4 7 6 5
2
1 0 1 2 1 4 3 6 5 4 7 6 5 8 7 6
3
1 1 0 1 2 1 2 3 2 3 4 3 4 5 4 5
4
1 2 1 0 3 2 1 4 3 2 5 4 3 6 5 4
5
2 1 2 3 0 1 2 1 2 3 2 3 4 3 4 5
6
3 4 1 2 1 0 1 2 1 2 3 2 3 4 3 4
7
2 3 2 1 2 1 0 3 2 1 4 3 2 5 4 3
8
5 6 3 4 1 2 3 0 1 2 1 2 3 2 3 4
9
4 5 2 3 2 1 2 1 0 1 2 1 2 3 2 3
10
3 4 3 2 3 2 1 2 1 0 3 2 1 4 3 2
11
6 7 4 5 2 3 4 1 2 3 0 1 2 1 2 3
12
5 6 3 4 3 2 3 2 1 2 1 0 1 2 1 2
13
4 5 4 3 4 3 2 3 2 1 2 1 0 3 2 1
14
7 8 5 6 3 4 5 2 3 4 1 2 3 0 1 2
15
6 7 4 5 4 3 4 3 2 3 2 1 2 1 0 1
16
5 6 5 4 5 4 3 4 3 2 3 2 1 2 1 0
Рисунок 2.3 – Матрица расстояний
2.Так как все микросхемы не распределены по посадочным местам, то
рассчитываем коэффициент взвешенной связности для всех микросхем по
формуле (2.1).
08
.0
59
5
1
DD
Ф
*
19
.0
16
3
4
DD
Ф
07
.0
59
4
7
DD
Ф
08
.0
59
5
10
DD
Ф
08
.0
48
4
2
DD
Ф
05
.0
55
3
5
DD
Ф
1.
0
60
6
8
DD
Ф
08
.0
53
4
11
DD
Ф
1.
0
51
5
3
DD
Ф
07
.0
72
5
6
DD
Ф
08
.0
59
5
9
DD
Ф
Выбираем для размещения микросхему, имеющую максимальный ко-
эффициент взвешенной связности. Такой микросхемой является микросхема
DD4(помечена знаком "*").
3.Расчитываем коэффициент размещения для посадочных мест по
формуле (2.2), в которой элемент a
ij
– количество связей вершины DD12 с
вершиной ХS1(см. матрицу смежности).
32
F
2
=3х1=3
F
7
=3х2=6
F
9
=3х4=12 F
11
=3х6=18
F
14
=3х7=21
F
4
=3х1=3
F
8
=3х5=15
F
10
=3х3=9 F
12
=3х5=15
F
15
=3х6=18
F
6
=3х3=9
F
13
=3х4=12
F
16
=3х5=15
Выбираем минимальный коэффициент размещения. Так как мини-
мальным является коэффициент F для ячеек 2 и 4, то выбираем ячейку с ми-
нимальным индексом. Такой ячейкой является ячейка 2. Следовательно,
микросхему DD4 размещаем во второй ячейке.
4.Рассчитываем коэффициент взвешенной связности для остальных
неразмещенных микросхем, с учетом того, что ранее размещенными элемен-
тами являются микросхема DD4 и разъем XS1. Т.е. формулу 2.1 можно запи-
сать в виде:
j
DD
XS
j
p
a
a
Ф
4
1
12
.0
59
2
5
1
DD
Ф
07
.0
59
0
4
7
DD
Ф
1.
0
59
1
5
10
DD
Ф
*
21
.0
48
6
4
2
DD
Ф
09
.0
55
2
3
5
DD
Ф
12
.0
60
1
6
8
DD
Ф
08
.0
53
0
4
11
DD
Ф
1.
0
51
0
5
3
DD
Ф
07
.0
72
0
5
6
DD
Ф
1.
0
59
1
5
9
DD
Ф
Так как максимальный коэффициент взвешенной связности имеет
микросхема DD2, то размещаем эту микросхему на коммутационное поле
платы.
5. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых. Т.е. формулу 2.2 можно записать в сле-
дующем виде:
3
4
1
1
2
f
DD
DD
f
XS
DD
f
d
a
d
a
F
33
F
4
=4x1+6x2=16 F
11
=4x6+6x7 =66
F
6
=4x3+6x4 =36 F
12
=4x5+6x6 =56
F
7
=4x2+6x3 =26 F
13
=4x4+6x5 =46
F
8
=4x5+6x6 =56 F
14
=4x7+6x8 =76
F
9
=4x4+6x5 =46 F
15
=4x6+6x7 =66
F
10
=4x3+6x4 =36 F
16
=4x5+6x6 =56
Минимальный коэффициент размещения имеет ячейка 4. Следова-
тельно, микросхему DD2 размещаем в четвертой ячейке коммутационного
поля.
6. Рассчитываем коэффициент взвешенной связности для оставшихся
микросхем , с учетом того, что ранее размещались элементы.
*
2.
0
59
5
2
5
1
DD
Ф
13
.0
72
4
0
5
6
DD
Ф
1.
0
59
5
1
5
9
DD
Ф
2.
0
51
5
0
5
3
DD
Ф
07
.0
59
4
0
4
7
DD
Ф
1.
0
59
4
1
5
10
DD
Ф
18
.0
55
5
2
3
5
DD
Ф
12
.0
60
4
1
6
8
DD
Ф
08
.0
53
2
0
4
11
DD
Ф
Выбираем для размещения микросхему, имеющую максимальный коэф-
фициент взвешенной связности. Такой микросхемой является микросхема
DD1.
7. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых
F
11
=5x6+2x7+5x5 =69
F
6
=5x3+2x4+5x2=33
F
12
=5x5+2x6+5x4 =57
F
7
=5x2+2x3+5x1 =21
F
13
=5x4+2x5+5x3 =45
F
8
=5x5+2x6+5x4 =57
F
14
=5x7+2x8+5x6 =81
F
9
=5x4+2x5+5x3 =45
F
15
=5x6+2x7+5x5 =69
34
F
10
=5x3+2x4+5x2 =33
F
16
=5x5+2x6+5x4 =57
Микросхему DD1 размещаем в седьмой ячейке.
8. Рассчитываем коэффициент взвешенной связности для оставшихся
микросхем , с учетом того, что ранее размещались элементы.
22
.0
72
7
4
0
5
6
DD
Ф
*
36
.0
59
10
5
1
5
9
DD
Ф
27
.0
51
4
5
0
5
3
DD
Ф
24
.0
59
6
4
0
4
7
DD
Ф
24
.0
59
4
4
1
5
10
DD
Ф
27
.0
55
5
5
2
3
5
DD
Ф
25
.0
60
4
4
1
6
8
DD
Ф
25
.0
53
7
2
0
4
11
DD
Ф
Размещаем микросхему DD9.
9. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых
F
6
=5x3+1x4+5x2+10x1=39
F
12
=5x5+1x6+5x4+10x3 =81
F
8
=5x5+1x6+5x4+10x3 =81
F
13
=5x4+1x5+5x3+10x2 =60
F
9
=5x4+1x5+5x3+10x2 =60
F
14
=5x7+1x8+5x6+10x5 =123
F
10
=5x3+1x4+5x2+10x1 =39 F
15
=5x6+1x7+5x5+10x4 =102
F
11
=5x6+1x7+5x5+10x4 =102 F
16
=5x5+1x6+5x4+10x3 =81
Следовательно, микросхему DD9 размещаем в шестую ячейку.
10. Рассчитываем коэффициент взвешенной связности для оставшихся
микросхем , с учетом того, что ранее размещались элементы.
31
.0
72
6
7
4
0
5
6
DD
Ф
35
.0
51
4
4
5
0
5
3
DD
Ф
32
.0
59
5
6
4
0
4
7
DD
Ф
32
.0
59
5
4
4
1
5
10
DD
Ф
35
35
.0
55
4
5
5
2
3
5
DD
Ф
35
.0
60
6
4
4
1
6
8
DD
Ф
*4
.0
53
8
7
2
0
4
11
DD
Ф
Размещаем микросхему DD11.
11. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых
F
12
=4x5+0x6+2x4+7x3+8x2 =65
F
8
=4x5+0x6+2x4+7x3+8x2=65 F
13
=4x4+0x5+2x3+7x2+8x3 =60
F
9
=4x4+0x5+2x3+7x2+8x1 =44 F
14
=4x7+0x8+2x6+7x5+8x4 =107
F
10
=4x3+0x4+2x2+7x1+8x2 =39 F
15
=4x6+0x7+2x5+7x4+8x3 =86
F
11
=4x6+0x7+2x5+7x4+8x3 =86 F
16
=4x5+0x6+2x4+7x3+8x4 =81
Микросхему DD11 размещаем в девсятую ячейку.
12. Рассчитываем коэффициент взвешенной связности для оставшихся
микросхем , с учетом того, что ранее размещались элементы.:
*
51
.0
51
4
4
4
5
0
5
3
DD
Ф
41
.0
59
5
5
6
4
0
4
7
DD
Ф
42
.0
55
4
4
5
5
2
3
5
DD
Ф
5.
0
60
9
6
4
4
1
6
8
DD
Ф
39
.0
72
6
6
7
4
0
5
6
DD
Ф
39
.0
59
4
5
4
4
1
5
10
DD
Ф
Размещаем микросхему DD3.
13. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых
F
8
=5x5+0x6+5x4+4x3+4x2+4x2=73
F
9
=5x4+0x5+5x3+4x2+4x1+4x1 =51
F
11
=5x6+0x7+5x5+4x4+4x3+4x3 =95
F
12
=5x5+0x6+5x4+4x3+4x2+4x2 =73
F
13
=5x4+0x5+5x3+4x2+4x3+4x1 =59
36
F
14
=5x7+0x8+5x6+4x5+4x4+4x4 =117
F
15
=5x6+0x7+5x5+4x4+4x3+4x3 =95
F
16
=5x5+0x6+5x4+4x3+4x4+4x2 =81
Микросхему DD3 размещаем в девятую ячейку.
14. Рассчитываем коэффициент взвешенной связности для оставшихся
микросхем , с учетом того, что ранее размещались элементы.
53
.0
59
7
5
5
6
4
0
4
7
DD
Ф
49
.0
55
4
4
4
5
5
2
3
5
DD
Ф
*
57
.0
60
4
9
6
4
4
1
6
8
DD
Ф
5.
0
72
8
6
6
7
4
0
5
6
DD
Ф
49
.0
59
6
4
5
4
4
1
5
10
DD
Ф
Размещаем микросхему DD8.
15. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых
F
8
=6x5+1x6+4x4+4x3+6x2+9x2+4x1=98
F
11
=6x6+1x7+4x5+4x4+6x3+9x3+4x2 =132
F
12
=6x5+1x6+4x4+4x3+6x2+9x2+4x1 =98
F
13
=6x4+1x5+4x3+4x2+6x3+9x1+4x2 =98
F
14
=6x7+1x8+4x6+4x5+6x4+9x4+4x3 =166
F
15
=6x6+1x7+4x5+4x4+6x3+9x3+4x2 =132
F
16
=6x5+1x6+4x4+4x3+6x4+9x2+4x3 =118
Микросхему DD8 размещаем в восьмую ячейку.
16. Рассчитываем коэффициент взвешенной связности для оставшихся
микросхем , с учетом того, что ранее размещались элементы.
37
*
62
.0
55
7
4
4
5
5
5
2
3
5
DD
Ф
61
.0
59
5
7
5
5
6
4
0
4
7
DD
Ф
61
.0
72
8
8
6
6
7
4
0
5
6
DD
Ф
59
.0
59
6
6
4
5
4
4
1
5
10
DD
Ф
Размещаем микросхему DD5.
17. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых
F
11
=3x6+2x7+5x5+5x4+4x3+4x3+4x2+7x1=116
F
12
=3x5+2x6+5x4+5x3+4x2+4x2+4x1+7x2 =96
F
13
=3x4+2x5+5x3+5x2+4x3+4x1+4x2+7x3 =92
F
14
=3x7+2x8+5x6+5x5+4x4+4x4+4x3+7x2=150
F
15
=3x6+2x7+5x5+5x4+4x3+4x3+4x2+7x3=130
F
16
=3x5+2x6+5x4+5x3+4x4+4x2+4x3+7x4=126
Микросхему DD5 размещаем в тринадцатую ячейку.
18. Рассчитываем коэффициент взвешенной связности для оставшихся
микросхем , с учетом того, что ранее размещались элементы.
*
76
.0
72
11
8
8
6
6
7
4
0
5
6
DD
Ф
69
.0
59
5
5
7
5
5
6
4
0
4
7
DD
Ф
68
.0
59
5
6
6
4
5
4
4
1
5
10
DD
Ф
Размещаем микросхему DD6.
19. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых
F
11
=5x6+0x7+4x5+7x4+6x3+6x3+8x2+8x1+11x2=160
F
12
=5x5+0x6+4x4+7x3+6x2+6x2+8x1+8x2+11x1=121
38
F
14
=5x7+0x8+4x6+7x5+6x4+6x4+8x3+8x2+11x3=215
F
15
=5x6+0x7+4x5+7x4+6x3+6x3+8x2+8x3+11x2=176
F
16
=5x5+0x6+4x4+7x3+6x4+6x2+8x3+8x4+11x1=165
Микросхему DD6 размещаем в двенадцатую ячейку.
20. Рассчитываем коэффициент взвешенной связности для оставшихся
микросхем , с учетом того, что ранее размещались элементы.
*
83
.0
59
8
5
5
7
5
5
6
4
0
4
7
DD
Ф
83
.0
59
9
5
6
6
4
5
4
4
1
5
10
DD
Ф
Размещаем микросхему DD7.
21. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых
F
11
=4x6+0x7+4x5+6x4+5x3+5x3+7x2+5x1+5x2+8x1=135
F
14
=4x7+0x8+4x6+6x5+5x4+5x4+7x3+5x2+5x3+8x2=184
F
15
=4x6+0x7+4x5+6x4+5x3+5x3+7x2+5x3+5x2+8x1=145
F
16
=4x5+0x6+4x4+6x3+5x4+5x2+7x3+5x4+5x1+8x2=146
Микросхему DD7 размещаем в одиннадцатую ячейку.
22. Размещаем последнюю микросхему DD10.
23. Рассчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых
F
14
=5x7+1x8+4x6+4x5+5x4+4x4+6x3+6x2+5x3+9x2+10x1=196
F
15
=5x6+1x7+4x5+4x4+5x3+4x3+6x2+6x3+5x2+9x1+10x2=169
F
16
=5x5+1x6+4x4+4x3+5x4+4x2+6x3+6x4+5x1+9x2+10x3=182
Микросхему DD10 размещаем в пятнадцатую ячейку.
39
XS1
DD4 5 DD8 DD7
3 DD9 DD11 DD6 DD10
DD2 DD1 DD3 DD5
Рисунок 2.4 – Размещение микросхем на коммутационном поле платы
Исходя из размещения микросхем на коммутационном поле платы со-
ставляется сборочный чертеж платы и спецификация к нему(см. приложе-
ние).
2.3 Расчет площади печатной платы
Выберем размер сторон платы для этого необходимо произвести рас-
чет площади платы. Расчет площади печатной платы производится по сле-
дующей формуле
УСТ
З
ЭЛ
ПП
S
m
k
S
S
,
(2.3)
где
УСТ
S
установочная площадь платы: если крепление платы по че-
тырем углам, то
УСТ
S
= 4*10*10=400 мм
2
;
ЭЛ
S
площадь элементов на плате:
З
k
коэффициент заполнения, можно принять
З
k
=0,4 или
З
k
=0,5;
m количество монтажных сторон платы m=1;
ЭЛ
S
площадь всех элементов, устанавливаемых на плате:
.
5,
7
5,
17
раз
ЭЛ
S
n
S
(2.4)
где n количество микросхем;
17,5*7,5 мм
2
установочная площадь микросхем;
.
раз
S
площадь разъема.
75
.
1507
4
16
1
5,
7
5,
17
11
ЭЛ
S
мм
2
Тогда площадь печатной платы должна быть больше
3415
400
1
5.
0
75
.
1507
ПП
S
мм
2
40
Исходя из рассчитанной площади платы, размеры сторон платы выбираем
80х115 мм.
41
3 ТРАССИРОВКА ШИН «ЗЕМЛЯ» И «ПИТАНИЕ» С
ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА ПОСТРОЕНИЯ
КСС
3.1 Трассировка шины «земля» с помощью алгоритма Краскала
Проведѐм трассировку шины «земля» с помощью алгоритма Краскала.
Этот алгоритм строит кратчайшую связующую сеть (КСС), которая должна
удовлетворять трѐм условиям:
1) длина рѐбер должна быть минимальна;
2) ребро должно быть инцидентно только одной вершине;
3) максимальное подключение проводников к одному контакту
ρ
max
= 3…4.
Построение КСС осуществляется путѐм последовательного выбора
рѐбер, удовлетворяющих трѐм условиям, при этом формируется массив ин-
дексов этих ребер, упорядоченный по возрастанию, который анализируется
по трѐм условиям. Условием получения покрывающего дерева является вы-
черчивание всех номеров вершин в массиве номеров.
По координатной сетке строим матрицу длин (количество клеток от
вывода к выводу по вертикали и горизонтали) шаг координатной сетки равен
2,5 мм.
K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11
K1
0 14 21 20 27 34 41 20 27 34
41
K2
0
7 26 19 20 27 34 27 20
27
K3
0 33 26 19 20 41 34 27
20
K4
0
7 14 21 8
7
14
21
K5
0
7 14 15 8
7
14
K6
0
7 22 15
8
7
K7
0 29 22 15
8
K8
0
7
14
21
K9
0
7
14
K10
0
7
K11
0
Рисунок 3.1 – Матрица длин
Составим массив рѐбер, упорядоченных по возрастанию. Для этого
можно использовать половину матрицы длин (по диагонали). Получаем мас-
сив
d
23
, d
45
, d
49
, d
56
, d
510
, d
67
, d
611
, d
89
, d
910
, d
1011
, d
48
, d
59
, d
610
, d
711
, d
12
, d
46
,
d
410
, d
57
, d
511
, d
810
, d
911
, d
25
и т.д.
Применяем алгоритм Краскала, анализируя массив по трѐм условиям,
42
в результате получаем:
d
23
, d
12
, d
25
, d
45
, d
49
, d
56
, d
510
, d
67
, d
611
, d
89
т.е. последовательность соеди-
нения микросхем:
DD8 – DD7 – DD4 – DD11 – DD9 – DD1– DD6– DD3- DD10- DD5-
DD2.
Рисунок проведения шины «земля» приведен в приложении. Шина
«земля» строится со стороны пайки.
3.2 Трассировка шины «питание» с помощью алгоритма Прима
К шине «питание» подключается 14-й вывод микросхем. Трассировку
шины «питание» проводим с помощью алгоритма Прима. В нѐм построение
КСС получаем путѐм присоединения не рѐбер, а ближайших изолированных
вершин. Алгоритм Прима работает с полной матрицей расстояний, которая
приведена на рис.3.2.
K1 K2 K3 K4 K5 K6 K7 K8 K9 K10 K11
K1
0 14 21 14 21 28 35 20 27 34
41
K2
14 0
7
8
7 14 21 34 27 20
27
K3
21 7
0 15 8
7 14 41 34 27
20
K4
14 8 15 0
7 14 21 26 19 20
27
K5
21 7
8
7
0
7 14 33 26 19
20
K6
28 14 7 14 7
0
7 40 33 26
19
K7
35 21 14 21 14 7
0 47 40 33
26
K8
20 34 41 26 33 40 47 0
7
14
21
K9
27 27 34 19 26 33 40 7
0
7
14
K10 34 20 27 20 19 26 33 14 7
0
7
K11 41 27 20 27 20 19 26 21 14
7
0
Рисунок 3.2 – Матрица расстояний
Просматриваем строки матрицы и выбираем элемент d
23
, являющийся
минимальным в этой строке. При наличии нескольких элементов с одинако-
выми минимальными значениями выбираем элемент с меньшим индексом.
Помечаем элемент d
23
: Исключаем из рассмотрения (вычѐркиваем) все эле-
менты второго третьего столбцов (рис.3.3).
43
K1 K4 K5 K6 K7 K8 K9 K10 K11
K1
0 14 21 28 35 20 27 34
41
K2
14 8
7 14 21 34 27 20
27
K3
21 15 8
7 14 41 34 27
20
K4
14 0
7 14 21 26 19 20
27
K5
21 7
0
7 14 33 26 19
20
K6
28 14 7
0
7 40 33 26
19
K7
35 21 14 7
0 47 40 33
26
K8
20 26 33 40 47 0
7
14
21
K9
27 19 26 33 40 7
0
7
14
K10 34 20 19 26 33 14 7
0
7
K11 41 27 20 19 26 21 14
7
0
Рисунок 3.3 – Матрица расстояний
Просматриваем вторую и третью строку матрицы и выбираем элемент
d
25
, являющийся первым минимальным в этих строках. Помечаем элемент
d
25
: Исключаем из рассмотрения (вычѐркиваем) все элементы пятого столбца
(рис.3.4).
K1 K4 K6 K7 K8 K9 K10 K11
K1
0 14 28 35 20 27 34
41
K2
14 8 14 21 34 27 20
27
K3
21 15 7 14 41 34 27
20
K4
14 0 14 21 26 19 20
27
K5
21 7
7 14 33 26 19
20
K6
28 14 0
7 40 33 26
19
K7
35 21 7
0 47 40 33
26
K8
20 26 40 47 0
7
14
21
K9
27 19 33 40 7
0
7
14
K10 34 20 26 33 14 7
0
7
K11 41 27 19 26 21 14
7
0
Рисунок 3.4 – Матрица расстояний
Просматриваем вторую, третью и пятую строку строки матрицы и вы-
бираем элемент d
36
являющийся первым минимальным в этих строках. По-
мечаем элемент d
36
: Исключаем из рассмотрения (вычѐркиваем) все элементы
шестого столбца (рис.3.5).
44
K1 K4 K7 K8 K9 K10 K11
K1
0 14 35 20 27 34
41
K2
14 8 21 34 27 20
27
K3
21 15 14 41 34 27
20
K4
14 0 21 26 19 20
27
K5
21 7 14 33 26 19
20
K6
28 14 7 40 33 26
19
K7
35 21 0 47 40 33
26
K8
20 26 47 0
7
14
21
K9
27 19 40 7
0
7
14
K10 34 20 33 14 7
0
7
K11 41 27 26 21 14
7
0
Рисунок 3.5 – Матрица расстояний
d
45
, являющийся первым минимальным. Помечаем элемент d
45
: Ис-
ключаем из рассмотрения (вычѐркиваем) все элементы четвертого столбца
(рис.3.6).
K1 K7 K8 K9 K10 K11
K1
0 35 20 27 34
41
K2
14 21 34 27 20
27
K3
21 14 41 34 27
20
K4
14 21 26 19 20
27
K5
21 14 33 26 19
20
K6
28 7 40 33 26
19
K7
35 0 47 40 33
26
K8
20 47 0
7
14
21
K9
27 40 7
0
7
14
K10 34 33 14 7
0
7
K11 41 26 21 14
7
0
Рисунок 3.6 – Матрица расстояний
d
67
, являющийся первым минимальным. Помечаем элемент d
67
: Ис-
ключаем из рассмотрения (вычѐркиваем) все элементы седьмого столбца
(рис.3.7).
45
K1 K8 K9 K10 K11
K1
0 20 27 34
41
K2
14 34 27 20
27
K3
21 41 34 27
20
K4
14 26 19 20
27
K5
21 33 26 19
20
K6
28 40 33 26
19
K7
35 47 40 33
26
K8
20 0
7
14
21
K9
27 7
0
7
14
K10 34 14 7
0
7
K11 41 21 14
7
0
Рисунок 3.7 – Матрица расстояний
d
21
, являющийся первым минимальным. Помечаем элемент d
21
: Ис-
ключаем из рассмотрения (вычѐркиваем) все элементы первого столбца
(рис.3.8).
K8 K9 K10 K11
K1
20 27 34
41
K2
34 27 20
27
K3
41 34 27
20
K4
26 19 20
27
K5
33 26 19
20
K6
40 33 26
19
K7
47 40 33
26
K8
0
7
14
21
K9
7
0
7
14
K10 14 7
0
7
K11 21 14
7
0
Рисунок 3.8 – Матрица расстояний
d
49
, являющийся первым минимальным. Помечаем элемент d
49
: Ис-
ключаем из рассмотрения (вычѐркиваем) все элементы девятого столбца
(рис.3.9).
46
K8 K10 K11
K1
20 34
41
K2
34 20
27
K3
41 27
20
K4
26 20
27
K5
33 19
20
K6
40 26
19
K7
47 33
26
K8
0
14
21
K9
7
7
14
K10 14
0
7
K11 21
7
0
Рисунок 3.9 – Матрица расстояний
d
98
, являющийся первым минимальным. Помечаем элемент d
98
: Ис-
ключаем из рассмотрения (вычѐркиваем) все элементы восьмого столбца
(рис.3.10).
K10 K11
K1
34
41
K2
20
27
K3
27
20
K4
20
27
K5
19
20
K6
26
19
K7
33
26
K8
14
21
K9
7
14
K10
0
7
K11
7
0
Рисунок 3.10 – Матрица расстояний
d
910
, являющийся первым минимальным. Помечаем элемент d
910
: Ис-
ключаем из рассмотрения (вычѐркиваем) все элементы десятого столбца
(рис.3.11).
47
K11
K1
41
K2
27
K3
20
K4
27
K5
20
K6
19
K7
26
K8
21
K9
14
K10
7
K11
0
Рисунок 3.11 – Матрица расстояний
Вершина одиннадцать последняя вершина присоединяема по алгорит-
му Прима d
1011
.
В результате применения алгоритма Прима и учитывая условия по-
строения КСС, соединяем микросхемы в следующей последовательности:
DD8 – DD7 – DD11 – DD6 – DD9 – DD10 – DD4– DD1– DD2– DD3–
DD5.
Трассировка шины «питание» приведена в приложении выполняется со
стороны монтажа элементов.
48
4 АЛГОРИТМЫ ТРАССИРОВКИ ПЕЧАТНОГО
МОНТАЖА
Проектирование печатного монтажа является одной из самых слож-
ных задач автоматизации проектирования РЭА. Для ее решения предложено
большое число различных алгоритмов.
Основным недостатком всех используемых в АСП программ является
заложенный в них принцип последовательного и фрагментального просмотра
коммутационного пространства. Локализация задачи в пределах одного
фрагмента не обеспечивает оптимизации монтажа в целом, так как качество
последующей разводки существенным образом зависит от ранее проведен-
ных трасс.
Задача проектирования печатного монтажа может быть сформулиро-
вана следующим образом. На коммутационной поверхности заданы своими
координатами (x,y) множество конструктивных элементов R={r
1
, r
2,
, ..., r
T
}.
Выводы этих элементов образуют некоторое множество из L связных под-
множеств:
ε
={C
1
, C
2
, …, C
L
}, причем каждое l-е подмножество C
l
объединяет
N
l
выводов конструктивных элементов из множества R в соответствии с
принципиальной электрической схемой. Кроме того, заданы расположение
групп контактных площадок разъемов и монтажных отверстий, а также ряд
требований, предъявляемых к топологии платы: минимальная ширина про-
водников и зазора между ними, размеры контактных площадок, число слоев
металлизации и способы перехода одного слоя на другой и т. п. Требуется с
учетом заданных конструкторско-технологических ограниений соединить
выводы конструктивных элементов внутри каждого подмножества C
l
ε
так, чтобы полученные соединения отвечали выбранному показателю качест-
ва.
На практике при оптимизации топологии печатного монтажа часто
используют следующие критерии качества:
минимум суммарной длины всех соединений;
минимум числа соединений проводников;
равномерность распределения проводников на печатной плате;
минимальная протяженность параллельных участков соседних
проводников;
минимум числа изгибов проводников;
минимум числа слоев металлизации и числа переходов из слоя в
слой (применяется при проектировании многослойных печатных плат).
Наибольшее распространение на практике получило разбиение рабо-
чего поля на правильные квадраты, что обеспечивает простую адресацию
ячеек в прямоугольной системе координат и привычную форму соединений.
Размеры ячеек определяются конструктивно-технологическими тре-
бованиями, предъявляемыми к печатному монтажу. Так как в каждой ячейке
49
обычно размещается только один вывод или печатный проводник, макси-
мальные размеры ячеек определяются допустимой точностью воспроизведе-
ния проводников. Минимальные размеры ячеек обуславливаются возможно-
стью запоминающих устройств ЭВМ и соотношением
(4.1)
где d — расстояние между центрами соседних ячеек; b
пр
— мини-
мальная ширина печатного проводника; l
з
— минимальное расстояние меж-
ду соседними проводниками.
Соединение выводов конструктивных элементов осуществляется в ре-
зультате последовательного заполнения ячеек трассами, конфигурация кото-
рых является локально оптимальной (соединения проводятся оптимальным
образом лишь по отношению к ранее построенным проводникам) в соответ-
ствии с выбранными критериями трассировки. Необходимо заметить, что при
последовательном процессе проведения трасс, поскольку многие соединения
конкурируют между собой, число разведенных цепей и их конфигурация оп-
ределяются последовательностью трассировки отдельных соединений.
Известные алгоритмы трассировки печатных плат можно условно
разбить на три большие группы:
1) волновые алгоритмы, основанные на идеях Ли и разработанные
Ю. Л. Зиманом и Г. Г. Рябовым. Данные алгоритмы получили широкое
распространение в существующих АСП, поскольку они позволяют легко
учитывать технологическую специфику печатного монтажа со всей
совокупностью конструктивных ограничений. Эти алгоритмы всегда
гарантируют построение трассы, если путь для нее существует;
2) ортогональные
алгоритмы,
обладающие
большим
быстродействием, чем алгоритмы первой группы. Реализация их на ЭВМ
требует 75…100 раз меньше вычислений по сравнению с волновыми
алгоритмами. Такие алгоритмы применяют при проектировании печатных
плат со сквозными металлизированными отверстиями. Недостатки этой
группы алгоритмов связаны с получением большого числа переходов со слоя
на слой, отсутствием 100%-ной гарантии проведения ряда трасс, большим
числом параллельно идущих проводников;
3) алгоритмы эвристического типа, получающие все более широкое
распространение. Эти алгоритмы частично основаны на эвристическом
приме поиска пути в лабиринте. При этом каждое соединение проводится по
кратчайшему пути, обходя встречающиеся на пути препятствия.
4.1 Волновой алгоритм Ли
Данный алгоритм является классическим примером использования
методов динамического программирования для решения задач трассировки
печатных соединений. Основные принципы построения трасс с помощью
d ≥ b
пр
+l
з
,
50
волнового алгоритма сводятся к следующему.
Все ячейки монтажного поля подразделяют на занятые и свободные.
Занятыми, считают ячейки, в которых уже расположены проводники, постро-
енные на предыдущих шагах, или находятся монтажные выводы элементов, а
также ячейки, соответствующее границе платы и запрещенным для прокла-
дывания проводников участкам. Каждый раз при проведении новой трассы
можно использовать лишь свободные ячейки, число которых по мере прове-
дения трасс сокращается.
На множестве свободных ячеек коммутационного поля моделируют
волну влияния из одной ячейки в другую, соединяемых впоследствии общим
проводником. Первую ячейку, в которой зарождается волна влияний, назы-
вают источником, а вторую — приемником волны. Чтобы иметь возможность
следить за происхождением фронта влияний, его фрагментам на каждом эта-
пе присваивают некоторые веса:
(4.2)
где P
k
и P
k-1
- веса ячеек k-ого и (k-1)-ого фронтов; ψ(f
1
, f
2
, … , f
g
) —
весовая функция, являющаяся показателем качества проведения пути, каж-
дый параметр которой f
i
(i=1, 2, …,g) характеризует путь с точки зрения одно-
го из критериев качества (длины пути, числа пересечений и т. п.). На P
k
на-
кладывают одно ограничение – веса ячеек предыдущих фронтов не должны
быть больше весов ячеек последующих фронтов.Фронт распространяется
только на соседние ячейки, которые имеют с ячейками предыдущего фронта
либо общую сторону, либо хотя бы одну общую точку. Процесс распростра-
нения волны продолжается до тех пор, пока ее расширяющийся фронт не
достигнет приемника или на Θ-ом шаге не найдется ни одной свободной
ячейки, которая могла бы быть включена в очередной фронт, что соответст-
вует случаю невозможности проведения трассы при заданных ограничениях.
Если в результате распространения волна достигла приемника, то
осуществляют «проведение пути», которое заключается в движении от при-
емника к источнику по пройденным на этапе распространения волны ячей-
кам следя за тем, чтобы значения P
k
монотонно убывали. В результате полу-
чают путь, соединяющий эти две точки. Из описания алгоритма следует, что
все условия, необходимые для проведения пути, закладываются в правила
веса ячейкам.
Чтобы исключить неопределенность при проведении пути для случая,
когда несколько ячеек имеют одинаковый минимальный вес, вводят понятие
путевых координат, задающих предпочтительность проведения трассы. Каж-
дое направление кодируют двоичным числом по mod q, где q – число про-
сматриваемых соседних ячеек. При этом чем более предпочтительно то или
иное направление, тем меньший числовой код оно имеет. Например, если за-
даться приоритетным порядком проведения пути сверху, справа, снизу и сле-
ва, то коды соответствующих путевых координат будут 00, 01, 10 и 11. При-
P
k
= P
k-1
+ ψ (f
1
, f
2
, … , f
g
)*,
51
писание путевых координат производят на этапе распространения волны.
При проведении пути движение от ячейки к ячейке осуществляют по путе-
вым координатам.
На рисунке 4.1 приведен пример проведение трассы от восьмого вы-
вода микросхемы DD11 к первому выводу микросхемы DD8 на рисунке по-
казана как распространяется волна по монтажному пространству.
Рисунок 4.1 - Процесс распространения волны
В каждой ячейке указаны приписанные ей на этом этапе распростра-
нения волны путевые координаты и леса. Ячейка B достигается при построе-
нии 11-го фронта волны.
Проведение пути начинаем от первого вывода микросхемы DD8 .
Просматриваем окрестность точки приемника и находим ячейку, которая в
наиболее предпочтительном направлении имеет вес на единицу меньше. Пе-
ремещаемся в эту ячейку и отмечаем след перехода. Процесс продолжаем до
тех пор, пока след не приведет в точку начала распространения волны. Из
52
рисунка видно, что построенный проводник действительно является крат-
чайшим между точками.
Рисунок 4.2 - Процесс распространения волны
На рисунке 4.2 приведен пример проведение трассы от восьмого вы-
вода микросхемы DD6 к первому выводу микросхемы DD10 на рисунке по-
казана как распространяется волна по монтажному пространству.
В каждой ячейке указаны приписанные ей на этом этапе распростра-
нения волны путевые координаты и леса. Ячейка B достигается при построе-
нии 10-го фронта волны.
Проведение пути начинаем от первого вывода микросхемы DD10.
Просматриваем окрестность точки приемника и находим ячейку, которая в
наиболее предпочтительном направлении имеет вес на единицу меньше. Пе-
ремещаемся в эту ячейку и отмечаем след перехода. Процесс продолжаем до
тех пор, пока след не приведет в точку начала распространения волны. Из
рисунка видно, что построенный проводник действительно является крат-
чайшим между точками.
53
Рисунок 4.3 - Процесс распространения волны
На рисунке 4.3 приведен пример проведение трассы от третьего выво-
да микросхемы DD1 к десятому выводу микросхемы DD1 на рисунке показа-
на как распространяется волна по монтажному пространству.
В каждой ячейке указаны приписанные ей на этом этапе распростра-
нения волны путевые координаты и леса. Ячейка B достигается при построе-
нии 6-го фронта волны.
Проведение пути начинаем от десятого вывода микросхемы DD1 .
Просматриваем окрестность точки приемника и находим ячейку, которая в
наиболее предпочтительном направлении имеет вес на единицу меньше. Пе-
ремещаемся в эту ячейку и отмечаем след перехода. Процесс продолжаем до
тех пор, пока след не приведет в точку начала распространения волны. Из
рисунка видно, что построенный проводник действительно является крат-
чайшим между точками.
54
ЗАКЛЮЧЕНИЕ
В результате работы были получены следующие результаты:
- с помощью последовательного алгоритма компоновки элементы элек-
трической функциональной схемы были разбиты по корпусам микросхем и
на основе проделанных расчетов разработана схема электрическая принци-
пиальная;
- с помощью алгоритма размещения корпуса микросхем были оптималь-
но распределены по посадочным местам на монтажном поле платы относи-
тельно разъема, а также на основе расчетов был разработан сборочный чер-
теж;
-по методам трассировки оптимально, с точки зрения длины проводни-
ков, была проведена трассировка шины питания (по алгоритму Прима), ши-
ны земли (по алгоритму Краскала) и сигнальных цепей (по волновому алго-
ритму). На основе поведенной трассировки был разработан чертеж печатной
платы.
55
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Деньдобренко, Б. Н. Автоматизация конструирования РЭА: Учебник
для вузов / Б. Н. Деньдобренко, А. С. Малика. – М.: Высш. шк., 1980.
2. Корячко, В. П. Теоретические основы САПР: Учебник для вузов /
В.П. Корячко, В.М. Курейчик, И.П. Норенков – М.: Энергоатомиздат, 1987.
3. Методические указания к лабораторным работам по курсу «Автома-
тизация конструкторского и технологического проектирования РЭС» для
студентов специальности 1-39 02 01/ А. И. Толстая, и др.;– Минск: БГУИР,
2008.
4. ГОСТ 2.701-84 ЕСКД. Схемы. Виды и типы. Общие требования к
выполнению.
5. ГОСТ 2.710-81 ЕСКД. Обозначения буквенно-цифровые в электриче-
ских схемах.
56
ПРИЛОЖЕНИЕ
Информация о работе Трассировка шин «земля» и «питание» с использованием алгоритма по- строения КСС