Алгоритм покрытия схем разнотипными модулями

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ.

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

 

 

Заочно-вечерний факультет.

Специальность: «Конструирование и технология электронных средств».

Лабораторные работы по МО САПР

 

 

                                                                           Выполнил студент группы: Рбзу-21                     

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

                                  

 

Ульяновск 2019

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

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

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

ОБЩИЕ СВЕДЕНИЯ О ЗАДАЧЕ ПОКРЫТИЯ

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

Построение цепи.

Математическая формулировка задачи

 

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

Допустим, схема состоит из множества элементов E = {e₁, e₂,…,e_n} и для каждого из элементов  известен тип функции F(e_i) (i = 1, 2,…, l), которую он реализует (усилитель, детектор, триггер, схема «И», «ИЛИ» и т.д.).

Набор модулей определяется библиотекой T = {T₁, T₂,…, T_n}.

Количественный состав схемы по типам элементов опишем вектором , в котором b_j – число элементов типа j. Состав модулей библиотеки опишем матрицей , в которой a_kj – число элементов типа j в модуле T_k. Отметим, что элемент схемы может быть реализован с помощью элемента того же типа, находящегося в одном из модулей библиотеки, либо с помощью элементов других типов. Например, элемент ИЛИ с двумя входами может быть реализован элементом ИЛИ с большим числом входов.

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

В качестве критериев оптимальности в задаче покрытия используют:

- суммарную стоимость модулей, покрывающих схему;

- общее число модулей в покрытии;

- число типов используемых модулей;

- число связей между модулями;

- число неиспользованных элементов в модулях.

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

Для оценки качества покрытия используют дополнительный критерий – коэффициент покрытия G = N/M, где N – число элементов в схеме, а M – число модулей (микросхем), которыми покрыта схема.

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

Пусть известны стоимости модулей каждого типа c_1,…, c_k,…, c_m. Если ввести целочисленные переменные x_k , определяющие число модулей типа k, которые необходимы для покрытия с минимальной стоимостью, задача сведется к минимизации функции

                                                (1.1)

при ограничениях

,                                          (1.2)

где j = 1, 2,…,l, a_kj - число элементов типа j в T_k.

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

                    (1.3)

x_k – целое число для всех k, так как любой модуль используется только полностью, независимо от числа задействованных в нем компонентов.

Задача (1.1) – (1.3) является задачей целочисленного программирования.

Целевая функция для минимизации стоимости и числа модулей имеет вид:

,

где r₁ и r₂ – коэффициенты, учитывающие важность используемых критериев.

Алгоритм покрытия схем разнотипными модулями

 

Рассмотрим решение этой задачи при условии, что каждый элемент схемы l_i реализуется элементом того же типа в модулях набора T. В качестве дополнительного критерия при компоновке примем число межмодульных соединений. Решение задачи разобьем на два этапа:

1) Определение необходимого числа модулей с минимальной суммарной стоимостью.

2) Минимизация числа связей между модулями.

а) Допустим, что каждый из модулей T содержит элементы одного типа k, тогда минимальное число модулей для покрытия схемы, определяющее и минимальную стоимость покрытия, равно

,                                  (1.4)

где а_к – число элементов в модуле T_k; b_k – число элементов типа k в схеме; { } – символ ближайшего большого целого; x_k – число использованных модулей типа k. Отметим, что для модулей с однотипными элементами получаем квадратную матрицу , причем a_k = 0 при , и .

б) Практический интерес представляют наборы модулей с разнотипными элементами.

Пусть известны:

1) Библиотека типовых элементов, содержащая m типов интегральный микросхем (ИМС). Общее число типов элементов в ИМС библиотеки l. Тогда библиотеку зададим матрицей вида .

2) Электрическая схема узла, состоящая из соединения элементов одинаковых типов. Зададим схему вектором .

 

АЛГОРИТМ 1

 

1. Составить вектор  количественного состава схемы по типам элементов: .

2. Упорядочить модули (микросхемы) T_k библиотеки по возрастанию их стоимостей:

.

3. Составить матрицу  описания состава библиотеки в соответствии с их стоимостью; .

4. Выполнить поэлементное деление вектора  на строку  матрицы A:

 для , .

5. Найти  и на данном шаге использовать  модулей типа k.

6. Найти вектор непокрытых элементов

, где ; .

7. Если элементы , перейти к , если , перейти к .

8. Определить количество использованных ячеек каждого типа

 (  – определяет число итераций) и вычислить их суммарную стоимость: .

Конец.

Расчет.

1) Создаем исходный вектор (2,2,2,2,2,2)

2) Создаем матрицу А

 2 0 0 1 0 0

А=   0 2 0 0 1 0

0 0 2 0 0 1

3)Выполним поэлементное деление вектора  на строку  матрицы A. В делении участвуют только значащие числа, а в результатах делений учитываются только целые части

.

Выбираем одну ИМС Т1

 

Вектор непокрытых элементов

 

 Снова  выполним поэлементное деление

Выбираем одну ИМС Т2

Вектор непокрытых элементов

 

 

Снова выполним поэлементное деление

Выбираем одну ИМС Т3

Вектор непокрытых элементов

 

 Результат не равен нулю. Снова выбираем самую дешевую ИМС и просчитываем покрытие

0,5≈1 Выбираем одну ИМС Т1

Вектор непокрытых элементов

 

 Остались еще не покрытые элементы, продолжаем покрытие ИМС Т2

Выбираем одну ИМС Т2

Вектор непокрытых элементов

 

 

Выбираем одну ИМС Т3

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

 

Рис.1 исходный вектор и матрица.

 

 

 

 

Рис 2. Схема, составленная из выбранных элементов.

 

Результаты: 1) Мы видим,что при ручном расчете,так же как и при автоматическом мы имеем 6 ИМС разных типов. Сумарная стоимость их равна 12. Коэффициент покрытия равен

G=N/M= 2.0

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

 

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

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

схем радиоэлектронных средств.

Коэффициент разбиения 7:4 (8 элементов)

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

 

---

Дата добавления: 2019-07-17; просмотров: 293; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!