Short locator method

• US 5,299,139 A
• Filed: 06/21/1991
• Issued: 03/29/1994
• Est. Priority Date: 06/21/1991
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Baisuck, Allen, Hoover, William W. III
• Primary Examiner(s): Trans, Vincent N.
• Application Number:
  US07/718,969
• Time in Patent Office: 1,012 Days
• Field of Search: 364/488, 364/489, 364/490, 364/491
• US Class Current: 716/112
• CPC Class Codes: 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

Abstract

An improved circuit layout-verifying system and method operates on a plurality of polygons that are representative of an electrical node to test the proper or improper connection of each polygon to another contiguous polygon and designates for display those polygons that represent improper connections between known or identified reference points on the node. Traversals along a sequence of contiguous polygons between known reference points on the same electrical node are designated as proper connections or successes, and traversals along a sequence of contiguous polygon between reference points associated with different electrical nodes are designated as improper connections or failures at least along a portion of the sequence. Data from all traversals of all polygons from all known reference points is then analyzed to remove unambiguous sequences of polygons for the improperly connected electrical nodes. High resolution analysis is performed on large, single electrical nodes by selectively breaking down the node into subpolygons that can be analyzed in the previous manner.

Claims

1. A computer implemented method for analyzing an electrical node of a circuit layout to locate erroneous connections thereon, the method comprising the steps of:

forming a representation of the area of an electrical node including the erroneous connections therein for analysis;

segregating the area of the electrical node into a plurality of individual polygons oriented in contiguous array within said area wherein said step of segregating includes the substeps of;

identifying all obtuse angles along the perimeter of the area of the electrical node including the erroneous connections therein; and

forming alternate substantially horizontal and vertical divisions of the area of the electrical node at the locations of the obtuse angles in selected sequence along the perimeter of said area to form thereby a plurality of individual polygons in contiguous array; and

analyzing each individual polygon for proper connection to a contiguous polygon commencing from an initial starting point on a polygon within the area of the node.

2. The method according to claim 1, wherein for any individual polygon, obtuse angles are identified;

and

substantially horizontal and vertical divisions are formed in alternate array along the perimeter thereof at the locations of the identified obtuse angles to form thereby a plurality of individual subpolygons in contiguous array with each other and with other individual polygons within the area of the electrical node.

3. The method according to claim 1, wherein the step of forming a representation comprises the steps of:

retrieving connectivity information for said circuit layer, including information pertaining to the number of layers in said circuit layout and interconnections between said layers; and

generating an internal data structure for holding said connectivity information.

4. The method according to claim 1, wherein the step of analyzing each individual polygon includes the step of designating a plurality of said polygons as reference points which are associated with at least two different electrical nodes.

5. The method according to claim 4, further comprising the step of:

removing from a set of polygons to be analyzed any polygon which is not a reference point and which initially is connected to two or fewer other polygons.

6. A computer implemented method for analyzing an electrical node of a circuit layout to locate erroneous connections therein, the method comprising the steps of:

forming a representation of the area of an electrical node including the erroneous connections therein for analysis;

identifying a plurality of reference points in the area of the electrical node which are associated with at least two different electrical nodes;

forming a plurality of contiguous polygons along and within the area of the electrical node at least between said reference points;

traversing a sequence of polygons from one reference point toward another reference point on the electrical node to determine electrical connection of each polygon to an adjacent polygon previously traversed in the sequence, and storing the results of the determination for each polygon along the course of another reference point;

designating success of connections in the stored results under conditions of the sequence proceeding between two reference points associated with the same electrical node, and designating failure of connections in the stored results under conditions of the sequence proceeding between two reference points associated with different electrical nodes; and

displaying a representation of at least a portion of the sequence of polygons for which the stored results designate failure between two reference points.

7. The method according to claim 6 wherein the step of traversing includes traversing forward in the sequence of polygons newly encountered and designating any polygon associated with a junction to another electrical node, and traversing backward in the sequence of polygons upon condition of encountering a reference point associated with another electrical node, the backward traverse continuing from such another reference point at least to a polygon associated with a junction to designate the polygons in the backward traverse as failures of connections;

traversing forward from the junction polygon along another sequence of polygons toward another reference point with designations of success of connections in the stored results for each polygon between the junction polygon and a reference point associated with the same electrical node; and

displaying at least a representation of the junction polygon.