АКИТ
Автор: Пользователь скрыл имя, 19 Декабря 2012 в 19:16, курсовая работа
Описание работы
Цель курсовой работы
- с помощью последовательного алгоритма компоновки элементы
электрической функциональной схемы были разбиты по корпусам микросхем
и на основе проделанных расчетов разработана схема электрическая
принципиальная;
- с помощью алгоритма размещения корпуса микросхем были
оптимально распределены по посадочным местам на монтажном поле платы
относительно разъема, а также на основе расчетов был разработан сборочный
чертеж;
-по методам трассировки оптимально, с точки зрения длины
проводников, была проведена трассировка шины питания (по
алгоритму Прима), шины земли (по алгоритму Краскала) и
сигнальных цепей (по волновому алгоритму). На основе поведенной
трассировки был разработан чертеж печатной платы
Содержание
Введение.................................................................................................................. 5
1 Покрытие электрической схемы и компоновка модулей микросхем при по-
мощи последовательного алгоритма компоновки................................................. 5
1.1 Покрытие электрической схемы..................................................................... 5
1.2 Общее описание алгоритма............................................................................. 5
1.3 Пошаговое описание алгоритма ..................................................................... 7
2 Размещение микросхем на плате....................................................................... 22
2.1 Обще описание алгоритма............................................................................... 22
2.2 Пошаговая работа алгоритма.......................................................................... 23
2.3 Расчет площади печатной платы .................................................................... 30
3 Алгоритмы трассировки печатного монтажа................................................... 32
3.1 Волновой алгоритм Ли .................................................................................... 33
4 Трассировка шин «земля» и «питание» с использованием алгоритма по-
строения ксс......................................................................................................... 37
4.1 Трассировка шины «земля» с помощью алгоритма Краскала..................... 37
4.2 Трассировка шины «питание» с помощью алгоритма Прима..................... 39
Заключение ................................................................................................................ 42
Список использованной литературы....................................................................... 43
Работа содержит 1 файл
4
Содержание
Введение.................................................................................................................. 5
1 Покрытие электрической схемы и компоновка модулей микросхем при по-
мощи последовательного алгоритма компоновки................................................. 5
1.1 Покрытие электрической схемы..................................................................... 5
1.2 Общее описание алгоритма............................................................................. 5
1.3 Пошаговое описание алгоритма ..................................................................... 7
2 Размещение микросхем на плате....................................................................... 22
2.1 Обще описание алгоритма............................................................................... 22
2.2 Пошаговая работа алгоритма.......................................................................... 23
2.3 Расчет площади печатной платы .................................................................... 30
3 Алгоритмы трассировки печатного монтажа................................................... 32
3.1 Волновой алгоритм Ли .................................................................................... 33
4 Трассировка шин «земля» и «питание» с использованием алгоритма по-
строения ксс......................................................................................................... 37
4.1 Трассировка шины «земля» с помощью алгоритма Краскала..................... 37
4.2 Трассировка шины «питание» с помощью алгоритма Прима..................... 39
Заключение ................................................................................................................ 42
Список использованной литературы....................................................................... 43
Приложение ............................................................................................................... 44
5
ВВЕДЕНИЕ
Процесс проектирования РЭС является чрезвычайно трудоемким, по-
скольку РЭС является сложной технической системой. Поэтому целесооб-
разно разделение проектных работ на различные стадии, уровни, аспекты и
их автоматизация.
Процесс проектирования РЭС подразделяется на следующие этапы:
1)
системотехническое проектирование – исходя из всестороннего
анализа ТЗ, принимается решение относительно методики построения и реа-
лизации заданных функций, разрабатывается структурная схема РЭС и алго-
ритмы функционирования отдельных элементов структуры;
2)
схемотехническое проектирование – осуществляется переход от
структурной схемы к функциональной, затем к принципиальной, выбирается
элементная база и рассчитываются номиналы всех элементов;
3)
информационное проектирование – создается необходимое при-
кладное и системное ПО;
4)
конструкторское проектирование – решает задачи синтеза конст-
рукций изделия в целом, определяет компоновку и размещение, разрабатыва-
ет топологию электрических соединений;
5)
технологическое проектирование – создание необходимой техноло-
гической документации для сборки, проверки, создания необходимой техно-
логической оснастки для изготовления деталей конструкции.
Цель курсовой работы
- с помощью последовательного алгоритма компоновки элементы
электрической функциональной схемы были разбиты по корпусам микросхем
и на основе проделанных расчетов разработана схема электрическая
принципиальная;
- с помощью алгоритма размещения корпуса микросхем были
оптимально распределены по посадочным местам на монтажном поле платы
относительно разъема, а также на основе расчетов был разработан сборочный
чертеж;
-по методам трассировки оптимально, с точки зрения длины
проводников, была проведена трассировка шины питания (по
алгоритму Прима), шины земли (по алгоритму Краскала) и
сигнальных цепей (по волновому алгоритму). На основе поведенной
трассировки был разработан чертеж печатной платы
6
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)
В каждом подграфе число вершин не должно превосходить ранее за-
данного ограничения на число модулей в микросхеме.
Для любого разбиения должны выполняться следующие условия
7
G
G
n
i
i
1
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
8-й шаг. Составляем матрицу смежности, заменяя вершины x
i
и x
j
од-
ной вершиной x
ij
(суммируя связи). И базовой вершиной считаем x
ij
.
9-й шаг. Повторяем шаги 5,6,7 и 8 до тех пор, пока не будет скомпо-
нована микросхема.
10-й шаг. Приступаем к формированию нового подграфа со 2-го шага,
убрав из общего графа, сформированный подграф.
11-й шаг. Повторяем алгоритм компоновки до тех пор, пока все моду-
ли узла не будут скомпонованы в микросхемы.
На электрическая функциональная имеется три типа модулей, отно-
сящихся к микросхемам К155ТВ6 К155ЛИ1и К155ЛИ4 (рис.1.1).
а)
б)
в)
Рисунок 1.1 – Типы модулей:
а) микросхемы К155ЛИ1;
б) микросхемы К555ЛИ4
в) микросхемы К555ТВ6
На рис.1.2 приведено условное графическое изображение (УГО) мик-
росхем.
9
а)
б)
в)
Рисунок 1.2 – УГО микросхем:
1-ый шаг. Разбиваем схему электрическую функциональную на от-
дельные узлы, содержащие однотипные модули, оставляя связи внутри узлов
(рис.1.4).
Рисунок 1.3 – Функциональная схема:
10
2-ой шаг. Составляем граф-схему (рис.1.4) для первого функциональ-
ного узла, петли не учитываем.
Рисунок 1.4 – Граф-схема
3-ий шаг. Составляем по граф-схеме матрицу смежности и подсчиты-
ваем степени вершин (рис.1.5).
z
1
z
2
z
3
z
4
z
5
z
6
z
7
z
8
p
i
z
1
0
0
0
0
0
0
0
0
0
z
2
0
0
0
0
1
0
0
0
1
z
3
0
0
0
0
0
0
0
0
0
z
4
0
0
0
0
0
1
0
0
1
z
5
0
1
0
0
0
0
1
0
2*
z
6
0
0
0
1
0
0
0
0
1
z
7
0
0
0
0
1
0
0
1
2
z
8
0
0
0
0
0
0
1
0
1
Рисунок 1.5 – Матрица смежности
4-ый шаг. За базовую принимаем вершину, имеющую максимальную
степень. За базовую принимаем вершину z
5
(отмечена знаком «*» на рис.1.5).
5-ый шаг. Вершина z
1
имеет отображение Гz
1
= {z
2
, z
7
}.
6-ой шаг. Вычисляем функционалы по формуле (1.4).
Lz
2
= 1 – 1 = 0*;
Lz
7
= 2 – 1 = 1.
7-ой шаг. Выбираем вершину z
2
.
8-ой шаг. Стягиваем вершину z
2
с базовой вершиной z
5
и составляем
матрицу смежности, суммируя связи и обнуляя ее по главной диагонали
11
(рис.1.6). Частичный граф показан на рис.1.7.
z
1
z
3
z
4
z5z2
z
6
z
7
z
8
p
i
z
1
0
0
0
0
0
0
0
0
z
3
0
0
0
0
0
0
0
0
z
4
0
0
0
0
1
0
0
1
z5z2
0
0
0
0
0
1
0
2*
z
6
0
0
1
0
0
0
0
1
z
7
0
0
0
1
0
0
1
2
z
8
0
0
0
0
0
1
0
1
Рисунок 1.6 – Матрица смежности с базовой вершиной z*
52
9-ый шаг. Повторяем шаги 5, 6, 7.
Функционалы:
Lz
7
= 2 – 1 = 1.
Стягиваем вершину z
7
с вершиной z
5z2
. Частичный граф и матрица
смежности показаны на рис.1.7 и 1.8 соответственно.
z
1
z
3
z
4
z5z2z7
z
6
z
8
p
i
z
1
0
0
0
0
0
0
0
z
3
0
0
0
0
0
0
0
z
4
0
0
0
0
1
0
1
z5z2z7
0
0
0
0
0
1
3*
z
6
0
0
1
0
0
0
1
z
8
0
0
0
1
0
0
1
Рисунок 1.7 – матрица смежности с базовой вершиной z*
527
Выполняем дальше шаги в заданной последовательности. Подсчиты-
ваем функционалы:
Lz
8
= 1 – 1 = 0.
Вершина x
8
является последним модулем в микросхеме. Так как мик-
росхема К155ЛИ1 имеет 4 модуля, то она уже скомпонована.
Так как осталось четыре вершины, то оставшиеся вершины составля-
ют вторую микросхему К155ЛИ1 .
12
Та как К555ЛИ4 состоит из 3 модулей и у нас всего три модуля, то
они составят одну микросхему.
Составим граф-схему и матрицу смежности для третьего функцио-
нального узла К555ТВ6 рисунок 1.8 и рисунок 1.9.
Рисунок 1.8 – Граф-схема
x
1
x
2
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
x
11
x
12
ρ
i
x
1
0
9 9 9 9 9 9 9 9 9
9
9 99*
x
2
9
0 9 9 9 9 9 9 9 9
9
9 99
x
3
9
9 0 9 9 9 9 9 9 9
9
9 99
x
4
9
9 9 0 9 9 9 9 9 9
9
9 99
x
5
9
9 9 9 0 9 9 9 9 9
9
9 99
x
6
9
9 9 9 9 0 9 9 9 9
9
9 99
x
7
9
9 9 9 9 9 0 9 9 9
9
9 99
x
8
9
9 9 9 9 9 9 0 9 9
9
9 99
x
9
9
9 9 9 9 9 9 9 0 9
9
9 99
x
10
9
9 9 9 9 9 9 9 9 0
9
9 99
x
11
9
9 9 9 9 9 9 9 9 9
0
9 99
x
12
9
9 9 9 9 9 9 9 9 9
9
0 99
Рисунок 1.9 – Матрица смежности
13
За базовую принимаем вершину, имеющую максимальную степень. За
базовую принимаем вершину x
1
(отмечена знаком «*» на рис.1.5).
Вершина x
1
имеет отображение Гx
1
= { x
2
, x
3
, x
4
, x
5
, x
6
, x
7
, x
8 .
x
9
, x
10
,
x
11
, x
12
, }.
Вычисляем функционалы по формуле (1.4).
Lx
2
= 99 –9 =90;
Lx
3
= 99 – 9 =90;
Lx
4
= 99 – 9 =90;
Lx
5
= 99 – 9 =90;
Lx
6
= 99 – 9 =90;
Lx
7
= 99 – 9 =90;
Lx
8
= 99 – 9 =90;
Lx
9
= 99 – 9 =90;
Lx
10
= 99 – 9 =90;
Lx
11
= 99 – 9 =90;
Lx
12
= 99 – 9 =90.
Выбираем вершину x
2
.
Стягиваем вершину x
2
с базовой вершиной x
5
Так как микросхема
К155ЛИ1 состоит из 2 модулей, то она уже скомпонована. Удаляем столбцы
и строки из матрицы.
x
3
x
4
x
5
x
6
x
7
x
8
x
9
x
10
x
11
x
12
ρ
i
x
3
0 9 9 9 9 9 9 9
9
9 81*
x
4
9 0 9 9 9 9 9 9
9
9 81
x
5
9 9 0 9 9 9 9 9
9
9 81
x
6
9 9 9 0 9 9 9 9
9
9 81
x
7
9 9 9 9 0 9 9 9
9
9 81
x
8
9 9 9 9 9 0 9 9
9
9 81
x
9
9 9 9 9 9 9 0 9
9
9 81
x
10
9 9 9 9 9 9 9 0
9
9 81
x
11
9 9 9 9 9 9 9 9
0
9 81
x
12
9 9 9 9 9 9 9 9
9
0 81
Рисунок 1.10 – Матрица смежности
За базовую принимаем вершину, имеющую максимальную степень. За
базовую принимаем вершину x
3
(отмечена знаком «*» на рис.1.10).
Вершина x
3
имеет отображение Гx
3
= { x
3
, x
4
, x
5
, x
6
, x
7
, x
8 .
x
9
, x
10
, x
11
,
x
12
, }.
Вычисляем функционалы по формуле (1.4).
14
Lx
4
= 81 – 9 =72;
Lx
5
= 81 – 9 =72;
Lx
6
= 81 – 9 =72;
Lx
7
= 81 – 9 =72;
Lx
8
= 81 – 9 =72;
Lx
9
= 81 – 9 =72;
Lx
10
= 81 – 9 =72;
Lx
11
= 81 – 9 =72;
Lx
12
= 81 – 9 =72.
Выбираем вершину x
4
.
Стягиваем вершину x
4
с базовой вершиной x
3
так как микросхема
К155ЛИ1 состоит из 2 модулей, то она уже скомпонована. Удаляем столбцы
и строки из матрицы.
x
5
x
6
x
7
x
8
x
9
x
10
x
11
x
12
ρ
i
x
5
0 9 9 9 9 9
9
9 63*
x
6
9 0 9 9 9 9
9
9 63
x
7
9 9 0 9 9 9
9
9 63
x
8
9 9 9 0 9 9
9
9 63
x
9
9 9 9 9 0 9
9
9 63
x
10
9 9 9 9 9 0
9
9 63
x
11
9 9 9 9 9 9
0
9 63
x
12
9 9 9 9 9 9
9
0 63
Рисунок 1.11 – Матрица смежности
За базовую принимаем вершину, имеющую максимальную степень. За
базовую принимаем вершину x
5
(отмечена знаком «*» на рис.1.11).
Вершина x
5
имеет отображение Гx
5
= { x
6
, x
7
, x
8 .
x
9
, x
10
, x
11
, x
12
, }.
Вычисляем функционалы по формуле (1.4).
Lx
6
= 54;
Lx
7
= 54;
Lx
8
=54;
Lx
9
= 54;
Lx
10
= 54;
Lx
11
= 54;
Lx
12
= 54.
Выбираем вершину x
6
.
Стягиваем вершину x
6
с базовой вершиной x
5
так как микросхема
К155ЛИ1 состоит из 2 модулей, то она уже скомпонована. Удаляем столбцы
15
и строки из матрицы.
x
7
x
8
x
9
x
10
x
11
x
12
ρ
i
x
7
0 9 9 9
9
9 45*
x
8
9 0 9 9
9
9 45
x
9
9 9 0 9
9
9 45
x
10
9 9 9 0
9
9 45
x
11
9 9 9 9
0
9 45
x
12
9 9 9 9
9
0 45
Рисунок 1.12 – Матрица смежности
За базовую принимаем вершину, имеющую максимальную степень. За
базовую принимаем вершину x
7
(отмечена знаком «*» на рис.1.12).
Вершина x
7
имеет отображение Гx
7
= { x
8 .
x
9
, x
10
, x
11
, x
12
, }.
Вычисляем функционалы по формуле (1.4).
Lx
8
=36;
Lx
9
= 36;
Lx
10
= 36;
Lx
11
= 36;
Lx
12
= 36.
Выбираем вершину x
8
.
Стягиваем вершину x
8
с базовой вершиной x
7
так как микросхема
К155ЛИ1 состоит из 2 модулей, то она уже скомпонована. Удаляем столбцы
и строки из матрицы.
x
9
x
10
x
11
x
12
ρ
i
x
9
0 9
9
9 27*
x
10
9 0
9
9 27
x
11
9 9
0
9 27
x
12
9 9
9
0 27
Рисунок 1.13 – Матрица смежности
За базовую принимаем вершину, имеющую максимальную степень. За
базовую принимаем вершину x
9
(отмечена знаком «*» на рис.1.13).
Вершина x
9
имеет отображение Гx
9
= { x
10
, x
11
, x
12
, }.
Вычисляем функционалы по формуле (1.4).
Lx
10
= 18;
Lx
11
= 18;
16
Lx
12
= 18.
Выбираем вершину x
10
.
Стягиваем вершину x
10
с базовой вершиной x
9
так как микросхема
К155ЛИ1 состоит из 2 модулей, то она уже скомпонована.
Так как оформление схем электрических принципиальных должно со-
ответствовать [4], то окончательный вариант схемы электрической принци-
пиальной приведѐн в приложении. В этом варианте нумерация микросхем
учитывалась в соответствии с [4]. К схеме электрической принципиальной
составляется перечень элементов, также приведенный в приложении.
17
2 РАЗМЕЩЕНИЕ МИКРОСХЕМ НА ПЛАТЕ
2.1 Общее описание алгоритма
После распределения конструктивных элементов РЭА по коммутаци-
онным пространствам различного уровня иерархии для каждой полученной в
результате компоновки сборочной единицы производят размещение вклю-
чѐнных в его состав элементов предыдущего уровня, т.е. выбирают такое их
взаимное расположение, при котором наилучшим образом учитываются
предъявляемые к аппаратуре требования.
Исходной информацией, при решении задач размещения являются
данные о конфигурации и размерах коммутационного пространства, опреде-
ляемые требованиями установки и крепления данной сборочной единицы в
аппаратуре. Количество и геометрические размеры конструктивных элемен-
тов, подлежащих размещению, схема соединений, а также ряд ограничений
на взаимное расположение отдельных элементов, учитывающие особенности
разрабатываемой конструкции.
Задача сводится к отысканию для каждого размещаемого элемента та-
ких позиций, при которых оптимизируется выбранный показатель качества и
обеспечиваются наиболее благоприятные условия для последующего эле-
ментного монтажа. Особое значение эта задача приобретает при проектиро-
вании аппаратуры на печатных платах. Основная сложность в постановке за-
дач размещения заключается в выборе целевой функции. Связано это с тем,
что одной из главных целей размещения является создание наилучших усло-
вий для дальнейшей трассировки соединений, что невозможно проверить без
проведения самой трассировки.
Следовательно, если для оценки качества размещения элементов вы-
брать критерий непосредственно связанный с получением оптимального ри-
сунка металлизации печатной платы, то конечный результат может быть
найден только при совместном решении задачи размещения, выбора очеред-
ности проведения соединения и трассировки, что практически невозможно
уже для схем средней сложности вследствие огромных затрат машинного
времени. Поэтому все применяемые в настоящее время алгоритмы размеще-
ния используют промежуточные критерии, которые лишь качественно спо-
собствуют решению основной задачи, получению оптимальной трассировки
соединений. К таким критериям относятся:
1) Минимум суммарной взвешенной длины соединений.
2) Минимальное число соединений, длина которых больше задан-
ной.
3) Минимальное число пересечений проводников.
4) Максимальное число соединений между элементами, находящи-
мися в соседних позициях, либо в позициях указанных разработчиком.
5) Максимальное число цепей простой конфигурации.
18
Наибольшее распространение в алгоритме размещения получил пер-
вый критерий, что объясняется следующими причинами:
1) Уменьшение длин соединений улучшает электрические характе-
ристики устройства.
2) Упрощает трассировку печатных проводников.
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-ой вершиной.
19
4) Для вершины, у которой коэффициент взвешенной связности
максимальный, находим посадочное место на коммутационном поле из усло-
вия, что коэффициент размещения минимален. Коэффициент размещения
определяется по формуле:
fl
n
f
ij
f
d
a
F
1
,
(2.2)
где d
fl
– количество связей ячейки f с ранее закрепленной ячейкой l, в
которой размещена вершина x
i
;
n – количество не занятых посадочных мест.
5) Шаги 3, 4 повторяются до тех пор, пока все элементы не будут
размещены на плате.
DD1 DD2 DD3 DD4 DD5 DD6 DD7 DD8 DD9 XP1
pi
DD1
0
4
2
36
2
36
36
36
36 9 197
DD2
4
0
0
2
5
3
2
1
0
6
23
DD3
2
0
0
1
4
2
3
1
2
4
19
DD4
36
2
1
0
1
36
36
36
36 8 192
DD5
2
5
4
1
0
1
2
2
2
9
28
DD6
36
3
2
36
1
0
36
36
36 8 194
DD7
36
2
3
36
2
36
0
36
36 8 195
DD8
36
1
1
36
2
36
36
0
36 8 192
DD9
36
0
2
36
2
36
36
36
0
8 192
XP1
9
6
4
8
9
8
8
8
8
0 197
Рисунок 2.1 – Матрица смежности
1
2
5
8 11
3
6
9 12
4
7 10 13
Рисунок 2.2 – Коммутационное поле платы
1.По рисунку 2.2 составим матрицу расстояний (рис.2.3).
20
1 2 3 4 5 6 7 8 9 10 11 12 13
1
0 1 1 1 6 2 2 5 4 3 6 5 4
2
1 0 1 2 1 2 3 2 3 4 3 4 5
3
1 1 0 1 6 1 2 5 4 3 6 5 4
4
1 2 1 0 5 2 1 4 3 2 5 4 3
5
6 1 6 5 0 1 4 1 2 3 2 3 4
6
2 2 1 2 1 0 1 2 1 2 3 2 3
7
2 3 2 1 4 1 0 3 2 1 4 3 2
8
5 2 5 4 1 2 3 0 1 2 1 2 3
9
4 3 4 3 2 1 2 1 0 1 2 1 2
10 3 4 3 2 3 2 1 2 1 0 3 2 1
11 6 3 6 5 2 3 4 1 2 3 0 1 2
12 5 4 5 4 3 2 3 2 1 2 1 0 1
13 4 5 4 3 4 3 2 3 2 1 2 1 0
Рисунок 2.3 – Матрица расстояний
2.Так как все микросхемы не распределены по посадочным местам, то
рассчитываем коэффициент взвешенной связности для всех микросхем по
формуле (2.1).
05
.0
197
9
1
DD
Ф
04
.0
194
8
6
DD
Ф
26
.0
23
6
2
DD
Ф
04
.0
195
8
7
DD
Ф
21
.0
19
4
3
DD
Ф
04
.0
192
8
8
DD
Ф
04
.0
192
8
4
DD
Ф
04
.0
192
8
9
DD
Ф
*
32
.0
28
9
5
DD
Ф
Выбираем для размещения микросхему, имеющую максимальный ко-
эффициент взвешенной связности. Такой микросхемой является микросхема
DD5(помечена знаком "*").
3.Расчитываем коэффициент размещения для посадочных мест
3,4,5,7,..13 по формуле (2.2), в которой элемент a
ij
– количество связей вер-
шины DD5 с вершиной ХS1(см. матрицу смежности).
F
3
=9х1=9*
F
9
=9х4=36
21
F
4
=9х1=9
F
10
=9х3=27
F
5
=9х6=54
F
11
=9х6=54
F
6
=9х2=18
F
12
=9х5=45
F
8
=9х5=45
F
13
=9х4=36
Выбираем минимальный коэффициент размещения. Так как мини-
мальным является коэффициент F для ячеек 3 и 4, то выбираем ячейку с ми-
нимальным индексом. Такой ячейкой является ячейка 3. Следовательно,
микросхему DD5 размещаем в третей ячейке.
4.Рассчитываем коэффициент взвешенной связности для остальных
неразмещенных микросхем, с учетом того, что ранее размещенными элемен-
тами являются микросхема DD5 и разъем XS1. Т.е. формулу 2.1 можно запи-
сать в виде:
j
DD
j
x
j
p
a
a
Ф
3
1
06
.0
197
2
9
1
DD
Ф
05
.0
194
1
8
6
DD
Ф
*
48
.0
23
5
6
2
DD
Ф
05
.0
195
2
8
7
DD
Ф
42
.0
19
4
4
3
DD
Ф
05
.0
192
2
8
8
DD
Ф
05
.0
192
1
8
4
DD
Ф
05
.0
192
2
8
9
DD
Ф
Так как максимальный коэффициент взвешенной связности имеет
микросхема DD2, то размещаем эту микросхему на коммутационное поле
платы.
5.Расчитываем коэффициент размещения для оставшихся ячеек по
формуле 2.2, с учетом ранее занятых. Т.е. формулу 2.2 можно записать в сле-
дующем виде:
2
5
1
1
2
f
DD
DD
f
X
DD
f
d
a
d
a
F
22
F
9
=6х4+5х4 =44
F
4
=6х1+5х1 =11* F
10
=6х3+5х3 =33
F
5
=6х6+5х6 =66
F
11
=6х6+5х6 =66
F
6
=6х2+5х2 =22
F
12
=6х5+5х5 =55
F
8
=6х5+5х5 =55
F
13
=6х4+5х4 =44
Минимальный коэффициент размещения имеет ячейка 4. Следова-
тельно, микросхему DD2 размещаем в четвертой ячейке коммутационного
поля.
6.Расчитываем коэффициент взвешенной связности для оставшихся
микросхем
08
.0
197
4
2
9
1
DD
Ф
06
.0
194
3
1
8
6
DD
Ф
06
.0
195
2
2
8
7
DD
Ф
*
42
.0
19
0
4
4
3
DD
Ф
06
.0
192
1
2
8
8
DD
Ф
06
.0
192
2
1
8
4
DD
Ф
06
.0
192
0
2
8
9
DD
Ф
Выбираем для размещения микросхему, имеющую максимальный ко-
эффициент взвешенной связности. Такой микросхемой является микросхема
DD3.
F
5
=4х6+4х6+0х5 =20
F
10
=4х3+4х3+0х2 =28
F
6
=4х2+4х2+0х1 =12
F
11
=4х6+4х6+0х5 =36
F
8
=4х5+4х5+0х4 =28
F
12
=4х5+4х5+0х4 =28
F
9
=4х4+4х4+0х3 =20
F
13
=4х4+4х4+0х3 =36
Минимальный коэффициент размещения имеет ячейка 6. Микросхему DD3
размещаем в шестой ячейке.
7.Подсчитываем коэффициент взвешенной связности:
*
09
.0
197
2
4
2
9
1
DD
Ф
08
.0
195
3
2
2
8
7
DD
Ф
23
06
.0
192
1
2
1
8
4
DD
Ф
06
.0
192
1
1
2
8
8
DD
Ф
07
.0
194
2
3
1
8
6
DD
Ф
06
.0
192
2
0
2
8
9
DD
Ф
Так как максимальный коэффициент взвешенной связности имеет
микросхема DD1. Размещаем микросхему DD1.
Коэффициент размещения:
F
5
=9х6+2х6+4х5+2х4=45
F
10
=9х3+2х3+4х2+2х1=62
F
8
=9х5+2х5+4х4+2х3 =62
F
11
=9х6+2х6+4х5+2х4=79
F
9
=9х4+2х4+4х3+2х2=45
F
12
=9х5+2х5+4х4+2х3=62
F
13
=9х4+2х4+4х3+2х2=79
Минимальный коэффициент размещения имеет ячейка 5. Следова-
тельно, микросхему DD1 размещаем в пятую ячейку.
8.Подсчитываем коэффициент взвешенной связности:
26
.0
195
36
3
2
2
8
7
DD
Ф
25
.0
192
36
1
2
1
8
4
DD
Ф
25
.0
192
36
1
1
2
8
8
DD
Ф
*
26
.0
194
36
2
3
1
8
6
DD
Ф
25
.0
192
36
2
0
2
8
9
DD
Ф
Так как максимальный коэффициент взвешенной связности имеет
микросхема DD6. Размещаем микросхему DD6.
Коэффициент размещения:
F
8
=8x4+1x3+3x4+2x2+36x1=87
F
11
=8x5+1x4+3x5+2x3+36x2=129
F
9
=8x3+1x2+3x3+2x1+36x2=117
F
12
=8x4+1x3+3x4+2x2+36x3=167
F
10
=8x4+1x3+3x4+2x2+36x3=151
F
13
=8x5+1x4+3x5+2x3+36x4=21
Минимальный коэффициент размещения имеет ячейка 8. Следова-
24
тельно, микросхему DD6 размещаем в восьмую ячейку.
9.Подсчитываем коэффициент взвешенной связности:
44
.0
192
36
36
1
2
1
8
4
DD
Ф
44
.0
192
36
36
1
1
2
8
8
DD
Ф
*
45
.0
195
36
36
3
2
2
8
7
DD
Ф
44
.0
192
36
36
2
0
2
8
9
DD
Ф
Так как максимальный коэффициент взвешенной связности имеет
микросхема DD7. Размещаем микросхему DD7.
Коэффициент размещения:
F
9
=8x3+2x2+2x3+3x1+36x2+36x1=145
F
11
=8x5+2x4+2x5+3x3+36x2+36x1=175
F
10
=8x4+2x3+2x4+3x2+36x3+36x2=232 F
12
=8x4+2x3+2x4+3x2+36x3+36x2=232
F
13
=8x5+2x4+2x5+3x3+36x4+36x3=319
Минимальный коэффициент размещения имеет ячейка 10. Следова-
тельно, микросхему DD7 размещаем в десятую ячейку.
10.Подсчитываем коэффициент взвешенной связности:
*
63
.0
192
36
36
36
1
2
1
8
4
DD
Ф
63
.0
192
36
36
36
1
1
2
8
8
DD
Ф
63
.0
192
36
36
36
2
0
2
8
9
DD
Ф
Так как максимальный коэффициент взвешенной связности имеет
микросхема DD4. Размещаем микросхему DD4.
Коэффициент размещения:
F
10
=8x4+1x3+2x4+1x2+36x3+36x2+36x1=261
F
11
=8x5+1x4+2x5+1x3+36x2+36x1+36x2=237
F
12
=8x4+1x3+2x4+1x2+36x3+36x2+36x1=261
25
F
13
=8x5+1x4+2x5+1x3+36x4+36x3+36x2=381
Минимальный коэффициент размещения имеет ячейка 11. Следова-
тельно, микросхему DD4 размещаем в одинадцатую ячейку.
11.Подсчитываем коэффициент взвешенной связности:
*
81
.0
192
36
36
36
36
1
1
2
8
8
DD
Ф
81
.0
192
36
36
36
36
2
0
2
8
9
DD
Ф
Так как максимальный коэффициент взвешенной связности имеет
микросхема DD8. Размещаем микросхему DD8.
Коэффициент размещения:
F
10
=8x4+2x3+1x4+1x2+36x3+36x2+36x1+36x3=368
F
12
=8x4+2x3+1x4+1x2+36x3+36x2+36x1+36x1=296
F
13
=8x5+2x4+1x5+1x3+36x4+36x3+36x2+36x2=452
Минимальный коэффициент размещения имеет ячейка 12. Следова-
тельно, микросхему DD8 размещаем в двенадцатую ячейку.
Размещаем последнюю микросхему DD9.
Коэффициент размещения:
F
10
= 8x4+2x3+0x4+1x2+36x3+36x2+36x1+36x3+36x2=296
F
13
= 8x5+2x4+0x5+1x3+36x4+36x3+36x2+36x2+36x1=452
Минимальный коэффициент размещения имеет ячейка 10. Следова-
тельно, микросхему DD9 размещаем в десятую ячейку.
Продолжая расчеты согласно выше приведенной методике коммута-
ционное поле платы с размещенными микросхемами имеет вид (рис. 2.4).
26
XS
2
DD1 DD6 DD4
DD5 DD3 DD7 DD8
DD2
DD9
Рисунок 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)
В формуле (2):
n количество микросхем;
17,5*7,5 мм
2
установочная площадь микросхем;
.
раз
S
площадь разъема.
2180
10
100
1
5,
7
5,
17
9
ЭЛ
S
Тогда площадь печатной платы должна быть больше
27
4762
400
1
5.
0
2180
ПП
S
Исходя из рассчитанной площади платы, размеры сторон платы выбираем
95х80 мм.
28
3 ТРАССИРОВКА ШИН «ЗЕМЛЯ» И «ПИТАНИЕ» С
ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА ПОСТРОЕНИЯ
КСС
3.1 Трассировка шины «земля» с помощью алгоритма Краскала
Проведѐм трассировку шины «земля» с помощью алгоритма Краскала.
Этот алгоритм строит кратчайшую связующую сеть (КСС), которая должна
удовлетворять трѐм условиям:
1) длина рѐбер должна быть минимальна;
2) ребро должно быть инцидентно только одной вершине;
3) максимальное подключение проводников к одному контакту
ρ
max
= 3…4.
Построение КСС осуществляется путѐм последовательного выбора
рѐбер, удовлетворяющих трѐм условиям, при этом формируется массив ин-
дексов этих ребер, упорядоченный по возрастанию, который анализируется
по трѐм условиям. Условием получения покрывающего дерева является вы-
черчивание всех номеров вершин в массиве номеров.
По координатной сетке строим матрицу длин (количество клеток от
вывода к выводу по вертикали и горизонтали) Необходимо соединить выво-
ды К1..К10
K1
K2
K3
K4
K5
K6
K7
K8
K9
K1
0
14
26
18
26
25
19
20
26
K2
0
40
32
18
39
25
33
25
K3
0
7
21
6
14
7
14
K4
0
14
7
7
6
13
K5
0
21
7
14
7
K6
0
14
13
20
K7
0
7
6
K8
0
7
K9
0
Рисунок 3.1 – Матрица длин
Составим массив рѐбер, упорядоченных по возрастанию. Для этого
можно использовать половину матрицы длин (по диагонали). Получаем мас-
сив
d
36
, d
48
, d
78
, d
34
, d
38
, d
47
, d
57
, d
59
, d
78
, d
89
, d
49
, d
68
,
d
12
, d
37
, d
39
, d
45
, d
58
, d
14
, d
25
, d
17
, и т.д.
Применяем алгоритм Краскала, анализируя массив по трѐм условиям,
29
в результате получаем:
d
36
, d
34
, d
38
, d
78
, d
79
, d
59
, d
41
, d
12
, т.е. последовательность соединения
микросхем:
DD6 – DD8 – DD7 – DD4 – DD3 – DD1 – DD5 – DD9– DD2.
Рисунок проведения шины «земля» показан в приложении. Шина
«земля» строится со стороны пайки.
3.2 Трассировка шины «питание» с помощью алгоритма Прима
К шине «питание» подключается 14-й вывод микросхем. Трассировку
шины «питание» проводим с помощью алгоритма Прима. В нѐм построение
КСС получаем путѐм присоединения не рѐбер, а ближайших изолированных
вершин. Алгоритм Прима работает с полной матрицей расстояний, которая
приведена на рис.3.2.
K1
K2
K3
K4
K5
K6
K7
K8
K9
K1
0
14
26
6
20
7
13
20
26
K2
14
0
40
14
25
21
18
33
25
K3
26
40
0
25
39
18
32
7
14
K4
6
14
25
0
14
7
7
18
19
K5
20
25
39
14
0
21
7
32
25
K6
7
21
18
7
21
0
14
19
26
K7
13
18
32
7
7
14
0
25
18
K8
20
33
7
18
32
19
25
0
7
K9
26
25
14
19
25
26
18
7
0
Рисунок 3.2 – Матрица длин
Просматриваем первую строку матрицы и выбираем элемент d
14
, яв-
ляющийся минимальным в этой строке. При наличии нескольких элементов с
одинаковыми минимальными значениями выбираем элемент с меньшим ин-
дексом. Помечаем элемент d
14
: Исключаем из рассмотрения (вычѐркиваем)
все элементы первого и четвертого столбцов (рис.3.3).
30
K2
K3
K5
K6
K7
K8
K9
K1
14
26
20
7
13
20
26
K2
0
40
25
21
18
33
25
K3
40
0
39
18
32
7
14
K4
14
25
14
7
7
18
19
K5
25
39
0
21
7
32
25
K6
21
18
21
0
14
19
26
K7
18
32
7
14
0
25
18
K8
33
7
32
19
25
0
7
K9
25
14
25
26
18
7
0
Рисунок 3.3 – Матрица расстояний
Выбираем элемент d
16
, являющийся первым минимальным в этих
строках. Исключаем из рассмотрения все элементы шестого столбца
(рис.3.4).
K2
K3
K5
K7
K8
K9
K1
14
26
20
13
20
26
K2
0
40
25
18
33
25
K3
40
0
39
32
7
14
K4
14
25
14
7
18
19
K5
25
39
0
7
32
25
K6
21
18
21
14
19
26
K7
18
32
7
0
25
18
K8
33
7
32
25
0
7
K9
25
14
25
18
7
0
Рисунок 3.4 – Матрица расстояний
Выбираем элемент d
47
, являющийся первым минимальным в этих
строках. Помечаем элемент d
47
: Исключаем из рассмотрения (вычѐркиваем)
все элементы седьмого столбца (рис.3.5).
31
K2
K3
K5
K8
K9
K1
14
26
20
20
26
K2
0
40
25
33
25
K3
40
0
39
7
14
K4
14
25
14
18
19
K5
25
39
0
32
25
K6
21
18
21
19
26
K7
18
32
7
25
18
K8
33
7
32
0
7
K9
25
14
25
7
0
Рисунок 3.5 – Матрица расстояний
d
75
, являющийся первым минимальным. Помечаем элемент d
75
: Ис-
ключаем из рассмотрения (вычѐркиваем) все элементы пятого столбца
(рис.3.6).
K2
K3
K8
K9
K1
14
26
20
26
K2
0
40
33
25
K3
40
0
7
14
K4
14
25
18
19
K5
25
39
32
25
K6
21
18
19
26
K7
18
32
25
18
K8
33
7
0
7
K9
25
14
7
0
Рисунок 3.6 – Матрица расстояний
d
12
являющийся первым минимальным. Помечаем элемент d
12
: Исклю-
чаем из рассмотрения (вычѐркиваем) все элементы второго столбца (рис.3.7).
K3
K8
K9
K1
26
20
26
K2
40
33
25
K3
0
7
14
K4
25
18
19
K5
39
32
25
K6
18
19
26
K7
32
25
18
K8
7
0
7
K9
14
7
0
Рисунок 3.7 – Матрица расстояний
32
d
63
, являющийся первым минимальным. Помечаем элемент d
63
: Ис-
ключаем из рассмотрения (вычѐркиваем) все элементы третьего столбца
(рис.3.8).
K8
K9
K1
20
26
K2
33
25
K3
7
14
K4
18
19
K5
32
25
K6
19
26
K7
25
18
K8
0
7
K9
7
0
Рисунок 3.8 – Матрица расстояний
d
38
, являющийся первым минимальным. Помечаем элемент d
38
: Ис-
ключаем из рассмотрения (вычѐркиваем) все элементы восьмого столбца
(рис.3.9).
K9
K1
26
K2
25
K3
14
K4
19
K5
25
K6
26
K7
18
K8
7
K9
0
Рисунок 3.9 – Матрица расстояний
d
89
, последняя вершина присоединяема по алгоритму Прима.
В результате применения алгоритма Прима и учитывая условия по-
строения КСС, соединяем микросхемы в следующей последовательности:
DD9 – DD7 – DD3 – DD5 – DD2 – DD8 - DD6– DD4– DD1.
Трассировка шины «питание» выполняется со стороны монтажа эле-
ментов.
33
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
ε
так, чтобы полученные соединения отвечали выбранному показателю качест-
ва.
На практике при оптимизации топологии печатного монтажа часто ис-
пользуют следующие критерии качества:
минимум суммарной длины всех соединений;
минимум числа соединений проводников;
равномерность распределения проводников на печатной плате;
минимальная протяженность параллельных участков соседних
проводников;
минимум числа изгибов проводников;
минимум числа слоев металлизации и числа переходов из слоя в
слой (применяется при проектировании многослойных печатных
плат).
Трассировку соединений осуществляют с помощью алгоритмов, осно-
ванных на методах динамического программирования. Общим для этих алго-
ритмов является разбиение монтажного поля на ячейки, размер и форма ко-
торых определяют плотность и конфигурацию печатных проводников.
34
Наибольшее распространение на практике получило разбиение рабоче-
го поля на правильные квадраты, что обеспечивает простую адресацию ячеек
в прямоугольной системе координат и привычную форму соединений.
Размеры ячеек определяются конструктивно-технологическими требо-
ваниями, предъявляемыми к печатному монтажу. Так как в каждой ячейке
обычно размещается только один вывод или печатный проводник, макси-
мальные размеры ячеек определяются допустимой точностью воспроизведе-
ния проводников. Минимальные размеры ячеек обуславливаются возможно-
стью запоминающих устройств ЭВМ и соотношением
(4.1)
где d — расстояние между центрами соседних ячеек; b
пр
— минимальная
ширина печатного проводника; l
з
— минимальное расстояние между сосед-
ними проводниками.
Соединение выводов конструктивных элементов осуществляется в ре-
зультате последовательного заполнения ячеек трассами, конфигурация кото-
рых является локально оптимальной (соединения проводятся оптимальным
образом лишь по отношению к ранее построенным проводникам) в соответ-
ствии с выбранными критериями трассировки. Необходимо заметить, что при
последовательном процессе проведения трасс, поскольку многие соединения
конкурируют между собой, число разведенных цепей и их конфигурация оп-
ределяются последовательностью трассировки отдельных соединений.
Известные алгоритмы трассировки печатных плат можно условно раз-
бить на три большие группы:
1) волновые алгоритмы, основанные на идеях Ли и разработанные Ю.
Л. Зиманом и Г. Г. Рябовым. Данные алгоритмы получили широкое
распространение в существующих АСП, поскольку они позволяют легко
учитывать технологическую специфику печатного монтажа со всей
совокупностью конструктивных ограничений. Эти алгоритмы всегда
гарантируют построение трассы, если путь для нее существует;
2) ортогональные алгоритмы, обладающие большим быстродействием,
чем алгоритмы первой группы. Реализация их на ЭВМ требует 75…100 раз
меньше вычислений по сравнению с волновыми алгоритмами. Такие
алгоритмы применяют при проектировании печатных плат со сквозными
металлизированными отверстиями. Недостатки этой группы алгоритмов
связаны с получением большого числа переходов со слоя на слой,
отсутствием 100%-ной гарантии проведения ряда трасс, большим числом
параллельно идущих проводников;
3) алгоритмы эвристического типа, получающие все более широкое
распространение. Эти алгоритмы частично основаны на эвристическом
приме поиска пути в лабиринте. При этом каждое соединение проводится по
кратчайшему пути, обходя встречающиеся на пути препятствия.
d ≥ b
пр
+l
з
,
35
4.1 Волновой алгоритм Ли
Данный алгоритм является классическим примером использования ме-
тодов динамического программирования для решения задач трассировки пе-
чатных соединений. Основные принципы построения трасс с помощью вол-
нового алгоритма сводятся к следующему.
Все ячейки монтажного поля подразделяют на занятые и свободные.
Занятыми, считают ячейки, в которых уже расположены проводники, по-
строенные на предыдущих шагах, или находятся монтажные выводы элемен-
тов, а также ячейки, соответствующее границе платы и запрещенным для
прокладывания проводников участкам. Каждый раз при проведении новой
трассы можно использовать лишь свободные ячейки, число которых по мере
проведения трасс сокращается.
На множестве свободных ячеек коммутационного поля моделируют
волну влияния из одной ячейки в другую, соединяемых впоследствии общим
проводником. Первую ячейку, в которой зарождается волна влияний, назы-
вают источником, а вторую — приемником волны. Чтобы иметь возмож-
ность следить за происхождением фронта влияний, его фрагментам на каж-
дом этапе присваивают некоторые веса:
(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
монотонно убывали. В результате получают
путь, соединяющий эти две точки. Из описания алгоритма следует, что все
условия, необходимые для проведения пути, закладываются в правила при-
писания веса ячейкам.
Чтобы исключить неопределенность при проведении пути для случая,
когда несколько ячеек имеют одинаковый минимальный вес, вводят понятие
путевых координат, задающих предпочтительность проведения трассы. Каж-
P
k
= P
k-1
+ ψ (f
1
, f
2
, … , f
g
)*,
36
дое направление кодируют двоичным числом по mod q, где q – число про-
сматриваемых соседних ячеек. При этом чем более предпочтительно то или
иное направление, тем меньший числовой код оно имеет. Например, если за-
даться приоритетным порядком проведения пути сверху, справа, снизу и сле-
ва, то коды соответствующих путевых координат будут 00, 01, 10 и 11. При-
писание путевых координат производят на этапе распространения волны.
При проведении пути движение от ячейки к ячейке осуществляют по путе-
вым координатам. На рисунке 4.1 приведен пример проведения дорожки от
четвертого вывода микросхемы DD9 к одиннадцатому выводу микросхемы
DD7.
Рисунок 4.1 Волновой алгоритм Ли.
На рисунке 4.2 приведен пример проведения дорожки от третьего вы-
вода микросхемы DD9 ко второму выводу микросхемы DD3.
37
Рисунок 4.2 Волновой алгоритм Ли.
38
ЗАКЛЮЧЕНИЕ
В результате работы были получены следующие результаты:
- с помощью последовательного алгоритма компоновки элементы элек-
трической функциональной схемы были разбиты по корпусам микросхем и
на основе проделанных расчетов разработана схема электрическая принци-
пиальная;
- с помощью алгоритма размещения корпуса микросхем были оптималь-
но распределены по посадочным местам на монтажном поле платы относи-
тельно разъема, а также на основе расчетов был разработан сборочный чер-
теж;
-по методам трассировки оптимально, с точки зрения длины проводни-
ков, была проведена трассировка шины питания (по алгоритму Прима), ши-
ны земли (по алгоритму Краскала) и сигнальных цепей (по волновому алго-
ритму). На основе поведенной трассировки был разработан чертеж печатной
платы.
39
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Деньдобренко, Б. Н. Автоматизация конструирования РЭА: Учебник
для вузов / Б. Н. Деньдобренко, А. С. Малика. – М.: Высш. шк., 1980.
2. Корячко, В. П. Теоретические основы САПР: Учебник для вузов /
В.П. Корячко, В.М. Курейчик, И.П. Норенков – М.: Энергоатомиздат, 1987.
3. Методические указания к лабораторным работам по курсу «Автома-
тизация конструкторского и технологического проектирования РЭС» для
студентов специальности 1-39 02 01/ А. И. Толстая, и др.;– Минск: БГУИР,
2008.
4. ГОСТ 2.701-84 ЕСКД. Схемы. Виды и типы. Общие требования к
выполнению.
5. ГОСТ 2.710-81 ЕСКД. Обозначения буквенно-цифровые в электриче-
ских схемах.
40
ПРИЛОЖЕНИЕ
Информация о работе АКИТ