A Formal Algorithm for Routing Traces on a Printed Circuit Board
D. R. Hedgley · NASA Technical Reports Server (NASA) · 1996
This paper addresses the classical problem of printed circuit board routing: that is, the problem of automatic routing by a computer other than by brute force that causes the execution time to grow exponentially as a function of the complexity. Most of the present solutions are either inexpensive but not efficient and fast, or efficient and fast but very costly. Many solutions are proprietary, so not much is written or known about the actual algorithms upon which these solutions are based. This paper presents a formal algorithm for routing traces on a printed circuit board. The solution presented is very fast and efficient and for the first time speaks to the question eloquently by way of symbolic statements. NOMENCLATURE The following nomenclature do not appear in alphabetical order as each definition is predicated upon previous definitions. the major axis (horizontal or vertical direction) where the sequence is associated with. the minor axis (horizontal or vertical direction) where the sequence i s associated with. RM a rectangular matrix of evenly spaced grid points where a node is defined to be an arbitrary grid point belonging to RM. RM represented as a sequence of horizontal lines composed of grid points. RM represented as a sequence of vertical lines composed of grid points (fig. 1). µ Ji { } µ β Mki { } β