XOR-based decomposition and its application in memory-based and reversible logic synthesis

• Autorzy: Mazurkiewicz Tomasz

Identyfikatory

DOI

10.15439/2023F4382

• Języki publikacji: EN

Abstrakty

EN

In this research paper, we propose a novel approach to digital circuit design using XOR-based decomposition. The proposed technique utilizes XOR gates as a fundamental building block for decomposing complex Boolean functions into simpler forms, leading to more efficient and compact digital circuits. We demonstrate the effectiveness of our approach in two different contexts: memory-based logic synthesis and reversible logic synthesis. In particular, we demonstrate that the proposed technique can efficiently reduce the number of input variables, which is a crucial task when using memories in the design. Obtained results prove that the XOR-based approach can efficiently complement variable reduction and dimensionality reduction algorithms. Furthermore, we show its application in generating the XOR-AND-XOR form of a reversible function and demonstrate how to combine it with another technique, i.e., a functional decomposition for reversible logic synthesis

Słowa kluczowe

EN

dimensionality reduction; computer science; Boolean functions; input variables; memory management; logic gate; minimization

PL

redukcja wymiarowości; informatyka; funkcje boolowskie; zmienna wejściowa; zarządzanie pamięcią; bramka logiczna; minimalizacja

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2023
• Tom: Vol. 35
• Strony: 183--190
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

Twórcy

autor

Mazurkiewicz Tomasz

• Cyber Command Warsaw, Poland

• https://orcid.org/0000-0001-7305-2379

Bibliografia

• 1. Bennett C. H., “Logical Reversibility of Computation,” in: IBM Journal of Research and Development, vol. 17, no. 6, pp. 525–532, 1973, https://doi.org/10.1147/rd.176.0525.
• 2. Bernasconi A., Berti A., Ciriani V., Corso G. D. and Fulginiti I., “XOR-AND-XOR Logic Forms for Autosymmetric Functions and Applications to Quantum Computing,” in: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, https://dx.doi.org/10.1109/TCAD.2022.3213214.
• 3. Borowik G. and Łuba T., “Fast Algorithm of Attribute Reduction Based on the Complementation of Boolean Function,” Advanced Methods and Applications in Computational Intelligence, 2014, pp. 25–41, https://dx.doi.org/10.1007/978-3-319-01436-4_2.
• 4. Brayton, R., Mishchenko, A., “ABC: An Academic Industrial-Strength Verification Tool, “ in: Computer Aided Verification. CAV 2010. Lecture Notes in Computer Science, vol 6174. Springer, Berlin, Heidelberg. https://dx.doi.org/10.1007/978-3-642-14295-6_5.
• 5. Czajkowski T. S. and Brown S. D., “Functionally linear decomposition and synthesis of logic circuits for FPGAs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 12, pp. 2236–2249, https://dx.doi.org/10.1109/TCAD.2008.2006144.
• 6. Mazurkiewicz T. and Łuba T., “Linear and Non-linear Decomposition of Index Generation Functions,” in 26th International Conference Mixed Design of Integrated Circuits and Systems (MIXDES), 2019, pp. 246–251, https://dx.doi.org/10.23919/MIXDES.2019.8787031.
• 7. Mazurkiewicz T., “Non-disjoint functional decomposition of index generation functions,” IEEE 50th International Symposium on Multiple-Valued Logic (ISMVL), Miyazaki, Japan, 2020, pp. 137-142, https://dx.doi.org/10.1109/ISMVL49045.2020.00-16.
• 8. Mishchenko A. and Perkowski M., “Fast Heuristic Minimization of Exclusive-Sums-of-Products,” in: 5th International Reed-Muller Workshop, 2001.
• 9. Łuba T., Borowik G. and Jankowski C., “Gate-based decomposition of index generation functions”, in: Proc. SPIE. 10031, Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments 2016. Vol. 10031. SPIE, 2016. pp. 100314A–1–100314A–10, https://dx.doi.org/10.1117/12.2248754.
• 10. Rawski M. and Szotkowski P., “Reversible logic synthesis of boolean functions using functional decomposition,” 22nd International Conference Mixed Design of Integrated Circuits & Systems (MIXDES), Torun, Poland, 2015, pp. 380-385, https://dx.doi.org/10.1109/MIXDES.2015.7208547.
• 11. Sasao T., “Memory-Based Logic Synthesis,” Computer Science, Springer, 2011, https://dx.doi.org/10.1007/978-1-4419-8104-2.
• 12. Sasao T., “Index Generation Functions, Logic Synthesis for Pattern Matching”, EPFL Workshop on Logic Synthesis & Verification, Lausanne, Switzerland, 2015.
• 13. Sasao T., “Index Generation Functions,” Synthesis Lectures on Digital Circuits & Systems, Springer Cham, 2020, https://dx.doi.org/10.1007/978-3-031-79911-2.
• 14. Toffoli, T., “Reversible Computing,” in: Proceedings of the 7th Colloquium on Automata, Languages and Programming, Springer-Verlag, pp. 632–644, http://doi.org/10.1007/3-540-10003-2_104.

Uwagi

1. Main Track Regular Papers

2. Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).