Data compaction techniques for generation of a complex image
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is a continuation of application Ser. No. 07/774,535 filed Oct. 8, 1991, now abandoned. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention generally relates to techniques that allow significant compaction of the data used to describe a design which lacks repetition and, more particularly, to an effective data compaction technique for the generation of complex computer images. The invention has particular application in electron beam lithography for the fabrication of complex integrated circuit structures. 
     2. Description of the Prior Art 
     The amount of data required to describe the patterns to be written by an electron beam (e-beam) lithography system for complex integrated circuit (IC) structures such as advanced computer chips, read only storage (ROS), programmable logic arrays (PLAs), and other array structures, is enormous, typically requiring gigabytes (GBs) of data. Generally, the pattern data is not compacted because the patterns lack the repetition needed by step-and-repeat, macro commands and other known compaction methods. This results in excessive data volumes and post processing times for such designs. 
     R. D. Moore and P. M. Ryan in &#34;Personalization of ROS Memories Using an E-Beam System&#34;, IBM Technical Disclosure Bulletin, vol. 20, no. 2., July 1977, pp. 588, 589, describe a method for improving writing speed for a rigidly defined ROS array where the exposure locations and pattern (single spot) and pattern length are fixed and the exposure data is not compacted. 
     U.S. Pat. No. 4,291,231 to Kawashima et al. for &#34;Electron Beam Exposure System and Apparatus for Carrying Out the Same&#34; describes a system using fixed patterns stored in memory to provide repeated exposure of the same pattern sequence at various locations. The pattern consists of the same sequence of pattern elements repeated over and over. It does not allow individual selection of pattern elements. 
     U.S. Pat. No. 4,259,724 to Sugiyama, like the patent to Kawashima et al., allows step and repeat exposures of a pattern segment (i.e., a fixed string of shapes) with an elementary repetitive pattern in a rectangular area which may consist of a number of fractional patterns. 
     U.S. Pat. No. 4,531,191 to Koyama provides for monitoring of the input data string to detect repeated data sequences and generates a repeat count used during actual exposure. In the Koyama system, repeated sequences must occur in succession. 
     U.S. Pat. No. 4,051,457 to Inose et al. discloses a system which increases the speed by which codes for Chinese characters are interpreted and the address for the string of shapes needed to write the character is obtained. 
     None of the foregoing patents disclose a system that would allow variations of the basic pattern at each exposure location; that is, they do not allow for selective exposure of shapes within a string. 
     SUMMARY OF THE INVENTION 
     It is therefore a general object of the present invention to provide a method of compacting the data required to generate complex images by a computer. 
     It is another, more specific object of the invention to provide a technique for the compaction of patterns in the manufacture of advanced computer chips despite the fact that the overall designs lack repetition because of personalization of the chips. 
     According to the invention, a pattern is segmented into numerous blocks with each block including an identical grid pattern of predetermined potential shapes for specific locations within each block. The blocks do not have to be uniform and can be of different sizes and shapes. The shapes within a block do not have to fit into different areas and can overlap. There can be a number of different selectable alternatives for an area in the block which are mutually exclusive, and there can be several differently shaped shapes which can go at the same x,y coordinates for different applications or functions. 
     Each of the set of shapes, which fits into a different area of the grid pattern of a given block, is stored in memory and each is given a sequence number. Each of the shapes with that sequence number is placed at a predetermined location in the grid pattern for a given block. Each shape for that predetermined location is different, but it can be of the same dimensions as a pattern for other locations within the block. The shapes are adapted in terms of their ratio of length to width and scale to contribute a particular shape to a predetermined location in a grid pattern. In that way, each shape, when present, adds a different feature to its area of the grid pattern. 
     One or more standard building blocks is selected for the design to be encoded. Each shape in a block is given a sequence number for use in a data word for the building block. The set of shape descriptors for each block is stored in a reference memory. The data word referencing a block includes a number of bytes which specify the stored shape data for the block, and data words encode which shapes in the pattern are to be included or excluded. Each shape is assigned a bit according to its sequence number. For a given shape, if it is to be included, it is a binary &#34;1&#34;, and if it is to be excluded, it is a binary &#34;0&#34;. Each standard shape to fit into a block has a set of parameters which are stored in memory. They include the Δx n  and Δy n  offsets from a reference location x,y plus the width w n  and height h n , where n equals the sequence number of the shape. Patterns can be placed in any sequence at random, making it possible to provide a large number of patterns with far less processing of data. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which: 
     FIG. 1 is a block diagram of the electron beam exposure system according to a preferred embodiment of the invention; 
     FIG. 2A is a block diagram showing the addressing of the reference memory, which is a modification to the existing pattern control section shown in FIG. 1, according to a preferred implementation of the invention; 
     FIG. 2B is a block diagram showing the data structure of a typical shape descriptor; 
     FIG. 3 is a block and logic diagram showing the memory access scheme linking the reference memory to the pattern buffer, which again is a modification to the existing pattern control section shown in FIG. 1, according to a preferred implementation of the invention; 
     FIG. 4A is a plan view showing a portion of a personalized ROS array; 
     FIG. 4B is a diagram illustrating one possible maximum shape configuration for patterning the ROS array of FIG. 4, with individual shapes numbered with shape numbers; 
     FIG. 5A is a diagram showing the format of the control word used in the practice of the invention; 
     FIG. 5B is a diagram showing the format of the control bits of the control word labeled to show which shapes are used; 
     FIG. 6A is a circuit diagram showing a first typical logic circuit; 
     FIG. 6B is a circuit diagram showing a second typical logic circuit; 
     FIG. 7 is a plan view showing a maximum pattern set used to fabricate the circuits of FIGS. 6A and 6B; 
     FIG. 8 shows the control bits for constructing the circuits of FIGS. 6A and 6B using the pattern set shown in FIG. 7; 
     FIG. 9 is a plan view, similar to FIG. 7, showing a variation of the basic pattern numbering method shown in FIG. 7 whereby sets of shapes that are always used together are identified with the same sequence number; and 
     FIG. 10 shows the control bits for constructing the circuits of FIGS. 6A and 6B using the pattern set shown in FIG. 9. 
    
    
     DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT OF THE INVENTION 
     Referring now to the drawings, and more particularly to FIG. 1, there is shown an e-beam system of the type in which a preferred embodiment of the invention is implemented. An x-y work table 8 is moved beneath an electron beam B. The work table 8 carries a target 7, which is typically a semiconductor substrate. An electron beam exposure system is indicated generally by the phantom line 10. An electron beam source 11 produces a beam B which is shaped into various spot shapes and blanked by the deflection and aperture apparatus 12, under the control of spot shaping apparatus, both located in spot shaping, blanking analog electronics unit 14 according to Michail et al. in U.S. Pat. No. 3,900,736. The positioned and shaped spot is controlled, in part, by unit 14 under the control of digital electronics in pattern control section 15. This determines the pattern written in the sub-field under the control of the control computer 16, again according to Michail et al., supra. 
     Pattern control section 15 supplies signals on line 64 to spot shaping, blanking and analog electronics unit 14, on line 65 to shape deflection apparatus 33 and on line 66 to deflection system 19, to control beam position, spot shaping and beam on/off control in a well-known manner. The beam is shaped by the deflection and aperture apparatus 12, positioned over short distances by deflection plates 13 and positioned over longer ranges by deflection coils 17. 
     The next field is positioned orthogonally with respect to the direction of motion of the x-y drive work table 8 which supports the substrate 7, under control of the stage position measurement system 21. All operations are under direction of the control computer 16. The writing of patterns is temporarily stopped after writing at a chip position on substrate 7 has been completed, and a reregistration cycle on substrate 7 is initiated. The beam B is deflected to the nominal location of four registration marks for the next field on substrate 7, and four areas are scanned by the electron beam. The actual positions of the registration marks are determined by detection of backscattered electrons which strike detectors 22. The signals from detectors 22 are fed on lines 27 and 28 to registration detection circuits 23 to determine the actual next field position which provides a signal on lines 60 and 61 to pattern control section 15, and on lines 60 and 62 to the control computer 16. The designed chip position is supplied from control computer 16 on line 63 to the pattern control section 15. In pattern control section 15, the values on lines 63 and 61, i.e., the designed field position and the actual position, are compared, and corrections are applied on line 65 to the vector deflection apparatus 33. The registration cycle is alternated with writing cycles until the final chip location is exposed. 
     The x-axis work table positioning is controlled by an x position signal included in an x/y position signal on line 24 from control computer 16 to stage position measurement system 21. The signal on line 24 is predetermined by wafer specifications stored in the form of position control data in control computer 16 as modified by current registration signals received via lines 60 and 62 from registration detection circuits 23. The actual x position of work table 8 is determined by stage position measurement system 21, and that value is compared to the desired x position signal on line 24 from control computer 16. A resulting position error signal on line 25 is applied to a servo apparatus in the x stage drive mechanism 26 which applies a drive signal to motor 67. The y-axis work table positioning is similarly controlled by a servo apparatus in the Y stage drive mechanism 35 which responds to a signal on line 34 from the stage position measurement system 21. 
     The addressing of the reference memory which is part of the pattern control section 15 is illustrated in FIG. 2, to which reference is now made. The reference memory 70 can be part of the main pattern buffer in pattern control section 15 or a separate unit. The block specifier 71 may typically be 64-bits and comprises an operation code (op code) field 72, an address field 73, an x position field 74, a y position field 75, and a number of control bits 76. The control bits 76 correspond to the sequence numbers of the pattern shapes in a maximum shape configuration, as will become clear from the following description. 
     The address field 73 of the block specifier 71 is used to enter the reference memory 70. The data structure of the shape descriptions. 80 in the reference memory 70 is shown in FIG. 2A and comprises the Δx n  and Δy n  offsets from the reference location x,y of block specifier 71 plus the width w n  and height h n , where n equals the sequence number of the shape, and the exposure dose for the shape D. When the common shapes, denoted C in the first two entries of the reference memory 70, have all been used, the control bits 76 in the block specifier 71 dictate which of the sixteen possible shapes in the block of shapes addressed in the reference memory 70 are to be used. When a binary &#34;1&#34; is encountered in the string of control bits 76, the shape descriptor at an offset corresponding to the position of the bit in the control field is used. FIG. 2 shows the example for bit position three corresponding to a shape sequence number 3. 
     The shape descriptor 80 contains all the data necessary to identify (common or sequence number), place, size, and expose (dose) the shape. The op code in field 81 determines whether it is a common shape or a selectable shape. The op code 72 in the main pattern buffer determines whether that word is a block specifier for compacted data or some other type of tool control or uncompacted pattern data. 
     FIG. 3 shows how the reference memory 70 and the pattern buffer 90 are linked in the data flow of the pattern control section. In practice, the reference memory 70 can be part of the pattern buffer 90 set aside, possibly dynamically, for storage of shape descriptors of the compacted part of the overall pattern. The op code in each word of the pattern buffer 90 tells what type of data word it is. Addresses from block specifiers 71 (FIG. 2) are routed to the reference memory 70 to address shape descriptors, while block position data from the x and y fields of the block specifier in the pattern buffer are sent to the deflection system 19 (FIG. 1). Only shape descriptor data goes to the shape deflection apparatus 33. The adder 92 is used to calculate the final address for the shape. The shape data for compacted shapes comes from memory 70, while memory 90 supplies data for uncompacted shapes. 
     FIG. 4 shows a portion of a ROS array fabricated on an IC chip. The ROS array in FIG. 4 is shown divided into a plurality of regions or blocks, which are numbered according to the numerals along the x and y axes. So, for example, the block in the lower left corner of the array is identified as block (1,1). The ROS array illustrated has been personalized for a particular application, and while there is some repetition of shapes in this example, in general there is no significant pattern of shapes that would lead to a meaningful compaction of data using conventional techniques. FIG. 4A shows one of the possible maximum shape configurations that could be used to construct each of the regions into which the ROS array portion shown in FIG. 4 has been divided. Block (1,1) in FIG. 4 has been labeled to show the subset of the shape numbers from 1 to 16 for the particular maximum shape configuration that would be required to properly expose that particular region of the ROS array. The shape numbers correspond to a sequence of control bits 76 in the block specifier 71 shown in FIG. 2. Although none of the other regions may require the same subset of shapes, the entire ROS array can be generated from the shapes in the maximum shape configuration shown in FIG. 4A by setting the control bit sequence according to which shapes of the maximum shape configuration are to be exposed and which are not to be exposed. 
     FIG. 5A illustrates a possible format for the control word 71 that would appear in the main pattern data stream with a block specifier op code to activate this compaction feature in order to expose the particular area of the ROS array being patterned. The address field points to the shape specifier memory area 70 shown in FIG. 2A that consists of an op code field 81, x and y offset fields 82 and 83, width and height fields 84 and 85, and an exposure dose field 86. The op code causes the pattern control section 15 (FIG. 1) to recognize the occurrence of the use of compacted data and an address pointing to the shape data (i.e., descriptors) residing in the reference memory 70. The x and y values establish the reference position of the block of shape descriptors in the writable area. The control bits, as defined by FIG. 5B, determine which of the shapes (i.e., 1 through 16 in FIG. 2) in the maximum shape configuration will actually be exposed. If the control bit for a given shape is a &#34;1&#34;, the shape is positioned at the location (x+Δx, y+ Δy) and the area defined by its width, w, and its height, h, is exposed. A binary &#34;1&#34; indicates the shape will be written, while a binary &#34;0&#34; indicates that the shape will not be written; that is, it will be skipped. Different control bit sequences in successive control words cause different patterns to be exposed in successive regions of the ROS array. 
     The lack of a significant repetitive pattern of shapes is even greater when logic circuits are to be fabricated, as shown in FIGS. 6A and 6B. FIG. 6A shows a simple common base NPN bipolar transistor circuit having an input, I 3 , connected to the emitter and an output, O 1 , connected to the collector, with the collector biased to a supply voltage, Vcc. FIG. 6B shows a multiple emitter NPN bipolar transistor connected in a common base circuit. This circuit has three inputs, I 1 , I 2  and I 3 , each connected to a separate emitter, and an output, O 1  &#39;, connected to the collector 
     FIG. 7 shows the shape patterns which may be used to fabricate the circuits shown in FIGS. 6A or 6B. FIG. 8 shows the control bits for fabricating the circuits, identified as CKT 1 and CKT 2, respectively shown in FIGS. 6A and 6B. Note, for example, only shape 14 is omitted in constructing the circuit of FIG. 6B, whereas shapes 1, 2, 4, 5, 7, 8, 15, and 16 are omitted in constructing the circuit of FIG. 6A. Very often different logic circuits will have mutually exclusive overlapped sets of shapes from which a selection is made when the actual circuit is being constructed. Here, the location of outputs O 1  and O 1  &#39; are different, and the shapes used to generate them (i.e., shapes 14, 15 and 16) are mutually exclusive. 
     The maximum compaction factor is related to the size of the maximum shape configuration for use, not the size of the array being exposed. This is because the maximum shape configuration replaces the data needed to describe the group of shapes with a reference and a data word describing which shapes will actually be exposed. The maximum shape configuration can describe a horizontal, vertical or rectangular portion of an array to be fabricated. 
     Further compaction can be achieved if the data word only contains bits for the shapes with variable use, with the fixed shapes always used. Alternatively, the data word could be partitioned to provide a count of the fixed shapes and bits for the variable shapes. Another variation would be to label sets of shapes with a common sequence number, as shown in FIG. 9. Combinations of sequences of shapes would define the pattern ultimately exposed. For the approach taken in FIG. 9, only eight control bits are required rather than the sixteen used in the example shown in FIG. 7. The control bits for the logic circuits shown in FIG. 6A and 6B are shown in FIG. 10. 
     While the invention has been described in terms of a single preferred embodiment, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims. For example, the invention is useful for any pattern generator, including lasers, ion beam systems and light tables and is not limited to e-beam systems.