Layout Pattern Similarity Determination Based On Binary Turning Function Signatures

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:

• receiving layout data of layout patterns;
• determining one or more binary turning function signatures for each of the layout patterns, the one or more binary turning function signatures comprising binary turning function signatures for polygons in the each of the layout patterns, determination of the binary turning function signature of a polygon comprising:
• determining a binary turning function sequence number for the polygon based on assigning a binary digit to each vertex of the polygon or each vertex of a predominant-direction-reduced version of the polygon, the assigning being based on whether edge tracing turns right or left, and
• deriving a minimum binary number or a maximum binary number among variants of the binary turning function sequence number generated by circular bit shifting and bit sequence reversing;
• determining similar layout patterns in the layout patterns based on the one or more binary turning function signatures;
• and
• storing information of the similar layout patterns in a computer-accessible medium.

A system, comprising:

• one or more processors, the one or more processors programmed to perform a method, the method comprising:
• receiving layout data of layout patterns;
• determining one or more binary turning function signatures for each of the layout patterns, the one or more binary turning function signatures comprising binary turning function signatures for polygons in the each of the layout patterns, determination of the binary turning function signature of a polygon comprising:
• determining a binary turning function sequence number for the polygon based on assigning a binary digit to each vertex of the polygon or each vertex of a predominant-direction-reduced version of the polygon, the assigning being based on whether edge tracing turns right or left, and
• deriving a minimum binary number or a maximum binary number among variants of the binary turning function sequence number generated by circular bit shifting and bit sequence reversing;
• determining similar layout patterns in the layout patterns based on the one or more binary turning function signatures;
• and
• storing information of the similar layout patterns in a computer-accessible medium.