Исследование эффективности алгоритма компоновки схем радиоэлектронных средств

Размещено на http://www.allbest.ru/

Ульяновский государственный технический университет

Кафедра «Проектирования и технологии электронных средств»

Лабораторная работа

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА КОМПОНОВКИ СХЕМ РАДИОЭЛЕКТРОННЫХ СРЕДСТВ

Студент гр. Шермонов В.В.

Преподаватель: Мактас М.Я.

Ульяновск 2014

Введение

Цель работы - исследовать эффективность последовательного метода компоновки конструктивных элементов и узлов РЭС в узлы высшего уровня; усвоить особенности алгоритмизации и программирования задачи компоновки конструктивных элементов на ПЭВМ; приобрести навыки построения математических моделей объектов конструирования, реализации и исследования их при решении задачи компоновки в САПР.

1. Общие сведения о задаче компоновки

В настоящее время в радиоэлектронике принят функционально-узловой метод проектирования [1 - 7]. Он предусматривает расчленение радиоэлектронных средств (РЭС) на отдельные конструктивно законченные единицы (модули) различных уровней (рангов). Это могут быть отдельные платы - типовые элементы замены (ТЭЗы), функциональные узлы, субблоки, блоки, панели, пульты, стойки. В связи с этим при разработке конструкций РЭС проектировщик неизбежно сталкивается с задачей распределения элементов схемы низшего уровня по коммутационным пространствам модулей данного уровня иерархии. При ее решении основным критерием оптимальности компоновки модулей является минимизация числа межмодульных связей, что необходимо для повышения надежности схем (за счет уменьшения числа разъемных соединений), уменьшения влияния наводок и времени задержки сигнала в цепях (вследствие минимизации суммарной длины соединений), упрощения конструкции и повышения технологичности разрабатываемого устройства.

Последовательные алгоритмы компоновки

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

Метод максимальной конъюнкции - минимальной дизъюнкции

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

Рассмотрим метод максимальной конъюнкции - минимальной дизъюнкции [1, 4].

Пусть дана схема с множеством элементов

,

соединенных между собой множеством электрических цепей

.

Ее необходимо скомпоновать в узлы, включающие по t элементов. Число внешних связей узлов не должно превышать z (z - число контактов в разъеме).

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

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

При работе алгоритма схема представляется в виде графа Кенига , в котором подмножество вершин E и V интерпретируют соответственно множества элементов E и электрических цепей V. При этом вершина соединяется с вершиной ребром в том случае, когда элемент принадлежит цепи . Для вычисления на ЭВМ граф задается матрицей инцидентности , в которой число строк n определяется количеством элементов схемы, а столбцов m - количеством электрических цепей. Элемент , стоящий на пересечении iй строки и jго столбца, равен 1, если элемент подключен к цепи , и нулю в противном случае.

АЛГОРИТМ

1. Ввод матрицы .

2. По матрице определяем локальные степени вершин :

.

3. Из множества нераспределенных вершин E выбираем вершину с локальной степенью

.

4. Назначаем выбранную вершину во множество , формируемого узла.

5. Строку матрицы , соответствующую назначенной вершине , модифицируем путем поразрядной дизъюнкции со строками матрицы, соответствующими нераспределенным элементам:

; ;…

6. Определяем суммы элементов в модифицированных строках

.

7. Из множества строк выбираем такие, в которых . Объединяем их во множество .

8. Если , то переходим к 17, иначе к 9.

9. Строку матрицы , соответствующую элементу , модифицируем путем поразрядной конъюнкции со строками множества :

;…

10. Определяем суммы элементов в модифицированных строках .

11. Из множества строк выбираем такую, в которой .

12. Вершину , дающую назначаем в формируемый узел .

13. Если , то идти к 17, иначе к 14.

14. Определяем множество нераспределенных элементов . Если , то идти к 19, иначе к 15.

15. Составляем матрицу . Для чего в исходной матрице вместо строк, соответствующих элементам, назначенным в узел , записываем дизъюнкцию всех указанных строк.

16. Идти к 5.

17. Узел считаем сформированным. Поэтому преобразуем матрицу . Исключаем из нее строки, соответствующие элементам, включенным в узел . Получаем матрицу .

18. Идти к 2.

19. Конец.

Рисунок 1. Схема Электрическая Принципиальная.

Рисунок 1.1. Матрица инцидентности.

Практические решения:

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

Ручной рассчет

Решение

По матрице исходного графа определяем локальные степени вершин и приписываем их справа к каждой строке матрицы (число цепей, подключенных к каждому элементу схемы):

Q1=

Максимальную локальную степень, равную четырем, имеет вершина е_5,. В качестве исходной выбираем 5ю по порядку е₅. Выполним дизъюнкции 5й строки q₅, соответствующей е₅, с остальными строками:

Сумма элементов в дизъюнкции c(q₅₁)= 6

Находим суммы элементов в дизъюнкциях:

c(q₅₁)= 5, c(q₅₂)= 7 ,c(q₅₃)=5 ,

c(q₅₄)= 6 ,c(q₅₆)= 6, c(q₅₇)= 7, c(q₅₈)= 5 ,c(q₅₉)= 6, c(q₅₁₀)= 6, c(q₅₁₁)= 6, с(q₅₁₂₎=6 .

Выбираем вершины, имеющие , и включение которых в формируемый узел не превысит условия z?5. Такими являются вершины е₃ и е₈. Выполним конъюнкцию 5й строки со строками отобранных элементов е_3, е_8.

Сумма элементов в коньюнкции S(b₅₃) = 1

Вычисляем суммы элементов в конъюнкциях S(b₅₈)=0.

Выбираем вершину е₃, величина S(b₅₃)=1 у которой максимальна и минимальное число выводов z=4 и включаем ее в узел T₁={e₅,e₃}.

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

Для этого модифицируем матрицу .

Вместо 5й и 3й строк в ней запишем дизъюнкцию этих строк.

Получим матрицу Q₂:

Q2=

Снова вычисляем дизъюнкции строки (5 v 3) со всеми остальными и определяем суммы элементов в них.

Результаты суммирований запишем справа от каждой строки матрицы . Минимальную c(q_(53)k)=6 имеют e₂=8,e_8,е₉=6, e_1,е₄,e₆,e₇,e₁₀,e₁₁,e₁₂=7. После выполнения конъюнкции строки (5 v 3) со строками отобранных элементов е_8, е₉.

Справа от матрицы запишем . Максимальное значение =1 имеют вершины e₉

Вершину e₉ включаем в узел : T₁={e₃,e₅,e₉}.

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

Для этого модифицируем матрицу .

Вместо 9й , 5й и 3й строк в ней запишем дизъюнкцию этих строк.

Q₃₌

Минимальную c(q_(8)k)=7 имеет остальные по 9_. e₂=10, e₁₁=8_{. П}осле выполнения конъюнкции строки (5 v 3) v 9 с остальными строками и суммирования элементов в результирующих строках получим:

Максимальное значение S(b_(539)k)=1

Ее и включаем в узел : T₁={e₃,e₅,е₆,e₉}.

Итак, узел сформирован, поскольку в него назначено четыре элемента.

Аналогично формируем второй узел , рассматривая оставшиеся вершины. E_f = E/T₁={e₁,e₂,e₄,e₇,e₈,e₁₀,e₁₁,e₁₂} Для этого из исходной матрицы исключаем строки, соответствующие элементам e₃,e₅,e₆,e₉.

Получим: Q₄ =

Максимальную локальную степень, равную трем, имеют вершины e_2, e_9, e₁₀. В качестве исходной выбираем 2ю по порядку e₂.

Выполним дизъюнкции 2й строки q₂, соответствующей e₂, с остальными строками:

Находим суммы элементов в дизъюнкциях: c(q₂₁)=4, c(q₂₄)=5, c(q₂₇)=6, c(q₂₈)=4, c(₁₀)=5, c(q₁₁)=5, c(q₁₂)=5.

Выбираем вершины, имеющие , и включение которых в формируемый узел не превысит условия z?4. Такой является вершина e_1, e₈ у которой c(q_jk)?4.

Выполним конъюнкцию 2й строки со строками отобранных элементов e_1,e₈:

Вычисляем суммы элементов в конъюнкциях S(b₂₁)=1, S(b₂₈)=0. Выбираем вершину e₁, величина S(b₂₁)=1 у которой максимальна, и включаем ее в узел T₂={e₂,e₁}.

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

Для этого модифицируем матрицу .

Вместо 1й и 2й строк в ней запишем дизъюнкцию этих строк.

Получим матрицу Q₅:

Снова вычисляем дизъюнкции строки 2 v 1 со всеми остальными и определяем суммы элементов в них.

Результаты суммирований запишем справа от каждой строки матрицы . Минимальную c(q(_8)k)=5 имеет e₈. После выполнения конъюнкции строки 2 v 1 с остальными строками и суммирования элементов в результирующих строках получим:

Справа от матрицы запишем . Максимальное значение S(b_(7)k)=1, S(b₍₁₀₎)=1 имеют вершины e₇, e₁₀. е₇ включаем в узел : T₂={е₂,e₁,e₇}.

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

Для этого модифицируем матрицу .

Вместо 1й , 2й и 7й строк в ней запишем дизъюнкцию этих строк.

Q₆=

Минимальную c(q(_217)k)=7 имеют e_8. После выполнения конъюнкции строки (2v1)v7 с остальными строками и суммирования элементов в результирующих строках получим:

Максимальное значение S(b_(127)10)=1,

Ее и включаем в узел : T₂={e₂,e₁,e₇,e₁₀}.

Итак, узел сформирован, поскольку в него назначено четыре элемента.

Аналогично формируем второй узел , рассматривая оставшиеся вершины. E_f = E/T₂={е₄,e₈,e₁₁,e₁₂} Для этого из исходной матрицы исключаем строки, соответствующие элементам. Получим:

Q7 =

Максимальную локальную степень, равную двум, имеют все вершины, кроме e₈ . В качестве исходной выбираем 1ю по порядку e₄. Выполним дизъюнкции 1й строки q₄, соответствующей e₄, с остальными строками:

Находим суммы элементов в дизъюнкциях: c(q₄₈)=3, c(q₄₁₁)=3, c(q₄₁₂)=3,

Выбираем вершины, имеющие , и включение которых в формируемый узел не превысит условия z?5. Такими являются вершины e_8, e₁₁ и e₁₂ , у которых 3.

Выполним конъюнкцию 1й строки со строками отобранных элементов q_8,q₁₁,q_12, :

Вычисляем суммы элементов в конъюнкциях. S(b₄₈)=0, S(b₄₁₁)=1, S(b₄₁₂)=1. Выбираем вершину e₁₁, величина S(b₄₁₁)=1 у которой максимальна, и включаем ее в узел. T₂={e₄,e₁₁} .

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

Для этого модифицируем матрицу .

Вместо 4й и 11й строк в ней запишем дизъюнкцию этих строк.

Получим матрицу Q₈:

Q8=

Снова вычисляем дизъюнкции строки (4v11) со всеми остальными и определяем суммы элементов в них. Результаты суммирований запишем справа от каждой строки матрицы . Минимальную c(q(_4118)k)=4 имеют e₈, e₁₂. После выполнения конъюнкции строки (4v11) с остальными строками и суммирования элементов в результирующих строках получим:

Результаты суммирований запишем справа от каждой строки матрицы . Минимальную c(q(_4118)k)=4 имеют ...