Представление схемы ориентированным графом. (аналогично ультраграфу)

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

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

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

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

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

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

• «элементы Э являются источниками сигналов для цепей С » и

• «цепи С являются источниками сигналов для элементов Э ». Обозначим эти отношения через Д1(Э,С) и Д2(С,Э) соответственно.

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

– множеству элементов схемы Э и множеству цепей С поставим во взаимно-однозначное соответствие множества вершин ультраграфа X и ребер U: Э «X, С«U; – отношения Д1(Э,С) и Д2(С,Э) формально зададим предикатами Г1(X, U) и Г2(U, X) соответственно: Д1(Э,С) ~ Г1(X, U), Д2(С,Э) ~ Г2(U, X).