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 вывода разъема.

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). Выбирается произвольная точка, которая служит началом координат

5.                  Согласно полученному эскизу печатной платы каждому выводу корпуса назначается своя координата относительно начала координат.

Рис. 13 Матрица D до начала выполнения алгоритма венгра

Рис. 13 Матрица D после выполнения алгоритма венгра

Результат выполнения программы – более оптимальное подключение цепей к контактам разъема.

Проведем проверку длин цепи до и после переназначения вывода разъема.

Рассмотрим цепь №17

До переназначения выводов: L=95+38=133 мм

После переназначения выводов: L=95+12=107 мм

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

5. Трассировка электрических соединений контактов элементов

Используя результаты предыдущих разделов (компоновка, минимизация расстояний), перечертим принципиальную схему используя редактор Schematic (результат представлен в приложении 3). Далее выполняем команду utils/ Generate NetList… После чего запускаем редактор PCB, в котором чертим контур платы, подключаем нужные библиотеки, в нашем случае mai.lib, после чего выполняем команду utils/ Load NetList… Появившиеся элементы расставляем в соответствии с результатами полученными в разделе 3. Использую команду Route/ Autorouters, в появившемся окне выбираем тип трассировки Quick route и нажимаем кнопку Start. Результаты трассировки представлены в приложении 4.

Выводы

В ходе выполнения курсовой работы был пройден весь путь разработки функциональной цифровой ячейки от функциональной логической схемы проектируемого узла до печатной платы узла. Были приобретены практические навыки применения алгоритмов и методов автоматизированного проектирования РЭС, закреплены теоретические знания.

Решение задачи компоновки позволило сократить количество внешних связей между блоками (корпусами микросхем) за счет увеличения количества внутренних (внутри блока) связей.

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

В результате решения задачи назначения выводов элементов схемы и разъема каждый элемент закреплен в конкретную позицию, что отображено в «схеме соединения выводов».

Результатом работы программы-трассировщика является 2-х слойная печатная плата.

Страницы: 1, 2, 3