Формализованная формулировка

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

Сведения к задаче математического программирования

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

В частном случае, когда ИМС содержит несвязанные между собой логические элементы, то задача становится линейной и упрощается: это задача ЦЛП – целочисленного линейного программирования [7].

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

Ввиду трудности формализации и сложности решения задача покрытия схем ЭС решается обычно вручную. Известные алгоритмы являются эвристическими [1]. Для частного случая, когда удается свести задачу к ЦЛП, можно применить метод отсечений [7] или эвристические алгоритмы.

 

Описание проектной задачи разбиения схем ЭС

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

Входные данные

1. Схема электрическая принципиальная ЭС (пример СxЭПр представлен на рис. 2).

2. Параметры конструкций будущих конструктивных узлов. Обычно это вместимость узла и число внешних выводов узла (число контактов соединителей конструктивного узла).

Выходные данные

Полученная совокупность подсхем (электрических принципиальных).

Критерии качества

1. Минимум числа межузловых соединений.

2. Минимум числа узлов (подсхем).

3. Минимум числа типов узлов (задача типизации).

4. Функциональная законченность узлов (подсхем).

Ограничения

1. Вместимость конструктивного узла,

2. Число внешних выводов узла.

Математические модели объектов проектирования

Математические модель СxЭПр ЭС – взвешенный по вершинам гиперграф. В отличие от задачи покрытия здесь веса вершин имеют другой смысл: это например площадь, занимаемая элементами в монтажном поле. Другой пример – это мощность теплоотдачи элемента.

Формализованная формулировка задачи

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