Модель компонента

При оптимизации электрических соединений необходимо учитывать конструктивно-технологические особенности компонентов и МП:

• Порядок расположения выводов;

• Возможность прохода соединений между выводами;

• Эквивалентность некоторых выводов или групп выводов и т.д.

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

Для реализации задачи трассировки не-

обходимо задать информацию о взаим-

ном расположении выводов модуля и

t_f задать бинарные соотношения между

тремя множествами:

- множеством модулей (компонентов) X={x_i}, i=1,N, |X|=N;

- множеством выводов модулей С={c_gⁱ}, g=1,n_i, | c_gⁱ |=n_i;

-множеством электрических цепей T={t_f}, f=1,M, |T|=M.

Модели электрических схем

• Матричные модели электрических схем

Матрица цепей Т = XC(T) размерностью N x g _{i max}. Элементом матрицы является номер электрической цепи t_f, инцидентный j-тому контакту i-того модуля, g _{i max} – максимальное число контактов i-того модуля.

Внимание!!! Недостаток матрицы (N x g _{i max}).

Матрица контактов C = XT(C) размерностью M x N. Элементом матрицы является номер вывода i-того модуля, инцидентный цепи t_f.

Матрица модулей (компонентов) X = TC(X) размерностью M x g_max. Элементом матрицы является имя модуля, у которого контакт c_jⁱ инцидентен цепи t_f.

Т.к. на практике M>N и N>>g, то размерность матрицы Т меньше, чем размерность матриц С и Х, поэтому более часто применяется матрица Т.

Если среднее число подключенных выводов модулей в схеме С_СР < 0,5(g_max– 1), то информацию о схеме целесообразно задавать в виде списков.

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

• Графовые модели электрических схем

Модель 1 (Мультиграф схемы)

Компоненты схемы представляются вершинами X={x₁, x₂, ..., x_N}, а внешние контактные площадки (ВКП) электрических цепей схемы — вершинами К={K₁, K₂, • • •, K_n} неориентированного взвешенного графа G(Z, V), где Z=XK.

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

X₁ X₅ X₁ X₅

X₆ K₂ X₆ K₂

Рис. а) Рис. б)

Полный подграф Одно из возможных

для цепи t₂ деревьев цепи t₂

Согласно теореме Кэли число возможных деревьев на полном графе определяется по формуле D=N^N-2, где N – число вершин графа. В определенной мере этот недостаток может быть скомпенсирован, если при определении веса ребер (коэффициент связей) графа G учитывать различие полных графов и графов реальных электрических цепей, представляющих собой дерево.

На Рис. б) представлено одно из 16 возможных деревьев для цепи t₂.

Для представленной схемы матрица связей R={r_ij}_NxN имеет след. вид:

Характеристики Модели 1:

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

2. На основании модели, как уже отмечалось, нельзя точно определить основные параметры устройства.

3. Модель представляет собой граф, который описывается матрицей ||r_ij||. Поэтому все алгоритмы обработки модели достаточно просты.

4. Переход от схемы к модели 1 не представляет сложности и состоит из определения коэффициентов связи и формирования матрицы ||r_ij||.

б. Модель описывается с помощью симметричной матрицы ||r_ij|| размера NхN. Недостатком такого описания является значительный объем машинной памяти, который необходим для хранения матрицы ||r_ij||.

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

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

Модель 2 (Гиперграф схемы)

Гиперграф G(Z T) схемы представляет собой множество вершин Z=XK и множество ребер T={t₁ t₂ t₃, …, t_М}, где М – число электрических цепей (при сквозной нумерации). Каждому ребру гиперграфа однозначно соответствует некоторая электрическая цепь.

С другой стороны, каждое ребро гиперграфа представляет собой некоторое подмножество вершин Z(t_f), инцидентных цепи t_f.

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

Списки гиперграфа.

а) Список T(z_i) – список электрических цепей, инцидентных вершине z_i:

Пример списка T(X1) = (t₂ t₃ t₄), T(X2) = (t₁ t₄ t₃), T(X5) = (t₂ t₃ t₇).

б) Список Z(t_f) – список модулей, инцидентных цепи t_f.

Пример списка Z(t₂) = (K2 X1 X5 X6), Z(t₃) = (X1 X2 X5).

Матрица инциденций гиперграфа.

Элементом матрицы является псевдобулева переменная

{

δ_ij = 1, если z_i  Z(t_f) или t_f  T(z_i)

0

Пример матрицы инциденций см. ниже.

Граф Кёнига для гиперграфа.

Гиперграф м.б. представлен в виде графа Кёнига G(Z' V') с множеством вершин Z'=ZT и множеством ребер V'= TX таких, что вершины z_i и t_f смежны тогда и только тогда, когда вершина z_i смежна ребру (цепи) t_f (двудольный граф).

Пример графа Кёнига представлен ниже.

Граф Кёнига

t1 t2 t3 t4 t5 t6 t7

X1 1 1 1

X2 1 1 1

X3 1 1 1

X4 1 1 1

||δ_if|| = X5 1 1 1

X6 1 1 1

K1 1

K2 1

K3 1

Матрица инциденций

Характеристики модели 2

1. Модель можно использовать для решения задач компоновки, размещения и (при соответствующей моди­фикации) трассировки.

2. На основании модели можно точно определить все основные конструктивные параметры устройства.

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

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

5. Модель описывается одним из следующих способов:

или в виде списков Z(t_f), T(z_i) или с помощью матрицы инциденций ||δ _if ||_.

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

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

6. Теория гиперграфов является новой ветвью математики, и соответствующий математический аппарат в настоящее время создается.

7. Гиперграф является обобщением обычного графа. Поэтому от описания модели 2 можно всегда перейти к описанию модели 1.

Модель 3 (ультраграф схемы).

'В данной модели схеме ставится в соответствие ультраграф G (Z' V'). Ультраграф является обобщением ориентированных графов и гиперграфов. Считают, что задан ультраграф G(Z' V'), если задано множество вершин Z'=ZV и множество ориентированных ребер V'.

В модели З каждому ребру ультраграфа (как и в модели 2) взаимнооднозначно соответствует некоторая электрическая цепь схемы. Каждое ребро ультраграфа «ориентируется» в соответствии с порядком прохождения сигналов в схеме. При описании ультраграфа и его изображения удобно использовать его представление в виде ориентированного графа Кенига (см. рис.).

Ультраграф может быть задан:

- в виде двух пар альтернативных списков

а) T(z_i) – подмножеств ребер УГ таких, что

t_f  T(z_i) существует ребро (z_i t_f) V' - вершина z_i - источник сигнала,

б) T'(t_i) – подмножеств ребер таких, что

t_f  T'(t_f) существует ребро (t_f z_i) V' - вершина z_i - приемник сигнала.

Или

а) Z(t_f) – подмножество вершин таких, что

Z_i  Z(t_f) существует ребро (t_f z_i)  V' – вершина t_f - источник сигнала,

б) Z'(t_f) подмножество вершин таких, что

z_i  Z'(t_f) существует ребро (z_i t_f)  V' – вершина t_f - приемник сигнала

Пример:

T(K1)={t₁}, T'(K1)={0}, T(X₃)={ t₅ t₆ }, T'(X₃)={ t₁}, T(X₆)={o}, T'(X₆)={t₂ t₅ t₇}

Таким образом, модулю z_i инцидентны цепи, входящие в состав подмножеств T(z_i) и T'(z_i), т. е. Tz_i=T(z_i) T'(z_i).

Подмножества Z(t_f) и Z'(t_f) записываются аналогично:

- в виде пары матриц

||δ_if||_T(Z) и ||δ_if||_T'(Z), где

{

{

δif _T(z_i) = 1, если t_f  T(z_i) δif _T'(z_i) = 1, если t_f  T'(z_i)

0 0

Характеристики модели 3

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

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

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

4. Если в схеме для каждого компонента известны сигналы, на него поступающие, и сигналы, им генерируемые, то переход от схемы к ультраграфу является однозначным и не сложным.

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

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

7. От описания модели 3 всегда можно перейти к описанию моделей 2 и 1.