# Patent

## Title
Method and system for computing fourier series coefficients for mask layouts using FFT

## Abstract

A method and system for computing Fourier coefficients for a Fourier representation of a mask transmission function for a lithography mask. The method includes: sampling a polygon of a mask pattern of the lithography mask to obtain an indicator function which defines the polygon, performing a Fourier Transform on the indicator function to obtain preliminary Fourier coefficients, and scaling the Fourier coefficients for the Fourier representation of the mask transmission function, where at least one of the steps is carried out using a computer device.

## Background
CROSS-REFERENCE TO RELATED APPLICATION
This is a continuation of application Ser. No. 13/0824,440 filed on Apr. 8, 2011, which claims priority under claims priority under 35 U.S.C. §119 from European Patent Application No. 10161674.6 filed Apr. 30, 2010, the entire contents of which are incorporated herein by reference.


BACKGROUND OF INVENTION
The present invention relates to a method for computing Fourier series coefficients for mask layouts used in modern optical lithography processes. There is a need to calculate the Fourier coefficients for 2D mask design in a manner that is less time-consuming and avoids the introduction of aliasing.
SUMMARY OF THE INVENTION
The present invention provides a method for calculating a Fourier representation of mask transmission function of IC mask layouts in a more efficient manner, in addition to reducing aliasing.
One aspect of the invention includes a method for computing Fourier coefficients for a Fourier representation of a mask transmission function for the print simulation of a lithography mask used in the manufacture of lithography masks, the lithography masks having use in the manufacture of integrated circuits, the method including the steps of: sampling at least one polygon of a mask pattern of the lithography mask to obtain an indicator function defining at least one polygon, performing a Fourier Transform on the indicator function to obtain Preliminary Fourier coefficients, and scaling the Preliminary Fourier coefficients to obtain the Fourier coefficients of the Fourier representation of the mask transmission function, where at least one of the steps is carried out using a computer device.
Another aspect of the invention includes a method for computing Fourier coefficients for a Fourier representation of a mask transmission function for the print simulation of a lithography mask used in the manufacture of lithography masks, the lithography masks having use in the manufacture of integrated circuits. The method includes the steps of: sampling at least one polygon of a mask pattern of the lithography mask to obtain an indicator function defining at least one polygon, performing a Fourier Transform on the indicator function to obtain Preliminary Fourier coefficients, scaling the Preliminary Fourier coefficients to obtain the Fourier coefficients of the Fourier representation of the mask transmission function, using the Fourier coefficients to obtain a print simulation of the lithography mask, and using the print simulation in the manufacture of at least one of lithography mask and integrated circuit, where at least one of the steps is carried out using a computer device.
Another aspect of the invention includes a system for computing Fourier coefficients for a Fourier representation of a mask transmission function for a lithography mask. The system includes a means for sampling at least one polygon of a mask pattern of the lithography mask to obtain an indicator function defining at least one polygon; a computer device including means for performing a Fourier Transform operation on the indicator function to obtain preliminary Fourier coefficients; and scaling means for scaling the preliminary Fourier coefficients to obtain the Fourier coefficients for the Fourier representation of the mask transmission function.



BRIEF DESCRIPTION OF THE DRAWINGS
Embodiments of the present invention are described in detail in conjunction with the accompanying drawings, in which:
FIG. 1 shows the overall process of designing a pattern of a printable mask which results in a desired pattern when used in an optical lithography system;
FIG. 2 shows a schematic diagram for illustrating details of the print simulation process of a given mask layout;
FIG. 3 shows an example of a tile consisting of a rectilinear polygon;
FIG. 4 shows a block diagram for illustrating the method steps of computing the exact Fourier coefficient of a mask transmission function; and
FIG. 5 shows a schematic representation of an implementation of the scaling step.



DESCRIPTION OF THE EMBODIMENTS
In optical lithography, the Fourier representation of mask layers is commonly used for mask optimization procedures such as model-based optical proximity correction (OPC) or source-mask optimization (SMO). The Fourier representation of mask layers is based on Fourier coefficients. Efficiently and accurately computing the Fourier series coefficients of patterns, such as polygons for IC mask designs, is essential for the print simulation in the mask manufacturing process.
The print simulation is vital due to the very high cost of mask manufacturing. The print simulation takes into account the Fourier Transformation of the optical system as well as the Fourier Transformation of the mask transmission function. Combining these and performing an inverse Fourier Transformation lead to the illuminated pattern on a resist and in conjunction with a resist model and an etching model the printed image using the IC mask can be simulated. Hence, it is understood that the accuracy of the Fourier coefficients used to describe the mask transmission function is essential.
A potential embodiment of the above method is to obtain exact Fourier coefficients from the preliminary Fourier coefficients of a discrete Fourier Transformation of an indicator function derived from one or more polygons of a mask layout. The indicator function describes the one or more polygons by a minimum of pixels. Every polygon in the mask pattern is hence represented by a sample having a reduced number of pixels such that the complexity of the Fourier Transform based on that indicator function is essentially reduced. The Fourier coefficients can be obtained by a scaling relationship by multiplying preliminary Fourier coefficients obtained by the Fourier Transform with a provided scaling factor to obtain the exact Fourier coefficients.
Furthermore, tiles may be defined as a portion of the mask layout with one or more polygons such that the one or more polygons are fully contained in the tile, wherein the pixel size may be defined as a pixel size in at least one dimension wherein the pixel size in the at least one dimension is obtained as the greatest common divider of the tile size in the at least one dimension and the coordinates of the vertices of the one or more polygons in the at least one dimension.
The indicator function can represent the polygon by a function of coordinates within the tile, wherein the function defines whether a point is within the polygon or not over the coordinates, each coordinate corresponds to a pixel having the pixel size in the at least one dimension.
FIG. 1 shows schematically the general steps for designing a lithography mask used e.g. for a manufacturing process of highly integrated circuits having a pattern size in a range of the wavelength of the illuminating light of the lithography equipment. Starting with a given desired pattern which shall be obtained on a substrate, a print simulation 11 of an initial mask layout is performed by simulating the behavior of illuminating light being passed through the initial mask layout and its effect on a photoresist to be exposed. The result is a simulated printed image which can be compared with the given desired pattern in a defect detection process 12. Depending on the differences between the desired pattern and the simulated printed image, the initial mask layout is iteratively modified in a correction process 13 and the step of simulating the printed image is repeated as long as a measure of the difference between the simulated printed image and the desired pattern is above a tolerance threshold.
In FIG. 2, the print simulation process of a given lithography mask layout is shown in more detail. As an overview, the simulated printed image is obtained by taking into account the optical model of the lithography environment as well as the resist model and the etching model modeling the behavior of the photoresist applied onto the substrate and the characteristics of an etchant used for etching the exposed (or non-exposed) photoresist, respectively. The optical modeling of the lithography environment is done using a pupil function describing the transmission of the one or more lenses and the characteristics of the source which are mixed in a mixing process 21 and fed to an Eigenvector decomposition process 22. The result of the Eigenvector decomposition process 22 is Fourier-Transformed in a first Fourier Transform process 23 to obtain a Fourier representation of optical model.
In a second Fourier Transform process 24 the mask transmission function of the lithography mask layout is also Fourier-Transformed such that the Fourier representation of the lithography mask layout and the Fourier representation of the optical model of the lithography environment are mixed in a second mixing process 25 and supplied to an inverse Fourier Transform process 28 to obtain a simulated illumination pattern of light which is irradiated onto the substrate. By feeding the simulated illumination pattern to a subsequent resist model process 26 for taking into account the characteristics of the photoresist and etching model process 27 for taking into account the characteristics of the etching process the simulated printed image can be obtained.
As mentioned before, the Fourier Transformation of the mask transmission function of the lithography mask layout can be complex, so that for modern IC layouts the complexity is not tractable anymore. Using a discrete Fourier Transform on a sampled lithography mask layout the complexity can be reduced. However, aliasing is introduced such that the Fourier coefficients computed do not correspond anymore to the original mask pattern.
According to one embodiment proposed herein, the Fourier Transform of the given desired lithography mask layout is computed in three steps. These steps are illustrated in the block diagram of FIG. 4.
According to a first step, which is a sampling step 31, the given lithography mask layout is sampled.
It is common to apply the transformation over a rectangular subset TεR2, which is called a tile:

T=[0,Tx)×[0,Ty),Tx,TyεN 

wherein Tx and Ty correspond to the size of the tile in two dimensions (x-axis, y-axis) in Cartesian coordinates. In the context of a semiconductor manufacturing process, this section can consist of the entire substrate layer or a subsection thereof. In many cases, the layer will be divided up into individual tiles and the polygons in each tile are obtained by extracting the tiles such that only the polygon description is kept that fits into the particular tile.
A rectilinear polygon P contained in the tile is a subset of the tile whose boundaries are parallel either to the x-axis or the y-axis. The polygon P can be described by the ordered list of its K vertices:

{(x0,y0),(x1,y1), . . . ,(xk-1,yK-1)},(xi,yi)εZ2 

The vertices of the polygon P can be ordered clockwise in this embodiment, as illustrated by an example polygon which is shown in FIG. 3. Usually, as in a semiconductor manufacturing process the polygons contained in a tile are non-overlapping and thus the mask transmission function can be defined as the sum of the indicator functions f(x, y) of the different polygons P0, . . . , PM-1⊂T:




  
    
      f
      T
    
    ⁡
    
      (
      
        x
        ,
        y
      
      )
    
  
  =
  
    
      ∑
      
        i
        =
        0
      
      
        M
        -
        1
      
    
    ⁢
    
      1
      
        {
        
          
            (
            
              x
              ,
              y
            
            )
          
          ∈
          
            P
            i
          
        
        }
      
    
  




The indicator function f(x, y) corresponds to a function of coordinates within the tile, wherein the function defines whether a point is within the polygon or not over the coordinates.
The sampling of the discrete image is done essentially by sampling f(x, y) on a regular grid. The grid is chosen in order to minimize the size of the discrete image created and such that every polygon P can be represented as an integer number of pixels. Thus, a pixel is of the size px×py, where px is the greatest common divider (GCD) of Tx and the x-coordinates of the polygons' vertices and respectively py is the GCD of Ty and the y-coordinates of the polygons' vertices. In other words, px and py represent the greatest common dividers of all the distances (from the origin) along the x-coordinates and the y-coordinates, respectively, between the vertices defining the polygon P as indicated in (2). Then, the discrete image is given by:



  
    
      
        
          f
          ^
        
        T
      
      ⁡
      
        [
        
          m
          ,
          n
        
        ]
      
    
    =
    
      
        f
        T
      
      ⁡
      
        (
        
          
            
              p
              x
            
            ⁢
            m
          
          ,
          
            
              p
              y
            
            ⁢
            n
          
        
        )
      
    
  




  
    
      m
      =
      0
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        N
        x
      
      -
      1
    
  




  
    
      n
      =
      0
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        N
        y
      
      -
      1
    
  



where




  
    N
    x
  
  =
  
    
      
        
          T
          x
        
        
          P
          x
        
      
      ⁢
      
        
      
      ⁢
      and
      ⁢
      
        
      
      ⁢
      
        N
        y
      
    
    =
    
      
        T
        y
      
      
        P
        y
      
    
  




The inputs are the coordinates of the vertices of the polygons, the tile size is Tx×Ty and the pixel size is px×py.
In the second step, which is a Fourier-Transform process 32, the two-dimensional fast Fourier Transformation of fT[m, n] is computed. For example, the computation can be implemented using a standard butterfly hardware structure. The preliminary Fourier coefficients are obtained as follows:



  
    
      
        F
        ^
      
      
        k
        ,
        l
      
    
    =
    
      
        FFT
        
          k
          ,
          l
        
      
      ⁢
      
        {
        
          
            
              f
              ^
            
            T
          
          ⁡
          
            [
            
              m
              ,
              n
            
            ]
          
        
        }
      
    
  




  
    
      k
      =
      0
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        N
        x
      
      -
      1
    
  




  
    
      l
      =
      0
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        N
        y
      
      -
      1
    
  



In a next step, which is a scaling process 33, a scaling procedure is performed on the obtained preliminary Fourier series coefficients {circumflex over (F)}k,l of f(x, y) by using the following relationship:

Fk,l=ψk,l{circumflex over (F)}k,l 

wherein the scaling factor is given by:




  
    Ψ
    
      k
      ,
      l
    
  
  =
  
    
      p
      x
    
    ⁢
    
      p
      y
    
    ⁢
    sin
    ⁢
    
      
    
    ⁢
    
      c
      ⁡
      
        (
        
          k
          
            N
            x
          
        
        )
      
    
    ⁢
    sin
    ⁢
    
      
    
    ⁢
    
      c
      ⁡
      
        (
        
          1
          
            N
            y
          
        
        )
      
    
    ⁢
    
      e
      
        
          -
          j
        
        ⁢
        
          
        
        ⁢
        
          π
          ⁡
          
            (
            
              
                k
                
                  N
                  x
                
              
              +
              
                l
                
                  N
                  y
                
              
            
            )
          
        
      
    
  




The sin c function is defined as:




  
    sin
    ⁢
    
      
    
    ⁢
    
      c
      ⁡
      
        (
        x
        )
      
    
  
  =
  
    
      sin
      ⁡
      
        (
        
          π
          ⁢
          
            
          
          ⁢
          x
        
        )
      
    
    
      π
      ⁢
      
        
      
      ⁢
      x
    
  




By convention, sin c (0)=1. This scaling factor can be written as:



  
    
      Ψ
      
        k
        ,
        l
      
    
    =
    
      βe
      
        -
        jθ
      
    
  




  
    β
    =
    
      
        p
        x
      
      ⁢
      
        p
        y
      
      ⁢
      sin
      ⁢
      
        
      
      ⁢
      
        c
        ⁡
        
          (
          
            k
            
              N
              x
            
          
          )
        
      
      ⁢
      sin
      ⁢
      
        
      
      ⁢
      
        c
        ⁡
        
          (
          
            l
            
              N
              y
            
          
          )
        
      
    
  




  
    θ
    =
    
      π
      ⁡
      
        (
        
          
            k
            
              N
              x
            
          
          +
          
            l
            
              N
              y
            
          
        
        )
      
    
  



Thus in practice, the multiplication of a complex number z by Ψk,l can be implemented using three additions and three multiplications as described in H.J. Nussbaumer, “Fast Fourier Transform and Convolution Algorithms”, Springer Verlag, Berlin, 1982, an implementation of which is schematically shown in FIG. 5.

p1=β(cos θ−sin θ)

p2=−β(cos θ+sin θ)

p3=β cos θ

s1=Re{z}+Im{z}

m1=s1p3 

m2=p1Im{z}

m3=p2Re{z}

Re{βe−jθz}=m1−m2 

Im{βe−jθz}=m1+m3 

FIG. 5 shows a possible implementation of the scaling step which is made of adder stages 51, multiplication stages 52 and a subtraction stage 53. The indices r and i denote respectively real and imaginary parts. The output corresponds to q=βe−jθ z The scaling factors p1, p2 and p3 can be precomputed and stored in a lookup table 34. In hardware this can be implemented using simple logic. Alternatively, a CORDIC unit can be used performing a multiplication by a scalar and vector rotation in a single step or only vector rotation using two multiplicators in addition for the multiplication by β. In that case, only β and θ need to be stored in the lookup table 34. As an alternative implementation, the calculation can be performed in a microprocessor carrying out a software code.
In the following, the mathematical background is discussed to show that the Fourier series of f(x, y) can be expressed in terms of the discrete Fourier Transform of

{circumflex over (f)}[m,n]

Fk,l=Ψk,l{circumflex over (F)}k,l 

where



  
    
      F
      
        k
        ,
        l
      
    
    =
    
      
        F
        
          k
          ,
          l
        
      
      ⁢
      
        {
        f
        }
      
    
  




  
    
      
        F
        ^
      
      
        k
        ,
        l
      
    
    =
    
      
        D
        ⁢
        
          
        
        ⁢
        F
        ⁢
        
          
        
        ⁢
        T
        ⁢
        
          {
          
            f
            ^
          
          }
        
      
      =
      
        
          ∑
          
            m
            =
            0
          
          
            
              N
              x
            
            -
            1
          
        
        ⁢
        
          
            ∑
            
              n
              =
              0
            
            
              
                N
                y
              
              -
              1
            
          
          ⁢
          
            
              
                f
                ^
              
              ⁡
              
                [
                
                  m
                  ,
                  n
                
                ]
              
            
            ⁢
            
              e
              
                
                  -
                  j
                
                ⁢
                
                  
                
                ⁢
                2
                ⁢
                
                  π
                  ⁡
                  
                    (
                    
                      
                        km
                        
                          N
                          x
                        
                      
                      +
                      
                        ln
                        
                          N
                          y
                        
                      
                    
                    )
                  
                
              
            
          
        
      
    
  



When f(x, y) is the indicator function of M non-overlapping rectilinear polygons included in a tile T=[0, Tx)×[0, Ty), as described above, the coordinates of the polygons are:




  
    
      
        ⋃
        
          i
          =
          0
        
      
      
        M
        -
        1
      
    
    ⁢
    
      
        {
        
          (
          
            
              x
              
                i
                ,
                j
              
            
            ,
            
              y
              
                i
                ,
                j
              
            
          
          )
        
        }
      
      
        j
        =
        0
      
      
        
          K
          i
        
        -
        1
      
    
  
  ,
  
    
      x
      
        i
        ,
        j
      
    
    ∈
    
      {
      
        0
        ,
        ...
        ⁢
        
          
        
        ,
        
          T
          x
        
      
      }
    
  
  ,
  
    
      y
      
        i
        ,
        j
      
    
    ∈
    
      {
      
        0
        ,
        ...
        ⁢
        
          
        
        ,
        
          T
          y
        
      
      }
    
  




where Ki is the number of vertices of the ith polygon. Choose px, pyεN such that

xi,j=px{tilde over (x)}i,j,{tilde over (x)}i,jεN,∀i,j 

Tx=pxNx,NxεN 

yi,j=py{tilde over (y)}i,j,{tilde over (y)}i,jεN,∀i,j 

Ty=pyNy,NyεN 

Since px=1 and py=1 always satisfy these relationships such numbers can be found easily. However, px and py should be chosen as large as possible, hence:



  
    
      p
      x
    
    =
    
      G
      ⁢
      
        
      
      ⁢
      C
      ⁢
      
        
      
      ⁢
      
        D
        ⁡
        
          (
          
            
              T
              x
            
            ,
            
              
                
                  ⋃
                  
                    i
                    =
                    0
                  
                
                
                  M
                  -
                  1
                
              
              ⁢
              
                
                  {
                  
                    x
                    
                      i
                      ,
                      j
                    
                  
                  }
                
                
                  j
                  =
                  0
                
                
                  
                    K
                    i
                  
                  -
                  1
                
              
            
          
          )
        
      
    
  




  
    
      p
      y
    
    =
    
      G
      ⁢
      
        
      
      ⁢
      C
      ⁢
      
        
      
      ⁢
      
        D
        ⁡
        
          (
          
            
              T
              y
            
            ,
            
              
                
                  ⋃
                  
                    i
                    =
                    0
                  
                
                
                  M
                  -
                  1
                
              
              ⁢
              
                
                  {
                  
                    y
                    
                      i
                      ,
                      j
                    
                  
                  }
                
                
                  j
                  =
                  0
                
                
                  
                    K
                    i
                  
                  -
                  1
                
              
            
          
          )
        
      
    
  



where GCD(a, b, . . . ) gives the greatest common divider of all the numbers in argument. Pixel function is as follows:




  
    ψ
    ⁡
    
      (
      
        x
        ,
        y
      
      )
    
  
  =
  
    {
    
      
        
          1
        
        
          
            
              if
              ⁢
              
                
              
              ⁢
              0
            
            ≤
            x
            <
            
              
                p
                x
              
              ⁢
              
                
              
              ⁢
              and
              ⁢
              
                
              
              ⁢
              0
            
            ≤
            y
            <
            
              p
              y
            
          
        
      
      
        
          0
        
        
          otherwise
        
      
    
  




Finally, it is possible to define the sampled version of f(x, y) as outlined before:



  
    
      
        
          f
          ^
        
        ⁡
        
          [
          
            m
            ,
            n
          
          ]
        
      
      =
      
        f
        ⁡
        
          (
          
            
              mp
              x
            
            ,
            
              np
              y
            
          
          )
        
      
    
    ,
    
      

    
    ⁢
    
      m
      =
      0
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        N
        x
      
      -
      1
    
  




  
    
      n
      =
      0
    
    ,
    ...
    ⁢
    
      
    
    ,
    
      
        N
        y
      
      -
      1
    
  



If the relations of above equations are respected, then we have the following relationship between f(x, y) and {circumflex over (f)}[m,n]:




  
    f
    ⁡
    
      (
      
        x
        ,
        y
      
      )
    
  
  =
  
    
      ∑
      
        m
        =
        0
      
      
        
          N
          x
        
        -
        1
      
    
    ⁢
    
      
        ∑
        
          n
          =
          0
        
        
          
            N
            y
          
          -
          1
        
      
      ⁢
      
        
          
            f
            ^
          
          ⁡
          
            [
            
              m
              ,
              n
            
            ]
          
        
        ⁢
        
          ψ
          ⁡
          
            (
            
              
                x
                +
                
                  mp
                  x
                
              
              ,
              
                y
                -
                
                  np
                  y
                
              
            
            )
          
        
      
    
  




To compute the Fourier series coefficients of this expression, f and Ψ has to be made periodic of period Tx and Ty in the x and y direction, respectively. Thus, the 2D Fourier series coefficients can be computed as:



  
    
      F
      ⁢
      
        {
        f
        }
      
    
    =
    
      
        ∫
        0
        
          T
          x
        
      
      ⁢
      
        
          ∫
          0
          
            T
            y
          
        
        ⁢
        
          
            f
            ⁡
            
              (
              
                x
                ,
                y
              
              )
            
          
          ⁢
          
            e
            
              -
              
                j
                ⁡
                
                  (
                  
                    
                      
                        w
                        x
                      
                      ⁢
                      kx
                    
                    +
                    
                      
                        w
                        y
                      
                      ⁢
                      ly
                    
                  
                  )
                
              
            
          
          ⁢
          
            d
            x
          
          ⁢
          
            d
            y
          
        
      
    
  




  
    
      where
      ⁢
      
        
      
      ⁢
      
        w
        x
      
    
    =
    
      
        
          
            2
            ⁢
            π
          
          
            T
            x
          
        
        ⁢
        
          
        
        ⁢
        and
        ⁢
        
          
        
        ⁢
        
          w
          y
        
      
      =
      
        
          2
          ⁢
          π
        
        
          T
          y
        
      
    
  



Combining both equations above:




  
    F
    ⁢
    
      {
      f
      }
    
  
  =
  
    
      ∫
      0
      
        T
        x
      
    
    ⁢
    
      
        ∫
        0
        
          T
          y
        
      
      ⁢
      
        
          ∑
          
            m
            =
            0
          
          
            
              N
              x
            
            -
            1
          
        
        ⁢
        
          
            ∑
            
              n
              =
              0
            
            
              
                N
                y
              
              -
              1
            
          
          ⁢
          
            
              
                f
                ^
              
              ⁡
              
                [
                
                  m
                  ,
                  n
                
                ]
              
            
            ⁢
            
              ψ
              ⁡
              
                (
                
                  
                    x
                    -
                    
                      mp
                      x
                    
                  
                  ,
                  
                    y
                    -
                    
                      np
                      y
                    
                  
                
                )
              
            
            ⁢
            
              e
              
                -
                
                  j
                  ⁡
                  
                    (
                    
                      
                        
                          w
                          x
                        
                        ⁢
                        kx
                      
                      +
                      
                        
                          w
                          y
                        
                        ⁢
                        ly
                      
                    
                    )
                  
                
              
            
            ⁢
            
              d
              x
            
            ⁢
            
              d
              y
            
          
        
      
    
  




Furthermore:




  
    
      
        
          e
          
            -
            
              j
              ⁡
              
                (
                
                  
                    
                      w
                      x
                    
                    ⁢
                    kx
                  
                  +
                  
                    
                      w
                      y
                    
                    ⁢
                    ly
                  
                
                )
              
            
          
        
        =
        
        ⁢
        
          
            e
            
              -
              
                j
                ⁡
                
                  (
                  
                    
                      
                        w
                        x
                      
                      ⁢
                      
                        k
                        ⁡
                        
                          (
                          
                            x
                            -
                            
                              mp
                              x
                            
                          
                          )
                        
                      
                    
                    +
                    
                      
                        w
                        y
                      
                      ⁢
                      
                        l
                        ⁡
                        
                          (
                          
                            y
                            -
                            
                              np
                              y
                            
                          
                          )
                        
                      
                    
                  
                  )
                
              
            
          
          ⁢
          
            e
            
              -
              
                j
                ⁡
                
                  (
                  
                    
                      
                        w
                        x
                      
                      ⁢
                      
                        kmp
                        s
                      
                    
                    +
                    
                      
                        w
                        y
                      
                      ⁢
                      ln
                      ⁢
                      
                        
                      
                      ⁢
                      
                        p
                        y
                      
                    
                  
                  )
                
              
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            e
            
              -
              
                j
                ⁡
                
                  (
                  
                    
                      
                        w
                        x
                      
                      ⁢
                      ku
                    
                    +
                    
                      
                        w
                        y
                      
                      ⁢
                      lv
                    
                  
                  )
                
              
            
          
          ⁢
          
            e
            
              -
              
                j2π
                ⁡
                
                  (
                  
                    
                      km
                      
                        N
                        x
                      
                    
                    +
                    
                      ln
                      
                        N
                        y
                      
                    
                  
                  )
                
              
            
          
        
      
    
  




where we used the substitution u=x−m px and v=y−n py. Hence it becomes:




  
    
      
        
          F
          ⁢
          
            {
            f
            }
          
        
        =
        
        ⁢
        
          
            ∑
            
              m
              =
              0
            
            
              
                N
                x
              
              -
              1
            
          
          ⁢
          
            
              ∑
              
                n
                =
                0
              
              
                
                  N
                  y
                
                -
                1
              
            
            ⁢
            
              
                
                  f
                  ^
                
                ⁡
                
                  [
                  
                    m
                    ,
                    n
                  
                  ]
                
              
              ⁢
              
                e
                
                  -
                  
                    j2π
                    ⁡
                    
                      (
                      
                        
                          km
                          
                            N
                            x
                          
                        
                        +
                        
                          ln
                          
                            N
                            y
                          
                        
                      
                      )
                    
                  
                
              
            
          
        
      
    
  
  
    
      
        
        ⁢
        
          
            ∫
            
              -
              
                mp
                x
              
            
            
              
                T
                x
              
              -
              
                mp
                x
              
            
          
          ⁢
          
            
              ∫
              
                -
                
                  np
                  y
                
              
              
                
                  T
                  y
                
                -
                
                  np
                  y
                
              
            
            ⁢
            
              
                ψ
                ⁡
                
                  (
                  
                    u
                    ,
                    v
                  
                  )
                
              
              ⁢
              
                e
                
                  -
                  
                    j
                    ⁡
                    
                      (
                      
                        
                          
                            w
                            x
                          
                          ⁢
                          ku
                        
                        +
                        
                          
                            w
                            y
                          
                          ⁢
                          lv
                        
                      
                      )
                    
                  
                
              
              ⁢
              
                d
                u
              
              ⁢
              
                d
                v
              
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            ∑
            
              m
              =
              0
            
            
              
                
                  (
                  a
                  )
                
                ⁢
                
                  N
                  x
                
              
              -
              1
            
          
          ⁢
          
            
              ∑
              
                n
                =
                0
              
              
                
                  N
                  y
                
                -
                1
              
            
            ⁢
            
              
                
                  f
                  ^
                
                ⁡
                
                  [
                  
                    m
                    ,
                    n
                  
                  ]
                
              
              ⁢
              
                e
                
                  -
                  
                    j2π
                    ⁡
                    
                      (
                      
                        
                          km
                          
                            N
                            x
                          
                        
                        +
                        
                          ln
                          
                            N
                            y
                          
                        
                      
                      )
                    
                  
                
              
            
          
        
      
    
  
  
    
      
        
        ⁢
        
          
            ∫
            0
            
              T
              x
            
          
          ⁢
          
            
              ∫
              0
              
                T
                y
              
            
            ⁢
            
              
                ψ
                ⁡
                
                  (
                  
                    u
                    ,
                    v
                  
                  )
                
              
              ⁢
              
                e
                
                  -
                  
                    j
                    ⁡
                    
                      (
                      
                        
                          
                            w
                            x
                          
                          ⁢
                          ku
                        
                        +
                        
                          
                            w
                            y
                          
                          ⁢
                          lv
                        
                      
                      )
                    
                  
                
              
              ⁢
              
                d
                u
              
              ⁢
              
                d
                v
              
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          D
          ⁢
          
            
          
          ⁢
          F
          ⁢
          
            
          
          ⁢
          T
          ⁢
          
            {
            
              f
              ^
            
            }
          
          ⁢
          F
          ⁢
          
            {
            ψ
            }
          
        
      
    
  




where we used in (a) the periodicity of Ψ(x, y) to remove the dependency of the integral on m and n.
Now the value of Ψk,l=Fk,l{Ψ} is computed. Ψ(x, y) can be written as:



  
    
      ψ
      ⁡
      
        (
        
          x
          ,
          y
        
        )
      
    
    =
    
      
        
          rect
          
            p
            x
          
        
        ⁡
        
          (
          
            x
            -
            
              
                p
                x
              
              2
            
          
          )
        
      
      ⁢
      
        
          rect
          
            p
            y
          
        
        ⁡
        
          (
          
            y
            -
            
              
                p
                y
              
              2
            
          
          )
        
      
    
  




  where




  
    
      
        rect
        B
      
      ⁡
      
        (
        t
        )
      
    
    =
    
      {
      
        
          
            1
          
          
            
              
                if
                ⁢
                
                  
                
                -
                
                  B
                  2
                
              
              ≤
              t
              <
              
                B
                2
              
            
          
        
        
          
            0
          
          
            otherwise
          
        
      
    
  



and if it is periodized with period T, the corresponding Fourier series is given by:




  
    
      F
      k
    
    ⁢
    
      {
      
        rect
        B
      
      }
    
  
  =
  
    
      B
      ⁢
      
        
      
      ⁢
      sin
      ⁢
      
        
      
      ⁢
      
        c
        ⁡
        
          (
          
            
              k
              T
            
            ⁢
            B
          
          )
        
      
    
    =
    
      
        sin
        ⁡
        
          (
          
            π
            ⁢
            
              
            
            ⁢
            
              k
              T
            
            ⁢
            B
          
          )
        
      
      
        π
        ⁢
        
          
        
        ⁢
        
          k
          T
        
      
    
  




If in addition the delay property and the separability of the Fourier series is used:




  
    
      
        
          ψ
          
            k
            ,
            l
          
        
        =
        
        ⁢
        
          
            p
            x
          
          ⁢
          sin
          ⁢
          
            
          
          ⁢
          
            c
            ⁡
            
              (
              
                
                  k
                  
                    T
                    x
                  
                
                ⁢
                
                  p
                  x
                
              
              )
            
          
          ⁢
          
            e
            
              
                -
                j
              
              ⁢
              
                
              
              ⁢
              2
              ⁢
              π
              ⁢
              
                k
                
                  T
                  x
                
              
              ⁢
              
                
                  p
                  x
                
                2
              
            
          
          ⁢
          
            p
            y
          
          ⁢
          sin
          ⁢
          
            
          
          ⁢
          
            c
            ⁡
            
              (
              
                
                  l
                  
                    T
                    y
                  
                
                ⁢
                
                  p
                  y
                
              
              )
            
          
          ⁢
          
            e
            
              
                -
                j2π
              
              ⁢
              
                1
                
                  T
                  y
                
              
              ⁢
              
                
                  p
                  y
                
                2
              
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            p
            x
          
          ⁢
          sin
          ⁢
          
            
          
          ⁢
          
            c
            ⁡
            
              (
              
                k
                
                  N
                  x
                
              
              )
            
          
          ⁢
          
            e
            
              
                -
                jπ
              
              ⁢
              
                k
                
                  N
                  x
                
              
            
          
          ⁢
          
            p
            y
          
          ⁢
          sin
          ⁢
          
            
          
          ⁢
          
            c
            ⁡
            
              (
              
                l
                
                  N
                  y
                
              
              )
            
          
          ⁢
          
            e
            
              
                -
                jπ
              
              ⁢
              
                1
                
                  N
                  y
                
              
            
          
        
      
    
  




In conclusion we can show that the Fourier series of f(x, y) can be expressed in terms of the DFT of {circumflex over (f)}[m,n]:



  
    
      where
      ⁢
      
        
      
      ⁢
      
        F
        
          k
          ,
          l
        
      
    
    =
    
      
        Ψ
        
          k
          ,
          l
        
      
      ⁢
      
        
          F
          ^
        
        
          k
          ,
          l
        
      
    
  




  
    
      F
      
        k
        ,
        l
      
    
    =
    
      
        F
        
          k
          ,
          l
        
      
      ⁢
      
        {
        f
        }
      
    
  




  
    
      
        F
        ^
      
      
        k
        ,
        l
      
    
    =
    
      
        D
        ⁢
        
          
        
        ⁢
        F
        ⁢
        
          
        
        ⁢
        T
        ⁢
        
          {
          
            f
            ^
          
          }
        
      
      =
      
        
          ∑
          
            m
            =
            0
          
          
            
              N
              x
            
            -
            1
          
        
        ⁢
        
          
            ∑
            
              n
              =
              0
            
            
              
                N
                y
              
              -
              1
            
          
          ⁢
          
            
              
                f
                ^
              
              ⁡
              
                [
                
                  m
                  ,
                  n
                
                ]
              
            
            ⁢
            
              e
              
                
                  -
                  2
                
                ⁢
                
                  π
                  ⁡
                  
                    (
                    
                      
                        km
                        
                          N
                          x
                        
                      
                      +
                      
                        ln
                        
                          N
                          y
                        
                      
                    
                    )
                  
                
              
            
          
        
      
    
  



While the present invention has been described with reference to certain embodiments, it will be understood by those skilled in the art that various changes can be made and equivalents can be substituted without departing from the scope of the present invention. In addition, many modifications can be made to adapt a particular situation to the teachings of the present invention without departing from its scope. Therefore, it is intended that the present invention not be limited to the particular embodiment disclosed, but that the present invention will include all embodiments falling within the scope of the appended claims. For example, the present invention can be contemplated for various applications. While embodiments described above shall merely find applications in lithography masks, the skilled person can appreciate potential applications to other methods of printing. Furthermore, alternative definitions can be used for the Fourier coefficients, the Fourier Transform, etc., as usual in this field. Also, various Fourier Transform types can be relied upon, e.g. a Fast Fourier Transform or evolutions thereof.

## Claims

1. A method for computing a Fourier series representation of a mask transmission function for a print simulation of a lithography mask used in a manufacture of lithography masks, the method comprising the steps of:
sampling at least one polygon of a mask pattern of the lithography mask to obtain an indicator function defining the at least one polygon using a number of pixels;
performing a Discrete Fourier Transform (DFT) on the indicator function to obtain coefficients of the DFT; and
scaling, using a computer device, the coefficients of the DFT to obtain exact coefficients of a Fourier series that represents the mask transmission function,
wherein the mask pattern comprises at least one tile, wherein the at least one tile comprises the at least one polygon.

2. The method according to claim 1, such that the at least one polygon is fully contained in the at least one tile, wherein a pixel size is defined as a pixel size in at least one dimension.

3. The method according to claim 2, wherein the pixel size in the at least one dimension is obtained as a greatest common divider of a tile size in the at least one dimension and a coordinates of vertices of the at least one polygon in the at least one dimension.

4. The method according to claim 1, wherein a pixel size in at least one dimension is obtained as a greatest common divider of a tile size in the at least one dimension and coordinates of vertices of the at least one polygon in at least one dimension.

5. The method according to claim 1, wherein the DFT is a two-dimensional Fast Fourier Transform.

6. The method according to claim 1, wherein the sampling utilizes a minimal number of pixels possible.

7. The method according to claim 1, further comprising the step of using the exact coefficients of the Fourier series to obtain the print simulation of the lithography mask.

8. The method according to claim 1, further comprising the step of using the exact coefficients of the Fourier series for manufacture of at least one of integrated circuits and lithography masks.

9. The method according to claim 1, wherein the indicator function represents the at least one polygon by a function of coordinates within the at least one tile, wherein the indicator function defines whether a point is within the at least one polygon, wherein each the coordinate corresponds to a pixel having a pixel size in at least one dimension.

10. The method according to claim 9, wherein the step of scaling the coefficients of the DFT is performed by multiplying the coefficients of the DFT by scaling factors, wherein the scaling factors are determined according to a scaling factor function depending on the coordinates.

11. The method according to claim 10, wherein the scaling factors are provided using a lookup table.

12. A system, comprising:
means for sampling at least one polygon of a mask pattern of a lithography mask to obtain an indicator function defining the at least one polygon using a number of pixels;
a computer device including means for performing a Discrete Fourier Transform operation on the indicator function to obtain coefficients of a Discrete Fourier Transform; and
means for scaling the coefficients of the Discrete Fourier Transform to obtain exact coefficients of a Fourier series that represents a mask transmission function for the lithography mask,
wherein the mask pattern comprises at least one tile, wherein the at least one tile comprises the at least one polygon.

13. The system according to claim 12, such that the at least one polygon is fully contained in the at least one tile, wherein a pixel size is defined as a pixel size in at least one dimension.

14. The system according to claim 13, wherein the pixel size in the at least one dimension is obtained as a greatest common divider of a tile size in the at least one dimension and coordinates of vertices of the at least one polygon in the at least one dimension.

15. The system according to claim 12, wherein a pixel size in at least one dimension is obtained as a greatest common divider of a tile size in the at least one dimension and coordinates of vertices of the at least one polygon in at least one dimension.

16. The system according to claim 12, wherein the Discrete Fourier Transform is a two-dimensional Fast Fourier Transform.

17. The system according to claim 12, wherein the sampling utilizes a minimal number of pixels possible.

18. A method, comprising the steps of:
sampling at least one polygon of a mask pattern of a lithography mask to obtain an indicator function defining the at least one polygon using a number of pixels;
performing a discrete Fourier transformation on the indicator function to obtain coefficients of a discrete Fourier Transform; and
scaling, using a computer device, the coefficients of the discrete Fourier Transform to obtain exact coefficients of a continuous Fourier series that represents a mask transmission function, wherein the mask pattern comprises at least one tile, wherein the at least one tile comprises the at least one polygon;
using the continuous Fourier series to obtain a print simulation of the lithography mask; and
using the print simulation for manufacturing at least one of an integrated circuit and a lithography mask.

19. The method according to claim 18, such that the at least one polygon is fully contained in the at least one tile, wherein a pixel size is defined as a pixel size in at least one dimension.

20. The system according to claim 15, wherein the exact coefficients of the Fourier series are used to obtain a print simulation of the lithography mask, and wherein the print simulation is used to manufacture at least one of an integrated circuit and a lithography mask.