2.1.

Overview

Circuit layouts are typically stored in GDSII (Ref. 5) or OASIS (Ref. 6) formats. GDSII and OASIS represent circuit features such as polygons and lines, and describe them by their corner points.^{5, 7} GDSII and OASIS formatted data are far more compact than the uncompressed image of a circuit layer. Therefore it may initially appear that the GDSII and OASIS formats are good candidates for this particular application. However, this is not the case because maskless writers operate directly on pixel bit streams and GDSII and OASIS layout representations must be converted into layout images before the lithography process begins. In general, this conversion requires 1. eliminating hierarchical structures by replacing all of the copied parts with actual features, 2. arranging the circuit features such as polygons and lines into the corresponding layers of the circuit, and 3. rasterizing (see Fig. 3). As the conversion usually takes hours using a complex computer system with large memory, it cannot be performed within the decoder chip.

Fig. 3

Preparing layout images from a circuit layout—rasterizing process.

Our compression algorithm is inspired by the compactness of the GDSII/OASIS format and is designed to take advantage of ideas such as corner representation and the copying of repeated structures. However, we avoid the complex flattening and rasterizing processes and offer a simple decoding process. We assume throughout that all of the circuit layer images are binary images.

Optical proximity correction (OPC), which is widely used for conventional lithography systems to adjust the shapes of mask features, is not in general necessary for maskless lithography when the application is the direct fabrication of real circuits. OPC is conventionally used to compensate for the image errors due to the diffraction effect,⁸ which is not an issue for maskless lithography using electron beams. The only exception is when maskless lithography is used to make precise masks for the fabrication of circuits via photolithography. Since mask making is not a high volume application, we are more interested in the direct fabrication of real circuits, which is the only problem we consider. In this setting we need not worry about OPC.

We instead consider electron beam proximity correction for maskless lithography systems to obtain good quality line edge roughness. This is achieved by applying a multilevel electron beam dosage to each pixel.⁹ As shown in Figs. 4a and 4b, uniform electron beam doses result in blurry boundary edges because of the electron beam proximity effect. To compensate for that phenomenon, a higher electron beam dosage was applied to the boundary pixels as in Fig. 4c and the proximity effect has been corrected as in Fig. 4d.

It is possible to represent the proximity corrected layout image using gray images.⁹ However, this data eventually has to be reinterpreted as a binary image because the lithography writer does not produce a multilevel electron beam dose during a single write time. Instead, the lithography writer utilizes an electron beam writer to write the corresponding pixel multiple times so that the pixel is exposed with the targeted electron beam dosage; i.e., each electron beam writer uses a proximity-corrected layout image to write a portion of a gray image pixel which corresponds to a block of binary pixels. Our paper considers the “idealized pixel printing model” as in Ref. 3; however, it can be applied to general proximity correction methods by reinterpreting the proximity corrected gray image as a binary image.

Fig. 4

Proximity correction using gray tone exposure (Ref. 9).

Under the idealized pixel printing model, we generated the gray images by the following process as in Ref. 3. First, we start with the GDSII or OASIS layout. Second, as illustrated in Fig. 3, we rasterize the layout image in a 1 nm grid and output a large binary image. Third, this binary image is segmented in blocks and quantized with the appropriate gray level. For example, if we are targeting a 45 nm process technology, the electron beam pixel size chosen would be 22 nm (half the minimum feature size) and a block of 22 × 22 binary pixels would make up a single gray pixel. To obtain a 1 nm edge placement Dai³ suggested counting the number of fills in every 22 × 22 pixel block and quantizing that number to one among 32 levels.

The generated gray image is then reinterpreted as a binary image so that it directly maps to the lithography writer control signal, by changing the grid size. For the previous example, we want a 22 nm pixel to have a 1-nm edge replacement. That means, we need at least 22 dose levels.¹1 Therefore, instead of 32 levels we can choose a quantization of 25 (=5×5) levels. Since every electron beam dose will increase a single level, each 22 nm pixel is written 25 times or, equivalently, that each control signal covers a 4.4 nm (=22/5) pixel size. For simplicity, we can recompute the numbers so that each control signal covers a 4 nm (=22/5.5) pixel size and is one among 30 levels (≈5.5×5.5) for each 22 nm pixel. Finally, this new binary representation can be obtained by rasterizing the layout GDSII or OASIS file to the targeted grid (4 nm for example).

A simple illustration of this binary image to gray image and gray image to binary conversion is shown in Fig. 5. Here the grid size of the gray image is set to 4 nm and the grid size of the binary image is set to 2 nm. Fig. 5a shows the binary rasterized image at a grid size of 1 nm. By grouping 4×4 blocks of this image as a pixel and quantizing the number of fills to 4 levels (2 bits), we obtain Fig. 5b, which corresponds to the gray image at a grid size of 4 nm. Because each gray image pixel has 4 levels, we could interpret this as a 4 nm pixel written 4 times. Here a 4 nm gray pixel corresponds to a 2×2 block of binary pixels from a 2 nm binary grid as in Fig. 5c. Observe that Fig. 5c is not generated from Fig. 5b but could be generated from Fig. 5a by forming the appropriate 2×2 blocks.

Fig. 5

Binary image versus gray image.

Finally, an overview of the compression algorithm is shown in Fig. 6.²¹ We begin by seeking frequently occurring patterns. This part roughly matches the patterns that are frequent to improve the compression performance without increasing the encoding complexity. We next transform the remaining image into corner images. We then apply run length encoding (RLE)¹⁰ and end-of-block (EOB) coding to further compress the transformed image. We finally compress the resulting data stream with arithmetic coding.¹¹

Fig. 6

Compression process overview (Ref. 21).

In Secs. 2B, 2C, we will first describe how the frequent pattern replacement and corner transform processes work as separate processes. In Sec. 2D, we will illustrate how we should tweak them to work in a unified system, and in Sec. 2E we will describe the final entropy coding process.

2.2.

Frequent Pattern Replacement

GDSII/OASIS formats are designed to take advantage of the hierarchical structure presented within circuit layouts. In particular, if a substructure is repeatedly used in a circuit layout, GDSII/OASIS identifies it and then refers to it whenever the substructure occurs. For example, the GDSII/OASIS representation for an 8-bit adder, which is implemented using two 4-bit adders, will consist of a definition of a 4-bit adder and the description of the 8-bit adder in terms of two 4-bit adders as in Fig. 7.

Fig. 7

8-bit adder using two 4-bit adders: GDSII definition (solid line boxes) and references (shaded boxes).

By searching the GDSII/OASIS file and counting the number of references for each definition, we obtain a list of frequent patterns in the mask image. We could alternatively run a complex pattern matching algorithm to detect the frequent patterns, but the outcome would not be significantly different due to the blockwise design of typical circuits. Our approach is not efficient for compression purposes if the input GDSII/OASIS file is unstructured, but this issue can be handled by a preprocessing algorithm proposed by Gu and Zakhor¹² which efficiently restructures input GDSII/OASIS files.

Figure 8 offers an overview of frequent pattern replacement. The input to the procedure is the GDSII/OASIS file and the layer number of the layout image. The first step is to detect all of the substructures that are defined in the GDSII/OASIS representation. The next step is to count the number of references of each substructure extracted in the previous step. We proceed to order the substructures by the number of their occurrences and select the most frequent P of them, where P is chosen so that the representation of the P substructures requires less than P _SIZE bytes of memory. Note that we are not fixing the number P, but P _SIZE, the memory that is required to store the P patterns. Also, note that because of the decoder memory constraint, P _SIZE is very small, and hence, we can only pick a small number of patterns. Each of the P substructures undergoes the rasterizing process.²2 During the rasterizing process, we increase both the pattern width and height by 1, so that the pattern has an empty top row and an empty leftmost column as in Fig. 8. The reason why we are adding this empty boundary will be explained in Sec. 2D. Finally, given the binary layout image the encoder seeks the P patterns within the image. Whenever one of the patterns is matched within the search region, the encoder will replace the top left part of the corresponding part of the image with a string described below and will replace the rest of the filled pixels that have been matched with “0”s (or empty). Note that since the GDSII/OASIS format allows rotated/flipped copies of a substructure, the encoder needs to check all possible rotations/flips during the pattern matching process, and return an encoding accordingly.

In order to restrict the decoder memory, the inside pattern (which excludes the surrounding empty row and column) is encoded using the following symbol string format:

Suppose the pattern p dimension is w _p  ×  h _p . Then, in order to make this encoded stream fit in the top row of the image, we assume the original image size [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {min}(w_p, h_p)$\end{document} $\mathtt{min}(w_p,h_p)$ is no shorter than [TeX:] \documentclass[12pt]{minimal}\begin{document}$\lceil {\rm log}_2(P) \rceil + 2 \cdot \texttt {is\,(Rotation)} + \texttt {is\,(Flip)}\break + \lceil \texttt {max} [ {\rm log}_2 (w_p-q_{w_p}), {\rm log}_2 (h_p-q_{h_p})] \rceil$\end{document} $\lceil {\log }_2\left(P\right)\rceil +2·\mathtt{is}\left(\mathtt{Rotation}\right)+\mathtt{is}\left(\mathtt{Flip}\right)+\lceil \mathtt{max}[{\log }_2(w_p-q_{w_p}),{\log }_2(h_p-q_{h_p})]\rceil$ where [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {is(x)}$\end{document} $\mathtt{is}\left(\mathtt{x}\right)$ is 1 if [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {\it x}$\end{document} $\mathit{x}$ is permitted and 0 otherwise, and [TeX:] \documentclass[12pt]{minimal}\begin{document}$q_{w_p}$\end{document} $q_{w_p}$ (or [TeX:] \documentclass[12pt]{minimal}\begin{document}$q_{h_p}$\end{document} $q_{h_p}$ ) is one more than the number of empty rightmost columns (or the bottom columns) of the pattern. The final term [TeX:] \documentclass[12pt]{minimal}\begin{document}$\lceil \texttt {max} [ {\rm log}_2 (w_p-q_{w_p}), {\rm log}_2 (h_p-q_{h_p})] \rceil$\end{document} $\lceil \mathtt{max}[{\log }_2(w_p-q_{w_p}),{\log }_2(h_p-q_{h_p})]\rceil$ is added because of the decoder memory restriction which will be explained in Sec. 3B.

In Fig. 8, we illustrate an example where P = 1 and the rasterized layer image of the frequent substructure is a 3×3 square. Since the layout image contains two copies of this pattern without the possibility of a rotation or a flip, the encoder outputs $ (depicted by one “gray” pixel) for the pixel corresponding to the top-left corner of each 3×3 square pattern in the input layout image and “white” pixels for the remaining 8 pixels. For this pattern, [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {min}(w_p,h_p)=3$\end{document} $\mathtt{min}(w_p,h_p)=3$ and is greater than [TeX:] \documentclass[12pt]{minimal}\begin{document}$\lceil {\rm log}_2 1 \rceil + 2 \cdot 0 + 0\break + \lceil \texttt {max} [ {\rm log}_2 (3-1), {\rm log}_2 (3-1)] \rceil = 1$\end{document} $\lceil {\log }_{2}1\rceil +2·0+0+\lceil \mathtt{max}[{\log }_2(3-1),{\log }_2(3-1)]\rceil =1$ .

During the generation of binary layout images an image could be truncated if there is a mismatch between the pixel grid and the GDSII grid. As a result, a pattern could be truncated when it is realized as a binary image; i.e., a substructure could be repeated within the GDSII/OASIS domain but the corresponding pattern may not repeat within the binary image domain. Despite this issue, the experimental results indicate that this approach to pattern extraction yields improvements in compression and encoding time over prior algorithms for this problem. To understand why this is the case, observe that the patterns we extract have a limited size and so the mismatch between the two domains is less likely to occur.

The parts of the layout image that have not been matched during the frequent pattern replacement process are handled by the corner transformation step which we will discuss in Sec. 2C.

2.3.

Corner Transformation

In the GDSII/OASIS representation of a structurally flattened single layer, the layout polygons are represented in terms of their corner points. While this representation is efficient for a system in which decoder memory is large, it is infeasible when the decoder memory is restricted because the decoder needs to access a memory block of size (| x ₁ − x ₂| + 1) × (| y ₁ − y ₂| + 1) for the encoder to connect an arbitrary pair of points ( x ₁, y ₁) and ( x ₂, y ₂) as in Fig. 9.

Fig. 9

Required decoder memory (shaded region) to reconstruct a line (dashed line) from ( x ₁, y ₁) to ( x ₂, y ₂).

However, if the angle of a contour line is constrained to a small set then there can be considerable simplification in the rasterizing process. In our previous research,¹³ we restricted the contour lines to be either horizontal or vertical and decomposed an arbitrary polygon into a number of Manhattan polygons, i.e., polygons with right angle corners. This decomposition is well-suited to this application because most components of circuit layouts are produced using CAD tools which design the circuit in a rectilinear space, and even the non-Manhattan parts can be easily described by Manhattan components.

If the contour lines are constrained to be either horizontal or vertical and the decoder scans the image in raster order, i.e., each row in order from left to right, then when the decoder encounters a corner it only needs to decide whether it should reconstruct a horizontal and/or a vertical line. The raster order implies that a corner is either the beginning of a line going to the right and/or down or the end of a line. In our previous research,¹³ we specified this decoding decision by representing each pixel with five possible symbols — ‘not corner,’ “right,” “right and “down,” “down,” and “stop.” However, as we will see, this five-symbol representation can be further simplified.

To motivate the simplified transformation, observe that a row (or a column) of the original layout image consists of alternating runs of 1's (fill) and runs of 0's (empty). We encode the pixels where there are transitions from 0 to 1 (or 1 to 0) using symbol “1” and encode the other places using symbol “0.” Since most polygons are Manhattan, after applying this encoding in the horizontal direction we obtain alternating runs of 1's and 0's in the vertical direction as seen in Fig. 10b. Therefore, we can re-apply this encoding in the other direction to produce the final corner image. We call this encoding scheme the binary corner transformation because the final encoded image is binary and the location of the 1-pixels indicate the corners of the polygons. In order to illustrate how the transform is applied, we will first discuss a two-step transformation process and then introduce a one-step transformation process which requires less memory during the encoding process and runs faster than the two-step transformation process.

The two-step transformation process consists of a horizontal encoding step and a vertical encoding step. In the horizontal encoding step, we process each row from left to right. For each row, the encoder initializes the previous pixel value to 0 (not filled). If the value of the current pixel differs from the previous one we encode it with a 1 and otherwise with a 0. After the horizontal encoding is completed, we use the intermediate encoded result as input to the vertical encoding process. This is identical to the horizontal encoding process except that instead of processing rows we process each column from top to bottom.

Fig. 10

Two-symbol corner transformation.

Algorithm 1

Transformation : Two-Step Algorithm

Algorithm 2

Transformation : One-Step Algorithm

The algorithm is summarized in Algorithm 1. In the algorithm, x is the column index [1, ⋅⋅⋅, C] of the image and y is the row index of the image [1, ⋅⋅⋅, R].

As we can see from Line 13 of the algorithm, [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {OUT}(x,y)=1$\end{document} $\mathtt{OUT}(x,y)=1$ only if [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {TEMP}(x,y) \ne \texttt {TEMP}(x,y-1)$\end{document} $\mathtt{TEMP}(x,y)\ne \mathtt{TEMP}(x,y-1)$ . That is, [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {OUT}(x,y)=1$\end{document} $\mathtt{OUT}(x,y)=1$ only if [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {TEMP}(x,y)=1$\end{document} $\mathtt{TEMP}(x,y)=1$ and [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {TEMP}(x,y\break -1)=0$\end{document} $\mathtt{TEMP}(x,y-1)=0$ , or if [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {TEMP}(x,y)=0$\end{document} $\mathtt{TEMP}(x,y)=0$ and [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {TEMP}(x,y -1)=1$\end{document} $\mathtt{TEMP}(x,y-1)=1$ . Since [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {TEMP}(x,y)=1$\end{document} $\mathtt{TEMP}(x,y)=1$ only if [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {IN}(x-1,y) \ne \texttt {IN}(x,y)$\end{document} $\mathtt{IN}(x-1,y)\ne \mathtt{IN}(x,y)$ as in Line 5, we can simplify the corner transform process as in Algorithm 2.

The preceding algorithm bypasses the need for intermediate memory. Here pixel ( x, y) is processed as a function of the input pixels ( x − 1, y), ( x, y − 1) and ( x − 1, y − 1). This simplification results in a much faster running time. Finally, note that the transformation can handle layout images with width-1 lines as shown in Fig. 11.

Fig. 11

Handling width-1 lines.

2.4.

Frequent Pattern Replacement + Corner Transformation

In Secs. 2B, 2C, we separated the discussion of frequent pattern replacement and corner transformation. Since the output of frequent pattern replacement is a ternary image, a modification is needed to the corner transformation. Figure 12 illustrates the tweaking of the frequent pattern replacement and the corner transformation processes when P = 1. The frequent pattern replacement process now outputs two images, namely the matched pattern image and the residue image produced by removing the matched patterns from the original layout image. In this decomposition the pattern embeddings are compressed by the frequent pattern replacement and the residue image is compressed by the corner transformation.

Fig. 12

Handling frequent pattern replacement and corner transformation in a unified system.

Note that the filled pixels in our “corner” image are more closely related to transitions than to actual corners in the original layout image. Therefore, filled pixels in the corner image can appear to the right, down, or right-down of the corresponding actual corner in the layout image and can hence overwrite the frequent pattern stream if the frequent pattern does not contain an empty top row or an empty left column. Because we added an empty row and column to the frequent patterns, we can add the matched pattern image and the corner image to form the transformed image without any distortion.

Figure 12 illustrates the combination of the frequent pattern replacement and the corner transformation processes. The frequent pattern replacement process now outputs two images, the matched pattern image and the residue image produced by removing the matched patterns from the original layout image. In this decomposition, the pattern embeddings are represented by the frequent pattern replacement process and the residue image is represented by the corner transformation. The outputs of the two processes are summed to obtain the transformed image. Observe that two nonzero symbols are never summed, and so the summation is well-defined and the transformed image is over the alphabet {0, 1, $}.

We next describe an entropy coding scheme to compress the transformed image.

2.5.

Entropy Coding

We expect the transformed image to contain long runs of zeroes, and it is therefore effective to use a type of run length encoding (RLE)¹⁰ for compression. The nonzero pixels of the transformed image are written as they are, but each run of zeroes is represented by its run length which we encode with an M-ary representation. More specifically, we introduce new symbols “2,” “3,” ⋅⋅⋅, “M+1” to represent the base- M symbols “0 _M ,” “1 _M ,” ⋅⋅⋅, “( M − 1) _M .” For example, if the transformed stream was “1 00000 00000 1 00000 0000 1 00000 00000 000” and M = 3, then the encoding of the stream is “1 323 1 322 1 333” because the run length are 10 (= 101 ₃), 9 (= 100 ₃), and 13 (= 111 ₃), and 2/3/4 is used to represent 0 ₃/1 ₃/2 ₃.

These M symbols are to be encoded using arithmetic coding¹¹ for further compression. For arithmetic decoding, we need to allocate memory for each symbol, and hence, in our restricted decoder memory setting, we want to choose M as small as possible. However, small M is not desirable since there are very long runs of zeroes. These long runs of zeroes occur frequently if the circuit features are aligned in a grid manner.

Therefore, in order to obtain a high compression ratio while restricting the size of the decoder memory, we segment each line into k blocks of length L, and we introduce a new “EOB (end-of-block)” symbol “X.” If a run of zeroes ends after a block, instead of representing the run length using an M-ary representation, we use the end-of-block symbol X. Hence, we encode a line of zeroes with k X's instead of roughly log _M ( kL) symbols. Continuing the previous example, if M = 2, k = 5, and L = 7, then the transformed stream “1000000 0000100 0000000 1000000 0000000” is represented as “1X 3221X X 1X X,” where 2/3 (= 0 ₂/1 ₂) is used for the binary representations of runs of zeroes.

After applying EOB coding, there tends to be long runs of “X”s in the encoded stream. Therefore, we can apply run length encoding to this stream by reusing the M symbols for the initial runs of zeroes and introducing N new symbols for an N-ary representation of runs of “X”s . Persisting with the previous example, if M = N = 2, k = 5, and L = 7, then the next representation is the string “1 5 3221 45 1 45,” where 2/3 (or 4/5) is used for the binary representation of runs of zeroes (or “X”s).

Our last encoding step compresses the preceding stream with the implementation of arithmetic coding provided by Witten ¹⁴ The decoder requires four bytes per alphabet symbol, and since we used M+ N+3 symbols, 4( M + N + 3) bytes were used for arithmetic decoding. Note that M symbols are used for runs of zeroes, N symbols are used for runs of “X”s, 0/1 is used for the corner pixel, $ is used to handle the frequent P patterns.

3.1.

Corner Transformation

The corner transformation uses pixels from the previous row and column to decode the current pixel. Because the decoding process depends on the previous row, we designed the decoder to decode the corner image in a row-by-row manner instead of in its entirety in order for this process to be compatible with the restricted memory available to a maskless writer. In our transform decoder we use a row buffer ( [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {BUFF}$\end{document} $\mathtt{BUFF}$ ). The buffer is used to store the status of the previous (decoded) row. It uses two symbols, 0 and 1, to represent its status, and hence, the buffer requires width bits of memory. “0” means “no transition” while “1” means “transition” which indicates the starting/ending point of a vertical line. Using the current row of the corner image and the buffer, we can reconstruct the layer image as in Algorithm 3. Note that the [TeX:] \documentclass[12pt]{minimal}\begin{document}$\bigoplus$\end{document} $⨁$ operation is a binary [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {XOR}$\end{document} $\mathtt{XOR}$ operation, and is only applied to binary summands.

Algorithm 3

Inverse Transformation

Lines 4 to 8 process the buffer. If the buffer is filled, i.e., if there is a vertical fill, then the corresponding pixel is filled. Line 9 initializes the status of the horizontal fill. Lines 10 to 16 process each column of the corner image from left to right. If the pixel is 1, the decoder makes horizontal/vertical changes to the image. We first have to update the horizontal fill status (Line 12), fill the output pixel if necessary (Line 14), and update the buffer if necessary (Line 15). If the pixel is 0, the decoder makes no horizontal/vertical changes to the image, but fills the output pixels and updates the buffer according to the fill status. For example, if the decoder was previously filling the horizontal line, it keeps filling the line (Line 14) and updates the buffer (Line 15) in order to process the next row.

3.2.

Pattern Reconstruction

If the decoder finds string $, it starts the pattern reconstruction process. Depending on the number P of patterns, the decoder reads ⌈log ₂( P)⌉ pixels to determine which pattern p is used. If the pattern p is allowed to be rotated, then the decoder next reads another two pixels to determine its rotation. Similarly, if the pattern p is allowed to be flipped, then the decoder reads the next pixel to determine whether p is flipped or not. Hence, the [$ PPP RR F] stream specifies the pattern to reconstruct.

In order to perform row-wise decoding of these patterns, we use a row buffer ( [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {BUFF}$\end{document} $\mathtt{BUFF}$ ). When the decoder finds the pattern string [$ PPP RR F], it places that string into the corresponding buffer location to specify what pattern should be reconstructed. Furthermore, in order to specify which row of the pattern p the decoder should next process the decoder adds a [TeX:] \documentclass[12pt]{minimal}\begin{document}$\lceil {\rm log}_2 (h_p-q_{h_p}) \rceil$\end{document} $\lceil {\log }_2(h_p-q_{h_p})\rceil$ bit binary representation of the next row number after the pattern string, where [TeX:] \documentclass[12pt]{minimal}\begin{document}$q_{h_p}$\end{document} $q_{h_p}$ is one more than the number of empty rows on the bottom of the pattern. Observe that if the bottom r rows of the pattern p are empty, then the decoder needs to reconstruct h _p − ( r + 1) more rows. Recall that the shorter dimension of the pattern p, [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {min}(w_p, h_p)$\end{document} $\mathtt{min}(w_p,h_p)$ , may be no less than [TeX:] \documentclass[12pt]{minimal}\begin{document}$2 + \lceil {\rm log}_2(P) \rceil + 2 \cdot \texttt {is(Rotation)}\break + \texttt {is(Flip)} + \lceil \texttt {max} \left[ {\rm log}_2 (w_p-q_{w_p}), {\rm log}_2 (h_p-q_{h_p}) \right] \rceil$\end{document} $2+\lceil {\log }_2\left(P\right)\rceil +2·\mathtt{is}\left(\mathtt{Rotation}\right)+\mathtt{is}\left(\mathtt{Flip}\right)+\lceil \mathtt{max}\left[{\log }_2(w_p-q_{w_p}),{\log }_2(h_p-q_{h_p})\right]\rceil$ .

For example, if we are decoding the compressed image in Fig. 8, then the 3×3 square instead of the larger 4×4 square (as in Fig. 8) is stored in the decoder memory. After reading the $ symbol in the second row, the decoder processes the first row of the 3×3 square pattern, and fills the corresponding three pixels of the second row. Then, it updates [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {BUFF}$\end{document} $\mathtt{BUFF}$ to [$0] starting from the leftmost corner of the pattern so that the decoder knows it should process the second row of the 3×3 square pattern. (Here we are assuming that P = 1. Since the only pattern is the same whether it is rotated or flipped, there is no need to specify the rotation and flip. The last bit 0 indicates that the decoder now has to reconstruct the second row of the 3×3 square pattern. Since h _p = 3 and [TeX:] \documentclass[12pt]{minimal}\begin{document}$q_{h_p}=1$\end{document} $q_{h_p}=1$ , we only need 1 bit for the purpose.) When the decoder processes the third row, it reconstructs the second row of the 3×3 square pattern by filling the three pixels, and updates [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {BUFF}$\end{document} $\mathtt{BUFF}$ to [$1] so that the decoder knows it should process the last row of the 3×3 square pattern for the next row. A similar procedure applies to the third row, and after processing the fourth row, [TeX:] \documentclass[12pt]{minimal}\begin{document}$\texttt {BUFF}$\end{document} $\mathtt{BUFF}$ is updated to [00] which terminates the reconstruction of the 3×3 square pattern.

In order to operate this frequent pattern reconstruction along with the corner transformation, the decoder requires ⌈log ₂(3) × width⌉ bits for the row buffer and P _SIZE bits to store the entire pattern table.

4.1.

Memory

For the memory circuit, Corner2 was set with parameters k = 1 and L = width, and Corner was set with parameters M = 128, k = 2, and L = 8192. We found that given the nearly even distribution of memory cells among the circuit layers a choice of k > 1 results in poorer performance than the choice k = 1 because of the frequency of all-zero rows in the images. We chose different M, N, and P _SIZE depending on the layer so that the required decoder memory is similar to that of Corner and Block C4 while giving us the best compression performance. The parameters are reported in Table 1 and the decoder memory sizes were 4.9 kBytes for Corner2, Corner, and Block C4, and 20 kBytes for JBIG.

Table 1

Memory—Corner2 parameters.

Table 2 shows the total file sizes in bytes of the algorithms. The input file sizes are measured for the raw images without any format (i.e., 1 pixel corresponds to a bit). The circuit layers are categorized into five types: wire, metal, active, poly, and via. Table 3 provides the compression ratios for Table 2. The compression ratios are defined as

Table 2

Memory—File size (bytes).

Table 3

Memory—Compression ratio ( x).

Because the memory circuit had highly regular wire layers (horizontal/vertical), we treated these layers (metal/poly) separately in the discussion. JBIG gave the highest compression results for the wire layers. However, the performance of JBIG was marginally better than Corner2 as we can see from Table 2. Observe that the wire layers consist of polygons over the entire circuit which are long in the horizontal or vertical direction. These are well-suited to the 3-line context-based prediction of JBIG and the corner representation of both Corner2 and Corner. The improvement of Corner2 over Corner is mainly due to the more efficient RLE methods introduced by Corner2. By contrast, Block C4 is less efficient because its search regions were block segmented for faster processing. For these wire layers our frequent pattern replacement algorithm did not extract any patterns, and therefore we were able to use larger M and N values for Corner2 while maintaining similar decoder memory.

For the other layers, Corner2 outperformed all other algorithms. The compression performance was the lowest for the metal layers (excluding the wire-grid layers) because the patterns were more complex and the truncation problem caused some pattern mismatch within the frequent pattern replacement process. However, both Corner2 and Corner attain higher compression ratios than Block C4 on average. The main reason that Corner2 outperforms Corner is because Corner2 applies additional RLE on EOBs and utilizes the frequent patterns — in this case, it was the pattern of the repeated memory cell — while Corner did not. While JBIG had competing performance, Corner2 outperformed it about 30%, while requiring only a quarter of the decoder memory.

Tables 4, 5 show the average run times of the algorithms for each layer type. As we can see from Table 4, the encoding time of Corner2 was 51 times faster than that of Block C4 which reduced the complexity of the earlier algorithm C4 (Ref. 2) by block segmentation. While both Block C4 and Corner2 utilize the frequent patterns, Corner2 runs much faster because it analyzes the input GDSII file instead of the image to choose the set of frequent patterns. This heuristic has no guarantee of optimality but it improves upon earlier work. However, Corner2 was about 2.9 times slower than Corner because the frequent pattern matching process is nontrivial for the memory circuit; the largest pattern size was 143×52 (= 930 bytes).

Table 4

Memory—Encoding time (s).

Table 5

Memory—Decoding time (s).

Table 5 shows the average decoding runtimes for each layer. Because of the frequent pattern replacement, Corner2 had a slightly longer decoding time than Corner but was still 18 times faster than that of Block C4 and 8% faster than that of JBIG. Similar to Table 3, the last rows of Table 4, 5 display “net average,” which is defined as

4.2.

BFSK

For the BFSK circuit, Corner2 extracts frequent patterns only for the via layer which was very small ( P _SIZE = 5), and the other parameters were fixed to M = 256, N = 256, k = 4, L = 8192. The parameters of Corner were set to M = 128, k = 4, and L = 8192. These choices allowed for similar decoder memory sizes for Corner2, Corner, and Block C4. For these parameter settings and this circuit the decoder memory sizes for Corner2, Corner, Block C4, and JBIG were, respectively, 8.4, 8.5, 8.4, and 24 kBytes.

Table 6 shows the total file sizes in bytes of the algorithms. The circuit layers are categorized into four types: active, metal, poly, and via. This time, the circuit did not contain the connection wire grid as in the memory array so the wire array was omitted. The compression ratios are computed in Table 7. As we can see from Table 7, Corner2 mostly outperforms other algorithms. The exception is for the metal layers with JBIG, but the difference was marginal (about 1%) (see Table 6).

Table 6

BFSK—File size (bytes).

Table 7

BFSK—Compression ratio ( x).

We can also see that the transform-based techniques Corner2 and Corner both attain higher compression ratios than Block C4. While Block C4 relies on context prediction and finding repeating regions within an image, Corner2 and Corner use actual polygon corners, and these corners cannot be predicted correctly by Block C4's context predictor. Corner2 outperforms Corner mainly because of the improvement in the entropy encoder.

Tables 8, 9 show the average run times of the algorithms for each layer type. As we can see from Table 8, the encoding time of Corner2 was 196 times faster than that of Block C4, but was about 7% slower than Corner. The improvement over Block C4 is due to the relatively high computational complexity of the context-based prediction and region copy components of the C4/Block C4 algorithm, and the encoding time of Corner2 is slightly longer than that of Corner because of more complex run-length encoding is used.

Table 8

BFSK—Encoding time (s).

Table 9

BFSK—Decoding time (s).

Table 9 shows that the decoding process for Corner2 is 5.7 times faster than Corner which is 5.2 times faster than Block C4. It was also 1.4 times faster than that of JBIG. The improvement in decoding time over Corner is due to the smaller output alphabet for the corner transformation process. Unlike Corner, which has to decide whether or not the corresponding pixel is a corner and to identify the type of each corner, Corner2 only needs to determine whether the pixel is a corner or not, and hence can be run faster than Corner during the transform process. Moreover, in contrast to the memory circuit, the frequent pattern replacement process was trivial for the BFSK circuit.