Application of Graph Theory Algorithms in Non-disjoint Functional Decomposition of Specific Boolean Functions

Authors

  • Tomasz Mazurkiewicz Military University of Technology in Warsaw image/svg+xml

DOI:

https://doi.org/10.26636/jtit.2020.142520

Keywords:

logic synthesis, functional decomposition, non-disjoint decomposition, index generation functions

Abstract

Functional decomposition is a technique that allows to minimize Boolean functions that cannot be optimally minimized using other methods, such as variable reduction and linear decomposition. A heuristic method for finding nondisjoint decomposition has been proposed lately. In this paper, we examine how the usage of different graph theory techniques affects the computation time and the quality of the solution obtained. In total, six different approaches were analyzed. The results presented herein prove the advantages of the proposed approaches, showing that results obtained for standard benchmark M-out-of-20 functions are better than those presented in previous publication. Results obtained for randomly generated functions prove that time complexity and scalability are significantly better when using the heuristic graph coloring algorithm. However, quality of the solution is worse, in general.

Downloads

Download data is not yet available.

References

[1] T. Sasao, „Index generation functions: Minimization methods", In Proc. 47th IEEE Int. Symp. on Multiple-Valued Logic ISMVL 2017, Novi Sad, Serbia, 2017, pp. 197-206. DOI: https://doi.org/10.1109/ISMVL.2017.22
View in Google Scholar

[2] T. Mazurkiewicz and T. Łuba, „Linear and non-linear decomposition of index generation functions", in Proc. 26th Int. Conf. on Mixed Design of Integr. Circ. and Syst. MIXDES 2019, Rzeszów, Poland, 2019, pp. 246-251. DOI: https://doi.org/10.23919/MIXDES.2019.8787031
View in Google Scholar

[3] T. Mazurkiewicz and T. Łuba, „Non-disjoint decomposition Rusing r-admissibility and graph coloring and its application in index generation functions minimization", in Proc. 26th Int. Conf. on Mixed Design of Integr. Circ. and Syst. MIXDES 2019, Rzeszów, Poland, 2019, pp. 252-256. DOI: https://doi.org/10.23919/MIXDES.2019.8787118
View in Google Scholar

[4] T. Mazurkiewicz, „Non-disjoint functional decomposition of index generation functions", in Proc. 50th IEEE Int. Symp. on Multiple-Valued Logic ISMVL 2020, Miyazaki, Japan, 2020, pp. 137-142. DOI: https://doi.org/10.1109/ISMVL49045.2020.00-16
View in Google Scholar

[5] T. Sasao, K. Matsuura, and Y. Iguchi, „A heuristic decomposition of index generation functions with many variables", in Proc. of the 20th Worksh. on Synth. and Syst. Integr. of Mixed Inform. Technol. SASIMI 2016, Kyoto, Japan, 2016 [Online]. Available: http://www.lsi-cad.com/sasao/Papers/files/SASIMI2016.pdf
View in Google Scholar

[6] T. Sasao, K. Matsuura, and Y. Iguchi, „An algorithm to find optimum support-reducing decompositions for index generation functions", In Proc. of Design, Autom. & Test in Europe Conf. & Exhibition DATE 2017, Lausanne, Switzerland, 2017, pp. 812-817. DOI: https://doi.org/10.23919/DATE.2017.7927100
View in Google Scholar

[7] H. A. Curtis, New Approach to Design of Switching Circuits, 1st ed. D. Van Nostrand, 1962 (ISBN: 9780442017941).
View in Google Scholar

[8] J. A. Brzozowski and T. Łuba, „Decomposition of Boolean functions specified by cubes", J. of Multi-Valued Logic & Soft Comput., vol. 9, pp. 377-417, 2003 [Online]. Available: http://maveric.uwaterloo.ca/reports/2003 JMVLSC BrzozowskiLuba.pdf
View in Google Scholar

[9] G. Borowik, T. Łuba, and P. Tomaszewicz, „A notion of r-admissibility and its application in logic synthesis", IFAC Proc. Vol., vol. 42, no. 21, pp. 172-177, 2009. DOI: https://doi.org/10.3182/20091006-3-ES-4010.00032
View in Google Scholar

[10] Q. Wu and J.-K. Hao, „A review on algorithms for maximum clique problems", Eur. J. of Operat. Res., vol. 242, no. 3, pp. 693-709, 2015. DOI: https://doi.org/10.1016/j.ejor.2014.09.064
View in Google Scholar

[11] The Sage Developers, „SageMath, the Sage Mathematics Software System (Version 8.3)" [Online]. Available: https://www.sagemath.org
View in Google Scholar

[12] S. Niskanen and P. R. J. Ostergard, „Cliquer User's Guide, version 1.0", Tech. Rep. T48, Helsinki University of Technology, Department of Electrical and Communications Engineering, Communications Laboratory, Espoo, Finland, 2003.
View in Google Scholar

[13] J. M. Robson, „Finding a maximum independent set in time O(2n=4)", Tech. Rep., LaBRI, Universite Bordeaux, 2001.
View in Google Scholar

[14] D. J. A. Welsh and M. B. Powell, „An upper bound for the chromatic number of a graph and its appli.
View in Google Scholar

[15] M. Aslan and N. A. Baykan, „A performance comparison of graph coloring algorithms", in Proc. Int. Conf. on Adv. Technol. & Sci. ICAT'16, Konya, Turkey, 2016, pp. 266-273.
View in Google Scholar

Downloads

Submitted

2023-05-22

Published

2020-09-30

Issue

No. 3 (2020)

Section

ARTICLES FROM THIS ISSUE

License

Copyright (c) 2020 Journal of Telecommunications and Information Technology

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

How to Cite

[1]
T. Mazurkiewicz, “Application of Graph Theory Algorithms in Non-disjoint Functional Decomposition of Specific Boolean Functions”, JTIT, vol. 81, no. 3, pp. 67–74, Sep. 2020, doi: 10.26636/jtit.2020.142520.