A New Automatic Logic Interconnection Verification System for VLSI Design

A new VLSI checking program, LIVES (Logic Interconnection VErification System), has been developed. LIVES verifies the geometrical layout data to determine whether or not it correctly reflects the original logic level description. An excellent LIVES feature, which no other programs have possessed yet, is that it can perform the check even when there are no identification marks on each logic gate in layout level description data. This feature is realized by employing new algorithms based on graph theory. In the verification procedure, LIVES Adopts graph isomorphism, which uses the new partitioning methods for vertices, especially tailored for the logic diagram. In the error detection procedure, a graph is divided into subgraphs, based on a new concept, "route-subgraph," and tests for graph isomorphism between subgraphs are performed. These algorithms enable precise and rapid search for any error points in the VLSI design. These new algorithms have been implemented and examined for practical feasibility. Experimental results have ensured that this program can detect errors in the VLSI layout patterns very quickly and precisely. LIVES will be a highly efficient tool in VLSI logic design by using it systematically combined with other CAD programs.