Федеральное агентство по образованию
Государственное образовательное учреждение высшего
профессионального образования
« Владимирский государственный университет»
Факультет радиофизики, электроники и
медицинской техники
Кафедра конструирования и технологии радиоэлектронных средств
Лабораторная работа № 1
по дисциплине «Физические основы микроэлектроники».
Выполнил Ст. гр. Р-107
Проверил
Владимир 2009
Краткие теоретические сведения
Задачи разбиения схем делятся на два класса:
1) покрытие функциональных схем функционально-типизированными узлами (модулями) из данного набора;
2) разбиение электрических схем на подсхемы, реализуемые конструктивными узлами, в которых функции преобразования сигналов не задаются.
Точное решение может быть получено с помощью метода ветвей и границ, приближенное значение дают эвристические алгоритмы, которые группируются в 3 класса: последовательные, итерационные (алгоритмы парных перестановок и обобщенный алгоритм парных перестановок), дихотомического деления.
Разбиение схемы на подсхемы – это распределение элементов схемы по конструктивным узлам.
Критерии качества:
1) число междузловых соединений;
2) минимум числа узлов;
3) минимум числа типов узлов;
4) фундаментальная законченность узла.
Ограничения:
1) вместимость узла;
2) число внешних выводов узла.
Алгоритмы разбиения схем:
1) последовательный алгоритм;
2) итерационный;
3) точный;
4) дихатомический.
Критерии сравнения алгоритмов:
1) быстродействие;
2) точность;
3) сложность:
- полиномиальной сложности;
- алгоритмы экспоненциальной сложности.
Самый быстрый алгоритм – последовательный. Для итерационного алгоритма требуется начальное разбиение схемы: либо в ручную, либо с помощью последовательного алгоритма.
Модель схемы – гиперграф, взвешенный по вершинам. Погрешность представления элементов – вершин гиперграфов заключается в том, что учитывается их площадь.
Критерии качества покрытия схем:
1) минимальная стоимость покрытия;
2) минимальное число израсходованных узлов в покрытии;
3) минимальное число типов узлов покрытия;
4) минимальное число межузловых соединений.
Рис.1. Схема программы DECOM-3
Выполнение работы
Входные данные:
Количество элементов схемы Е = 27;
Число электрических цепей схемы H = 90;
Число внешних цепей схемы V = 14;
Число выводов элементов B = 14;
Максимальная вместимость узла G = 8;
Максимальное число внешних цепей узла W = 21.
Массив данных, занесенных в файл BDP.DEC, имеют вид:
27 90 14 14 8 21
15 15 16 15 15 16 0 49 19 19 19 18 18 0
79 79 41 41 40 80 0 87 16 16 35 17 17 0
41 80 80 40 56 82 0 84 83 81 82 81 49 0
85 85 86 27 3 38 0 85 83 83 83 84 49 0
0 86 20 20 20 22 0 21 20 20 20 20 20 0
0 86 20 20 20 24 0 23 20 20 20 20 20 0
0 86 20 20 20 26 0 25 27 27 27 23 20 0
0 86 27 27 27 28 0 27 27 27 27 25 27 0
0 37 27 27 27 31 0 30 27 27 27 25 27 0
0 37 34 34 34 33 0 32 34 34 34 30 34 0
0 37 32 34 34 36 0 29 34 34 34 30 34 0
21 21 1 22 22 2 0 3 23 23 4 24 24 0
25 25 5 26 26 6 0 7 27 27 8 28 28 0
30 30 9 31 31 10 0 11 32 32 12 33 33 0
29 29 13 36 36 14 0 37 85 85 0 0 0 0
41 42 45 45 45 47 0 48 46 46 46 43 44 0
49 49 76 49 48 77 0 40 38 39 39 1 4 0
0 77 74 74 74 0 0 75 74 74 74 76 74 0
49 67 78 78 78 90 0 89 78 78 88 75 73 0
3 5 9 11 13 51 0 59 7 10 13 50 7 0
50 50 52 52 1 53 0 54 53 55 55 51 51 0
1 3 57 57 57 62 0 56 54 54 58 12 13 0
61 62 66 66 66 67 0 42 65 65 65 62 63 0
7 9 5 8 14 68 0 61 58 59 60 60 14 0
1 3 2 4 6 71 0 44 71 12 69 69 5 0
61 61 64 64 63 63 0 43 63 63 73 44 44 0
8 14 10 10 10 12 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
15 18 20 27 34 41 55 79 85 87 88 89 90 35
Выходные данные (файл BDP.DER) имеют вид:
Число сформированных узлов:
4
Массив элементного состава узлов:
20 24 27 14 22 21 25 13
4 3 2 17 12 5 6 7
19 18 1 23 26 16 8 9
11 10 15 0 0 0 0 0
Массив межузловых соединений:
3 25 30 31 13 55 26 27 32 2 14 61 1 4 33 62 56 28 44 0 0
85 86 27 3 76 41 79 49 48 56 87 16 35 77 1 4 20 26 2 25 0
49 61 90 89 88 77 41 76 15 16 18 62 48 44 86 27 28 25 37 31 30
37 32 34 13 14 30 33 85 0 0 0 0 0 0 0 0 0 0 0 0 0
Результат разбиения приведен на рис. 2.
Вывод: ______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.