Волновые алгоритмы трассировки

Содержание
ВВЕДЕНИЕ
1. ВЫБОР ТЕХНОЛОГИИ ИЗГОТОВЛЕНИЯ ПЕЧАТНОЙ ПЛАТЫ
2. АНАЛИЗ АЛГОРИТМОВ ТРАССИРОВКИ И КРИТЕРИЕВ КАЧЕСТВА ТРАССИРОВКИ
2.1 Анализ алгоритмов трассировки
2.2 Трассировка печатных плат в системе PCAD
2.2.1. Автотрассировщик Quick Route
2.2.2 Автотрассировщик Pro Route
2.2.3. Бессеточный трассировщик P-CAD Shape-Based Router
2.2.3.1. Настройка стратегии трассировки
2.2.3.2. Ручная трассировка
2.2.3.3. Интерактивная трассировка
2.3 Экспериментальная трассировка печатной платы в среде PCAD 2002
3 КРИТЕРИИ КАЧЕСТВА ТРАССИРОВКИ ПЕЧАТНЫХ ПЛАТ
Рассмотрим общепризнанные критерии качества трассировки печатных плат
3.1 Процент автоматически проложенных соединений
3.2 Число переходных отверстий
3.3 Длина проводников
3.4 Время разводки
4. АНАЛИЗ АЛГОРИТМОВ ТРАССИРОВКИ,ИСПОЛЬЗУЕМЫХ ПРИ ПРОИЗВОДСТВЕ ПЕЧАТНЫХ ПЛАТ
5. ТРЕБОВАНИЯ К АЛГОРИТМУ ТРАССИРОВКИ.
6. РАЗРАБОТКА АЛГОРИТМА ТРАССИРОВКИ
6.1 Разработка структур и типов данных
6.2 Разработка алгоритмов
6.3 Руководство пользователя
6.3.1 Основные сведения
6.3.2 Запуск программы
6.3.3Интерфейс программы
6.3.4Начало работы
6.4 Тестирование программы
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ А Таблица Область применения и практическое обоснование классов точности
ПРИЛОЖЕНИЕ Б Листинг разработанной программы

Волновые алгоритмы трассировки

Волновые алгоритмы выбраны в связи с тем, что это наиболее распространенные, универсальные и отработанные алгоритмы. Они позволяют построить любую сложную трассу, если она вообще существует [96]. Основой построения этих алгоритмов является динамическое программирование [53,96], наиболее полно соответствующее содержанию решаемой задачи [23,38].
Эвристические алгоритмы могут быть применены для анализа возможного движения среди детерминистких препятствий, особенно если препятствия размещены по одному из описанных выше законов регулярности.
Рассмотрим алгоритм волновой трассировки
Пусть задана некоторая плоскость. Рассматривая эту плоскость, как коммутируемое поле, введем прямоугольную систему координат SOT (рис.2.1). Выберем единицы измерения hs и ht соответственно вдоль осей ОS и ОТ. Проведем через точки осей с координатами и , где N, прямые, параллельные осям координат. Тогда рассматриваемая плоскость может быть разбита на элементарные прямоугольные ячейки размером . Прямые разбиения образуют координатную сетку с шагом hs по оси ОS и шагом ht по оси ОТ. Совокупность элементарных ячеек, на которые разбивается выбранная плоскость, назовем дискретным рабочем полем (ДРП).
Рис. 2.1 Модель дискретного рабочего поля для алгоритмов трассировки.
Разбиение на элементарные ячейки может быть как регулярным , так и нерегулярным . Регулярное разбиение на квадраты не вызывает затруднений. Нерегулярное разбиение на прямоугольники несколько сложнее. Желательно, чтобы прямоугольников при разбиении было как можно меньше [53], так как при этом уменьшается время трассировки, а также размеры таблиц для представления данных. Рассмотрим ДРП с регулярным разбиением на квадратные участки .
Таким образом, для решения рассматриваемой задачи целесообразно плату представлять в виде дискретного рабочего поля.
Глобальное планирование трассы можно рассматривать как построение трассы между двумя точками, при наличии запретных участков (препятствий), т.е. при построении траекторий возможно использовать традиционные алгоритмы трассировки для соединения 2-х точек.
В алгоритмах трассировки на первом этапе строятся модели топологии размещения препятствий в виде дискретного рабочего поля [53,96].
Как известно, волновой алгоритм трассировки Ли состоит в следующем [53]: