Fast convolution method and its application in mask optimization for intensity calculation using basis expansion

Finer grid representation is required for a more accurate description of mask patterns in inverse lithography techniques, thus resulting in a large-size mask representation and heavy computational cost. To mitigate the computation problem caused by intensive convolutions in mask optimization, a new method called convolution using basis expansion (CBE) is discussed in this paper. Matrices defined in fine grid are projected on coarse gird under a base matrix set. The new matrices formed by the expansion coefficients are used to perform convolution on the coarse grid. The convolution on fine grid can be approximated by the sum of a few convolutions on coarse grid following an interpolation procedure. The CBE is verified by random matrix convolutions and intensity calculation in lithography simulation. Results show that the use of the CBE method results in similar image quality with significant running speed enhancement compared with traditional convolution method.

Fast robust correlation

A new, fast, statistically robust, exhaustive, translational image-matching technique is presented: fast robust correlation. Existing methods are either slow or non-robust, or rely on optimization. Fast robust correlation works by expressing a robust matching surface as a series of correlations. Speed is obtained by computing correlations in the frequency domain. Computational cost is analyzed and the method is shown to be fast. Speed is comparable to conventional correlation and, for large images, thousands of times faster than direct robust matching. Three experiments demonstrate the advantage of the technique over standard correlation.

High-speed multidimensional convolution

Fast computation algorithms are developed for twodimensional and general multidimensional convolutions. Two basic techniques (overlap-and-add, overlap-and-save) are described in detail. These techniques allow speed and storage requirement tradeoffs and they define a decomposition of the total convolution into partial convolutions that can be easily found by parallel use of fast sequential cyclic convolution algorithms. It is shown that unlike what is the case in one dimension, the ``overlap-and-save'' method enjoys a clear advantage over the ``overlap-and-add'' method with respect to speed and storage in multidimensional convolution. A specific computational burden is assessed for the case where these methods are used in conjunction with radix-2 fast Fourier transform algorithms.