Постановка задачи для автоматизированного топологического проектирования РЭС делиться на 3 этапа: задача компоновки, задача размещения и задача трассировки.

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

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

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

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

Сформулируем задачу компоновки схемы как задачу разбиения графа G= (X, U) на части G_i= (X_i, U_i), X_iX; U_iU, iI= {1,2,…,l}, где l - число частей, на которое разбивается граф.

Совокупность частей B (G) называется разбиением (разрезанием) графа G= (X, U) если

G_iB (G) (G_i 0), iI;

G_i, G_jB (G) [G_iG_jX_i X_j=

(U_i U_j=U_{i, j} U_i U_j=)],

G_i = G (1)

Другими словами, совокупность B (G) ={G₁, G₂, …,G_i,…,G_l} является разбиением графа G, если любая часть из этой совокупности не пустая, если для любых двух частей из B (G) пересечение множества вершин пусто, а пересечение множества ребер может быть не пустым, а также если объединение всех частей в точности равно графу G.

В выражении (1) U_i,j определяет подмножество ребер U_i,jU, попадающих в разрез (сечение) между частями G_i и G_j графа G. Обозначим U_i,j=k_i,j и назовем его числом реберного соединения частей G_i и G_j графа G. Число реберного соединения всех частей графа

(2)

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

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

Исходными данными при решении задач размещения являются монтажная плоскость, как правило, прямоугольной формы, число элементов, которое получено в результате компоновки, т.е. разбиения графа схемы на части, и граф схемы соединений элементов G= (X,U). На монтажную плоскость наносят координатную сетку и оси координат s и t и, таким образом, представляют ее в виде графа G_r.

(3)

Задача размещения сводится теперь к отображению заданного графа схемы G= (X,U) в координатную сетку G_r таким образом, чтобы вершины множества Х размещались в ее узлах и суммарная длина связей были наименьшими для возможных способов отождествления вершин графа и узлов сетки. в выражении (3) r_i,j - число кратных ребер между вершинами x_i и x_j; d_i,j - расстояние между узлами i и j графа G_r.

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

определения перечня соединений;

размещение по слоям;

определение порядка соединений;

трассировка проводников.

2. Компоновка

2.1 Последовательный метод разбиения