# US 2013/0298094 A1 · Methods and Apparatus for Layout Verification

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2013/0298094 A1
- Document ID: US20130298094A1
- Status: Published application
- Kind: A1
- Application number: 13/464,417
- Filed: 2012-05-04
- Published: 2013-11-07
- Earliest claimed: 2012-05-04
- Assignees: Taiwan Semiconductor Manufacturing Company, Ltd.
- Inventors: Shin-Huang Chen; Yin-Chuan Chen
- Web page: https://patentgrep.com/patent/US20130298094A1

## CPC

- G06F 30/398: Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36)
- G06F 2119/18: Manufacturability analysis or optimisation for manufacturability
- Y02P 90/02: Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y02P: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN THE PRODUCTION OR PROCESSING OF GOODS

## Abstract

Methods and apparatus of performing layout-versus-layout (LVL) comparison are disclosed. A layout may be in various formats such as GDSII or OASIS, for different circuits, and represented by a basic layout element, a hierarchical cell or a plurality of independent cells in various layers. A basic layout element, a hierarchical cell, and a layout with a plurality of independent cells may have a signature generated according to the embodiment methods. The signature of a basic layout element may be generated based on values of a center and a circumference, and a hashed trace value generated by a hash function of a trace of the basic layout element. The signature of a hierarchical cell can be generated recursively. A signature of a first layout may be compared to a signature of a second layout to determine whether the first layout matches the second layout.

## Claims

### Claim 1

A method performed by a computer for comparing a first layout with a second layout, comprising:
receiving, by an input device of a computer, a first input corresponding to a first layout of an integrated circuit (IC), wherein the first layout comprises a first basic layout element;
receiving, by the input device of the computer, a second input corresponding to a second layout of the IC, wherein the second layout comprises a second basic layout element;
forming, by a processor of the computer, a first trace of the first basic layout element, and a second trace of the second basic layout element, wherein the first trace is a first description that uniquely identifies the first basic layout element and its location, and the second trace is a second description that uniquely identifies the second basic layout element and its location;
generating, by the processor of the computer, a first signature from the first input, wherein the first signature comprises a first trace signature representing the first trace for the first basic layout element;
generating, by the processor of the computer, a second signature from the second input, wherein the second signature comprises a second trace signature representing the second trace for the second basic layout element;
comparing, by the processor of the computer, the first signature and the second signature to determine whether the first layout is same as the second layout; and
producing, by an output device of the computer, an output.

### Claim 2 (depends on 1)

The method of claim 1, wherein the first layout and the second layout are of a format selected from a group consisting essentially of Graphic Data System II (GDSII), Open Artwork System Interchange Standard (OASIS), Open Access, Milkyway, and Electronic Design Data Model (EDDM).

### Claim 3 (depends on 1)

The method of claim 1, wherein the first signature is generated by a different computer aided design (CAD) tool from a tool used to create the first layout.

### Claim 4 (depends on 1)

The method of claim 1, wherein generating the first signature comprises:
forming a hashed trace value of the first trace of the first basic layout element; and
forming the first trace signature of the first basic layout element based on the hashed trace value.

### Claim 5 (depends on 1)

The method of claim 1, wherein the first trace signature for the first basic layout element is generated from a first orientation, and the second trace signature for the second basic layout element is generated from a second orientation.

### Claim 6 (depends on 1)

The method of claim 1, wherein the first basic layout element is a polygon and the first trace of the first basic layout element is formed by connecting an x coordinate and a y coordinate of a plurality of vertexes of the polygon along edges of the polygon to form a string.

### Claim 7 (depends on 4)

The method of claim 4, wherein the first basic layout element is a circle and the first trace of the first basic layout element is formed by connecting an x coordinate and a y coordinate of a center of the circle.

### Claim 8 (depends on 4)

The method of claim 4, wherein the hashed trace value of the first trace is generated by a hash function applied to the first trace.

### Claim 9 (depends on 8)

The method of claim 8, wherein the hash function is a cyclic redundancy check (CRC) code.

### Claim 10 (depends on 9)

The method of claim 9, wherein the CRC code is a CRC32 code.

### Claim 11 (depends on 7)

The method of claim 7, wherein the first trace signature of the first basic layout element is formed by a formula selected from a group consisting essentially of:
a circumference of the first basic layout element*x coordinate of the center of the first basic layout element*y coordinate of the center of the first basic layout element*the hashed trace value; the circumferencê2 of the first basic layout element*x coordinate of the center of the first basic layout element*y coordinate of the center of the first basic layout element*the hashed trace value; or the hashed trace value.

### Claim 12 (depends on 7)

The method of claim 7, wherein the first trace signature of the first basic layout element is formed as a plurality of numbers each of which is generated by a formula selected from a group consisting essentially of: a circumference of the first basic layout element*x coordinate of the center of the first basic layout element*y coordinate of the center of the first basic layout element*the hashed trace value; the circumferencê2 of the first basic layout element*x coordinate of the center of the first basic layout element*y coordinate of the center of the first basic layout element*the hashed trace value; or the hashed trace value.

### Claim 13 (depends on 1)

The method of claim 1, further comprising:
receiving the first input corresponding to the first layout, wherein the first layout comprises a hierarchical cell;
generating the first signature for the hierarchical cell comprising:
generating a signature of a component cell of the hierarchical cell, which is a basic layout element, by forming a trace of the component cell, forming a hashed trace value of the trace of the component cell, and forming a component trace signature of the component cell based on the trace of the component cell;
generating a signature of a hierarchical component cell recursively; and
adding all signatures of all component cells of the hierarchical cell to be the first signature for the hierarchical cell.

### Claim 14 (depends on 1)

The method of claim 1, wherein the first layout comprises a plurality of independent cells, and generating the first signature comprises:
generating a signature for each independent cell of the first layout; and
generating the first signature based on the signature for each independent cell.

### Claim 15 (depends on 14)

The method of claim 14, wherein the first signature is generated by adding the signature of each independent cell.

### Claim 16 (depends on 14)

The method of claim 14, wherein the first signature is generated by forming an array of signatures for all independent cells of the first layout.

### Claim 17

A system performing a layout-versus-layout (LVL) comparison, comprising:
an input device to receive a first layout and a second layout, wherein the first layout comprises a first basic layout element, and the second layout comprises a second basic layout element;
a processor that is to:
form a first trace of the first basic layout element, and a second trace of the second basic layout element, wherein the first trace is a first description that uniquely identifies the first basic layout element and its location, and the second trace is a second description that uniquely identifies the second basic layout element and its location;
generate a first signature for the first layout, a second signature for the second layout, wherein the first signature comprises a first trace signature representing the first trace, and the second signature comprises a second trace signature representing the second trace;
compare the first signature and the second signature to determine whether the first layout is same as the second layout, and
produce an output, wherein the first signature and the second signature are a number or a plurality of numbers.

### Claim 18 (depends on 17)

The system of claim 17, wherein the first basic layout element is a circle, and the processor generates the first trace signature based on values of a center and a circumference of the circle, and a hashed trace value generated by a hash function of a trace of the circle.

### Claim 19 (depends on 17)

The system of claim 17, wherein the first layout comprises a hierarchical cell, and the processor generates the first signature by adding each signature of each component cell which is a basic layout element, whose value is related to values of a hashed trace value generated by a hash function of a trace of the component cell; and each signature of a hierarchical component cell generated recursively.

### Claim 20 (depends on 17)

The system of claim 17, wherein the first layout comprises a plurality of independent cells, and the processor generates the first signature related to a signature for each independent cell of the first layout.
