Математические модели конструкций и схем.

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

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

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

(16.1)

1. Первый способ дает оценку длинны соединения между двумя точками с координатами (x_i, y_i), (x_j, y_j) по кратчайшему расстоянию (Рис.3, а, б).

Рис.3. Виды монтажных соединений:

а – цепь; б – звезда; в-д – ортогональные соединения.

2. Второй способ дает оценку длинны соединения между двумя точками при ортогональных соединениях, прокладываемых параллельно осям координат (Рис.3, в-д), когда соединения проводятся по магистралями или каналам (для БИС и СБИС).

3. Третий способ полезен, когда в задачах оптимизации требуется уменьшение не только суммарной, но и максимальной длинны проводников. При использовании последней метрики при S=2, 3, … «длинные» соединения сильнее влияют на функцию оптимизации.

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

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

Рис.4.

Элементы схемы (e_i), и внешние выводы (c_{i, j}), каждого элемента суммируются, а выводы схемы, имеющие одинаковый потенциал, группируются в комплексы соединений (V_j) также нумерованные (Рис.5).

Рис.5

Перенумерованные n (e_о) элементов схемы составляют множество Е={ e_i, i=0, 1, 2, …n }. Внешние выводы элементов образуют семейство множества С={ С_{i, j}, j=1, 2, …, k, i=0, 1, 2, …, n }, где i – номер элемента; j – номер вывода в данном элементе; k_i – число выводов i -го элемента. Отметим, что элементы множества С₀ относят к внешним выводам схемы, образуя специальное множество e_о. Комплексы соединений выделенные на Рис.5 пунктирными линиями, образуют семейство множеств V={ V_{, j}, j=1, 2, …, М }, где V_{, j} – множество эквипотенциальных выводов схемы; М – число комплексов. Поскольку выводы, принадлежащие различным комплексам соединений, непосредственно не связаны (только через элемент), то

Приведенное формальное описание может быть представлено в виде графа (Рис.6), если элементы множества Е, С, V рассматривать как вершины, а также ввести ребра, F определяющие принадлежность выводов элементам (элементарные ребра F) и принадлежность выводов комплексам соединений (сигнальные ребра W). Подобная математическая модель в виде графа широко используется в задачах дискретной оптимизации.

Граф с вершинами трех типов (Е, С, V) и ребрами двух типов (F, W) дает наиболее детальное представление схемы, т.е. задает полную информацию о схеме.

Однако в ряде задач и алгоритмов можно обойтись меньшим объемом информации о схеме, например, используя граф, полученный после втягивания вершины С_i в вершины Е и удаления элементарных ребер F (Рис.6).

Рис.6.

Для отображения коммуникационной схемы в ЭВМ применяется также матричное и списочное представление рассмотренного графа.

1. В матричном представлении используются матрицы инциденций «номер комплекса – номер вывода элемента» или «номер элемента – номер вывода элемента» размерности и ХХъъ соответственно.

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

Пример матричного и списочного описания полной модели представлен на Рис.7, 8.

Пример матричного описания:

Пример списочного описания: