Исследование и разработка векторно-алгебраических методов проектирования топологии печатных плат

В решениях ХХУТ съезда партии КПСС по развитию народного хозяйства СССР предусматривается расширение исследований по прикладной математике и развитие научных работ, направленных на создание и внедрение систем автоматизации и механизации проектно-конструкторских работ.

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

Постоянное усложнение, повышение интеграции радиоэлектронной аппаратуры (РЭА), интенсивное внедрение ее в различные отрасли народного хозяйства, а также необходимость разработки качественной и за короткие сроки новой сложной аппаратуры, удовлетворяющей требованиям мировых стандартов, выдвигают на первый план задачу совершенствования методов проектирования с использованием современных электронных вычислительных машин и автоматизации отдельных этапов проектирования. Так, например, при разработке РЭА на основе больших интегральных структур (БИС) и сверхбольших интегральных структур (СБИС) необходимо решать большой комплекс таких сложных задач, как, например, расчет отдельных элементов БИС, определение их геометрии, взаимного расположения, выделения наибольших планарных частей, так и составление математической модели функционирования всей схемы в целом для оптимизации ее конструкции, что при ручном проектировании требует больших материальных и временных затрат.

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

Большой вклад в развитие методов автоматизированного проектирования внесли советские ученые В. М. Глушков [i], Л. Б. Абрайтис.

2], С. А. Майоров [з], НД. Матюхин [4], М. Е. Штейн [б], А. Н. Мелихов [б], В. А. Селютин [7], А. Н. Петренко [в], В.М.Ку-рейчик [б], Р. П. Базилевич [9], Б. Н. Деньдобренко [ю] ряд зарубежных специалистов и др.

В современном подходе к проектированию сложных схем можно условно выделить три крупных этапа [б*8&bdquo-, 10+26], которые в свою очередь разбиваются на более мелкие. Это следующие этапы: системотехнический, схемотехнический и технический.

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

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

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

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

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

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

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

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

Целью технологического проектирования является разработка технологии и составление технологической документации, необходимой для производства изделия.

Конструкторское проектирование это один из наиболее трудоемких и ответственных этапов всего процесса проектирования РЭА и по своему характеру является многокритериальной задачей.

28*49]. Осуществление полной оптимизации конструкции на практике связано со значительными трудностями из-за большого числа частных 1фитериев, переменных и ограничений, поэтому такие задачи решают используя методы последовательной субоптимизации или организуя обобщающий критерий.

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

Разработка математических моделей схем при конструкторском проектировании базируется на использовании аппарата теории графов, гиперграфов, структурных чисел, их матричных списковых эквивалентов [5*8, 48+59j.

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

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

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

Вопросы планарности графов достаточно глубоко и всесторонне рассмотрены в теории графов [5,6,7,53,56,60+63]. Поэтому основным способом исследования планарности схемы есть переход к эквивалентному графовому представлению и последующему исследованию его планарности. Однако, представляется, что методы теории графов не вполне адекватны задачам проектирования соединений, в частности, нацример, проблема планарности графа не эквивалентна проблеме планарности схемы [53, 64]. Эта неэквивалентность вызвана причинами, которые принципиально отличают схему от графа. К таким отличиям можно отнести следующие: неоднозначное представление электрических соединений, наличие запрещенных областей монтажного пространства, фиксированная ориентация некоторых компонентов, наличие контактов электрических соединений схемы на границе монтажного пространства.

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

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

Анализ и сравнение методов, используемых при конструкторском проектировании, позволяет сделать выводы, что дальнейшее повышение качества проектирования связано с разработкой новых более совершенных подходов и принципов. К этому следует отнести разработку топологических методов трассировки, учет требований планарной реализации на всех этапах проектирования, разработку комбинированных систем проектирования (ЭВМ плюс специализированное устройство), разработку математических моделей схем, использующих аппарат отличный от теории графов. Так в работах [65,66] показано построение комбинированной системы проектирования, а в работах [67+7l] показана возможность использования методов векторной алгебры на всех этапах проектирования топологии соединений.

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

Работа состоит из четырех глав, введения, заключения.

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

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

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

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

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

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

Практическая ценность и результаты внедрения работы. Исследования автора выполнялись в рамках госбюджетной и хоздоговорной тематики по заданиям министерства в соответствии с постановлениями Госкомитета СМ СССР по науке и технике. Разработан пакет программ проектирования топологии печатных плат. Пакет программ базируется на ЕС ЭВМ. Программы написаны на языке Фортран ЕС ЭВМ. Реализованный в диссертационной работе подход к решению задачи определения планарных подмножеств фактически предлагает достаточно общую методику проектирования топологии печатных плат.

Разработанные методы и алгоритмы использовались в научно-исследовательских и практических работах НПО Автоматгормаш при разработке пакета программ САПР топологии печатных плат, С применением разработанных методов и алгоритмов разработан пакет программ позволяющий выделять планарные части схемы в топологическом пространствеусодержащей до 1500 выводов, что соответствует 100 интегральным микросхемам по четырнадцать выводов или 30 БИС по сорок восемь выводов.

Использование, разработанного пакета программ проектирования топологии печатных плат, и включение его в качестве одной из подсистем существующей САПР позволило получить экономический эффект в размере 62 т.руб., что подтверждено соответствующим актом, приведенным в приложении I.

Новые научные результаты вносимые автором на защиту состоят в :

— исследовании и установлении возможности использования алгебраических методов определения пересечения цепей и разделения схем на планарные части;

— определении условий пересечения цепей и их областей в топологическом цространстве;

— разработке форм представления пересечения цепей при представлении их областями;

— разработке алгебраических методов разделения схем на планарные части и выделении максимально пленарных частей;

— разработке специализированных структур для выполнения пленарных частей.

Основные результаты диссертационной работы докладывались: на научно-технической конференции по проблеме «Автоматизация проектирования радиоэлектронной аппаратуры на промышленных предприятиях», г. Запорожье, 1977 г.- на всесоюзной конференции по проблеме «Автоматизация проектирования ЭВМ», г. Киев, 1977 г.- на семинарах научного совета по проблеме «Кибернетика» АН УССР «Технические средства автоматики», г-Донецкна семинаре «Теоретические и прикладные вопросы технической кибернетики», г. Таганрогна региональном научно-техническом семинаре «Автоматизация проектирования электронной аппаратуры (АП-81)», г. Таганрог, 1981 г.

I. ТОПОЛОГИЧЕСКИЕ МОДЕЛИ ЭЛЕКТРОННЫХ СХЕМ.

I.I. Представление электронных схем с использованием аппарата теории графов.

На этапе технического проектирования необходимая информация берется из принципиальной схемы. При этом для того, чтобы по заданной схеме можно было спроектировать конструкцию необходимо, чтобы она удовлетворяла ряду ограничений. Условно эти ограничения можно разделить на две группы: метрические и топологические, К первой группе, метрических, относятся ограничения, определяемые шириной проводников, минимально допустимыми расстояниями между различными элементами, фиксированными размерами компонентов и ряд других, определяемых конкретными физическими размерами, Во вторую группу входят: ограничения на расположение трасс в заданных областях монтажного пространства, ограничения на пересечение различных соединений, требование электрического объединения определенных контактов, то есть ограничения, определяемые топологическими свойствами объекта. Степень влияния вида ограничения при проектировании, как правило, различна в зависимости от вида конструкции. Например, всегда можно подобрать схему с небольшим числом компонентов, которую невозможно реализовать на однослойной конструкции и наоборот. Поэтому процесс проектирования, как правило, разбивают на два этапа [72,73] .На первом этапе проводится проектирование с учетом топологических ограничений. На втором этапе проводят проектирование с учетом уже не только топологических ограничений, но и метрических. Такой подход к проектированию называется топологическим, так как он учитывает топологические ограничения на всех промежуточных этапах [8, 57, 64] и включает следующие основные этапы: построение математической модели схемы, формирование плоской укладки модели схемы (топологический анализ), планаризация модели, формирование графического изображения укладки модели, построение окончательного варианта размещения компонентов соединений.

Топологическая модель схемы для исследования планарности получается в результате объединения представлений компонентов и соединений.

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

Другое представление компонентов основано на положении, при котором каждому контакту компонента взаимно однозначно соответствует вершина модели. При этом вершины, соответствующие соседним контактом, соединяют ребрами, которые называются структурными [74]. Такое представление позволяет учитывать прохождение трассы между определенными контактами, фиксирует порядок расположения выводов компонента. Таким образом, компонент представляется подграфом Vij-)), где P (j-) и V (j-) — соответственно множество вершин и структурных ребер. В зависимости от вида подграфа (j (J^) определяют следующие типы компонентов и их представлений в модели: линейные, циклические, связные, несвязные. Примеры линейного и циклического представления компонентов приведены на рис. 1.1. Компоненты, представление которых имеет циклический вид, могут быть ориентированными и неориентированными. Представление компонента рис. 1.16 считается ориентированным. Адекватным представлением неориентированного циклического компонента является граф типа «колесо» рис. 1.1 В. Для компонента с фиксированной ориентацией не существует адекватного.

J &L.

Р, 3 Ы pft P’O fe p$.

Pi p5 Л Ps Рис .1.1Линейные (a) 'и циклические. (<5в), гфедставления- 4'-компонентов-.'v-'• ¦ ¦ -У— -'-" C^v ¦:•¦¦—U7:':¦ ' •а з — i — s.

G.

7 —.

— 14.

— 12-и.

— 9 — S.

Рис .1.2. Представление. кошонентов с о>1Ктившш.

—'•. верплшайи -''. — представления в виде графа. Так, микросхемам серии KI04, К106, КПЗ, KI33 ряду других соответствует топологическая модель, приведенная на рис. 1.1а, микросхемам серии KI2I, KI22, KI40 и ряду других соответствует топологическая модель, приведенная на рис. 1.1а, б.

Использование структурных ребер позволяет учесть ограничения на проведение трасс между контактами. Если проводить трассу нельзя, то ребро вводится в модель, если проводить трассу можно, то ребро в модель не вводится. Если рассматривать строго, то учет ограничения на количество трасс между контактами в топологических моделях невозможен, поскольку данное ограничение метрическое, поэтому возможность проведения трасс между контактами в некоторых системах [59, 63] используется на этапе метризации. При этом в модели компонента структурным ребрам присваивают пропускные способности, равные допустимому количеству трасс медду контактами. Пример приведен на рис. 1.2.

Среди различных вариантов математического описания схем наиболее часто используется описание топологии с использованием аппарата теории графов — граф, гиперграф, многоместный граф.

5+8, 52, 72, 73]. Модели схемы в виде графа можно построить используя два разных представления. При первом представлении (П1) каждой вершине графа соответствуют компоненты, а соединениями между компонентами соответствуют ребра, при втором представлении (П2) каждой вершине графа соответствуют контакты. Непланар-ные схемы и их топологические модели, построенные с использованием первого представления приведены на рис. 1.3, при этом предполагается, что соединения проводить под компонентами нельзя^ На рис. 1.4 приведен пример пленарной схемы, разрешается проводить соединения под компонентами, топологическая модель которой, построенная с использованием первого представления, непланарна.

Таким образом, из примера рис. 1.3 следует, что достаточное условие планарности схемы не следует из планарности модели и наоборот, из рис Л. 4 следует, что непланарной модели соответствует шганарная схема.

Из приведенных примеров можно сделать вывод, что в общем случае топологическая модель схемы, построенная с использованием точечного представления компонентов, не позволяет проверять ни необходимые, ни достаточные условия планарности схемы, хотя можно определить класс схем, для которых использование точечного представления компонентов позволяет строить адекватные топологические модели. Этому классу схем присущи следующие свойства: не фиксируется порядок контактов компонента, не разрешается проведение соединений под компонентами. В работе [7] доказано, что построенная таким образом топологическая модель является адекватной.

При построении топологических моделей основанных на представлении П2 используют гиперграфы, многоместные графы. Считают, что гиперграф /-/ = (Z., /}) задан, если задано множество вершин Z’TUK и множество ребер • • v причем каждое ребро гиперграфа представляет собой некоторое подмножество вершин. В представлении П2 каждому ребру гиперграфа ставится взаимно однозначно некоторая электрическая цепь схемы. При этом может заранее не обуславливаться в каком порядке будут соединяться вершины инцидентные данному ребру. Если каждое ребро гиперграфа, инцидентно только двум вершинам, то оно вырождается в обычное ребро графа. Так как гиперграф является обобщением обычного графа, то поэтому от описания модели с использованием гиперграфов всегда можно перейти к описанию схемы с использованием графов. Теория гиперграфов является сравнительно новой отраслью математики и поэтому соответствующий математический аппарат еще развивается.

При решеши топологических задач анализа схем возникают ограничения на порядок расположения контактов. Для учета этого ограничения [58] используется модель схемы представляющая собой многоместный граф. Рассмотрим понятие многоместного графа. Пусть /7 = аг,.~ множество элементов, а й множество всевозможных неупорядоченных групп, содержащее п элементов из А. Многоместным отношением на множестве, А называется подмножество объединения всех степеней.

71 ^.

А от I до /Т1 t т. е. Я С2 U Й. Подмножество п /пп, Лв/.

Rn d Н — это П. местное отношение на А. Многоместный граф G-, вводится как упорядоченная пара G — (йR) Элементы множества, А называются вершинами, элемента R — комплексами. Введенное понятие многоместного графа является обобщением известного ранее понятия обыкновенного графа, т. е. обыкновенный граф можно рассматривать как многоместный, для которого.

Использование многоместного графа в представлении П2, как показано в [б4] приводит к фиксированной звездной конфигурации всех трасс, при Этом появляется возможность проверять достаточное условие планарности схемы. В общем случае планарность рассмотренного представления не является необходимым условием планарности схемы. Недостатком этого представления является большая размерность. В условиях незафиксированного порядка контактов компонентов представление П2 становится эквивалентным представлению Щ. Использование в представлении П2 модели компонентов в виде линейного дерева может привести к тому, что непланарная схема, при условии запрещения проведения проводников под элементами, становится пленарной. Для устранения указанного недостатка приходится принимать специальные меры.

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

1.2. Неадекватность топологических графовых моделей схем при анализе планарности.

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

Для решения топологических задач и, в частности, задач разделения соединений на пленарные подмножества в большинстве случаев применяется теория графов. Так как вопросы планарности графов глубоко исследованы в теории графов, поэтому для анализа планарности схем в большинстве случаев применяют хорошо разработанные методы и соответствующие теоремы теории графов [5,6,7,53,56,60*63,75]. При этом для решения задачи плнар-ности переходят к соответствующему графовому изображению и последующему исследованию его планарности.

Как показано [53,64] проблема планарности схемы не эквивалентна проблеме определения планарности графа. Эта неэквивалентность вызвана следующими причинами, принципиально отличающими схему от графа: неоднозначностью представления электрических соединений, наличием областей монтажного пространства, в котором запрещено размещение соединений или компонентов, фиксированной ориентацией некоторых компонентов, наличием контактов, принадлежащих границе монтажного пространства.

Первая причина обусловлена, тем, что граф соединения является деревом, построенном на множестве вершин Ьк, которые соответствуют контактам. Так как согласно теореме Л^/Ш число деревьев, которые могут быть построены на множестве вершин 4 г определяется как 0. к — * где / Д. | = /1К .

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

Q = nQ* (1Л).

AW.

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

Вторая причина вызвана тем, что существуют области монтажного пространства, запрещенные для проведения трасс и размещения компонентов. На плате существуют области, отводимые для крепленил конструкции, технологические отверстия. Такие области не оказывают влияния на топологическое проектирование. Однако существуют области монтажного пространства, которые сводятся к областям на границах которых содержатся контакты. Такие области не представляется возможным отразить в графе, представляющем схему, в то же время учет таких областей необходимо проводить, так как легко привести примеры, когда непланарные схемы представляются пленарным графом.

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

К последней причине относится размещение контактов на границе монтажного пространства. Назначение этих контактов — связь схемы с другими внешними по отношению к ней схемами. Такими контактами являются контакты разъемов печатных плат, внешние контактные площадки полупроводниковых кристаллов интегральных схем.

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

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

1.3. Векторно-алгебраические методы представления топологии электронных схем .

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

Введение

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

69, 70] t которая не обладает метрическими свойствами, но обладав твсеми достоинствами координатно-базисных систем пространств с метрикой. Такая координатно-базисная система обеспечивает возможность представления с небольшими: затратами и в то же время не использует метрических категорий (длина, угол, расстояние и т. п.).

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

Для построения координатно-базисных систем (КБС) вводится ряд основных определений.

Полюс — первичный элемент топологического пространства. Полюсточка пространства. Полею не является синонимом контактной площадки, вывода электронной схемы. Контактная площадка элемента электронной схемы может потребовать для представления несколько полюсов. Точка плоскости — модель полюса.

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

На векторах определены операции сложения и вычитания.

Сложение векторов — операция, которая определена для двух векторов, если исток одного их них и сток другого инцидентны общему полюсу. Сумма двух векторов — вектор, исток и сток которого инцидентны соответственно истоку и стоку слагаемых векторов.

Вычитание векторов — операция, которая определена для двух векторов, у которых общему полюсу инцидентны их истоки либо их стоки. Разность векторов — вектор, исток и сток которого инцидентны соответственно истоку уменьшаемого и истоку вычитаемого, 4. либо стоку вычитаемого и стоку уменьшаемого. Примеры операций сложения и вычитания векторов цриведены на рис. 1.5. Операции сложения и вычитания векторов коммутативны и ассоциативны.

Корпус — минимальное по составу множество полюсов и заданных на них векторов, суша которых равна нулю.

— 9 fi+o. $ + Ю+ с) ~ & +(61 cj to •sj.

Корпус образован таким множеством векторов, которое делит пространство на две части — внутреннюю и внешнюю, и образует границу замкнутой области. При изображении корпуса на плоскости пересечения между его векторами — ребрами отсутствуют. Все точки пространства, за исключением тех, которые принадлежат векторам, находятся либо внутри, либо вне указанной плоскости. Векторы, образующие корпус, ориентированы таким образом, что создается определенное направление обхода. Длина ребер, кривизна, углы образованные ребрами, при изображении корпуса на плоскости не играют роли. Корпус является тем элементарным объектом, который может быть строго показан на плоскости. Множество линий, образующее изображение корпуса на плоскости, всегда планарно. Примеры корпусов приведены на рис. 1.6.

Корпусы, образованные на произвольных множествах, могут иметь общие полюсы и векторы. Каждый полюс и вектор может входить в несколько корпусов.

Два корпуса минимально связны, если пересечение множеств их полюсов содержит один и только один полюс. Отношение минимальной связности показано на рис. 1.66.

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

Используя введенные понятия и определения строятся математические модели компонентов.

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

Элементы электронных схем могут быть связными и полусвязными.

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

Полусвязный элемент — элемент, множество выводов которого образует по 1файней мере две топологически независимые области плоскости.

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

Рассмотрим представление некоторых компонентов электронных схем в топологическом пространстве.

Элементы с точечной системой выводов рис. 1.7а. Точечные системы выводов характерны для большинства навесных компонентов-ре зис торы, конденсаторы, полупроводниковые диоды, транзисторы многих типов и т. д. Каждый вывод точечной системы в топологическом пространстве представляется областью, ограниченной однополюсным корпусом. Промежуток между контактными площадками велик и может быть использован для размещения соединений, потенциалы которых не совпадают с потенциалами указанных выводов. Элементы с точечной системой выводов обязательно полусвязны. Их выводы связаны метрическими ограничениями в метрической плоскости, но не имеют никакой связи между собой в топологическом пространстве. Элементы с одномерной системой выводов рис. 1.76,в, 1.8. В одномерной линейной системе выводов промежутки между соседними выводами меньше ширины проводника и его изолирующей дорожки так что он не может быть размещен в указанном промежутке, если его потенциал не совпадает с потенциалами выводов. Одномерная система выводов может возникнуть и при широких промежутках между ними, при условии, когда необходимо запретить проведение соединений на определенных участках платы. Элементы с одномерной системой выводов могут быть связными и полусвязными рис. 1.8.

5;

Ps.

Рц.

•Рл.

6).

W/ Wa Wv W5 YУс W7 Л.

— е.

• Лг.

-©—-—О.¦¦&-ha />,/.

Pg PS.

Pf.

1.7. 'Представление кодгаонентоз:. a) ~ еяекэнт. с точечными выводами.- б, в — влетит /с одномерной 'системой' выводов*.

Ni w3 A/V Wе в — © «.'¦в. в. о — - о.

О ¦ ' о «¦'¦ о '. О © 0 о :

W/v W/3 w/2 w/7.

Pi<> ,. Pff P/o —. f>9 к.

Рй Рз Рч Ps: Pc pi* f>/{ pic — рэ: *>*.

ЕаоД, 8^-Полусвязний элемент с одномерной системой •¦¦•'.'¦ выводов. ¦ ¦ ¦ ¦ «¦ ' '.

Существенным отличием одномерной системы выводов от точечной является несовпадение числа полюсов корпуса, которыми определяется каждая замкнутая область, с числом соответствующих выводов. Так как в одномерной системе две стороны линии топологически различны, то некоторые выводы рис. 1.7, 1.8, при представлении замещаются парами полюсов. Потенциалы таких пар полюсов всегда тождественно равны, что должно учитываться при проектировании соединений. Поэтому общее число полюсов в представляемой модели может заметно отличаться от общего числа выводов, а представление схемы — от нее самой.

Топологическое пространство без метрики упорядочивается координатно-базисной системой (КБС). Координатно-базисная система — связное множество корпусов, содержащее все полюсы системы и образованное таким множеством векторов, что каждый из них входит в один и только один корпус.

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

Для КБС определены ряд свойств и закономерностей:

Связное множество корпусов, образующее КБС — планарно.

В координатно-базисной системе различают ветви и связи.

Ветвь — вектор, входящий в состав координатно-базисной системы.

Связь — вектор, который не входит в состав координатно-базисной системы.

Любая связь, которая определена на множестве полюсов, входящих в координатно-базисную систему, может быть представлена в виде линейной комбинации ее ветвей.

Топологическая проекция связи — множество ветвей коорди-натно-базисной системы, которые являются дополнением связи до корпуса. Так, согласно рис. 1.9, для связи Si или.

— S,=6 +6 +6 12 «(X.3).

Таким образом, сумма ветвей, входящих в проекцию связи, образует путь по ветвям от полюса, где она начинается, к полюсу, где она заканчивается.

Проекции связей не изменяются при объединении областей. Координатно-базисная система эквивалентна корпусу.

Координатно-базисная система определяет многомерное пространство, число измерений которого равно числу ветвей. Каждую ветвь КБС можно считать вектором-ортом, а коэффициенты в линейных комбинациях (проекциях связей) — скалярным произведением вектора связи i на соответствующий базисный вектор многомерного пространства.

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

Основная особенность КБС — однозначность представления топологии электронных схем. Топологически различимые связи, которые при представлении на плоскости не могут быть совмещены друг с другом путем деформации и перемещения принадлежащих им точек в заданной КБС, не могут иметь совпадающих проекций.

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

Таким образом для полного и непротиворечивого описания топологии электронной схемы должны быть определены координатно-базисная система, а также проекции базисных связей всех ее цепей. Под базисными связями многополюсной цепи из П. связей [69+71], будем понимать любые (ПI) связей корпуса цепи, которые определены на полюсах, линейно независимы и образуют базисный набор, т. е. позволяющий в виде линейной комбинации представить любой вектор цепи, а исключение из него любой связи нарушает целостность цепи. Однако часто имеет место неопределенность, когда электронная схема может быть представлена множеством топологически различимых способов даже в заданной КБС. Такая неоднозначность не является недостатком, так как из топологически различимых представлений всегда можно выбрать наилучшее по тем или иным |фитериям. Сложность задачи при этом возрастает, особенно если учесть, что оценка каждого из них может быть выполнена лишь после окончания проектирования. Использование векторно-алгебраичес-ких методов дает возможность такого определения цепей, при котором органически учитывается неопределенность, а процесс проектирования при заданной КБС не требует перебора вариантов. При этом схемы разбиваются на строго определенные и симметричныенестрого определенные.

Строго определенная схема — схема, цепи которой могут быть представлены на полюсах КБС путем определения набора базисных связей единственным топологически различимым способом.

Симметричная (нестрого определенная) схема — схема, цепи которой на полюсах заданной КБС могут быть определены не единственным топологически различимым способом, т. е. сохранены электрические свойства схемы при определенных ее преобразованиях.

Симметрия обусловлена различными причинами.

Линейная симметрия. При представлении топологии элементов с линейной системой выводов число полюсов перестает совпадать с числом выводов рис. 1.7. Некоторые выводы оказываются представлены парой полюсов. Полюсы, переходящие в пару, неразличимы по своим электрическим свойствам, но топологически эти полюса различны — можно осуществить соединение с любым из них.

Симметрия выводов. Существуют элементы с подмножествами выводов, которые неразличимы по их электрическим свойствам, но различаются топологически. Это схемы, например, дискретного действия, осуществляющие операции конъюнкции, дизъюнкции и т. п. Перестановка номеров соответствующих полюсов, на которых определены цепи, не меняет электрических свойств схем, но может значительно изменить результаты проектирования топологии.

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

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

Основным требованием к возможным представлениям симметрия^ ных схем является их различимость при изменениях цепей, которые происходят при преобразованиях из группы симметрии. Как показано б9,71], любое переопределение цепей, являющееся результатом переопределения схемы на основании ее симметрии может быть представлено перестановкой соответствующих полюсов координатно-базис-ной системы и преобразованием самой системы.

Рассмотрим представление схем, учитывающее симметрию в заданной координатно-базисной системе.

Линейная симметрия. Определение цепей схем с линейной симметрией рассмотрим на примере, приведенном на рис. 1.10, На рис. 1.10а представлена схема, рис. 1.106 — координатно-базисная система, рис. 1.10в — координатно-базисный корпус и всевозможные варианты проведения двухполюсных цепей Су и С^ с учетом линейной симметрии. Из рисЛ. Юв следует, что совокупность четырех способов определения цепи является результатом ее симметризации. Можно построить систему взаимных пересечений между симметризован-ными цепями и найти их наилучшее определение по критерию планарности. Размерности задач в этом случае становятся большими. Чтобы этого избежать переходят от понятия области, которая тождественна цепи, к области, где цепь может быть определена. В рассматриваемом примере область определения цепи С{ представлена на рис. 1.10г и определена на полюсах^jq Р12* а область определения цепи С2 — на полюсах Р г?, РдРц" Для определения областей определения в схему введены дополнительные связи Syy и для цепи с, и ?>02, — для цепи С^. Таким а).

Ps д) /^ЧР.

Р7 -#9 fe. I- 10. Области• опрелелёнЕя:/ цепей" ^тссхет^о ^дйнейнс!

• '. О!' • 'О! Я:¦, *.. ' v -" ' ','.'* •, -'. :"'•-'—.-• образом, область определения цепи — область, ограниченная корпусом, который в заданной КБС определен на полюсах, которые могут принадлежать цепи. Поэтому наилучшее по тем или иным критериям определение цепи в схеме с линейной симметрией может быть выполнено на основании информации только с базисных связях ее области определения.

Области определения цепей в схемах с линейной симметрией независимы так же, как независимы цепи, определяемые в своих областях.

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

Симметрия выводов. При представлении топологии схем с симметрией выводов справедливы все положения, касающиеся линейной симметрии. Однако для симметрии выводов характерны и принципиальные особенности. Главная особенность симметрии выводов — перекрытие областей определения цепей, т. е. множества, на которых определены цепи, могут содержать общие элементы. Поэтому могут существовать базисные связи, которые принадлежат областям определения разных цепей, но определены на одних и тех же полюсах рис. 1.II.

Цепи С I, С2″ С з определены соответственно: £Г i-на полюсах Р j, Р 3″ «.

Как видно из рис. 1.II, отношения связей, ограничивающих области определения цепей с симметрией выводов, вдоме отношения пересечения имеют еще и отношение полупересечения.

Симметрия компонентов. При представлении топологии схем с симметрией компонентов сохраняются положения, касающиеся схем с.

С з — на полюсах линейной симметрией и симметрией выводов. Однако есть одна особенность — это зависимость преобразований цепей, заданных в своих областях определения. Она заключается в том, что при перестановке номеров компонентов с исходного на новый должны быть одновременно перенесены все цепи.

Симметрия элементов. Представление схем с симметрией элементов не отличается от представления схем с компонентной симметрией.

1.4. Выводы.

Проведенный анализ методов представления электронных схем позволяет сделать следующие выводы.

1. Предложен способ построения системы технического проек тирования вычислительных структур со схемной реализацией модуля подсистемы решения задач технического проектирования.2. Разработан принцип построения специализированной струк туры для реализации модуля определения планарной части проектируе мой схемы со следующими свойствами: • высшая скорость обработки информации, определяемая време нем отработки переходных процессов в однородной сети- • возможность наращивания объема однородной сети, необходи мость которого вызывается увеличением сложности проектируемой аппаратуры- • технологичность изготовления, определенная возможностью использования методов интегральной технологии.3. Разработаны функциональные схемы: • блока моделирования матрицы пересечений- • блока формирования схемных ограничений- • блока определения матрицы перестановок. З, А К Л Ю Ч Е Н И Е В диссертационной работе с использованием аппарата вектор ной алгебры разработаны и исследованы методы определения пересе чения цепей в топологическом пространстве. Предлояены формы пред ставления пересечения цепей, разработан аппарат их формальных преобразований, методы и алгоритмы выделения планарных частей схемы," Предложены формы компактного представления систем ограни чений, оцределенн и исследованы свойства и операции над ними, позволивпше сфорь/оглировать метод формирования полного набора пла нарных частей схемы. Используя сформулированные векторно-алгебраические методы, показана возможность построения специализированных структур для выделения планарных частей схемы. Основные результаты работы сводятся к следующему: • исследована и установлена возможность использования ал гебраических методов определения пересечения и разделения элек тронных схем на планарные части в топологическом цространстве- • доказано, что отношение пересечения цепей и областей определения цепей носят топологический характер и не зависят от размещения элементов на плоскости печатной платы- • разработаны алгебраические методы разделения электронных схем на планарные части, позволящие вести проектирование топо логии печатных плат с учетом симметрии, эквивалентности, зазтруз ки узких мест и т. д.- • разработаны методы компактного представления и форвдаль ных преобразований множеств ограничений, позволившие ползгчать точные решения и полный набор планарных подмножеств проектзаруе мой схемы- • разработаны приближенные методы разделения схем на пла нарные части позволяющие вести проектирование одновременно во всех слоях платы- • показана возможность построения специализированных ст руктур для выделения планарных частей схемыРазработанные в диссертащЕи методы и алгоритмы проектиро вания схем используются в научно-исследовательских и проектно конструкторских работах при разработке систем технического проек тирования печатных плат в институте ЗВИЙРС, Ш О Автоматгормаш при разработке системы контроля изготовления печатных плат и жгуто вого монтажа,' Теоретические и практические результаты, полученные в дис сертационной работе использованы в научно-исследовательских и проектно-конструкторских работах Ш О Автоматгормаш при разработ ке пакета прозтрамм САПР топологии печатных платРазработанный пакет программ позволяет обрабатывать схемы содержащие до 1500 выводов, что соответствует схеме из 100 интегральных микросхем по 14 выводов или 30 Ш С по 48 выводовИспользование, разработанного пакета программ в качестве одной из подсистем существующей САПР в институте ЗНИИРС позволи ло получить экономический эффект в размере 62 т.руб., что под тверждено соответстеущим актомОсновные результаты, полученные в диссертации, опублико ваны в работах [б7+71, 79, 80 J и докладывались на республи канской конференции «Автоматизация проектирования радиоэлектрон ной аппаратуры на промышленных предприятиях», г. Запорожье, 1977 г-, на всесоюзной конференции по проблеме «Автовдатизация проектирова ния ЭВМ», г-Киев, 1977 г-, на региональном научно-техническом семинаре «Автоматизация проектвфования электронной аппаратуры», Г. Таганрог, I98I г, на семинарах научного совета по проблеме «Кибернетика» АВ УССР «Технические средства автоматики», г. Донецк, на семинаре «Теоретические и прикладные вопросы технической ки бернетики», г. Таганрог,.