Connection Routing Algorithm for Printed Circuit Boards

A generalized algorithm for forming interconnections between points on a multilayer circuit board is described and evaluated. The algorithm treats interconnections on individual layers and connections between layers by means of plated holes. Generalizing the well-known Lee algorithm and using its terminology, this algorithm makes use of a coded C array that is stored in memory and records the state of the multilayer circuit board. Completed paths, possible remaining paths between points to be connected, and circuitboard interconnection restrictions are recorded in the coded C array. The algorithm consists of five iterative steps that involve decisions on the basis of the state of the circuit board as stored in the C array. All possible routes are attempted, and the routing sequence is stopped when the path is completed or all attempted path routes are exhausted. A number of modifications to the algorithm permitting various circuit connection constraints to be satisfied are also presented. The algorithm has been programmed for a GE-635 computer. Typical results for some of the printed circuit boards that were used to evaluate the algorithm are included.