Show simple item record

dc.contributor.advisorHazlewood, Carol
dc.contributor.authorZaporojets, Olga V. ( )
dc.identifier.citationZaporojets, O. V. (2002). Polygon reduction algorithm for layout extraction and parasitic signal calculation (Unpublished thesis). Southwest Texas State University, San Marcos, Texas.
dc.description.abstractThe design of a specific polygon reduction algorithm to be applied to the process of layout extraction is proposed. The algorithm is tested with the Star-RCXT parasitic signal extraction tool and the impact of the reduction algorithm is measured and analyzed. There are many polygon reduction algorithms but they all are application specific and not particularly suitable for the extraction tool. The research objective is to generate a reduction algorithm which may be used by any Electric Design Automation (EDA) layout extraction tool and which most effectively achieves a goal of maximum reduction of the number of extracted polygons and preserves connectivity and area of the polygons for further processing. The reduction algorithm described in this paper is created as a local greedy method with some history back tracking for the combined error control. It is used with trapezoidation processing, which is the most common way to perform polygon extraction by EDA tools. The reduction method developed is very general yet effective since it allows not only reduction of “not carrying information” trapezoids but trapezoids with a slight topology modification, fixing trapezoids displacements which may result from the lack of precision of a layout tool used to generate data. The trapezoidation and reduction algorithm was implemented in C++ and tested on real design data. The worst time reduction complexity is 0(n2) and the worst time complexity of the trapezoidation and reduction performed together is 0(n2 log2n). The reduction of the number of polygons achieved in the most accurate mode is 73% and it may be much higher if the less accurate mode is used. The accuracy tests displayed that extracted data produced using reduction algorithm is identical to the extraction data produced without reduction. Total reduction of the parasitic signal extraction time of the designs in the most accurate reduction mode is approximately 26%, which is very significant for the tape out time constraints in the competitive high technology industry. Implemented as a “stand alone” tool, the reduction algorithm may be used not only with Star RCXT tool created by Avant!, but with any other extraction tool.
dc.format.extent175 pages
dc.format.medium1 file (.pdf)
dc.subjectComputer algorithms
dc.titlePolygon Reduction Algorithm for Layout Extraction and Parasitic Signal Calculation
txstate.documenttypeThesis Science Texas State University of Computer Science
txstate.departmentComputer Science


This item is restricted to the Texas State University community. TXST affiliated users can access the item with their NetID and password authentication. Non-affiliated individuals should request a copy through their local library’s interlibrary loan service.

If this is your thesis or dissertation, you can make it open access. This will allow all visitors to view the document. To request open access, fill out the form linked below:

This item appears in the following Collection(s)

Show simple item record