автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Алгоритмы анализа сложных схем

РОССИЙСКАЯ АКАДЕМИЯ НАУК ДАЛЬНЕВОСТОЧНОЕ ОТДЕЛЕНИЕ Институт проблем морских технологий

НАУМОВ Леонид Анатольевич

Алгоритмы анализа сложных

схем

Специальность 05. 13. 16 — Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (в области технических наук)

ДИССЕРТАЦИЯ

на соискание ученой степени доктора технических наук

Владивосток 1997

Оглавление

Введение 4

1. Краткий обзор современных методов анализа 10

1.1. Основные понятия теории графов......................10

1.2. Направленные графы....................................18

1.3. Топологические методы анализа........................26

1.4. Теоретико-множественные методы анализа линейных цепей..................................27

1.5. Применение графов и теоретико-множественных методов при анализе нелинейных электрических цепей 31

2. Алгоритмы анализа электрических цепей, представленных сигнальными графами 33

2.1. Алгоритм нахождения всех путей и контуров направленного графа...................... 33

2.2. Нахождение путей и контуров графа на основе обобщенного алгоритма Гаусса............... 39

2.3. Алгоритм определения передачи сигнального графа . 43

2.4. Алгоритмы нахождения минимального множества сечений контуров обратной связи........... 52

3. Структурно-топологические алгоритмы анализа цепей, представленных обобщенными сигнальными графами 63

3.1. Алгоритмы нахождения передач направленного графа 63

3.2. Анализ сложных направленных графов........ 72

3.3. Алгоритм исключения группы узлов направленного графа............................ 76

4. Анализ сложных электрических цепей с помощью структурно-матричного преобразования 85

4.1. Изображение узлового определителя.......... 87

4.2. Изображение алгебраических дополнений....... 90

4.3. Входная и взаимная проводимости......................93

4.4. Функции проводимостей схемы при коротком замыкании ......................................................94

4.5. Анализ пассивных цепей................................97

4.6. Обобщенные линейные схемы .............100

4.7. Анализ активных цепей.................104

5. Анализ электрических цепей с помощью структурно-топологического преобразования 107

5.1. Идентификация деревьев графа............108

5.2. Выявление всех деревьев графа............116

5.3. Алгоритм нахождения ^Г-деревьев графа.......123

5.4. Анализ линейных электрических цепей с помощью структурно-топологического преобразования.....126

5.5. Анализ электрических цепей на основе усилителей с бесконечным усилением.................131

6. Структурно-топологический анализ сложных линейных цепей 135

6.1. Выявление деревьев сложных графов.........135

6.2. Выявление всех 2-деревьев сложных графов.....144

6.3. Реализация корректирующих цепей усилителей с глубокой обратной связью ...............147

7. Вопросы анализа и реализации функций электрических цепей 150

7.1. Анализ чувствительности передачи линейных электрических цепей.....................150

7.2. Анализ стабильности..................156

7.3. Синтез одного класса структур измерительных устройств ...........................160

7.4. Вопросы реализации функций линейных электрических цепей ........................163

8. Структурно-топологические методы в анализе нелинейных цепей 165

8.1. Формирование математической модели схемы при отсутствии связанных неправильных размещений . . 166

8.2. Формирование математической модели схемы при наличии связанных неправильных размещений ... 171

8.3. Алгебраический подход к решению систем нелинейных дифференциальных уравнений цепи.......173

9. Заключение 178

9.1. Общие выводы по работе................178

Литература 181

Введение

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

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

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

Среди работ, заложивших основу топологических методов, наиболее важное место занимают труды Кирхгофа, Максвелла, У. Персиваля, С. Мэзона, С. Коутса, У. Майеды, Ф. Резы, С. Дезое-ра и др. Дальнейшее развитие данного научного направления, получившего свое отражение в многочисленных трудах отечественных и зарубежных ученых, предопределило место графов в теории цепей. Графы нашли применение при анализе и синтезе пассивных и активных цепей (В.И. Анисимов, Б.И. Блажкевич, Г.П. Гаев, П.А. Ионкин, Ю.М. Калниболотский, Н.Г Максимович, В.И. Пам-пуро, В.П. Сигорский, С. Сешу, A.M. Сучилин, и др.), в вопросах автоматизации расчета схемных функций (Р.В. Дмитришин, А.Г. Ларин, Д.И. Томашевский, А.Г Остапенко, А.И. Петренко и др.), при решении конструкторско-технологических задач проек-

тирования радиоэлектронных устройств (Р.П. Базилевич), в синтезе систем автоматики (А.Н. Мелихов, Т.Н. Райцин) и для описания электромеханических систем (Н.Ф. Ильинский, В.К. Цацет-кин)

Применение теоретико-множественного аппарата положило основу методам структурных и обобщенных чисел. Здесь следует прежде всего отметить работы С. Беллерта и Я.К. Тро-хименко. Дальнейшее развитие эти методы получили в работах Л.Я.Нагорного, В.Г. Табарного, В.К. Ловкого. Применение аппарата схемных множеств и внешней алгебры известно благодаря работам Ю.В. Королева и Н.Г. Максимовича. Разработке матричных методов, граничащих как с графами, так и со структурными числами, посвящены работы Л.Г. Шатихина. Основы исследования сложных цепей по частям разработаны российскими и зарубежными учеными: Г.Г. Пуховым, Г. Кроном, X. Хэппом и др. Методы редукции и макромоделирования являются предметом исследований В.Н. Ильина, Р.В. Дмитришина.

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

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

В методе обобщенных чисел Я.К. Трохименко модель исследуемой цепи представлена направленным графом С. Коутса. Появи-

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

У истоков машинного анализа нелинейных цепей стоят: Д. Ка-лахан, Е. Ку, Р. Рорер, К. Джир, Ф. Брэнин, Л. Линвилл, Чэнь и др., а также ученые России и стран ближнего зарубежья: Б.И. Белов, Б.В. Анисимов, И.П. Норенков, Т.М. Агахонян, В.Н. Ильин, Е.А. Чахмахсазян и многие другие. В одной из последних монографий А.И. Петренко показывается, что не существует непроходимой пропасти между методами анализа линейных и нелинейных цепей. И те и другие можно анализировать с помощью алгоритмов, построенных на единой алгебраической основе.

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

Связь темы с планами отраслей наук и народного хозяйства.

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

— Программно-аппаратное обеспечение локальных средств сопряжения автоматизированных систем и анализ методов моделирования физико-технических процессов и объектов, N гос. регистрации 00187.0043109;

— Разработка пакетов прикладных программ и микро-ЭВМ с перифирийными устройствами для автоматизации научных исследований, N гос. регистрации 01.84.0038879;

— Разработка алгоритмов и программ анализа электронных цепей, N гос. регистрации 78001264.

В указанных НИР автор принимал участие в качестве научного руководителя.

Целью данной работы является:

— дальнейшее развитие теоретико-множественных методов анализа сложных цепей;

— разработка алгоритмов анализа, позволяющих моделировать исследуемые системы в общем виде, удобные для применения ЭВМ;

— формальное доказательство на основе классических положений теории цепей с применением в качестве математического аппарата коммутативной алгебры основных расчетных формул;

— разработка методов и алгоритмов анализа сложных схем, позволяющих организовать параллельные вычислительные процессы;

— решение задач анализа и реализации функций электрических цепей;

— применение структурно-топологических методов в анализе нелинейных цепей.

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

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

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

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

Методы исследования.

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

ной алгебр, теории радиотехники, автоматики и систем управления.

На защиту выносятся.

1. Алгоритмы анализа электрических цепей, представленных сигнальными графами.

2. Структурно-топологические методы и алгоритмы анализа цепей, представленных обобщенными сигнальными графами.

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

4. Моделирование электрических цепей с помощью структурно-топологического преобразования.

5. Вопросы анализа и реализации функций электрических цепей.

6. Структурно-топологические методы при анализе нелинейных цепей.

Практическая значимость и реализация результатов работы.

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

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

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

Основные алгоритмы, предложенные в работе, применялись при разработки прецизионных приборов метрологических комплексов в рамках хоздоговорных и Госбюджетных работ. Результаты работы используются в учебном процессе в курсовом и дипломном проектировании.

Лично автором поставлены, решены, разработаны и внедрены все задачи рассматриваемой в работе проблемы.

Апробация работы.

Основные положения работы докладывались, обсуждались и получили одобрение:

— на XV научно-технической конференции ХПИ в 1977 г. (г.Хабаровск);

— на республиканской научно-технической конференции по структурным методам повышения точности измерительных устройств и систем в 1972 г. (г. Киев);

— на всесоюзной конференции "Радиотехника, тонкие магнитные пленки, вычислительная техника" в 1973 г. (г. Красноярск);

— на научных семинарах факультета электронной техники ХГТУ в 1983-1987 г.г.;

— на научных семинарах Института проблем морских технологий ДВО РАН в 1988-1997 г.г.

Работа в полном объеме обсуждалась:

— на научно-техническом семинаре ОКБ ведущей организации ГНПП НЗПП с ОКБ, г.Новосибирск, 1996 г.;

— на расширенном научном семинаре факультета электронной техники

ХГТУ, г.Хабаровск, 1996 г.;

— на научном семинаре кафедры радиотехники ТГТУ, г.Томск, 1996 г.;

— на ученом совете ИПМТ ДВО РАН, г Владивосток, 1997 г.

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

1. Краткий обзор современных методов анализа

1.1. Основные понятия теории графов

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

Точное определение графа С? состоит в том, что задаются два множества (первое из них обязательно непустое) и предикат, указывающий, какую пару элементов первого множества соединяет тот или иной элемент второго, и обозначается1

С = (Х,Д;Е0,

где X = ф 0; Я = (X П Я = 0).

1 Здесь и далее, где нет специальных ссылок, обозначения и определения соответствуют [47].

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

Линейный граф, у которого каждое ребро ориентировано, называется направленным графом и обозначается

д = (х,щи)9

где й — множество дуг (ориентированных ребер). На рис. 1.1,1.2 даны примеры ненаправленного и направленного графов.

а

Рис. 1.3

Граф, содержащий как ребра, так и дуги, называется частично направленным графом (рис. 1.3) и обозначается

г^ о«/

Если X' С X ж Я' С Я — подмножества вершин и ребер графа С? = (X, Я; и), а II — предикат, индуцированный инцидентором на этих подмножествах, то граф О = (X , Я ; II) называется частью графа С.

Часть С?' = (X , Я ; {/) называется подграфом графа (2 = (Х,Я;11), порожденным подмножеством вершин X С X , если подмножество ребер Я С Я выбрано так, что при образовании части С' сохранены все те ребра С?, которые соединяют между собой сохраняемые вершины.

Часть графа О = (X, Я; II), в котором X = X, называется су-графом графа (2. Два графа С = (X, Я] и ) и <7 = (X ,Я ;11) называются изоморфными, если между их вершинами, а также между их ребрами можно установить однозначное соответствие

X <-»■ X , я<-> Я ,

сохраняю�