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

• Autorzy: Mazurkiewicz Tomasz

Identyfikatory

DOI

10.26636/jtit.2020.142520

• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

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

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2020
• Tom: nr 3
• Strony: 67--74
• Opis fizyczny: Bibliogr. 15 poz., rys., tab.

Twórcy

autor

Mazurkiewicz Tomasz

• Faculty of Cybernetics, Military University of Technology, Kaliskiego 2, 00-909 Warsaw, Poland

Bibliografia

• [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: 10.1109/ISMVL.2017.22).
• [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: 10.23919/MIXDES.2019.8787031).
• [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: 10.23919/MIXDES.2019.8787118).
• [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: 10.1109/ISMVL49045.2020.00-16).
• [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
• [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: 10.23919/DATE.2017.7927100).
• [7] H. A. Curtis, New Approach to Design of Switching Circuits, 1st ed. D. Van Nostrand, 1962 (ISBN: 9780442017941).
• [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
• [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: 10.3182/20091006-3-ES-4010.00032).
• [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: 10.1016/j.ejor.2014.09.064).
• [11] The Sage Developers, „SageMath, the Sage Mathematics Software System (Version 8.3)" [Online]. Available: https://www.sagemath.org
• [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 [Online]. Available: https://users.aalto.fi/~pat/cliquer/cliquer fm.pdf
• [13] J. M. Robson, „Finding a maximum independent set in time O(2n=4)", Tech. Rep., LaBRI, Universite Bordeaux, 2001 [Online]. Available: https://www.labri.fr/perso/robson/mis/techrep.html
• [14] D. J. A. Welsh and M. B. Powell, „An upper bound for the chromatic number of a graph and its appli (DOI: 10.1093/comjnl/10.1.85).
• [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 (DOI: 10.18201/ijisae.273053).