5) Повторяем пункты 3-4 пока все точки не будут соеденены (все столбцы ‘вычеркнуты’).
Проведём трассировку методом Примма ‘корпусной’ цепи питания.
В качестве стартовой берём точку 1 и ‘вычёркиваем’ столбец 1. Локальную степень вершины принимаем равной 4. Самая короткая связь по матрице расстояний у неё с тчк. 2. Проводим связь. Рассматриваем две строки – 1-ю и 2-ю. Самая короткая связь между 1 и 8, между которыми и проводится следующая связь. ‘Вычёркивается’ столбец 2. Теперь рассматриваем три строки – 1-ю, 2-ю, и 8-ю. Наименьшее расстояние имеется между 8 и 3, 8 и 9. Проводим эти связи ‘вычёркивая’ соотв. столбцы. И т.д.
Повторяем до тех пор, пока все точки не будут соеденены (т.е. все столбцы матрицы смежности будут ‘вычеркнуты’).
Полученый результат виден на рис. 3.1.
3.2 Трассировка по алгоритму Краскала
Алгоритм Краскала заключается в следующей последовательности:
1) Выписываем все возможные рёбра.
2) Упорядочиваем получившийся список рёбер по длинне.
3) Проводим связь первого ребра из списка.
4) Из списка рёбер выбираем следующее по очереди ребро.
5) Если обе вершины выбраного ребра уже есть в списке проведённых ребер, вычёркиваем это ребро из списка и возвращаемся к п. 4.
Если же одна (и только одна!) из вершин выбраного ребра уже участвует в связи (присутствует как вершина в списке проведённых рёбер), то проводим это ребро, иначе возвращаемся к п. 4.
6) Повторяем пункты 4-5 до тех пор, пока список рёбер не опустеет.
Проведём трассировку цепи питания +5В.
Выпишем список всех возможных рёбер, сразу откидывая ребро, если в списке уже есть ребро с такими же вершинами.
1-2 1-3 1-4 1-5 1-6 1-7 1-8 1-9 1-10 1-11 1-12 1-13 1-14
2-3 2-4 2-5 2-6 2-7 2-8 2-9 2-10 2-11 2-12 2-13 2-14
3-4 3-5 3-6 3-7 3-8 3-9 3-10 3-11 3-12 3-13 3-14
4-5 4-6 4-7 4-8 4-9 4-10 4-11 4-12 4-13 4-14
5-6 5-7 5-8 5-9 5-10 5-11 5-12 5-13 5-14
6-7 6-8 6-9 6-10 6-11 6-12 6-13 6-14
7-8 7-9 7-10 7-11 7-12 7-13 7-14
8-9 8-10 8-11 8-12 8-13 8-14
9-10 9-11 9-12 9-13 9-14
10-11 10-12 10-13 10-14
11-12 11-13 11-14
12-13 12-14
13-14
Упорядочим этот список в порядке увеличения длинны рёбер. Полученый список запишем построчно:
5-6 6-11 11-12 4-7 7-10 10-13 3-8 8-9 9-14 1-2 2-3 3-4 4-5
7-8 6-7 9-10 10-11 12-13 13-14 5-11 6-12 4-7 7-13 3-9 8-14 2-4
3-5 6-8 9-11 12-14 1-8 1-9 1-14 3-7 5-7 4-6 4-8 6-10 7-11
9-7 8-10 11-13 10-12 10-14 9-13 2-8 2-7 3-6 5-8 8-11 6-9 9-12
11-14 5-10 6-13 4-9 7-14 7-12 4-11 3-10 8-13 2-9 2-14 3-13 4-14
4-12 5-13 1-4 1-7 1-10 1-13 1-5 1-6 2-13 3-11 5-9 8-12 6-14
2-5 2-6 2-11 3-12 5-14 2-12
Проводим первую связь 5-6. Следующее ребро имеющее общую точку – 6-11. Проводим и его. Проводим следующее ребро 11-12.
Следующее проведённое нами ребро 4-5, затем 4-7, 7-10 и 10-13. Теперь 3-4 и 3-8, 8-9 и 9-14.
Затем проводим рёбро 2-3 и наконец 1-8.
Цепь разведена, поскольку все возможные вершины уже присутствуют в списке проведённых рёбер. Рисунок проведённых дорожек приведёна на рис.3.2.
| Å | 5 | Å | Å | 6 | Å | Å | 11 | Å | Å | 12 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | DD10 | Å | Å | DD11 | Å | Å | DD13 | Å | Å | DD12 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | 4 | Å | Å | 7 | Å | Å | 10 | Å | Å | 13 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | DD9 | Å | Å | DD8 | Å | Å | DD6 | Å | Å | DD7 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | 3 | Å | Å | 8 | Å | Å | 9 | Å | Å | 14 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | DD5 | Å | Å | DD2 | Å | Å | DD3 | Å | Å | DD4 | Å | ||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | ||||||||
| Å | 2 | Å | |||||||||||||
| Å | Å | ||||||||||||||
| Å | Å | ||||||||||||||
| Å | DD1 | Å | |||||||||||||
| Å | Å | ||||||||||||||
| Å | Å | ||||||||||||||
| Å | Å | ||||||||||||||
| Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | Å | ||
3.3 Трассировка классическим волновым алгоритмом Ли
Проведем печатный проводник, соединяющий DD11 (вывод 6), DD13 (вывод 4) на стороне монтажа печатной платы. Для этого вычерчиваем часть монтажного поля, содержащую ИМС DD11 и DD13 (рис.3.1).
| 12 | 11 | 10 | 9 | 10 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 11 | 10 | 9 | 8 | 9 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 |
| 10 | 9 | 8 | 7 | 8 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 9 | 8 | 7 | 6 | Å | 6 | 7 | Å | 11 | 12 | 13 | 14 | 15 | Å | 17 | 18 | Å | 20 | 21 | 22 |
| 8 | 7 | 6 | 5 | Å | 5 | 6 | Å | 12 | 13 | 14 | 15 | 16 | Å | 18 | 19 | Å | 21 | 22 | 23 |
| 7 | 6 | 5 | 4 | Å | 4 | 5 | Å | 13 | 14 | 15 | 16 | 17 | Å | 19 | 20 | Å | 22 | 23 | 24 |
| 6 | 5 | 4 | 3 | Å | 3 | 4 | Å | 14 | 15 | 16 | 17 | 18 | Å | 20 | 21 | Å | 23 | 24 | 25 |
| 5 | 4 | 3 | 2 | Å | 2 | 3 | Å | 15 | 16 | 17 | 18 | 19 | Å | 21 | 22 | Å | 24 | 25 | 26 |
| 4 | 3 | 2 | 1 | Å | 1 | 2 | Å | 16 | 17 | 18 | 19 | 20 | Å | 22 | 23 | Å | 25 | 26 | 27 |
| 5 | 4 | 3 | 2 | Å | 2 | 3 | Å | 17 | 18 | 19 | 20 | 21 | Å | 23 | 24 | Å | 26 | 27 | 28 |
Наименьшая ‘длинна’ волны подходящей к выводу 4 DD13 составляет 18. Именно по этому пути и проложим проводник соеденяющий выводы 6 и 4 DD11 и DD13 соотв.
Можно наметить перспективы развития конструирования и технологии производства ЭВА и РЭС. Естественно ожидать совершенствование уже известных и появление принципиально новых методов. Их реализация будет осуществляться с помощью ЭВМ, поскольку использование ЭВМ позволяет значительно уменьшить время на разработку конструкций любой сложности, а также повысить качество и снизить цену. Уже сейчас существуют программы (PCAD, AccelEDA, ORCAD и др.), с помощью которых успешно решаются задачи по проектированию печатных плат.
— 16 —
1. Б.Н.Деньдобренко, А.С.Малика «Автоматизация конструирования РЭА. Учебник для ВУЗов». — М.: Высшая школа, 1980.
2. «Конструирование и технология печатных плат. Учеб. пособие для ВУЗов». Под ред. А.Т.Жигалова. — М.: Высшая школа,1973.
3. А.А.Яншин «Теоретические основы конструирования, технологии и надежности ЭВА. Учеб. пособие для ВУЗов». — М.: Радио и связь, 1983.
4. «Системы автоматизированного проектирования в радиоэлектронике. Справочник». Под ред. И.П.Норенкова. — М.: Радио и связь, 1986.
5. М.И.Богданович, И.Н.Грель, В.А.Прохоренко, В.В.Шалимо «Цифровые интегральные микросхемы. Справочник». — Мн.: Беларусь, 1991.
6. «Печатные платы в конструкциях РЭС. Учеб. пособие по курсу «Конструирование радиоэлектронных устройств» для студентов специальности «Проектирование и производство РЭС» /Под ред. Ж.С.Воробьевой, Н.С.Образцова. — Мн.: БГУИР, 1999.