Canonization of graphs during transistor circuits decompilation
Objectives. The objective of the work is to develop the means for recognition (extraction) of high-level structures in circuits on transistor level. This allows to obtain a representation on logical level, equivalent to original flat description on transistor level. Obtaining such a representation s...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
National Academy of Sciences of Belarus, the United Institute of Informatics Problems
2022-09-01
|
| Series: | Informatika |
| Subjects: | |
| Online Access: | https://inf.grid.by/jour/article/view/1205 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832543465698754560 |
|---|---|
| author | D. I. Cheremisinov L. D. Cheremisinova |
| author_facet | D. I. Cheremisinov L. D. Cheremisinova |
| author_sort | D. I. Cheremisinov |
| collection | DOAJ |
| description | Objectives. The objective of the work is to develop the means for recognition (extraction) of high-level structures in circuits on transistor level. This allows to obtain a representation on logical level, equivalent to original flat description on transistor level. Obtaining such a representation significantly reduces the time to perform VLSI topology check, but also provides the basis for reengineering of integrated circuits and reverse engineering for detecting unauthorized attachments.Methods. Graph based methods and software tools are proposed for recognizing topologically equivalent transistor circuits, which makes it possible to divide the set of subcircuits into topologically equivalent classes. The problem is reduced to checking the isomorphism of labeled graphs defining circuits on transistor level by canonizing them and comparing canonical labeling. The original flat and resulting two-level transistor circuits are presented in SPICE format.Results. The proposed methods are implemented in C++ as a part of a transistor circuit decompilation program for the case without predetermined cell library. The proposed method of canonization of labeled graphs is used: to recognize topologically equivalent subcircuits among functionally equivalent subcircuits that implement logical elements; to split the set of subcircuits not recognized as logical elements into classes of topologically equivalent ones; to verify the results of extraction of the hierarchical circuit at the transistor-logic level relative to the flat circuit at the transistor level.Conclusion. The decompilation program has been tested on practical transistor-level circuits. Experiments indicate that this tool is fast enough to process the circuits with more than one hundred thousand transistors in a few minutes on a personal computer. |
| format | Article |
| id | doaj-art-f3e241cb3ad5411a9ad2b973a013993e |
| institution | Kabale University |
| issn | 1816-0301 |
| language | Russian |
| publishDate | 2022-09-01 |
| publisher | National Academy of Sciences of Belarus, the United Institute of Informatics Problems |
| record_format | Article |
| series | Informatika |
| spelling | doaj-art-f3e241cb3ad5411a9ad2b973a013993e2025-02-03T11:40:30ZrusNational Academy of Sciences of Belarus, the United Institute of Informatics ProblemsInformatika1816-03012022-09-01193253910.37661/1816-0301-2022-19-3-25-391008Canonization of graphs during transistor circuits decompilationD. I. Cheremisinov0L. D. Cheremisinova1The United Institute of Informatics Problems of the National Academy of Sciences of BelarusThe United Institute of Informatics Problems of the National Academy of Sciences of BelarusObjectives. The objective of the work is to develop the means for recognition (extraction) of high-level structures in circuits on transistor level. This allows to obtain a representation on logical level, equivalent to original flat description on transistor level. Obtaining such a representation significantly reduces the time to perform VLSI topology check, but also provides the basis for reengineering of integrated circuits and reverse engineering for detecting unauthorized attachments.Methods. Graph based methods and software tools are proposed for recognizing topologically equivalent transistor circuits, which makes it possible to divide the set of subcircuits into topologically equivalent classes. The problem is reduced to checking the isomorphism of labeled graphs defining circuits on transistor level by canonizing them and comparing canonical labeling. The original flat and resulting two-level transistor circuits are presented in SPICE format.Results. The proposed methods are implemented in C++ as a part of a transistor circuit decompilation program for the case without predetermined cell library. The proposed method of canonization of labeled graphs is used: to recognize topologically equivalent subcircuits among functionally equivalent subcircuits that implement logical elements; to split the set of subcircuits not recognized as logical elements into classes of topologically equivalent ones; to verify the results of extraction of the hierarchical circuit at the transistor-logic level relative to the flat circuit at the transistor level.Conclusion. The decompilation program has been tested on practical transistor-level circuits. Experiments indicate that this tool is fast enough to process the circuits with more than one hundred thousand transistors in a few minutes on a personal computer.https://inf.grid.by/jour/article/view/1205transistor subcircuit extractioncmos circuitsvlsi layout verificationlogical gates recognitiongraph isomorphismspice format |
| spellingShingle | D. I. Cheremisinov L. D. Cheremisinova Canonization of graphs during transistor circuits decompilation Informatika transistor subcircuit extraction cmos circuits vlsi layout verification logical gates recognition graph isomorphism spice format |
| title | Canonization of graphs during transistor circuits decompilation |
| title_full | Canonization of graphs during transistor circuits decompilation |
| title_fullStr | Canonization of graphs during transistor circuits decompilation |
| title_full_unstemmed | Canonization of graphs during transistor circuits decompilation |
| title_short | Canonization of graphs during transistor circuits decompilation |
| title_sort | canonization of graphs during transistor circuits decompilation |
| topic | transistor subcircuit extraction cmos circuits vlsi layout verification logical gates recognition graph isomorphism spice format |
| url | https://inf.grid.by/jour/article/view/1205 |
| work_keys_str_mv | AT dicheremisinov canonizationofgraphsduringtransistorcircuitsdecompilation AT ldcheremisinova canonizationofgraphsduringtransistorcircuitsdecompilation |