Shape Approximation of Printed Images in VLSI Design

Han, Khine

Permalink

https://hdl.handle.net/2142/11990 Copy

Description

Title

Shape Approximation of Printed Images in VLSI Design

Author(s)

Han, Khine

Issue Date

2009-06-01T16:07:27Z

Director of Research (if dissertation) or Advisor (if thesis)

Wong, Martin D.F.

Department of Study

Electrical and Computer Engineering

Discipline

Electrical and Computer Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• vlsi
• polygon
• approximation

Abstract

Despite application of optical proximity correction (OPC) and resolution enhancement techniques (RET) to improve printing, limitations in lithography and manufacturing processes still lead to undesirable irregularities in printed images on wafer. These post-lithographic distorted shapes are of interest for electrical extraction of printed circuits. To reduce processing time, it is desirable to approximate the resulting two-dimensional contours with simpler polygons. For the case of capacitance extraction algorithms, pairs of outer and inner approximate polygons, which approach the original shape with tighter error restriction, are preferable. Many existing approximation algorithms produce a single approximate polygon per shape, utilizing two main approaches: piecewise linear fit with a fixed number of segments or bounded error, and identification of subsets of dominant points in the resultant polygon. This research presents an approximation algorithm of the former approach using simple one-dimensional methods to efficiently approximate two-dimensional closed shapes by pairs of outer and inner polygons. Each input shape is first decomposed using a greedy strategy into a set of connected functions; the set size is assumed to be small compared to the input size, and each function is assigned an x or y approximation direction. Each decomposed function is approximated with an optimal number of subdivision points within a certain bounded error restricted to one particular assigned direction; the upper- and lower-bound vertices associated with each subdivision are also calculated. A decision method is employed to determine the relative locations of the outer and inner regions of the two-dimensional curve, the results are pieced together to generate the complete outer and inner approximate polygons. The one-dimensional approach guarantees linear-time approximation of each function. Under the assumption of possible decomposition into a small set of connected functions, the total approximation time of the proposed algorithm is linear in the number of input vertices. For verification, the algorithm is applied to several test files containing either post-lithographic or arbitrary two-dimensional closed shapes for several specified bounded error values. A few techniques are also discussed for further performance improvements.

Graduation Semester

2009-5

Permalink

http://hdl.handle.net/2142/11990

Copyright and License Information

Copyright 2009 Khine Han

Owning Collections