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

4. Дальнейшее исследование возможных вариантов размещения.

Во время исследования отсекаются бесперспективные варианты решения (те варианты, у которых нижняя оценка больше верхней границы).

Приведем полученное дерево:

357 src="images/referats/11128/image013.png">

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

 Скачать реферат