Автоматизированное топологическое проектирование узла на печатной плате

Размещено на http://www.allbest.ru/

Федеральное агентство по образованию Российской Федерации

Воронежский государственный технический университет

Кафедра конструирования и производства радиоаппаратуры

Курсовой проект

Автоматизированное топологическое проектирование узла на печатной плате

2007

Содержание

Введение

1. Компоновка схемы

1.1 Последовательный алгоритм разбиения

1.2 Метод парных перестановок

1.3 Реализация задачи компоновки

2. Размещение компонентов схемы на плате

2.1 Последовательный алгоритм размещения

2.2 Алгоритм размещения методом парных перестановок

2.3 Реализация алгоритмов размещения компонентов схемы на плате

3. Трассировка соединений

3.1 Построение минимального покрывающего дерева с помощью алгоритма Прима

3.2 Расслоение топологии

3.3 Волновой алгоритм проведения трассировки

3.4 Реализация алгоритмов решения задачи трассировки

Заключение

Список литературы

Приложение

Введение

Целью курсового проекта является изучение и практическое применение конкретных математических методов и алгоритмов, используемых при автоматизированном топологическом проектировании узлов РЭС на печатных платах для решения задач конструктивного синтеза и анализа проектных решений.

Курсовой проект содержит решение трех типовых задач топологического проектирования РЭС: компоновки, размещения и трассировки соединений.

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

Рисунок 1 ? Исходный граф схемы

1. Компоновка схемы

Компоновкой электрической схемы на конструктивно законченные части называется процесс распределения элементов низшего конструктивного уровня в высший в соответствии с выбранным критерием.

Такими критериями могут быть: минимум типов конструктивно законченных частей, плотность компоновки, минимум соединений между устройствами, простота диагностирования схем и т.д.

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

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

Задача компоновки: разбить граф G(А;U), который является математической моделью электрической схемы, на части, называемые подграфами, Gi(Аi;Ui), i=1,2,…,k, чтобы выполнялись условия:

Gi(Аi;Ui)? Gj(Аj;Uj)=Ш и .

1.1 Последовательный алгоритм разбиения

Последовательный алгоритм разбиения имеет ограниченное число шагов, которое не превышает числа элементов в схеме (n), а значит, обладает высоким быстродействием, но точность результатов невелика.

Для реализации этого алгоритма необходимо по матрице смежности выбрать модуль, имеющий наибольшее число соединений с остальными. Полученная группа модулей, состоящая из выбранного модуля и соединенного с ним, помещается в первый блок (с числом вершин n1). Сравнивается число вершин в первом блоке с максимальным числом вершин в подграфе (N):если n1 = N, то формирование блока закончено; если n1 <N, то к выделенной группе добавляется модуль, имеющий максимальное число соединений с модулями этой группы, этот процесс продолжается до тех пор пока не выполнится условие n1 = N; если n1 > N, то из выделенной группы убирается модуль, имеющий наименьшее число связей с оставшимися. Для модулей, не вошедших в этот блок, процесс повторяется до распределения всех элементов по блокам.

1.2 Метод парных перестановок

Пусть в результате произвольного начального распределения сформированы Z блоков. Обозначим их через X, X, X,...,XZ. Подсчитав количество соединений между двумя блоками, например, между блоком Х и блоком Х, меняем взаимно местами по одному модулю из блока Х и из блока Х. После этого вновь считаем количество соединений между блоками. Если после перестановки количество соединений уменьшилось, то перестановка целесообразна. Если же увеличилось или осталось прежним, по перестановка не целесообразна. Можно производить перестановку каждого модуля блока Х с каждым модулем блоков Х, Х, ..., Хz, а затем каждого модуля блока Х с каждым модулем остальных блоков и т.д. В результате можно получить минимизацию соединений между блоками.

Целесообразность перестановки i - го элемента, находящегося в блоке Х, с j - м элементом, находящимся в блоке Х, определяется по формуле:

 (1)

где - функционал для элементов и ;

- количество внешних соединений элемента с блоком Х;

- количество внешних соединений элемента с блоком Х;

- количество внутренних соединений элемента блока Х с другими элементами этого же блока;

- количество внутренних соединений элемента блока Х с другими элементами этого же блока;

- количество общих (прямых) соединений между переставляемыми элементами и.

- первый блок; Х - множество элементов блока (обозначаются буквой i).

- второй блок; Х- множество элементов блока (обозначаются буквой j).

Если 0, то перестановка этих элементов нецелесообразна, то есть эта перестановка не ведет к уменьшению числа межблочных соединений, а ведет к их возрастанию или не изменяет их количество. Если > 0, то перестановка целесообразна. Далее, подсчитав функционалы всех пар элементов и произведя перестановку двух элементов, для которых функционал имеет максимальное положительное значение, вновь производят вычисления всех функционалов для этих двух блоков. Если окажется, что для каких-либо двух элементов функционал больше нуля, то снова производят перестановку и так несколько раз, до тех пор, пока все функционалы будут равны или меньше нуля. Следует подчеркнуть, что после каждой перестановки все функционалы вычисляются вновь. В результате таких перестановок достигается обычно локальный минимум межблочных соединений.

1.3 Реализация задачи компоновки

Матрица смежности

Модуль А3 имеет максимальное число соединений с остальными модулями. Выбирая модули, имеющие максимальное число соединений с модулем А3, получим разбиение исходной схемы на два блока. В состав первого блока входят модули А1, А2, А4, А5, А7, в состав второго блока - модули А3, А6, А8, А9, А10.

Для оптимизации числа межблочных соединений воспользуемся алгоритмом парных перестановок, рассчитав значения функционалов для каждой пары модулей по выше приведённой формуле.

радиоэлектронный печатный плата узел



Получили, что для двух пар модулей F > 0. Это пары Х5Х6 и Х5Х10, для которых F56 =4 и F510 =8. Проведем перестановку двух элементов для которых функционал имеет максимальное положительное значение, то есть поменяем местами элементы 5 и 10. Далее вновь произведем вычисления всех функционалов для этих двух блоков.

В состав первого блока входят модули А1, А2, А4, А7, А10, в состав второго блока - модули А3, А5, А6, А8, А9.



Все функционалы отрицательны, а значит, размещение модулей по блокам оптимально, перестановка не требуется. На рисунке 2 показана компоновка модулей по блокам.

Рисунок 2 ? Компоновка модулей по блокам

2. Размещение компонентов схемы на плате

С помощью последовательного алгоритма проводится размещение компонентов одного из полученных при компоновке блоков на коммутационном поле платы, а затем осуществляется оптимизация начального варианта размещения с помощью итерационного алгоритма.

Но сначала необходимо определить размер платы. Учитывая, что размер модулей 7Ч14, количество модулей - 10, коэффициент заполнения К = 0,5, рассчитаем площадь платы:

.

2.1 Последовательный алгоритм размещения

На первом шаге устанавливаются разъёмы в областях на краю платы, на каждом последующем шаге выбирается из схемы модуль, имеющий максимальное число соединений с уже установленными модулями. Этот модуль устанавливается в ближайшую свободную область у ранее размещенных модулей.

2.2 Алгоритм размещения методом парных перестановок

Сначала по заданной исходной схеме составляется матрица связей, в которой каждый элемент показывает количество связей между i-ым и j-ым модулями.

По заданному исходному размещению модулей в позициях составляется матрица расстояний, в которой каждый элемент показывает в условных единицах длины расстояние между i-ым и j-ым модулями.

После этого по специально выведенной формуле (2) производится вычисление значений Wij - величин, показывающих изменение суммарной длины соединений при перестановке местами i-го и j-го модулей.

(2)

Если Wij меньше или равно нулю, то перестановка считается нецелесообразной. Если же Wij больше нуля, то перестановка считается целесообразной, i-ый и j-ый модули переставляются местами и вычисление значений Wij для нового размещения модулей в позициях производится вновь и так до тех пор, пока не наступит оптимизация, т. е. все значения Wij будут отрицательными или равными нулю.

2.3 Реализация алгоритмов размещения компонентов схемы на плате

Рассмотрим блок 1, в состав которого входят модули А1, А2, А4, А7, А10. Используя последовательный алгоритм размещения, проведем размещение модулей на плате. Наименьшее число связей с другими модулями имеют модули А2. Расположим модуль А2 ближе к разъёму. Наибольшее число связей у А2 с модулем А1, поэтому располагаем его рядом с модулем А2. Рассуждая таким образом, получим схему размещения, представленную на рисунке 3.

Рисунок 3 ? Размещение компонентов первого блока на плате

Координаты модулей, входящих в состав блока №1: А1 - (20;10), А2 - (12;10), А4 - (4;30), А7 - (20;30), А10 - (12;30).

Матрица соединений модулей блока №1

Суммарная длина соединений для начального размещения рассчитывается по формуле (3):

(3)

W0=1·(8+0)+3·(16+20)+5·(0+20)+0+0+1·(8+20)+0+4·(16+0)+1·(8+0)+5·(8+0=356

По формуле (2) вычисляются значения ДWij показывающие изменение суммарной длины соединений при перестановке местами i-го и j-го модулей.

Аналогично получим значения для остальных ДWij:

ДW14 = ?36, ДW17 = ?120, ДW110 = 44, ДW24 = ?104, ДW27 = ?60, ДW210 = ?120, ДW47 = ?32, ДW410 = 16, ДW710 = ?8.

Из всех значений Wij выбираем максимальное. Им является W110 = 44, и так как оно положительное то производим перестановку местами модулей 1 и 10. Схема расположения модулей после перестановки показана на рисунке 4.

Рисунок 4 ? Размещение компонентов первого блока на плате после перестановки

Координаты модулей, входящих в состав блока №1 после перестановки: А1 - (12;30), А2 - (12;10), А4 - (4;30), А7 - (20;30), А10 - (20;10). Аналогичным образом вычислим все значения Wij уже для нового размещения модулей.

W0=1·(0+20)+3·(8+0)+5·(8+0)+0+0+1·(8+20)+0+4·(16+0)+1·(16+20)+

+5·(0+20)=312ед.

ДW12 = ?140, ДW14 = ?8, ДW17 = ?32, ДW110 = ?44, ДW24 = ?32,

ДW27 = ?60, ДW210 = ?24, ДW47 = ?64, ДW410 = ?40, ДW710 = ?140.

Так как все ДWij ? 0, то можно сделать вывод, что модули размещены наилучшим образом, можно переходить к следующему пункту - трассировке соединений.

Эскиз платы с элементами представлен на рисунке 5.



Рисунок 5 ? Эскиз платы с элементами.

3. Трассировка соединений

Для полученного варианта размещения компонентов схемы на плате необходимо построить кратчайшие покрывающие деревья с помощью алгоритма Прима.

Для ликвидации пересечений проводников и уменьшения плотности соединений на плате ? провести распределение проводников по слоям.

Для двух-трех наиболее длинных проводников провести трассировку соединений с помощью волнового алгоритма.

3.1 Построение минимального покрывающего дерева с помощью алгоритма Прима

Выбирается произвольно одна из вершин графа и соединяется с ближайшей к ней. Выбирается вершина, ближайшая к одной из двух уже соединенных и соединяется с этой вершиной. На каждом шаге из оставшихся вершин выбирается ближайшая к уже соединённым и соединяется с соответствующими вершиной. Для удобства реализации этого алгоритма первоначально составляется матрица длин D, общий элемент которой dij равен расстоянию между i-й и j-й точками.

3.2 Расслоение топологии

Для того чтобы реализовать схему без пересечений проводников, но с минимальным числом слоев воспользуемся методом раскраски вершин графа (определения хроматического числа графа). Хроматическое число - минимально необходимое количество цветов для того, чтобы раскрасить вершины графа так, что все соединяющиеся между собой ребрами вершины были разноцветны. Для решения задачи расслоения используется граф пересечения - граф, число вершин которого соответствует числу ребер исходного графа схемы, при этом соединены те вершины, которые соответствуют пересекающимся ребрам исходного графа. Необходимое число слоев печатной платы соответствует хроматическому числу графа пересечения.

3.3 Волновой алгоритм проведения трассировки

Предварительно поверхность печатной платы разбивается на ячейки, размер которых соответствует минимально допустимой ширине проводника. В процессе трассировки идет распространение числовой волны от источника к приёмнику. Для этого ячейки, начиная от источника, нумеруются целыми числами с шагом 1. Совокупность ячеек с одинаковым номером - фронт волны. Распространения волны заканчивается, когда очередной фронт дойдет до приемника. Соединения проводят через ячейки с последовательно убывающим номером (от преемника к источнику). Достоинством этого алгоритма является возможность огибания препятствий и построения нескольких соединений различной конфигурации, но одинаковой длины.

3.4 Реализация алгоритмов решения задачи трассировки

Составим матрицу длин для блока №1

Выбираем модуль А4, просматриваем первую строку, находим первый минимальный элемент - длина соединения между модулями А4 и А1 равна 8 единиц, проводим это соединение, вычеркивая первый и третий столбцы. Далее алгоритм повторяется до полного покрытия пространства трассами. Минимальное покрывающее дерево, построенное с помощью алгоритма Прима для блока №5, представлено на рисунке 6. Исходный граф схемы представлен на рисунке 7, а граф пересечения для определения хроматического числа - на рисунке 8.

Рисунок 6 ? Минимальное покрывающее дерево для блока №1

Рисунок 7 ? Исходный граф схемы

Рисунок 8 ? Граф пересечения

На рисунке 7 видно два пересечения ребер исходного графа, с помощью этого рисунка построен граф пересечений, содержащий два ребра и десять вершин, окрашенных в два цвета. Вершина u6 окрашена в черный цвет, остальные вершины - в серый. Это значит, что печатная плата содержит только два слоя, в одном из которых находятся проводник u6, в другом слое - остальные проводники.

Для реализации волнового алгоритма проведения проводников выбраны соединения между элементами А1 и А7 (1/4 и 7/4), результаты представлены на рисунке 9, и между элементами А8 и А9 (7/2 и 10/8) - результат на рисунке 10.

Рисунок 9 ? Распространение волны для соединения модулей А4 и А10.

Рисунок 10 ? Распространение волны для соединения модулей А7 и А10.

Заключение

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

С помощью последовательного алгоритма разбиения получили начальный вариант разбиения всех модулей схемы на два блока, воспользовавшись итерационным алгоритмом, а точнее методом парных перестановок определили оптимальный вариант компоновки модулей. Решена задача размещения модулей на плате, основным критерием которой явилась минимизация суммарных длин соединений. Проведена трассировка соединений построением минимального покрывающего дерева с помощью алгоритма Прима и волнового алгоритма трассировки (алгоритма Ли). Расслоение топологии методом определения хроматического числа графа позволило выявить минимальное число слоев платы.

Список литературы

1. Автоматизация проектирования РЭС: Учеб. пособ. для вузов О.В, Алексеев, А.А. Головков, И.Ю. Пивоваров и др.; Под. ред О.В.Алексеева. М: Высшая школа, 2000. 479 с.

2. Автоматизация оптимальной компоновки модулей РЭС с помощью ПЭВМ. Методические указания к лабораторной работе по дисциплине "Основы проектирования РЭС" для студентов дневного и заочного обучения специальности 200 800 "Проектирование и технология производства РЭС"/Воронеж, гос. техн. ун-т; Сост. В.С. Скоробогатов. Воронеж, 1998. - 24с.

3. Оптимизация размещения модулей на коммутационном поле методом парных перестановок. Методическое указания к лабораторной работе по дисциплине "Основы проектирования РЭС" для студентов дневного и заочного обучения специальности 200 800 "Проектирование и технология производства РЭС"/Воронеж, гос. техн. ун-т; Сост. В.С. Скоробогатов. Воронеж, 1998. - 24 с

4. Норенков И.П. Введение в автоматизированное проектирование технических устройств и систем: Учеб. пособие для втузов - 2-е изд., перераб. и доп. - М.: Высш. шк., 1986. - 304 с., ил.

Приложение

Группа: РК-032

Студент: Макевв Сергей Николаевич.

-------------------------

Связи для элемента №1.

Вывод №1--2/1, 5/3,

Вывод №2--

Вывод №3--

Вывод №4--5/8, 7/4,

Вывод №5--4/6, 7/9,

Вывод №6--4/10, 6/8,

Вывод №7--3/4, 4/9, 7/2,

Вывод №8--5/3, 7/7,

Вывод №9--3/3, 7/8,

Вывод №10--

---------------

Связи для элемента №2.

Вывод №1--5/7,

Вывод №2--

Вывод №3--

Вывод №4--

Вывод №5--3/3,

Вывод №6--

Вывод №7--

Вывод №8--7/9,

Вывод №9--

Вывод №10--

---------------

Связи для элемента №3.

Вывод №1--5/10,

Вывод №2--6/2, 6/2, 8/4, 9/3, 9/8, 10/9,

Вывод №3--

Вывод №4--5/5, 9/4,

Вывод №5--6/3, 10/4, 10/7,

Вывод №6--6/8, 8/1, 9/5,

Вывод №7--8/2, 8/8,

Вывод №8--5/3, 5/5, 10/1,

Вывод №9--

Вывод №10--4/2, 5/7, 6/2,

---------------

Связи для элемента №4.

Вывод №1--8/1, 8/7, 8/2, 10/6,

Вывод №2--7/5,

Вывод №3--

Вывод №4--7/5,

Вывод №5--8/9,

Вывод №6--7/8,

Вывод №7--

Вывод №8--9/7,

Вывод №9--7/1, 9/10,

Вывод №10--

---------------

Связи для элемента №5.

Вывод №1--9/9, 10/5,

Вывод №2--8/2, 10/3,

Вывод №3--9/3, 10/6,

Вывод №4--

Вывод №5--

Вывод №6--

Вывод №7--9/5, 10/7,

Вывод №8--6/7, 6/9, 6/7, 9/6, 10/1,

Вывод №9--

Вывод №10--6/9, 8/6,

---------------

Связи для элемента №6.

Вывод №1--8/3, 9/5,

Вывод №2--7/4, 9/6,

Вывод №3--

Вывод №4--10/10,

Вывод №5--7/5,

Вывод №6--9/4, 10/10,

Вывод №7--8/6, 8/5,

Вывод №8--8/2,

Вывод №9--

Вывод №10--7/10, 7/2, 9/8,

---------------

Связи для элемента №7.

Вывод №1--

Вывод №2--8/8, 10/8, 10/10,

Вывод №3--

Вывод №4--8/10, 8/8,

Вывод №5--

Вывод №6--10/10, 10/8, 10/10,

Вывод №7--8/6,

Вывод №8--8/9,

Вывод №9--

Вывод №10--

---------------

Связи для элемента №8.

Вывод №1--

Вывод №2--

Вывод №3--10/7, 10/5,

Вывод №4--10/10,

Вывод №5--9/6, 9/7,

Вывод №6--9/3, 10/6,

Вывод №7--

Вывод №8--

Вывод №9--9/10,

Вывод №10--9/8, 10/6,

---------------

Связи для элемента №9.

Вывод №1--

Вывод №2--

Вывод №3--

Вывод №4--

Вывод №5--

Вывод №6--

Вывод №7--

Вывод №8--

Вывод №9--

Вывод №10--

---------------

Связи для элемента №10.

Вывод №1--

Вывод №2--

Вывод №3--

Вывод №4--

Вывод №5--

Вывод №6--

Вывод №7--

Вывод №8--

Вывод №9--

Вывод №10--

---------------

Таблица Количества Связей

1 2 3 4 5 6 7 8 9 10

1 X 1 2 3 3 1 5 0 0 0

2 0 X 1 0 1 0 1 0 0 0

3 0 0 X 1 5 5 0 4 4 4

4 0 0 0 X 0 0 4 4 2 1

5 0 0 0 0 X 4 0 2 4 5

6 0 0 0 0 0 X 4 4 4 2

7 0 0 0 0 0 0 X 5 0 5

8 0 0 0 0 0 0 0 X 5 5

9 0 0 0 0 0 0 0 0 X 0

10 0 0 0 0 0 0 0 0 0 X

Размещено на Allbest.ru