Patent US6128767A successfully refreshed from Google Patents.
US6128767A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Polygon representation in an integrated circuit layout
Assignee: Individual
•
Filing: 1997-10-30
•
Granted: 2000-10-03
•
Expires: 2017-10-30
Abstract
Abstract An approach for representing polygons in an integrated circuit (IC) layout is provided. Polygons are represented by one or more wires, which in turn are each represented by one or more wire segments. Each wire segment is represented by a pair of directed line segments. A data structure hierarchy includes polygon data, wire data, wire segment data and branch data. The polygon data represents a set of IC devices to be represented in the IC layout. The wire data represents the wires that represent the polygons and specifies the associated wire segments and associated polygons. The wire segment data represents the wire segments and specifies the associated directed line segments for each wire segment that represent the wires and references the wire data. The branch data specifies connections between wires by specifying the connecting wire segments in the wires. A spacing check between a first polygon and a second polygon involves determining the canonical direction from the first polygon to the second polygon and testing the two closest faces between the polygons. To satisfy a spacing violation, an exclusion zone is constructed around the first polygon and the second polygon is moved a distance outside the exclusion zone which causes the minimum spacing required by a set of predetermined spacing criteria to be satisfied.
Inventors
- 👤 David C. Chapman
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:51
CPC Classifications
H; H10; H10D; H10D84/00; H10D84/01; G; G06; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398; H10W; H10W72/00; H10W72/071; H10W72/075
Claims Analysis
Total Claims: 42
Claim 1
Independent Claim
195 words
A computer system for generating a data representation of an integrated circuit (IC) layout, the computer system comprising: a) a memory; and b) one or more processors coupled to the memory, wherein the memory contains a set of instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of i) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires, each of the one or more wires is represented by one or more wire segments and each of the one or more wire segments is represented by two directed line segments, ii) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data, iii) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data, and iv) generating directed line segment data that represents the two directed line segments for each wire segment and indicates a direction of each directed line segment.
Claim 2
Dependent Claim
195 words
A computer system for generating a data representation of an integrated circuit (IC) layout, the computer system comprising: a) a memory; and b) one or more processors coupled to the memory, wherein the memory contains a set of instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of i) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires, each of the one or more wires is represented by one or more wire segments and each of the one or more wire segments is represented by two directed line segments, ii) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data, iii) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data, and iv) generating directed line segment data that represents the two directed line segments for each wire segment and indicates a direction of each directed line segment.
Claim 3
Dependent Claim
66 words
The computer system of claim 1, wherein the set of instructions further includes instructions which, when executed by the one or more processors cause the one or more processors to perform the steps of: v) generating at least one reference in the polygon data that references the wire data, and vi) generating at least one reference in the wire data that references the wire segment data.
Claim 4
Dependent Claim
105 words
The computer system of claim 2, wherein the step of v) generating at least one reference in the polygon data that references the wire data includes the step of for each wire represented in the wire segment data, generating a reference in the polygon data that references data in the wire data that represents that wire, and the step of vi) generating at least one reference in the wire data that references the wire segment data includes for each of the one or more wires generating a reference in the wire data that references both the first and last wire segments contained in the wire.
Claim 5
Dependent Claim
80 words
The computer system of claim 1, wherein the directed line segment data indicates for each directed line segment a change in first coordinates for a change in second coordinates, and the set of instructions further includes instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of generating directed line segment data that indicates for each directed line segment a change in first coordinates for a change in second coordinates.
Claim 6
Dependent Claim
45 words
The computer system of claim 1, wherein the set of instructions further includes instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of generating branch data that specifies wire segments associated with connected wires.
Claim 7
Dependent Claim
178 words
A computer-readable medium carrying sequences of instructions for generating a data representation of an integrated circuit layout, the sequences of instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires, each of the one or more wires is represented by one or more wire segments and each of the one or more wire segments is represented by two directed line segments, b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data, c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data, and d) generating directed line segment data that represents the two directed line segments for each wire segment and indicates a direction of each directed line segment.
Claim 8
Dependent Claim
178 words
A computer-readable medium carrying sequences of instructions for generating a data representation of an integrated circuit layout, the sequences of instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires, each of the one or more wires is represented by one or more wire segments and each of the one or more wire segments is represented by two directed line segments, b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data, c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data, and d) generating directed line segment data that represents the two directed line segments for each wire segment and indicates a direction of each directed line segment.
Claim 9
Dependent Claim
46 words
The computer-readable medium of claim 6, wherein the sequences of instructions include instructions for e) generating at least one reference in the polygon data that references the wire data, and f) generating at least one reference in the wire data that references the wire segment data.
Claim 10
Dependent Claim
103 words
The computer-readable medium of claim 7, wherein the step of e) generating at least one reference in the polygon data that references the wire data includes the step of for each wire represented in the wire segment data, generating a reference in the polygon data to data in the wire data that represents that wire, and the step of f) generating at least one reference in the wire data that references the wire segment data includes for each of the one or more wires generating a reference in the wire data to both the first and last wire segments contained in the wire.
Claim 11
Dependent Claim
65 words
The computer-readable medium of claim 6, wherein the directed line segment data indicates for each directed line segment a change in first coordinates for a change in second coordinates, and the sequences of instructions further include instructions for performing the step of generating directed line segment data that indicates for each directed line segment a change in first coordinates for a change in second coordinates.
Claim 12
Dependent Claim
31 words
The computer-readable medium of claim 6, wherein the plurality of sequences of instructions includes instructions for performing the step of generating branch data that specifies wire segments associated with connected wires.
Claim 13
Independent Claim
155 words
A method for generating a data representation of an integrated circuit (IC) layout, the method comprising the steps of: a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires, each of the one or more wires is represented by one or more wire segments and each of the one or more wire segments is represented by two directed line segments, b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data, c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data, and d) generating directed line segment data that represents the two directed line segments for each wire segment and indicates a direction of each directed line segment.
Claim 14
Independent Claim
155 words
A method for generating a data representation of an integrated circuit (IC) layout, the method comprising the steps of: a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires, each of the one or more wires is represented by one or more wire segments and each of the one or more wire segments is represented by two directed line segments, b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data, c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data, and d) generating directed line segment data that represents the two directed line segments for each wire segment and indicates a direction of each directed line segment.
Claim 15
Dependent Claim
42 words
The method of claim 11, further including the steps of e) generating at least one reference in the polygon data that references the wire data, and f) generating at least one reference in the wire data that references the wire segment data.
Claim 16
Dependent Claim
102 words
The method of claim 12, wherein the step of e) generating at least one reference in the polygon data that references the wire data includes the step of for each wire represented in the wire segment data, generating a reference in the polygon data to data in the wire data that represents that wire, and the step of f) generating at least one reference in the wire data that references the wire segment data includes for each of the one or more wires generating a reference in the wire data to both the first and last wire segments contained in the wire.
Claim 17
Dependent Claim
59 words
The method of claim 11, wherein the directed line segment data indicates for each directed line segment a change in first coordinates for a change in second coordinates, and the method further includes the step of generating directed line segment data that indicates for each directed line segment a change in first coordinates for a change in second coordinates.
Claim 18
Dependent Claim
21 words
The method of claim 11, further including the step of generating branch data that specifies wire segments associated with connected wires.
Claim 19
Dependent Claim
160 words
The method of claim 11, wherein the step of a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout further comprises the step of generating polygon data associated with a plurality of polygons that represent a set of IC devices to be represented by the IC layout, wherein each polygon of the plurality of polygons is represented by one or more wires, and the method further includes the step of e) performing a validity check of the polygon data by performing the steps of: i) selecting a first polygon and a second polygon from the plurality of polygons to be checked, ii) determining the canonical direction from the first polygon to the second polygon, and iii) based upon the canonical direction from the first polygon to the second polygon, determining whether a spacing between the first polygon and the second polygon satisfies a set of predetermined spacing criteria.
Claim 20
Dependent Claim
232 words
The method of claim 16, wherein the step of ii) determining the canonical direction from the first polygon to the second polygon includes the steps of 1) selecting a side of the first polygon from one or more previously unselected sides of the first polygon, 2) determining the canonical direction from the selected side of the first polygon to the second polygon, 3) determining, based upon the canonical direction from the selected side of the first polygon to the second polygon, whether the second polygon is on top of or is directly outside the selected side of the first polygon, 4) if the second polygon is on top of or is directly outside the selected side of the first polygon, then determining a canonical direction associated with the selected side of the first polygon, 5) if the second polygon is not on top of and is not directly outside the selected side of the first polygon, then repeating steps 1) through 4) until all of the one or more previously unselected sides of the first polygon have been selected, and 6) if the second polygon is not on top of or directly outside of any of the selected sides of the first polygon, then determining the canonical direction from the first polygon to the second polygon using the canonical direction from two or more of the selected sides to the second polygon.
Claim 21
Dependent Claim
88 words
The method of claim 16, further including the step of, if the spacing between the first polygon and the second polygon does not satisfy the set of predetermined spacing criteria, then performing the step of moving the second polygon with respect to the first polygon in a direction that is opposite from the direction of two sides of the first polygon that are closest to the second polygon, causing a separation to be generated between the first polygon and the second polygon to satisfy the predetermined spacing criteria.
Claim 22
Dependent Claim
125 words
The method of claim 18, wherein the method further includes the step of defining an exclusion zone around the first polygon that specifies a separation from the second polygon that satisfies the set of predetermined spacing criteria, and the step of moving the second polygon with respect to the first polygon in a direction that is opposite from the direction of the two sides of the first polygon that are closest to the second polygon further includes the step of moving the second polygon with respect to the first polygon in a direction that is opposite from the direction of the two sides of the first polygon that are closest to the second polygon, causing the second polygon to be located outside the exclusion zone.
Claim 23
Dependent Claim
49 words
The method of claim 16, further including the step of if the spacing between the first polygon and the second polygon does not satisfy the set of predetermined spacing criteria, then changing the size of the second polygon to cause the set of predetermined spacing criteria to be satisfied.
Claim 24
Dependent Claim
83 words
The method of claim 16, further including the steps of determining a size of the first polygon based upon a canonical direction from a first side of the first polygon to a second side of the first polygon, and if the size of the first polygon does not satisfy a set of size criteria, then moving the second side of the first polygon with respect to the first side of the first polygon to cause the set of size criteria to be satisfied.
Claim 25
Dependent Claim
147 words
The method of claim 16, wherein the step of i) selecting a first polygon and a second polygon from the plurality of polygons to be checked includes the step of selecting a first wire segment and a second wire segment from the plurality of wire segments to be checked, the step of ii) determining the canonical direction from the first polygon to the second polygon includes the step of determining the canonical direction from the first wire segment to the second wire segment, and the step of iii) determining whether a spacing between the first polygon and the second polygon satisfies a set of predetermined spacing criteria includes the step of based upon the canonical direction from the first wire segment to the second wire segment, determining whether the spacing between the first wire segment and the second wire segment satisfies the set of predetermined spacing criteria.
Claim 26
Dependent Claim
153 words
The method of claim 11, further comprising the step of e) based upon a first wire segment having a left face defined by first and second endpoints and a second wire segment having a left face defined by first and second endpoints, generating polygon output data by performing the step of if the first endpoint of the left face of the first wire segment is collinear with both the first and second endpoints of the left face of the second wire segment and the second endpoint of the left face of the first wire segment is collinear with the first endpoint of the left face of the second wire segment, then establishing a first left polygon face having a first endpoint defined by the first endpoint of the left face of the first wire segment and a second endpoint defined by the second endpoint of the left face of the second wire segment.
Claim 27
Dependent Claim
165 words
The method of claim 11, further comprising the step of e) based upon a first wire segment having a left face defined by first and second endpoints and a second wire segment having a left face defined by first and second endpoints, generating polygon output data by performing the step of if the second endpoint of the left face of the first wire segment is coincident with the first endpoint of the left face of the second wire segment, then establishing both a first left polygon face having a first endpoint defined by the first endpoint of the left face of the first wire segment and a second endpoint defined by the second endpoint of the left face of the first wire segment and a second left polygon face having a first endpoint defined by the second endpoint of the left face of the first wire segment and a second endpoint defined by the second endpoint of the left face of the second wire segment.
Claim 28
Independent Claim
108 words
A method for determining the canonical direction from a directed line segment to an arbitrary point in an integrated circuit layout, the method comprising the steps of: a) determining the location of the arbitrary point with respect to a point on the directed line segment; b) determining the location of the arbitrary point with respect to a first endpoint of the directed line segment; and c) determining the location of the arbitrary point with respect to a second endpoint of the directed line segment; and d) based upon the results of steps a) through c), assigning a canonical direction from the directed line segment to the arbitrary point.
Claim 29
Independent Claim
108 words
A method for determining the canonical direction from a directed line segment to an arbitrary point in an integrated circuit layout, the method comprising the steps of: a) determining the location of the arbitrary point with respect to a point on the directed line segment; b) determining the location of the arbitrary point with respect to a first endpoint of the directed line segment; and c) determining the location of the arbitrary point with respect to a second endpoint of the directed line segment; and d) based upon the results of steps a) through c), assigning a canonical direction from the directed line segment to the arbitrary point.
Claim 30
Independent Claim
137 words
A method for generating a data representation of an integrated circuit (IC) layout, the method comprising the steps of: a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires and the one or more wires is represented by one or more wire segments, wherein each wire segment is represented by four sides, and wherein none of the four sides has a preferred orientation with respect to a reference; b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data; and c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data.
Claim 31
Independent Claim
137 words
A method for generating a data representation of an integrated circuit (IC) layout, the method comprising the steps of: a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires and the one or more wires is represented by one or more wire segments, wherein each wire segment is represented by four sides, and wherein none of the four sides has a preferred orientation with respect to a reference; b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data; and c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data.
Claim 32
Dependent Claim
27 words
The method as recited in claim 26, wherein for each wire segment, none of the four sides must be parallel to any other of the four sides.
Claim 33
Dependent Claim
136 words
A computer-readable medium for determining the canonical direction from a directed line segment to an arbitrary point in an integrated circuit layout, the computer- readable medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: a) determining the location of the arbitrary point with respect to a point on the directed line segment; b) determining the location of the arbitrary point with respect to a first endpoint of the directed line segment; and c) determining the location of the arbitrary point with respect to a second endpoint of the directed line segment; and d) based upon the results of steps a) through c), assigning a canonical direction from the directed line segment to the arbitrary point.
Claim 34
Dependent Claim
136 words
A computer-readable medium for determining the canonical direction from a directed line segment to an arbitrary point in an integrated circuit layout, the computer- readable medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: a) determining the location of the arbitrary point with respect to a point on the directed line segment; b) determining the location of the arbitrary point with respect to a first endpoint of the directed line segment; and c) determining the location of the arbitrary point with respect to a second endpoint of the directed line segment; and d) based upon the results of steps a) through c), assigning a canonical direction from the directed line segment to the arbitrary point.
Claim 35
Dependent Claim
153 words
A computer system for determining the canonical direction from a directed line segment to an arbitrary point in an integrated circuit layout, the computer system comprising: one or more processors; and a memory communicatively coupled to the one or more processors, the memory including one or more sequences of one or more instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of a) determining the location of the arbitrary point with respect to a point on the directed line segment, b) determining the location of the arbitrary point with respect to a first endpoint of the directed line segment, c) determining the location of the arbitrary point with respect to a second endpoint of the directed line segment, and d) based upon the results of steps a) through c), assigning a canonical direction from the directed line segment to the arbitrary point.
Claim 36
Dependent Claim
153 words
A computer system for determining the canonical direction from a directed line segment to an arbitrary point in an integrated circuit layout, the computer system comprising: one or more processors; and a memory communicatively coupled to the one or more processors, the memory including one or more sequences of one or more instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of a) determining the location of the arbitrary point with respect to a point on the directed line segment, b) determining the location of the arbitrary point with respect to a first endpoint of the directed line segment, c) determining the location of the arbitrary point with respect to a second endpoint of the directed line segment, and d) based upon the results of steps a) through c), assigning a canonical direction from the directed line segment to the arbitrary point.
Claim 37
Dependent Claim
167 words
A computer-readable medium for generating a data representation of an integrated circuit (IC) layout, the computer readable medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wire more wires and the one or more wires is represented by one or more wire segments, wherein each wire segment is represented by four sides, and wherein none of the four sides has a preferred orientation with respect to a reference; b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data; and c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data.
Claim 38
Dependent Claim
167 words
A computer-readable medium for generating a data representation of an integrated circuit (IC) layout, the computer readable medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of: a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wire more wires and the one or more wires is represented by one or more wire segments, wherein each wire segment is represented by four sides, and wherein none of the four sides has a preferred orientation with respect to a reference; b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data; and c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data.
Claim 39
Dependent Claim
28 words
The computer-readable medium as recited in claim 30, wherein for each wire segment, none of the four sides must be parallel to any other of the four sides.
Claim 40
Dependent Claim
181 words
A computer system for generating a data representation of an integrated circuit (IC) layout comprising: one or more processors; and a memory communicatively coupled to the one or more processors, wherein the memory include one or more sequences of one or more instructions which, when executed by the one or more processors cause the one or more processors to perform the steps of a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires and the one or more wires is represented by one or more wire segments, wherein each wire segment is represented by four sides, and wherein none of the four sides has a preferred orientation with respect to a reference; b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data; and c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data.
Claim 41
Dependent Claim
181 words
A computer system for generating a data representation of an integrated circuit (IC) layout comprising: one or more processors; and a memory communicatively coupled to the one or more processors, wherein the memory include one or more sequences of one or more instructions which, when executed by the one or more processors cause the one or more processors to perform the steps of a) generating polygon data associated with a polygon that represents a set of IC devices to be represented by the IC layout, wherein the polygon is represented by one or more wires and the one or more wires is represented by one or more wire segments, wherein each wire segment is represented by four sides, and wherein none of the four sides has a preferred orientation with respect to a reference; b) generating wire data that both represents the one or more wires and contains at least one reference to the polygon data; and c) generating wire segment data that both represents the one or more wire segments and contains at least one reference to the wire data.
Claim 42
Dependent Claim
28 words
The computer system as recited in claim 32, wherein for each wire segment, none of the four sides must be parallel to any other of the four sides.
References Cited (Backward Citations)
US5097422A
Cited
DE3935418A1
Cited
US5113451A
Cited
US5416722A
Cited
US5689433A
Cited
US5581475A
Cited
US5613102A
Cited
US5515293A
Cited
US5612893A
Cited
US5625568A
Cited
US5640497A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-03 | 2004-04-03 | 2004-10-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-03 | 2008-04-03 | 2008-10-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-03 | 2012-04-03 | 2012-10-03 | $7700.00 | Window Closed / Lapsed |