close

Вход

Забыли?

вход по аккаунту

?

ммм

код для вставкиСкачать
ВВЕДЕНИЕ
Основные задачи развития технологии электрического монтажа - это увеличение плотности компоновки элементов, обеспечение режима согласования линий связи и равномерного распределения потенциалов питания между активными элементами электронных устройств. Автоматизация проектирования изделий электронной техники, исходя из степени однородности задач и методов их решения в процессе проектирования изделия, подразделяется на следующие четыре этапа:
системотехническое проектирование, при котором выбираются и формулируются цели проектирования, формируется структура будущего изделия, определяются его основные технико-экономические характеристики;
функциональное (схемотехническое) проектирование, в ходе которого выбирается функционально-логическая база, разрабатываются принципиальные электрические схемы изделий электронной техники в целом и ее составных частей, оптимизируются ее параметры;
техническое (конструкторское) проектирование, которое решает задачи синтеза конструкций изделия в целом, определяет компоновку и размещение, разрабатывает топологию электрических соединений;
проектирование технологических процессов, которое предусматривает определение состава технологического оборудования для изготовления печатной платы, подготовку необходимых организационно-технических мероприятий, связанных с обеспечением функционирования технологических линий изготовления печатных плат, и разработки правил подготовки проекта печатной шиты для ее изготовления в единичном, мелкосерийном и крупносерийном вариантах.
ПОКРЫТИЕ ЭЛЕКТРИЧЕСКОЙ СХЕМЫ И КОМПОНОВКА МОДУЛЕЙ МИКРОСХЕМЫ ПРИ ПОМОЩИПОСЛЕДОВАТЕЛЬНОГО АЛГОРИТМА КОМПОНОВКИ
Покрытие электрических схем
При переходе от схемы функциональной к схеме электрической принципиальной необходимо решать задачи покрытия схем, то есть анализа схем. При решении этой задачи учитывается назначение модулей на схеме функциональной, вид и связи используемых микросхем. Основными критериями покрытия схем являются:
число типов модулей микросхем, используемых в схеме.
число однотипных модулей, входящих в микросхему.
число микросхем, необходимых для покрытия исходной схемы.
Общее описание алгоритма
Компоновка электрической схемы на конструктивно законченные части - это процесс распределения элементов низшего конструктивного уровня в высший в соответствии с выбранным критерием. В общем виде при описании алгоритма компоновки удобно использовать теорию графов, при этом электрическая схема представляется ненаправленным мультиграфом, вершинами которого являются отдельные модули, а ребрами связи между модулями. Тогда задача компоновки формируется следующим образом. Задан мультиграф (вся схема), требуется разбить его на подграфы так, чтобы число ребер, соединяющее эти подграфы, было минимально, то есть скомпоновать модули в микросхемы таким образом, чтобы наиболее связанные модули были в одной микросхеме, а связи между микросхемами минимизировать. В общем виде задача разбиения графа на подграфы записывается следующим образом:
U_i=(X_i,U_i) (1.1)
В каждом графе число вершин не должно превосходить ранее заданного ограничения на число модулей в микросхеме. Для любого разбиения должны выполняться условия:
⋃_(i=1)^n▒G_i =G_0; (1.2)
⋂_(i=1)^n▒〖G_i=∅〗; (1.3)
∑_(i=1)^n▒X_i =|X|(1.4)
Пошаговое описание алгоритма
Шаг 1. Проанализировав функциональную схему и выполнив задачи покрытия схемы, разбиваем эту схему на отдельные узлы, соединяющие однотипные модули, причем связи между модулями данного узла сохраняются, а связи к другим узлам не учитываются.
Шаг 2. Каждый модуль принимаем за вершину графа и составляем граф схему для отдельного узла.
Шаг 3. По граф схеме составляем матрицу смежности и подсчитываем степень каждой вершины. Шаг 4. Формирование отдельных микросхем начинается с выбора базовой вершины. Такой вершиной является вершина, имеющая максимальную степень:
p^* (x_i)=maxp(x). (1.5)
Если несколько вершин имеют одинаковую максимальную степень, то за базовую принимают вершину с максимальным числом кратных ребер. Если таких вершин несколько, то за базовую вершину принимается вершина с минимальным индексом. Если нет вершин имеющих кратные ребра, то за базовую принимается вершина, имеющая максимальную степень и наименьший индекс.
Шаг 5. Из множества вершин Xi выделяем подмножество вершин связанных с базовой, то есть находим отображение базовой вершины.
Шаг 6. Вычисляем функционал для вершины, связанной с базовой по формуле:
L_j=p^* (x_i )-α_ij, (1.6)
где p^* (x_i )- степень базовой вершины, α_ij - число связей базовой вершины x_i с вершиной x_j. Шаг 7. Выбираем вершину, имеющую минимальный функционал и стягиваем ее с базовой вершиной. Если несколько вершин имеют одинаковые минимальные функционалы, то выбираем вершину с наименьшим индексом.
Шаг 8. Составляем новый граф и матрицу смежности, заменяя вершины Xiи Xjодной вершиной Xij. Базовой считается вершина Xij.
Шаг 9. Повторяем шаги 5, 6, 7 и 8 до тех пор, пока не будет скомпонована микросхема.
Шаг 10. Приступаем к формированию нового подграфа (микросхемы)
со второго шага, убрав сформированную микросхему.
Шаг 11. Повторяем алгоритм компоновки до тех пор, пока все модули узла не будут скомпонованы в микросхемы.
Шаг 12. По вышеописанному алгоритму компонуем все узлы схемы.
Выполнение компоновки
Данную электрическую функциональную схему разбиваем на 3 отдельных функциональных узла (рисунки 1.1, 1.2, 1.3), включающих одинаковые модули микросхем, причем связи между модулями данного узла сохраняются, а связи с другими узлами не учитываются.
Рисунок 1.1 - Первый функциональный узел
Рисунок 1.2 - Второй функциональный узел
Рисунок 1.3 - Третий функциональный узел
На схеме имеется три типа модулей, относящихся к микросхемам К155ЛР1, К155ЛА3 и К155ЛА4. На рисунке 1.4 представлено их условное графическое изображение:
К155ЛР1 К155ЛА4 К155ЛА3 Рисунок 1.4 - Условное графическое изображение микросхем
Приступаем к компоновке первого функционального узла. Микросхема К155ЛР1 содержит 2 модуля. Функциональный узел содержит 14 модулей и для него необходимо 7 микросхем, все будут заполнены полностью. Составляем граф схему для первого функционального узла на микросхеме К155ЛР1, петли не учитываем. Граф для первого блока изображен на рисунке 1.5:
Рисунок 1.5-Граф-схема первого функционального узла
По граф-схеме составляем матрицу смежности и подсчитываем степень вершины (Таблица 1.1):
Таблица 1.1 - Матрица смежности первого функционального узла:
X_1X_2X_3X_4X_5X_6X_7X_8X_9X_10X_11X_12X_13X_14∑РiX_10999999000000054*X_29099999000000054X_39909999000000054X_49990999000000054X_59999099000000054X_69999909000000054X_79999990000000054X_80000000023223214X_90000000202322314X_100000000320232214X_110000000232023214X_120000000223202314X_130000000322320214X_140000000232232014
Подсчитываем сумму степеней всех вершин и выбираем базовую вершину, которая имеет наибольшую сумму степени вершины. Так как таких вершин семь (X_1-X_7), то за базовую принимаем вершину с наибольшим числом кратных ребер. Так как таких вершин семь, то за базовую принимаем вершину с наименьшим индексом. Следовательно, вершине Х1 присваиваем позиционное обозначение DD1.1.
Находим отображение вершины X_1 : Г_(X_1 )={X_2,X_3,X_4,X_5,X_6,X_7}.
Вычисляем функционалы для вершин, связанных с базовой по формуле(1.6):
L_(X_2 )=54-9=45* L_(X_4 )=54-9=45 L_(X_3 )=54-9=45 L_(X_5 )=54-9=45
L_(X_6 )=54-9=45 L_(X_7 )=54-9=45
Находим минимальный функционал, который имеют вершины х2,х3, х4, х5, х6 и х7. Выбираем вершину с наименьшим индексом, то есть вершину х2. Вершине х2 присваиваем позиционное обозначение DD1.2 с соответствующей нумерацией выводов.
Убираем из функционального узла скомпонованные вершины с инцидентными ребрами и строим подграф из оставшихся вершин (рисунок1.6):
Рисунок 1.6 - Граф-схема
По граф-схеме составляем матрицу смежности и подсчитываем степень каждой вершины (Таблица 1.2):
Таблица 1.2 - Матрица смежности
X_3X_4X_5X_6X_7X_8X_9X_10X_11X_12X_13X_14∑РiX_309999000000036*X_490999000000036X_599099000000036X_699909000000036X_799990000000036X_800000023223214X_900000202322314X_1000000320232214X_1100000232023214X_1200000223202314X_1300000322320214X_1400000232232014 Подсчитываем сумму степеней всех вершин и выбираем базовую вершину, которая имеет наибольшую сумму степени вершины. Так как таких вершин пять (X_3-X_7), то за базовую принимаем вершину с наибольшим числом кратных ребер. Так как таких вершин пять, то за базовую принимаем вершину с наименьшим индексом. Следовательно, вершине Х3 присваиваем позиционное обозначение DD2.1.
Находим отображение вершины X_3 : Г_(X_3 )={X_4,X_5,X_6,X_7}.
Вычисляем функционалы для вершин, связанных с базовой по формуле(1.6):
L_(X_4 )=36-9=27* L_(X_5 )=36-9=27
L_(X_6 )=36-9=27 L_(X_7 )=36-9=27
Находим минимальный функционал, который имеют вершины x4, x5, x6 и x7. Выбираем вершину с наименьшим индексом, то есть вершину x4. Вершине x4 присваиваем позиционное обозначение DD2.2 с соответствующей нумерацией выводов.
Убираем из функционального узла скомпонованные вершины с инцидентными ребрами и строим подграф из оставшихся вершин (рисунок1.7):
Рисунок 1.7 - Граф-схема
По граф-схеме составляем матрицу смежности и подсчитываем степень каждой вершины (Таблица 1.3).
За базовую вершину принимаем вершину, имеющую максимальную степень, так как таких вершин три (x5, x6 и x7), то за базовую принимаем вершину с наибольшим числом кратных ребер. Наибольшее число кратных ребер у вершин одинаковое и равное девяти. Так как таких вершин три, то за базовую вершину принимаем вершину с минимальным индексом. Базовая вершина х5. Следовательно, вершине x5 присваиваем позиционное обозначение DD3.1
Таблица 1.3 - Матрица смежности
X_5X_6X_7X_8X_9X_10X_11X_12X_13X_14∑РiX_5099000000018*X_6909000000018X_7990000000018X_8000023223214X_9000202322314X_10000320232214X_11000232023214X_12000223202314X_13000322320214X_14000232232014
Находим отображение вершины х5: Г_(X_5 )={х6 и х7}.
Вычисляем функционалы для вершин, связанных с базовой:
L_(X_6 )=18-9=9* L_(X_7 )=18-9=9
Находим минимальный функционал, который имеют вершины x6 и x7. Выбираем вершину с наименьшим индексом, то есть вершину x6. Вершине x6 присваиваем позиционное обозначение DD3.2 с соответствующей нумерацией выводов.
Убираем из функционального узла скомпонованные вершины с инцидентными ребрами и строим подграф из оставшихся вершин (рисунок1.8): Рисунок 1.8 - Граф-схема
По граф-схеме составляем матрицу смежности и подсчитываем степень каждой вершины (Таблица 1.4):
Таблица 1.4 - Матрица смежности
X_7X_8X_9X_10X_11X_12X_13X_14∑РiX_7000000000X_80023223214*X_90202322314X_100320232214X_110232023214X_120223202314X_130322320214X_140232232014 За базовую вершину принимаем вершину, имеющую максимальную степень, так как таких вершин семь (x8, x9, x10, x11, x12, x13 и x14), то за базовую принимаем вершину с наибольшим числом кратных ребер. Наибольшее число кратных ребер у вершин одинаковое. Так как таких вершин семь, то за базовую вершину принимаем вершину с минимальным индексом. Базовая вершина х8. Следовательно, вершине x8 присваиваем позиционное обозначение DD4.1.
Находим отображение вершины х8: Г_(X_8 )={X_9,X_10,X_11,X_12,X_13,X_14}
Вычисляем функционалы для вершин, связанных с базовой:
L_(X_9 )=14-2=12 L_(X_10 )=14-3=11* L_(X_11 )=14-2=12 L_(X_12 )=14-2=12
L_(X_13 )=14-3=11 L_(X_14 )=14-2=12
Находим минимальный функционал, который имеют вершины x10 и x13. Выбираем вершину с наименьшим индексом, то есть вершину x10. Вершине x10 присваиваем позиционное обозначение DD4.2 с соответствующей нумерацией выводов.
Убираем из функционального узла скомпонованные вершины с инцидентными ребрами и строим подграф из оставшихся вершин (рисунок 1.9).
По граф-схеме составляем матрицу смежности и подсчитываем степень каждой вершины (Таблица 1.5).
Рисунок 1.9 - Граф-схема
Таблица 1.5 - Матрица смежности
X_7X_9X_11X_12X_13X_14∑РiX_70000000X_900322310*X_1103023210X_120220239X_130232029X_1403232010 Подсчитываем сумму степеней всех вершин и выбираем базовую вершину, которая имеет наибольшую сумму степени вершины. Так как таких вершин три (X_9,X_11 и X_14), то за базовую принимаем вершину с наибольшим числом кратных ребер. Так как таких вершин три, то за базовую принимаем вершину с наименьшим индексом. Следовательно, вершине Х9 присваиваем позиционное обозначение DD5.1.
Находим отображение вершины X_12 : Г_(X_9 )={X_11,X_12,X_13,X_14}.
Вычисляем функционалы для вершин, связанных с базовой по формуле(1.6):
L_(X_11 )=10-3=7 L_(X_12 )=10-2=8
L_(X_13 )=10-2=8 L_(X_14 )=10-3=7
Находим минимальный функционал, который имеют вершины x11 и x14. Выбираем вершину с наименьшим индексом, то есть вершину x11. Вершине x11 присваиваем позиционное обозначение DD5.2 с соответствующей нумерацией выводов.
Убираем из функционального узла скомпонованные вершины с инцидентными ребрами и строим подграф из оставшихся вершин (рисунок1.10): Рисунок 1.10 - Граф-схема
По граф-схеме составляем матрицу смежности и подсчитываем степень каждой вершины (Таблица 1.6):
Таблица 1.6 - Матрица смежности
X_7X_12X_13X_14∑РiX_700000X_1200235X_1302024X_1403205 Подсчитываем сумму степеней всех вершин и выбираем базовую вершину, которая имеет наибольшую сумму степени вершины. Так как таких вершин две (X_12 и X_14), то за базовую принимаем вершину с наибольшим числом кратных ребер. Так как таких вершин две, то за базовую принимаем вершину с наименьшим индексом. Следовательно, вершине Х12 присваиваем позиционное обозначение DD6.1.
Находим отображение вершины X_12 : Г_(X_12 )={X_13,X_14}.
Вычисляем функционалы для вершин, связанных с базовой по формуле(1.6):
L_(X_13 )=5-2=3 L_(X_14 )=5-3=2
Находим минимальный функционал, который имеет вершина x14. Вершине x14 присваиваем позиционное обозначение DD6.2 с соответствующей нумерацией выводов.
Убираем из функционального узла скомпонованные вершины с инцидентными ребрами и строим подграф из оставшихся вершин (рисунок 1.11): Рисунок 1.11 - Граф-схема
Так как базовая вершина не имеет отображения, а в микросхеме К155ЛР1 можно скомпоновать два модуля, то произвольно присваиваем вершине x7 и x13 позиционное обозначение DD7.1 и DD7.2 с соответствующей нумерацией выводов. В результате получаем скомпонованный функциональный модуль.
Компоновка первого функционального узла закончена. Фрагмент схемы электрической принципиальной для первого функционального узла показан на рисунке 1.12:
Рисунок 1.12 - Фрагмент схемы электрической принципиальной на микросхемах Л155ЛР1
Приступаем к компоновке второго функционального узла. Микросхема К155ЛА4 содержит три модуля. Функциональный узел содержит 7 модулей и для него необходимо три микросхемы, две из которых будут заполнены полностью. Для второго функционального узла на микросхеме К155ЛА4 составляем граф схему, петли не учитываем. Граф для второго блока изображен на рисунке 1.13:
Рисунок 1.13-Граф схема второго функционального узла
По граф-схеме составляем матрицу смежности и подсчитываем степень вершины (Таблица 1.7):
Таблица 1.7 - Матрица смежности второго функционального узла
X_15X_16X_17X_18X_19X_20X_21∑РiX_1501111116*X_1610111116X_1711011116X_1811101116X_1911110116X_2011111016X_2111111106 Подсчитываем сумму степеней всех вершин и выбираем базовую вершину, которая имеет наибольшую сумму степени вершины. Так как таких вершин семь (X_15-X_21), то за базовую принимаем вершину с наименьшим индексом. Следовательно, вершине Х15 присваиваем позиционное обозначение DD8.1.
Находим отображение вершины X_15 : Г_(X_15 )={X_16,X_17,X_18,X_19,X_20,X_21}.
Вычисляем функционалы для вершин, связанных с базовой по формуле(1.6):
L_(X_16 )=6-1=5* L_(X_17 )=6-1=5 L_(X_18 )=6-1=5 L_(X_19 )=6-1=5
L_(X_20 )=6-1=5 L_(X_21 )=6-1=5
Находим минимальный функционал, который имеют вершины х16, х17, х18, х19, х20 и х21 . Выбираем вершину с наименьшим индексом, то есть вершину х16. Вершине х16 присваиваем позиционное обозначение DD8.2 с соответствующей нумерацией выводов.
Стягиваем вершину х16 с базовой вершиной х15 и строим частичный подграф с базовой вершиной х1516 (рисунок 1.14):
Рисунок 1.14-Частичный граф с базовой вершиной х1516
По граф-схеме составляем матрицу смежности и подсчитываем степень каждой вершины (Таблица 1.8):
Таблица 1.8 - Матрица смежности
X_1516X_17X_18X_19X_20X_21∑РiX_151602222210*X_172011116X_182101116X_192110116X_202111016X_212111106 Находим отображение вершины X_1516 : Г_(X_1516 )={X_17,X_18,X_19,X_20,X_21}.
Вычисляем функционалы для вершин, связанных с базовой по формуле(1.6):
L_(X_17 )=10-2=8* L_(X_18 )=10-2=8 L_(X_19 )=10-2=8 L_(X_20 )=10-2=8
L_(X_21 )=10-2=8
Вершина X_17 является последним модулем в микросхеме (DD8.3) с соответствующей нумерацией выводов. Так как микросхема К155ЛА4 имеет три модуля, то она уже скомпанована.
Убираем из функционального узла скомпонованные вершины с инцидентными ребрами и строим подграф из оставшихся вершин (рисунок 1.15): Рисунок 1.15 - Граф-схема
По граф-схеме составляем матрицу смежности и подсчитываем степень каждой вершины (Таблица 1.9):
Таблица 1.9 - Матрица смежности
X_18X_19X_20X_21∑РiX_1801113*X_1910113X_2011013X_2111103 Подсчитываем сумму степеней всех вершин и выбираем базовую вершину, которая имеет наибольшую сумму степени вершины. Так как таких вершин четыре (X_18-X_21), то за базовую принимаем вершину с наименьшим индексом. Следовательно, вершине Х18 присваиваем позиционное обозначение DD9.1.
Находим отображение вершины X_18 : Г_(X_18 )={X_19,X_20,X_21}.
Вычисляем функционалы для вершин, связанных с базовой по формуле(1.6):
L_(X_19 )=3-1=2* L_(X_20 )=3-1=2 L_(X_21 )=3-1=2
Находим минимальный функционал, который имеют вершины х19, х20 и х21 . Выбираем вершину с наименьшим индексом, то есть вершину х19. Вершине х19 присваиваем позиционное обозначение DD9.2 с соответствующей нумерацией выводов.
Стягиваем вершину х19 с базовой вершиной х18 и строим частичный подграф с базовой вершиной х1819 (рисунок 1.16):
Рисунок 1.16-Частичный граф с базовой вершиной х1819
По граф-схеме составляем матрицу смежности и подсчитываем степень каждой вершины (Таблица 1.10):
Таблица 1.10 - Матрица смежности
X_1819X_20X_21∑РiX_18190224*X_202013X_212103 Находим отображение вершины X_1819 : Г_(X_1516 )={X_20,X_21}.
Вычисляем функционалы для вершин, связанных с базовой по формуле(1.6):
L_(X_20 )=4-2=2* L_(X_21 )=4-2=2
Вершина X_20 является последним модулем в микросхеме (DD9.3) с соответствующей нумерацией выводов. Так как микросхема К155ЛА4 имеет три модуля, то она уже скомпанована.
Убираем из функционального узла скомпонованные вершины с инцидентными ребрами и строим подграф из оставшихся вершин (рисунок 1.17): Рисунок 1.17 - Граф-схема
Граф содержит всего один модуль, относящийся к микросхеме К155ЛА4. Помещаем его в одну микросхему и присваиваем позиционное обозначение DD10.1. Фрагмент схемы электрической принципиальной для второго функционального узла показан на рисунке 1.18:
Рисунок 1.18 - Фрагмент схемы электрической принципиальной для функционального узла на микросхемах К155ЛА4
Приступаем к компоновке третьего функционального узла. Он содержит два модуля и для него необходимо одна микросхема К155ЛА3, которая будет заполнена не полностью. Для третьего функционального узла составляем граф-схему, петли не учитываем (рисунок 1.19):
Рисунок 1.19 - Граф-схема
По граф-схеме составляем матрицу смежности и подсчитываем степень каждой вершины (Таблица 1.10):
Таблица 1.10 - Матрица смежности
X_22X_23∑РiX_22011X_23101 Граф содержит всего два модуль, относящихся к микросхеме К155ЛА3, состоящей из четырех модулей. Помещаем их в одну микросхему и присваиваем позиционное обозначение DD10.1 и DD10.2 соответственно. Фрагмент схемы электрической принципиальной для третьего функционального узла показан на рисунке 1.20:
Рисунок 1.20 - фрагмент схемы электрической принципиальной для третьего функционального узла
Для разъема присваиваем обозначение ХS1.
В результате получаем схему электрическую принципиальную. Так как оформление схем электрических принципиальных должно соответствовать [4], то окончательный вариант схемы электрической принципиальной приведѐн на рисунке 1.21. В этом варианте нумерация микросхем учитывалась в соответствии с [4], нумерация модулей микросхем не изменилась. К схеме электрической принципиальной составляется перечень элементов.
Рисунок 1.21 - схема электрическая принципиальная
РАЗМЕЩЕНИЕ МИКРОСХЕМ НА МОНТАЖНОМ ПРОСТРАНСТВЕ С ИСПОЛЬЗОВАНИЕМ ПОСЛЕДОВАТЕЛЬНОГО АЛГОРИТМА РАЗМЕЩЕНИЯ Общее описание алгоритма
После распределения конструктивных элементов РЭА по коммутационным пространствам различного уровня иерархии (компоновки) для каждой полученной в результате этого конструктивной единицы производят размещение включенных в ее состав элементов предыдущего уровня, то есть выбирают такое их взаимное расположение, при котором наилучшим образом учитываются предъявляемые к аппаратуре требования. Исходной информацией при решении задачи размещения являются данные о конфигурации и размерах конструкционного пространства (150 х 150 мм) определяемые требованиями установки и крепления данной сборочной единицы в аппаратуре. Также учитывается количество и геометрические размеры конструкционных элементов, подлежащих размещению, взаимное расположение отдельных элементов. Задача сводится к отысканию для каждого размещаемого элемента таких позиций, при которых оптимизируется выбранный показатель качества и обеспечивается наиболее благоприятные условия для последующего элементного монтажа. Особое знание эта задача приобретает при проектировании аппаратуры на печатных платах. Основная сложность в постановке задачи размещения заключается в выборе целевой функции. Связано это с тем, что одной из главных задач размещения является создание наилучших условий для дальнейшей трассировки соединений, что невозможно провести без проведения самой трассировки. Следовательно, если для оценки качества размещения элементов выбрать критерий непосредственно связанный с получением оптимального рисунка металлизации печатной платы, то конечный результат может быть найден только при совместном решении задачи размещения, выбора очередности проведения соединения трассировки, что практически невозможно уже для схем средней сложности вследствие огромных затрат машинного времени. Поэтому все применяемые в настоящее время алгоритмы размещения используют промежуточные критерии, которые лишь качественно способствуют решению основной задачи, получению оптимальной трассировки соединений. К таким критериям относятся:
Минимум суммарной, взвешенной длины соединения.
Минимальное число соединений, длина которых больше заданной.
Минимальное число пересечений проводников.
Максимальное число соединений между элементами, находящихся в соседних позициях, либо в позициях указанных разработчиком. Максимальное число цепей простой конфигурации.
Наибольшее распространение в алгоритмах размещения получил первый критерий, что объясняется следующими причинами:
Уменьшение длин соединений улучшает электрические характеристики устройства.
Упрощает трассировку печатных проводников.
Снижает трудоемкость изготовления печатных плат
Сравнительно простой в реализации.
Наиболее распространенным алгоритмам размещения является последовательный алгоритм. Он основан на допущении, что для получения оптимального размещения необходимо в соседних позициях расположить элементы максимально связанные друг с другом. Сущность этих алгоритмов состоит в последовательном закреплении заданного набора коммутационных элементов на печатной плате. В качестве первоначального закрепленного на плате элемента обычно выбирают разъемы, которые, как правило, устанавливаются на каком-либо краю платы. На каждом шаге для установки на коммутационную плату выбирают элементы из числа еще неразмещенных и имеющих максимальную степень связности с ранее закрепленными элементами. Процесс размещения элементов заканчивается после выполнения L шагов, когда все элементы будут размещены на коммутационном поле.
Пошаговое описание алгоритма
Шаг1. По полученной схеме электрической принципиальной составляем граф, считая за вершины скомпонованные микросхемы и разъем. По графу строим матрицу смежности, обнуляя ее по главной диагонали. Шаг2.Формируем матрицу расстояний для коммутационного поля с учетом ранее закрепленного элемента (разъем х1)
Шаг3. Выбираем из множества неразмещенных микросхем ту микросхему, для которой коэффициент взвешенной связности максимальный. Коэффициент взвешенной связности рассчитываем по формуле:
Ф_j=∑_(j=1)^m▒a_ij/p_j (2.1)
〖где a〗_ij - количество связей i-ой вершины с ранее закрепленной вершиной хi.
p_j - степень j-ой вершины.
m - количество вершин, связанных с j-ой вершиной.
Шаг4.Для вершины, у которой коэффициент взвешенной связности максимальный, находим посадочное место на коммутационном поле из условия, что коэффициент размещения минимальный.
Коэффициент размещения рассчитывается по формуле:
F_f=∑_(f=1)^n▒a_ij ×d_fl(2.2)
〖где d〗_fl - количество связей ячейки f с ранее закрепленной ячейкой l, в которой размещена вершина хi.
n - количество не занятых посадочных мест.
Шаг5. Шаги 3 и 4 повторяются до тех пор, пока все элементы не будут размещены на плате.
Размещение элементов на печатной плате
На коммутационном поле платы первое посадочное место закреплено за разъемом XS1, второе и восьмое посадочные места запрещенные (рисунок 2.1).
X12581114369121547101316
Рисунок 2.1 - Модель монтажной платы
По полученной схеме электрической принципиальной составляем граф, считая за вершины скомпонованные микросхемы и разъем (рисунок 2.2):
Рисунок 2.2 - Граф-схема
По графу строим матрицу смежности и определяем степень каждой вершины (таблица 2.1).
По матрице смежности и коммутационному полю платы размещаем элементы на посадочные места. На коммутационном поле платы первое посадочное место закреплено за разъемом XS1. 2 и 8 посадочные места запрещенные. По коммутационному полю составляем матрицу расстояний (таблица 2.2).
Так как все микросхемы еще не распределены по посадочным местам, то рассчитываем коэффициент взвешенной связности для всех микросхем по формуле (2.1), считая, что ранее закрепленный элемент XS1.
Таблица 2.1 - Матрица смежности
DD1DD2DD3DD4DD5DD6DD7DD8DD9DD10DD11XS1∑piDD1030004214202106115DD230201192023023DD302048000950331DD400204000420416DD501840010950331DD6421000043601818110DD719001402113022DD8422000362001818109DD900949010041230DD1021252518118401683DD1103000131110010XS160343808260040 Таблица 2.2 - Матрица расстояний
123456789101112131415161011132243354465521012123234545656311012123234345454121032143254365453123012123434545622121012123234347232121032143254384234123012123234933232121012123231034323212103214321155454341230121231244343232121012121345434323212103211466565452341230115554543432321210165654543432321210
Ф_DD1=6/115=0.0522 Ф_DD2=0/23=0
Ф_DD3=3/31=0.0968 Ф_DD4=4/16=0.25*
Ф_DD5=3/31=0.0968 Ф_DD6=8/110=0.0727
Ф_DD7=0/22=0 Ф_DD8=8/109=0.0734
Ф_DD9=2/30=0.0667 Ф_DD10=6/83=0.0723
Ф_DD11=0/10=0
Выбираем для размещения микросхему DD4, которая имеет максимальный коэффициент взвешенной связности. Так как все посадочные места, кроме 1, 2 и 8 не заняты, то коэффициент размещения рассчитываем для всех посадочных мест, кроме 1, 2 и 8.
Коэффициент размещения рассчитываем по формуле (2.2):
F3=4×1=4* F10=4×3=12
F4=4×1=4 F11=4×5=20
F5=4×3=12 F12=4×4=16
F6=4×2=8 F13=4×4=16
F7=4×2=8 F14=4×6=24
F9=4×3=12 F15=4×5=20
F16=4×5=20
Выбираем минимальный коэффициент размещения. Так как такой коэффициент имеют ячейки 3 и 4, то выбираем ячейку с минимальным индексом. Следовательно, за микросхемой DD4 закрепляем 3-е посадочное место. Рассчитываем коэффициент взвешенной связности для остальных неразмещенных микросхем с учетом того, что уже ранее размещенными элементами считается разъем х1 и микросхема DD4. Значит, формулу (2.1) можно записать в виде:
Ф_j=(a_х1j+a_DD1)/p_j (2.3)
Ф_DD1=(6+0)/115=0.0522 Ф_DD2=(0+0)/23=0
Ф_DD3=(3+4)/31=0.2258 Ф_DD5=(3+4)/31=0.2258 Ф_DD6=(8+0)/110=0.0727 Ф_DD7=(0+0)/22=0 Ф_DD8=(8+0)/109=0.0734 Ф_DD9=(2+4)/30=0.2 Ф_DD10=(6+2)/83=0.0964 Ф_DD11=(0+0)/10=0
Выбираем для размещения микросхему DD3, которая имеет максимальный коэффициент взвешенной связности. Так как все посадочные места, кроме 1, 2, 3 и 8 не заняты, то коэффициент размещения рассчитываем для всех посадочных мест, кроме 1, 2, 3 и 8.
Формула (2.2) приобретает следующий вид:
F_f=a_(DD3-xs1)×d_(f-1)+a_(DD3-DD4)×d_(f-2) (2.3)
F4=3*1+4*1=7 F11=3*5+4*4=31
F5=3*3+4*2=17 F12=3*4+4*3=24
F6=3*2+4*1=10 F13=3*4+4*4=28
F7=3*2+4*2=14 F14=3*6+4*5=38
F9=3*3+4*2=17 F15=3*5+4*4=31
F10=3*3+4*3=21 F10=3*5+4*5=35
Так как минимальный коэффициент размещения получился для ячейки 4, то микросхему DD3 помещаем в 4-ую ячейку.
Рассчитываем коэффициент взвешенной связности для оставшихся микросхем.
Ф_DD1=(6+0+0)/115=0,0522 Ф_DD2=(0+0+2)/23=0,087
Ф_DD5=(3+4+8)/31=0,484 Ф_DD6=(8+0+0)/110=0,0727
Ф_DD7=(0+0+0)/22=0 Ф_DD8=(8+0+0)/109=0,0734
Ф_DD9=(9+4+2)/30=0,5 Ф_DD10=(5+2+6)/83=0,157
Ф_DD11=(0+0+0)/10=0
Максимальный коэффициент взвешенной связности получился для микросхемы DD9, следовательно, приступаем к ее размещению.
Рассчитываем коэффициент размещения для ячеек 5, 6, 7, 9, 10, 11,12, 13, 14, 15, 16.
F5=2*3+9*3+4*2=41 F11=2*5+9*5+4*4=71
F6=2*2+9*2+4*1=26 F12=2*4+9*4+4*3=56
F7=2*2+9*1+4*2=21 F13=2*4+9*3+4*4=51
F9=2*3+9*3+4*2=41 F14=2*6+9*6+4*5=86
F10=2*3+9*2+4*3=36 F15=2*5+9*5+4*4=71
F16=2*5+9*4+4*5=66
Так как минимальный коэффициент размещения получился для ячейки 7, то микросхему DD9 помещаем в 7-ую ячейку.
Рассчитываем коэффициент взвешенной связности для микросхем DD1, DD2, DD5, DD6, DD7, DD8, DD10, DD11.
Ф_DD1=(6+0+0+0)/115=0,0522 Ф_DD2=(0+0+2+0)/23=0,087
Ф_DD5=(3+4+8+9)/31=0,774 Ф_DD6=(8+0+0+0)/110=0,0727
Ф_DD7=(0+0+0+1)/22=0,0455 Ф_DD8=(8+0+0+0)/109=0,0734
Ф_DD10=(5+2+4+6)/83=0,205 Ф_DD11=(0+0+1+0)/10=0,1
Выбираем для размещения микросхему DD5, которая имеет максимальный коэффициент взвешенной связности. Рассчитываем коэффициент размещения для посадочных мест 5, 6, 9, 10, 11, 12, 13, 14, 15, 16.
F5=3*3+9*2+4*2+8*3=59 F12=3*4+9*3+4*3+8*4=83
F6=3*2+9*1+4*1+8*2=35 F13=3*4+9*2+4*4+8*3=70
F9=3*3+9*2+4*2+8*3=59 F14=3*6+9*5+4*5+8*6=131
F10=3*3+9*1+4*3+8*2=46 F15=3*5+9*4+4*4+8*5=107
F11=3*5+9*4+4*4+8*5=107 F16=3*5+9*3+4*5+8*4=94
Так как минимальный коэффициент размещения получился для ячейки 6, то микросхему DD5 помещаем в 6-ую ячейку.
Рассчитываем коэффициент взвешенной связности для микросхем DD1, DD2, DD6, DD7, DD8, DD10, DD11.
Ф_DD1=(6+0+0+0+0)/115=0,0522 Ф_DD2=(0+0+2+0+1)/23=0,130
Ф_DD6=(8+0+0+0+0)/110=0,0727 Ф_DD7=(0+0+0+1+1)/22=0,091
Ф_DD8=(8+0+0+0+0)/109=0,0734 Ф_DD10=(5+2+4+6+5)/83=0,265
Ф_DD11=(0+0+1+0+0)/10=0,1
Выбираем для размещения микросхему DD10, которая имеет максимальный коэффициент взвешенной связности. Рассчитываем коэффициент размещения для посадочных мест 5, 9, 10, 11, 12, 13, 14, 15, 16.
F5=6*3+4*2+5*1+2*2+5*3=50 F12=6*4+4*3+5*2+2*3+5*4=72
F9=6*3+4*2+5*1+2*2+5*3=50 F13=6*4+4*2+5*3+2*4+5*3=70
F10=6*3+4*1+5*2+2*3+5*2=48 F14=6*6+4*5+5*4+2*5+5*6=116
F11=6*5+4*4+5*3+2*4+5*5=94 F15=6*5+4*4+5*3+2*4+5*5=94
F16=6*5+4*3+5*4+2*5+5*4=92
Так как минимальный коэффициент размещения получился для ячейки 10, то микросхему DD10 помещаем в 10-ую ячейку.
Рассчитываем коэффициент взвешенной связности для микросхем DD1, DD2, DD6, DD7, DD8, DD11.
Ф_DD1=(6+0+0+0+21)/115=0,235 Ф_DD2=(0+0+2+0+1+2)/23=0217
Ф_DD6=(8+0+0+0+0+18)/110=0,236 Ф_DD7=(0+0+0+1+1+1)/22=0,136
Ф_DD8=(8+0+0+0+0+18)/109=0,239 Ф_DD11=(0+0+1+0+0+1)/10=0,2
Выбираем для размещения микросхему DD8, которая имеет максимальный коэффициент взвешенной связности. Рассчитываем коэффициент размещения для посадочных мест 5, 9, 11, 12, 13, 14, 15, 16.
F5=8*3+18*3+0*2+0*1+0*2+0*3=78 F13=8*4+18*1+0*4+0*3+0*4+0*3=50
F9=8*3+18*1+0*2+0*1+0*2+0*3=42 F14=8*6+18*4+0*5+0*4+0*5+0*6=120
F11=8*5+18*3+0*4+0*3+0*4+0*5=94 F15=8*5+18*3+0*4+0*3+0*4+0*5=94
F12=8*4+18*2+0*3+0*2+0*3+0*4=68 F16=8*5+18*2+0*5+0*4+0*5+0*4=70
Так как минимальный коэффициент размещения получился для ячейки 9, то микросхему DD8 помещаем в 9-ую ячейку.
Рассчитываем коэффициент взвешенной связности для микросхем DD1, DD2, DD6, DD7, DD11.
Ф_DD1=(6+0+0+0+21+42)/115=0,6 Ф_DD2=(0+0+2+0+1+2+2)/23=0,304
Ф_DD6=(8+0+0+0+0+18+36)/110=0,564 Ф_DD7=(0+0+0+1+1+1+2)/22=0,227
Ф_DD11=(0+0+1+0+0+1+1)/10=0,3
Выбираем для размещения микросхему DD1, которая имеет максимальный коэффициент взвешенной связности. Рассчитываем коэффициент размещения для посадочных мест 5, 11, 12, 13, 14, 15, 16.
F5=6*3+21*3+0*2+42*2+0*1+0*2+0*3=165
F11=6*5+21*3+0*4+42*2+0*3+0*4+0*5=177
F12=6*4+21*2+0*3+42*1+0*2+0*3+0*4=108
F13=6*4+21*1+0*2+42*2+0*3+0*4+0*3=129
F14=6*6+21*4+0*5+42*3+0*4+0*5+0*6=246
F15=6*5+21*3+0*4+42*2+0*3+0*4+0*5=177
F16=6*5+21*2+0*3+42*3+0*4+0*5+0*4=198
Так как минимальный коэффициент размещения получился для ячейки 12, то микросхему DD1 помещаем в 12-ую ячейку.
Рассчитываем коэффициент взвешенной связности для микросхем DD2, DD6, DD7, DD11.
Ф_DD2=(0+0+2+0+1+2+2+3)/23=0,435 Ф_DD6=(8+0+0+0+0+18+36+42)/110=0,945 Ф_DD7=(0+0+0+1+1+1+2+1)/22=0,273
Ф_DD11=(0+0+1+0+0+1+1+0)/10=0,3
Выбираем для размещения микросхему DD6, которая имеет максимальный коэффициент взвешенной связности. Рассчитываем коэффициент размещения для посадочных мест 5, 11, 13, 14, 15, 16.
F5=8*3+18*3+0*5+36*2+0*1+0*2+0*3+42*3=276
F11=8*5+18*3+0*4+36*2+0*3+0*4+0*5+42*1=208
F13=8*4+18*1+0*2+36*2+0*3+0*4+0*3+42*1=164
F14=8*6+18*4+0*5+36*3+0*4+0*5+0*6+42*2=312
F15=8*5+18*3+0*4+36*2+0*3+0*4+0*5+42*1=208
F16=8*5+18*2+0*3+36*3+0*4+0*5+0*4+42*2=268
Так как минимальный коэффициент размещения получился для ячейки 13, то микросхему DD6 помещаем в 13-ую ячейку.
Рассчитываем коэффициент взвешенной связности для микросхем DD2, DD7, DD11.
Ф_DD2=(0+0+2+0+1+2+2+3+1)/23=0,4783 Ф_DD7=(0+0+0+1+1+1+2+1+4)/22=0,4545
Ф_DD11=(0+0+1+0+0+1+1+0+1)/10=0,4
Выбираем для размещения микросхему DD2, которая имеет максимальный коэффициент взвешенной связности. Рассчитываем коэффициент размещения для посадочных мест 5, 11, 14, 15, 16.
F5=0*3+2*3+0*2+2*2+1*4+1*1+0*2+2*3+3*3=30
F11=0*5+2*3+0*4+2*2+1*2+1*3+0*4+2*5+3*1=28
F14=0*6+2*4+0*5+2*3+1*3+1*4+0*5+2*6+3*2=39
F15=0*5+2*3+0*4+2*2+1*2+1*3+0*4+2*5+3*1=28
F16=0*5+2*2+0*3+2*3+1*1+1*4+0*5+2*4+3*2=29
Так как минимальный коэффициент размещения получился для ячеек 11 и 15, то микросхему DD2 помещаем в 11-ую ячейку, так как она имеет меньший индекс.
Рассчитываем коэффициент взвешенной связности для микросхем DD7 и DD11.
Ф_DD7=(0+0+0+1+1+1+2+1+4+9)/22=0,8636
Ф_DD11=(0+0+1+0+0+1+1+0+1+3)/10=0,7
Выбираем для размещения микросхему DD7, которая имеет максимальный коэффициент взвешенной связности. Рассчитываем коэффициент размещения для посадочных мест 5, 11, 14, 15, 16.
F5=0*3+1*3+1*2+2*2+4*4+1*1+0*2+0*3+9*4+1*3=65
F14=0*6+1*4+1*5+2*3+4*3+1*4+0*5+0*6+9*1+1*2=42
F15=0*5+1*3+1*4+2*2+4*2+1*3+0*4+0*5+9*2+1*1=41
F16=0*5+1*2+1*3+2*3+4*1+1*4+0*5+0*4+9*3+1*2=48
Так как минимальный коэффициент размещения получился для ячейки 15, то микросхему DD7 помещаем в 15-ую ячейку.
Выбираем для размещения оставшуюся микросхему DD11, которая имеет коэффициент взвешенной связности равный единице и рассчитываем коэффициент размещения для посадочных мест 5, 14, 16.
F5=0*3+1*3+1*2+1*2+3*4+1*4+0*1+0*2+0*3+3*4+0*3=35
F14=0*6+1*4+1*5+1*3+3*1+1*3+0*4+0*5+0*6+3*1+0*2=21
F16=0*5+1*2+1*3+1*3+3*1+1*1+0*4+0*5+0*4+3*3+0*2=15
Так как минимальный коэффициент размещения получился для ячейки 16, то микросхему DD11 помещаем в 16-ую ячейку.
В результате получилось следующее размещение микросхем на плате(рис. 2.3):
X1DD2DD4DD5DD8DD1DD7DD3DD9DD10DD6DD11
Рисунок 2.3
Исходя из размещения микросхем на коммутационном поле платы, составляется сборочный чертеж платы и спецификация к нему.
РАСЧЕТ ПЛОЩАДИ ПЕЧАТНОЙ ПЛАТЫ
1.Расчет площади печатной платы производится по формуле:
S_пп≥(∑▒S_эл )/(K_j*m)+S_уст ;
где m - количество монтажных сторон платы m=1;
S_уст - установочная площадь платы, если крепления расположены по четырем углам, то
S_уст=4*10*10=400 〖мм〗^2;
K_j - коэффициент заполнения, K_j=0,4;
∑▒S_эл - площадь элементов на печатной плате, рассчитывается как сумма произведения количества микросхем на размер 1 микросхемы с площадью разъема.
∑▒S_эл =n*17.5*7.5+S_раз
где S_раз - площадь разъема (S_раз=22*8=176);
17,5*7,5 - установочная площадь микросхемы;
n - количество микросхем.
2. Рассчитаем площадь элементов на печатной плате:
∑▒S_эл =11*17,5*7,5+22*8=1443,75+176=1619,75
3.Расчет площади печатной платы с учетом площади элементов, рассчитанной выше:
S_пп≥1619,75/(0,4*1)+400=4449,375 〖мм〗^2.
Возьмем S_пп=4500 〖мм〗^2
АЛГОРИТМЫ ТРАССИРОВКИ ПЕЧАТНОГО МОНТАЖА. ТРАССИРОВКА ШИНЫ "ЗЕМЛЯ" ПРИ ПОМОЩИ АЛГОРИТМА КРАСКАЛА
Трассировка - прокладка электрических трасс, проводов (при проводном монтаже), дорожек.
Проектирование печатного монтажа является одной из самых сложных задач автоматизированного проектирования. Трассировку соединений осуществляют с помощью алгоритмов, основанных на методах динамического программирования. Общим для этих алгоритмов является разбиение монтажного пространства на ячейки, размер и форма которых определяют плотность и конфигурацию печатных проводников. Наибольшее распространение на практике получило разбиение рабочего поля на правильные квадраты, что обеспечивает простую адресацию ячеек в прямоугольной системе координат и привычную форму соединений. Размеры ячеек определяют конструктивно-технологическими требованиями, предъявляемые к печатному монтажу. Так как в каждой ячейке обычно размещается только один вывод или печатный проводник, максимальные размеры ячеек определяются допустимой точностью воспроизведения проводников. Минимальные размеры ячеек определяются соотношением:
d≥bnp+l3 (3.1)
d - расстояние между центрами соседних ячеек.
Bnp- минимальная ширина печатного проводника.
l3 - минимальное расстояние между соседними проводниками. Соединения выводов конструктивных элементов осуществляются в результате последовательного заполнения ячеек трассами, конфигурация которых является локально-оптимальной в соответствии с выбранными критериями трассировки печатных плат.
Общие сведения алгоритма Краскала
Строится кратчайшая связывающая сеть путем последовательного присоединения к ней ребер, удовлетворяющих следующим условиям:
- длина ребра должна быть минимальной;
- ребро инцидентно только по одной вершине;
- присоединение рассматриваемого ребра не приводит к повышению степени любой вершины больше заданного числа.
Последовательность:
- на множестве вершин строится полный граф, задаются матрица расстояний
- упорядочиваются ребра в порядке возрастания их длины Построение КСС осуществляется путем последовательного выбора ребер удовлетворяющих трем условиям, при этом формируется массив индексов ребер. Условием получения покрывающего дерева является вычерчивание всех номеров вершин в массиве номеров.
Выполнение трассировки
По координатной сетке строим матрицу расстояний от каждого контакта к каждому, считая числа клеток по горизонтали и вертикали под прямым углом (таблица 4.1):
Таблица 4.1 - Матрица расстояний
К1К2К3К4К5К6К7К8К9К10К11К101922211477715814К20414033202026342727К307821291571428К407282814142135К502121771428К608141477К701422157К808721К90721К10014К110
Составляем массив ребер, упорядоченных по возрастанию.
d16, d17, d18, d34, d39, d45, d58, d59, d610, d611, d711, d810, d910, d110, d35, d67, d89, d15, d111, d310, d48, d49, d510, d68, d69, d78, d1011, d19, d38, d710, d12, d26, d27, d14, d36, d410, d56, d57, d811, d911, d13, d79, d28, d210, d211, d311, d46, d47, d511, d37, d25, d29, d411, d24, d23.
Анализируя данный массив по трем условиям алгоритма Краскала, получим массив ребер: Последовательность соединения (прокладки трасс) такова: DD4 - DD3 - DD9 - DD5 - DD8 - DD10 - DD6 - DD1 - DD7 - DD11 - DD2.
Рисунок 4.1- Внешний вид платы с шиной "земля".
ТРАССИРОВКА ШИНЫ ПИТАНИЯ С ПОМОЩЬЮ АЛГОРИТМА ПРИМА
Общие сведения
К шине питания должен подключаться 14-й вывод микросхем. В алгоритме Прима, в отличие от алгоритма Краскала, построение КСС ведется путем присоединения ближайших изолированных вершин, при этом все манипуляции проводятся лишь с матрицей расстояний.
Выполнение трассировки
По координатной сетке строим матрицу расстояний (таблица 5.1) от каждого контакта к каждому, считая числа клеток по горизонтали и вертикали под прямым углом.
Таблица 5.1 - Матрица расстояний
К1К2К3К4К5К6К7К8К9К10К11К1074021141977332620К27041221520148342727К340410192621473371428К421221907342814202741К51415267027217192034К61920213427026201477К771447282126014403319К8783314720140261927К93334720191440260721К102627142720733197014К1120272841347192721140
В начале, просматриваем первую строку матрицы и выбираем минимальный элемент (d_12). Присваиваем вес контактам данного элемента. (К1=К2=1). Исключаем из матрицы расстояний столбцы 1 и 2. Получаем следующую матрицу (таблица 5.2).
Просматриваем 1-ю и 2-ю строки и выбираем минимальный элемент(d_17). Присваиваем вес контактам данного элемента. (К1=2, К7=1). Исключаем из матрицы расстояний столбец 7. Получаем следующую матрицу (таблица 5.3).
Просматриваем 1-ю, 2-ю и 7-ю строки и выбираем минимальный элемент(d_18). Присваиваем вес контактам данного элемента. (К1=3, К8=1). Исключаем из матрицы расстояний столбец 8. Получаем следующую матрицу (таблица 5.4).
Таблица 5.2 - Матрица расстояний
К3К4К5К6К7К8К9К10К11К14021141977332620К241221520148342727К30192621473371428К41907342814202741К5267027217192034К6213427026201477К747282126014403319К83314720140261927К9720191440260721К10142720733197014К112841347192721140 Таблица 5.3 - Матрица расстояний
К3К4К5К6К8К9К10К11К1402114197332620К2412215208342727К301926213371428К419073414202741К52670277192034К62134270201477К74728212614403319К833147200261927К97201914260721К101427207197014К1128413472721140 Таблица 5.4 - Матрица расстояний
К3К4К5К6К9К10К11К140211419332620К241221520342727К3019262171428К4190734202741К5267027192034К621342701477К747282126403319К83314720261927К972019140721К1014272077014К11284134721140 Просматриваем 1-ю, 2-ю, 7-ю и 8-ю строки и выбираем минимальный элемент(d_58). Присваиваем вес контактам данного элемента. (К8=2, К5=1). Исключаем из матрицы расстояний столбец 5. Получаем следующую матрицу (таблица 5.5):
Таблица 5.5 - Матрица расстояний
К3К4К6К9К10К11К1402119332620К2412220342727К30192171428К419034202741К526727192034К6213401477К7472826403319К8331420261927К9720140721К10142777014К112841721140 Просматриваем 1-ю, 2-ю, 5-ю, 7-ю и 8-ю строки и выбираем минимальный элемент(d_45). Присваиваем вес контактам данного элемента. (К5=2, К4=1). Исключаем из матрицы расстояний столбец 4. Получаем следующую матрицу (таблица 5.6).
Таблица 5.6 - Матрица расстояний
К3К6К9К10К11К14019332620К24120342727К302171428К41934202741К52627192034К62101477К74726403319К83320261927К97140721К101477014К1128721140 Просматриваем 1-ю, 2-ю, 4-ю, 5-ю, 7-ю и 8-ю строки и выбираем минимальный элемент (d_16). Присваиваем вес контактам данного элемента. (К1=4, К6=1). Исключаем из матрицы расстояний столбец 6. Получаем следующую матрицу (таблица 5.7).
Просматриваем 1-ю, 2-ю, 4-ю, 5-ю, 6-ю, 7-ю и 8-ю строки и выбираем минимальный элемент (d_610). Присваиваем вес контактам данного элемента. (К6=2, К10=1). Исключаем из матрицы расстояний столбец 10. Получаем следующую матрицу (таблица 5.8).
Таблица 5.7 - Матрица расстояний
К3К9К10К11К140332620К241342727К3071428К419202741К526192034К6211477К747403319К833261927К970721К10147014К112821140 Таблица 5.8 - Матрица расстояний
К3К9К11К1403320К2413427К30728К4192041К5261934К621147К7474019К8332627К97021К1014714К1128210 Просматриваем 1-ю, 2-ю, 4-ю, 5-ю, 6-ю, 7-ю, 8-ю и 10-ю строки и выбираем минимальный элемент (d_611). Присваиваем вес контактам данного элемента. (К6=3, К11=1). Исключаем из матрицы расстояний столбец 11. Получаем следующую матрицу (таблица 5.9).
Таблица 5.9 - Матрица расстояний
К3К9К14033К24134К307К41920К52619К62114К74740К83326К970К10147К112821 Просматриваем 1-ю, 2-ю, 4-ю, 5-ю, 6-ю, 7-ю, 8-ю, 10-ю и 11-ю строки и выбираем минимальный элемент (d_910). Присваиваем вес контактам данного элемента. (К10=2, К9=1). Исключаем из матрицы расстояний столбец 9. Получаем следующую матрицу (таблица 5.10).
Таблица 5.9 - Матрица расстояний
К3К140К241К30К419К526К621К747К833К97К1014К1128 Просматриваем все строки и выбираем минимальный элемент(d_39). Присваиваем вес контактам данного элемента. (К9=2, К3=1). Переходя от элементов к микросхемам, получим следующую последовательность соединения микросхем:
DD11-DD6-DD10-DD9-DD3-DD4-DD5-DD8-DD1-DD2-DD7
Рисунок 5.1 - Трассировка шины "питание"
ТРАССИРОВКА СИГНАЛЬНЫХ ЦЕПЕЙ С ПОМОЩЬЮ ВОЛНОВЫХ АЛГОРИТМОВ
Общие сведения
Данный алгоритм является классическим примером использования методов динамического программирования для решения задачи трассировки печатных соединений. Основные принципы построения трасс с помощью волнового алгоритма сводятся к следующему.
Все ячейки монтажного поля подразделяют на занятые и свободные. Занятыми считаются ячейки, в которых уже расположены проводники, построенные на предыдущих шагах, или находятся монтажные выводы элементов, а также ячейки, соответствующие границе платы запрещенным для прокладывания проводников участкам. Каждый раз при проведении новой трассы можно использовать лишь свободные ячейки, число которых по мере проведения трасс сокращается.
На множестве ячеек (свободных) коммутационного поля моделируют волну влияния из одной ячейки в другую, соединяемых впоследствии одним проводником. Первую ячейку, в которой зарождается волна влияний называют источником, а вторую - приемником волны. Чтобы иметь возможность следить за прохождением фронта волны влияний, его фрагментом на каждом этапе присваивают некоторые веса:
,(5.1)
где и - веса ячеек k - го и (k-1) -го фронтов;
ψ - весовая функция, являющаяся показателем качества проведения пути;
На накладывают одно ограничение - веса ячеек предыдущих фронтов не должны быть больше весов ячеек последующих фронтов. Фронт распространяется только на соседние ячейки, которые имеют с ячейками предыдущего фронта либо общую сторону, либо хотя бы одну общую точку. Процесс распространения волны продолжается до тех пор, пока ее расширяющийся фронт не достигнет приемника или на θ шаге не найдется ни одной свободной ячейки, которая могла бы быть включена в очередной фронт, что соответствует случаю невозможности проведения трассы при заданных ограничениях.
Если в результате распространения волна достигла приемника, то осуществляют "проведение пути", которое заключается в движении от приемника к источнику по пройденным на этапе распространения волны ячейкам, следя за тем, чтобы значение монотонно убывали. В результате получают путь, соединяющий эти две точки. Из описания алгоритма следует, что все условия, необходимые для проведения пути, закладываются в правила приписания веса ячейка. Чтобы исключитьнеопределенность при проведении пути для случая, когда несколько ячеек имеют одинаковый минимальный вес, вводят понятие путевых координат задающих предпочтительность проведения трассы.
Проведение трассировки
Требуется соединить контакт 3 DD4 и контакт 5DD5. Волну будем распространять из контакта 3 DD4 (рисунок 6.1).
Рисунок 6.1
Требуется соединить контакт 2 DD3 и контакт 1 DD9. Волну будем распространять из контакта 2 DD3 (рис.6.2).
Рисунок 6.2
Требуется соединить контакт 5 DD3 и контакт 5 DD9. Волну будем распространять из контакта 5 DD3 (рис.6.3).
Рисунок 6.3
Заключение
В процессе выполнения данной работы мы ознакомились с основными алгоритмами компоновки и размещения элементов на монтажном поле. Трассировка шин питания, а также шин земли была произведена по алгоритмам Прима и Краскала, соответственно. Имел место пример трассировки сигнальных цепей по волновому алгоритму. В результате проведенной работы по функциональной схеме "МПС реверсивное с разнополярным тактированием" мы скомпоновали блоки в микросхемы: К155ЛА3, К155ЛА4, К555ЛР1; разместили на плате размером данные микросхемы; произвели трассировку цепей "Земля" по алгоритму Краскала, "Питание" по алгоритму Прима, сигнальных цепей по волновому алгоритму. Вид монтажной платы, сборочный чертеж, схема электрическая принципиальная показаны в приложении.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Н. В. Альферович. Учебное пособие. Проектирование радиоэлектронных средств на корпусных интегральных микросхемах. Минск 2004.
2. Н. В. Альферович. Учебное пособие для студентов специальностей "Моделирование и компьютерное проектирование РЭС", "Радиотехника" и "Радиотехнические системы" всех форм обучения. Минск 2004..
3. А. И. Толстая, И. Л. Селезнев, Т. В. Малышева, И. Н. Цырельчук. Методические указания к лабораторным работам. Автоматизация конструкторского и технологического проектирования РЭС. Минск БГУИР 2009.
51
Документ
Категория
Разное
Просмотров
36
Размер файла
598 Кб
Теги
ммм
1/--страниц
Пожаловаться на содержимое документа