Canonical forms of layout patterns
View Patent ↗Aspects of the disclosed technology relate to techniques for determining canonical forms of layout patterns. Coordinates of vertices of geometric elements in a window of a layout design are first transformed into new coordinates of the vertices, wherein the coordinates of vertices do not comprise clipped coordinates and the transforming comprises: performing a translation on the coordinates of vertices based on differences between maximum and minimum X/Y coordinate values of the vertices. Based on sums of X/Y coordinate values of the new coordinates of the vertices, a canonical form of the geometric elements is determined. The canonical form coordinates of the vertices may then be determined and sorted. The sorted canonical form coordinates may be employed for pattern matching.
1. A method, executed by at least one processor of a computer, comprising:
transforming coordinates of vertices of geometric elements in a window of a layout design into new coordinates of the vertices, wherein the coordinates of vertices do not comprise clipped coordinates and the transforming comprises:
performing a translation on the coordinates of vertices based on differences between maximum and minimum X coordinate values of the vertices and between maximum and minimum Y coordinate values of the vertices (the clipped coordinate values not considered); and
determining a canonical form of the geometric elements based on a sum of X coordinate values of the new coordinates of the vertices and a sum of Y coordinate values of the new coordinates of the vertices.
2. The method recited in claim 1 , wherein the performing comprises:
determining an origin of a new coordinate system based on differences between maximum and minimum X coordinate values of the vertices and between maximum and minimum Y coordinate values of the vertices.
3. The method recited in claim 1 , wherein the transforming further comprises:
scaling down the translated coordinates by a factor if the factor is greater than 1, wherein the factor is a greatest common factor of the translated coordinates of the vertices.
4. The method recited in claim 1 , further comprising:
determining canonical form coordinates of the vertices based on a relationship between the canonical form and an original form of the geometrical elements; and
sorting the canonical form coordinates according to a predetermined rule.
5. The method recited in claim 4 , further comprising:
performing pattern matching using the sorted canonical form coordinates.
6. The method recited in claim 1 , wherein the canonical form of the geometric elements is obtained by performing an operation on the geometric elements, wherein the operation is one of symmetry operations comprising: identity operation, 90-degree-rotation operation, 180-degree-rotation operation, 270-degree-rotation operation, mirror-reflection operation, 90-degree-rotation mirror-reflection operation, 180-degree-rotation mirror-reflection operation, and 270-degree-rotation mirror-reflection operation.
7. One or more non-transitory computer-readable media storing computer-executable instructions for causing one or more processors to perform a method, the method comprising:
transforming coordinates of vertices of geometric elements in a window of a layout design into new coordinates of the vertices, wherein the coordinates of vertices do not comprise clipped coordinates and the transforming comprises:
performing a translation on the coordinates of vertices based on differences between maximum and minimum X coordinate values of the vertices and between maximum and minimum Y coordinate values of the vertices (the clipped coordinate values not considered); and
determining a canonical form of the geometric elements based on a sum of X coordinate values of the new coordinates of the vertices and a sum of Y coordinate values of the new coordinates of the vertices.
8. The one or more non-transitory computer-readable media recited in claim 7 , wherein the performing comprises:
determining an origin of a new coordinate system based on differences between maximum and minimum X coordinate values of the vertices and between maximum and minimum Y coordinate values of the vertices.
9. The one or more non-transitory computer-readable media recited in claim 7 , wherein the transforming further comprises:
scaling down the translated coordinates by a factor if the factor is greater than 1, wherein the factor is a greatest common factor of the translated coordinates of the vertices.
10. The one or more non-transitory computer-readable media recited in claim 7 , wherein the method further comprises:
determining canonical form coordinates of the vertices based on a relationship between the canonical form and an original form of the geometrical elements; and
sorting the canonical form coordinates according to a predetermined rule.
11. The one or more non-transitory computer-readable media recited in claim 10 , wherein the method further comprises:
performing pattern matching using the sorted canonical form coordinates.
12. The one or more non-transitory computer-readable media recited in claim 7 , wherein the canonical form of the geometric elements is obtained by performing an operation on the geometric elements, wherein the operation is one of symmetry operations comprising: identity operation, 90-degree-rotation operation, 180-degree-rotation operation, 270-degree-rotation operation, mirror-reflection operation, 90-degree-rotation mirror-reflection operation, 180-degree-rotation mirror-reflection operation, and 270-degree-rotation mirror-reflection operation.
13. A system, comprising:
a transformation unit configured to transform coordinates of vertices of geometric elements in a window of a layout design into new coordinates of the vertices, wherein the coordinates of vertices do not comprise clipped coordinates and the transforming comprises: performing a translation on the coordinates of vertices based on differences between maximum and minimum X coordinate values of the vertices and between maximum and minimum Y coordinate values of the vertices (the clipped coordinate values not considered); and
a canonical form determination unit configured to determine a canonical form of the geometric elements based on a sum of X coordinate values of the new coordinates of the vertices and a sum of Y coordinate values of the new coordinates of the vertices.
14. The system recited in claim 13 , further comprises:
a canonical form coordinates determination and sorting unit configured to determine canonical form coordinates of the vertices based on a relationship between the canonical form and an original form of the geometrical elements and to sort the canonical form coordinates according to a predetermined rule.
15. The system recited in claim 14 , further comprising:
a pattern matching unit configured to perform pattern matching using the sorted canonical form coordinates.
16. The system recited in claim 13 , wherein the performing comprises:
determining an origin of a new coordinate system based on differences between maximum and minimum X coordinate values of the vertices and between maximum and minimum Y coordinate values of the vertices.
17. The system recited in claim 13 , wherein the transforming further comprises:
scaling down the translated coordinates by a factor if the factor is greater than 1, wherein the factor is a greatest common factor of the translated coordinates of the vertices.
18. The system recited in claim 13 , wherein the canonical form of the geometric elements is obtained by performing an operation on the geometric elements, wherein the operation is one of symmetry operations comprising: identity operation, 90-degree-rotation operation, 180-degree-rotation operation, 270-degree-rotation operation, mirror-reflection operation, 90-degree-rotation mirror-reflection operation, 180-degree-rotation mirror-reflection operation, and 270-degree-rotation mirror-reflection operation.