Содержание к диссертации
Введение
1. Обзор задач моделирования печатных цепей 11
1.1. Использование моделирования печатных плат для диагностики межсоединений 11
1.2. Контроль электромагнитной обстановки в бортовой космической аппаратуре 14
1.3. Актуальность моделирования печатных цепей с помощью графов и разработки алгоритмов разбиения поверхностей для численного метода моментов 21
1.4. Обзор алгоритмов для моделирования печатных цепей 23
1.5. Обзор алгоритмов разбиения поверхностей на ортогональные прямоугольники для численного метода моментов 31
1.6. Обзор инструментария и комплексов программ 38
1.7. Постановка задач исследования 41
2. Методика моделирования цепей печатных плат с помощью графов 46
2.1. Формулировка задачи моделирования 46
2.2. Построение модели печатной цепи 53
2.3. Алгоритм получения сжатого гомеоморфного графа 57
2.4. Тестирование моделей 60
2.5. Генерация принципиальной схемы 66
2.6. Основные выводы и результаты главы 75
3. Алгоритмы аппроксимации переходных отверстий и полигонов для численного метода моментов 76
3.1. Переходные отверстия 77
3.2. Многоугольник с круглыми вырезами 92
3.3. Тестирование алгоритмов 98
3.4. Основные выводы и результаты главы 104
4. Программы и алгоритмы для квазистатического анализа 106
4.1. Программа для метода моделирования печатных цепей с помощью графов 106
4.2. Программа для моделирования переходных отверстий и полигонов 108
4.3. Программа для создания DHTML-диалогов 114
4.4. Программа для быстрого преобразования Фурье на графическом процессоре 116
4.5. Программа для построения графиков 118
4.6. Программа, реализующая интерпретатор для вычисления математических выражений 120
4.7. Алгоритмы аппроксимации набора данных 122
4.8. Использование результатов работы 134
4.9. Основные выводы и результаты главы 145
Заключение 147
Литература 148
- Актуальность моделирования печатных цепей с помощью графов и разработки алгоритмов разбиения поверхностей для численного метода моментов
- Алгоритм получения сжатого гомеоморфного графа
- Многоугольник с круглыми вырезами
- Программа для создания DHTML-диалогов
Актуальность моделирования печатных цепей с помощью графов и разработки алгоритмов разбиения поверхностей для численного метода моментов
Геометрическое моделирование [4] - это направление в математике, в котором изучается построение кривых линий, тел и поверхностей. В печатных платах проводники представлены параллелепипедами, переходные отверстия - системой цилиндров и колец, полигоны - выпуклыми многогранниками [5]. Построенные геометрические модели реальных печатных плат позволяют осуществить отображение платы и её дальнейший анализ. Совершенствование геометрического моделирования элементов печатных плат бывает обусловлено спецификой последующего анализа. Например, для частного случая трехмерного квазистатического анализа методом моментов, когда подобласти трехмерных конфигураций могут быть по форме только прямоугольными, а по ориентации - только ортогональными осям декартовых координат, можно вычислить элементы матрицы СЛАУ по аналитическим формулам [6].
Для дальнейшего анализа печатных плат (на основе геометрической модели) необходимо использование ряда известных и разработка ряда новых алгоритмов. Одним из главных инструментов при анализе печатных плат являются алгоритмы и структуры данных из теории графов, поскольку с их помощью можно установить однозначное соответствие цепи и графа. Теория графов -это раздел дискретной математики, в котором изучаются свойства графов, где граф - это совокупность вершин, соединенных ребрами [7]. Поскольку печатные трассы представляют собой отрезки, а соединения - узлы, то полученная геометрическая модель печатной платы может быть представлена в виде графовой модели. Эта модель позволяет преобразовать геометрию печатной платы в принципиальную схему с учетом геометрических и электрических параметров.
Для построения геометрических моделей необходимо разработать систему моделирования [8], для квазистатического анализа надо применить теорию графов для создания структуры данных, с помощью которой будет осуществляться создание графовой модели на основе геометрической для генерации принципиальной схемы. В итоге получим систему компьютерного моделирования с возможностью построения геометрической модели печатной платы и генерацией принципиальной схемы для квазистатического анализа.
Рассмотрим некоторые отечественные системы компьютерного моделирова 22 ния, пригодные для проектирования [9, 10] с учетом ЭМС. ELCUT [11] - это комплекс программ, предназначенный для моделирования электромагнитных, тепловых и механических задач методом конечных элементов. Модуль электростатики позволяет вычислять ёмкости различных структур. В данном модуле поверхность элементов автоматически разбивается на треугольники.
АСОНИКА [12] - комплекс программ, предназначенный для моделирования надежности и качества аппаратуры.
TALGAT [13-15] - комплекс программ, предназначенный для квазистатического анализа двумерных и трёхмерных структур, электродинамического анализа трёхмерных структур и структурно-параметрической оптимизации.
Из таблицы 1.1 видно, что отечественные системы компьютерного моделирования не включают в себя многие возможности анализа, которые удобны для проектирования с учетом электромагнитной совместимости (ЭМС). Сложившуюся проблему можно решить двумя способами: использовать несколько дешевых аналогов, каждый из которых обладает частью необходимого функционала, или доработать одну из существующих систем компьютерного моделирования. Преимущество первого подхода заключается в том, что необходимый инструментарий можно получить безотлагательно, заплатив за несколько лицензий. Однако, за продление лицензий нужно будет платить определенный период. Также нет гарантии дальнейшего развития полученного инструментария. Преимущество второго подхода заключается в том, что самостоятельно разработанное программное обеспечение включает в себя все нужные возможности, а при необходимости можно добавлять новые. Потенциально, за счет использования новых технологий и научных подходов, самостоятельно разрабатываемое специализированное приложение может стать лучше существующих аналогов. В таблице 1.1 показано самостоятельно разрабатываемое программное обеспечение TALGAT до выполнения диссертационной работы. Подробный обзор зарубежных систем моделирования представлен в работе [16].
Известны исследования по автоматизированному составлению электрической схемы для корпуса ИС [17], а также СБИС [18, 19]. Однако для печатных плат этот вопрос мало исследован.
Геометрически печатные трассы представляют собой отрезки на плоскости, соединенные точками (места соединения печатных трасс). Обычно каждая из печатных трасс принадлежит какой-либо цепи. Все печатные трассы, которые входят в одну цепь, соединены между собой. В задачах анализа печатных плат иногда требуется выделить лишь одну цепь с целью вычислить отклик. Для этого надо построить её принципиальную схему. Для определения структуры схемы и длины каждого отрезка, необходимо создать серию сечений для каждой печатной трассы, исключая при этом одинаковые сечения. Печатные трассы в сечениях геометрически представляют собой прямоугольники, которые расположены на различных уровнях в пределах прямоугольной области. Эта область ограничена по высоте толщиной печатной платы (ПП), по ширине - заданной шириной рассекаемой ПП.
Для эффективного решения задач анализа печатных трасс целесообразно использовать графовые структуры данных. В частности, для печатных плат подходят ацикличные графы, которые также называются деревьями [20]. Можно построить граф, который будет однозначно соответствовать какой-либо цепи в печатной плате. После этого к графу можно применять множество эффективных алгоритмов из теории графов.
После изготовления печатных плат необходимо проводить тестирование с целью обнаружения разрывов в соединениях и печатных трассах. Для этого используется роботизированный манипулятор с двумя щупами. Задача состоит в том, чтобы проверить все печатные трассы и соединения за минимальное количество движений робота. В терминах теории графов цель состоит в том, чтобы посетить весь набор вершин в порядке, который минимизирует расстояние и время обхода. Эту цель можно достигнуть, используя алгоритмы решения известной задачи коммивояжёра (поиск оптимального пути). Однако этот алгоритм не учитывает техническую часть, а именно сбалансированность нагрузки на щупы. Таким образом, для этого нужно решать задачу разбиения графа на подграфы, каждый из которых представляет меньшую область на печатной плате, после чего нужно определить связность внутри каждой области. Для определения связности двух подграфов достаточно взять две любые вершины из подграфов и проверить их. Для того, чтобы эффективно разбить граф на подграфы, можно применить алгоритмы поиска минимального остовного дерева, а в качестве веса ребер использовать расстояние между точками, время разгона, движения и замедления щупа. Такой подход обеспечил компании Integriest сокращение дистанции маршрута щупов на 30% по сравнению с первоначальным алгоритмом [21].
Алгоритм получения сжатого гомеоморфного графа
Мощности множеств V{ ограничены количеством проводников, проходящих в соответствующих множествам поперечных сечениях, где г =1... п. Таким образом, количество вершин в множествах может быть равно 1, так как, по крайней мере один проводник проходит сквозь поперечное сечение, и максимум может содержать w/t-m, где w - ширина поперечного сечения, t - ширина проводника, проходящего через поперечное сечение, т - количество слоев в плате. Общее количество множеств V{ в итоговой модели определяется количеством разных геометрических конфигураций поперечных сечений вдоль выбранной печатной цепи. Мощности множеств Е{ ограничены диапазоном l-min(V _i, V +i).
Цепь печатной платы - это множество прямых отрезков SG = {Li 1 і m}, соединенных между собой концами, где т - количество простых отрезков в цепи, L = (x,y,Xi,yi,w,t) - кортеж;, состоящий из компонентов, которые описывают координаты начала и конца отрезка, а также его толщину и ширину. Каждый отрезок цепи имеет уникальный идентификатор id.
Поперечные сечения делаются перпендикулярно отрезкам печатной цепи и представляет собой множество SC = {ТІ 1 і п}, элементы которого описывают пересекаемые отрезки, гдеп - количество отрезков, которые пересекает поперечное сечение, Т = (id,i,x,y,t,w) - кортеж;, который описывает сечение одного отрезка в поперечном сечении, где id - уникальный идентификатор отрезка, і - номер слоя, ж, у - координаты левого нижнего угла сечения отрезка в поперечном сечении, t - толщина проводника, w - ширина проводника.
Таким образом, печатная цепь представляется множеством упорядоченных поперечных сечений SSC = {Pi 0 і N}, где N - количество всех поперечных сечений, Р = (j, d, SC) - кортеж;, который состоит из компонентов j -номер отрезка цепи, d - расстояние от начала j -ro отрезка, SC - множество элементов поперечного сечения.
Поскольку объектов математического моделирования множество и между ними существуют связи, то для отображения этих связей удобно использовать графы. Зададим общий граф G = (У, Е), где V - множество вершин, Е - множество ребер. Каждая вершина соответствуют сечению отрезка в отдельности. Поэтому, чтобы отделить вершины различных поперечных сечений, будем использовать множества V{, где 1 і \SSC\. При этом существует биективная функция / : V{ -о- Т между множествами V{ и Т, где Т ЄР{. Таким образом, множество всех вершин V и ребер Е определяется как
Рассмотрим пример моделирования печатной цепи (однослойной печатной платы), представленной на рис. 2.7, где вертикальными линиями показаны места поперечных сечений, а печатные трассы оканчиваются круглыми контактными площадками. подмножествами существуют ребра. Граф является ориентированным, все компоненты связности топологически отсортированы.
Сначала каждому из множеств добавляется фиктивная вершина, которая смежна всем вершинам соответствующего множества, при этом добавляемые ребра не ориентированны. Левая фиктивная вершина называется источником s, а правая стоком t. Далее запускается алгоритм поиска максимального потока для нахождения величины f(s,t). Если f(s,t) = Vi и f(s,t) = Vi+i, то выполняется сжатие смежных вершин (vertex contraction) в одну, в результате из двух множеств остается только одно.
На рис. 2.10 в первом случае поток равен 3, а мощность первого множества 4, значит сжатие не будет произведено. Во втором случае поток равен 2, а мощность обоих множеств равна 3. В третьем величина потока равна мощности обоих множеств, значит необходимо выполнить сжатие смежных нефиктивных вершин. Поскольку такое сжатие не нарушает изоморфности (graph isomorphism) разбиений исходного и полученного графов, а удаляемые вершины не разветвляются, то граф G и сжатый G являются гомеоморфными (graph homeomorphism). Однако гомеоморфизм графов выполняется только до тех пор, пока соседние множества вершин Vi сжаты минимум до двух равных по мощности соседних множеств, а величина потока между соседними множествами совпадает с мощностью множеств. Полученный граф является го-меоморфным только без учета фиктивных вершин, необходимых для поиска величин потока между множествами V{.
Таким образом, задача заключается в том, чтобы найти сжатый гомеоморф-ный граф G для исходного графа G. При этом сжатие осуществляется только между соседними подмножествами V{.
Для моделирования электрофизических явлений в печатной цепи необходимо построить принципиальную схему. Все линии передачи должны соответствовать группе одинаковых соседних поперечных сечений, для блока линий передачи задаются погонные электрические параметры, а также длина линии передачи. Поскольку поперечных сечений много, то нужно исключить одинаковые поперечные сечения и увеличить длину линии передачи на соответствующие значения удаленных поперечных сечений. Используя математическую модель, необходимо получить данные, с помощью которых можно построить принципиальную схему.
Решение поставленной математической задачи рассмотрим на примере рис. 2.7 с ориентированным графом G из рис. 2.8. На основе G построим граф смешанного типа GM = (G, U,A), где U - множество фиктивных вершин, добавленных к каждому подмножеству Vi, А - множество неориентированных ребер, которые соединяют фиктивные вершины с соответствующими вершинами множеств V{ (рис. 2.11), а вершины V{ соединены между собой ориентированными ребрами.
В этом алгоритме: Q - структура данных типа дек [58], которая позволяет брать первое значение (front), удалять его (popfront) и вставлять в конец очереди (pushback); WHILE - оператор, позволяющий выполнять блок инструкций, пока выполняется условие; IF, THEN и ELSE - условные операторы; getFlow(s,t) - функция, которая находит величину максимального потока (па-росочетание [59]) между истоком s и стоком t. Необходимо заметить, что, так как поиск потока происходит в графах, которые относятся к двудольным, то можно использовать алгоритм Куна для нахождения максимального паросоче-тания в двудольном графе. Поскольку ребра между долями графа ориентированы, то алгоритм будет работать за линейное время 0(У).
Многоугольник с круглыми вырезами
Вывод прямоугольных подобластей осуществляется с помощью алгоритма, который представлен в виде блок-схемы на рис. 3.15. Данный алгоритм определяет, в какую плоскость необходимо вставить прямоугольник
К фигуре, состоящей из цилиндров, также относятся и многоугольники с круглыми вырезами. Например, полигон печатной платы состоит из двух многоугольников, соединенных вместе цилиндрами. Рассмотрим алгоритм, который позволяет аппроксимировать многоугольник с круглыми вырезами набором ортогональных прямоугольников, которые в итоге составляют поверхность фигуры. Для моделирования переходного отверстия с полигонами необходим алгоритм аппроксимации многоугольника с круглыми вырезами. Рассмотрим операции алгоритма, который позволяет разбивать многоугольник с круглыми вырезами на прямоугольные подобласти. Пусть S = {si,...,sn} - множество прямоугольников, на которые разбивается поверхность полигона, где Si = х,у,Х\,уі , где ж, у - координаты левого нижнего угла прямоугольника и х\, у\ - координаты правого верхнего угла. Введем две операции над элементами этого множества: DELETE(sx) и ADD(sx). Первая удаляет элемент sx из множества, вторая - добавляет. Если множество S реализовано на списках [47, 62], то операция DELETE будет выполняется заО(1), поскольку для удаления не нужно выполнять других операций. Операция ADD в тривиальной реализации будет работать за 0(п), так как для добавления необходимо, чтобы добавляемый прямоугольник sx геометрически не пересекался с уже имеющимися элементами множества. Пусть sxf]sy j 0, если имеется пересечение прямоугольников sx и sy. Таким образом, чтобы добавить новый элемент sx в множество, нужно, чтобы sxf]si т 0, SieS, і = 1...n, n = \S\. Также введем операцию GETNEWS(sx, sy) (рис. 3.18), которая возвращает новые прямоугольники (если sxf]sy т 0), на основе пересечения двух sx и sy. Таким образом, GETNEWS возвращает от 1 до 4 новых прямоугольников, которые не будут пересекаться с sy, но являются частью sx. Также пусть имеется множество V = {г і,..., г т}, определяющее радиусы и координаты центра переходных отверстий Vi = т,х,у . Доступ к элементам множества показан в алгоритме символом «.». Также используются операторы: FOR - выполнение итераций, IF - выполнение условия. Рассмотрим общий алгоритм.
Построение угловых прямоугольников с использованием части алгоритма (который генерирует точки на окружности) геометрического моделирования переходного отверстия.
Построение переходных отверстий с вертикальными боковыми стенками на слое полигона (переходные отверстия, не соединенные с полигоном) и без стенок (переходные отверстия, соединенные с полигоном).
Блок-схема вышеописанного алгоритма представлена на рис. 3.16. Операция DELETE заменена эквивалентным символом «\», обозначающим удаление элемента из множества. Операция ADD заменена эквивалентным символом «U», обозначающим объединение множеств. (Начало)
Алгоритм GETNEWS для составления новых прямоугольников на основе двух пересечений Диагоналями показаны новые прямоугольники, полученные на основе пересечения sx и Sy. В результате выполнения алгоритма получается полигон, аппроксимированный прямоугольными подобластями ряд примеров аппроксимации показан на рис. 3.19, а. Например, на рис. 3.19, а показан вид сверху реальной печатной платы, для которой проводились измерения. Плата состоит из пяти переходных отверстий, четыре из которых соединены с полигоном, их аппроксимация выполняется с помощью алгоритма аппроксимации цилиндрической фигуры. Центральное переходное отверстие соединено с микроплоском, который находится на другом слое печатной платы.
В первых пяти строках загружаются необходимые для моделирования модули. После задаются массивы х и у для построения графика. Далее в цикле задается число подынтервалов на поверхностях и командой CYLINDER_RING_ER2_XY генерируется описание переходного отверстия. В следующих строках вычисляется емкость переходного отверстия, после чего данные заносятся в массив. На основе полученных данных построен график (рис. 3.21) зависимости ёмкости от точности аппроксимации переходного отверстия. В этом примере изменение ёмкости для і от 3 до 4 составляет около 2%, а дальше быстро уменьшается. 35,5
Выбор сегментации позволяет сократить порядок матрицы, сохраняя при этом приемлемую точность вычислений. При более частой сегментации возрастает порядок матрицы СЛАУ, полностью описывающей проводники и диэлектрики структуры.
Эксперимент 2. Чтобы верифицировать алгоритм моделирования системы колец и цилиндров, выполнено сравнение результатов моделирования с результатами измерений [64]. В качестве параметра для сравнения использовалась ёмкость между сигнальным и опорным проводниками специально изготовленной для этого печатной платы (рис. 3.23, а). Она содержит две симметричные печатные структуры, являющиеся посадочными местами для соединителей типа SMA. Поэтому каждая печатная структура содержит пять переходных отверстий, в которые устанавливается соединитель SMA. Центральное переходное отверстие является сигнальным, и от него по верхнему слою платы отходит трасса. На нижней стороне платы расположен сплошной слой земли. Поэтому на нижней стороне платы четыре внешних переходных отверстия соединены с землей. Модель описанной печатной структуры с грубой аппроксимацией проводников показана на рис. 3.23, б. Диэлектрик моделировался упрощенно: горизонтальной границей на высоте 10 мкм над контактными площадками с относительной диэлектрической проницаемостью под ней 4,8.
Программа для создания DHTML-диалогов
Получение аналитических моделей для стеков ПП. Для получения моделей по параметрам стеков ПП рассчитаны значения погонной задержки г для всех сочетаний параметров каждого стека. (Сегментация: 50 мкм для диэлектрических и 10 мкм для проводниковых границ стеков 1-3; 10 мкм для всех границ стеков 4-8.) Из исходных данных на основе рассмотренного анализа получены модели для каждого варианта стека в виде полинома второй степени:
Верификация моделей для промежуточных значений параметров выполнена путем сравнения значений погонных задержек, полученных по аналитическим формулам и в системе TALGAT. Для каждого стека произвольным образом ( по методу Монте-Карло) выбрано 500 значений геометрических и электрических параметров из полного набора значений. Параметры структур и их максимальные ошибки приведены в табл. 4.14.
Таким образом, полученные математические модели требуют малого объема памяти, корректны, обеспечивают быстрый расчет погонных задержек со средней погрешностью менее 1% и максимальной - не более 5%. Их использование в широком диапазоне изменения параметров трасс всех возможных стеков позволит быстрое вычисление задержки с приемлемой точностью. Отметим, что для каждого стека получено по одной модели, что дает минимальное количество коэффициентов, требуя минимального объема памяти для хранения модели. При необходимости меньших погрешностей можно получить отдельные для каждого значения одного или нескольких параметров, что увеличит точность за счет уменьшения числа параметров в каждой модели, но увеличит затраты памяти.
Результаты сравнения аппроксимации данных разными методами. В этом разделе даны результаты практической аппроксимации данных для структур стеков 4-8 с помощью коэффициентов и полинома второй степени. Например, набор данных для стека 4 состоит из 3428985 строк вида: hPrep ErPrep hCore ErCore t w г. Объем данных в распакованном виде составляет 208 Мб. В таблице 4.16 представлены результаты, полученные с помощью первого метода.
Для понижения размерности в первом методе используется функция polyfit (из MATLAB), которая позволяет получить коэффициенты для f(x) = Х Г=о aix\i гДе п степень полиномов, (іі - коэффициенты полинома. Из таблицы 4.16 видно, что структуры 4,5 и 8 аппроксимируются с приемлемой точностью, тогда как на остальных максимальная ошибка достигает больших значений. Однако средняя ошибка для всех структур меньше 12%.
Таким образом, из всех рассмотренных видов аппроксимации наиболее приемлемые данные были показаны с помощью аппроксимирующей функции в виде полинома второй степени.
ОКР «УЭМ» для ОАО ИСС. Программы для отображения графиков и вычисления БПФ использованы в работах этапа «Разработка конструкторской и программно-методической документации. Разработка программных средств» ОКР «Разработка комплекса программных и технических средств проектирования, изготовления и испытаний унифицированного ряда электронных модулей на основе технологии «система-на-кристалле» для систем управления и электропитания космических аппаратов (КА) связи, навигации и дистанционного зондирования Земли с длительным сроком активного существования», шифр ОКР «УЭМ». Вычисление временного отклика с использованием преобразования Фурье для схемы, описывающей цепь реальной печатной платы (рисунок 4.12), продемонстрировано на рисунке 4.13. Временные отклики отражают задержку сигнала и искажения его формы.
Программа для импорта печатных плат использована на этапе «Изготовление и комплектация автоматизированных рабочих мест, испытательных стендов и технологического оборудования подсистем комплекса, предварительные испытания, приобретение оборудования, комплектующих и программного обеспечения». На рисунке 4.14 приведен пример результата импорта геометрических и электрических параметров печатной платы радиотехнического блока 1200 из
После формирования электрической принципиальной схемы и выбора воздействия выполняется вычисление частотного и/или временного откликов. Пример отклика на входное трапецеидальное воздействие приведен на рисунке 4.19.
Заключительной частью квазистатического анализа является анализ полученных результатов и проверка соответствия печатной платы требованиям по ЭМС. Проверка заключается в задании порогового значения амплитуды напряжения в узлах схемы. Если значения амплитуды не превышают пороговых, то печатная плата удовлетворяет требованиям ЭМС.
Грант РФФИ 12-01-31110. В работах по проекту «Теоретический анализ эволюционных стратегий для эллиптической модели целевой функции», получены математические модели для реализации оптимизации эволюционными стратегиями, разработана эволюционная стратегия на языке СИ—Ь и в пакете MATLAB, использована программа построения графиков.
ОКР по программе ГЛОНАСС для ОАО «ИСС». В работах по проекту «Разработка материалов в эскизный проект ОКР «Развитие наземного сегмента космического комплекса системы ГЛОНАСС» в части создания составных частей наземных станций контроля и управления» (договор 24/13 от 09.01.2013 с ОАО «ИСС») выполнен обзор возможностей существующих программ моделирования печатных плат.
ОКР «САН» для ОАО «ИСС». В ходе разработки аванпроекта ОКР «Разработка принципов построения и элементов системы автономной навигации с применением отечественной специализированной элементной базы на основе наногетероструктурной технологии для космических аппаратов всех типов орбит» (тема «САН», договор 96/12 от 16.11.2012 для ОАО «ИСС» по Постановлению 218 Правительства РФ) выполнено моделирование вычислительных устройств и цепей управления системы автономной навигации. Геометрические модели печатных плат, импортированных в систему TALGAT, показаны на рисунках 4.20-4.22.
