типовых задач конструкторского проектирования.

 4.1. Элементы теории графов, используемые при описании

моделей конструкций РЭА.

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

      Графом G(X,U)  называется математический объект,  состоящий из двух множеств: множества вершин X и множества ребер U, находящихся между собой в заданном отношении.

      Графу G (X,U) может быть поставлена в соответствие матрица смежности A = êêa_ij êê_{n x n} - квадратная матрица размерностью n x n , каждый элемент которой a_ij равен числу ребер, связывающих вершину x_i с вершиной x_j.

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

      Число ребер, инцидентных вершине x_i, называют локальной степенью вершины x_i и обозначают r( x_i ).

      Два ребра u_ij и u_ik называют смежными, если они имеют общую вершину x_i. Две вершины x_i и x_j называют смежными, если они соединены ребром u_ij.

      Отображение Гx_i представляет собой совокупность всех смежных с вершиной x_i вершин графа.

      Последовательность ребер u_ij Π U (заданных   парами   вершин      (x₁ ,x₂ ),(x₂ ,x₃ ), ...,(x_k-1 ,x_k )), в которой любые два соседних ребра смежные, называется маршрутом.

      Граф G (X,U) называется связным,  если любые две его вершины  связаны маршрутом.

      Маршрут, в  котором  начальная и конечная вершины совпадают, называется циклом.

      Связный граф без циклов называется деревом.

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

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

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

      В системах  автоматизированного проектирования широкое распространение получил алгоритм Прима построения кратчайших покрывающих деревьев (КПД).  Этот алгоритм основан на последовательном разрастании поддерева  путем добавления к нему  ребер графа  G (X,U) с наименьшим весом и не образующих циклов с ранее включенными в строящееся  поддерево  ребрами.  Процесс  разрастания поддерева продолжается до тех пор, пока число включенных в него  ребер не станет равным n-1 (n - число вершин искомого графа).

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

      Данный алгоритм может быть также реализован в матричной форме. Для этого составляется матрица весовых коэффициентов (длин), каждый элемент которой a_ij равен длине ребра u_ij. В первой строке матрицы находим минимальный элемент a_1j и первое соединение в строящемся КПД проводим между вершинами x₁ и x_j.  Элементы 1 и j столбцов исключаем из дальнейшего рассмотренияч. Далее просматриваем оставшиеся элементы 1-й и j-й строк. Среди них находим минимальный элемент. Предположим, что найденный элемент находится в k-м столбце. Тогда, если этот элемент располагается в 1-й строке, то следующее соединение строящегося КПД проводим между вершинами x₁ и x_k, а если - в j-й строке, то соединение проводим между вершинами x_j и x_k.  Все элементы k-го столбца исключаем из дальнейшего рассмотрения. Далее просматриваем оставшиеся элементы 1-й, j-й и k-й строк и так далее до тех пор, пока все элементы исходной матрицы не будут исключены.

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

      При конструкторском проектировании электронно-вычислительной аппаратуры (ЭВА) к топологическим чертежам часто предъявляют требования  получения плоского изображения схемы  или ее частей.  Граф G (X,U),  отображающий искомую схему,  называется плоским, если его ребра ,  расположенные на плоскости в двумерном  евклидовом пространстве,  не пересекаются (рис. 4.1.4).  Граф,  изоморфный плоскому и расположенный в двумерном пространстве с пересечением ребер,  называется планарным  (рис. 4.1.4).  Необходимость в решении задачи определения планарности графа и построения его плоского изображения возникает,  напр., при проектировании однослойных печатных плат.

4.2. Типовые задачи конструкторского проектирования.

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

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

n компонент (напр., вентиль микросхемы),

n  элемент (напр.,  микросхема), 

n ячейка или типовой  элемент замены (напр., печатная плата),

n устройство

n стойка.

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

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

      Кроме описания исходной схемы для конструкторского  проектирования ЭВА необходима следующая условно-постоянная информация,  хранящаяся в библиотеке базовых элементов САПР:

         -  описание элементной базы;

         -  описание типовых конструктивов всех уровней;

         -  описание форматов конструкторской документации;

         -  описание технологических требований.

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

      В конструкторском проектировании выделяют три группы задач:

         -  синтез конструкции;

         -  контроль полученных конструктивных решений;

-  оформление конструкторской документации.

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

      Основными задачами этапа синтеза конструкции ЭВА являются:

         - типизация:  определение  элементной базы,  необходимой для

реализации исходной функциональной  схемы,  когда  номенклатура конструктивных  элементов неизвестна;

         - покрытие: определение элементной базы, необходимой для реализации исходной функциональной схемы, когда номенклатура элементов известна;

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

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

         - трассировка монтажных соединений между размещенными  конструктивными элементами.

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

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

      Формирование и выпуск проектно-конструкторской   документации осуществляется с применением стандартных пакетов машинной графики с использованием форматов документов из  библиотеки  базовых  элементов     САПР.

4.3. Алгоритмы покрытия.

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

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

      Исходной информацией  для  этой  проектной операции является функциональная схема,  разработанная на схемотехническом  этапе    проектирования, и  набор  типов модулей (конструктивных элементов) N ={n₁ ,n₂ ,...n_v ,...,n_p },  где p - число конструктивных  модулей в наборе N.