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

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