Навигация
Дальнейшее исследование возможных вариантов размещения
20857
знаков
11
таблиц
19
изображений
4. Дальнейшее исследование возможных вариантов размещения.
Во время исследования отсекаются бесперспективные варианты решения (те варианты, у которых нижняя оценка больше верхней границы).
Приведем полученное дерево:
4. Минимизация длины связей между контактами разъема и контактами внешних цепей
На данном этапе необходимо используя Венгерский алгоритм минимизировать длины связей между контактами разъёма и контактами внешних цепей.
Назначение осуществляется в полуавтоматическом режиме с помощью «Венгерского алгоритма» (с использованием программы VENGR.EXE).Структурная схема «венгерского алгоритма» показана на рисунке 7.
Рисунок 9 – структурная схема венгерского алгоритма.
1 блок – начальное преобразование матрицы эффективности в эквивалентную матрицу. Для этого из каждой строки вычитается минимальный элемент.
2 блок – в полученной матрице эффективности помечаются нули, образующие правильное решение, таким образом, чтобы в каждой строке и столбце было не более одного помеченного нуля.
3 блок – проверка: получен ли полный правильный выбор нулей. Выбор нулей называется полным, если помечено нулей, где – размерность матрицы. Если получен полный правильный выбор, то – к выходу, если «нет», то к блоку 4.
4 блок – помечаем «+» столбцы, в которых есть нули со «*». Таким образом помечаем все ребра, инцидентные вершинам. Каждый «+» соответствует вершине.
5 блок – проверка: есть ли в матрице незанятые нули. Нуль называется незанятым, если его строка и его столбец не помечены «+».
6 блок – помечаем незанятый нуль «/».
7 блок – проверка: есть ли в строке нуля, помеченного «/» в блоке 6 нуль со «*», если «да», то переход в блок 8.
8 блок – если в строке есть нуль со «*», то снимаем «+» со столбца, в котором он находился, а строку помечаем «+».
9 блок – если нуля со «» в строке нет, то это означает, что можно увеличить количество нулей со «*» на 1. Строится расширяющая цепочка, начиная с последнего помеченного нуля (блок 6): переходим по столбцу к нулю со «», по строке к нулю со «/», по столбцу к нулю со «*», пока цепочка не прервется. Возможно, что цепочка прервется сразу.
10 блок – в результате процедуры в блоке 9 образовалась цепочка, состоящая из нулей со «/» и нулей со «», но нулей с «/» на 1 больше. Если теперь в цепочке снять с нулей «», а «/» заменить на «*», то нулей со «*» станет на 1 больше. Снимаем все метки, кроме «» и переходим к блоку 2.
11 блок – выполняется эквивалентное преобразование матрицы с целью увеличения количества нулей. Если в блоке 5 свободных нулей не найдено, то надо их добавить – для этого в незанятых строках, не помеченных «+» находится минимальный элемент, больший нуля hmin. Вычитаем hmin из элементов всех строк, не помеченными «+» и прибавляем ко всем элементам строк столбцов, помеченных «+».
Исходными данными для работы алгоритма является матрица эффективности назначений, для ее вычисления мы должны построить матрицы R и D (связей и расстояний соответственно) и получить все элементы матрицы эффективности назначений по формуле:
Cij = ri, 1di, 1 + ri, 2di, 2 + … + ri, j-1di, j-1 + ri, jdi, j, где i, j – номера строки и столбца, на пересечении которых находится элемент. В нашем случае программа сама рассчитывает матрицу эффективности назначений. Исходными данными для нее служит матрица, отражающая координаты выводов микросхем и разъема.
Первоначальное подключение цепей к контактам разъема
Первоначальное подключение берется из задания, также вычисляется суммарная оценка длины проводников, определяющая качество данного назначения выводов разъема.
| № вывода разъема | № проводника, подключаемого к разъему |
| 1 | 4 |
| 2 | 8 |
| 3 | 12 |
| 4 | 20 |
| 5 | 16 |
| 6 | 24 |
| 7 | 28 |
| 8 | 2 |
| 9 | 27 |
| 10 | 15 |
| 11 | 7 |
| 12 | 17 |
Оценка длины проводника подключаемого к разъему – длина цепи, включающей все выводы элементов и вывод разъема с одинаковыми номерами.
Пример расчета оценки длины проводника для 1 вывода разъема.
1. Исходя из эскиза печатной платы (см Приложение 2) находятся координаты выводов подключенных к 1-му выводу разъема и координаты самого вывода разъема. Разъем: (97,5; 50), вывод 1 (0; 0) вывод 2 (12,5; 0)
2. Аналитически находится оптимальная последовательность подключения выводов к разъему. Последовательность: вывод 1 – вывод 2 – разъем.
3. Расчет оценки длины проводника
4. Аналогично рассчитываются остальные оценки длин.
Такое подключение, возможно, не является оптимальным, для оптимизации первоначального подключения цепей к разъему применяются алгоритмы линейного назначения. В данной курсовой работе используется программа, основанная на венгерском алгоритме. Для получения матрицы назначений в программе требуется заполнить следующую таблицу (см рис 6).
Рис. 10. Исходные данные программы оптимизации подключения цепей к разъему
Алгоритм заполнения таблицы.
1. Согласно имеющимся данным по микросхеме К155ЛА4 (Рис. 11 и Рис. 12) и данным по компоновке логических элементов в блоки составляется соответствие выводов каждого блока и вывода корпуса.
2. Согласно данным по размещению (Раздел 2) составляется эскиз печатной платы с размещенными на ней корпусами микросхемы (см Приложение 2). Выбирается произвольная точка, которая служит началом координат
|
|
|
| Рис. 11. Корпус микросхемы | Рис. 12. Соответствие логических выводов микросхемы выводам корпуса |
Похожие работы
... (ШД), адресов (ША) и управления (ШУ). Однокристальные микропроцессоры получаются при реализации всех аппаратных средств процессора в виде одной БИС или СБИС (сверхбольшой интегральной схемы). По мере увеличения степени интеграции элементов в кристалле и числа выводов корпуса параметры однокристальных микропроцессоров улучшаются. Однако возможности однокристальных микропроцессоров ограничены ...
... : ¾ температура, °С +25±10; ¾ относительная влажность воздуха, % 45...80; ¾ атмосферное давление, мм рт. ст. 630...800. Так как блок интерфейсных адаптеров предназначен для работы в нормальных условиях, в качестве номинальных значений климатических факторов указанные выше принимают нормальные значения ...
... мероприятия по обеспечению однородности выпускаемой продукции. Все эти мероприятия можно объединить в четыре группы: 1. совершенствование технологии производства; 2. автоматизация производства; 3. технологические (тренировочные) прогоны; 4. статистическое регулирование качества продукции. 2.10. Проектирование технологических процессов с использованием средств ...
... . Целью дипломного проекта является разработка и исследование автоматической системы регулирования (АСР) асинхронного высоковольтного электропривода на базе автономного инвертора тока с трехфазным однообмоточным двигателем с детальной разработкой программы высокого уровня при различных законах управления. В ходе конкретизации из поставленной цели выделены следующие задачи. Провести анализ ...
0 комментариев