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

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 || k´k (рис. 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.

На рядку Value проставляють номінал компоненту, наприклад опір резистора.

Після вибору в меню Place->Part потрібного компоненту і введення необхідних параметрів натискають Ok - курсор прийме форму перехрестя з розривом в центрі для точного позиціонування у вузлах сітки. Безпосереднє розміщення символу компоненту на схемі виконується після клацання курсором в будь-якій точці вікна. До тих пір, поки не відпущена ліва кнопка миші, символ переміщається по екрану. Він повертається на 90 градусів в напрямі проти годинникової стрілки і дзеркально відображається натисненням клавіш R і F відповідно. Повторне клацання курсором розміщує на схемі чергову копію символу вибраного компоненту, привласнюючи йому наступні позиційні позначення, які одночасно виводяться в рядку інформації. Для збільшення на 1 номери секції компоненту перед розміщенням символ натискають клавішу P, а для збільшення - клавішу D. Зменшити ці значення можна одночасним натисненням клавіш Shift-P або Shift-D. Натиснення правої кнопки миші або Esc припиняє введення символу.

7.3      Розміщення електричних ланцюгів

Після вибір команди Place->Wire курсор приймає форму перехрестя. Клацанням миші наголошується початкова точка ланцюга. Кожне натиснення лівої кнопки миші фіксує точку зламу. Натиснення клавіші 0 до опускання лівої кнопки миші змінює кут введення лінії з числа розміщених варіантів, натиснення клавіші F змінює її орієнтацію. У зв'язку з тим, що на схемі звичайно переважають горизонтальні або вертикальні ланцюги, в меню Options->Configure досить включити тільки режим введення ортогональних ланцюгів 90/90 Line-Line. Завершується введення ланцюга натисненням правої кнопки миші або Esc.

Ширина ланцюга, що прокладається, встановлюється по команді Options->Current Wire: Thick - широка (шириною 0.381), Thin - вузька (шириною 0.254 мм ) і User - що задається користувачем.

Привласнити ланцюги інше ім'я можна 2 способами.

По-перше, індивідуально вибрати кожен ланцюг і клацанням правої кнопки миші відкрити меню редагування пункт Properties. На екрані з'явиться інформація про вибраний ланцюг. На закладці Net можна змінити ім'я ланцюга, замінивши на рядку Net Name призначене системою ім'я іншим. Це ім'я буде видимим, якщо включити на закладці Wire перемикач Display. Тип і розмір шрифту імені указують після натиснення на клавішу Text Styles. На закладці Net можна також задати значення різним атрибутам ланцюга, натиснувши на клавішу Net Attrs.

По-друге, можна спростити введення імен груп ланцюга тих, що мають однорідні імена типу D1, D2, і т.д., і їх перейменування. Для цього потрібно вибрати команду Utils>Rename Nets, клацнути курсором в будь-якій точці схеми і в меню, що відкривається, на рядку Net Name ввести префікс імені, наприклад IN, і вибрати параметр Increment Name (режим приросту імені). Після закриття цього меню клацанням курсора по першому ланцюгу їй привласнюється ім'я IN0, по другій IN1 і т.д. Що б почати нумерацію ланцюгів не з 0, потрібне початкове ім'я ввести в явному вигляді, наприклад DATA5. Тоді перший ланцюг одержить ім'я DATA5, друга DATA6 і т.д.

7.4      Розміщення шин

Вибір команди Place->Bus активізує режим введення шин. Клацанням курсора відзначають початок шини і точки її зламу. Побудова шини завершується натисненням правої кнопки миші або Esc.

Після цього по команді Place->Wire розміщують ланцюги. При малюванні ланцюга, що входить до складу шини, її початок або кінець повинні розташовуватися в будь-якій точці шини. При цьому при підключенні до шини автоматично зображається злам ланцюга по кутом 45 градусів (стиль цього зображення встановлюють в меню командою Options->Display).

Імена ланцюгів, створюючих шину задаються підключенням до ланцюгів по команді Place->Port спеціальних портів (командами Edit->Nets і Util->Rename Nets в цих цілях користуватися не рекомендується). Після вибору команди Place->Port клацанням миші на будь-якій точці схеми відкривається меню вибору порту. На розташованому вгорі рядку Net Name указують ім'я першого ланцюга, наприклад D1. Якщо включити перемикач Increment Port Name, то при розміщенні портів вони автоматично одержать імена D1, D2, і т.д.

7.5      Створення списку з'єднань

Список з'єднань включає список компонентів і ланцюгів з вказівкою номерів виведень компонентів, до яких вони підключені. Він використовується для так званої процедури “упаковки схеми на друкарську платню” - розміщення на полі друкарської платні корпусів компонентів з вказівкою їх електричних зв'язків згідно принциповій схемі. По команді Utils->Generate Netlist відкривають меню настройки параметрів. У пункті меню Netlist Format вибирається формат списку з'єднань: PCAD ASCII, Tango, FutureNet Netlist, FutureNet Pinlist, Master Designer, EDIF 2.0.0, PSpice, Xspice..

Рисунок. 7.1 - Схема електрична принципова в САПР PCAD

8          РОЗМІЩЕННЯ ЕЛЕМЕНТІВ НА ПЛАТІ В САПР PCAD

Перед розміщенням компонентів на плату визначається крок сітки робочого поля. Наприклад, для компонентів з планерними висновками цей крок встановлюється рівним 1,25 мм, а для компонентів з штирьовими висновками - 2,5 мм.

Потім необхідно в шарі Board намалювати на робочому полі монітора замкнутий контур друкарської плати. Промальовування проводиться за допомогою команд Place/Line і Place/Arc.

Якщо відсутня принципова схема, виконана в P-CAD Schematic, то компоненти на плату встановлюють по команді Place/ Component. Зв'язки між компонентами проводять по команді Place/ Connection.

Якщо ж принципова схема є, то проводиться так звана упаковка схеми на друкарську плату (повинна бути відкрита потрібна бібліотека).

8.1       Упаковка схеми на друкарську плату

Спочатку необхідно по команді Utils/Load Netlist (мал. 8.1) завантажити файл списку з'єднань (розширення *.net) друкарської плати.

У діалоговому вікні використовуються наступні опції:

-Netlist Filename - вибір імені файлу списку з'єднань на жорсткому диску.

Якщо вибраний формат ASCII, то стає доступною область Attribute Handling, в якій задається режим обробки атрибутів:

-Merge Attributes (Favor Netlist) - об'єднання атрибутів списку ланцюгів з поточними атрибутами ланцюгів проекту; пріоритет за атрибутами списку ланцюгів;

-Merge Attributes (Favor Design) - об'єднання атрибутів списку ланцюгів з поточними атрибутами ланцюгів проекту; пріоритет за атрибутами ланцюгів проекту;

-Replace Existing Attributes - заміна поточних атрибутів проекту на атрибути списку ланцюгів;

-Ignore Netlist Attributes - ігнорування атрибутів списку ланцюгів;

-Прапорець Optimize Nets - включає режим оптимізації довжин з'єднань шляхом перестановки логічно еквівалентних вентилів і контактів. Якщо цей режим вимкнений, то зв'язки проводяться в тому порядку, в якому вони записані в списку з'єднань. Прапорець рекомендується включити після впорядковування розміщення компонентів уручну або по команді Utils/Optimize Nets;

-Прапорець Reconnect Cooper - дозволяє підключати до ланцюгів схеми ділянки металізації, що є на платі. Якщо цей режим вимкнений, то екрани, що є на платі, розглядаються як вільні області;

-Прапорець Check for Cooper Sharing - включає режим перевірки наявності помилок на платні із заздалегідь розміщеними компонентами і частиною заздалегідь проведених з'єднань. В результаті частина електричних з'єднань вважається вже відрасированою або підлягає дотрассировці.

-Прапорець Create Pseudo Pattern - допускає завантаження списку з'єднань, що містить посилання на компоненти, що не мають приєднаних корпусів.

Якщо списки ланцюгів виконані у форматі P-CAD ASCII, то можливі два варіанти настройки атрибутів ланцюгів. Настройка класів ланцюгів проводиться у області Net Class and Rules Handling:

-Replace Existing Net Classes - заміна існуючих класів ланцюгів проекту класами ланцюгів із списку ланцюгів;

-Ignore Netlist Net Classes - ігнорувати існуючі класи ланцюгів.

Після завантаження команди Utils/Load Netlist виводиться повідомлення про необхідність дотримувати наступні обмеження:

-компоненти із співпадаючими на платні і схемі позиційними позначеннями (RefDes) повинні мати однаковий тип корпусу (Турі). Інакше упаковка схеми не проводиться;

-всі компоненти, встановлені на плату перед упаковкою, але що не входять в список з'єднань, будуть збережені;

-на друкарську плату переносяться всі компоненти із списку з'єднань, які заздалегідь не були встановлені на плату;

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

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

Після натиснення на кнопку Yes завантажувані компоненти проекту розміщуються над верхньою межею друкарської плати (якщо вже розміщена заготівка друкарської плат). Якщо ж немає заготівки, то всі компоненти розміщуються в лівому нижньому кутку робочого простору проекту. При цьому на екрані відображаються прямі лінії ще не проведених електричних зв'язків.

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

По команді Library/Setup можна проглянути перелік відкритих бібліотек.

Тепер можна розміщувати компоненти схеми в контурі друкарської платі.

8.2       Розміщення компонентів на платі

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

“Павутина” ліній зв'язків, що з'являється між компонентами, дозволяє розробнику орієнтуватися при розміщенні компонентів. При переміщенні компонентів вказана “павутина” переміщається разом з компонентом. Компоненти при установці можна розгортати (клавіша R) або переносити на протилежну сторону плати (клавіша F).

При розміщенні компонентів можна приховати або зробити видимими електричні зв'язки для однієї або декількох ланцюгів, можна перейменувати один ланцюг або групу ланцюгів, можна відредагувати значення атрибутів. Для цих і інших цілей служить діалогове вікно команди Edit/Nets (мал. 8.3).

У вікні Nets відображені імена всіх ланцюгів проекту, а у вікні Nodes вказані імена компонентів і номера їх контактів, пов'язані з виділеним ланцюгом. Можна виділити всі ланцюги списку (кнопка Set All Nets). Або після натиснення на кнопку Set Nets By Attribute виділити всі ланцюги, що мають однакове значення атрибуту (наприклад, однакову ширину провідника Width). Виділення ланцюгів по атрибуту проводиться в діалоговому вікні, що з'явилося. Зняття виділення всіх ланцюгів проводиться кнопкою Clear All Nets.

Потрібний ланцюг можна виділити по його імені.

Кнопка Set Nets By Node Count дозволяє вибрати ланцюги з мінімальним і максимальним числом контактів, значення яких встановлюються у вікнах Min і Мах.

Кнопка Edit Attributes дозволяє перейти до редагування або установки атрибутів виділеного ланцюга. Кнопка View Attributes відкриває редактора Notepad для проглядання встановлених атрибутів ланцюга.

 Натиснення кнопки Info відображає всю інформацію про виділений ланцюг.

Кнопка Show Conns підсвічує на екрані всі фрагменти, відповідні вибраному ланцюгу, а кнопка Show Conns Only on Drag включає видимість всіх зв'язків тільки при переміщенні компоненту.

Кнопка Hide Conns приховує відображення виділеного ланцюга і її зв'язків.

Кнопки Highlight і Unhighlight висвічують або прибирають підсвічування виділеного ланцюга або ланцюгів. Якщо виділений ланцюг і її вузол у вікні Nodes, то натиснення кнопки Jump to Node дозволяє перейти до вказаного вузла. Кнопка Select дозволяє перейти до редагування вибраного ланцюга.

Кнопка Pad Properties дозволяє змінити стиль контактного майданчика.

Автоматичне вирівнювання компонентів на друкарській платі

Для автоматичного вирівнювання компонентів після розміщення на друкарській платі спочатку їх треба виділити (при виборі другого і подальшого компонентів утримувати клавішу Ctrl). Потім натиснути праву кнопку миші, вибрати точку прив'язки Selection Point і встановити її в точку друкарської платі, щодо якої проводитиметься вирівнювання. Знов натиснути праву кнопку миші і вибрати строчку Align. У області Alignment діалогового вікна вибрати один з трьох можливих напрямів вирівнювання:

-Horizontal Aboute Selection Point - вирівнювання по горизонталі щодо вказаної на платі точки прив'язки;

-Vertical Aboute Selection Point - вирівнювання по вертикалі щодо точки прив'язки;

-Onto Grid - вирівнювання у вузлові точки сітки.

У області Component Spasing, якщо встановлений прапорець Space Egually, то у вікні Spacing можна точно встановити відстань між компонентами, що вирівнюються, у вибраній системі одиниць.

Помітимо, що вказані команди вирівнювання не діють на зафіксовані компоненти.

 

Рисунок. 8.1 - Розміщення на друкарскій платі

9          ТРАСУВАННЯ ПЕЧАТНИХ СПОЛУЧЕНЬ ПЕЧАТНОЇ ПЛАТИ В САПР PCAD   9.1      Установка кроку сітки

В деяких випадках, окрім регулярної сітки, для трасування можна використовувати і нерегулярну сітку з метою 100-процентної прокладки всіх з'єднань схеми. Наприклад, якщо крок між виведеннями компоненту заданий велічиной 2,5мм і діаметр контактної площадки-равен 1,5 мм, то для прокладки двох провідників завтовшки 0,2 мм між сусідніми висновками при допустимій величині зазора 0,2 мм необхідно задати сітку 1,05 мм-0,2 мм-0,2 мм-1,05 мм або 1 мм-0,5 мм-1 мм.

Щоб встановити вказану нерегулярну сітку, необхідно виконати команду Opnions/Grids, в діалоговому вікні, що з'явилося, у області Grid Spasing ввести через пропуск вибрані кроки нерегулярної сітки і натиснути кнопку Add. Введена сітка зафіксується у вигляді окремого рядка у області вікна Grids.

9.2      Установка зазорів між провідниками

Для різних об'єктів (для сукупності електричних ланцюгів, для різних ділянок ПП і т. п.) проекту встановлюються різні правила трасування і їм привласнюються різні пріоритети:

-Class To Class - правила клас-клас (вищий пріоритет);

-Net - правила для ланцюгів;

-Net Class - правила для класів ланцюгів;

-Global - глобальні правила (нижчий пріоритет).

Глобальні установки зазорів встановлюються в меню Options/ Design Rules в закладці Design

Зазори між різними об'єктами в різних шарах ПП встановлюються в закладці Layer

Класи ланцюгів визначають в закладці Net Class команди Options/ Design Rules (мал. 9.2). Усередині кожного класу встановлюються допустимі зазори для пари об'єктів (контактний майданчик - провідник, контактний майданчик - контактний майданчик, провідник - провідник і т. п.) і загальні правила установки зазорів. Помітимо, що автотрасировщик PRO Route використовує тільки глобальні установки зазорів і правила трасування закладки Net меню Options/ Design Rules.

У вікні Net Classes задані імена класів ланцюгів, а у вікні Net Class Rules виведені конкретні значення атрибутів для виділеного класу ланцюгів. Значення виділеного атрибуту може бути змінено після натиснення на кнопку Edit, потім на кнопку Properties і введенні у вікно Value потрібного значення атрибуту.

Для того, щоб ввести Net Class - новий клас ланцюгів (група ланцюгів, що використовують одні і ті ж правила трасування), треба натиснути на кнопку Edit Net Classes, потім у вікні Class Name введіть ім'я нового класу ланцюгів і клацніть кнопку справа Add (додати). Нове ім'я класу ланцюгів з'явиться у вікні Classes.

Для завдання атрибуту новому класу ланцюгів треба виділити в списку ім'я нового класу і натиснути кнопку Edit праворуч від вікна Net Class Rules. З'явиться нове вікно Attributes. Після натиснення на кнопку Add в новому вікні Place Attribute, що з'явилося, треба вибрати категорію атрибуту (Attribute Caterory), ім'я атрибуту (Name), проставити значення (Value) атрибуту і натиснути ОК. Для зміни значення атрибуту у вікні Attributes натиснути кнопку Properties.

Додавання нового ланцюга до виділеного класу проводиться після вибору однієї або декількох (утримуйте клавішу Shift або Ctrl) ланцюгів в полі Unassigned Nets і натисненні кнопки Add. Імена виділених ланцюгів відобразяться у вікні Nets in this Class, а в полі Unassigned Nets відображається список ланцюгів, що не належать ні до одного з класів ланцюгів.

Класи ланцюгів можна перейменовувати (Rename) і видаляти (Delete).

У вікні Class Attributes записані вже сформовані після натиснення кнопки Edit Attrs значення атрибутів.

Кнопка Set Nets From Design Selection дозволяє внести в список ланцюгів, що належать даному класу, всі ланцюги, виділені користувачем за допомогою команди Edit Select на малюнку принципової схеми.

Зазори для конкретних ланцюгів встановлюються в закладці Net команди Options/Design Rules. Для цього заздалегідь вибирають курсором ім'я ланцюга, натискають кнопку Edit, потім на кнопку Add, в графі Name виділяють ім'я потрібного атрибуту і у області Value вікна Place Attribute, що з'явилося, вводять необхідне значення зазора.

Редагування ланцюга проводиться після виділення її імені в стовпці Nets, натисненні на кнопку Edit Nets.

Зазори між ланцюгами, що відносяться до різних класів, встановлюють в закладці Class to Class. Формування пари класів проводиться після виконання наступних операцій. Натискається кнопка Edit Class to Class. У вікні, що з'явилося, в двох однойменних рядках Net Class Name вибирають імена двох різних класів ланцюгів, які визначені раніше, і натискають кнопку Add Definition. В результаті імена пари класів з'являються у вікні Net Class To Net Class Definition. Потрібні величини зазорів встановлюють у вікні Place Attribute, що з'явилося, після послідовних натиснень на кнопки Edit і Add.

9.3      Автотрасувальник Quick Route

Автотрасувальник запускається з графічного редактора P-CAD РСВ за допомогою меню Route/Autorouters.

Автотрасувальник не вимагає вказівки межі друкарської плати в шарі Board і не змінює топологію заздалегідь прокладених користувачем провідників. Заздалегідь на платні повинні бути розміщені всі компоненти, визначені всі електричні зв'язки. Деякі зв'язки можуть бути вже проведені. Можна задати області заборони для трасування по команді Place/KeepOut.

У області Strategy діалогового вікна знаходяться наступні кнопки:

-Strategy File - файл стратегії трасування, тобто сукупність параметрів для трасування (розширення файлу - .STR). За умовчанням має ім'я вхідного файлу;

-Output PCB File - файл із записом результатів трасування (розширення файлу *.РСВ). За умовчанням має ім'я вхідного файлу, але перед ім'ям файлу додається буква R;

-Output Log File - текстовий звіт про результати трасування (розширення файлу *.LOG). За умовчанням має ім'я вхідного файлу, але перед ім'ям файлу додається буква R.

Кнопка Load завантажує готовий файл стратегії. Кнопка Save зберігає вибраний файл стратегії для поточного проекту. Кнопка Set Base встановлює параметри стратегії і імена перерахованих вище трьох файлів за умовчанням.

Кнопка Layers викликає для перевірки або можливих змін діалогове вікно Options Layers.

Кнопка Net Attrs викликає діалогове вікно Edit Nets для перегляду і редагування атрибутів ланцюгів або редагування атрибутів.

Кнопка Via Style викликає діалогове вікно Options Via Style для перегляду і редагування стеків контактних майданчиків. Перехідні отвори, які завжди розташовуються у вузлах сітки трасування, для різних ланцюгів можна задавати за допомогою атрибуту VIASTYLE. Максимальний діаметр перехідного отвору обмежений двома кроками сітки трасування.

Після натиснення на кнопку Passes в діалоговому вікні Pass Selection простановкой відповідних прапорців вибираються типи проходів трасування.

Wide Line Routing - автотрасувальник проводить розводку в першу чергу широких ланцюгів, що мають атрибути AUTOROUTEWIDE і WIDTH. Розводка проводиться тільки в горизонтальному і вертикальному напрямах. Похилі траси проводяться уручну, і при подальшому запуску QuickBoute ширина таких трас трасувальником не змінюється.

Horizontal - трасування простих трас тільки горизонтальними лініями без перехідних отворів з мінімальними, відхиленнями від горизонтальної лінії.

Vertical - трасування простих трас тільки вертикальними лініями без перехідних отворів з мінімальними відхиленнями від вертикальної лінії.

"L" Routes ( 1 via) - формування фрагментів ланцюга, що мають два провідники (вертикальний і горизонтальний), що розташованих в двох різних шарах і сполучаються перехідним отвором. Така конфігурація має вид букви L з різною її орієнтацією. Провідники розміщуються на відстані не більше 100 mil (2,5 мм) від сторін прямокутника, вершини якого розташовані в центрі двох контактних майданчиків, що сполучаються трасою. Якщо протилежні шари плати мають орієнтацію траси відмінну від ортогональної, то даний прохід не використовується.

"Z" Routes (2 vias) - формування фрагментів ланцюга, що мають три провідники (вертикальні і горизонтальні), що розташованих в двох різних шарах і сполучаються двома перехідними отворами. Така конфігурація має вид букви Z з різною її орієнтацією. Провідники розміщуються на відстані не більше 100 mil (2,5 мм) від сторін прямокутника, вершини якого розташовані в центрі двох контактних майданчиків, що сполучаються трасою. Якщо протилежні шари платні мають орієнтацію траси відмінну від ортогональної, то даний прохід не використовується.

"С" Routes (2 vias) - формування фрагментів ланцюга, що мають три провідники (вертикальні і горизонтальні), що розташованих в двох різних шарах і сполучаються двома перехідними отворами. Така конфігурація має вид букви Із з різною її орієнтацією. Провідники розміщуються на відстані більш ніж 100 mil (2,5 мм) від сторін прямокутника, вершини якого розташовані в центрі двох контактних майданчиків, що сполучаються трасою.

Any Node (2 vias) - спроба трассировки.связи між двома контактними майданчиками з введенням не більше ніж двох перехідних отворів з метою виконання якнайповнішого трасування схеми. При цьому оптимізація (мінімізація) довжини траси, на відміну від попередніх проходів, не проводиться.

Maze Routes - оптимізуюче “лабіринтове” трасування, що не має обмежень на орієнтацію провідників на шарі. Немає обмежень і на число перехідних отворів. Максимальне число перехідних отворів для одного ланцюга встановлюється атрибутом MAXVIAS (за умовчанням число перехідних отворів для однієї. траси рівне 10).

Any Node (maze) – “лабіринтове” трасування без оптимізації довжини траси, з метою спроби проведення траси “за всяку ціну”.

Route Cleanup - використовується для поліпшення “зовнішнього вигляду” друкарської платні шляхом випрямлення вже проведених трас. Прохід використовується після завершення розводки всіх електричних ланцюгів.

Via Minimisazion - зменшує число перехідних отворів на розведеній платні.

У рядку Routing Grid вікна Route Autorouters визначається сітка трасування з чотирьох можливих значень кроків трасування: 25 mil, 20 mil, 16,7 -16,6 - 16,7 mil (для нерегулярної сітки) і 12,5 mil. Інші значення кроків трасування, включаючи і метричну систему одиниць, заборонені.

У рядку Line Width вибирається ширина всіх провідників. Мінімальне значення ширини - 0,1 mil (0,01 мм - в метричній системі). Максимальне значення ширини провідників обмежене вибраним кроком сітки трасування. Якщо необхідно задати ширину окремого провідника, то вона визначається при виконанні команди Edit/Nets завданням атрибуту WIDTH.

Область перемикача Error Messages дозволяє вивести повідомлення про помилки на екран монітора (Output to Screen), у файл діагностики (Output to Log File) або як у файл, так і на екран (Output to Both).

Команда Route/Info виводить поточну інформацію про хід трасування. Команда Route/Cancel припиняє процес трасування, а користувач повинен зробити вибір - тимчасово припинити трасування і запам'ятати проміжні результати (Stop Routing and Save), або припинити трасування без збереження результатів (Cancel Routing and do not save).

Після натиснення на кнопку Start процес розводки ланцюгів візуалізується на екрані, а в рядку станів виводяться повідомлення про хід трасування.

Після закінчення трасування у файлі-протоколі .LOG формується інформація про результати виконання окремих кроків трасування і підсумкові дані.

9.4      Обмеження для QuickRoute:

-Використовуються тільки прості контактні майданчики і перехідні отвори, що мають одну і ту ж форму на всіх шарах;

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

-Широкі ланцюги, що розводяться на проході Wide Line Routing, повинні мати атрибути VIASTYLE, WIDTH і AUTOROUTEWIDE. Значення ширини провідника і стилі перехідних отворів встановлюються різними для кожного широкого ланцюга;

-Діаметр перехідного отвору не повинен перевищувати подвійного розміру поточної сітки трасування;

-Метрична сітка трасування не вирішується, а дозволені сітки трасування можуть мати кроки 10 mil, 12,5 mil, 16,7-16,6-16,7 mil, 20 mil і 25 mil;

-Ширина провідника не повинна перевищувати половину кроку поточної сітки;

-Атрибут RIPUP трасувальником не підтримується;

-Атрибут MAXVIAS використовується тільки при розводці типу “лабіринт”;

-Для перехідних отворів спеціальну сітку створити не можна;

-Виведення компонентів дозволено повертати тільки на 90;

-Допускається не більше чотирьох шарів металізації.

Рисунок. 9.1 - Трасування друкованої плати

10        ТЕХНОЛОГІЧНИЙ КОНТРОЛЬ ПЕЧАТНОЇ ПЛАТИ

Після завершення розробки топології друкарської плати і перед формуванням даних для випуску фотошаблонів необхідно перевірити плату на відповідність принциповій схемі, правилам проектування і технологічним обмеженням, тобто тим правилам, які встановлені командою Options/Design Rules. Перевірка проводиться з використанням утиліти DRC (Design Rule Check). Запускається утиліта командою Utils/DRC.

Нижче приводяться опції правил перевірки друкарської платні:

-Netlist Compare - порівняння списку з'єднань поточної друкарської платні і відповідної їй принципової схеми;

-Clearence Violations - перевірка заданих зазорів;

-Text Violations - перевірка правил написання тексту;

-Netlist Violations - перевірка відповідності з'єднань поточної друкарської платні і початкового списку ланцюгів проекту;

-Width Violations - перевірка обмежень на задану ширину трас;

-Unrouted Nets - перевірка на наявність непроведених ланцюгів;

-Unconnected Pins - перевірка неприєднаних виводів;

-Net Length - перевірка обмежень на довжину ланцюгів;

-Silk Screen Violations - перевірка зазорів між контактними майданчиками або перехідними отворами в шарі шелкографії;

-Copper Pour Violations - перевірка правильності виконання зазорів в областях металізації в сигнальних шарах;

-Plane Violations - перевірка у внутрішніх шарах типу “земля” і “живлення” накладення областей металізації, неправильного під'єднування до ним контактних майданчиків, перехідних отворів, ізольованих областей металізації;

-Component Violations - перевірка помилок розміщення компонентів;

-Drilling Violations - перевірка правильності свердлення отворів для штирьових висновків, крізних і глухих перехідних отворів.

У області Report Options указуються наступні опції перевірок:

-View Report - виводить текст звіту на екран монітора.

-Summarize Ignored Errors - кількість ігнорованих помилок;

-Summarize Overriden Errors - кількість помилок, що перекриваються, виведення яких заборонене в закладці Miscellaneous діалогового вікна Options Display команди Options/Display.

У області Error Options використовуються опції:

-Annotate Errors - індикація помилок спеціальними маркерами;

-Clear All Overrides - видалення всіх маркерів помилок, що перекриваються.

Для даної схеми сгенеровано наступний файл:

NETLIST LENGTH VIOLATIONS:

0 warning(s) detected.

0 error(s) detected.

WIDTH VIOLATIONS:

0 warning(s) detected.

0 error(s) detected.

COPPER POUR VIOLATIONS:

0 warning(s) detected.

0 error(s) detected.

PLANE VIOLATIONS:

0 warning(s) detected.

0 error(s) detected.

COMPONENT VIOLATIONS:

0 warning(s) detected.

0 error(s) detected.

DRILL VIOLATIONS:

0 warning(s) detected.

0 error(s) detected.

Netlist:

Errors: 0

Warnings: 0

Ignored Errors: 0

Unrouted Nets:

Errors: 0

Warnings: 0

Ignored Errors: 0

Unconnected Pins:

Errors: 54

Warnings: 0

Ignored Errors: 0

Net Length:

Errors: 0

Warnings: 0

Ignored Errors: 0

Width:

Errors: 0

Warnings: 0

Ignored Errors: 0

Copper Pour:

Errors: 0

Warnings: 0

Ignored Errors: 0

Plane:

Errors: 0

Warnings: 0

Ignored Errors: 0

Component:

Errors: 0

Warnings: 0

Ignored Errors: 0

Drilling:

Errors: 0

Warnings: 0

Ignored Errors: 0

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

ВИСНОВОК

У курсовій роботі було спроєктовано друковану плату з застосуванням різноманітних алгоритмів для кожного етапу проектування.

Проектування включало в себе розміщення елементів на друкованій платі, компоновки, трасування сполучень ,розподілу по шарах.

Також було застосовано алгоритми оптимізації для етапів розміщення та компоновки, а для трасування використано 2 алгоритми (1 для багатошарового трасування та 1 загальний).

Курсовій роботі була використане спеціалізоване програмне забезпечення – системи автоматизації проектування PCAD, де було сформовано описи логічних елементів в схемі, була спроектована принципова електрична схема в редакторі PCAD Schematic та проведено трасування трасувальником QuickRoute.

В завершення був проведений технологічний контроль печатної плати з використанням утиліти DRC (Design Rule Check).