Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

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

DOI: http://dx.doi.org/10.15439/2023F4382

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 183–190 ()

Full text

Abstract. 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.

References

  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.