Home
Authors Papers Year of conference Themes Organizations To MES conference
| On complexity of inverter graphs for Boolean functions of small number of variables |
|
 |
|
|
| Authors |
| | Lozhkin S.A. |
| | Zizov V.S. |
| | Shupletsov M.S. |
| | Zhukov V.V. |
| | Khzmalian D.E. |
| | Belyankov O.O. |
| Date of publication |
| | 2020 |
| DOI |
| | 10.31114/2078-7707-2020-4-95-102 |
|
| Abstract |
| | In this paper, we consider the problem of exact synthesis inverter graphs for Boolean functions of small number of variables. Main task was to construct catalogue of such schemes. This problem is considered for two models of inverter graphs: and-inverter graph and majority-inverter graph. Algorithms for exact synthesis and corresponding software have been developed to solve this problem. These methods include re-writing, SAT-based synthesis, graph enumeration, iterative minimization and can be applied to any inverter graph model. The qualitative analysis of these methods had been performed. Near-optimal inverter graphs for all functions of five or less variables were obtained. We have all optimal majority-inverter graph realizations with complexity equal or less than 4. An upper bound of the complexity for all functions of five variables was established 11 for the MIG model and 17 for the AIG model. The average complexity of majority-inverter graphs in our database is 7.701 and the average complexity of and-inverter graphs is 12.800. As a result, average complexity for MIG model was shown to be approximately 39.8% less than the average complexity of AIG model. An implementation in the MIG model was demonstrated for the single worst-case equivalence class of Boolean functions (Fig. 8). |
| Keywords |
| | methods for exact synthesis, Boolean logic network, Post basis, complexity of Boolean functions, average complexity, majority function, circuit design database. |
| Library reference |
| | Lozhkin S.A., Zizov V.S., Shupletsov M.S., Zhukov V.V., Khzmalian D.E., Belyankov O.O. On complexity of inverter graphs for Boolean functions of small number of variables // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2020. Issue 4. P. 95-102. doi:10.31114/2078-7707-2020-4-95-102 |
| URL of paper |
| | http://www.mes-conference.ru/data/year2020/pdf/D103.pdf |
|
|
