Lossless compression of VLSI layout image data.

We present a novel lossless compression algorithm called Context Copy Combinatorial Code (C4), which integrates the advantages of two very disparate compression techniques: context-based modeling and Lempel-Ziv (LZ) style copying. While the algorithm can be applied to many lossless compression applications, such as document image compression, our primary target application has been lossless compression of integrated circuit layout image data. These images contain a heterogeneous mix of data: dense repetitive data better suited to LZ-style coding, and less dense structured data, better suited to context-based encoding. As part of C4, we have developed a novel binary entropy coding technique called combinatorial coding which is simultaneously as efficient as arithmetic coding, and as fast as Huffman coding. Compression results show C4 outperforms JBIG, ZIP, BZIP2, and two-dimensional LZ, and achieves lossless compression ratios greater than 22 for binary layout image data, and greater than 14 for gray-pixel image data.     

New properties of sigma-delta modulators with DC inputs

New properties of single- and double-loop sigma-delta modulators with constant inputs are derived by exploiting the inherent structure os the output sequences or codewords that the modulators are capable of producing. Upper bounds are derived on the number of N-bit codewords for the single- and double-loop modulators. Analytical lower bounds on the mean squared error (MSE) obtainable by any decoder, linear or nonlinear, in approximating the constant input are also derived. Optimal nonlinear decoders for constant inputs based on a table lookup approach which operates directly on the nonuniform quantization intervals are considered. Using simulations is is found that the optimal nonlinear decoders perform better than linear decoders, by about 3 and 20 dB for the single- and double-loop modulators, respectively. A cascade structure specifically for constant inputs is introduced, and its corresponding decoding algorithm is derived. It is shown that for a fixed latency, the MSE performance of the cascade structure is 12 dB superior, and its throughput is twice that of the conventional two-stage MASH modulator     

Reconstruction of oversampled band-limited signals fromΣΔ encoded binary sequences

Considers the application of ΣΔ modulators to analog-to-digital conversion. The authors have previously shown that for constant input signals, optimal nonlinear decoding can achieve large gains in signal-to-noise ratio (SNR) over linear decoding. The present paper shows a similar result for band-limited input signals. The new nonlinear decoding algorithm is based on projections onto convex sets (POCS), and alternates between a time-domain operation and a band limitation to find a signal invariant under both. The time-domain operation results in a quadratic programming problem. The band limitation can be based on singular value decomposition of a certain matrix. The authors show simulation results for the SNR performance of a POCS-based decoder and a linear decoder for the single loop, double loop and two-stage ΣΔ modulators and for a specific fourth-order interpolative modulator. Depending on the modulator and the oversampling ratio, improvements in SNR of up to 10-20 dB can be achieved     

A new class of B/W halftoning algorithms

A new class of dithering algorithms for black and white (B/W) images is presented. The basic idea behind the technique is to divide the image into small blocks and minimize the distortion between the original continuous-tone image and its low-pass-filtered halftone. This corresponds to a quadratic programming problem with linear constraints, which is solved via standard optimization techniques. Examples of B/W halftone images obtained by this technique are compared to halftones obtained via existing dithering algorithms.     

Lossless Compression Algorithms for Hierarchical IC Layout

An important step in today's integrated circuit (IC) manufacturing is optical proximity correction (OPC). While OPC increases the fidelity of pattern transfer to the wafer, it also significantly increases IC layout file size. This has the undesirable side effect of increasing storage, processing, and I.O. times for subsequent steps of mask preparation. In this paper, we propose two techniques for compressing layout data, including OPC layout, while remaining compliant with existing industry standard formats such as OASIS and GDSII. Our approach is to eliminate redundancies in the representation of the geometrical data by finding repeating groups of geometries between multiple cells and within a cell. We refer to the former as ldquointercell subcell detection (InterSCD)rdquo and the latter as ldquointracell subcell detection (IntraSCD).rdquo We show both problems to be nondeterministic polynomial time hard (NP-hard), and propose two sets of heuristics to solve them. For OPC layout data, we also propose a fast compression method based on IntraSCD which utilizes the hierarchical information in the pre-OPC layout data. We show that the IntraSCD approach can also be effective in reconstructing hierarchy from flattened layout data. We demonstrate the results of our proposed algorithms on actual IC layouts for 90-nm, 130-nm, and 180-nm feature size circuit designs.     

Reconstruction of two-dimensional signals from level crossings

Recent results indicate that reconstruction of two-dimensional signals from crossings of one level requires, in theory and practice, extreme accuracy in positions of the samples. The representation of signals with one-level crossings can be viewed as a tradeoff between bandwidth and dynamic range, in the sense that if the available bandwidth is sufficient to preserve the level crossings accurately, then the dynamic range requirements are significantly reduced. On the other hand, representation of signals by their samples at the Nyquist rate can be considered as requiring relatively small bandwidth and large dynamic range, because, at least in theory, amplitude information at prespecified points is needed, to infinite precision. An overview of existing results in zero crossing representation is presented, and a number of new results on sampling schemes for reconstruction from multiple-level threshold crossing are developed. The quantization characteristics of these sampling schemes appear to lie between those of Nyquist sampling and one-level crossing representations, thus bridging the gap between explicit Nyquist sampling and implicit one-level crossing sampling strategies     

Binary and phase shifting mask design for optical lithography

The authors propose a number of pre-distorted mask design techniques for binary and phase-shifting masks. Their approach is based on modeling the imaging mechanism of a stepper by the Hopkins equations and taking advantage of the contrast-enhancement characteristics of photoresist. Optimization techniques such as the branch and bound algorithm and simulated annealing algorithm are used to systematically design pre-distorted masks under incoherent and partially coherent illumination. Computer simulations are used to show that the intensity contour shapes and developed resist shapes of their designed mask patterns are sharper than those of conventional masks. The designed phase-shifting masks are shown to result in higher contrast as well as sharper contours than binary masks. An example of phase conflicting masks designed with the algorithm is shown to outperform a simple intuitive design. This example indicates that a fairly general design procedure consisting of alternating phase shifts and their optimized phase-shift masks is a viable candidate for future phase-shifting mask design