Abstract:
A technique for determining, without having to perform optical proximity correction, when the result of optical proximity correction will fail to meet the design requirements for printability. A disclosed embodiment has application to a process for producing a photomask for use in the printing of a pattern on a wafer by exposure with optical radiation to optically image the photomask on the wafer. A method is set forth for checking the printability of a target layout proposed for defining the photomask, including the following steps: deriving a system of inequalities that expresses a set of design requirements with respect to the target layout; and checking the printability of the target layout by determining whether the system of inequalities is feasible.

Description:
RELATED APPLICATION 
   Priority is claimed from U.S. Provisional Patent Application No. 60/709,881, filed Aug. 19, 2005, and said Provisional Patent Application is incorporated herein by reference. 

   FIELD OF THE INVENTION 
   This invention relates to the field of fabrication of integrated circuits and, more particularly, to the checking for printability of a lithography target used in the production of integrated circuits. 
   BACKGROUND OF THE INVENTION 
   Patterns in an integrated circuit are designed according to requirements of circuit performance, layout and routing. The output of layout and routing is a set of target polygons that are input to photomask design. The goal of photomask design is to minimize the difference between the pattern that will be rendered on the wafer, and the target pattern, for a sufficiently large process window. Process window refers to a region in the exposure dose-defocus plane on which one or more critical dimension of a pattern is printed within an acceptable tolerance. Photomask design is an optimization process. Resolution enhancement techniques (RET) and optical proximity corrections (OPC) are techniques that are used to optimize the photomask for a given target pattern. 
   An important consideration in chip design is that not every pattern can be rendered by lithography. It is entirely possible to specify a target pattern that is not printable, or printable with an unacceptably narrow process window, using a specific lithography process. 
   Layout and routing is constrained by a set of geometric design rules. For example, design rules may include minimum line width, minimum space width, disallowed combinations of line and space widths. Conformance of a target pattern to design rules is performed by a design rule check (DRC) software, which is based on geometry operations. A set of design rules is specific to a certain combination of wavelength, numerical aperture of the lithography projector, illumination condition, and photoresist. Design rules are selected to ensure that if a pattern conforms to the design rules, the pattern will be printable with a sufficient process window. 
   However, design-rule checking of the prior art has deficiencies and limitations, including the following: (1) there is no guarantee that a finite set of geometric rules can predict printability of countless two-dimensional patterns; (2) if design rules ensure printability, they may be overly conservative and may lead to increased chip size; (3) designers may choose to violate design rules to achieve a higher density of devices, for example in an SRAM design. 
   If design rules are bypassed or design rules unwittingly allow a pattern that is not printable, RET and OPC can be thrown into an endless loop. If an RET/OPC approach fails to achieve a desired target pattern and process window, the natural reaction of the RET/OPC engineer is to change the parameters of optimization, or to consider different RET schemes. This process can waste precious design time because prior art RET/OPC cannot definitively state that a certain target is unprintable irrespective of photomask technology at a given wavelength and numerical aperture (NA). 
   The prior art includes determination of printability after applying optical proximity corrections to the photomask layout (see: Choi et al., Proceedings of SPIE, Vol. 5377, p. 713-720, SPIE Bellingham, Wash., 2004). 
   It is among the objects of the present invention to provide a technique for determining when the result of optical proximity corrections will fail to meet the design requirements, without having to perform the optical proximity corrections. It is also among the objects of the present invention to improve on existing techniques for checking the printability of a lithography target layout. [As used herein, “printability” of a target layout means that when the layout is employed in projecting an image on the wafer, the pattern that is printed (for example, on a photoresist film coating of a wafer) by exposure with optical radiation, has acceptable tolerances.] 
   SUMMARY OF THE INVENTION 
   The invention provides, inter alia, a technique for determining, without having to perform optical proximity correction, when the result of optical proximity correction will fail to meet the design requirements for printability. 
   An embodiment of the invention has application to a process for producing a photomask (e.g. a transmissive or reflective type of photomask) for use in the printing of a pattern on a wafer by exposure with optical radiation to optically image the photomask on the wafer. [As used herein, “optical radiation” means light having wavelength within or outside the visible, used to obtain exposure of a film, for example a photoresist film.] In accordance with this embodiment, a method is set forth for checking the printability of a target layout proposed for defining said photomask, including the following steps: deriving a system of inequalities that expresses a set of design requirements with respect to the target layout; and checking the printability of said target layout by determining whether said system of inequalities is feasible. 
   An embodiment of the invention further comprises dividing said target layout into parts, and the step of determining the printability of the target layout comprises determining the printability of said parts of the target layout. 
   In an embodiment of the invention, the photomask is for printing of a pattern on a film on said wafer, and variations in the exposure dose of target points of the pattern are represented by dose latitude in said system of inequalities. In a form of this embodiment, a determination is made of a dose latitude for which at least part of the target layout is printable. 
   In an embodiment of the invention, said system of inequalities includes the wavelength of the optical radiation. Also this embodiment, the optical radiation is produced by a projector having objective optics and a numerical aperture of its projection objective, and said system of inequalities includes said numerical aperture, and also includes the depth of field of the projector optics. Further in this embodiment, said system of inequalities includes edge-placement tolerance of the pattern associated with the target layout. Also, a form of this embodiment includes determination of an edge-placement tolerance for which at least part of said target pattern is printable. 
   In an embodiment of the invention, the step of checking the printability of said target layout is performed before performing at least one of the following changes to said target layout: applying an optical proximity correction; adding a sub-resolution feature; or assigning a phase-shift to a feature. In a form of this embodiment, the step of checking the printability of said target layout is performed before an illumination condition of the photolithography projector is determined. 
   A further embodiment of the invention includes the following steps: providing a plurality of processors; and dividing said step of determining the printability of said target layout among said plurality of processors, whereby different processors determine the printability of different parts of said target layout. 
   An embodiment of the invention has application to the fabrication of integrated circuits that includes a process for producing a photomask for use in the printing of a pattern on a photoresist film which coats at least part of a semiconductor wafer, by exposure with optical radiation from a projector to optically image the photomask on the wafer. A method is set forth for checking the printability of a target layout proposed for defining said photomask, including the following steps: deriving a system of inequalities that expresses a set of design requirements with respect to the target layout; dividing said target layout into parts; and checking the printability of said parts of said target layout by determining whether said system of inequalities is feasible. In a form of this embodiment, said checking is performed during layout or routing of an integrated circuit. In a further form of this embodiment, the layout or routing is modified until printability is achieved. 
   The invention also has application to mask-less lithography and immersion lithography. An embodiment hereof is broadly directed to a process for printing of a pattern on a wafer by optically projecting an image on the wafer. In accordance with this embodiment, a method is set forth for checking the printability of a target layout proposed for defining said pattern, including the following steps: deriving a system of inequalities that expresses a set of design requirements with respect to the target layout; and checking the printability of said target layout by determining whether said system of inequalities is feasible. 
   Further features and advantages of the invention will become more readily apparent from the following detailed description when taken in conjunction with the accompanying drawings. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a schematic diagram showing a target polygon, target points, and some normal vectors. 
       FIG. 2  is a schematic diagram of a computation domain and a karo containing a pattern. 
       FIG. 3   a  is a flow chart of a routine in accordance with an alternative embodiment of the invention. 
       FIG. 3   b  is a flow chart of a routine in accordance with another embodiment of the invention. 
       FIG. 4  is a block diagram of an apparatus in accordance with an embodiment of the invention. 
   

   DETAILED DESCRIPTION 
   The terms “karo”, “target points,” and “normal vectors” are used in the description, and will first be defined. 
   Techniques hereof check a small region of the target layer at a time. This region is called a karo. The union of karos cover the chip, or the part of the layout to be checked. Karos may overlap. Karos are rectangular in a preferred embodiment, although in alternative embodiments they can have any shape. The preferred size of a karo is between 0.5 and 2 micrometers for 193 nm exposure wavelength. 
   In a given karo, target points r 1 ,r 2 , . . . , r M  are selected on the edges of target polygons. The target points are used to help encapsulate the design requirements by a mathematical expression. In an embodiment hereof, target points on a polygon are approximately equally spaced by a distance of (k SAMPLE  λ/NA), where k SAMPLE  is a dimensionless factor that is less than 0.25 and preferably larger than 0.1; λ is the exposure wavelength, and NA is the numerical aperture of the lithography projector. In a preferred embodiment hereof, target points are not placed on vertices of target polygons because sharp corners are not printable. 
   In an embodiment hereof, a two-dimensional normal vector n j  is assigned to each target point r j . The normal vector is substantially perpendicular to the edge of the target polygon or the expected wafer pattern. The normal vector points in the direction of increasing image intensity.  FIG. 1  shows a target polygon  110 . In a preferred embodiment, target points  120   a ,  120   b , . . . ,  120   j , . . . are placed on a curve  130  that fits the target polygon  110  except at the vertices. The unit vector that is perpendicular to the tangent of curve  130  at target point  120   j  is n j . In an alternative embodiment, the target points are placed on the target polygon  110  avoiding its vertices, and the unit vector n j  is perpendicular to the edge of the target polygon at target point  120   j.    
   In the following portion of the description, the design requirements for a preferred embodiment will be described in mathematical terms. No process parameter can be held absolutely constant. There is an acceptable range of variation for any quantity that one wishes to keep constant. Let (Δdose) be the accepted range of exposure dose variability. Dose variations can be caused by changes in the thickness, refractive index, or extinction coefficient of the photoresist, or any other film on the wafer. Dose variations can also be caused by temporal or spatial nonuniformity of the exposure intensity. Variations in the post-exposure-bake temperature (PEB) can alter the dose threshold at which the resist dissolves upon development. Therefore, variations in the PEB temperature are equivalent to a dose variation. 
   A goal of design for manufacturability (DFM) is to keep the edge of the pattern that will be printed on the wafer within an acceptable tolerance Δe of each target point when dose varies by Δdose. This requirement can be expressed as a set of inequalities: 
                             U   ⁡     (       r   j     +     Δ   ⁢           ⁢     e   j     ⁢     n   j         )       ≥     t     1   -       Δ   ⁢           ⁢   dose     dose           ;           ⁢     j   =   1       ,   2   ,   …   ⁢           ,   M                     U   ⁡     (       r   j     -     Δ   ⁢           ⁢     e   j     ⁢     n   j         )       ≤     t     1   +       Δ   ⁢   dose     dose           ;           ⁢     j   =   1       ,   2   ,   …   ⁢           ,   M                 (   1   )               
In the above system of inequalities, U(r) is the latent image intensity at a point r ∈ R 2  in the plane of the wafer; n j  is the unit normal of the pattern edge at the j th  target point r j ; t is a threshold in the units of image intensity such that the resist at r dissolves if U(r)&gt;t and does not dissolve if U(r)&lt;t. The inequalities above ensure that the resist edge will not deviate more than a distance of Δe j  from the target point r j  when the dose changes by a fractional amount ±Δdose/dose. The first line in Equation (1) ensures that the edge-placement tolerance is met when the wafer is under exposed by Δdose. The second line in Equation (1) ensures that the edge-placement tolerance is met when the wafer is over exposed by Δdose.
 
   To give a numerical example, the specification can be Δe=5 nm for Δdose/dose=5%. This specification ensures that critical dimension (line width) will not change by more than ±10 nm, and the contribution of the present layer to overlay will not exceed ±5 nm, when the dose changes by ±5%. 
   In a preferred embodiment, the edge placement tolerance Δe j  can be different for each target point r j . For example, in a gate layer of a CMOS ULSI chip, the edge-placement tolerance can be tighter (smaller) at the edges that define the gate-lengths of transistors on a critical circuit, and Δe j  can be larger at the edges of interconnections in the field poly-silicon. The tolerances can be tighter at the edges of contact landing pads whose placement is critical for overlay. The tolerances can be derived from Boolean operations on patterns at multiple layers and user-specified rules. In an alternative embodiment, all edge tolerances Δe j  are the same. 
   Inequality (1) encapsulates the design goals regarding the geometry of the desired pattern to be formed in photoresist, the edge placement tolerance, and the required dose latitude. 
   The latent image intensity is band-limited in the spatial-frequency domain, or equivalently, wave-number domain. The latent image can be expressed as a 2-dimensional Fourier integral:
 
 U ( r )=∫exp( ik·r ) Û ( k ) d   2   k   (2)
 
The Fourier transform variable k ∈ R 2  is a 2-dimensional wave-vector, and the integral is taken over the entire 2-dimensional Euclidian space, and Û(k) is the Fourier transform of U(r). The support of Û(k), that is the closure of the set over which Û(k) takes non-zero values, is:
 
Supp{ Û}={k| ∥k∥≦k   MAX }  (3)
 
 k   MAX =4 πNA/λ   (4)
 
   Equation (4) expresses that the period of the highest spatial-frequency pattern that can be printed by an optical lithography projector is λ/(2NA). 
   If the pattern periodically repeats, then the latent image is a spatially-periodic pattern. In this case, the Fourier integral in Equation (2) reduces to a Fourier series with finitely many terms as shown in Equation (5a). Any portion of an arbitrary pattern can be approximated by a periodic pattern for the purposes of image calculation, by stepping and repeating the portion of interest and some buffer zone around it. 
   
     
       
         
           
             
               
                 
                   
                     
                       
                         U 
                         ⁡ 
                         
                           ( 
                           r 
                           ) 
                         
                       
                       = 
                       
                         
                           ∑ 
                           
                             m 
                             = 
                             
                               - 
                               M 
                             
                           
                           M 
                         
                         ⁢ 
                         
                           
                             ∑ 
                             
                               
                                 n 
                                 = 
                                 
                                   - 
                                   N 
                                 
                               
                               ⁢ 
                               
                                 
 
                               
                               ⁢ 
                               
                                 
                                    
                                   
                                     k 
                                     mn 
                                   
                                    
                                 
                                 ≤ 
                                 
                                   k 
                                   
                                     M 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     AX 
                                   
                                 
                               
                             
                             N 
                           
                           ⁢ 
                           
                             { 
                             
                               
                                 
                                   α 
                                   mn 
                                 
                                 ⁢ 
                                 
                                   cos 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         k 
                                         mn 
                                       
                                       · 
                                       r 
                                     
                                     ) 
                                   
                                 
                               
                               + 
                               
                                 
                                   β 
                                   mn 
                                 
                                 ⁢ 
                                 
                                   sin 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         k 
                                         mn 
                                       
                                       · 
                                       r 
                                     
                                     ) 
                                   
                                 
                               
                             
                             } 
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         k 
                         mn 
                       
                       = 
                       
                         2 
                         ⁢ 
                         
                           π 
                           ⁡ 
                           
                             ( 
                             
                               
                                 m 
                                 
                                   Λ 
                                   x 
                                 
                               
                               , 
                               
                                 n 
                                 
                                   Λ 
                                   y 
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       M 
                       = 
                       
                         ceil 
                         ⁡ 
                         
                           ( 
                           
                             
                               Λ 
                               x 
                             
                             ⁢ 
                             
                               
                                 k 
                                 
                                   M 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   AX 
                                 
                               
                               / 
                               
                                 ( 
                                 
                                   2 
                                   ⁢ 
                                   π 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     
                       N 
                       = 
                       
                         ceil 
                         ⁡ 
                         
                           ( 
                           
                             
                               Λ 
                               y 
                             
                             ⁢ 
                             
                               
                                 k 
                                 
                                   MA 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   X 
                                 
                               
                               / 
                               
                                 ( 
                                 
                                   2 
                                   ⁢ 
                                   π 
                                 
                                 ) 
                               
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
             
             
               
                 ( 
                 
                   5 
                   ⁢ 
                   a 
                 
                 ) 
               
             
           
         
       
     
   
   In Equation (5a), α mn  and β mn  are real-valued Fourier coefficients; Λ x  is the period in the x-direction; Λ y  is the period in the y-direction; m and n are integer indices; ceil(x) stands for the smallest integer that is greater than or equal to x; and k mn ·r denotes the inner-product of the vectors k mn  and r. Although it is not explicitly stated in Equation (5a), it is understood that only linearly independent combinations of sin(k mn ·r) and cos(k mn ·r) are taken in the double summation. That is, if (m,n) is taken in the summation, (−m,−n) is not taken, except when (m,n)=(0,0). The sin(k 00 ·r) term is not taken since that term would equal zero. Therefore, the first line of (5a) can be more explicitly written as: 
   
     
       
         
           
             
               
                 
                   U 
                   ⁡ 
                   
                     ( 
                     r 
                     ) 
                   
                 
                 = 
                 
                   
                     α 
                     00 
                   
                   + 
                   
                     
                       ∑ 
                       
                         
                           n 
                           = 
                           1 
                         
                         
                           
                              
                             
                               k 
                               
                                 0 
                                 ⁢ 
                                 n 
                               
                             
                              
                           
                           ≤ 
                           
                             k 
                             
                               M 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               AX 
                             
                           
                         
                       
                       N 
                     
                     ⁢ 
                     
                       { 
                       
                         
                           
                             α 
                             
                               0 
                               ⁢ 
                               n 
                             
                           
                           ⁢ 
                           
                             cos 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   k 
                                   
                                     0 
                                     ⁢ 
                                     n 
                                   
                                 
                                 · 
                                 r 
                               
                               ) 
                             
                           
                         
                         + 
                         
                           
                             β 
                             
                               0 
                               ⁢ 
                               n 
                             
                           
                           ⁢ 
                           
                             sin 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   k 
                                   
                                     0 
                                     ⁢ 
                                     n 
                                   
                                 
                                 · 
                                 r 
                               
                               ) 
                             
                           
                         
                       
                       } 
                     
                   
                   + 
                   
                     
                       ∑ 
                       
                         m 
                         = 
                         1 
                       
                       M 
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           
                             n 
                             = 
                             
                               - 
                               N 
                             
                           
                           
                             
                                
                               
                                 k 
                                 mn 
                               
                                
                             
                             ≤ 
                             
                               k 
                               
                                 MA 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 X 
                               
                             
                           
                         
                         N 
                       
                       ⁢ 
                       
                         { 
                         
                           
                             
                               α 
                               mn 
                             
                             ⁢ 
                             
                               cos 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     k 
                                     mn 
                                   
                                   · 
                                   r 
                                 
                                 ) 
                               
                             
                           
                           + 
                           
                             
                               β 
                               mn 
                             
                             ⁢ 
                             
                               sin 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     k 
                                     mn 
                                   
                                   · 
                                   r 
                                 
                                 ) 
                               
                             
                           
                         
                         } 
                       
                     
                   
                 
               
             
             
               
                 ( 
                 
                   5 
                   ⁢ 
                   b 
                 
                 ) 
               
             
           
         
       
     
   
   Only the terms that satisfy: 
                       m   2       Λ   x   2       +       n   2       Λ   y   2         ≤       k     MA   ⁢           ⁢   X     2         (     2   ⁢   π     )     2               (   6   )               
are taken in the summations in Equation (5). Equations (5) and (6) assume a rectangular array of unit cells of size Λ x  by Λ y . It is possible to generalize (5) and (6) for arrays that are not rectangular. For example, a honeycomb is not a rectangular array, meaning the centers of its unit cells do not lie on lines that intersect each other at right angles. For simplicity, non-rectangular arrays are not treated.
 
   There are no more than (2M+1)(2N+1) terms in the series in Equation (5b). Most significantly, the latent image can be uniquely reconstructed from no more than (2M+1)(2N+1) real-valued coefficients (α mn  and β mn ). In other words, the latent image is represented by no more than (2M+1)(2N+1) real numbers. 
   The image of a periodic pattern can also be represented by finitely many samples of the image according to the Nyquist Sampling Theorem. The image can be sampled at points on a rectangular grid: 
                         s   pq     =             U   ⁢     (         x   0     +     p   ⁢           ⁢   dx       ,       y   0     +     q   ⁢           ⁢   dy         )       ;             p   =   1     ,   2   ,   …   ⁢           ,     P   ;               q   =   1     ,   2   ,   …   ⁢           ,   Q                       dx   =         Λ   x     P     &lt;     π     k     M   ⁢           ⁢   AX                       dy   =         Λ   y     Q     &lt;     π     k     M   ⁢           ⁢   AX                         (   7   )               
The distances dx and dy are the sampling intervals along the x and y axes, respectively. The integer indices p and q indicate that the image intensity at the point (x 0 +pdx, y 0 +qdy) is s pq . The coordinate (x 0 ,y 0 ) is any convenient origin in the computation domain. According to Nyquist theorem, the samples s pq ; p=1,2, . . . , P; q=1,2, . . . , Q uniquely determine the Fourier coefficients (α mn , β mn ) and vice versa. The Fourier coefficients are related to the samples by the linear equation:
 
                 s   =       [     A   ⁢           ⁢   B     ]     [         α           β         ]             (   8   )               
where s ∈ R (PQ)  is a column vector containing the samples
 
                 s   =     [           s   11               s   21             ⋮             s   PQ           ]             (   9   )               
The vector
 
             [         α           β         ]               
of Fourier coefficients has two partitions:
 
   
     
       
         
           
             
               
                 
                   α 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             α 
                             00 
                           
                         
                       
                       
                         
                           
                             α 
                             01 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             α 
                             
                               0 
                               ⁢ 
                               N 
                             
                           
                         
                       
                       
                         
                           
                             α 
                             
                               1 
                               , 
                               
                                 - 
                                 N 
                               
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             α 
                             
                               M 
                               , 
                               N 
                             
                           
                         
                       
                     
                     ] 
                   
                 
                 ; 
                 
                   β 
                   = 
                   
                     [ 
                     
                       
                         
                           
                               
                           
                         
                       
                       
                         
                           
                             β 
                             01 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             β 
                             
                               0 
                               ⁢ 
                               N 
                             
                           
                         
                       
                       
                         
                           
                             β 
                             
                               1 
                               , 
                               
                                 - 
                                 N 
                               
                             
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             β 
                             
                               M 
                               , 
                               N 
                             
                           
                         
                       
                     
                     ] 
                   
                 
                 ; 
               
             
             
               
                 ( 
                 10 
                 ) 
               
             
           
         
       
     
   
   There are no entries in the column vectors α and β corresponding to the indices m, n for which: 
                 m   2       Λ   x   2       +       n   2       Λ   y   2         &gt;         k     MA   ⁢           ⁢   X     2         (     2   ⁢   π     )     2       .           
The number of entries in
 
                 [         α           β         ]           
are less than or equal to, and typically less than, (2M+1)(2N+1). The coefficient matrix [A B] has two partitions. The entries of partition A and B are:
 
                         A     p   ,     q   ;   m     ,   n       =     cos   (         (       x   0     +   pdx     )     ⁢       2   ⁢   π   ⁢           ⁢   m       Λ   x         +       (       y   0     +   qdy     )     ⁢       2   ⁢   π   ⁢           ⁢   n       Λ   y           )                   B     p   ,     q   ;   m     ,   n       =     sin   (         (       x   0     +   pdx     )     ⁢       2   ⁢   π   ⁢           ⁢   m       Λ   x         +       (       y   0     +   qdy     )     ⁢       2   ⁢   π   ⁢           ⁢   n       Λ   y           )                   (   11   )               
The indices p,q are mapped to a row number and the indices m,n are mapped to a column number. There are no columns in A and B corresponding to the indices m, n for which:
 
                 m   2       Λ   x   2       +       n   2       Λ   y   2         &gt;         k     M   ⁢           ⁢   AX       2   ⁢                   (     2   ⁢   π     )     2       .           
The Fourier coefficients can be obtained from the samples as follows:
 
   
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           α 
                         
                       
                       
                         
                           β 
                         
                       
                     
                     ] 
                   
                   = 
                   Cs 
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   C 
                   = 
                   
                     
                       
                         
                           ( 
                           
                             
                               
                                 [ 
                                 AB 
                                 ] 
                               
                               T 
                             
                             ⁡ 
                             
                               [ 
                               AB 
                               ] 
                             
                           
                           ) 
                         
                         
                           - 
                           1 
                         
                       
                       ⁡ 
                       
                         [ 
                         AB 
                         ] 
                       
                     
                     T 
                   
                 
               
             
             
               
                 ( 
                 12 
                 ) 
               
             
           
         
       
     
   
   The intensity at any point is calculated by the Fourier series: 
   
     
       
         
           
             
               
                 
                   
                     U 
                     ⁡ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       G 
                       ⁡ 
                       
                         ( 
                         
                           x 
                           , 
                           y 
                         
                         ) 
                       
                     
                     ⁢ 
                     s 
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   G 
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               D 
                               ⁡ 
                               
                                 ( 
                                 
                                   x 
                                   , 
                                   y 
                                 
                                 ) 
                               
                             
                           
                           
                             
                               E 
                               ⁡ 
                               
                                 ( 
                                 
                                   x 
                                   , 
                                   y 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       ] 
                     
                     ⁢ 
                     C 
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       D 
                       
                         m 
                         , 
                         n 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         cos 
                         ⁡ 
                         
                           ( 
                           
                             
                               
                                 2 
                                 ⁢ 
                                 π 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 mx 
                               
                               
                                 Λ 
                                 x 
                               
                             
                             + 
                             
                               
                                 2 
                                 ⁢ 
                                 π 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 ny 
                               
                               
                                 Λ 
                                 y 
                               
                             
                           
                           ) 
                         
                       
                       ⁢ 
                       
                         
 
                       
                       ⁢ 
                       
                         
                           E 
                           
                             m 
                             , 
                             n 
                           
                         
                         ⁡ 
                         
                           ( 
                           
                             x 
                             , 
                             y 
                           
                           ) 
                         
                       
                     
                     = 
                     
                       sin 
                       ⁡ 
                       
                         ( 
                         
                           
                             
                               2 
                               ⁢ 
                               π 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               mx 
                             
                             
                               Λ 
                               x 
                             
                           
                           + 
                           
                             
                               2 
                               ⁢ 
                               π 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               ny 
                             
                             
                               Λ 
                               y 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
             
             
               
                 ( 
                 13 
                 ) 
               
             
           
         
       
     
   
   The row vector D has as many entries as the column vector α. The indices m, n are mapped to the column index of D. The row vector E has as many entries as the column vector β. The indices m, n are mapped to the column index of E. The row vectors D and E, and the row vector G depend on the position (x,y) at which the image intensity is evaluated. There are no entries in D and E corresponding to the indices m, n for which: 
   
     
       
         
           
             
               
                 m 
                 2 
               
               
                 Λ 
                 x 
                 2 
               
             
             + 
             
               
                 n 
                 2 
               
               
                 Λ 
                 y 
                 2 
               
             
           
           &gt; 
           
             
               
                 k 
                 
                   MA 
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   X 
                 
                 2 
               
               
                 
                   ( 
                   
                     2 
                     ⁢ 
                     π 
                   
                   ) 
                 
                 2 
               
             
             . 
           
         
       
     
   
   The image of any pattern in a karo can be approximated by the image of a periodic pattern. This is illustrated by  FIG. 2 . A karo  210  is a subset of a target pattern that is evaluated for printability. Each karo is evaluated separately. The union of karos cover the part of the patterned layer that is subject to evaluation, which may be all of a patterned layer. Karos may overlap, or they may be disjoint. Each karo  210  is embedded in a corresponding computation domain  220 . Target polygon  230  is a part of the target layout to be patterned on the wafer. At any point on the boundary of a karo, the distance  240  to the boundary of the computation domain is greater than or equal to the length of optical influence which is on the order of 3λ/NA. The image of the pattern calculated in the karo is not influenced by the pattern outside the computation domain. Therefore, the pattern can be assumed to repeat periodically outside the computation domain. This approximation has negligible influence on the image calculated at points inside the karo, if the buffer distance  240  is large enough. This approximation allows the representation of the image in the karo by a finite Fourier series as in Equation (5). 
   In the preferred embodiment, target points are placed in the karo and no target points are placed outside the karo. The reason for this is that the image calculated outside the karo is potentially inaccurate due to the periodicity assumption. 
   Some polygons in the target layout may intersect the boundary of the karo  210  and/or the boundary of the computation domain  220 . Effectively, in the image calculation, the polygons are clipped or cut at the boundary of the computation domain  220 , and the pattern in the computation domain is stepped and repeated endlessly. No clipping of polygons occurs at the boundary of the karo  210 . 
   In case the pattern is actually periodic, the distance  240  is zero; the karo, the computation domain, and a unit cell of periodic pattern are one and the same. 
   Next, the feasibility of the design requirements will be treated. The design requirements can be expressed as: 
                 Ws   ≤   h           (   14   )                 W   =     [           -     G   ⁡     (       r   1     +     Δ   ⁢           ⁢   e   ⁢           ⁢     n   1         )                   -     G   ⁡     (       r   2     +     Δ   ⁢           ⁢   e   ⁢           ⁢     n   2         )                 ⋮             G   ⁡     (       r   1     -     Δ   ⁢           ⁢   e   ⁢           ⁢     n   1         )                 G   ⁡     (       r   2     -     Δ   ⁢           ⁢   e   ⁢           ⁢     n   2         )               ⋮             -   I             I         ]       ;       ⁢     h   =     [             -   t     /     [     1   -       (     Δ   ⁢           ⁢   dose     )     /   dose       ]                   -   t     /     [     1   -       (     Δ   ⁢           ⁢   dose     )     /   dose       ]               ⋮             t   /     [     1   +       (     Δ   ⁢           ⁢   dose     )     /   dose       ]                 t   /     [     1   +       (     Δ   ⁢           ⁢   dose     )     /   dose       ]               ⋮           0             1   ⁢     U     MA   ⁢           ⁢   X               ]               (   15   )               
In inequality (14), Ws≦h means each entry of the column vector on the left-hand-side is less than or equal to the corresponding entry of the column vector on the right-hand-side. In Equation (15), the number of columns of the identity matrix I is equal to the number of samples (length of vector s). The bold symbol  0  stands for a column vector such that its every entry is 0. The bold symbol  1  stands for a column vector such that its every entry is 1. The positive number U MAX  is an upper bound for intensity at any point in the image. In a preferred embodiment, image intensity is normalized by the image intensity for a clear mask. Therefore, U MAX  is on the order of, but larger than, 1. The image intensity can exceed 1 due to constructive interference, especially when the illumination is highly coherent. For example, for annular illumination, U MAX =1.2 is possible.
 
   Inequality (14), Ws≦h , may or may not have a feasible set. Meaning, there may be no vector of samples s for which Ws≦h is true. In that case, it can be said the inequality Ws≦h and the design requirements are infeasible. If Ws≦h is infeasible, there can be no image, and no photomask design for which the design requirements will be met. Applying sub-resolution assist features, using an alternating-aperture phase-shift mask (AA-PSM), using a custom optimized illumination, or using the double-dipole method will not change the condition of infeasibility. 
   Checking the feasibility of an inequality is a well developed numerical method because it occurs in linear and quadratic programming. Fourier-Motzkin algorithm is one of the algorithms that are used to determine the feasibility of a system of linear inequalities (see, for example, Pablo A. Parrilo and Sanjay Lall, “Linear Inequalities and Elimination,” Workshop presented at the 42nd IEEE Conference on Decision and Control, Maui Hi., USA, Dec. 8th, 2003). In an alternative embodiment, determining the feasibility of Ws≦h is transformed into a linear programming problem by the following transformation: 
   
     
       
         
           
             
               
                 
                   min 
                   ⁢ 
                   t 
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       W 
                       ~ 
                     
                     ⁢ 
                     
                       x 
                       ~ 
                     
                   
                   = 
                   h 
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     x 
                     ~ 
                   
                   ≥ 
                   0 
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     W 
                     ~ 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           W 
                         
                         
                           
                             - 
                             W 
                           
                         
                         
                           I 
                         
                         
                           h 
                         
                       
                     
                     ] 
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     x 
                     ~ 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             s 
                             + 
                           
                         
                       
                       
                         
                           
                             s 
                             - 
                           
                         
                       
                       
                         
                           ξ 
                         
                       
                       
                         
                           t 
                         
                       
                     
                     ] 
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   s 
                   = 
                   
                     
                       s 
                       + 
                     
                     - 
                     
                       s 
                       - 
                     
                   
                 
               
             
             
               
                 ( 
                 16 
                 ) 
               
             
           
         
       
     
   
   In (16), the vectors s, s + , s −  and ξ have the same dimensions. All entries of the vectors s + , s −  and ξ are non-negative; t is a non-negative scalar variable. The constraints of the minimization in (16) have a feasible starting point: 
             x   ~     =       [           s   +               s   -             ξ           t         ]     =       [         0           0           0           1         ]     .             
The vector {tilde over (x)} is not to be confused with the x-coordinates.
 
   Its entries are dimensionless, normalized image intensities. The linear cost function t in (16) attains a unique minimum t* at a solution {tilde over (x)}*. Ws≦h is feasible if and only if all entries of the vector ξ*+ht* are non-negative. The linear programming problem (16) can be solved using the Simplex Method (Linear Programming and its Extensions, George Danzig, Princeton University Press, 1993) or using Interior-point methods (Karmarkar, N. “A New Polynomial-Time Algorithm for Linear Programming.”  Combinatorica  4, 373-395, 1984; S. Mehrotra, “On the implementation of a primal-dual interior point method,” SIAM Journal on Optimization, 2 (1992), pp. 575-601.) 
     FIG. 3  is a flow chart of a routine that can be used for controlling a processor or processors, such as the processors of  FIG. 4 , for implementing an embodiment of the invention. The routine starts at  310 , and block  320  represents selecting a karo and its buffer zone, which together make up a computation domain. Target points are selected in the karo, as represented by  330 . The coefficient matrix and the right hand side of the inequality Ws≦h are formed and stored, as represented by block  340 , according to Equation (15). Determination is then made (decision block  360 ) regarding the feasibility of the inequality Ws≦h. If Ws≦h is not feasible, the karo is marked as not printable (block  370 ) and the result is reported in a log file. If there is a feasible set, the karo is marked as “printable” (block  375 ). Determination is then made (decision block  380 ) as to whether any other region of the target layout remains to be checked. If there are no other regions to be checked, the routine terminates at (block  390 ). Otherwise, block  320  is re-entered where a yet unchecked karo is selected, and the routine repeats until all regions of interest of the target pattern are checked. 
   In an alternative embodiment shown in  FIG. 3   a , at step  370 , when a karo is found to be not printable, (Δdose)/dose, i.e., the fractional dose latitude is reduced as indicated in block  371 ; and the feasibility of Ws≦h is checked again in block  372 . The steps of reducing and checking are repeated until one of the following happens: a dose latitude at which Ws≦h is feasible is found; or a predetermined number of iterations or computation time is reached, as shown in block  373 . The resulting reduced (Δdose)/dose is recorded as shown in block  374 . Thus, in this embodiment, not only is a weak area located, but its dose latitude is also evaluated for the given edge-placement tolerance. 
   In another embodiment shown in  FIG. 3   b , at step  370 , when a karo is found to be not printable, the edge placement tolerance, Δe, is increased as shown in block  375 , and the feasibility of Ws≦h is checked again in block  376 . The steps of increasing and checking are repeated until one of the following happens: an edge-placement tolerance at which Ws≦h is feasible is found; or a predetermined number of iterations or computation time is reached, as indicated in block  377 . The resulting increased Δe is recorded as shown in block  378 . Thus, in this embodiment, not only is a weak area located, but its edge placement error is also evaluated for a given dose latitude. 
   Although k MAX  does not explicitly appear in Equation (15) or (13), the feasibility of Ws≦h is determined by k MAX . This is because k MAX  effects A, B, D, E, and consequently W, through condition (6). In an alternative embodiment, feasibility is determined for a value of k MAX  that is less than 4π NA/λ, such as: 
                     k     M   ⁢           ⁢   AX       =       4   ⁢   π   ⁢           ⁢   NA       λ   ⁡     (     1   +     safety   ⁢           ⁢   margin       )           ⁢     
     ⁢       safety   ⁢           ⁢   margin     &gt;   0             (   17   )               
In this alternative embodiment, when a pattern is determined to be printable, it is printable with a safety margin.
 
   In a preferred embodiment hereof, the printability is checked during the layout and routing of the physical layout of an integrated circuit. If part of any layer of the circuit is found to be not printable, the layout and routing is changed until it becomes printable. 
     FIG. 4  is a block diagram of an apparatus  400  that can be used in practicing an embodiment of the invention. The method described above is coded as instructions, in a machine readable format, stored in a medium  402 , such as a CD, DVD, magnetic disk or tape. The instructions are loaded onto memory  445  of a processor  440  through an I/O device  410 . Alternatively, the instructions can be loaded on the machine via a network. The processor  440  has storage system  420  that stores the target layout and the output data that indicates which regions are unprintable. The processor  440  has user interface  430  such as a keyboard, mouse, and screen. Alternatively, the user interface can be on a remote computer linked to system  400  via a network. The processor  440  has memory  445  to store at least part of the target layout, instructions, and results of intermediate calculations. In a preferred embodiment, processor  440  can be one of many processors  440 ,  460   a , . . . ,  460   z  linked by a high-speed network  470 . Processor  440  acts as a head node, which means, it divides up the computation into parts that can be performed in parallel, and assigns each part to one of the parallel processors  460 . Upon completion of the said part of the computation, processor  460  sends the result through network  470  back to the head node  440 , which collects all such outputs and stores the end result in a file in storage  420 . Head node  440  may assign a new karo to be checked to a processor  440  when it becomes available. Performing the computation in parallel reduces the overall turn-around time of the computation. Each processor  460  has associated memory  465   a , . . . ,  465   z . Optionally, each processor  460  may have its own storage device (not shown). In an alternative embodiment, all of the computation is performed on one computer  440  and further processors  460  are not present. 
   Alternative Embodiment 
   In a preferred embodiment hereof, the left hand side of the inequality is formed in terms of Fourier coefficients, α and β. The intensity at any point (x,y) can be expressed as: 
   
     
       
         
           
             
               
                 
                   
                     U 
                     ⁡ 
                     
                       ( 
                       
                         x 
                         , 
                         y 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               D 
                               ⁡ 
                               
                                 ( 
                                 
                                   x 
                                   , 
                                   y 
                                 
                                 ) 
                               
                             
                           
                           
                             
                               E 
                               ⁡ 
                               
                                 ( 
                                 
                                   x 
                                   , 
                                   y 
                                 
                                 ) 
                               
                             
                           
                         
                       
                       ] 
                     
                     ⁢ 
                     γ 
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   γ 
                   = 
                   
                     [ 
                     
                       
                         
                           α 
                         
                       
                       
                         
                           β 
                         
                       
                     
                     ] 
                   
                 
               
             
             
               
                 ( 
                 18 
                 ) 
               
             
           
         
       
     
   
   D and E are as defined in Equation (13). The intensity at Nyquist sampling points (Equation 9) can be written as
 
s=[AB]γ,
 
   where A and B are defined in Equation (11). In addition to the edge-constraints defined in Equation (1), we can also enforce constraints on the intensity values at Nyquist sampling points to ensure that the image intensity is not marginally close to the threshold t in regions where it is intended to be dark or bright: 
   At the Nyquist points in regions of the image that are intended to be dark, image intensity must be greater than or equal to zero, and less than a pre-selected threshold t L  which in turn is less than or equal to the threshold t in Equation (1). 
   At the Nyquist points in features that are intended to be bright, image intensity must be less than U MAX , and greater than a pre-selected threshold t U  which in turn is greater than or equal to t. 
   If a Nyquist sample point is closer to an edge of a feature than a predetermined distance δ, then the image intensity at that Nyquist sample point is constrained to be between 0 and U MAX . In an alternative embodiment, no constraint is enforced at such a Nyquist sample point. 
   Let s D  be the array (vector) of intensities at the Nyquist points in dark regions, s B  be the array of intensities at those points in bright regions, and s C  be the intensities at those points close to the edges of polygons. We enforce the following constraints on the intensities at the Nyquist sample points:
 
0≦s D ≦t L &lt;t&lt;t U ≦s B ≦U MAX   (19)
 
0≦s C ≦U MAX  
 
   In a preferred embodiment, the thresholds t L  and t U  are selected as follows: 
   
     
       
         
           
             
               
                 
                   
                     t 
                     L 
                   
                   = 
                   
                     t 
                     
                       1 
                       + 
                       
                         η 
                         ⁢ 
                         
                           
                             Δ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             dose 
                           
                           dose 
                         
                       
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     t 
                     U 
                   
                   = 
                   
                     t 
                     
                       1 
                       - 
                       
                         η 
                         ⁢ 
                         
                           
                             Δ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             dose 
                           
                           dose 
                         
                       
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   n 
                   &gt; 
                   1 
                 
               
             
             
               
                 ( 
                 20 
                 ) 
               
             
           
         
       
     
   
   In a preferred embodiment, the dimensionless factor η is an increasing function of the distance δ, which is the smallest possible distance between the Nyquist sampling points designated bright or dark, and an edge of a feature. Typically, η is between 1 and 2. 
   The constraints at the Nyquist sample points, and the edge-constraints in Equation (1) can be put together to form a system of inequalities: 
   
     
       
         
           
             
               
                 
                   
                     
                       K 
                       ⁡ 
                       
                         ( 
                         
                           r 
                           + 
                           
                             Δ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             en 
                           
                         
                         ) 
                       
                     
                     ⁢ 
                     γ 
                   
                   ≤ 
                   
                     
                       1 
                       ⁢ 
                       
                         U 
                         MAX 
                       
                     
                     ⁢ 
                     
                       
 
                     
                     - 
                     
                       K 
                       ⁢ 
                       
                         ( 
                         
                           r 
                           + 
                           
                             Δ 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             en 
                           
                         
                         ) 
                       
                       ⁢ 
                       γ 
                     
                   
                   ≤ 
                   
                     
                       - 
                       t 
                     
                     / 
                     
                       [ 
                       
                         1 
                         - 
                         
                           
                             ( 
                             
                               Δ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               dose 
                             
                             ) 
                           
                           / 
                           dose 
                         
                       
                       ] 
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     K 
                     ⁢ 
                     
                       ( 
                       
                         r 
                         + 
                         
                           Δ 
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           en 
                         
                       
                       ) 
                     
                     ⁢ 
                     γ 
                   
                   ≤ 
                   
                     
                       
                         - 
                         t 
                       
                       / 
                       
                         [ 
                         
                           1 
                           + 
                           
                             
                               ( 
                               
                                 Δ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 dose 
                               
                               ) 
                             
                             / 
                             dose 
                           
                         
                         ] 
                       
                     
                     ⁢ 
                     
                       
 
                     
                     - 
                     
                       
                         K 
                         ⁡ 
                         
                           ( 
                           
                             r 
                             - 
                             
                               Δ 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               en 
                             
                           
                           ) 
                         
                       
                       ⁢ 
                       γ 
                     
                   
                   ≤ 
                   0 
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       H 
                       D 
                     
                     ⁢ 
                     γ 
                   
                   ≤ 
                   
                     
                       t 
                       / 
                       
                         [ 
                         
                           1 
                           + 
                           
                             
                               λ 
                               ⁡ 
                               
                                 ( 
                                 
                                   Δ 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   dose 
                                 
                                 ) 
                               
                             
                             / 
                             dose 
                           
                         
                         ] 
                       
                     
                     ⁢ 
                     
                       
 
                     
                     - 
                     
                       
                         H 
                         D 
                       
                       ⁢ 
                       γ 
                     
                   
                   ≤ 
                   0 
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       H 
                       B 
                     
                     ⁢ 
                     γ 
                   
                   ≤ 
                   
                     
                       1 
                       ⁢ 
                       
                         U 
                         MAX 
                       
                     
                     ⁢ 
                     
                       
 
                     
                     - 
                     
                       
                         H 
                         B 
                       
                       ⁢ 
                       γ 
                     
                   
                   ≤ 
                   
                     
                       - 
                       t 
                     
                     / 
                     
                       [ 
                       
                         1 
                         - 
                         
                           
                             λ 
                             ⁡ 
                             
                               ( 
                               
                                 Δ 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 dose 
                               
                               ) 
                             
                           
                           / 
                           dose 
                         
                       
                       ] 
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     
                       H 
                       C 
                     
                     ⁢ 
                     γ 
                   
                   ≤ 
                   
                     
                       1 
                       ⁢ 
                       
                         U 
                         MAX 
                       
                     
                     ⁢ 
                     
                       
 
                     
                     - 
                     
                       
                         H 
                         C 
                       
                       ⁢ 
                       γ 
                     
                   
                   ≤ 
                   0 
                 
               
             
             
               
                 ( 
                 21 
                 ) 
               
             
           
         
       
     
   
   In the above inequalities, H=[AB], and K(x,y)=[D(x,y) E(x,y)]. The matrix K has as many rows as target points placed at the edges of the features. The matrix H D  has as many rows as the number of Nyquist sampling points in features that are intended to be dark. The matrix H B  has as many rows as the number of Nyquist sampling points in features that are intended to be bright. The matrix H C  has as many rows as the number of Nyquist sampling points that are closer than δ to an edge of a feature. Each line of (20) is a vector (array) of inequalities. By concatenating the rows of (20) in to one matrix inequality, we obtain:
 
Wγ≦h  (22)
 
   W and h in (21) are different from the ones in the embodiment described by Equation (15). 
   The embodiment described by Equations (14-15), and the embodiment described by Equations (20-21) both involve determining the feasibility of a system of inequalities. Feasibility of a system of inequalities can be determined by any of several methods. Among these methods are: Fourier-Motzkin algorithm; linear programming methods such as the Simplex method or the interior-point methods as described above. Below, we describe two algorithms for determining the feasibility of a system of inequalities. Both of these algorithms are more efficient than linear programming. 
   Algorithm (A) for Determining the Feasibility of Wγ≦h 
   We first introduce a vector of non-negative slack variables, ξ, to transform the inequality constraint into an equality constraint:
 
 Wγ+ξ=h;   (23)
 
ξ≧0
 
   The system of inequalities Wγ≦h is feasible if and only if there exists a slack vector ξ of non-negative entries which puts h−ξ in the range-space of matrix W. Thus determining the feasibility of the system of inequalities is the same as determining if these two convex sets intersect:
 
 C   1 ={ξ| ξ≧0} and
 
 C   2 ={ξ| (ξ− h )∈RangeSpace( W )}  (24)
 
   Let&#39;s call the orthogonal projectors of C 1  and C 2 , P 1  and P 2 , respectively. A point in the intersection of two convex sets can be found by successive, alternating projections on to the two convex sets. To form P 2 , we do the QR-factorization of W=QR where columns of Q are orthonormal and R is an upper-triangular, square matrix of size rank(W). (Matrix Computations, G. H. Golub and C. F. Van Loan, Section 6.4, John Hopkins University Press, 1983). The steps of algorithm A are as follows:
         1. Initialize ξ (0) =0, and define the vector θ=(I−QQ T )h   2. Iterate the following until convergence, or until a maximum number of iterations is reached:
 
ξ (k+1)   =P   1 ( P   2 (ξ (k) ))=max(0 , θ+QQ   T ξ (k) );  k= 0,1,2, . . .
    In a preferred embodiment, the criterion is ξ&gt;−ε, where ε is a small normalized-intensity tolerance such as 0.001.   3. Calculate the Fourier coefficients: γ=R −1 Q T (h−ξ) and the image intensity: Hγ.   4. Check if any entries of the inequality ξ&gt;−ε are violated. If so, record or graphically display the corresponding edge target points or Nyquist sample points where the constraints are violated.       

   In case of infeasibility, the convex sets C 1  and C 2  do not intersect, and the above equation converges to a realizable image intensity that is closest to satisfying the constraints. In case of infeasibility, at least some edge target points or Nyquist sample points are flagged. This indicates which features in the layout are infeasible in a location specific manner. 
   Algorithm (B) for Determining the Feasibility of Wγ≦h 
   In an alternative embodiment hereof, feasibility is determined by nonlinear minimization. The quantity that is minimized is: 
   
     
       
         
           
             
               
                 
                   min 
                   γ 
                 
                 ⁢ 
                 
                   
                      
                     
                       min 
                       ⁡ 
                       
                         ( 
                         
                           0 
                           , 
                           
                             h 
                             - 
                             
                               W 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               γ 
                             
                           
                         
                         ) 
                       
                     
                      
                   
                   2 
                 
               
             
             
               
                 ( 
                 25 
                 ) 
               
             
           
         
       
     
   
   In (25), ∥x∥ 2 =x T x stands for the square of the l 2 -norm of a vector. The min operator inside the norm selects, entry-by-entry, the lesser of 0 or the entry of the vector h−Wγ. The minimal value of the norm is 0 if and only if Wγ≦h is feasible. The minimization algorithm can be solved by one of many optimization algorithms. In a preferred embodiment, (25) is minimized by the Gauss-Newton algorithm, which is useful for minimizing sum of squares. To this end, we define the vector-valued residual f(γ) and its Jacobian matrix J: 
   
     
       
         
           
             
               
                 
                   
                     f 
                     ⁡ 
                     
                       ( 
                       γ 
                       ) 
                     
                   
                   = 
                   
                     min 
                     ⁡ 
                     
                       ( 
                       
                         0 
                         , 
                         
                           h 
                           - 
                           
                             W 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             γ 
                           
                         
                       
                       ) 
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     J 
                     ij 
                   
                   = 
                   
                     
                       
                         ∂ 
                         
                           f 
                           i 
                         
                       
                       
                         ∂ 
                         
                           γ 
                           j 
                         
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             0 
                           
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   f 
                                   i 
                                 
                               
                               = 
                               0 
                             
                           
                         
                         
                           
                             
                               - 
                               
                                 W 
                                 ij 
                               
                             
                           
                           
                             otherwise 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 ( 
                 26 
                 ) 
               
             
           
         
       
     
   
   The steps of algorithm B are as follows:
         1. Initialize vector γ 0 . In a preferred embodiment,       

   
     
       
         
           
             γ 
             0 
           
           = 
           
             
               
                 arg 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 min 
               
               Ϛ 
             
             ⁢ 
             
               
                 
                    
                   
                     h 
                     - 
                     
                       W 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       Ϛ 
                     
                   
                    
                 
                 2 
               
               . 
             
           
         
       
     
       
       
         
            In an alternative embodiment, γ 0 =0. 
           2. Iterate the following until convergence or until a maximum number of iterations is reached: 
         
       
     
  
   
     
       
         
           
             
               
                 γ 
                 
                   k 
                   + 
                   1 
                 
               
               = 
               
                 
                   γ 
                   k 
                 
                 + 
                 
                   
                     
                       arg 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       min 
                     
                     Ϛ 
                   
                   ⁢ 
                   
                      
                     
                       
                         
                           J 
                           ⁡ 
                           
                             ( 
                             
                               γ 
                               k 
                             
                             ) 
                           
                         
                         ⁢ 
                         Ϛ 
                       
                       + 
                       
                         f 
                         ⁡ 
                         
                           ( 
                           
                             γ 
                             k 
                           
                           ) 
                         
                       
                     
                      
                   
                 
               
             
             , 
             
               k 
               = 
               0 
             
             , 
             1 
             , 
             2 
             , 
             … 
           
           ⁢ 
           
               
           
         
       
     
       
       
         
           3. Calculate the image intensity Hγ. 
           4. Check if any entries of Wγ≦h are violated. If so, record or graphically display the corresponding edge target points or Nyquist sample points where the constraints are violated. 
         
       
     
  
   In the above iteration, argmin stands for: “the argument that minimizes the following function.” Said minimization, which is a linear least squares problem, is with respect to the dummy vector ζ. The vector γ k  remains constant during the minimization in step 2. The solution of the linear least squares problem 
             min   Ϛ     ⁢              J   ⁡     (     γ   k     )       ⁢   Ϛ     +     f   ⁡     (     γ   k     )                    
is well known (See: Matrix Computations, G. H. Golub and C. F. Van Loan, Chapter 6, John Hopkins University Press, 1983). In a preferred embodiment, the stopping criterion is: ∥f(γ k )∥&lt;ε, for some small, normalized-image intensity ε such as 0.001. In case of infeasibility, at least some edge target points or Nyquist sample points are flagged. This indicates which features in the layout are infeasible in a location-specific manner.
 
   The invention as been described with reference to particular preferred embodiments, but variations within the spirit and scope of the invention will occur to those skilled in the art. For example, the present invention is applicable to reflective as well as transmissive photomasks. Reflective masks are required in extreme-ultra-violet (EUV) wavelengths. EUV lithography operates at about 13.5 nm exposure-wavelength. EUV masks are typically formed by alternately depositing thin films of two materials of dissimilar refractive indices, such as molybdenum and silicon. The periodic structure formed by the stack of alternating films has a stop-band which reflects the incoming radiation. The photomask pattern is etched into an absorptive film, such as aluminum, deposited on top of the reflective stack of alternating films (see: Stephen P. Vernon, et al., “Masks for extreme ultraviolet lithography,” Proc. SPIE Vol. 3546, p. 184-193, December 1998, SPIE Press, Bellingham, Wash.). 
   The present invention is also applicable to mask-less lithography, wherein the photomask is replaced by a spatial light modulator. The spatial light modulator has an array of pixels each of which can modulate light that falls on it. The pixels are controlled according to the photomask data. The spatial light modulator typically comprises an array of micro-machined mirrors. The spatial light modulator is illuminated and its image is projected by an objective on to the wafer (see U.S. Pat. No. 6,700,095). 
   The present invention is also applicable to immersion lithography, wherein a transparent fluid such as water fills the gap between the last lens of the projection objective and the photoresist film on the semiconductor wafer. The refractive index of the fluid is higher than that of air. 
   The present invention is equally applicable to binary masks, attenuated-phase-shift masks, alternating aperture phase-shift masks, and multi-tone masks (masks having at least three portions of distinct transmission or reflection coefficients).