An Encoded Matrix Algorithm for Subcircuit Extraction Problem
| Autor: | Chia-Shin Ou, 歐家欣 |
|---|---|
| Rok vydání: | 2007 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 95 Subcircuit extraction problem is to find all occurrences of a pattern circuit in a larger main circuit. It is an important topic in many areas of VLSI circuit design. For example, recognition of logic gates in a large circuit can be used to simplify a transistor-level netlist into a gate-level netlist. Besides, the special case of the subcircuit extraction problem when the two involved circuits are of the same size is known as the layout-versus-schematic (LVS) checking in VLSI computer-aided-design flow. In this thesis, we propose an efficient algorithm to solve the subcircuit extraction problem. Our approach encodes the main circuit into a connection matrix consisting of positive integers and then shrinks the matrix by eliminating non-useful rows and columns. Finally, we apply an efficient mechanism to find all subcircuits from the surviving matrix. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|