Разбиение функциональных элементов по корпусам микросхем
Стр 1 из 3Следующая ⇒
Общее описание алгоритма. Общая схема процесса последовательной компановки по связности имеет следующий вид. Пусть дана схема соединения элементовов множеств
Определим последовательный процесс назначения элементов
в узлы Br( Узел считается завершенным, если число элементов в узле равно зачетному числу K. После завершения очередного узла аналогичная процедура повторяется для следующего узла, причем кандидатами для назначения являются элементы не включенные в предыдущие узлы. Процесс заканчивается когда все элементы из множества E распределены. Исходные данные являются: -электрическая схема устройства. -максимально допустимое число элементов в модуле. Электрическую схему удобно представлять графом G=(E,V), где множество вершин Е соответствует элементам эл-ой схемы, а множество ребер V –эл-ким связям между элементами. В таком виде задача компоновки может быть сформулирована как задача разрезания графа G=(E,V) на множество подграфов
Gr=(Er,Vr),где r=1,2,3…
В каждом подграфе число вершин соответственно Er должно не превосходить ранее заданного ограничения на число элементовов в узле К. Для любого разбиения должны выполняться следующие условия:
При проведении компоновки без учета ограничения на кол-во внешних выводов в узле все модули, кроме последнего, будут иметь полное заполнение. и последнее условие примет вид
Пошаговое описание алгоритма. Шаг 1. Формирование очередного подграфа Gr(r=1,2,3…
Базовая вершина будет первой по порядку вершиной подграфа Gr(Er,Vr), а оставшиеся вершины, принадлежащие множеству Базовая вершина Шаг 2. Из множества Для эл-та X
L(x)=
определяющий число цепей, связывающих вершину X и вершины из множества Г и Ir\
где Шаг 4. Из всех вершин Множество вершин подграфа Gr приобретает следующий вид:
где Шаг 5. Происходит стягивание вершин подграфа Gr в вершину Центр факторизации со степенью факторизации После данного процесса множество
В указанных обозначениях первый процесс факторизации запишется следующим образом:
В общем случае на
Шаг 6. Действия описанные в шагах 2,3,4,5, повторяются до полного заполнения формируемого модуля. Далее весь процесс повторяется до тех пор, пока не будет сформирован (
Выполнение компоновки. В данной электрической функциональной схеме элементы типа И-НЕ заменим элементами 2И-НЕ, в целях уменьшения количества микросхем и себестоимости платы. Данную электрическую функциональную схему разбиваем на 3 блока. Далее выполняем компоновку для каждого блока, для чего представляем их в виде графов, где множеству вершин соответствуют элементы электрической схемы блока, а множество ребер электрическим связям между этими элементами. Расчеты для первого блока: Чертим граф для элементов типа 3И-НЕ:
Рис.1
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|