Материал: Формальное представление электрических принципиальных схем для решения задач автоматизированного проектирования электронной аппаратуры (120

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Рис. 5.10. Граф и его матричное описание

Рис. 5.11. Вариант кодирования коммутационной схемы (а) и список ее соединений (б)

выводов C0 = {ci1,ci2,...,cin}. Кроме выводов элементов в КС присутствуют внешние выводы C0разъема. Для удобства будем считать, что эти выводы принадлежат фиктивному элементу x0.

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

26

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Для полноты описания необходимо ввести данные, определяющие, к какому конкретному выводу cik подходит электрическая цепь uj, инцидентная xi. Иными словами, следует задать описание инцидентности между тремя множествами: множеством цепей

U = {u1,u2,...,um}, элементов X = {x1,x2,...,xn}, включая и

разъемы, и выводов элементов Ci = {ci1,ci2,...,cik} (рис. 5.11, а). Итак, в КС соединения осуществляются через вывод cij (где i —

номер элемента; j — номер подключенной к нему цепи) образующие электрические цепи. Цепь — гальванически связанные между собой контакты элементов.

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

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

X = {x1,x2,...,xn}, соединенных цепью j (j = 1,2,...,M), при условии, что всегда

где ki — число задействованных выводов элемента xi; ρj — размер j-й цепи; K — общее число выводов в схеме; n — число элементов; M — число цепей.

Число элементов в комплексе называется размером элементного комплекса.

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

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

Рассмотрим несколько способов описания электрических принципиальных схем графами.

27

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Построение графа коммутационной схемы (ГКС). Введем вершины трех типов: Х , С, U. Вершины Х соответствуют элементам схемы, вершины С — выводам элементов, включая внешние выводы схемы, а вершины U — цепям (комплексам) схемы. Среди ребер различают элементные F и сигнальные W.

Элементные ребра определяют принадлежность выводов из множества С элементам из множества X и задаются парами вер-

шин (xi,ck).

Сигнальные ребра W определяют вхождение выводов из С в отдельные цепи и описываются парами вершин (ck,uj).

Для рассматриваемой схемы ГКС будет иметь такой же вид, что и на рис. 5.12.

Рис. 5.12. Граф коммутационной схемы

Учитывая, что ГКС содержит вершины и ребра разных типов, его структуру удобнее описывать с помощью пары матриц A и B.

Матрица A представляет взаимосвязь цепей и выводов схемы и определяется следующим образом: A = ||aij||M×K, где M — число цепей; K — число выводов в схеме; элемент aij = 1, если вывод cik принадлежит цепи uj, в противном случае aij = 0.

28

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Для рассматриваемого графа матрица А имеет вид

c01 c02 c03 c04 c11 c12 c13 c21 c22 c23 c31 c32 c33 c41 c42

Каждый столбец матрицы содержит одну единицу, поскольку любой вывод может входить лишь в одну цепь. Число единиц в любой строке матрицы равно размеру соответствующей цепи.

Матрица B = ||bij||n×K выделяет подмножества выводов, принадлежащие отдельным элементам. Элемент матрицы bij = 1, если вывод cik принадлежит элементу xi, в противном случае bij = 0.

Для рассматриваемого графа матрица B имеет вид:

c01 c02 c03 c04 c11 c12 c13 c21 c22 c23 c31 c32 c33 c41 c42

В каждом столбце матрицы B содержится одна единица, поскольку любой вывод может относиться лишь к одному элементу. Число единиц в любой строке равно числу соответствующих выводов на соответствующем элементе. Модель в виде ГКС используют при задании полной информации о схеме в процессе автоматизированного конструирования. При алгоритмическом решении отдельных задач конструирования удобнее пользоваться упрощенными моделями рассматриваемых схем. Так, при компоновке узлов можно отождествить наборы выводов Ci с самими элементами xi. В результате этого преобразования комплексы Uj переходят в элементные комплексы Uj, что соответствует в ГКС «стягиванию» определенных подмножеств вершин из C в вершины из X

29

Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»

Рис. 5.13. Граф элементных комплексов

и устранению элементных ребер F. Полученную модель схемы будем называть графом элементных комплексов (ГЭК).

Для рассматриваемой схемы ГЭК имеет такой же вид, что и на рис. 5.13. Для описания ГЭК удобно пользоваться матрицей Q = ||qij||n×M, строки которой соответствуют элементам xi, а столбцы — элементным комплексам Uj. Значение qij = 1, если элемент xi входит в комплекс (связан с j-й цепью), в противном

случае qij = 0.

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

Заметим, что между матрицей Q и введенными ранее для описания ГЭК матрицами А и В существует простая связь: Q = BA , где A — транспонированная матрица A.

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

Один из способов состоит в следующем. Подсчитаем для каждой пары элементов число связывающих их цепей. Далее построим граф G = (X,U), в котором вершины xi соответствуют элементам, ребра uij с приписанными к ним весами rij (rij > 0)

30