Boolean Expressions of Rectilinear Polygons with VLSI Applications.
Abstract
This work is devoted to the analysis of some aspects of the problem of mask verification in the design of integrated circuits. Boolean operations on masks - union, intersection, complement - are the fundamental steps in the development of these verification strategies. We first consider the problem of union and intersection of two masks in a rectilinear environment. The input masks are described by means of polygonal circuits. The output mask is the result of the boolean operation and it is always described by means of polygonal circuits. We present a plane sweep technique algorithm that solves this problem in time O(NlogN+k) and using memory O(N+k), where N is the total number of edges that define the polygonal circuits of the two input masks and k is the number of intersection points. The natural generalization of the problem is the construction of the plane regions that verify a boolean expression, whose variables are a set of masks. We first present an algorithm that has O(NlogN+k) running time and uses memory O(Nlogh+k'h+k'), where N is the total number of edges that define the polygonal circuits of all the masks, h the size of the boolean expression and k' is the number of intersection points that are vertices of the polygonal circuits of the output mask. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Nov 01, 1982
- Accession Number
- ADA124691
Entities
People
- Michele Pracchi
Organizations
- University of Illinois Urbana–Champaign