Regular Articles

Fast continuous Fourier and Haar transforms of rectilinear polygons from very-large-scale integration layouts

[+] Author Affiliations
Robin Scheibler

Ecole Polytechnique Fédérale de Lausanne, School of Computer and Communication Sciences, Audiovisual Communications Laboratory, BC Building, Station 14, Lausanne, Switzerland

Paul Hurley

IBM Research Zürich, Systems Department, Rüschlikon, Switzerland

Amina Chebira

Ecole Polytechnique Fédérale de Lausanne, School of Computer and Communication Sciences, Audiovisual Communications Laboratory, BC Building, Station 14, Lausanne, Switzerland

J. Micro/Nanolith. MEMS MOEMS. 12(4), 043008 (Dec 20, 2013). doi:10.1117/1.JMM.12.4.043008
History: Received September 7, 2012; Revised October 18, 2013; Accepted November 21, 2013
Text Size: A A A

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.

Figures in this Article
© 2013 Society of Photo-Optical Instrumentation Engineers

Citation

Robin Scheibler ; Paul Hurley and Amina Chebira
"Fast continuous Fourier and Haar transforms of rectilinear polygons from very-large-scale integration layouts", J. Micro/Nanolith. MEMS MOEMS. 12(4), 043008 (Dec 20, 2013). ; http://dx.doi.org/10.1117/1.JMM.12.4.043008


Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Book Chapters

Topic Collections

Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.