Материал: Формальное представление электрических принципиальных схем для решения задач автоматизированного проектирования электронной аппаратуры (120
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 5.14. Взвешенный граф схемы
определяют количество цепей между элементами xi и xj. Полученный граф называется взвешенным графом схемы (ВГС) и имеет такой же вид, что и на рис. 5.14. В общем случае ВГС может быть описан матрицей соединений R = ||rij||n×n, строки и столбцы которой соответствуют элементам схемы, а rij равен весу, приписанному соединению элементов xi и xj. Матрица R — симме-
тричная, с нулевой главной диагональю (rii = 0; i = 1,2,...,n). Для рассматриваемого графа матрица R имеет вид, показанный на
рис. 5.14.
Между матрицей соединений R и матрицей комплексов Q существует простая связь:
R = Q · Q ,
где Q — транспонированная матрица Q.
Для широкого класса схем матричная форма представления связности элементов явно неэкономна [4]. Наиболее компактная форма задания связи элемента xi с элементом xj графа G = (X,U)
— аналитическая, когда задано множество вершин X и отображений Γ в виде расширенной таблицы соединений (РТС). Однако из табличной формы записи (см. ниже) сложнее организовать оперативную выборку нужных элементов.
Для ввода в ЭВМ РТС представляют в виде следующих массивов:
•массив отображений вершин Z[1 : P];
•массив числа отображений вершин W[1 : P];
31
»ервисC-нигаK гентство«A ООО & »БИБКОМ« ЦКБ« ОАО Copyright
32
|
|
|
x0 |
|
|
|
x1 |
|
|
|
x2 |
|
|
|
|
x3 |
|
|
|
x4 |
|
|
|
||
Z[1 : P] |
1 |
2 |
|
3 |
4 |
|
0 |
2 |
3 |
|
0 |
1 |
3 |
|
0 |
1 |
|
2 |
4 |
|
0 |
2 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
5 |
6 |
7 |
|
8 |
9 |
10 |
|
11 |
12 |
13 |
14 |
|
15 |
16 |
17 |
|
|
||
|
|
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
W[1 : P] |
2 |
1 |
1 |
2 |
2 |
1 |
2 |
1 |
1 |
2 |
1 |
|
2 |
2 |
2 |
1 |
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
12 |
13 |
14 |
15 |
|
16 |
17 |
|
|
|
|
|
|
– массив границ отображений Γxi |
элементов xi графа G |
|
|
||||||||||
V [1 : l] |
4 |
7 |
10 |
14 |
1 |
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 5.15. Расширенная таблица соединений
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
• массив границ отображений V [1 : l], где l — число границ отображений Γxi вершин X, P —- объем массива Z и W.
Состояние РТС ВГС (см. рис. 5.14) может быть представлено в табличной форме (рис. 5.15).
Очевидно, что длина массивов Z и W составит P ячеек. Для оперативной выборки подмножеств Γxi организуется вспомогательный адресный массив V [1 : l], содержащий l информативных строк, в i-й строке которого содержатся начальный или конечный адреса i-го подмножества Γxi. Адресный массив позволяет организовать на множестве z и W любые алгоритмические процедуры, по скорости выполнения аналогичные матричным операциям.
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Приложение 1
СТРУКТУРА ДОМАШНЕГО ЗАДАНИЯ ПО ТЕМЕ «АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ ЭЛЕКТРОННОЙ АППАРАТУРЫ»
Исходная информация для решения задач конструкторского проектирования — электрическая принципиальная схема. Представить электрическую принципиальную схему в виде списка цепей — наиболее удобной форме для дальнейших формальных преобразований исходной информации с применением ЭВМ.
Формализация схемы электрической принципиальной для решения задач автоматизированного проектирования состоит в следующем:
а) преобразовать заданную электрическую принципиальную схему в КС;
б) представить КС в виде списка соединений (цепей); в) для КС построить модель в виде ГКС и представить ее ма-
трицами A и B;
г) преобразовать ГКС в ГЭК и представить его матрицей Q; д) преобразовать ГЭК в ВГС и представить его матрицей R; е) разработать расширенную таблицу соединений ВГС и пред-
ставить ее в форме массивов для ввода в ЭВМ.
2.Варианты алгоритмов преобразования исходной информации
ввиде списка цепей в различные формы представления:
а) преобразование списка цепей в матрицу A;
б) преобразование списка цепей в матрицу B;
в) преобразование списка цепей в матрицу Q;
г) преобразование списка цепей в матрицу R;
д) преобразование списка цепей в РТС в форме массивов отображений вершин Z, W, V .
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Приложение 2
КОНТРОЛЬНЫЙ ПРИМЕР
Рассмотрим пример выполнения домашнего задания по теме «Автоматизация проектирования электронной аппаратуры». Пример состоит из двух частей. В первой части происходит формализация исходной информации — электрической принципиальной схемы в соответствии с задачами проектирования. Во второй части приводится вариант схемы алгоритма для решения поставленной задачи.
П2.1. Формализация исходной информации
Постановка задачи. Для заданного варианта представить электрическую принципиальную схему в виде списка цепей и преобразовать в КС. Для КС построить модель в виде ГКС, представить в виде матриц A и B. Преобразовать ГКС в ГЭК, представить в виде матрицы Q. Построить ВГС, представить в виде матрицы R и РТС.
Исходные данные. Электрическая принципиальная схема функционального узла представлена на рис. П2.1.
Рис. П2.1. Электрическая принципиальная схема функционального узла 35