Identifying High-Level Components in Combinational Circuits

The problem of finding meaningful subcircuits in a logic layout appears in many contexts in computeraided design. Existing techniques rely upon finding exact matchings of subcircuit structure within the layout. These syntactic techniques fail to identify functionally equivalent subcircuits that are differently implemented, optimized, or otherwise obfuscated. We present a mechanism for identifying functionally equivalent subcircuits that can overcome many of these limitations. Such semantic matching is particularly useful in the field of design recovery. 1 Introduction The identification of meaningful subcircuits within a larger design is of interest in many CAD applications. Of particular interest is the identification of a cluster of connected low-level devices that form a highlevel component. Previous approaches to this problem have relied upon the discovery of subgraph isomorphisms to identify subcircuits [1--3]. While useful in applications such as converting a transistor netlist ..