# US 6,189,132 B1 · Design rule correction system and method

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

- Number: US 6,189,132 B1
- Document ID: US6189132B1
- Status: Granted
- Kind: B1
- Application number: 09/057,961
- Filed: 1998-04-09
- Granted: 2001-02-13
- Earliest claimed: 1998-04-09
- Assignees: International Business Machines Corporation
- Inventors: Fook-Luen Heng; Zhan Chen; Gustavo E. Tellez; John Cohn; Rani Narayan
- Web page: https://patentgrep.com/patent/US6189132B1

## 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: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A method of modifying a layout of a plurality of objects in accordance with a plurality of predetermined criteria is presented. An objective function is defined for measuring a location perturbation and a separation perturbation of the objects in the layout. A linear system is defined using linear constraints in terms of design rules and the objective function to describe separations between layout objects. The linear system is solved to simultaneously remove violations of the design rules, and shapes and positions of objects in the layout are modified in accordance with the solution of the linear system such that a total perturbation of the objects in the layout is reduced. A system for implementing the present invention is also presented.

## Claims

### Claim 1

A method of modifying a layout of a plurality of objects in accordance with a plurality of predetermined criteria comprising the steps of:
defining objective functions for measuring a location perturbation and a separation perturbation of the objects in the layout;
defining a linear system using linear constraints in terms of design rules and the objective functions to describe separations between layout objects and locations of the layout objects;
solving the linear system to simultaneously remove violations of the design rules; and
modifying shapes and positions of objects in the layout in accordance with the solution of the linear system such that a total perturbation of the objects in the layout, including a combination of separation perturbation and location perturbation, is reduced.

### Claim 2 (depends on 1)

The method as recited in claim 1, further comprising the step of weighting the location perturbation and the separation perturbation in accordance with predetermined criteria.

### Claim 3 (depends on 1)

The method as recited in claim 1, wherein the step of defining the objective function includes defining the objective function for the location perturbation equal to |Xi−Xiold| where Xi is a final location of object i and Xiold is an initial location of object i.

### Claim 4 (depends on 1)

The method as recited in claim 1, wherein the step of defining the objective function includes defining the objective function for the separation perturbation equal to |Xj−Xi−(Xjold−Xiold)| where Xi is a final location of object i, Xiold in an initial location of object i, Xj is a final location of object j and Xjold is an initial location of object j.

### Claim 5 (depends on 1)

The method as recited in claim 1, wherein the step of defining the system of linear constraints includes the step of defining linear constraints of the form Xj−Xi≧dij where Xj is a final location of object j, Xi is a final location of object i and dij is a relative distance between i and j as defined by design rules.

### Claim 6 (depends on 1)

The method as recited in claim 1, wherein the objective function is a non-linear function and further comprising the step of transforming the non-linear function to a linear function by modifying the linear constraints.

### Claim 7 (depends on 1)

The method as recited in claim 1, further comprising the steps of:
modifying the linear constraints in accordance with user defined design requirements; and
introducing the design requirements into the linear system to be used to modify the shapes and positions of the objects.

### Claim 8 (depends on 1)

The method as recited in claim 1, wherein the layout includes violations and further comprising the step of determining a status of the violation wherein the status is keep, remove or ignore the violation.

### Claim 9 (depends on 8)

The method as recited in claim 8, further comprising the step of modifying a linear constraint in the linear system, when the status is keep the violation.

### Claim 10 (depends on 9)

The method as recited in claim 9, wherein the linear constraint is of the form Xj−Xi≧dij where Xj is a final location of object j, Xi is a final location of object i and dij is a relative distance between i and j as defined by design rules and further comprising the step of modifying the linear constraint to Xj−Xi≧Xjold−Xiold where Xiold in an initial location of object i, and Xjold is an initial location of object j.

### Claim 11 (depends on 8)

The method as recited in claim 8, further comprising the step of deleting a linear constraint that is violated, when the status is ignore the violation.

### Claim 12 (depends on 8)

The method as recited in claim 8, further comprising the step of removing the violation by solving the linear system, when the status is remove the violation.

### Claim 13 (depends on 1)

The method as recited in claim 1, further comprising the step of relaxing constraints in accordance with a penalty term to improve the layout, when the layout includes violations where no solution exists.

### Claim 14

A method for modifying a layout of a plurality of objects to ensure compliance with a plurality of predetermined rules and design requirements comprising the steps of:
determining a weighted perturbation cost by providing a weighted objective function, the weighted objective function including a weighted separation perturbation objective function and a weighted location perturbation objective function;
creating a system of linear constraints in accordance with the design rules and the weighted perturbation cost;
modifying the system of linear constraints to reflect the design requirements;
modifying the system of linear constraints to ignore or keep predetermined violations of the design rules and the design requirements; and
modifying the layout to remove violations of design rules and design requirements such that a total perturbation based on a combination of separation perturbation and location perturbation of the objects in the layout is reduced.

### Claim 15 (depends on 14)

The method as recited in claim 14, wherein the objective function is a non-linear function and further comprising the step of transforming the non-linear function to a linear function by modifying the linear constrains.

### Claim 16 (depends on 14)

The method as recited in claim 14, further comprising the step of defining the objective function for a location perturbation equal to |Xi−Xiold| where Xi is a final location of object i and Xiold is an initial location of object i.

### Claim 17 (depends on 14)

The method as recited in claim 14, further comprising the step defining the objective function for a separation perturbation equal to |Xj−Xi−(Xjold−Xiold)| where Xi is a final location of object i, Xiold is an initial location of object i, Xj is a final location of object j and Xjold is an initial location of object j.

### Claim 18 (depends on 14)

The method as recited in claim 14, wherein the step of creating the system of linear constraints includes the step of defining linear constraints of the form Xj−Xi≧dij where Xj is a final location of object j, Xi is a final location of object i and dij a relative distance between i and j as defined by design rules.

### Claim 19 (depends on 14)

The method as recited in claim 14, wherein the step of modifying the system of linear constraints to ignore or keep predetermined violations includes the step of keeping the linear constraints by modifying the linear constraints to remove the violation.

### Claim 20 (depends on 19)

The method as recited in claim 19, wherein the linear constraints are of the form Xj−Xi≧dij where Xj is a final location of object j, Xi is a final location of object i and dij is a relative distance between i and j as defined by design rules and further comprising the step of modifying the linear constraints to Xj−Xi≧Xjold−Xiold where Xiold in an initial location of object i, and Xjold is an initial location of object j.

### Claim 21 (depends on 14)

The method as recited in claim 14, wherein the step of modifying the system of linear constraints to ignore or keep predetermined violations includes the step of ignoring the violation by deleting the linear constraint that is violated.

### Claim 22 (depends on 14)

The method as recited in claim 14, further comprising the step of relaxing constraints in accordance with a penalty term to improve the layout, when the layout includes violations where no solution exists.

### Claim 23

A system for modifying a layout of a plurality of objects in accordance with a plurality of predetermined criteria comprising:
objective functions for measuring a location perturbation and a separation perturbation of the objects in the layout;
a system of linear constraints in accordance with design rules and the objective functions for describing separations between layout objects and locations of the layout objects;
means for solving the linear system to simultaneously remove violations of the design rules; and
means for modifying shapes and positions of objects in the layout in accordance with the solution of the linear system such that a total perturbation of the objects in the layout, including a combination of separation perturbation and location perturbation, is reduced.

### Claim 24 (depends on 23)

The system as recited in claim 23, further comprising a weighting factor for weighting the location perturbation and the separation perturbation in accordance with predetermined criteria.

### Claim 25 (depends on 23)

The system as recited in claim 23, wherein the objective function for the location perturbation is equal to |Xi−Xiold| where Xi is a final location of object i and Xiold is an initial location of object i.

### Claim 26 (depends on 23)

The system as recited in claim 23, wherein the objective function for the separation perturbation is equal to |Xj−Xi−(Xjold−Xiold)| where Xi is a final location of object i, Xiold in an initial location of object i, Xj is a final location of object j and Xjold is an initial location of object j.

### Claim 27 (depends on 23)

The system as recited in claim 23, wherein the linear constraints include Xj−Xi≧dij where Xj is a final location of object j, Xi is a final location of object i and dij is a relative distance between i and j as defined by design rules.

### Claim 28 (depends on 23)

The system as recited in claim 23, wherein the objective function is a non-linear function transformed to a linear function by modifying the linear constraints.

### Claim 29 (depends on 23)

The system as recited in claim 23, wherein the linear constraints include user defined design requirements which are introduced into the linear system to modify the shapes and positions of the objects.

### Claim 30 (depends on 23)

The system as recited in claim 23, wherein the layout includes control means for addressing predetermined violations according to predefined criteria.

### Claim 31 (depends on 23)

The system as recited in claim 23, wherein the means for modifying includes a processor.

### Claim 32 (depends on 23)

The system as recited in claim 23, further comprising means for relaxing constraints in accordance with a penalty term for objects in the layout where no solution exists.
