Geodesic
Graph methods for recognition of CMOS gates in transistor-level circuits
Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 43-55.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: CMOS transistor circuit, logic gate recognition, SPICE format.
Mots-clés : subcircuit extraction, graph isomorphism 
@article{PDM_2024_2_a4,
     author = {D. I. Cheremisinov and L. D. Cheremisinova},
     title = {Graph methods for recognition of {CMOS} gates in transistor-level circuits},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {43--55},
     publisher = {mathdoc},
     number = {2},
     year = {2024},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/PDM_2024_2_a4/}
}
TY  - JOUR
AU  - D. I. Cheremisinov
AU  - L. D. Cheremisinova
TI  - Graph methods for recognition of CMOS gates in transistor-level circuits
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2024
SP  - 43
EP  - 55
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2024_2_a4/
LA  - en
ID  - PDM_2024_2_a4
ER  - 
%0 Journal Article
%A D. I. Cheremisinov
%A L. D. Cheremisinova
%T Graph methods for recognition of CMOS gates in transistor-level circuits
%J Prikladnaâ diskretnaâ matematika
%D 2024
%P 43-55
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2024_2_a4/
%G en
%F PDM_2024_2_a4
D. I. Cheremisinov; L. D. Cheremisinova. Graph methods for recognition of CMOS gates in transistor-level circuits. Prikladnaâ diskretnaâ matematika, no. 2 (2024), pp. 43-55. http://geodesic.mathdoc.fr/item/PDM_2024_2_a4/

[1] Abadir M. S. and Ferguson J., “An Improved Layout Verification Algorithm (LAVA)”, Proc. EDAC (Glasgow, UK), 1990, 391–395

[2] Baker R., CMOS Circuit Design, Layout, and Simulation, Third Ed., John Wiley Sons, 2010

[3] Kundu S., “A transistor to gate level model extractor for simulation, automatic test pattern generation and verification”, Proc. Int. Test Conf. IEEE (Washington), 1998, 372–381

[4] Hunt V. D., Reengineering: Leveraging the Power of Integrated Product Development, Oliver Wight Publ., Vermont, 1993, 282 pp.

[5] 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., 39:4 (2006), 311–339 | DOI

[6] Zhang N., Wunsch D. C., and Harary F., “The subcircuit extraction problem”, IEEE Potentials, 22:3 (2003), 22–25 | DOI | Zbl

[7] Logic Gate Recognition in Guardian LVS, Silvaco, 2009 http://www.silvaco.com/content/appNotes/iccad/2-003_LogicGates.pdf

[8] Lester A., Bazargan-Sabet P., and Greiner A., “YAGLE, a second generation functional abstractor for CMOS VLSI circuits”, Proc. ICM'98 (Monastir, Tunisia), 1998, 265–268

[9] Ebeling E., “GeminiII: A second generation layout validation program”, Proc. ICCAD-89 (Santa Clara, CA, USA), 1988, 322–325

[10] Ohlrich M., Ebeling C., 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, 31–37 | DOI

[11] Conte D., Foggia P., Sansone C., and Vento M., “Thirty years of graph matching in pattern recognition”, Int. J. Pattern Recognit. Artif. Intell., 18 (2004), 265–298 | DOI

[12] Cheremisinov D. I. and Cheremisinova L. D., “Extracting a logic gate network from a transistor-level CMOS circuit”, Russian Microelectronics, 48:3 (2019), 187–196 | DOI

[13] Cheremisinova L. D., Synthesis and Optimization of Combinational Structures of VLSI, UIIP NAS Belarus Publ., Minsk, 2005 (in Russian)

[14] Hartke S. G. and Radcliffe A. J., McKay's Canonical Graph Labeling Algorithm, 2008 https://api.semanticscholar.org/CorpusID:6454900 | MR

[15] Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman Publ., NY, 1979 | MR | Zbl

[16] McKay B. D., “Practical graph isomorphism”, Congressus Numerantium, 30 (1981), 45–87 | MR | Zbl

[17] Junttila T. and Kaski P., “Engineering an efficient canonical labeling tool for large and sparse graphs”, Proc. ALENEX (New Orleans, LA), 2007, 135–149 | Zbl

[18] Cheremisinov D. and Cheremisinova L., “Subcircuit pattern recognition in transistor level circuits”, Pattern Recognit. Image Anal., 30 (2020), 160–169 | DOI