A Deterministic Finite Automaton Approach to Design Rule Checking for VLSI

Integrated circuit fabrication technologies place certain restrictions on the relationships with and between mask layers. These "design rules" are intended to describe the class of designs that the fabrication process will correctly implement. The intent of this paper is to describe a general design rule checking algorithm that will take as input the rasterized design and a set of fabrication rules in the form of deterministic finite automation and report any errors in the design layout. This approach allows flexible design rule definitions, technology independent design rule checking code and is ideally suited for hardware implementation.