Рисунок. 3.15 - Нумерація виводів мікросхем

Рисунок. 3.16 - Орієнтація мікросхем на платі

Аналогічно проводиться розміщення в вузлах Т1, Т2, Т3.

Рисунок. 3.17 - Координатна сітка для вузлів Т1, Т2

Рисунок. 3.18 - Розміщення елементів в узлі Т1

Рисунок. 3.19 - Розміщення елементів в узлі Т2

В узлі Т3 тільки 1 елемент, тому його розміщення не розглядається.

4 ТРАСУВАННЯ СПОЛУЧЕНЬ

4.1 Алгоритм Лі

Для сполучення виводів мікросхем в відповідності з електричною принциповою схемою необхідно використати заданий алгоритм трасування. В процесі трасування слід виконати наступні основні етапи:

1) отримання списку сполучень (табл. 4.1),

2) визначення порядку прокладки сполучень,

3) трасування окремих сполучень.

Використовуючи один з заданих алгоритмів здійснюється попереднє трасування на одній площині. В процесі трасування необхідно мінімізувати геометричні параметри сполучень: довжину, число пересічень, кількість згибів.

Проводиться трасування вузла Т1.

Таблиця 4.1- Список сполучень вузла Т1

Провідник	Сполучення	Елементний комплекс	Примітка
1	D5: 24,D6: 24, D4: 14	Іспити
2	D5: 12,D6: 12, D4: 7	"Земля"
3	D5: 1, Ш:a1	V1
4	D5: 4, Ш:a6	V6
5	D5: 2, D1:5, D2:1	V7
6	D5: 3, D2:2	V8
7	D5: 5,D5:7 ,Ш:a22	V9
8	D5:10, D5:8, Ш:a7	V10
9	D5:15,D5:16, Ш:a8	V11
10	D5:18, D4:1, Ш:a23	V13
11	D4:4, Ш:a9	V14
12	D6:2,D6:3, Ш:a10	V15
13	D6:5,D6:7, Ш:a24	V16
14	D6:8,D6:9, Ш:a11	V17
15	D6:11,D6:17, Ш:a25	V18
16	D6:15,D6:16, Ш:a12	V19
17	D6:18, Ш:a26	V20
18	D6:19, Ш:a27	V21
19	D5:11,D5:17,D4:2,D4:3,D6:14	V22
20	D6:1,D4:5	V23
21	D6:4,D4:6	V24

Суттєвість хвильового алгоритму Лі полягає в наступному:

1. Плата розбивається на прямокутні осередки, в результаті чого утвориться дискретне робоче поле (ДРП).

2. Задається деяка функція F, що є критерієм якості шляху. В якості вагової функції F необхідно брати відстань від осередка А до розглядуваного осередка.

3. Осередку А ставимо в відповідність вагу 0, сусіднім з ній осередкам вага 1 і т. д. При цьому виникає числова хвиля, що буде розповсюджуватися від осередка А до осередка В, і як тільки фронт хвилі досягне осередка В, розповсюдження хвилі закінчується.

4. При русі від осередка В до осередка А по пройденим осередкам так, щоб числа зменшувалися монотонно, одержуємо трасу, що з'єднує осередки А і В.

Процес розповсюдження числової хвилі і проведення траси повторюється для всіх сполучень з табл. 4.1. Приклад проведення траси D6: 04 і D4: 06 показаний на рис. 4.1.

O	1	13	O
O	2	D5	14	O
O	3	15	O	16
O	4	15	O	16	15	16
O	5	17	O	16	15	14	15	16
O	6	18	O	15	14	13	14	15	16
O	7	19	O	14	13	12	13	14	15	16
O	8	20	O	13	12	11	12	13	14	15	16
O	9	21	O	12	11	10	11	12	13	14	15	16
O	10	22	O	11	10	9	10	11	12	13	14	15	16
16	O	11	23	O	10	9	8	9	10	11	12	13	14	15	16
16	15	O	12	24	O	9	8	7	8	9	10	11	12	13	14	15	16
16	15	14	13	12	11	10	9	8	7	6	7	8	9	10	11	12	13	14	15
16	15	14	13	12	11	10	9	8	7	6	5	6	7	8	9	10	11	12	13	14
15	14	13	12	11	10	9	8	7	6	5	4	O	1	13	O	12	13	14	15
14	13	12	11	10	9	8	7	6	5	4	3	O	2	D6	14	O	13	14	15	16
15	14	13	12	O	1	8	O	4	3	2	O	3	15	O	14	15	16
16	15	14	13	O	2	D4	9	O	3	2	1	O	4	15	O	15	16
16	15	14	O	3	10	O	4	3	2	O	5	17	O	16
16	15	O	4	11	O	5	4	3	O	6	18	O
16	O	5	12	O	6	5	4	O	7	19	O
17	O	6	13	O	7	6	5	O	8	20	O
16	O	7	14	O	8	7	6	O	9	21	O
16	15	14	13	12	11	10	9	8	7	O	10	22	O
16	15	14	13	12	11	10	9	8	O	11	23	O
16	15	14	13	12	11	10	9	O	12	24	O
16	15	14	13	12	11	10	11	12	13	14	15	16
16	15	14	13	12	11	12	13	14	15	16

Рисунок. 4.1 - Проведення траси D6: 04 і D4: 06

4.2 Алгоритм Хейса

Метод Хейса здійснює пошук найкоротшого шляху в багатошаровому ДРП між двома заданими осередками A і B. Для кожного шару i вводиться своє ДРПi. Однойменні осередки (вільні) можуть бути зв'язані переходами. Осередки можуть бути або зайнятими, або вільними. Кожному вільному осередку ставиться у відповідність індекс довжини Pi і індекс кількості переходів, причому при переході з шару в шар індекс довжини збільшується на 1. Індекс застосовується для зменшення числа переходів.

В процесі розповсюдження хвилі для кожного шару використовуються наступні масиви: ДРПi - стан осередків i-го шару; Li - поточного фронту хвилі в i-м шарі; Mi - осередки шару i сусідні до осередків з Li. При утворенні чергового фронту для i-го шару разом з осередками з Mi використовуються ті вільні осередки i-го шару, в яких можливий перехід з інших шарів і які мають той же індекс P.

Недолік методу: хвиля розповсюджується послідовно в кожному з шарів і незалежно, це приводить до великих витрат машинного часу.