Data processing: generic control systems or specific application – Specific application – apparatus or process – Product assembly or manufacturing
Reexamination Certificate
1998-01-23
2001-05-01
Gordon, Paul P. (Department: 2786)
Data processing: generic control systems or specific application
Specific application, apparatus or process
Product assembly or manufacturing
C700S096000, C700S098000, C700S117000, C700S121000, C716S030000, C716S030000, C716S030000, C716S030000
Reexamination Certificate
active
06226560
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to a method for routing wires or conductors on a printed-circuit board. This invention also relates to a method of enlarging the wire widths and wire spacings to optimize the surface area of the printed circuit board.
BACKGROUND OF THE INVENTION
Free-angle wiring is based on circular arcs and lines with Euclid distance and can utilize a wiring region more effectively than conventional rectilinear wiring or octilinear wiring. Where semiconductor chips are mounted on a printed-circuit board with high density, free-angle wiring will be very useful if it can be performed at high speed and automatically. A method of perfect free-angle wiring is described, for example, in Shaodi Gao, Mark Jerrum, Michael Kaufman, Kurt Mehlhorn, Wolfgang Rueling, and Christopher Storb, “On continuous homotopic one layer routing,” in Proceedings of the 4th annual ACM Symposium on Computational Geometry, pages 392-402, ACM, 1988. However, there is no practical free-angle wiring method.
Techniques for even-spacing and wire-width enlargement are important in order to enhance the yield and the stability in electrical characteristics of pin-grid array (PGA) packages, ball-grid array (BGA) packages, and multi-chip modules (MCMs) in addition to printed-circuit boards which utilize very fine wires. For PGA packages, a method for automatically realizing even-spacing and wire-width enlargement has been reported (in Changsheng Ying and Jun Gu, “Automated pin-grid array package routing on multilayer ceramic substrates,” IEEE Transaction on Very Large Scale Integration (VLSI) SYSTEMS, 1(4), pages 571-575, 1993). However, in this method, wires are only line segments which extend radially from the center, there is also a grid-shaped array of pins, which is characteristic of PGA packages. Consequently, this method lacks extensibility. As a matter of course, there is no product which carries out even-spacing and wire-width enlargement by general free-angle wiring.
A general object of the present invention is to provide a practical method and apparatus for routing wires between terminals on a printed circuit-board or other substrate.
Another object of the present invention is to provide a practical free-angle wiring method and apparatus which also enlarges wire spacings and wire widths to fully utilize the available surface area of the board.
SUMMARY OF THE INVENTION
The present invention transforms a topological wire route to a physical wire route. (A topological wire route is a surface configuration of a conceptual wire that meets less than all routing criteria. A topological wire route can, for example, be defined relative to the positions of other wires, pads, or other obstacles on a printed circuit board. For example, a portion of a topological wire “a” can be defined as residing somewhere between topological wires “b” and “c” and another portion of the topological wire “a” can be defined as residing somewhere between topological wire “x” and pad “y”.) A physical wire has a precise physical path on a board and should meet most if not all of the routing criteria. The transformation is achieved by (1) selecting a topological wire to be transformed, (2) generating a fan-shaped or arcuate forbidden region around each of various obstacles which includes pads, terminals, lands and other conductive regions, and (3) obtaining a shortest route for the selected wire so as not to pass through any of the forbidden regions. By enlarging the radius of the fan of this generated forbidden region, even-spacing and wire-width enlargement are realized.
According to one aspect of the invention, a topological wire is first selected. Then, obstacles which sight the selected topological wire are specified. A fan is set to each of the specified obstacles as a forbidden region, wherein each fan has a radius that is a predetermined number times minimum spacing that is required between each physical wire and each of the identified obstacles. The fan radius accounts for the wire widths and spacings between the selected topological wire and the identified obstacles. The physical wire is laid out along a shortest route which avoids forbidden regions. In this embodiment, when wire-width enlargement is performed, the right and left boundaries of the wire to be transformed are separately determined as the shortest route.
According to another aspect of the present invention, the foregoing determination of the forbidden regions is performed only for obstacles that “sight” the topological wire, i.e. “sight” means that a straight line can be drawn between the center of two obstacles and intersect the topological wire without the line being obstructed by another intervening obstacle.
In accordance with another aspect of the present invention, the radius of a fan-shaped forbidden region is enlarged to perform the even-spacing and enlargement of a wire. A factor is then identified for allocating surplus space on the board to enlargement of wire width and a factor for allocating surplus space to enlargement of wire spacing. By selecting wires which cross a critical cut between a first obstacle and a second obstacle and spacings of the wires, the upper limit of a wire width enlargement ratio relative to the second obstacle is determined in a range allowed by the factor for allocating to enlargement of wire width. In addition, the upper limit of a wire spacing enlargement ratio relative to the second obstacle is determined in a range allowed by the factor for allocating to enlargement of wire spacing. The lowest upper limit among the upper limits of the wire width enlargement ratios relative to obstacles which compose critical cuts with the first obstacle is stored as a wire width enlargement ratio of the first obstacle. In addition, the lowest upper limit among the upper limits of the wire spacing enlargement ratios relative to obstacles which compose critical cuts with the first obstacle is stored as a wire spacing enlargement ratio of the first obstacle. Furthermore, wires between a selected wire and the first obstacle are identified. The widths of the specified wires are enlarged by employing the wire width enlargement ratio set to the first obstacle, and the wire spacings between the specified wires are enlarged by employing the wire spacing enlargement ratio set to the first obstacle. The radius of the forbidden region is then calculated by adding the enlarged wire widths and the enlarged wire spacings for the specified wires.
REFERENCES:
patent: 4484292 (1984-11-01), Hong et al.
patent: 5438166 (1995-08-01), Carey et al.
patent: 5521837 (1996-05-01), Frankle et al.
patent: 5790414 (1998-08-01), Okano et al.
patent: 5880969 (1999-03-01), Hama et al.
patent: 5889677 (1999-03-01), Yasuda et al.
“On Continuous Homotopic One Layer Routing” by Gao et al, Proceedings of the 4th Annual ACM Symposium on Computation Geometry, pp. 392-402, ACM, 1988.
“Automated Pin Grid Array Package Routing on Multilayer Ceramic Substrates” by Ying et al, IEEE Transaction on Very Large Scale Integration (VLSI) Systems, vol. 1, No. 4, pp. 571-575, 1993.
“Topological Routing in SURF: Generating a Rubber-Bank Sketch” by Dai et al, 28th Design Automation Conference, pp.39-44, 1991.
Etoh Hiroaki
Hama Toshiyuki
Gordon Paul P.
International Business Machines - Corporation
Patel Ramesh
Samodovitz Arthur J.
LandOfFree
Method and apparatus for optimizing the path of a physical wire does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for optimizing the path of a physical wire, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for optimizing the path of a physical wire will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2444240