Покрытие функциональных схем функционально-типизированными узлами (модулями) из данного набора

Страницы работы

6 страниц (Word-файл)

Содержание работы

Федеральное агентство по образованию

Государственное образовательное учреждение высшего

профессионального образования

  « Владимирский государственный университет»

Факультет радиофизики, электроники и

медицинской техники

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

Лабораторная работа № 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.

Вывод: ______________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

___________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________


Похожие материалы

Информация о работе

Тип:
Задания на лабораторные работы
Размер файла:
320 Kb
Скачали:
0