PATENT 028651-001
DATA COMPRESSION PROCESS
BACKGROUND OF THE INVENTION
5 Field of the Invention:
The present invention generally relates to
processes for compressing geometrical data and, more
particularly, to processes for compressing data
relating to geometrical structures such as layouts
10 of integrated circuits.
State of the Art:
Modern integrated circuits, including
application-specific integrated circuits of the LSI
(large scale integration) or VLSI (very large scale
15 integration) class, normally are comprised of many
thousands of individual functional blocks. For
instance, functional blocks in integrated circuits
may comprise random access memories (RAMs), read-
only memories (ROMs), or arithmetic logic units
20 (ALUs). Also, functional blocks-may be as simple as
individual logic gates.
It is well known that computer-aided design
(CAD) tools can be used for designing application-
-1-
specific integrated circuits (ASICs). When
designing and fabricating such circuits, information
must be provided as to the layouts of the circuits.
In practice, layouts of integrated circuits can
5 comprise arrays of millions of polygonal shapes.
The locations of individual polygonal shapes within
the layouts are customarily described by specifying
the locations of the vertices of the polygons.
Because a high degree of precision is required when
10 describing layouts of integrated circuits, the
coordinates of the vertices of the polygonal shapes
must each have a relatively large number of
significant digits. Thus, in ordinary practice,
very large quantities of numeric information are
15 required to describe layouts of large integrated
circuits.
Although layout information for integrated
circuits can be manipulated quickly by modern
computers such as engineering work stations, the
20 communication of layout information from one
location to another through normal telecommunication
channels is slow and costly. For example,
communication of the layout of a typical VLSI
circuit over conventional telephone lines (i.e., via
25 a modem) can take many hours. Accordingly, there
exists a need for a process for compressing data
describing the layout of integrated circuits so that
-2-
the layout information can be readily communicated
over conventional telephone lines at substantially
increased speeds and, hence, at substantially
reduced cost.
5 SUMMARY OF THE INVENTION
The data compression techniques of the
present invention are normally applied to integrated
circuits, particularly ASIC circuits, that have been
designed with computer-aided design (CAD) methods.
10 The first data compression technique
according to the present invention is premised upon
the fact that, in most integrated circuits that have
been designed with computer-aided design (CAD)
methods, the circuits are comprised of arrays of
15 similar polygonal shapes having the same
orientation. Thus, as applied to integrated
circuits that have been designed with computer-aided
design (CAD) methods, the process according to the
present invention includes the steps of assigning
20 unique tokens to describe selected geometrical
attributes of sets of polygonal shapes, which tokens
ordinarily are less than a single byte of binary
information. For example, a token can be used to
signify that the x-direction coordinates of a second
25 polygon are all spaced from respective ones of the
-3-
x-direction coordinates of a first polygon by the
given distance.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention can be further
5 understood by reference to the following description
and the appended drawings which illustrate the
preferred embodiments of the invention. In the
drawings:
Figure 1 provides an example of a layout that
10 includes several repetitive polygonal shapes with
identical orientations and equal spacing;
Figure 2 provides an example of a layout that
includes a polygon having several redundant
coordinates;
15 Figure 3 provides an example of a layout that
includes several repetitive box-like shapes with
identical orientations but unequal spacing; and
Figure 4 provides an example of a layout that
includes several complex polygonal shapes with
20 identical orientations but unequal spacing.
-4-
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS OF THE
INVENTION
In Figure 1, an irregular polygonal shape El
has six vertices. If the six vertices were
5 described by their respective Cartesian coordinates,
six sets of numbers (x,y) would be required. (The
number llxll in each set normally designates the x-
direction coordinate of a vertex, and the number Ily"
designates the y-direction coordinate of a vertex.)
10 For purposes of discussion, the six vertices of
polygon El are designated, respectively, as (a,b),
(c,a), (c,d), (e,d), (e,f), and (a,f). Typically,
each of the numbers "a" through "f" usually have six
or more significant digits.
15 As mentioned above, a typical layout of an
integrated circuit can contain millions of polygonal
shapes such as shown in Figure 1. Accordingly, a
very large quantity of information is required to
communicate the layout information from one location
20 to another through normal telecommunication
channels. The following will describe techniques
for compression, or abbreviation, of the layout data
in a manner that reduces the time and expense of
data transmission.
-5-
A first data compression technique is
premised upon the observation that layouts of most
integrated circuits comprise arrays of repetitive
similar shapes having the same orientation. Thus,
5 by way of example, Figure 1 shows three polygonal
shapes E1, E2, and E3 that each have the same shape
and orientation at equal locations along a base line
11. If the array of those three polygonal shapes
were described using conventional Cartesian
10 coordinates, the description would require thirty-
six numbers (i.e., eighteen couplets of numbers)
where the circuit had only a single layer.
Compression of placement information for the
polygonal shapes in Figure 1 can be achieved by
is assigning "tokens" to describe selected geometrical
attributes of the polygons, where each token
comprises less than a single byte of binary
information. As a specific example, a token such as
the symbol "{" followed by the number "d" (i.e.,
20 "{d" ) could be used to signify that the x-direction
coordinates of the second polygon E2 are all spaced
from respective ones of the x-direction coordinates
of the first polygon by the given distance "d".
Given that the coordinates of the vertices are each
25 expressed as an ordered set, the same token "{"
could be used to signify that the y-direction
coordinates of the second polygon E2 are equal to
-6-
respective ones of the y-direction coordinates of
the first polygon El.
Once it is found that there is constant x-
direction displacement between corresponding ones of
5 the vertices of the second polygon E2 and the
vertices of first polygon El, the location and shape
of the third polygon E3 relative to the second
polygon E2 can be described by a single token. That
is, the location and shape of the third polygon E3
10 can be described without explicitly designating the
distance that separates its vertices from respective
ones of the vertices of the second polygon E2. Thus,
the description of the layout of the third polygon E3
can be compressed relative to the description of the
15 layout of second polygon E2.
A related data compression technique is
premised upon the observation that polygons in
integrated circuit layouts often have redundant
coordinates. In other words, data compression can
20 be achieved by eliminating coordinate redundancy.
A simplified example of coordinate redundancy
is provided by Figure 2. In that drawing, a polygon
E4 has a simple square shape, and the coordinates of
its vertices are given by the ordered sets of
25 numbers (A,B), (C,B) (C,D) and (A,D). In those four
-7-
sets, the numbers "A," "B," "IC," and "D" appear
twice and, hence, are redundant. The redundancy can
be eliminated by introducing tokens "r" and as
shown in Table I below:
5 Conventional A,B C,B C,D A,D;
Compressed A,B C,r r,D, -,r;
TABLE I
In Table I, the letter P. designates that
polygons are described by both the conventional data
10 and the compressed data. In the compressed
description, the token 'Ir" denotes that one of the
last x-dimension or y-dimension coordinates should
be repeated. Specifically, the first instance of
the token 'Ir" designates that the last x-dimension
15 coordinate (i.e., B) should be repeated. Likewise,
the second instance of the token "r" designates that
the last y-dimension coordinate (i.e., C) should be
repeated. Further in Table I, the token 11 - "
denotes that the first x-dimension coordinate of the
20 polygon should be repeated.
Yet another data compression technique is
premised upon the observation that numbers that
describe relative distances between vertices of
polygonal shapes in integrated circuit layouts are
25 usually substantially smaller (i.e., have fewer
-8-
significant digits) than the numbers that are
required to describe the distances between the
vertices and a common origin point. For instance,
the ordered set of numbers (698880, 395160) might be
5 required to describe the Cartesian coordinates of a
vertex of a polygon relative to an origin point,
while the position of that particular vertex
relative to another vertex of the same polygon might
be described by the ordered set of numbers such as
(0, 240) having substantially fewer significant
digits.
In the following, numbers that describe
displacements of vertices relative to one another
are called "delta" numbers. In layouts of
integrated circuits, common delta numbers can
frequently be found. That is, polygons are usually
located at equally spaced intervals in layouts of
integrated circuits. As will be explained further
below, substantial data compression can be achieved
by representing common delta numbers as tokens.
In conjunction with the simple rectangular
boxes B1 through B4 shown in Figure 3, Table II
provides a more detailed example of the above-
described data compression techniques. Initially, it
should be noted that boxes B, through B4 have
identical shapes and orientations but unequal spacing.
-9-
ARRAY OF BOXES BEFORE COMPRESSION
P 698640 394920 698640 395160 698880 395160 698880 394920;
P 699360 394920 699360 395160 699600 395160 699600 394920;
P 700080 394920 700080 395160 700320 395160 700320 394920;
P 700860 394920 700860 395160 701100 395160 701100 394920;
ARRAY OF BOXES AFTER COMPRESSION
P 698640 394920 & [240 [240|
P {720?
p +
P {780?
TABLE II
5 In the case of the first box described in
Table II, the token "&" designates that the
preceding y-dimension coordinate of the polygon
should be repeated. The token "[" designates the
preceding x-direction coordinate of the polygon
10 should be repeated with the quantity 240 added to it
(i.e., 394920 + 240 = 395160). Similarly, in its
second occurrence, the token "[" indicates that the
preceding y-dimension coordinate of the polygon
should be repeated with the quantity 240 added to it
15 (i.e., 698640 + 240 = 698880).
-10-
Further with reference to the description of
the first box in Table II, the token "|" indicates
that the first box is to be closed by a simple right
angle corner connecting the first vertex with the
5 last specified vertex. Thus, in this example, the
x-direction coordinate of the third vertex of the
first box will be understood, and the x- and y-
direction coordinates of the fourth vertex will be
understood to be redundant.
10 With reference to the description of the
second box in Table II, the token "{" signifies that
the x-direction coordinates of the second box are
all spaced from respective ones of the x-direction
coordinates of the first box by a given distance
15 (i.e., 720 units). Finally as to the second box,
the token "?" signifies that the coordinates of the
second box are to be completed in the same way as
the first box.
As to the third box defined by Table II, the
20 token "+" signifies that the x- and y-direction
coordinates of the vertices of the third box are
related to respective ones of the coordinates of the
vertices of the second box in the same manner that
the x- and y-direction coordinates of the vertices
25 of the second box are related to respective ones of
-11-
the coordinates of the vertices of the first box.
In accordance with the preceding discussion
and the complex polygonal shapes P1 through P4 shown
in Figure 4, Table 3 provides a more comprehensive
example of the above-described data-compression
techniques.
ARRAY OF POLYGONS BEFORE COMPRESSION
P 635780 746220 635780 746820 636080 746820 636080
747000 636020 747000 636020 747180 636200 747180
636200 747120 636440 747120 636440 747360 636980
747360 636980 747120 636740 747120 636740 746940
636800 746940 636800 746880 636860 746880 636860
746760 636740 746760 636740 746820
636680 746820 636680 746880 636440 746880 636440
746760 636320 746760 636320 746640 636440 746640
636440 746520 636560 746520 636560 746340
636380 746340 636380 746460 636260 746460 636260
746580 636020 746580 636020 746220;
P 637220 746220 637220 746820 637520 746820 637520
747000 637460 747000 637460 747180 637640 747180
637640 747120 637880 747120 637880 747360 638420
747360 638420 747120 638180 747120 638180 746940
638240 746940 638240 746880 638300 746880 638300
746760 638180 746760 638180 746820 638120 746820
638120 746880 637880 746880 637880 746760 637760
746760 637760 746640 637880 746640 637880 746520
638000 746520 638000 746340 637820 746340 637820
746460 637700 746460 637700 746580 637460 746580
637460 746220;
P 638660 746220 638660 746820 638960 746820 638960
747000 638900 747000 638900 747180 639080 747180
639080 747120 639320 747120 639320 747360 639860
747360 639860 747120 639620 747120 639620 746940
639680 746940 639680 746880 639740 746880 639740
746760 639620 746760 639620 746820 639560 746820
-12-
639560 746880 639320 746880 639320 746760 639200
746760 639200 746640 639320 746640 639320 746520
639440 746520 639440 746340 639260 746340 639260
746460 639140 746460 639140 746580 638900 746580
638900 746220;
P 640220 746220 640220 746820 640520 746820 640520
747000 640460 747000 640460 747180 640640 747180
640640 747120 640880 747120 640880 747360 641420
747360 641420 747120 641180 747120 641180 746940
641240 746940 641240 746880 641300 746880 641300
746760 641180 746760 641180 746820 641120 746820
641120 746880 640880 746880 640880 746760 640760
746760 640760 746640 640880 746640 640880 746520
641000 746520 641000 746340 640820 746340 640820
746460 640700 746460 640700 746580 640460 746580
640460 746220;
ARRAY OF POLYGONS AFTER COMPRESSION
P635780 746220&[600[300&&[180]60&&[180[180&&]60[240&&
[240[540&&]240]240&&]180[60&&]60[60&&]120]120&&
[60]60&&[60]240&&]120]120&&]120[120&&]120[120&&
]180]180&&[120]120&&[120]240|
P{1440?
P+
P{1560?
TABLE 3
Although the foregoing has described the
principles, preferred embodiments and modes of
operation of the present invention that result in
substantial data compression, the invention should
not be construed as limited to the particular
embodiments discussed. Instead, the above-described
-13-
embodiments should be regarded as illustrative
rather than restrictive, and it should be
appreciated that variations may be made in those
embodiments by workers skilled in the art without
departing from the scope of present invention as
defined by the following claims.
-14-
WHAT IS CLAIMED IS:
1 1. A process for compressing data relating
2 to polygonal shapes within layouts of integrated
3 circuits comprising the steps of:
4 assigning unique tokens to describe selected
5 geometrical attributes of sets of polygonal shapes,
6 which tokens ordinarily are less than a single byte
7 of binary information.
1 2. A process according to claim 1 wherein a
2 token is used to signify that the x-direction
3 coordinates of a second polygon are all spaced from
4 respective ones of the x-direction coordinates of a
5 first polygon by the given distance.
1 3. A process according to claim 2 wherein
2 the same token is used to signify that the y-
3 direction coordinates of the second polygon are
4 equal to respective ones of the y-direction
5 coordinates of the first polygon.
1 4. A process according to claim I further
2 wherein, if there is constant x-direction
3 displacement between corresponding ones of the
4 vertices of a second polygon and the vertices of a
5 first polygon, the location and shape of a third
-15-
6 polygon relative to the second polygon is described
7 by a single token.
1 5. A process according to claim 4 further
2 wherein the location and shape of the third polygon
3 is described without explicitly designating the
4 distance that separates its vertices from respective
5 ones of the vertices of the second polygon.
1 6. A process according to claim I further
2 comprising the steps of introducing token values in
3 the sets of numbers that represent the vertices of
4 polygons for eliminating redundancy.
1 7. A process according to claim 1 further
2 comprising the step of describing relative distances
3 between vertices of polygonal shapes in integrated
4 circuit layouts rather than the distances between
5 the vertices and a common origin point.
-16-
ABSTRACT OF THE DISCLOSURE
A process for compressing data describing the
layout of integrated circuits so that the layout
information can be readily communicated over
5 conventional telephone lines at substantially
increased speeds and, hence, at substantially
reduced cost. As applied to integrated circuits
that have been designed with computer-aided design
(CAD) methods, the process includes the steps of
10 assigning unique tokens to describe selected
geometrical attributes of sets of polygonal shapes,
which tokens ordinarily are less than a single byte
of binary information. For example, a token can be
used to signify that the x-direction coordinates of
15 a second polygon are all spaced from respective ones
of the x-direction coordinates of a first polygon by
the given distance.
-17-
Page created by: rh@ot1.com
Changes last made on: 02/08/06
HomePage