Abstract:
One embodiment of the present invention provides a system that facilitates representing a shape within a layout of an integrated circuit using a Boolean expression. The system operates by first receiving a representation of the shape and then converting the representation of the shape into a Boolean expression that is formed using a Boolean coordinate system expressed in a two-dimensional Gray code. The system then performs operations on the shape by performing Boolean operations on the Boolean expression for the shape.

Description:
BACKGROUND 
     1. Field of the Invention 
     The present invention relates to the process of designing an integrated circuit. More specifically the present invention relates to a method and an apparatus that uses Boolean expressions to represent shapes within a layout of an integrated circuit. 
     2. Related Art 
     As rapid advances in semiconductor technology make it possible to incorporate larger amounts of circuitry onto a semiconductor chip, it is becoming increasingly more difficult to generate a layout for circuit components on the semiconductor chip. This difficulty is exacerbated by differences between representations of the logical design of the circuitry and the physical layout of the circuitry. 
     The process of creating an integrated circuit typically starts with a logical description of the circuit. This logical description is subsequently transformed into a register transfer language (RTL) description. This RTL description is further transformed into a gate-level description of the circuit. Collectively, these steps are referred to as the “logical design” of the integrated circuit. 
     Upon completion of the logical design, the logical design is transformed into a physical design. Note that there exists a disparity between representations used in the logical design and the physical design. The logical design is typically represented in the Boolean domain, while the physical design is typically represented in the real-value domain. These different representations make the process of converting the logical design into the physical design difficult and time-consuming. Moreover, operations on the physical design involve numerical operations on real values. These numerical operations are much slower than the logical operations involving logical values that take place during the logical design process. 
     What is needed is a method and an apparatus that facilitates performing operations on the physical design of an integrated circuit without the problems described above. 
     SUMMARY 
     One embodiment of the present invention provides a system that facilitates representing a shape within a layout of an integrated circuit using a Boolean expression. The system operates by first receiving a representation of the shape and then converting the representation of the shape into a Boolean expression that is formed using a Boolean coordinate system expressed in a two-dimensional Gray code. The system then performs operations on the shape by performing Boolean operations on the Boolean expression for the shape. 
     In one embodiment of the present invention, the system incorporates the shape into the layout of the integrated circuit by incorporating the Boolean expression for the shape into a Boolean expression for the layout. 
     In one embodiment of the present invention, the system expresses multiple layers on a physical chip layout by using additional bits in the two-dimensional Gray code. 
     In one embodiment of the present invention, the system creates a Boolean function using the Boolean expression, whereby the Boolean function can be used to determine if a point is inside the shape. 
     In one embodiment of the present invention, performing operations on the shape can include performing AND operations, OR operations, EXCLUSIVE-OR operations, CONTAINMENT operations, or EQUIVALENCE operations. 
     In one embodiment of the present invention, the system defines a non-rectangular area by combining Boolean expressions of rectangular areas. 
     In one embodiment of the present invention, if the shape is a rectangle, the shape is represented using coordinates for each corner of the rectangle. 
     In one embodiment of the present invention, if the shape has a constant width, the shape is represented using coordinates for each end of the shape. 
    
    
     BRIEF DESCRIPTION OF THE FIGURES 
     FIG. 1 illustrates computer  102  in accordance with an embodiment of the present invention. 
     FIG. 2A illustrates two numbered points in accordance with an embodiment of the present invention. 
     FIG. 2B illustrates the points of FIG. 2A reflected about a horizontal line in accordance with an embodiment of the present invention. 
     FIG. 2C illustrates the points of FIG. 2B with prefixed zeros and ones in accordance with an embodiment of the present invention. 
     FIG. 2D illustrates the points of FIG. 2C reflected about a vertical line in accordance with an embodiment of the present invention. 
     FIG. 2E illustrates the points of FIG. 2D reflected about a horizontal line in accordance with an embodiment of the present invention. 
     FIG. 2F illustrates the points of FIG. 2E reflected about a vertical line in accordance with an embodiment of the present invention. 
     FIG. 3 is a flowchart illustrating the process of numbering a plane with a two-dimensional Gray code in accordance with an embodiment of the present invention. 
     FIG. 4 is a flowchart illustrating the process of incorporating a shape into an integrated circuit layout in accordance with an embodiment of the present invention. 
     FIG. 5 illustrates an alternate example of determining containment in accordance with an embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION 
     The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein. 
     The data structures and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as the Internet. 
     Computer System 
     FIG. 1 illustrates computer  102  in accordance with an embodiment of the present invention. Computer  102  can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance. 
     Computer  102  contains a number of code modules that perform various functions to facilitate using Boolean representations for shapes in a layout of an integrated circuit. These code modules include shape receiver  104 , Boolean point enumerator  106 , converter  108 , Boolean function generator  110 , and Boolean operator  114 . Shape receiver  104  receives shapes from an integrated circuit design system. Typically, these shapes are logical representations of circuit elements for an integrated circuit. 
     Boolean point enumerator  106  generates unique numbers for each point on the integrated circuit chip. The unique numbers are derived using a two-dimensional Gray code as described below in conjunction with FIGS. 2A-2F. This Gray code can be extended to a three-dimensional Gray code by adding bits for multiple layers and extending the method described below into the third dimension. 
     Converter  108  converts the representation of a shape received by shape receiver  104  into a Boolean expression that is formed using the Gray code coordinate system provided by Boolean point enumerator  106 . These Boolean expressions can be used to describe areas on the integrated circuit chip and can be operated upon using Boolean operators to combine shapes, thereby allowing arbitrary shapes to be encoded as Boolean expressions. 
     Boolean function generator  110  combines these Boolean expressions into functions. For example, one function can be used to determine if a point is within a shape. When this function is applied to the coded number of a point, it produces a true or a false indication of whether the point is within the shape. 
     Boolean operator  114  performs operations such as AND, OR, XOR, and EQUIVALENCE for purposes such as combining shapes and modifying shapes. Note that these Boolean operations operate on strings of bits instead of numerical values. 
     Numbering the Layout 
     FIGS. 2A-2F illustrate how a two-dimensional Gray code is constructed for numbering the points on the integrated circuit. FIG. 2A illustrates two numbered points in accordance with an embodiment of the present invention. Note that the points are shown as rectangles to provide clarity to the figures. Furthermore, note that these points may be densely packed on the surface of an integrated circuit chip. The points shown in FIG. 2A are numbered  0  and  1 . 
     FIG. 2B illustrates the points of FIG. 2A reflected about a horizontal line in accordance with an embodiment of the present invention. Horizontal line  202  has been placed next to the numbered points of FIG.  2 A and the point numbers have been reflected across horizontal line  202 . This results in four numbered points, however two points are numbered zero and two points are numbered one. To provide unique numbers and to provide a two-dimensional Gray code numbering, the numbers are augmented with prefixing zeros and ones as described below in conjunction with FIG.  2 C. 
     FIG. 2C illustrates the points of FIG. 2B with prefixed zeros and ones in accordance with an embodiment of the present invention. Each point on one side of horizontal line  202  receives a prefixing zero, while each point on the other side of horizontal line  202  receives a prefixing one. Note that using prefix values is not the only method for providing a unique two-dimensional Gray code numbering for the integrated circuit surface. For example, the zeros and ones could be added as a postfix to the original numbers rather than a prefix. 
     FIG. 2D illustrates the points of FIG. 2C reflected about a vertical line in accordance with an embodiment of the present invention. Vertical line  204  is placed adjacent to the points of FIG.  2 C and the point numbers are reflected across vertical line  204 . After the point numbers have been reflected, prefixing zeros and ones are added with zeros prefixed on the left of vertical line  204  and ones prefixed on the right of vertical line  204 . Note that prior to prefixing the zeros and ones, the right side is a mirror image of the left side. 
     FIG. 2E illustrates the points of FIG. 2D reflected about a horizontal line in accordance with an embodiment of the present invention. The point numbers are reflected about horizontal line  206  in a similar manner to that described above. After the point numbers have been reflected, prefixing zeros and ones are also added in a similar manner. 
     FIG. 2F illustrates the points of FIG. 2E reflected about a vertical line in accordance with an embodiment of the present invention. The point numbers are reflected about vertical line  208  in a similar manner to that described above. After the point numbers have been reflected, prefixing zeros and ones are also added in a similar manner. These operations of reflecting the current point numbers across a vertical or horizontal line and then prefixing zeros to the numbers on one side of the line and prefixing ones to the numbers on the other side of the line continues until the total surface has been numbered. Once the entire surface has been numbered, the process can be continued to provide numbering for additional layers of the integrated circuit. To number the different layers, the process continues by reflecting the surface numbers across a plane parallel to the surface and then adding zeros on one side of the plane and ones on the other side of the plane in a manner similar to that described above. Note that other means can be used to provide the two-dimensional Gray code numbering. 
     Numbering a Plane 
     FIG. 3 is a flowchart illustrating the process of numbering a plane with a two-dimensional Gray code in accordance with an embodiment of the present invention. The system starts by receiving a representation of an integrated circuit chip (step  302 ). Next, the system numbers two points within the chip (step  304 ). One of these points is numbered zero and the other point is numbered one. 
     The system then determines if all of the points have been numbered (step  306 ). If so, the process is ended. Otherwise, the system reflects the numbered points about a vertical or a horizontal line as described above with respect to FIGS. 2A-2F (step  308 ). Next, the system adds a zero to each point number on one side of the line and adds a one to each point number on the other side of the line (step  310 ). The process then continues at step  306  to determine if all points have been numbered. 
     Incorporating a Shape 
     FIG. 4 is a flowchart illustrating the process of incorporating a shape into an integrated circuit layout in accordance with an embodiment of the present invention. The system starts by receiving a representation of a shape to incorporate into an integrated circuit layout (step  402 ). Next, the system converts the representation into a Boolean expression (step  404 ). The system then performs Boolean operations on the shape by manipulating the Boolean expressions (step  406 ). These manipulations can include determining if a point within the shape is included in the integrated circuit layout. Finally, the system incorporates the shape into the integrated circuit layout (step  408 ). 
     EXAMPLES 
     This example illustrates the process of determining if a point is within a shape on an integrated circuit chip. Referring to FIG. 2F, we start with a shape that includes points 00100, 00110, 01110, 01100, 10110, 11110, 10111, and 11111. These points include two rectangular areas: 00100, 00110, 01110, and 01100; and 10110, 11110, 10111, and 11111. Each of these points can be identified using a string of variables X 1 X 2 X 3 X 4 X 5 . For example, the points of the first area, 00100, 00110, 01110, and 01100, can be described with the Boolean expressions {overscore (X)} 1 {overscore (X)} 2 X 3 {overscore (X)} 4 {overscore (X)} 5  {overscore (X)} 1 {overscore (X)} 2 X 3 X 4 {overscore (X)} 5 , {overscore (X)} 1 X 2 X 3 X 4 {overscore (X)} 5 , and {overscore (X)} 1 X 2 X 3 {overscore (X)} 4 {overscore (X)} 5  respectively. Combining these expressions yields: 
     
       
           {overscore (X)}   1   {overscore (X)}   2   X   3   {overscore (X)}   4   {overscore (X)}   5   +{overscore (X)}   1   {overscore (X)}   2   X   3   X   4   {overscore (X)}   5   +{overscore (X)}   1   X   2   X   3   X   4   {overscore (X)}   5   +{overscore (X)}   1   X   2   X   3   {overscore (X)}   4   {overscore (X)}   5   ={overscore (X)}   1   X   3   {overscore (X)}   5 . 
       
     
     The points of the second area can be described with the Boolean expressions 
     
       
           X   1   {overscore (X)}   2   X   3   X   4   {overscore (X)}   5   , X   1   X   2   X   3   X   4   {overscore (X)}   5   , X   1   {overscore (X)}   2   X   3   X   4   X   5 , and  X   1   X   2   X   3   X   4   X   5 . 
       
     
     Combining these expressions yields: 
     
       
           X   1   {overscore (X)}   2   X   3   X   4   {overscore (X)}   5   +X   1   X   2   X   3   X   4   {overscore (X)}   5   +X   1   {overscore (X)}   2   X   3   X   4   X   5   +X   1   X   2   X   3   X   4   X   5   =X   1   X   3   X   4 . 
       
     
     Combining expressions for the two rectangular areas yields the following function: 
     
       
         ƒ( X )= {overscore (X)}   1   X   3   {overscore (X)}   5   +X   1   X   3   X   4 . 
       
     
     This function can be used to determine if a point lies within the combination of the two areas. For example, applying this function to point 01000, which is outside of the area yields: ƒ(X)=101+000=0. The zero indicates that the point is outside of the area. Applying the function to point 11110, which is inside the area yields: ƒ(X)=011+111=1. The 1 indicates that the point is inside the area. 
     FIG. 5 illustrates an alternate example for determining containment in accordance with an embodiment of the present invention. The rectangle shown is sixteen units wide and eight units high and requires four bits to encode the length and three bits to encode the length. Thus a total of seven bits is needed to encode a point within this rectangle. Specifically, the x-axis (length includes the points 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, and 1000. The y-axis (width) includes the points 000, 001, 011, 010, 110, 111, 101, and 100. 
     In this example, the Gray code for the point is computed in an alternative manner. First, the Gray codes for the x and y coordinates are computed separately. Next, the Gray codes for the x and y coordinates are concatenated to form the Gray code for the point. The point (3, 5) is thus encoded as 0010111, where the first four bits come from the x-axis and the next three bits come from the y-axis. Three in the x-axis is encoded as 0010, while 5 in the y-axis is encoded 111. Concatenating these values yields 0010111. 
     There are two steps to derive the function ƒ. First, assume the corners are fixed; second, enumerate all possible corner points. Let P 1 , . . . , P n  be the variables for the corners and R the region defined by the corner variables. Then ƒ, bounded by the corners C 1 , . . . , C n , is given by ƒ=P 1 ==C 1 ), . . . , (P n ==C n )(P is inside R). 
     The Boolean function for P is inside R is simply the sum of all points inside R. The equivalence relation operator, ==, is the bit-wise exclusive-NOR (XNOR), i.e. it yields 1 if and only if all corresponding bits of the two operands are identical. For instance, P==(3,5) is the Boolean function P XNOR 00100111. 
     Given a rectangle with corners C 1 =(0,0), C 2 =(0,1), C 3 =(2,1), and C 4 =(2,0), in the sixteen by eight domain illustrated in FIG. 5, the points inside of R are (0,0), (1,0), (2,0), (0,1), (1,1), and (2,1). Then ƒ(P1,P2,P3,P4,P)=(P 1 =C 1 ),(P 2 =C 2 )(P 3 =C 3 ),(P 4 ==C 4 ){(P=0,0)+(P=1,0)+(P=2,1)+(P=2,0), where + is the Boolean OR. 
     The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.