The edge-based design rule model revisited.
A model for integrated circuit design rules based on rectangle edge constraints has been proposed by Jeppson, Christensson, and Hedenstierna. This model appears to be the most rigorous proposed to date for the description of such edge-based design rules. However, in certain rare circumstances their model is unable to express the correct design rule when the constrained edges are not adjacent in the layout. We introduce a new notation, called an edge path, which allows us to extend their model to allow for constraints between edges separated by an arbitrary number of intervening edges. Using this notation we enumerate all edge paths that are required to correctly model the original design rule macros of the JCH model, and prove that these macros are sufficient to model the most common  rules. We also show how this notation alows us to directly specify many kinds of conditional design rules that required ad hoc specification under the JCH model.
Introduction
The technology used to manufacture integrated circuits [8] imposes certain limits on the sizes and relative positioning
of features on the wafer. The resolution of optical lithography equipment, the amount of undercutting during a
wet-etch processing step, the control over lateral diffusion and junction depth in dopant implant steps-all will set
physical limits on how small device features can be, and how closely they can be separated, before the electrical
behavior of the circuit changes. In addition, the interaction of successive processing steps-step-coverage problems
in non-planar processes, or the ability to fill stacked vias, for example-also set limits on the manufacturability of the
integrated circuits.
Process and device engineers carefully characterize a semiconductor manufacturing process to understand these
interactions, seeing them as complex statistical distributions of sizes and feature proximities and their effect on circuit
reliability. Given only this raw data it would be very difficult and time-consuming to assess the overall reliability of a
complete integrated circuit, or for a layout designer to draw a layout with a known level of reliability. Therefore, this
statistical data is commonly codified into a set of much simpler design rules which can be given to the mask designers
to guide them in producing a manufacturable layout [7].
Integrated circuit design rules abstract away the details of the process technology, and instead impose rules on the
sizes and shapes of mask features and the separations and orientations of mask features in relation to one another. For
example, a poly-separation rule might specify that the edges of unconnected rectangles on the polysilicon mask layer
must be at least microns apart. One can also think of the design rules as imposing a set of constraints on the mask
data-if all of the features in a given mask set conform to the design rules, the layout is considered to be design rule
correct, and the designer can have some confidence that it can be manufactured with high yield.
1.
Proof of design rule correctness is required before manufacturing can begin, so an important class of CAD tools,
called design rule checkers, have been developed to check the mask data against the design rules in order to supply
such a proof. In addition, layout generation tools, such as placement and routing tools, layout compactors, and leaf-
less synthesis tools [3], require detailed information about the design rules so that correct layout can be produced.
Therefore, in addition to making sure that the design rules are simple enough for mask designers to follow easily, it is
important that they be specified in a formal and un-ambiguous manner so that they can be codified for use by algorithm
designers.
Two competing methods have evolved for the formal expression and modeling of VLSI design rules. The first
employs a sequence of operations acting on the layout rectangles, such as the expansion and shrinkage of particular
rectangle edges, and the union/intersection/inversion of overlapping rectangles. Design rules are defined by the presence
of an empty or non-empty intersection between rectangles of a specified mask layer, or combination of mask
layers, suitably expanded or shrunk by a given amount. Since these mask operations are global in nature, acting on all
rectangles of a particular mask layer in the layout, we refer to these as mask-based design rule models. Mask-based
modeling forms the basis of the commercial design rule checking software package Dracula [1], and has been formalized
by Modarres and Lomax [5] through the use of set theoretic methods. We refer to the model of Modarres and
Lomax as the ML model for design rules.
The second method developed for the modeling of design rules treats the rules as constraints on the distance
between individual edges of rectangles in the layout. There can potentially be a design rule constraint between any
pair of non-perpendicular edges in the layout. The presence of a constraint, and if one exists the distance at which the
edges are constrained to lie, depends on the layers making up the rectangles involved. Since this notion of design
rules is local in extent, with its definition based on individual rectangle edges, we refer to these approaches as edge-based
models. This second method has been formalized by K. Jeppson, S. Christensson, and N. Hedenstierna [2],
using a modeling approach which we refer to as the JCH model for design rules.
The two applications for design rules mentioned above, design rule checking and layout generation, expose two
facets to the problem of design rule modeling. Mask-based methods seem dominant in the application of design rule
checking, while edge-based models dominate in layout generation systems. In the former, the layout is static and
unchanging, and we only seek to know if any design rule violations exist, and if so, where they are located. The global
nature of the mask-based model suits this application well, and appears to lead the most naturally to elegant and
efficient implementations based on well studied methods on computational geometry [6]. However, in the latter application
one often requires the capability of making local queries in the layout as a new rectangle is added, to ensure
that the rectangle is legally placed with respect to its neighbors. In addition, many layout generation applications,
such as compaction, attempt to optimize the layout by finding optimal positions for each of the layout rectangles, subject
to the design rule constraints. Because of its ability to represent the design rules as constraints between individual
edges in the design, the edge-based model appears ideally suited to this application.
In the course of our research into optimization based approaches to VLSI layout generation, we have studied the
details of the JCH model, and have encountered several situations in which that model appears incomplete. In this
paper we revisit the JCH model and provide some extensions which we feel contribute toward its universal application

The basic notion of the edge-based design rule model, i.e. the definition of a design rule as a constraint on the relative
positions of two non-perpendicular rectangle edges, is fairly simple. The complexity arises in attempting to
characterize the specific rule, if any, which will apply to a given pair of edges. In the JCH model, each rectangle edge
is assigned a type based on the layers which are present on either side. Given all of the different edge types, they
exhaustively enumerate all pairs of edges which can appear adjacent to one another, and show how each possibility
maps into a particular design rule. The strength of the JCH model is its ability to support this exhaustive analysis,
which provides a proof of its correctness and completeness. This type of analysis has never been attempted for mask-
based models, and it would probably be very difficult given the fact that all design rules are defined as global operations
on the entire layout.
In our study of the JCH model we have observed a shortcoming in the model as it was presented in [2]. The root of
the problem is that, in their exhaustive enumeration of all possible design rules, the authors only examined the case of
rules between adjacent edges in the layout. They show one example in which two edges, which should be constrained,
are separated by an intermediate edge. Because of this intervening edge their model is unable to detect the proper
constraint. Under several different interpretations of their definition for a design rule, they solve this problem by placing
constraints on the values of the design rule parameters. When these constraints are satisfied the design rules that
are missed will always be covered by other design rules, so there is no danger of missing a violation. However, we
show one example in which their constraints are not strong enough, and we feel that constraining the model in this
way is an inelegant solution to the problem. Instead, we feel it should be possible to correctly express these design
rules so that they can always be detected.
In this paper we extend the JCH model to cover, without ambiguity, situations under which design rule constraints
can exist between edges with an arbitrary number of intermediate edges. To support the specification of design rules
under this model we develop a simple grammar, called the edge-path grammar, which can be used to describe a more
complete set of design rules. Using this grammar we describe the design rule macros of the JCH model and extend
these macros to cover design rules which were un-representable in the notation used in [2].
2. Previous Work-The JCH Model for Design Rules
In the VLSI layout environment as defined by Mead and Conway [4], an integrated circuit is represented symbolically
by a collection of geometric primitives on several different layout layers. The masks used to manufacture the
circuit can later be derived from this collection of layout layers 1 . Formally, a layout layer represents a set of geometric
primitives. All geometric primitives in a given set are said to be "on" that layout layer. One can also form derivative
layers by performing various logical set operations on the layout layers. We will use the general term layer to
refer either to a primary layout layer or a derivative layer.
In the JCH model for design rules, the basic layout primitive is the rectangle. Each rectangle has four edges marking
its boundaries. Where rectangles overlap, their edges are partitioned into disjoint intervals such that all points in a
given interval have the same combination of layers on both sides. The rectangle partitioning operator
defined by Modarres and Lomax [5] can be used for this purpose.
Each edge interval (usually just called an edge) in a rectangle can be assigned a type based on the different layers
that it separates. Furthermore, since each edge is normally part of only one layout rectangle (except in the case of
"touch-edges", which we will address later), the two sides of the edge can be unambiguously defined as the inside
layer and the outside layer. The type of an edge can therefore be expressed with the following notation.
Edge-type: inside-layer/outside-layer (2-1)

Figure

2-1 shows an example of two overlapping rectangles, one on layer A and one on layer B. The right-hand
edge of the rectangle on layer A has been partitioned into three edge intervals with different edge types because of its
overlap with the rectangle on layer B. To label the edges, the JCH model introduces the notation shown in the figure.
We consider A to be a boolean variable indicating whether one side of an edge is on layer A or not. If A appears uncomplemented
it indicates that side is on layer A. Conversely, if A appears complemented (written ) it indicates
that side is not on layer A. Therefore the edge-interval labeled , marked with a bold line, indicates that its
inside-layer consists of both layer A and layer B, while its outside-layer consists only of layer B.
1. In the interest of reducing the number of layout layers, it may not be necessary to maintain a direct one-to-one correspondence between
the layout layers and the masks. For instance, it is common to use only a single layout layer to represent interconnect vias, as the specific
oxide-etch mask that a via will appear on can be inferred from the surrounding layers.
layer A
AB/AB edges
AB/AB edges
AB/AB edges
edge-interval

Figure

Two overlapping rectangles and the resulting edge partitions and types.
AB/AB edges
A
Edges and edge intervals are represented geometrically by a line in the plane. In manhattan layouts, edges are
either vertical or horizontal. Vertical edges have a single x-axis coordinate, labelled , and a pair of y-axis coor-
dinates, labelled and , where by convention . Similarly, horizontal edges have a single
y coordinate and a pair of x coordinates. For simplicity, all of our examples will assume vertical edge, but they are
trivially extended to horizontal edges as well.
In the JCH model, there are two classes of design rules, both involving rectangle edges. Forbidden-edge rules simply
forbid a particular edge-type from occurring. Restricted-separation rules specify a separation value to be enforced
between two parallel edges 2 .
Restricted-separation rules can be viewed as a constraint enforcing either a minimum, maximum, or exact separation
between two edges, edge1 and edge2, and can be written as follows in the case of vertical edges.
Here we are specifying that the distance between the two edges, in the direction perpendicular to the edges, is constrainted
by some value d. The variable d is the design rule parameter, and is in general a conditional quantity whose
value may depend on any properties of the two edges that can be extracted from the layout. Common examples of
these properties are:
. the edge-types of edge1 and edge2
. the presence of rectangles overlapping edge1 or edge2
. the lengths of edge1 and edge2
. the widths of the rectangles formed by edge1 or edge2
. the edge-types of edges that lie between edge1 and edge2
. the degree of overlap of the two edges in the direction perpendicular to the edges
This could imply a semantically complex set of rules, but most common cases tend to be simple. The JCH model
advocates the creation of macros to express the common cases, and the treatment of more complex cases as further
conditions that can be placed on the design rules when required.
The JCH macros involve only the properties in the first bullet, the edge types of the two edges involved. Rectangles
overlapping one or both of the edges can conditionally form a special class of rules called "conjunctive" design rules,
and properties of the edges such as their length form classes of so-called "conditional" design rules in the JCH model.
We will review these in Section 2.3. In this paper, we will show several reasons to include the property of the fifth
bullet, the edges types of all edges lying between the two edges in the layout.
The property mentioned in the last bullet is a common implementation detail worth mentioning. Often, it is only
necessary to enforce a design rule between two edges that overlap somewhere along their length (i.e. vertical edges
must overlap in the y direction) as shown in Figure 2-2(a). However, in some design rules (typically the spacing rules)
the notion of overlap must be implemented carefully in order to ensure that the rule is enforced correctly at rectangle
corners. In these cases, for the purpose of detecting the edge overlap, the ends of the edges must be extended by the
design rule distance d, as shown in Figure 2-2(b). In the JCH model this edge extension is controlled by the "con-
cave" modifier to their "edge function". At these extended rectangle corners, some foundry design rules require the
design rule constraints to enforce the manhattan distance between the edges, and in some cases they allow the shorter
euclidean distance, as shown In Figure 2-2(c). The latter case can be supported by making the design rule parameter d
conditional on the y coordinates of vertical edges. The parameter d can be reduced as the edges cease to overlap in the
y direction, and the constraint is eliminated altogether when the edge-extensions cease to overlap.
In order to describe a design rule, the value of the design rule parameter must be given along with the conditions
under which it applies. As we mentioned above, in the JCH model the value of the design rule parameter in restricted-
2. Here we are assuming a manhattan model for layout in which all edges must be parallel to one euclidean axis. The model can easily be
extended to non-manhattan layouts by allowing constraints between all edges that are not perpendicular.
edge x
edge y1 edge y2 edge y1 edge y2
separation rule
- maximum separation rule
exact separation rule
separation constraints is commonly conditional only on the edge-types of the pair of edges involved. This condition is
given a notational representation which we refer to as an edge-pair, written in the following way:
Since the two edges in the edge-pair notation share a common outside layer, this implies that constraints can only
be placed between adjacent edges. At the end of Section 2. we will show that restricting the edges to be adjacent
proves to be a serious limitation. We will expand the definition of the design rule to include not only the edge-types of
both edges, but also the types of edges that may appear between these two edges. For brevity in our expanded defini-
tion, and in order to emphasize that the two edges must share a common outside-layer, we introduce the following
notation to represent the same edge-pair shown in (2-3).
We call this expression an edge-path, as it represents a sequence of edges between which the constraint lies. We
will develop the grammar for edge-paths more fully in Section 3.
In the remainder of this section we will describe the design rules of the JCH model using the edge-path notation.
These rules can be split up into two categories, one which contains rules involving only a single layer, and one which
contains rules involving two layers. The former are referred to as intra-layer rules, the latter inter-layer rules. These
will be reviewed in Sections 2.1. and 2.2. Section 2.3. will discuss the author's method for addressing design rules
which involve more than two layers, and Section 2.4. will address the limitations of the JCH model.
2.1. Intra-Layer Design Rules
Some design rules involve only a single layer. These are referred to as the intra-layer rules. When checking intra-
layers rules, one layer is considered at a time and the presence of all other layers is ignored. If we refer to this layer as
layer A, the layer type on either side of an edge can take on only the values A and . There are thus four possible
edges that can occur in this situation:
Of these, the patterns and do not represent actual edges, as the layer is the same on both sides. Therefore
d
constraint
euclidean
distance
manhattan
distance
d

Figure

Conditions placed on the design rule constraint by the degree of vertical overlap
of two vertical edges. In (a) a constraint is required because the rectangles overlap in the y
direction. In (b) a constraint is still required to prevent design rule violation at the rectangle
corners until the rectangles are separated in y by more than the distance d. In (c) is demonstrated
two possible interpretations of design rule constraints at rectangle corners.
(b) (c)
d
d overlap
(a)
A
A A
A A
A A
only the remaining two edges will appear in the design rule constraints.
Since the design rule constraints must share a common outside-layer, there are only two intra-layer constraints:
In (2-6) each row represents one design rule. The expressions WIDTH and SPACING represent two different
design rule parameters which correspond to the parameter d in (2-2), and the associated edge-path indicates the conditions
under which this design rule is applied. These two intra-layer rules are diagrammed in Figure 2-3.
2.2. Inter-Layer Design Rules
The case when two different layers can be involved in a design rule is more complex than the single-layer case. In
the JCH model these are referred to as the inter-layer design rules. For any pair of layers present in the design, if we
refer to these layers as layer A and layer B, the layer types on either side of an edge can take on the values , ,
, or . There are therefore 16 possible edges that can be formed, as shown below.
As in the intra-layer case, edges with the same layer type on both sides are not considered to be true edges, and we
can therefore eliminate four of these "non-edges" from the list shown in (2-7). In addition, there are four edges in
which both layers undergo a transition, which can also be eliminated. These edges are called "touch edges" in the
JCH model, and they will not normally be encountered during inter-layer design rule checks. We elaborate on this
issue in Section 4.3. Only the eight edge types shown in bold in (2-7) will be retained for the following analysis.
There are four possible layer types that can represent type1 in a design rule constraint. In order to form a valid pair
of edges there are only two possible values for the type2 layer given type1, and only two possible values for type3
given a value for type2. This results in 16 different inter-layer constraints, as shown below.
A A
A A
layer A layer A
layer A
WIDTH SPACING

Figure

2-3: The two intra-layer design rule parameters of the JCH model
In (2-8) notice that in the SPACING and WIDTH rules the variables for either layer A or layer B appear with the
same inversion in all three of the type1, type2 and type3 layer fields. Thus, this layer is either absent on both sides of
both edges, or always present on both sides. These edge paths will also be matched by the intra-layer WIDTH and
SPACING rules, and the JCH model assumes that they therefore need not be checked here.
With the WIDTH and SPACING rules eliminated, only the remaining four rules require inter-layer design rule
parameters. These four rules are illustrated in Figure 2-4. Note that in the JCH model the A-EXTENSION-OF-B rule
is given the name "extension" while the B-EXTENSION-OF-A rule is given the name "margin". We feel that these
names are ambiguous and have chosen more descriptive names.
Here we would like to point out that neglecting the SPACING and WIDTH constraints in the inter-layer macros
makes sense in the case of the first column in which the unchanging layer is always absent. However the case of the
second column, in which the unchanging layer is present and overlaps both edges, is an example of a "conjunctive"
rule, as discussed in Section 2.3. Conjunctive SPACING and WIDTH rules may be different in some processes than
the non-conjunctive rules, in which case a user may wish to retain these edge-paths as legitimate design rules.
2.3. Conditional and Conjunctive Design Rules
Two classes of design rules which cannot be directly represented in the JCH model are examined by its authors.
They refer to these two classes as conditional and conjunctive design rules.
Conditional design rules are ordinary intra-layer or inter-layer design rules in which the constraint parameter is
conditional on some outside factor. An example of this is the common metal-halation rule which requires a larger separation
between metal wires when one of the wires is wider than some threshold. This rule is a result of processing
effects due to the high reflectivity of interconnect metal and its effect on photoresist exposure times. The specification
of this rule requires that the SPACING rule for a particular layer be made conditional on the width of the rectangle to
which one or both of the edges belongs. This width would have to be extracted from the layout prior to design rule
constraint generation.
In conjunctive design rules, the constraint parameter value depends on the presence or absence of an otherwise
unrelated layer. As an example, step coverage problems in non-planar metallization processes may require the SPACING
between two metal-2 wires to be increased if either wire overlaps metal1. This is an example of the conjunctive
CLEARANCE A-EXTENSION-OF-B B-EXTENSION-OF-A OVERLAP

Figure

2-4: The four inter-layer design rule parameters of the JCH model
inter-layer SPACING rule discussed in the previous section. More complex conjunctive design rules may involve a
third layer, as in a conjunctive CLEARANCE rule between metal-1 and metal-2 wires which is increased if either
wire overlaps a polysilicon wire. This latter case, in which an inter-layer design rule between two layers A and B is
conditional on a third layer C is the only situation in which a design rule may involve edges between more than two
layers.
The authors suggest that some conditional and conjunctive design rule checks can be accomplished by forming
carefully chosen derivative layers. When this fails they suggest an ad-hoc method in which the design rules are
extended with special conditional constraints tailored to the specific problem.
Conditional design rules are difficult to characterize, as there can be an almost endless variety, and it may be the
case that one will always have to resort to ad-hoc methods. However, the extensions to the JCH model that we propose
in Section 3. are capable of expressing any conceivable conjunctive design rule.
2.4. Limitations of the JCH model
Recall that, in the JCH model, a design rule is represented by a constraint between a type1/type2 edge and a type3/
edge. This constraint can be interpreted and implemented in a number of ways. The authors choose to interpret
the constraint as a region of width d extending from the type1/type2 edge from which the type3/type2 edge is forbidden
from appearing, and vice versa.
For reasons of efficiency, the authors have chosen to implement their system with a simplified version of this inter-
pretation. Instead of searching for the type3/type2 edge within the constraint region, they search for any instances of
the layer type3. This would initially appear to be equivalent, but they discuss a case, shown in Figure 2-5(a), in which
these interpretations are not consistent. In this case, their simplified model would search for the layer inside the
constraint region of the edge, and would identify the clearance constraint shown. This should not be flagged
as an error since it does not comply with the original definition of clearance. They state that, in the case of the clearance
constraint, their simplified interpretation is only consistent with their original definition if the following constraint
holds.
A
A
spacing
extension
overlap
clearance
"correct"
clearance
A
A
spacing
extension
overlap
clearance
"correct"
clearance
(a) (b)

Figure

2-5: Examples of a clearance rule as identified by two different constraint implementa-
tions. Figure (a) shows the result of searching for the type3 layer, layer , inside the constraint
region of the type1/type2 edge. Figure (b) shows the result of searching only for the
layer that undergoes a transition across the rule definition's type3/type2 edge, in this case layer
. In both figures we show the "correct" clearance rule that we identify by eye.
{
When saying that the simplified interpretation is "consistent" under these conditions, they mean that edges identified
as constraints by the simplified interpretation, but not the original design rule definition, will never be flagged as
errors unless they violate other design rules as well. Similar constraints can be derived for the other three inter-layer
parameters.
However, we would like to point out that under their simplified interpretation, what most designers would consider
the correct clearance rule, marked in Figure 2-5(a), is never checked. This could lead to a design rule check passing
when in fact an error exists. Furthermore, and potentially more serious, the correct clearance rule is not identified by
the authors original definition of design rules either. The reason for this failure is the presence of an intermediate edge
between the edges that should be checked, which causes the outside layers of the two edges to be different. The following
constraint, more stringent than that of (2-9), is required to guarantee that clearance violations are not missed in
this example. Again, similar constraints are required for the other three inter-layer parameters.
Interestingly, the authors present a second simplified interpretation of the design rule constraints which actually
detects the correct edges in this case. An example of this interpretation in the context of the same clearance rule used
in

Figure

2-5(a) is shown in Figure 2-5(b). Instead of searching the constraint region of the type1/type2 edge for
instances of the layer type3, they search only for the layer that undergoes a transition across the type3/type2 edge
(recall that, in the absence of touch edges, only one layer will transition across the edge.) In this example it is equivalent
to searching for instances of layer B inside the constraint region of the edge. In this situation, the check
does in fact identify the correct clearance constraint, as shown. The authors indicate that this second simplified interpretation
for the design rules is only consistent with their original definition for design rules given the same constraint
written in (2-10). What they failed to observe is that when this constraint is not met, it is the simplified interpretation
that is correct and not the original interpretation. The adoption of this second simplified interpretation may seem to
solve the inaccuracy problem, but in Section 3.3. (Figure 3-4) we will show an example of a clearance rule that would
not be located by this method either.
As a final comment on this second simplified interpretation of the design rule constraints, we note that, unlike the
check in Figure 2-5(a), the check in Figure 2-5(b) is not reflexive. It is not possible to identify the same constraint by
searching for layer A from the edge, as the only inter-layer constraint that begin on edges is the
A-EXTENSION-OF-B constraint. Until this point, all constraints have had duals which allowed the constraint to be
identified starting from either edge involved. When all rules are reflexive, design rule checking can be simplified
because the layout only has to be scanned in one direction along each manhattan axis.
In the following section we develop our edge-path grammar and show how it provides an unambiguous definition
for the design rules under all circumstances. We also show how the edge-path grammar can be used to extend the JCH
design rule model to include a straightforward and consistent model for conjunctive design rules.
3. Extending the JCH model
The true nature of the limitations which have been demonstrated in the JCH model is its inability to model situations
in which one or more intermediate edges lie between the two which must be constrained. When this occurs, the
two edges no longer share a common outside layer, and the rule cannot be written as in (2-3). What is required is a
more general view of the design rule constraints that spans multiple edges. In order to express these, we will extend
the notation which we presented in (2-4) of Section 2., which we have called the edge-path grammar.
3.1. The Edge-Path Grammar
When defined in the most general way possible, a design rule constraint can exist between any two non-perpendicular
edges in a circuit layout. There can be an arbitrary number of intermediate edges between the two constrained
edges, and the value of the constraint can depend on the exact pattern of layer boundaries that make up these edges. If
{
we choose a point on each of the pair of edges we wish to check, and connect them with a line as shown in Figure 3-
1, this line will originate at one edge, cross a specific sequence of layers as we move from one edge to the other, and
terminate on the second edge. We call this sequence an edge-path, which is written as follows.
In an edge-path, type1, type2, ., and typen represent boolean products of layer variables which indicate the presence
or absence of each layer in that particular region. We will now present this in a more formal way.
Definition 3-1: l is a layer in an integrated circuit layout. The layer l can represent either a primary layout layer, or
a derivative layer formed by a sequence of logical set operations on the layout layers.
Definition 3-2: L is the set of all layers present in a particular integrated circuit layout.
Definition 3-3: p is a boolean variable representing a layer . The range of p is the set , in which the
value indicates the absence of layer l, and the value indicates the presence of layer l, in a particular region of
the layout. Alternatively, the range of p can be written where and . If a variable for a particular
layer does not appear in an expression, it can be considered a don't-care condition.
3-4: P is an expression representing the conjunction of one or more boolean variables . P
represents the combination of layers from the subset which are present in a particular region of a
layout. Since the variables p have a binary range, P can be thought of as a cube in an n-dimensional boolean lattice.
Definition 3-5: An edge-path E is a totally-ordered set , written , which represents
a sequence of layers encountered along a line drawn in the plane of the layout. Each pair of adjacent members in
the set, for all , represents an edge at which one or more layers undergoes a transition.
Definition 3-6: The length of an edge-path E is defined as , the number of edges encountered when following
a particular edge-path.
Using the edge-path grammar we have a more powerful notation for representing VLSI design rules than that of
the JCH model's edge-pair. We have already demonstrated that we can represent all of the JCH model intra-layer and
inter-layer rules as edge paths of length two. However, we have also demonstrated that this set of edge-paths is inadequate
to describe the design rules under all circumstances. We will show that a complete set of design rules, including
conjunctive rules and rules involving touch edges, can be modeled under the edge-path notation if the edge paths are
allowed to become arbitrarily long.
Fundamentally, the design rules for a semiconductor process can be described as a large set of edge-path/parame-
ter pairs. However, in order to simplify design rule entry, it is advantageous to follow the methodology of the JCH
model and classify these edge-paths into sets which effectively represent the same design rule. This facilitates the use
of design rule macros that free the user from an intimate knowledge of the full model. Many such classifications are
possible. We will demonstrate that any edge-path can either be classified as one of the six parameters of the JCH
model (SPACING, WIDTH, CLEARANCE, A-EXTENSION-OF-B, B-EXTENSION-OF-A, and OVERLAP), or it
corresponds to a configuration of geometry that does not normally require a design rule.
In some situations this simple classification will be inadequate. It neglects the conjunctive design rules and rules
involving touch edges. In some cases it may actually place a design rule on a geometrical pattern that should be forbidden
from occurring. Obviously the edge-path classification that we present should only be considered a typical
default. The user should be allowed to override the macros and forbid particular configurations, or add new edge-
paths for situations that are not covered, and we will discuss several situations in which it will be common to do so.

Figure

3-1: A edge-path between two edges with an arbitrary number of intervening edges
l L
{ }{ } 1
{ }
{
{ }
{ }
{ } L
{ }
3.2. Edge-Paths of Length Three
We begin by studying all edge-paths of length three. For simplicity, we have decided to forbid touch-edges for the
same reasons as stated earlier, so there are 32 edge paths of length three. It is easy to show that all non-conjunctive
intra-layer design rules can be captured in sequences of length two, so we will only concern ourselves with the inter-layer
design rules.
Recall that our methodology is to examine all possible edge-paths and show that each one either matches a specific
JCH model parameter, or it corresponds to a situation that is not a traditional design rule. Half of the 32 edge-paths of
length three fall under this latter case and do not match any of the six JCH model parameters. These are shown below,
and several examples are diagrammed in Figure 3-2.
One thing that each of the 16 edge-paths in (3-2) have in common is that, like the examples in Figure 3-2, they
begin on an edge of a rectangle, cross the near-side of a second rectangle, and terminate on the far edge of the second
rectangle, or vice versa. These two edges are usually constrainted by the sum of a width and a separation/clearance/
extension rule, and we know of no design rules in use that specify a more stringent rule in these circumstances. For
this reason, we choose to ignore these patterns when they are matched in a layout, essentially making them non-con-
straints. However, we emphasize that a designer could override this decision and specify design rule parameters for
each of these patterns if desired.
Each of the remaining 16 edge-paths can be matched to a specific intra-layer or inter-layer design rule parameter
as defined in the JCH model. These are shown below and diagrammed in Figure 3-3.
A A

Figure

3-2: Examples of edge-paths of length three that do not correspond to any inter-layer
rule
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
AB AB AB AB
Upon examining the 16 edge-paths in (3-3), we note that, just as in the case of the inter-layer edge-paths of length
two, the SPACING and WIDTH rules would be matched by the corresponding intra-layer design rules, and we can
eliminate them from the default inter-layer design rule specification. However, as before, these patterns represent conjunctive
design rules and the user may wish to specify these edge-paths to the system manually.
The remaining eight edge-paths should be generated by the inter-layer design rule macro in addition to the edge
paths in (2-8). They represent layout patterns which may exist in the layout but which are not matched by any of the
design rules in the JCH model. This will eliminate the constraints under which the JCH model will either indicate a
false positive or false negative during a design rule check as a result of layout situations like those addressed in [2],
and repeated in Figure 2-5. Of course some of these patterns, especially the new EXTENSION edge-paths, may correspond
to geometry which should not occur in the layout. If this is the case, the designer should specify these edge-
paths as forbidden edge types instead of allowing them to be matched to the corresponding inter-layer design rule.
3.3. Edge Paths of Length Four and Above
There are 64 edge paths of length four, 128 edge paths of length five, with the number continuing to double as the
length increases. For brevity we will only summarize our results in this section. It turns out that we can identify conjunctive
WIDTH and SPACING constraints with edge-paths of arbitrary length. We show the four layer A WIDTH
and SPACING design rules of length four in Figure 3-4. It is clear from these examples that we can insert an arbitrary
number of layer B edges between the layer A edges whose width or spacing is to be constrained, and vice versa. How-
ever, all of these cases can probably be covered by a single conjunctive intra-layer macro, if not by the original non-
conjunctive intra-layer macro.
Also shown in Figure 3-4 are the only inter-layer design rules of length four or larger, two CLEARANCE rules.
These two edge-paths, shown below in (3-4), should also be generated by the design rule compiler when an inter-layer
design rule macro is specified by the user, or specified as forbidden edge-paths by the user if they correspond to
an illegal configuration.
It is interesting to note that the CLEARANCE rules shown here would not be detected by the JCH model's second
simplified interpretation for the design rule constraints, which was discussed in Section 2.4. Under this interpretation
the CLEARANCE rule is detected by searching for instances of layer A within the constraint region of
edges and instances of layer B within the constraint regions of edges. However, there are no regions
along this edge path.
A
A
A
A-WIDTH
A
B-WIDTH
A
A
A
A

Figure

3-3: The 8 inter-layer design rules for edge-paths of length three
A
A
Just as was done in Equation 2-9, we can write the following constraint on the design rule parameters under which
the original JCH model will still be valid for these two CLEARANCE rules. This constraint is more strict than the
constraints described by the authors, and it corresponds to a situation in which their model could potentially have
generated false positive design rule checking results.
As a final result, we state that, with the exception of the conjunctive intra-layer design rules mentioned above,
which continue to appear in edge-paths of any length, there are no inter-layer design rules of length greater than four.
It should be obvious that OVERLAP rules cannot exist with path lengths greater than two (i.e. there can be no intermediate
edges.) In the case of the CLEARANCE and EXTENSION rules, except in the cases we have already dem-
onstrated, long edge-paths always contain shorter sub-strings that also match the same rule. This shorter sub-path
therefore covers the longer edge-path, guaranteeing that it will never be in violation. Examples of this effect are presented
in Figure 3-5.
A
A
A-WIDTH
A
A
A
A
A

Figure

3-4: The SPACING and WIDTH design rules for layer A (the rules for B are the same but
with A and B reversed), plus the two CLEARANCE rules, for edge-paths of length four.
A A
A
A-WIDTH
{
A
A

Figure

3-5: Example of cases in which a design rule with a path-length of four is blocked by
an identical rule which is a sub-expression of the same edge-path
A A
4. Implementation Suggestions
In this section we discuss several implementation details which are important if this model is to be incorporated
into a practical design system. In Section 4.1. we present a simple state machine representation of the design rule
edge paths which neatly summarizes the results of Section 3. As mentioned previously, there are no conjunctive rules
in the default specification, and by default touch edges are forbidden between layers that are to be checked for viola-
tions. In Sections 4.2. and 4.3. we show how this system can be extended to specify conjunctive inter-layer design
rules, and how touch-edges can be handled in an elegant way.
4.1. State Machine Representation of Design Rules
Section 3. presented a large collection of edge-paths and the design rule parameter that is associated with each.
These can be neatly summarized by the state diagram shown in Figure 4-1. We can view an edge-path as a straight-line
drawn in the layout plane, beginning at a point on a rectangle edge (the source edge), and projecting in a direction
perpendicular to that edge. As this line is traversed from the source-edge outward, each new edge that is encountered
will cause a state transition that maintains a record of the previous edges that have been encountered, and indicates
when a design rule check is needed. The line traversal can end when a terminal vertex in this state diagram is reached.
Design rule constraints are required when certain states are reached, as shown in the state diagram.
This conceptual view, in addition to providing a compact summary of the edge-path checks, leads to a direct
implementation of the common shadow algorithm used for constraint-generation in one-dimensional compaction, a
good summary of which is presented in [9].
begin
BEA
BEA C
O
BEA
BEA
O
done
done
done
done
done
done
done
done
done
done
done
done
done
done

Figure

4-1: State machine that summarizes the edge-paths resulting in design rule checks.
Key:
4.2. Conjunctive Design Rule Specification
We have already demonstrated how four of the inter-layer edge-paths of length two correspond to rules that can be
considered conjunctive versions of the intra-layer width and spacing rules. These edge-paths are ignored in the JCH
model because they are covered by the intra-layer rules. However, if conjunctive versions of these rules are required,
some method must be present to allow them to be checked.
Conjunctive versions of the inter-layer rules are also common. These can be specified simply by allowing edge-
path expressions to contain three or more boolean layer variables. As an example, Figure 4-2 shows a conjunctive
CLEARANCE rule in which the separation between layers A and B changes because of their overlap of layer C.
If conjunctive rules are required, the JCH model outlines a strategy which makes use of derived-layers obtained
through logical set operations on the existing layout layers. However, in the design rule system that we have outlined,
these rules can be specified directly by adding their edge-paths as additional checks. Of course, when three or more
layers are involved in the edge path expressions, this will result in a large number of possible edge-paths that a user
would be required to enter into the system, and that must be added to the state machine in Figure 4-1.
4.3. Touch Edges
In the JCH model, "touch-edges" are edges at which more than one layer undergoes a transition. Figure 4-3 shows
the two types of touch-edges which can occur during inter-layer checks. Outside-touch edges ( and
are formed when rectangles touch but don't overlap, and inside-touch edges ( and
are formed when rectangles overlap and touch on one edge.
The authors of the JCH model chose not to include touch edges in their definitions of the inter-layer rules. Instead
they introduce two flags into the inter-layer macro that, if set, simply forbid them from appearing for each pair of lay-
ers. Their reasoning is not given, but straightforward. It is usually the case that if any design rules exist between two
layers, touch edges will be forbidden from occurring. If the two layers interact during processing so as to require
design rules between them, the overlap, extension, and clearance rules ensure that rectangle edges are separated. It is
inconsistent under these circumstances to allow two rectangles to touch without overlapping. Conversely, if there are
no design rules between two layers, implying that they don't interact with each other during processing, there is no
reason for touch edges to be forbidden.

Figure

4-2: A conjunctive CLEARANCE rule involving layers A, B, and C.
A A
OUTSIDE_TOUCH INSIDE_TOUCH

Figure

4-3: Examples of OUTSIDE_TOUCH and INSIDE_TOUCH edges
It is unclear exactly how the design rules should be defined when touch edges are allowed on layers between
which design rule are defined. One valid option is that the designer could enter edge-path expressions to specify the
design rules between touch-edges and other edges. However, this could result in a large number of new rules.
The JCH model deals with touch edges by considering the inter-layer rules to be "minimum distance or touch
rules", though they fail to elaborate precisely what this means. We interpret this as meaning that when a touch-edge is
encountered, constraints are generated to the touch-edge exactly as if it were two separate edges of each layer individ-
ually. Thus, there can potentially be two constraints generated between a normal edge and a touch-edge, and there
may be up to four constraints generated between two touch edges.
If we make use of the state-machine description of the design rules shown in Figure 4-1, there is a particularly elegant
way of viewing constraint generation for touch edges under this "minimum distance or touch rule" interpreta-
tion. If a touch edge is encountered as an edge-path is being traced through the layout, the state machine simply
explores both branches out of the current state.
5. Conclusions
In Section 2.4. we discussed several limitations of the JCH model in the context of several examples provided by
its authors. We showed how the original definition of the design rules, a constraint between a type1/type2 and a type3/
type2 edge, can fail to match some edge patterns to the correct design rule. Two alternative interpretations for the
design rule definitions are presented by the authors. The first, which they chose to implement, searches for any
regions of type3 material inside the constraint region of the type1/type2 edge, and vice versa. The second interpretation
presented by the authors searches the type1/type2 constraint region for the presence of the layer in type3 that
makes a transition across the type3/type2 edge. As the authors point out, all three interpretations can yield different
results under certain conditions. All three methods can report false design rule violations under certain conditions
given by the authors, and more importantly, it can fail to report design rule violations under certain conditions, as we
have shown.
The authors of the JCH model have presented some constraints under which their various implementations of the
design rules are correct, in the sense that a design rule violation will not be reported between edges which are incorrectly
flagged with constraints by their model. However, we have demonstrated that their constraints are insufficient,
causing legitimate design rules to be missed. With tighter constraints their model can easily be corrected, but we do
not think that creating conditions under which the model does not apply is an elegant solution.
The root of the limitations of the JCH model are its inability to recognize design rules between rectangle edges
which are not adjacent. We propose an extension to the JCH model in the form of a new syntax for expressing the lay-out
patterns that define the different design rules, which we call an edge-path.
Edge-paths can express a constraint between two edges that are separated by a sequence of edges of arbitrary
length. With this syntax, we can perform an exhaustive examination of all possible edge-paths and check each pattern
to see if it corresponds to a design rule that should be enforced. We have demonstrated that we can characterize all
edge paths through the use of the six original JCH model design rule parameters. The two intra-layer parameters can
be expressed with only four edge-paths, all of length two. The four inter-layer parameters can be expressed using
edge paths with a length of at most four. We have also shown how this new syntax can be used to elegantly express
design rules involving "touch-edges" as well as the conjunctive design rules mentioned by the authors of the JCH
model.

Acknowledgments

The authors would like to thank Ronald Lomax and Jeff Bell for reading early drafts of this paper and for their
insightful comments.



--R

Cadence Design Systems
Formal definitions of edge-based geometric design rules
Combinatorial Algorithms for Integrated Circuit Layout.
Introduction to VLSI Systems.
A Formal Approach to Design-Rule Checking
Computational Geometry: An Introduction.
A statistical design rule developer.
Silicon Processing
Symbolic layout and compaction.
--TR
Computational geometry: an introduction
Combinatorial algorithms for integrated circuit layout
Introduction to VLSI Systems
Magic
Lyra
design rules;layout verification;design rule checking