Материал: Lab 5 Z недод

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ федеральное государственное бюджетное образовательное учреждения высшего образования «УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

Радиотехнический факультет Кафедра «Проектирование и технология электронных средств»

Дисциплина: «Математическое обеспечение САПР»

Лабораторная работа №5:

«ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ

ТРАССИРОВКИ ПРОВОДНЫХ СОЕДИНЕНИЙ»

Работу выполнил: Проверил: Студент группы Рбд-31 профессор Зарипов Т.Р. Мактас М.Я.

Ульяновск

2021

Цель работы – исследовать эффективность алгоритмов трассировки проводных соединений методом «внавал»; освоить особенности алгоритмизации и программирования задачи трассировки проводов на ПЭВМ; приобрести навыки построения математических моделей проводных соединений, реализации и исследования их при решении задачи трассировки с применением САПР.

1. Алгоритмы трассировки проводов

Задача проектирования соединений, иначе трассировка соединений, возника-ет на последних этапах проектирования радиоэлектронных средств (РЭС) и является одной из наиболее сложных задач в общей проблеме автоматизации проектирования РЭС [1-5]. Связано это с многообразием способов конструк-торско-технологической реализации соединений, каждый из которых обусловливает использование специфических критериев оптимизации и ограни-чений при алгоритмическом решении этой задачи.

Проводной монтаж, несмотря на широкое применение печатного монтажа, занимает значительное место в современных РЭС. Он более прост, т. к. проводники изолированы друг от друга, не надо думать об ограничениях на пересечения проводов, поэтому достаточно минимизировать длину соединений. В серийном производстве проводные соединения используют в узлах, платах, субблоках, кассетах, блоках, рамах, шкафах.

В современных РЭС трассировку проводных соединений производят двумя способами [1-2]:

– по прямым, соединяющим отдельные выводы модулей (монтаж «внавал»);

– по ортогональным направлениям – с помощью жгутов.

Достоинство монтажа «внавал»: простота при выполнении и высокая помехоустойчивость, т. к. он позволяет сократить до минимума общую длину проводников и протяженность участков их параллельного прохождения.

Недостатки: при его исполнении высока вероятность появления ошибок, которые трудно обнаружить, и из-за высокой плотности монтажа этот способ обладает малой ремонтопригодностью.

При жгутовом монтаже проводники объединяются в жгуты (перевязанные прочной нитью проводники), которые укладываются в специальные каналы.

Достоинство жгутового монтажа: более технологичен, т. к. позволяет разделить операции вязки и распайки жгутов, а также упростить процесс контроля и устранения ошибок, допущенных при монтаже.

Недостатки: неприемлем при создании высокочастотной и чувствительной к электрическим помехам аппаратуре. Основные ограничения при проводном монтаже – количество проводников, которые можно подсоединить к одному выводу (обычно не более трех) и число проводов в каждом жгуте.

Теоретически к одному выводу может быть подсоединено не более шести проводников. Это легко понять из чертежа, представленного на рис.1. Допустим, точки a₁, a₂, …, a_n удалены от точки О на расстояние R. Тогда можно считать, что эти точки расположены на окружности с радиусом R (рис.1, а). Из геометрии известно, что в круг вписывается правильный шестиугольник со стороной, равной радиусу круга (рис.1, б). Очевидно, что в данном случае минимальное дерево в вершинах O, a₁, a₂, a₃, a₄, a₅, a₆ только шестиугольника имеет суммарную длину ребер, равную 6R (рис.1, в, г). Причем максимальную локальную степень ρ = 6 будет иметь вершина O в звездном варианте такого дерева (рис.1, в). Любая дополнительная вершина a₇ на расстоянии R от вершины O будет уже ближе к одной из точек a_i (рис.1, д, е). Поэтому ρ_max = 6.

1. Математическая формулировка задачи

В общем виде задача формулируется следующим образом [2]. В системе координат XYZ, связанной с коммутационным пространством модуля, задано местоположение множества выводов . Это множество M разобьем в соответствии с электрической схемой соединений на непере-секающиеся подмножества M⁽¹⁾, M⁽²⁾,…,M^(k), каждое из которых включает в себя выводы, подлежащие электрическому объединению. Для каждого подмножества , i = 1, 2, …, k требуется определить последовательность соединений выводов и конфигурацию проводников, обеспечивающих при заданных ограничениях минимальную суммарную длину соединений.

Практически задача сводится к отысканию дерева с минимальной суммарной длиной ребер (построению кратчайшей связывающей сети). Согласно теореме Кэли на n вершинах может быть построено t = n^(n-2) деревьев. Поэтому при большом числе выводов в электрической цепи эта задача становится сложной.

Для определения минимального дерева на заданных n вершинах можно построить все возможные деревья и выбрать минимальное из них. Однако в РЭC число цепей исчисляется сотнями, поэтому поиск всех деревьев практи-чески нереален. К тому же существующие алгоритмы построения минимальных деревьев позволяют находить глобально-оптимальные или близкие к ним решения (при отсутствии ограничений на количество проводников, подсоединяемых к одному выводу). Поэтому эта задача является одной из немногих задач теории графов, которые считают полностью решенными [8]. Рассмотрим используемые в САПР алгоритмы Дж. Краскала и Р. К. Прима.

2. Алгоритм Краскала

Алгоритм Краскала реализует следующую процедуру [1, 2, 9].

Множество контактов n электрической цепи моделируют n вершин графа. На них строится полный граф. Число ребер в полном графе r = [n (n-1) / 2]. Из списка ребер полного графа последовательно выбираются самые короткие ребра до тех пор, пока не получится дерево.

Особенностью этого алгоритма является возможность параллельного образования нескольких поддеревьев, которые затем объединяются в единое дерево – остов.

При этом очередное выбранное ребро включается в список выбранных ре-бер в том случае, если оно не инцидентно сразу двум вершинам любого из уже построенных ранее фрагментов. Иначе ребро исключается, поскольку при его добавлении к фрагменту образовался бы простой цикл. Процедура выбора ре-бер продолжается до тех пор, пока в списке ребер дерева не окажется ровно

( n – 1 ) ребер.

Выбор ребра минимальной длины сводится к поиску минимального эле-мента в одной из половинок матрицы расстояний с последующим присвоением этому элементу значения, превышающего все остальные элемен-ты (например, ) для исключения повторного его выбора. Если при построе-нии дерева в полном графе оказывается несколько рёбер одинаковой минималь-ной длины, то для нахождения глобально-оптимального решения необходимо построить деревья с каждым из таких ребер и выбрать минимальное из них.

Проверка ребра на образование цикла выполняется с помощью таблицы меток вершин N_i, где i = 1, 2, …, n. В начале работы алгоритма в этой таблице все вершины имеют разные метки (например, свой номер N_i = i). Если две изолированные i и j вершины объединяются во фрагмент, то происходит поглощение меток: N_i присваивается значение N_j или наоборот. Аналогично обстоит дело и при образовании более сложных фрагментов: если два фраг-мента объединяются ребром r_ij в один, то все метки вершин получают одинако-вое значение N_i, обычно минимальное из сравниваемых. По таблице меток легко проверить, образует ли очередное выбранное ребро цикл или нет: цикл образуется в том случае, если соединяемые вершины имеют одинаковые метки.

Алгоритм позволяет строить дерево и с ограничениями на степени вершин, однако в этом случае получение минимального дерева не гарантируется.

Рис. 5.1.

Если локальные степени вершин не должны превышать двух, то задача построения минимального дерева сводится к задаче построения гамильтоновой цепи минимальной длины: пройти по всем вершинам графа, но не возвращаться в исходную вершину [6 – 9].

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

Алгоритм

1. На множестве вершин (выводов) M⁽ⁱ⁾ построить взвешенный полный граф (число ребер в нем n(n-1)/2 ). Для этого вычислить элементы матрицы расстояний по одной из формул:

или (5.1)

, (5.2)

где и – координаты i-й и j-й позиций монтажного пространства.

Формулой (5.1) пользуются для монтажа «внавал», а формулой (5.2) – при жгутовом монтаже.

2. Всем элементам, лежащим на главной диагонали и ниже её, присваивается значение . Присвоить нулевое значение длине L рёбер искомого дерева: L = 0; i = 0; j = 0.

3. Сформировать таблицу меток и локальных степеней вершин: ; ; ; ; .

4. Присвоить .

5. Найти минимальный элемент матрицы .

6. Если , то идти к 4.

7. Если или , то идти к 4.

8. Поглощение меток: все метки нового фрагмента получают значение , а локальные степени соединенных вершин – и .

9. Включить ребро во множество R ребер минимального дерева, а длину дерева увеличить на длину ребра: .

10. Если , то идти к 4, в противном случае к 11.

11. Минимальное дерево построено. R – множество его ребер, а L – суммарная их длина.

Конец.