Xreferat.com » Рефераты по информатике и программированию » Проектування друкованих плат пристроїв комп’ютерних систем

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

VALIGN=TOP> 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



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


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


Метод Хейса здійснює пошук найкоротшого шляху в багатошаровому ДРП між двома заданими осередками 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

Рисунок. 9.1 - Трасування (шар 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






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


Таблиця 9.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),(
Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: