Share Email Print

Journal of Micro/Nanolithography, MEMS, and MOEMS

Fast continuous Fourier and Haar transforms of rectilinear polygons from very-large-scale integration layouts
Author(s): Robin Scheibler; Paul Hurley; Amina Chebira
Format Member Price Non-Member Price
PDF $20.00 $25.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

We propose two new fast algorithms for the computation of the continuous Fourier series and the continuous Haar transform of rectilinear polygons such as those of mask layouts in optical lithography. These algorithms outperform their discrete counterparts traditionally used. Not only are continuous transforms closer to the underlying continuous physical reality, but they also avoid the inherent inaccuracies introduced by the sampling or rasterization of the polygons in the discrete case. Moreover, massive amounts of data and the intense processing methods used in lithography require efficient algorithms at every step of the process. We derive the complexity of each algorithm and compare it to that of the corresponding discrete transform. For the practical very-large-scale integration (VLSI) layouts, we find significant reduction in the complexity because the number of polygon vertices is substantially smaller than the corresponding discrete image. This analysis is completed by an implementation and a benchmark of the continuous algorithms and their discrete counterparts. We run extensive experiments and show that on tested VLSI layouts the pruned continuous Haar transform is 5 to 25 times faster, while the fast continuous Fourier series is 1.5 to 3 times faster than their discrete counterparts.

Paper Details

Date Published: 20 December 2013
PDF: 12 pages
J. Micro/Nanolith. MEMS MOEMS 12(4) 043008 doi: 10.1117/1.JMM.12.4.043008
Published in: Journal of Micro/Nanolithography, MEMS, and MOEMS Volume 12, Issue 4
Show Author Affiliations
Robin Scheibler, Ecole Polytechnique Fédérale de Lausanne (Switzerland)
Paul Hurley, IBM Research – Zürich (Switzerland)
Amina Chebira, Ecole Polytechnique Fédérale de Lausanne (Switzerland)

© SPIE. Terms of Use
Back to Top