An efficient VLSI circuit extraction algorithm for transistor-level to gate-level abstraction

This paper proposes an efficient VLSI extraction algorithm to extract a transistor level netlist to a gate level netlist for functional verification and diagnosis. Compared with other reported circuit extraction algorithm, our proposed technique does not require a cell library and is able to generate Boolean equations without the prior knowledge of transistor type or drain/source orientation of the transistors in the netlist. The proposed algorithm firstly transforms the netlist into a matrix. Secondly, the output nodes of different gates are detected using a pre-sorting comparison algorithm. Then, respective pull-up networks (PUNs) and pull-down networks (PDNs) are identified by a depth-first search algorithm. Finally, the function of the PUN/PDN is verified and stored in terms of Boolean equations. The results on 10 standard cells and 6 testing circuits show that the algorithm performs a near-linear time operation. For a 30-transistor standard cell (XOR4), the time required to complete the extraction is 35.4ms, and for a 3639-transistor combinational circuit, the time required to complete the extraction is around 114.4sec. Compared with the reported technique, our proposed algorithm has an average of 8.4% reduction in CPU time.