ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ДЛЯ ПРОЕКТИРОВАНИЯ СОЕДИНЕНИЙ НА МНОГОСЛОЙНЫХ ПЕЧАТНЫХ ПЛАТАХ

А.С. Шандриков

Витебский государственный колледж электротехники

ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ ДЛЯ ПРОЕКТИРОВАНИЯ СОЕДИНЕНИЙ НА МНОГОСЛОЙНЫХ ПЕЧАТНЫХ ПЛАТАХ

При проектировании радиоэлектронных средств часто применяют конструкции многослойных печатных плат (МПП), в которых не допускается применение дополнительных межслойных переходов (в частности, платы с открытыми контактными площадками). Тривиальное решением задачи расслоения для таких конструкций предусматривает проведение трассировки всех соединений, которые можно расположить на первом слое. Оставшиеся не проведёнными соединения трассируются во втором, третьем слое и т.д. Очевидно, что при таком подходе к решению задачи количество слоёв может получиться неоправданно большим и к тому же слои будут заполнены соединениями неравномерно. Избежать этих недостатков можно, если выполнять расслоение МПП с использованием системы автоматизированного проектирования. Для этого необходимо совокупность соединений МПП представить в виде математической модели. В работах [1-5] такая модель описывается в виде графа, вершинами которого являются печатные проводники, а рёбрами – пересечения между ними. Пересечение рассматривается как конфликт между проводниками, то есть невозможность проведения конфликтующих проводников в одном слое. В работах [1-5] приводятся также описания некоторых методов расслоения МПП. Наиболее простой метод расслоения МПП, который может быть автоматизирован, описан в [3].

В данной работе приводится описание достаточно простого оригинального метода расслоения МПП. В качестве исходных данных используется математическая модель соединений печатной платы, аналогичная описанной в [3], в которой каждому соединению сопоставлен прямолинейный отрезок.

Расслоение МПП осуществляется в следующей последовательности.

1. По математической модели соединений МПП построить матрицу пересечений соединений X. Элемент x_ij матрицы пересечений, расположенный на пересечении i-ой строки и j-го столбца, может принимать одно из двух значений: 0 – при отсутствии пересечения, 1 – при наличии пересечения.

2. Определить количество пересеченийρ(x_i) каждого отрезка.    

3. Выбрать отрезок с максимальным количеством пересечений. Этот отрезок будет начальным отрезком, назначенным на первый слой МПП. Если данному условию удовлетворяют несколько отрезков, то можно выбрать любой из них, но для автоматизированного решения данной задачи с использованием ЭВМ необходимо задать некоторый критерий выбора. Таким критерием в данной ситуации может служить индекс строки матрицы смежности, то есть выбор начального отрезка из нескольких отрезков с равным количеством пересечений может осуществляться по младшему (старшему) индексу матрицы пересечений.

4. Построить подмножество X_i, содержащее выбранный отрезок x_i и все непересекающиеся с ним отрезки.

5) Выявить в полученном подмножестве X_i выявить подмножества пересекающихся отрезков.

6) Объединить все выявленные подмножества пересекающихся отрезков в подмножество A.

7) Отрезки, входящие в состав полученного объединённого подмножества A, удалить из множества X_i.

8) Отрезки, оставшиеся в множестве X_i после удаления из него подмножества A, назначить в список S₁ соединений первого слоя многослойной печатной платы.

9) Поочерёдно проанализировать все отрезки подмножества A на наличие связей с отрезками списка S₁. Если будет выявлен хотя бы один отрезок, непересекающийся с отрезками из списка S₁, назначить его в этот список. В случае, когда более одного отрезка не имеют связей с отрезками из списка S₁, а назначить можно только один из них, то для назначения в список S₁ следует выбрать отрезок с большим количеством пересечений.

10) Из матрицы пересечений удалить строки и столбцы, соответствующие отрезкам сформированного списка S₁.

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

Если количество сигнальных слоёв задано изначально, то в результате описанных действий некоторые отрезки могут остаться нераспределёнными. В этом случае необходимо рассмотреть каждый такой отрезок и назначить его на тот слой, с отрезками которого он не будет иметь пересечений или количество пересечений будет минимальным. 

Описанный метод может быть проиллюстрирован следующим примером. На рис. 1 представлены 14 соединений, которые необходимо распределить по трём сигнальным слоям с минимальным количеством пересечений.

Решение

1. Построить матрицу пересечений X и подсчитать суммарное количество пересечений каждого отрезка.

2. Выбрать отрезок, имеющий максимальное количество пересечений и простроить подмножество, содержащее выбранный отрезок и все отрезки, с которыми он не пересекается. Таким отрезком является отрезок 10. Подмножество X₁₀ = {10, 4, 5, 6. 7, 8, 9, 11}.

3. В подмножестве X₁₀ были выявлены подмножества пересекающихся отрезков: X₄ = {4, 9}; X₅ = {5, 9}; X₉ = {9, 4, 5,7}.

4. Объединить подмножества пересекающихся отрезков.

A = X₄ U X₅ U X₇ U X₉ = {4, 5, 7, 9}.

5. Удалить отрезки подмножества A из подмножества X10. Оставшиеся отрезки подмножества X₁₀ назначить в список соединений первого слоя МПП:

S₁ = 10, 6, 8, 11.

6. Отыскать в подмножестве A отрезки, непересекающиеся с отрезками из спискаS₁ и назначить их в этот список. Получим:

S₁ = 4, 5, 6, 7, 8, 10, 11.

7. Удалить из матрицы соединений строки и столбцы, соответствующие отрезкам, вошедшим в список S₁.

8. Отрезки, у которых ρ_i = 0, автоматически назначить в список соединений второго слоя МПП:

S₂ = 1, 3, 9, 13.

9. Удалить из матрицы соединений строки и столбцы, соответствующие отрезкам, вошедшим в список S₂.

10. Оба отрезка, 2 и 12 пересекаются с отрезком 14, но не пересекаются между собой, поэтому они могут быть назначены на третий слой: S₃ = 2, 12.

11. Отрезок 14 может быть назначен либо на первый, либо на второй слой. На первом слое он пересекается с отрезком 10. Отрезок 10 нельзя переместить на второй слой, так как он будет иметь два пересечения: с отрезком 1 и с отрезком 3. На третьем слое отрезок 10 также будет иметь два пересечения: с отрезками 2 и 12.

На втором слое отрезок 14 пересекается с отрезком 13. Отрезок 13 можно переместить на третий слой, так как на третьем слое он не будет иметь пересечений, тогда отрезок 14 назначается на второй слой.

12. Учитывая целесообразность равномерного распределения соединений по слоям МПП можно некоторые отрезки переместить на третий слой, имеющий минимальное количество соединений. Например, отрезки 8 и 11 с первого, наиболее загруженного слоя можно переместить на третий слой. Окончательное распределение соединений:

S₁ = 4, 5, 6, 7, 10; S₂ = 1, 3, 9, 14; S₃ = 2, 8, 11, 12, 13.

Результат расслоения представлен на рис. 2-4.

Список использованных источников

1. Абрайтис, Л.Б. Автоматизация проектирования ЭВМ [Текст] : Автоматизированное техническое проектирование конструктивных узлов цифровых устройств / Л.Б. Абрайтис, Р.И. Шейнаускас, В.А. Жилявичюс ; под ред. Л.Б. Абрайтиса. – М. : Сов. радио, 1978. – 272 с. ; ил.

2. Автоматизация проектирования радиоэлектронных средств [Текст] : Учеб. пособие для вузов / О.В. Алексеев [и др.] ; под ред. О.В. Алексеева. – М. : Высш. шк. , 1987. – 479 с.

3. Конструирование и технология печатных плат [Текст] / А.Т. Жигалов [и др.] – М. : Высш. шк., 1973 – 216 с., ил.

4. Кофанов, Ю. Н. Автоматизация проектирования РЭС. Топологическое проектирование печатных плат. Версия 1.0 [Электрон. ресурс] :  электрон.  учеб.  пособие /  Ю.  Н.  Кофанов, А. В. Сарафанов, С. И. Трегубов. – Электрон. дан. (4 Мб). – Красноярск : ИПК СФУ, 2008. – (Компьютерные технологии в приборостроении : УМКД № 49-2007 / рук. творч. коллектива А. В. Сарафанов). – 1 электрон.  опт.  диск  (DVD).

5. Селютин, В.А. Машинное конструирование электронных устройств [Текст] / В.А. Селютин. – М. : Сов. радио , 1977. – 384 с. ; ил.