Информационные технологии проектирования электронных средств

- 59 - Тема: Методы автоматизированной трассировки соединений ЛЕКЦИЯ 18. Трассировка соединений с помощью построения деревьев Исходная информация: список цепей, параметры конструкции элемен- тов и коммутационного поля, результат размещения элементов на коммутаци- онном поле. В зависимости от конструктивной реализации связей выделяют следу- ющие виды трассировки: проводных соединений, печатных соединений, меж- соединений на кристалах БИС. Основным критерием трассировки проводных соединений является ми- нимум суммарной длины. Проводники изолированы друг от друга и нет огра- ничений на пересечение трасс. При автоматизированном конструировании пе- чатного и проводного монтажа возникает задача построения минимальных де- ревьев соединений. Сформулируем задачу трассировки следующим образом. Пусть P ={ p 1 , p 2 ,…, p n } – множество точек на плоскости, соответствую- щих выводам произвольной цепи. Рассмотрим полный граф G ( X , U ), где x i ∈ X соответствуют выводам це- пей, а ребра u j ∈ U характеризуют соединения между парами выводов. Каждому ребру u j приписан вес λ ( u j ), который может быть равен рассто- янию между соответствующими точками множества Р или может быть выра- жен как линейная комбинация: λ ( u j )= k 1 d 1 ( u j )+…+ k ν d ν ( u j ), где k s ( s =1,…, m ) – коэффициент ; d s ( u j ) − некоторая характеристика соеди-нения u j . Теперь необходимо в графе G ( X , U ) определить дерево, включа- ющее в себя все вершины х j ∈ X и имеющее минимальный суммарный вес ребер, т.е. кратчайшее покрывающее дерево (КПД).