The paper focuses on the decompilation of a flat transistor circuit in SPICE format into a hierarchical network of logic gates. The problem arises in VLSI layout verification as well as in reverse engineering transistor circuit to redesign integrated circuit and to detect untrusted attachments. The most general case is considered when the extraction of functional level structure from transistor-level circuit is performed without any predetermined cell library. Graph methods for solving some key tasks in this area are proposed. The presented graph methods have been implemented in C++ as a part of a decompilation program, which has been tested using practical transistor-level circuits.
Download file
Counter downloads: 5
- Title Graph methods for recognition of CMOS gates in transistor-level circuits
- Headline Graph methods for recognition of CMOS gates in transistor-level circuits
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 64
- Date:
- DOI 10.17223/20710410/64/4
Keywords
CMOS transistor circuit, subcircuit extraction, logic gate recognition, graph isomorphism, SPICE formatAuthors
References
Abadir M. S. and Ferguson J. An Improved Layout Verification Algorithm (LAVA). Proc. ED AC, Glasgow, UK, 1990, pp. 391-395.
Baker R. CMOS Circuit Design, Layout, and Simulation. Third Ed. John Wiley k, Sons, 2010.
Kundu S. A transistor to gate level model extractor for simulation, automatic test pattern generation and verification. Proc.Int. Test Conf. IEEE, Washington, 1998, pp. 372-381.
Blunt V.D. Reengineering: Leveraging the Power of Integrated Product Development. Vermont, Oliver Wight Publ., 1993. 282 p.
Yang L. and Shi C-J.R. FROSTY: A program for fast extraction of high-level structural representation from circuit description for industrial CMOS circuits.Integr. VLSI J., 2006, vol.39, no. 4, pp. 311-339.
Zhang N., Wunsch D. C., and Harary F. The subcircuit extraction problem. IEEE Potentials, 2003, vol.22, no. 3, pp. 22-25.
http://www.silvaco.com/content/appNotes/iccad/2-003_LogicGates.pdf - Logic Gate Recognition in Guardian LVS, Silvaco, 2009.
Lester A., Bazargan-Sabet P., and Greiner A. YAGLE, a second generation functional abstractor for CMOS VLSI circuits. Proc. ICM'98, Monastir, Tunisia, 1998, pp. 265-268.
Ebeiing E. GeminilL A second generation layout validation program. Proc. ICCAD-89, Santa Clara, CA, USA, 1988, pp. 322-325.
Ohlrich M., Ebeiing G., Ginting E., and Sather L. SubGemini: Identifying subcircuits using a fast subgraph isomorphism algorithm. Proc. 30th ACM/IEEE Design Automation Conf., Dallas, TX, USA, 1993, pp. 31-37.
Conte D., Foggia P., Sansone C., and Vento M. Thirty years of graph matching in pattern recognition.Int. J. Pattern Recognit. Artif.Intell., 2004, vol. 18, pp. 265-298.
Cheremisinov D. I. and Cheremisinova L. D. Extracting a logic gate network from a transistor-level CMOS circuit.Russian Microelectronics, 2019, vol. 48, no.3, pp. 187-196.
Cheremisinova L. D. Sintez i optimizatsiva kombinatsionnvkh struktur SBIS [Synthesis and Optimization of Combinational Structures of VLSI]. UIIP NAS Belarus Publ., Minsk, 2005. (in Russian).
Hartke S. G. and Radcliffe A. J. McKay's Canonical Graph Labeling Algorithm, https://api.semanticscholar.org/CorpusID:6454900, 2008.
Carey M. R. and Johnson D. S.Computers and Intractability: A Guide to the Theory of NP-Completeness. NY, W.H. Freeman Publ., 1979.
McKay B.D. Practical graph isomorphism. Congressus Numerantium, 1981, vol. 30, pp.45-87.
Junttila T. and Kaski P. Engineering an efficient canonical labeling tool for large and sparse graphs. Proc. ALENEX, New Orleans, LA, 2007, pp. 135-149.
Cheremisinov D. and Cheremisinova L. Subcircuit pattern recognition in transistor level circuits. Pattern Recognit. Image Anal., 2020, vol. 30, pp. 160-169.
Graph methods for recognition of CMOS gates in transistor-level circuits | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 64. DOI: 10.17223/20710410/64/4
Download full-text version
Counter downloads: 143