DESIGNING A COMPLEMENTARY DESIGN RULE CHECKER BASED ON A BINARY BALANCED QUAD LIST QUAD TREE

Abstract

An efficient real time VLSI-CAD tool, the complementary design rule checker (CDRC), composed of one interactive phase and one batch phase is presented. It is a general geometrical design rule model which checks some of the layout constraints in the interative phase and the other constraints in the batch phase. Those classified constraints are disjointed, and each one of them should be checked only once either during the interactive or batch phase. This system and the embedded layout editor are designed on the basis of the binary balanced quad list quad tree (BBQLQT) and its region query functions. The BBQLQT is more efficient than the most recently published spatial data structure, the Weyten's quad list quad tree. One day, provided that the BBQLQT has being further improved, the performance of our system will be promoted without giving more additional design effort. This system is therefore proven to be fully modularised and independent of any of the other spatial data structures.