Graph Boolean Operations for Analog IC Mask and Its Application

• 1、Department of Computer Science and Technology

Abstract：An important application of Boolean operations on polygons in EDA field is the parasitic extraction in analog integrated circuit layout. There are parasitic effects in integrated circuit. IC process brings a variety of parasitic components inevitably distributed throughout the chip. The presence of parasitic devices may create false logic switches, which make unintended impacts on circuit performance. It is necessary to extract the parasitic device and carry out circuit simulation to determine whether these parasitic components have an effect on circuit performance. Boolean operation on polygons is a core algorithm in extraction of parasitic devices. Corresponding Boolean operations is carried out based on different rules of the parasitic device extraction. In this paper we aimed at designing and implementing the Boolean operations for large number of graphics in an analog IC layout. We use the edge-based method which is derived from plane sweep algorithm. It defines a Scanbeam to help finishing the Polygon Boolean operation. This method can increase the speed of the graphics operation sharply and greatly speed up its processing power.

Keywords： Analog Integrated Circuitry Parasitic device extraction Polygon Boolean operations Plane sweep technique Scanbeam