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

Robin Scheibler; Paul Hurley; Amina Chebira

doi:10.1117/1.JMM.12.4.043008

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

Robin Scheibler, Paul Hurley, Amina Chebira

Author Affiliations +

Journal of Micro/Nanolithography, MEMS, and MOEMS, Vol. 12, Issue 4, 043008 (December 2013). https://doi.org/10.1117/1.JMM.12.4.043008

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.

Citation Download Citation

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

Published: 20 December 2013

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available

Members: $24.00

Non-members: $28.00 ADD TO CART

JOURNAL ARTICLE
12 PAGES

DOWNLOAD PAPER SAVE TO MY LIBRARY

GET CITATION

RIGHTS & PERMISSIONS

Get copyright permission Get copyright permission on Copyright Marketplace

KEYWORDS

Transform theory

Very large scale integration

Algorithm development

Lithography

Photomasks

Fourier transforms

Fast wavelet transforms

Show All Keywords

Keywords/Phrases

Search In:

Publication Years