61

ПОЯСНЮВАЛЬНА ЗАПИСКА

до курсової роботи за курсом

«АВТОМАТИЗАЦІЯ ПРОЕКТУВАННЯ КОМП'ЮТЕРНИХ СИСТЕМ»

на тему «Проектування друкованих плат пристроїв комп'ютерних систем»

РЕФЕРАТ

Пояснювальна записка до курсової роботи:

59 стор., 48 рис., 3 табл.

Метою курсової роботи є:

· Оволодіння навиками формування опису логічного елементу в середовищі системи проектування PCAD. Структура формованого опису повинна відповідати стандартній структурі опису логічного елементу, прийнятого в системі проектування PCAD.

· Вивчення принципів і оволодіння навиками проектування принципових електричних схем в редакторі PCAD Schematic. У цьому редакторі здійснюється розміщення умовного графічного позначення (УГП) елементів на робочому полі редактора, проведення електричних споучень між елементами, привласнення елементам позиційних позначень, формування шин і т.п.

· Оволодіння навиками трасування печатних сполучень в САПР PCAD.

• Зміст
• ВСТУП
• 1 ПОБУДОВА КОММУТАЦІЙНОЇ СХЕМИ. ПОДАННЯ КОММУТАЦІЙНОЇ СХЕМИ У ВИГЛЯДІ ГРАФІВ І МАТРИЦЬ
• 2 КОМПОНОВКА ЕЛЕМЕНТІВ СХЕМИ В ВУЗЛИ
• 2.1 Послідовний алгоритм компоновки
• 2.2 Мінімізація числа міжвузлових сполучень.
• 3 РОЗМІЩЕННЯ ЕЛЕМЕНТІВ НА ПЛАТІ
• 3.1 Послідовний алгоритм розміщення
• 3.2 Ітераційний алгоритм розміщення елементів на платі
• 4 ТРАСУВАННЯ СПОЛУЧЕНЬ
• 4.1 Алгоритм Лі
• 4.2 Алгоритм Хейса
• 5 РОЗПОДІЛ СПОЛУЧЕНЬ ПО ШАРАХ
• 6 РОЗРОБКА БІБЛІОТЕКИ ЕЛЕМЕНТІВ В САПР PCAD
• 6.1 Створення символу компоненту в PCAD Schematic
• 6.2 Створення корпусу компонентів в PCAD PCB
• 6.3 Створення компоненту за допомогою Library Executive
• 7 РОЗРОБКА СЕМИ ЕЛЕКТРИЧНОЇ ПРИНЦИПОВОЇ В САПР PCAD
• 7.1 Завантаження бібліотек
• 7.2 Розміщення компонентів на схемі
• 7.3 Розміщення електричних ланцюгів
• 7.4 Розміщення шин
• 7.5 Створення списку з'єднань
• 8 РОЗМІЩЕННЯ ЕЛЕМЕНТІВ НА ПЛАТІ В САПР PCAD
• 8.1 Упаковка схеми на друкарську плату
• 8.2 Розміщення компонентів на платі
• 9 ТРАСУВАННЯ ПЕЧАТНИХ СПОЛУЧЕНЬ ПЕЧАТНОЇ ПЛАТИ В САПР PCAD
• 9.1 Установка кроку сітки
• 9.2 Установка зазорів між провідниками
• 9.3 Автотрасувальник Quick Route
• 9.4 Обмеження для QuickRoute:
• 10 ТЕХНОЛОГІЧНИЙ КОНТРОЛЬ ПЕЧАТНОЇ ПЛАТИ.
• ВИСНОВОК
• ЛІТЕРАТУРА

ВСТУП

Курсова робота орієнтована на синтез та дослідження проектування друкованих плат, застосування алгоритмів розміщення елементів (послідовний алгоритм та оптимізація) на друкованій платі, компоновки (послідовний алгоритм та метод парних перестановок для оптимізації), трасування сполучень (алгоритми Лі та Хейса), розподілу по шарах.

Також в курсовій роботі передбачається використання спецілаізованого програмного забезпечення - системи автоматизації проектування PCAD, а саме оволодіння навиками формування опису логічного елементу в середовищі системи проектування PCAD, вивчення принципів і оволодіння навиками проектування принципових електричних схем в редакторі PCAD Schematic, оволодіння навиками трасування печатних сполучень в САПР PCAD.

1 ПОБУДОВА КОММУТАЦІЙНОЇ СХЕМИ. ПОДАННЯ КОММУТАЦІЙНОЇ СХЕМИ У ВИГЛЯДІ ГРАФІВ І МАТРИЦЬ

Елементами комутаційної схеми є автономні конструктивні одиниці - мікросхеми. Для переходу від принципової схеми до комутаційної необхідно на принциповій схемі виділити групи елементів, що складають окремі мікросхеми і замінити їх одним елементом комутаційної схеми.

Перехід від електричної принципової схеми до комутаційної схеми виконується в наступній послідовності:

Всі елементи схеми зображуються в вигляді умовних графічних позначок, у вигляді прямокутника, всередині якого записаний порядковий номер елементу (мікросхеми). При цьому різноманітні логічні елементи, розташовані в одному корпусі мікросхеми. Контакти роз'єму, т. т. Всі вхідні і вихідні сигнали, вважаються контактами фіктивного елементу D0.

На рис. 1.3. наведена комутаційна схема, відповідна принциповій схемі, зображеній на рис. 1.2. Всі електричні ланцюги комутаційної схеми послідовно нумеруються: V1, V2,...V38.

Кожний електричний ланцюг (безліч еквіпотенційних виводів елементів називається комплексом. Існує також поняття елементного комплексу. Елементний комплекс - це безліч елементів комутаційної схеми, об'єднаних одним електричним ланцюгом. Всі елементні комплекси на комутаційній схемі необхідно пронумерувати послідовним рядом чисел, починаючи з одиниці. Номера елементних комплексів доцільно проставляти у контактів всіх елементів, об'єднаних одним елементним комплексом.

Граф елементних комплексів (ГЕК) складається з: вершин, відповідних елементам (тип D); вершин, відповідних елементним комплексам (тип V); ребер, відповідних електричним сполученням.



Рисунок. 1.1 - Прилад



Рисунок. 1.2 - Мікросхеми



Рисунок. 1.3 - Комутаційна схема

ГЕК можна описати за допомогою матриці елементних комплексів Q

(рис. 1.4):

Q = ||q|| _{m n} ,

де m - кількість елементів D; n - кількість ланцюгів.

Рисунок. 1.4 - Матриця елементних комплексів (продовження)

	V1	V2	V3	V4	V5	V6	V7	V8	V9	V10	V11	V13	V14	V15	V16	V17	V18	V19
D0	1	1	1	1	1			1	1	1	1	1	1	1	1	1	1	1
D1		1	1	1	1	1
D2						1	1
D3
D4												1	1
D5	1					1	1	1	1	1	1	1
D6														1	1	1	1	1
D7

V20	V21	V22	V23	V24	V25	V26	V27	V28	V29	V30	V31	V32	V33	V34	V35	V36	V37	V38
1	1				1	1	1	1				1	1	1	1	1	1	1
										1	1
					1	1	1	1	1	1
		1	1	1
		1
1	1	1	1	1
									1	1	1	1	1	1	1	1	1	1

На рис. 1.5 наведений зважений граф схеми (ЗГС). Він складається з: вершин, відповідних елементам D₀, D₁,... …, D₉, і ребер, що з'єднають ці вершини. Ребро, що з'єднує вершини графа D_i і D_j з приписаною йому вагою, показує наявність і кількість зв'язків між елементами схеми E_i і E_j.



Рисунок. 1.5 - - Зважений граф схеми

ЗГС можна уявити в вигляді матриці сполучень R (рис 1.6):

R=¦¦ r ¦¦ _{m m}, r_ij - число зв'язків D_i і D_j.

Матриця R симетрична відносно головної діагоналі. Крім Того rii=0, i=0, …, m-1.

	0	1	2	3	4	5	6	7
0	0	4	0	4	2	7	7	7
1	4	0	1	0	0	2	0	0
2	0	1	0	1	0	2	0	2
3	4	0	1	0	0	0	0	2
4	2	0	0	0	0	2	3	0
5	7	2	2	0	2	0	1	0
6	7	0	0	0	3	1	0	0
7	7	0	2	2	0	0	0	0

Рис. 1.6 - Матриця сполучень

2 КОМПОНОВКА ЕЛЕМЕНТІВ СХЕМИ В ВУЗЛИ

2.1 Послідовний алгоритм компоновки

Компоновка елементів може здійснюватися різноманітними методами. В курсовій роботі застосований послідовний алгоритм компоновки.

Сутність задачі полягає в розподілі комутаційної схеми на частини (вузли) з наступними обмеженнями: кількість елементів (КЕ) вузла не повинна перевищувати 6, кількість зовнішніх виводів (В) вузла повинно бути менш або рівно 17. В алгоритмі закладений принцип мінімізації зовнішніх виводів вузла при максимізації внутрішньо вузлових зв'язків.

Послідовність рішення.

Перед початком компоновки безліч нерозподілених елементів включає D0 (фіктивний елемент, що об'єднує всі зовнішні виводи схеми), D1, D2, D3, D4, D5, D6, D7.

Фіктивний елемент D0 назначаємо в фіктивний вузол T0 (r=0). Після цієї безлічі нерозподілених елементів Ir= (D1, D2, D3, D4, D5, D6, D7).

Починаємо компоновку вузла Т1 (r=1) (табл. 2.1):

А) для кожного з нерозподілених елементів (безліч Ir при r=1) обчислюємо функціонал L1 - кількість електричних ланцюгів (комплексів), якими даний елемент Xr зв'язаний з безліччю ще нерозподілених.

де

Ir - безліч нерозподілених елементів.

В якості базового елементу вузла Tr (при r=1) вибираємо перший по порядку елемент з максимальним значенням L1. Це D2. Елемент D2 виключаємо з безлічі нерозподілених елементів Ir (r=1).

Б) для кожного з нерозподілених елементів розраховуємо значення функціонала L2, що показує число зовнішніх зв'язків вузла (отриманого доданням до вже розподіленого елементу D2 чергового кандидата) з безліччю інших елементів схеми, включаючи D0.

Кількість зовнішніх висновків вузла рівно числу ланцюгів, що зв'язують елементи вузла з елементами, що не входять до вузла. Ті елементи, для яких здійсненна умова L2 В, (де В=17), виключаються на даному кроку з числа кандидатів в вузол, що формується; ці елементи позначені зірочкою.

де - вузол з елементами;

Ts - вузли ,що сформувалися;

.

Для кандидатів ,що залишилися розраховуємо функціонал L3. Функціонал L3 - це число ланцюгів, що з'єднують розглядуваний елемент-кандидат з безліччю елементів даного вузла. Для призначення в вузол вибираємо той елемент, що має максимальне значення L3. Якщо таких елементів декілька, то слід вибирати перший по порядку, що має найменшу величину L2. На даному кроку це D5.

Елемент D5 виключаємо з безлічі нерозподілених. Отже, в перший вузол тепер розподілені елементи D2 і D5. Формування вузла буде завершене, коли число елементів в ньому досягне даного (КЕ=5), або не знайдеться жодного кандидата, додавання якого не порушить умови L2 В (B=17).

В) Для елементів ,що залишилися нерозподіленими, розраховуємо функціонали - L2, L3. По вище наведеним правилам визначаємо черговий елемент вузла D4.

Г) В результаті аналогічних розрахунків визначаємо наступний елемент вузла Т1-D1. На цьому компоновка першого вузла завершена, тому що додавання наступного кандидату порушить умову L2 В (B=17).

Виконуємо компоновку вузла Т2 (табл. 2.1, r=2.). Закінчення формування

цього вузла відбувається по досягненню заданого числа елементів в вузлі

(КЕ=5) та виконання умови L2 В (B=17). Це елементи: D3, D7.

Д) Елемент D6, що залишився, розміщуємо в вузол Т3 Всі

елементи розподілені.

Результатами компоновки є схеми внутрішньовузлових сполучень вузлів Т1, Т2, Т3.

Таблиця 2.1 - Таблиця компоновки елементів схеми

r	Dr1	L1	Gr1	Dr2	L2	L3	Gr2	Dr3	L2	L3	Gr3	Dr4	L2	L3	Gr4	Dr5	L2	L3
1	D1	1	D2	D1	8	1	D2	D1	14	1	D2	D1	17	1	D1	D3	22	-
	D2	4		D3	9	1	D5	D3	16	1	D4	D3	19	-	D2	D6	21	-
	D3	2		D4	9	-		D4	14	2	D5	D6	18	-	D4	D7	24	-
	D4	4		D5	11	2		D6	20	-		D7	21	-	D5
	D5	4		D6	14	-		D7	17	2
	D6	3		D7	11	2
	D7	3
2	D3	2	D3	D6	16	0	D3	D6	23	-
	D6	0		D7	13	2	D7
	D7	2
3	D6

2.2 Мінімізація числа міжвузлових сполучень

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

Розглянемо ітераційний алгоритм компоновки. Необхідно виконати компоновку елементів схеми в вузли (кількість елементів N=7) з урахуванням заданих обмежень (кількість елементів в вузлі не повинно перевищувати заданого значення КЕ). Можна вважати, що в кожному вузлі міститься максимальна кількість елементів (КЕ=6 для розглядуваного прикладу). В випадку, коли в якому-або вузлі число елементів К менш КЕ, необхідно додатково ввести Ng=KE-K фіктивних елементів, не зв'язаних з іншими елементами схеми.

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

Приріст числа міжвузлових сполучень при обміні місцями елементів буде рівно [1]:

L (x, y)=Ex+Ey - 2rxy,

де rxy - елемент матриці R;

Ex=Lx - Fx, Ey=Ly - Fy;

Lx (Ly) і Fx (Fy) відповідно зовнішні і внутрішні сполучення елементів Dx, Dy.

При розрахунку зовнішніх сполучень необхідно враховувати сполучення тільки між розглядуваними вузлами Т1, Т2. Зовнішні зв'язки з D0 можна не враховувати.



Рисунок. 2.1 - Мінімізація міжвузлових сполучень (крок 1)

d(4,6)=1+4-2*3=-1(покращень немає)

d(6,1)=4-2-2*0=2

d(6,2)=4-3-2*0=1

d(6,4)=4+1-2*3=-1 (покращень немає)

d(6,5)=4-5-2*1=-3 (покращень немає)

Елементи 6 та 1 міняємо місцями

Рисунок. 2.2- Мінімізація міжвузлових сполучень (крок 2)

d(2,3)=1-1-2*0=0 (покращень немає)

d(2,7)=1-0-2*2=-3 (покращень немає)

d(1,6)=3-4-2*0=-1 (покращень немає)

d(1,2)=3-1-2*1=0 (покращень немає)

d(1,4)=3-5-2*0=-2 (покращень немає)

d(1,5)=3-3-2*2=-4 (покращень немає)

Введемо фіктивний елемент 8 у вузол Т2



Рисунок. 2.3 - Мінімізація міжвузлових сполучень (крок 3)

d(2,8)=1-0-2*0=1

Елементи 2 та 8 міняємо місцями

Рисунок. 2.4 - Остаточний варіант компоновки

Більше покращень немпє.



Рисунок. 2.5 - Комутаційна схема внутрішньовузлових сполучень вузла Т1

Рисунок. 2.6 - Комутаційна схема внутрішньовузлових сполучень вузла Т2

Рисунок. 2.7 - Комутаційна схема внутрішньовузлових сполучень вузла Т3

Рисунок. 2.8 - Схема міжвузлових сполучень

3 РОЗМІЩЕННЯ ЕЛЕМЕНТІВ НА ПЛАТІ

3.1 Послідовний алгоритм розміщення

Мета етапу - оптимальне розміщення елементів на платі, використовуючи послідовний алгоритм.

Критеріями оптимальності є: сумарна довжина сполучень на платі, число пересічень сполучень, число шарів комутації. Для рішення задачі розміщення застосований послідовний алгоритм .

Суттєвість задачі розміщення полягає в наступному. Необхідно вибрати набір позицій для розміщення елементів. Позиції (посадочні місця) типового елементу заміни розмістити в вузлах координатної сітки, як, наприклад, показано на рис. 3.1. Крок сітки, що вимірюється в умовних одиницях, рівний 1. Нумерація позицій в загальному випадку може бути довільною, однак нумерацію потрібно виробляти так, щоб відстань між n_i і n_i+1 була мінімальною. Перший стовпчик сітки відводиться для роз'єму.

Вхідними даними для рішення задачі розміщення є матриця сполучень R (рис. 1.6) і матриця відстаней Р=¦¦ р_ij ¦¦_nn, в який елемент р_ij дорівнює відстані між центрами позицій n_i і n_j. Матриця Р - симетрична, з нульовою головною діагоналлю (р_ii=0, i=1, 2,..., n).

Рисунок. 3.1 - Координатна сітка

Для набору позицій, показаного на рис. 3.1 матриця Р має вигляд:

	0	1	2	3	4	5	6	7
0	0	1	1	1	1	2	2	2
1		0	1	2	3	4	3	2
2			0	1	2	3	2	1
3				0	1	2	1	2
4					0	1	2	1
5						0	1	2
6							0	1
7								0

Рисунок. 3.2 - - Матриця відстаней

Cутність послідовного алгоритму розміщення полягає в наступному:

Згідно з ТЗ:

Вибір першого елементу по максимальній кількості зв'язків з роз'ємом (з елементом D0).

Вибір наступного елементу по максимальній кількості зв'язків з елементами, розміщеними на попередніх кроках.

Для даного варіанту алгоритм розміщення виконується наступним чином. Елемент D0 вважається розміщеним. Тому викреслюється нульовий стовпчик матриці R (рис. 1.6), а з нульового рядка вибирається максимальний елемент і в позицію n₁ розміщується елемент D5, бо він має найбільше число зв'язків(r₀₅ =7) з елементом D0, тобто з роз'ємом. Якщо в даному рядку матриці є декілька елементів з максимальною вагою, то вибирається будь-який.

Рисунок. 3.3 - Розміщення (крок 1)

Кількість зв'язків з елементами, розміщеними на попередніх кроках

R(1,0,5)=4+2=6

R(2,0,5)=0+2=2

R(3,0,5)=4+0=4

R(4,0,5)=2+2=4

R(6,0,5)=7+1=8

R(7,0,5)=7+0=7

Обираємо макс. Кількість зв'язків - D6

Обираємо позицію

L(D6)(N2)=R(6,5)*d(N1,N2)+R(6,0)*d(N0,N2)=1*1+7*1=8

L(D6)(N3)=R(6,5)*d(N1,N3)+R(6,0)*d(N0,N3)=1*2+7*1=9

L(D6)(N4)=R(6,5)*d(N1,N4)+R(6,0)*d(N0,N4)=1*3+7*1=10

L(D6)(N5)=R(6,5)*d(N1,N5)+R(6,0)*d(N0,N5)=1*4+7*2=18

L(D6)(N6)=R(6,5)*d(N1,N6)+R(6,0)*d(N0,N6)=1*3+7*2=17

L(D6)(N7)=R(6,5)*d(N1,N7)+R(6,0)*d(N0,N7)=1*2+7*2=16

Обираємо мін. довжину - N2

Рисунок. 3.4 - Розміщення (крок 2)

Кількість зв'язків з елементами, розміщеними на попередніх кроках

R(1,0,5,6)=4+2+0=6

R(2,0,5,6)=0+2+0=2

R(3,0,5,6)=4+0+0=4

R(4,0,5,6)=2+2+3=7

R(7,0,5,6)=7+0+0=7

Обираємо макс. Кількість зв'язків - D4

Обираємо позицію

L(D4)(N3)=R(4,5)*d(N1,N3)+R(4,0)*d(N0,N3)+R(4,6)*d(N2,N3)=2*2+2*1+3*1=9

L(D4)(N4)=R(4,5)*d(N1,N4)+R(4,0)*d(N0,N4)+R(4,6)*d(N2,N4)=2*3+2*1+3*2=14

L(D4)(N5)=R(4,5)*d(N1,N5)+R(4,0)*d(N0,N5)+R(4,6)*d(N2,N5)=2*4+2*2+3*3=21

L(D4)(N6)=R(4,5)*d(N1,N6)+R(4,0)*d(N0,N6)+R(4,6)*d(N2,N6)=2*3+2*2+3*2=16

L(D4)(N7)=R(4,5)*d(N1,N7)+R(4,0)*d(N0,N7)+R(4,6)*d(N2,N7)=2*2+2*2+3*1=11

Обираємо мін. довжину - N3

Рисунок. 3.5 - Розміщення (крок 3)

Кількість зв'язків з елементами, розміщеними на попередніх кроках

R(1,0,5,6,4)=4+2+0+0=6

R(2,0,5,6,4)=0+2+0+0=2

R(3,0,5,6,4)=4+0+0+0=4

R(7,0,5,6,4)=7+0+0+0=7

Обираємо макс. Кількість зв'язків - D7

Обираємо позицію

L(D7)(N4)=R(7,5)*d(N1,N4)+R(7,0)*d(N0,N4)+R(7,6)*d(N2,N4)+R(7,4)*d(N3,N4)=0+7*1+0+0=7

L(D7)(N5)=R(7,5)*d(N1,N5)+R(7,0)*d(N0,N5)+R(7,6)*d(N2,N5)+R(7,4)*d(N3,N5)=0+7*2+0+0=14

L(D7)(N6)=R(7,5)*d(N1,N6)+R(7,0)*d(N0,N6)+R(7,6)*d(N2,N6)+R(7,4)*d(N3,N6)=0+7*2+0+0=14

L(D7)(N7)=R(7,5)*d(N1,N7)+R(7,0)*d(N0,N7)+R(7,6)*d(N2,N7)+R(7,4)*d(N3,N7)=0+7*2+0+0=14

Обираємо мін. довжину - N4

Рисунок. 3.6 - Розміщення (крок 4)

Кількість зв'язків з елементами, розміщеними на попередніх кроках

R(1,0,5,6,4,7)=4+2+0+0+0=6

R(2,0,5,6,4,7)=0+2+0+0+2=4

R(3,0,5,6,4,7)=4+0+0+0+2=6

Обираємо макс. Кількість зв'язків - D1

Обираємо позицію

L(D1)(N5)=R(1,5)*d(N1,N5)+R(1,0)*d(N0,N5)+R(1,6)*d(N2,N5)+R(1,4)*d(N3,N5)+R(1,7)*d(N4,N5)=2*4+4*2+0+0+0=16

L(D1)(N6)=R(1,5)*d(N1,N6)+R(1,0)*d(N0,N6)+R(1,6)*d(N2,N6)+R(1,4)*d(N3,N6)+R(1,7)*d(N4,N6)=2*3+4*2+0+0+0=14

L(D1)(N7)=R(1,5)*d(N1,N7)+R(1,0)*d(N0,N7)+R(1,6)*d(N2,N7)+R(1,4)*d(N3,N7)+R(1,7)*d(N4,N7)=2*2+4*2+0+0+0=12

Обираємо мін. довжину - N7

Рисунок. 3.7 - Розміщення (крок 5)

Кількість зв'язків з елементами, розміщеними на попередніх кроках

R(2,0,5,6,4,7,1)=0+2+0+0+2+1=5

R(3,0,5,6,4,7,1)=4+0+0+0+2+0=6

Обираємо макс. Кількість зв'язків - D3

Обираємо позицію

L(D3)(N5)=R(3,5)*d(N1,N5)+R(3,0)*d(N0,N5)+R(3,6)*d(N2,N5)+R(3,4)*d(N3,N5)+R(3,7)*d(N4,N5)+R(3,1)*d(N7,N5)=0+4*2+0+0+2*1+0=10

L(D3)(N6)=R(3,5)*d(N1,N6)+R(3,0)*d(N0,N6)+R(3,6)*d(N2,N6)+R(3,4)*d(N3,N6)+R(3,7)*d(N4,N6)+R(3,1)*d(N7,N6)=0+4*2+0+0+2*2+0=12

Обираємо мін. довжину - N5



Рисунок. 3.8 - Розміщення (крок 6)

Рисунок. 3.9 - Розміщення (крок 7)

3.2 Ітераційний алгоритм розміщення елементів на платі

Згідно з ТЗ - метод парних перестановок.

Обираються 2 елементи e(i) та e(j) з позиціями t(e(i)) та t(e(j)) відповідно. Знаходиться множина елементів Р:

Р=(Ге(i) V Гe(j))\e(i)e(j)

Далі перевіряється значення

Якщо значення більша за 0, елементи можна поміняти місцями.

Эл.	1	2	3	4	5	6	7
Поз.	7	6	5	3	1	2	4

Рисунок. 3.10 - Ітераційне розміщення (початок)

P(1,2)=D3, D5, D7 =====> delta=1
P(1,3)=D2, D5, D7 =====> delta=-4
P(1,4)=D2, D5, D6 =====> delta=0
P(1,5)=D2, D4, D6 =====> delta=2
P(1,6)=D2, D4, D5 =====> delta=-3
P(1,7)=D2, D3, D5 =====> delta=-3
P(2,3)=D1, D5, D7 =====> delta=-3
P(2,4)=D1, D3, D5, D6, D7 =====> delta=-3
P(2,5)=D1, D3, D4, D6, D7 =====> delta=-3
P(2,6)=D1, D3, D4, D5, D7 =====> delta=0
P(2,7)=D1, D3, D5 =====> delta=0
P(3,4)=D2, D5, D6, D7 =====> delta=-10
P(3,5)=D1, D2, D4, D6, D7 =====> delta=-4
P(3,6)=D2, D4, D5, D7 =====> delta=-9
P(3,7)=D2 =====> delta=1
P(4,5)=D1, D2, D6 =====> delta=4
P(4,6)=D5 =====> delta=1
P(4,7)=D2, D3, D5, D6 =====> delta=-5
P(5,6)=D1, D2, D4 =====> delta=3
P(5,7)=D1, D2, D3, D4, D6 =====> delta=-3
P(6,7)=D2, D3, D4, D5 =====> delta=-6

Міняємо елементи 4 та 5

Эл.	1	2	3	4	5	6	7
Поз.	7	6	5	1	3	2	4

Рисунок. 3.11 - Ітераційне розміщення (крок 1)

P(1,2)=D3, D5, D7 =====> delta=1
P(1,3)=D2, D5, D7 =====> delta=0
P(1,4)=D2, D5, D6 =====> delta=-2
P(1,5)=D2, D4, D6 =====> delta=0
P(1,6)=D2, D4, D5 =====> delta=-3
P(1,7)=D2, D3, D5 =====> delta=1
P(2,3)=D1, D5, D7 =====> delta=-3
P(2,4)=D1, D3, D5, D6, D7 =====> delta=-9
P(2,5)=D1, D3, D4, D6, D7 =====> delta=-1
P(2,6)=D1, D3, D4, D5, D7 =====> delta=-8
P(2,7)=D1, D3, D5 =====> delta=0
P(3,4)=D2, D5, D6, D7 =====> delta=-12
P(3,5)=D1, D2, D4, D6, D7 =====> delta=-6
P(3,6)=D2, D4, D5, D7 =====> delta=-13
P(3,7)=D2 =====> delta=1
P(4,5)=D1, D2, D6 =====> delta=-4
P(4,6)=D5 =====> delta=1
P(4,7)=D2, D3, D5, D6 =====> delta=-9
P(5,6)=D1, D2, D4 =====> delta=-1
P(5,7)=D1, D2, D3, D4, D6 =====> delta=-3
P(6,7)=D2, D3, D4, D5 =====> delta=-10

Міняємо місцями елементи 1 та 2

Эл.	1	2	3	4	5	6	7
Поз.	6	7	5	1	3	2	4

Рисунок. 3.12 - Ітераційне розміщення (крок 2)

P(1,2)=D3, D5, D7 =====> delta=-1
P(1,3)=D2, D5, D7 =====> delta=-4
P(1,4)=D2, D5, D6 =====> delta=-4
P(1,5)=D2, D4, D6 =====> delta=-2
P(1,6)=D2, D4, D5 =====> delta=-6
P(1,7)=D2, D3, D5 =====> delta=0
P(2,3)=D1, D5, D7 =====> delta=0
P(2,4)=D1, D3, D5, D6, D7 =====> delta=-8
P(2,5)=D1, D3, D4, D6, D7 =====> delta=0
P(2,6)=D1, D3, D4, D5, D7 =====> delta=-6
P(2,7)=D1, D3, D5 =====> delta=0
P(3,4)=D2, D5, D6, D7 =====> delta=-10
P(3,5)=D1, D2, D4, D6, D7 =====> delta=-6
P(3,6)=D2, D4, D5, D7 =====> delta=-11
P(3,7)=D2 =====> delta=-1
P(4,5)=D1, D2, D6 =====> delta=-4
P(4,6)=D5 =====> delta=1
P(4,7)=D2, D3, D5, D6 =====> delta=-9
P(5,6)=D1, D2, D4 =====> delta=-1
P(5,7)=D1, D2, D3, D4, D6 =====> delta=-7
P(6,7)=D2, D3, D4, D5 =====> delta=-10

Міняємо місцями елементи 4 та 6

Эл.	1	2	3	4	5	6	7
Поз.	6	7	5	2	3	1	4

Рисунок. 3.13 - Ітераційне розміщення (крок 3)

P(1,2)=D3, D5, D7 =====> delta=-1
P(1,3)=D2, D5, D7 =====> delta=-4
P(1,4)=D2, D5, D6 =====> delta=-6
P(1,5)=D2, D4, D6 =====> delta=-2
P(1,6)=D2, D4, D5 =====> delta=-5
P(1,7)=D2, D3, D5 =====> delta=0
P(2,3)=D1, D5, D7 =====> delta=0
P(2,4)=D1, D3, D5, D6, D7 =====> delta=-7
P(2,5)=D1, D3, D4, D6, D7 =====> delta=0
P(2,6)=D1, D3, D4, D5, D7 =====> delta=-8
P(2,7)=D1, D3, D5 =====> delta=0
P(3,4)=D2, D5, D6, D7 =====> delta=-12
P(3,5)=D1, D2, D4, D6, D7 =====> delta=-6
P(3,6)=D2, D4, D5, D7 =====> delta=-10
P(3,7)=D2 =====> delta=-1
P(4,5)=D1, D2, D6 =====> delta=-2
P(4,6)=D5 =====> delta=-1
P(4,7)=D2, D3, D5, D6 =====> delta=-10
P(5,6)=D1, D2, D4 =====> delta=-4
P(5,7)=D1, D2, D3, D4, D6 =====> delta=-7
P(6,7)=D2, D3, D4, D5 =====> delta=-10

Більше покращень зробити неможливо

Рисунок. 3.14 - Остаточне розміщення

Нумерація виводів мікросхем (рис. 3.15) та конструктивне розміщення елементів на графічній платі після виконання алгоритму розміщення зображено на рис. 3.16.

Рисунок. 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) визначення порядку прокладки сполучень,

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

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

Проводиться трасування вузла Т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.

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

Приклад: проведення траси D6:1,D4:5

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

Рисунок. 4.2 - Трасування (шар 1)

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

Рисунок. 4.3 - Трасування (шар 2)

Таблиця 4.2 - Проведення траси

шаг	L1	M1	v1	L2	M2	v2
1	,( 17, 13)	,( 17, 12),( 16, 13)	0	,( 17, 13)	,( 17, 12),( 16, 13)	0
2	,( 17, 12),( 16, 13)	,( 15, 13),( 16, 14),( 17, 11),( 16, 12),( 18, 12)	0	,( 17, 12),( 16, 13)	,( 17, 11),( 16, 12),( 16, 14),( 18, 12)	0
3	,( 15, 13),( 16, 14),( 17, 11),( 16, 12),( 18, 12)	,( 19, 12),( 18, 11),( 16, 11),( 15, 12),( 14, 13),( 15, 14),( 16, 15)	0	,( 17, 11),( 16, 12),( 16, 14),( 18, 12)	,( 16, 11),( 17, 10),( 18, 11),( 19, 12),( 16, 15)	0
4	,( 19, 12),( 18, 11),( 16, 11),( 15, 12),( 14, 13),( 15, 14),( 16, 15)	,( 19, 11),( 15, 11),( 14, 12),( 13, 13),( 14, 14),( 15, 15),( 16, 16)	0	,( 16, 11),( 17, 10),( 18, 11),( 19, 12),( 16, 15)	,( 16, 10),( 17, 9),( 18, 10),( 19, 11),( 20, 12),( 14, 13),( 16, 16)	1
5	,( 19, 11),( 15, 11),( 14, 12),( 13, 13),( 14, 14),( 15, 15),( 16, 16)	,( 17, 9),( 19, 10),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15),( 15, 16),( 16, 17)	1	,( 16, 10),( 17, 9),( 18, 10),( 19, 11),( 20, 12),( 14, 13),( 16, 16)	,( 16, 9),( 17, 8),( 18, 9),( 19, 10),( 20, 11),( 21, 12),( 14, 12),( 13, 13),( 14, 14),( 16, 17)	1
6	,( 17, 9),( 19, 10),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15),( 15, 16),( 16, 17)	,( 21, 12),( 17, 8),( 16, 9),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),( 14, 16),( 15, 17)	2	,( 16, 9),( 17, 8),( 18, 9),( 19, 10),( 20, 11),( 21, 12),( 14, 12),( 13, 13),( 14, 14),( 16, 17)	,( 16, 8),( 17, 7),( 18, 8),( 20, 10),( 21, 11),( 22, 12),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15)	1
7	,( 21, 12),( 17, 8),( 16, 9),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),( 14, 16),( 15, 17)	,( 17, 7),( 16, 8),( 15, 9),( 21, 11),( 22, 12),( 12, 11),( 11, 12),( 10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)	2	,( 16, 8),( 17, 7),( 18, 8),( 20, 10),( 21, 11),( 22, 12),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15)	,( 16, 7),( 17, 6),( 18, 7),( 21, 10),( 22, 11),( 23, 12),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),( 14, 16)	1
8	,( 17, 7),( 16, 8),( 15, 9),( 21, 11),( 22, 12),( 12, 11),( 11, 12),( 10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)	,( 17, 6),( 16, 7),( 15, 8),( 22, 11),( 23, 12),( 11, 11),( 10, 12),( 9, 13),( 10, 14),( 11, 15),( 12, 16),( 13, 17)	2	,( 16, 7),( 17, 6),( 18, 7),( 21, 10),( 22, 11),( 23, 12),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),( 14, 16)	,( 16, 6),( 17, 5),( 18, 6),( 22, 10),( 23, 11),( 24, 12),( 12, 11),( 11, 12),( 10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)	1
9	,( 17, 6),( 16, 7),( 15, 8),( 22, 11),( 23, 12),( 11, 11),( 10, 12),( 9, 13),( 10, 14),( 11, 15),( 12, 16),( 13, 17)	,( 17, 5),( 16, 6),( 15, 7),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11, 16),( 12, 17),( 23, 11),( 24, 12)	2	,( 16, 6),( 17, 5),( 18, 6),( 22, 10),( 23, 11),( 24, 12),( 12, 11),( 11, 12),( 10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)	,( 16, 5),( 18, 5),( 23, 10),( 24, 11),( 25, 12),( 11, 11),( 10, 12),( 9, 13),( 10, 14),( 11, 15),( 12, 16),( 13, 17),( 14, 18)	1
10	,( 17, 5),( 16, 6),( 15, 7),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11, 16),( 12, 17),( 23, 11),( 24, 12)	,( 17, 4),( 16, 5),( 15, 6),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10, 16),( 11, 17),( 14, 19),( 24, 11),( 25, 12)	3	,( 16, 5),( 18, 5),( 23, 10),( 24, 11),( 25, 12),( 11, 11),( 10, 12),( 9, 13),( 10, 14),( 11, 15),( 12, 16),( 13, 17),( 14, 18)	,( 24, 10),( 25, 11),( 26, 12),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11, 16),( 12, 17),( 13, 18),( 14, 19)	1
11	,( 17, 4),( 16, 5),( 15, 6),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10, 16),( 11, 17),( 14, 19),( 24, 11),( 25, 12)	,( 17, 3),( 16, 4),( 15, 5),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9, 16),( 10, 17),( 13, 19),( 15, 19),( 14, 20),( 25, 11),( 26, 12)	3	,( 24, 10),( 25, 11),( 26, 12),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11, 16),( 12, 17),( 13, 18),( 14, 19)	,( 25, 10),( 26, 11),( 27, 12),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10, 16),( 11, 17),( 12, 18),( 13, 19),( 14, 20),( 15, 19)	1
12	,( 17, 3),( 16, 4),( 15, 5),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9, 16),( 10, 17),( 13, 19),( 15, 19),( 14, 20),( 25, 11),( 26, 12)	,( 18, 3),( 17, 2),( 16, 3),( 15, 4),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7, 15),( 8, 16),( 9, 17),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19),( 26, 11),( 27, 12)	3	,( 25, 10),( 26, 11),( 27, 12),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10, 16),( 11, 17),( 12, 18),( 13, 19),( 14, 20),( 15, 19)	,( 18, 3),( 26, 10),( 27, 11),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9, 16),( 10, 17),( 11, 18),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19)	2
13	,( 18, 3),( 17, 2),( 16, 3),( 15, 4),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7, 15),( 8, 16),( 9, 17),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19),( 26, 11),( 27, 12)	,( 18, 2),( 16, 2),( 15, 3),( 14, 4),( 19, 3),( 7, 10),( 6, 11),( 5, 12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 11, 19),( 12, 20),( 13, 21),( 15, 21),( 16, 20),( 17, 19),( 27, 11),( 28, 12)	3	,( 18, 3),( 26, 10),( 27, 11),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9, 16),( 10, 17),( 11, 18),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19)	,( 17, 3),( 19, 3),( 18, 2),( 26, 9),( 27, 10),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7, 15),( 8, 16),( 9, 17),( 10, 18),( 11, 19),( 12, 20),( 13, 21),( 15, 21),( 16, 20),( 17, 19)	2
14	,( 18, 2),( 16, 2),( 15, 3),( 14, 4),( 19, 3),( 7, 10),( 6, 11),( 5, 12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 11, 19),( 12, 20),( 13, 21),( 15, 21),( 16, 20),( 17, 19),( 27, 11),( 28, 12)	,( 29, 12),( 28, 11),( 27, 10),( 20, 3),( 19, 2),( 15, 2),( 14, 3),( 13, 4),( 6, 10),( 5, 11),( 4, 12),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 10, 19),( 11, 20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)	3	,( 17, 3),( 19, 3),( 18, 2),( 26, 9),( 27, 10),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7, 15),( 8, 16),( 9, 17),( 10, 18),( 11, 19),( 12, 20),( 13, 21),( 15, 21),( 16, 20),( 17, 19)	,( 26, 8),( 27, 9),( 16, 3),( 17, 2),( 18, 1),( 19, 2),( 20, 3),( 6, 11),( 5, 12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 9, 18),( 10, 19),( 11, 20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)	2
15	,( 29, 12),( 28, 11),( 27, 10),( 20, 3),( 19, 2),( 15, 2),( 14, 3),( 13, 4),( 6, 10),( 5, 11),( 4, 12),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 10, 19),( 11, 20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)	,( 20, 4),( 21, 3),( 27, 9),( 28, 10),( 29, 11),( 30, 12),( 29, 13),( 18, 18),( 19, 19),( 18, 20),( 17, 21),( 9, 19),( 10, 20),( 11, 21),( 5, 10),( 4, 11),( 4, 15),( 5, 16),( 6, 17),( 13, 3),( 12, 4)	3	,( 26, 8),( 27, 9),( 16, 3),( 17, 2),( 18, 1),( 19, 2),( 20, 3),( 6, 11),( 5, 12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 9, 18),( 10, 19),( 11, 20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)	,( 29, 12),( 27, 8),( 26, 7),( 21, 3),( 20, 2),( 19, 1),( 17, 1),( 16, 2),( 15, 3),( 6, 10),( 5, 11),( 4, 12),( 3, 13),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 8, 18),( 9, 19),( 10, 20),( 11, 21),( 17, 21),( 18, 20),( 19, 19)	3
16	,( 20, 4),( 21, 3),( 27, 9),( 28, 10),( 29, 11),( 30, 12),( 29, 13),( 18, 18),( 19, 19),( 18, 20),( 17, 21),( 9, 19),( 10, 20),( 11, 21),( 5, 10),( 4, 11),( 4, 15),( 5, 16),( 6, 17),( 13, 3),( 12, 4)	,( 22, 3),( 21, 4),( 27, 8),( 28, 9),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 19, 18),( 19, 20),( 20, 19),( 18, 21),( 8, 19),( 9, 20),( 10, 21),( 5, 17),( 4, 16),( 4, 10),( 12, 3),( 11, 4)	3	,( 29, 12),( 27, 8),( 26, 7),( 21, 3),( 20, 2),( 19, 1),( 17, 1),( 16, 2),( 15, 3),( 6, 10),( 5, 11),( 4, 12),( 3, 13),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 8, 18),( 9, 19),( 10, 20),( 11, 21),( 17, 21),( 18, 20),( 19, 19)	,( 20, 1),( 21, 2),( 22, 3),( 16, 1),( 15, 2),( 14, 3),( 26, 6),( 27, 7),( 29, 11),( 30, 12),( 29, 13),( 19, 18),( 20, 19),( 19, 20),( 18, 21),( 5, 10),( 4, 11),( 3, 12),( 2, 13),( 3, 14),( 4, 15),( 5, 16),( 6, 17),( 7, 18),( 8, 19),( 9, 20),( 10, 21)	3
17	,( 22, 3),( 21, 4),( 27, 8),( 28, 9),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 19, 18),( 19, 20),( 20, 19),( 18, 21),( 8, 19),( 9, 20),( 10, 21),( 5, 17),( 4, 16),( 4, 10),( 12, 3),( 11, 4)	,( 22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),( 2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15, 1),( 14, 2),( 13, 3),( 23, 3),( 22, 4),( 27, 7),( 28, 8),( 29, 9),( 30, 10),( 30, 14),( 29, 15),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 9, 21),( 8, 20),( 7, 19),( 2, 13),( 11, 3),( 10, 4),( 4, 17)	4	,( 20, 1),( 21, 2),( 22, 3),( 16, 1),( 15, 2),( 14, 3),( 26, 6),( 27, 7),( 29, 11),( 30, 12),( 29, 13),( 19, 18),( 20, 19),( 19, 20),( 18, 21),( 5, 10),( 4, 11),( 3, 12),( 2, 13),( 3, 14),( 4, 15),( 5, 16),( 6, 17),( 7, 18),( 8, 19),( 9, 20),( 10, 21)	,( 22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),( 2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15, 1),( 14, 2),( 13, 3),( 26, 5),( 27, 6)	3
18	,( 22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),( 2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15, 1),( 14, 2),( 13, 3),( 23, 3),( 22, 4),( 27, 7),( 28, 8),( 29, 9),( 30, 10),( 30, 14),( 29, 15),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 9, 21),( 8, 20),( 7, 19),( 2, 13),( 11, 3),( 10, 4),( 4, 17)	,( 23, 4),( 24, 3),( 27, 6),( 28, 7),( 29, 8),( 30, 9),( 30, 15),( 29, 16),( 21, 18),( 22, 19),( 21, 20),( 20, 21),( 8, 21),( 7, 20),( 6, 19),( 2, 12),( 1, 13),( 2, 14)	4	,( 22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),( 2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15, 1),( 14, 2),( 13, 3),( 26, 5),( 27, 6)	,( 22, 1),( 23, 2),( 24, 3),( 23, 4),( 29, 9),( 30, 10),( 30, 14),( 29, 15),( 14, 1),( 13, 2),( 12, 3),( 27, 5),( 21, 18),( 22, 19),( 21, 20),( 20, 21),( 8, 21),( 7, 20),( 6, 19),( 5, 18),( 4, 17),( 3, 16),( 2, 15),( 1, 14),( 1, 12),( 2, 11),( 3, 10)	3
19	,( 23, 4),( 24, 3),( 27, 6),( 28, 7),( 29, 8),( 30, 9),( 30, 15),( 29, 16),( 21, 18),( 22, 19),( 21, 20),( 20, 21),( 8, 21),( 7, 20),( 6, 19),( 2, 12),( 1, 13),( 2, 14)	,( 23, 5)	4	,( 22, 1),( 23, 2),( 24, 3),( 23, 4),( 29, 9),( 30, 10),( 30, 14),( 29, 15),( 14, 1),( 13, 2),( 12, 3),( 27, 5),( 21, 18),( 22, 19),( 21, 20),( 20, 21),( 8, 21),( 7, 20),( 6, 19),( 5, 18),( 4, 17),( 3, 16),( 2, 15),( 1, 14),( 1, 12),( 2, 11),( 3, 10)	,( 23, 5)	3

Шляхи одночасно досягли координати ( 23, 5), тому шлях проводится за найменшим значенням ?.

Остаточно шлях має вигляд:

Шар 2:

(17,13),( 17, 12),( 17, 11),( 17, 10),( 17, 9),( 17, 8),( 17, 7),( 17, 6),

Перехід на шар 1:

( 17, 5),( 17, 4),( 17, 3),( 18, 3),( 19, 3),( 20, 3),( 21, 3),( 22, 3),( 23, 3),( 23, 4), ( 23, 5)

5 РОЗПОДІЛ СПОЛУЧЕНЬ ПО ШАРАХ

Розподіл сполучень по шарам полягає в виділенні на кожному кроку сполучення з максимальним числом пересічень і вилучення його на другий шар. Сполучення переносяться з першого шару на другий до тих пір, доки не будуть усунені всі пересічення.

При виконанні розшарування необхідно отримати граф пересічень, вершини якого відповідають окремим провідникам, а ребра - їхнім пересіченням. Побудуємо граф пересічень схеми сполучень, наведеної на рис. 5.1.

Граф пересічень (рис. 5.2) можна уявити в вигляді матриці пересічень П=|| n || kk (рис. 5.3), де

Якщо провідник i перетинається з провідником j;

В противному випадку.



Рисунок. 5.1 - Комутаційна схема сполучень вузла Т1

Рисунок. 5.2 - Граф пересічень

V1

V6

V7

V8

V9

V10

V11

V13

V14

V15

V16

V17

V18

V19

V20

V21

V22

V23

V24

V1

V6

V7

V8

V9

V10

V11

1

1

V13

1

1

V14

V15

1

1

V16

V17

V18

1

1

V19

V20

1

V21

1

V22

1

1

1

V23

1

1

V24

1

Рисунок. 5.3 - Матриця пересічень

По матриці П будуємо вектор-стовпчик Е1, з нього вибираємо максимальний елемент; якщо їх декілька, то береться будь-який. Отже, беремо елемент V22 і на його місце записуємо нуль, що відповідає переносу провідника V22 на другий шар. По матриці П визначаються ребра, і в векторі-стовпчикові Е1 значення елементів, відповідних цим провідникам, зменшуються на 1, т.т. в матриці П викреслюється стовпчик, відповідний провіднику 16. Одержуємо стовпчик Е2 після першого кроку алгоритму. З стовпчика Е2 вибираємо елемент V18 і процедура повторюється, доки не дістанемося стовпчика Е5, всі елементи якого дорівнюють нулю.

	V11	2		V11	1		V11	1		V11	1		V11	0
	V13	2		V13	1		V13	1		V13	1		V13	0
	V15	2		V15	1		V15	1		V15	0		V15	0
	V18	2		V18	2		V18	0		V18	0		V18	0
E1=	V20	1	E2=	V20	1	E3=	V20	0	E4=	V20	0	E5=	V20	0
	V21	1		V21	1		V21	0		V21	0		V21	0
	V22	3		V22	0		V22	0		V22	0		V22	0
	V23	2		V23	2		V23	2		V23	0		V23	0
	V24	1		V24	1		V24	1		V24	0		V24	0

Рисунок. 5.4 - Вектори - стовпчики Е для 2-го шару

Після перенесення провідників V11, V18, V22, V23 на другий шар отримаємо двошаровий розподіл сполучень схеми.

Далі проводиться розподіл по другому шару аналогічно

Рисунок. 5.5 Граф пересічень шара 2

	V11	V18	V22	V23
V11			1
V18
V22	1
V23

Рисунок. 5.6 - Матриця пересічень шара 2

Не будуючи вектори Е, можна зразу перенести V11 в 3-ій шар.

6 РОЗРОБКА БІБЛІОТЕКИ ЕЛЕМЕНТІВ В САПР PCAD

6.1 Створення символу компоненту в PCAD Schematic

Спочатку по команді Options-> Configure вибирають систему одиниць і по команді Options->Grid встановлюють необхідний крок сітки, в даному прикладі метрична система, крок сітки 5 мм.

Потім по команді Place->Line і Place->Arc малюється контур символу лініями шириною 0,25 мм.

Текстові написи наносять по команді Place->Text, висновки - по команді Place->Pin. У меню цієї команди в графі Display потрібно включити опції Pin Name і Pin Des (видимість на схемі імен і номерів висновків), в графі Length вказати довжину висновків (Short -2,5 мм, Normal - 7,6 мм, Long - 12,7 мм, User - призначається користувачем). Графіку висновків вибирають в графі Display Characteristic.

В результаті малюється заготівка символу (рис 6.1). Далі по команді Place->Attributes розміщують атрибути RefDes і Type. Всі виведення символу одержують однакове позиційне позначення за умовчанням. Виводи нумерують по команді Utils->Renumber. У графі Турі вибирають режим нумерації виведень Default Pin Des і на рядках Starting Number і Increment Value задаються початкове значення і приріст позиційних позначень виводів. Для нумерації виводів їх по черзі вибирають курсором, починаючи з першого. Як точка прив'язки по команді Place->Point звичайно відзначають верхній лівий вивід символу.

При створенні символу багатосекційного компоненту нумеруються тільки виведення першої секції, а виведення решти секцій нумеруються пізніше в таблиці виведень Pins View.

На закінчення всі об'єкти, що відносяться до символу компоненту, вибираються у вікні, і виконується команда його занесення в бібліотеку Library->Symbol Save As, при цьому елемент повинен бути виділений весь. У меню цієї команди вибирають ім'я однієї з відкритих бібліотек, куди потрібно занести створений символ, і вводять його ім'я.

6.2 Створення корпусу компонентів в PCAD PCB

Спочатку по команді Options-> Configure вибирають систему одиниць і по команді Options->Grid встановлюють необхідний крок сітки, рівний відстані між висновками, в даному прикладі вибрана метрична система з кроком сітки 2,5 мм.

Потім в два ряди розміщуються 14 (16, 18 або 24) висновків з кроком 2,5 мм між висновками і відстанню між рядами 7,5 мм. Як стиль стека контактних майданчиків за допомогою команди Options->Pad Style вибирають стиль за умовчанням DEFAULT або будь-який інший. Спочатку по команді Place->Pad розміщують перше виведення компоненту. Решту висновків можна розмістити двома способами. По-перше, все їх можна розмістити уручну, продовжуючи виконання команди Place->Pad. Проте зручніше скоректувати перший висновок, вибравши його, виконавши команду Edit->Copy Matrix. Встановлюють число рядів Number of Columns - 2, відстань між рядами Column Spacing - 7,5 мм, число рядків Number of Rows - 7, і відстань між виведеннями Row Spacing - 2,5 мм. Потім крок сітки зменшують до 0,5 мм, і на шарі Top Silk малюється контур компоненту за допомогою команд Place->Line і Place->Arc лініями шириною 0,2 мм.

Далі на шар Top Silk по команді Place->Attributes/У діалоговому меню команди указують тип нумерації Pad Num, початковий номер 1 (Starting Number). Для привласнення номерів висновки по черзі позначають курсором згідно цокольовки. Як точка прив'язки по команді Place->Point/RefPoint відзначають верхнє ліве (або нижній лівий) виведення компоненту (при необхідності також відзначають Glue Dot, Pick and Place і Test Point).

Components розміщують атрибути RefDes і Type (останній повернений на 90 градусів).

При розміщенні висновків всі вони за умовчанням одержали порядковий номер 0. Автоматична нумерація висновків виконується по команді Utils->Renumber, заздалегідь включивши режим вибору.

На закінчення всі об'єкти, що відносяться до корпусу компоненту, вибирають у вікні і виконують команду занесення його в бібліотеку Library->Patern Save As. У меню цієї команди указують ім'я однієї з відкритих бібліотек, куди потрібно занести корпус, і вводять ім'я корпусу, наприклад DIP14.

Опцію Match Default Pin Des to Pad Numbers потрібно включити, щоб позиційні позначення висновків за умовчанням співпали з введеними раніше номерами виведень компоненту Pad Numbers.

Рисунок. 6.2 - Корпус DIP24

6.3 Створення компоненту за допомогою Library Executive

Після завантаження Library Executive або Library Manager виконується команда створення нового компоненту Component->New, і в її діалоговому вікні указують файл бібліотеки, в який раніше занесені корпус і символ компоненту. Потім на екран виводиться вікно Component Information. У ньому спочатку натискають кнопку Select Pattern для підключення графіки корпусу компоненту. У вікні Library Browse, що відкрилося, із списку корпусів поміщених у відкриту бібліотеку вибирають потрібний корпус.

1) У рядку Number of Gates указують число секцій. Число виведень компоненту проставляється на рядку Number of Pads автоматично. У рядку RefDes Prefix указують префікс позиційного позначення компоненту, в даному прикладі D. Після цього стає доступною панель Select Symbol, після натиснення, на яку вибирають ім'я основного зображення символу компоненту.

2) У графі Component Type вибирають тип компоненту Normal.

3) У графі Component Style для однорідного компоненту вибирають рядок Homogeneous.

4) У графі Gate Numbering вибирають буквений спосіб іменування секцій компоненту. Всі секції однорідних компонентів за умовчанням одержують однаковий код логічної еквівалентності Gate Eq, що дозволить їх автоматично переставляти в процесі розміщення компонентів на друкарській платні.

Створення компоненту завершується заповнення таблиці висновків, яка виводиться на екран натисненням кнопки Pins View. Це сама трудомістка частина роботи із створення компоненту.

По-перше, потрібно встановити відповідність між номерами виводів всіх секцій Sym Pin # і позиційними позначеннями виведень корпусу Pin Des (порядкові номери виведень Pad Numbers звичайно вважають рівними Pin Des). Помітимо, що потрібно передбачити виводи “живлення” та “земля”.

В колонці Pin Name введемо імена виводів першої секції. Для цього курсором виділимо відповідний осередок і введемо необхідну інформацію, яка з'явиться на рядку над таблицею. Натисненням кнопки Enter введені дані переносяться у виділений осередок. Натиснення Esc відміняє введення.

У графах Gate Eq і Pin Eq еквівалентним секціям і вхідним виводам кожної секції привласнюється однаковий код еквівалентності, що дозволить міняти їх місцями в процесі автотрасування.

В графі Elec. Type указують тип висновку, використовуваний при пошуку помилок в принципових електричних схемах. Натиснення на праву кнопку миші відкриває список типів висновків (Electrical Type). Для швидкого вибору типу висновку досить надрукувати перший символ його імені. Наприклад, введення символу I привласнює тип Input. Якщо є декілька типів висновків, що починаються на один і той же символ, цей символ вводять другий раз, потім третій і т.д., циклічно перебираючи всі варіанти.

Для простановки символу логічної інверсії в імені висновку використовується знак “~”.

Рисунок. 6.3 - Компонент та його таблиця виводів

7 РОЗРОБКА СЕМИ ЕЛЕКТРИЧНОЇ ПРИНЦИПОВОЇ В САПР PCAD.

7.1 Завантаження бібліотек

Перед нанесенням на схему символів компонентів по команді L забезпечується доступ до необхідних бібліотек (рис 7.1.). Натиснувши клавішу. А, додають імена бібліотек в список відкритих бібліотек (Open Libraries). За допомогою клавіші Delete видаляють бібліотеки з цього списку, щоб звільнити місце для інших. За допомогою клавіш Move Up, Move Down змінюють порядок їх розташування в списку (потрібно враховувати, що при пошуку компонентів бібліотеки є видимими в списку в напрямі зверху - вниз).

7.2 Розміщення компонентів на схемі

У режим розміщення символів компонентів на схемі переходять по команді Place->Part,. Після цього клацання курсором в будь-якій точці схеми відкриває меню вибору компоненту.

У графі Num Parts указується загальне число секцій компоненту (змінювати їх на цьому етапі не можна).

Позиційні позначення компонентів на схемі проставляються автоматично. Наприклад, якщо з імпортної бібліотеки інтегральних мікросхем ТТЛ серії 7400 послідовно розміщувати на схемі 4-секційну ІС 7408, то перший елемент придбає позиційне позначення U1:А. Префікс позиційного позначення U призначений при створенні компоненту (при необхідності його можна замінити, наприклад на D), номер першого компоненту 1 і ім'я першої секції А проставляються автоматично, тобто перший елемент одержить позиційне позначення U1:А. Другий елемент одержить позиційне позначення U1:В, третій - U1:С, четвертий- U1:D, п'ятий - U2:А і т.д. Для зміни призначеного в бібліотеці префікса позиційного позначення його треба указувати в полі RefDes в явному вигляді. Для компонентів, що складаються з однієї секції, ім'я секції не проставляється.

Секції компонентів одержать позначення D1:1, D2:2 і т.д., як цього вимагає ЕСКД (по ЕСКД потрібно відокремлювати номер секції не двокрапкою, а крапкою: D1.1, D1.2 і т.д.). При зображенні багатосекційних компонентів суміщеним способом (зображення суміжних секцій примикають один до одного) позиційні позначення окремих секцій звичайно не указуються, для цього необхідно параметри RefDes всіх секцій, окрім першої, зробити невидимими (вимикати кнопку Visibility), тоді буде видно позиційне позначення тільки першої секції, наприклад D9:1.