Browse Prior Art Database

Wire Path Adjacency Avoidance

IP.com Disclosure Number: IPCOM000077163D
Original Publication Date: 1972-Jun-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 2 page(s) / 32K

Publishing Venue

IBM

Related People

Rubin, F: AUTHOR

Abstract

In the process of routing printed wire paths, a major difficulty is that the current wire may block future wires. Whenever two wire paths are adjacent, the two paths act as one large obstacle to future paths, rather than as separate small obstacles. A major thrust, then, is to keep wires apart.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 74% of the total text.

Page 1 of 2

Wire Path Adjacency Avoidance

In the process of routing printed wire paths, a major difficulty is that the current wire may block future wires. Whenever two wire paths are adjacent, the two paths act as one large obstacle to future paths, rather than as separate small obstacles. A major thrust, then, is to keep wires apart.

The technique to be introduced here is to adjust the path cost function to penalize path adjacencies. The new path cost function may be minimized by the Lee algorithm. One means of measuring adjacency is to examine the neighbors of each cell on the path for some distance in each direction, and add penalties according to the distance to each direction. The path cost function will then be f(p) = g(p) + Sigma over x epsilon p adj(x). where p is a path, f is the new cost function, g is the old cost function, and (x) is the set of cells on the path. The adjacency function, adj(x) has the form aL(x) + aR(x) + a (x) + aD(x) where L, R, U, and D are the four directions left, right, up, and down.

The penalty for an obstacle at distance d from the present cell should have the property that a path will tend to center itself between two obstacles. This will leave the most room for future paths. Let the distance between obstacles be 2d+1. Then the adjacency penalty will be a(d+e) + a(d-e). If we wish centering then a(d+e) + a(d-e) c a(d+h) + a(d-h) whenever h > e. One function with this property is a(d) = -- where K is some constant. For then a(d+e) + a(d-...