Developing the minimization of a polynomial normal form of boolean functions by the method of figurative transformations

Authors

DOI:

https://doi.org/10.15587/1729-4061.2021.229786

Keywords:

minimization of Boolean functions in the Reed-Muller basis, figurative transformation method, singular function

Abstract

This paper reports a study that has established the possibility of improving the effectiveness of the method of figurative transformations in order to minimize Boolean functions on the Reed-Muller basis. Such potential prospects in the analytical method have been identified as a sequence in the procedure of inserting the same conjuncterms of polynomial functions followed by the operation of super-gluing the variables.

The extension of the method of figurative transformations to the process of simplifying the functions of the polynomial basis involved the developed algebra in terms of the rules for simplifying functions in the Reed-Muller basis. It was established that the simplification of Boolean functions of the polynomial basis by a figurative transformation method is based on a flowchart with repetition, which is actually the truth table of the predefined function. This is a sufficient resource to minimize functions that makes it possible not to refer to such auxiliary objects as Karnaugh maps, Weich charts, cubes, etc.

A perfect normal form of the polynomial basis functions can be represented by binary sets or a matrix that would represent the terms of the functions and the addition operation by module two for them.

The experimental study has confirmed that the method of figurative transformations that employs the systems of 2-(n, b)-design, and 2-(n, x/b)-design in the first matrix improves the efficiency of minimizing Boolean functions. That also simplifies the procedure for finding a minimum function on the Reed-Muller basis. Compared to analogs, this makes it possible to enhance the performance of minimizing Boolean functions by 100‒200 %.

There is reason to assert the possibility of improving the efficiency of minimizing Boolean functions in the Reed-Muller basis by a method of figurative transformations. This is ensured by using more complex algorithms to simplify logical expressions involving a procedure of inserting the same function terms in the Reed-Muller basis, followed by the operation of super-gluing the variables.

Author Biographies

Mykhailo Solomko, National University of Water and Environmental Engineering

PhD, Associate Professor

Department of Computer Engineering

Iuliia Batyshkina, Rivne State University of Humanities

PhD, Associate Professor

Department of Informational and Communal Technologies and Computes Science Teaching Methods

Nataliia Khomiuk, Lesya Ukrainka Volyn National University

PhD

Department of International Economic Relations and Project Management

Yakiv Ivashchuk, National University of Water and Environmental Engineering

PhD

Department of Higher Mathematics

Natalia Shevtsova, Rivne State University of Humanities

PhD

Department of Informatics and Applied Mathematics

References

  1. Rytsar, B. Ye. (2013). A Numeric Set-Theoretical Interpretation of Polynomial Zhegalkin. Upravlinnia systemamy i mashynamy, 1, 11–26. Available at: http://dspace.nbuv.gov.ua/handle/123456789/83125
  2. Sasao, T. (1999). Switching Theory for Logic Synthesis. Springer US, 362. doi: https://doi.org/10.1007/978-1-4615-5139-3
  3. Sasao, T. (1996). Representations of Logic Functions Using EXOR Operators. Representations of Discrete Functions, 29–54. doi: https://doi.org/10.1007/978-1-4613-1385-4_2
  4. Sasao, T. (1997). Easily testable realizations for generalized Reed-Muller expressions. IEEE Transactions on Computers, 46 (6), 709–716. doi: https://doi.org/10.1109/12.600830
  5. Zakrevskiy, A. D., Toporov, N. R. (2003). Polinomial'naya realizatsiya chastichnyh bulevyh funktsiy i sistem. Moscow: Editorial URSS, 200. Available at: https://www.libex.ru/detail/book14536.html
  6. Zakrevskiy, A. D., Pottosin, Yu. V., Cheremisinova, L. D. (2007). Logicheskie osnovy proektirovaniya diskretnyh ustroystv. Moscow: Fizmatlit, 592. Available at: https://www.libex.ru/detail/book852648.html
  7. Fujiwara, H. (1985). Logic testing and design for testability. Cambridge. doi: https://doi.org/10.7551/mitpress/4317.001.0001
  8. Faraj, K. (2011). Design Error Detection and Correction System based on Reed-Muller Matrix for Memory Protection. International Journal of Computer Applications, 34 (8), 42–48. Available at: https://research.ijcaonline.org/volume34/number8/pxc3875929.pdf
  9. Solomko, M. (2021). Developing an algorithm to minimize boolean functions for the visual-matrix form of the analytical method. Eastern-European Journal of Enterprise Technologies, 1 (4 (109)), 6–21. doi: https://doi.org/10.15587/1729-4061.2021.225325
  10. Rytsar, B. (2015). The Minimization Method of Boolean Functionns in Polynomial Set-theoretical Format. Conference: Proc. 24th Inter. Workshop, CS@P’2015. Rzeszow, 130–146. Available at: https://www.researchgate.net/publication/298158364_The_Minimization_Method_of_Boolean_Functionns_in_Polynomial_Set-theoretical_Format
  11. Sampson, M., Kalathas, M., Voudouris, D., Papakonstantinou, G. (2012). Exact ESOP expressions for incompletely specified functions. Integration, 45 (2), 197–204. doi: https://doi.org/10.1016/j.vlsi.2011.10.001
  12. Knysh, D., Dubrova, E. (2011). Rule-based optimization of AND-XOR expressions. Facta Universitatis - Series: Electronics and Energetics, 24 (3), 437–449. doi: https://doi.org/10.2298/fuee1103437k
  13. Bibilo, P. N., Lankevich, Y. Y. (2017). The Use of Zhegalkin Polynomials for Minimization of Multilevel Representations of Boolean Functions Based on Shannon Expansion. Programmnaya Ingeneria, 8 (8), 369–384. doi: https://doi.org/10.17587/prin.8.369-384
  14. Egorova, E. K., Cheburakhin, I. F. (2013). On the minimization of complexity and automation of efficient representation of boolean functions in classes of formulas and circuits. Journal of Computer and Systems Sciences International, 52 (4), 618–627. doi: https://doi.org/10.1134/s1064230713030064
  15. Frantseva, A. S. (2018). An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic Circuits. The Bulletin of Irkutsk State University. Series Mathematics, 25, 144–158. doi: https://doi.org/10.26516/1997-7670.2018.25.144
  16. He, Z., Xiao, L., Huo, Z., Wang, T., Wang, X. (2019). Fast Minimization of Fixed Polarity Reed-Muller Expressions. IEEE Access, 7, 24843–24851. doi: https://doi.org/10.1109/access.2019.2899035
  17. Samofalov, K. G., Romlinkevich, A. M., Valuyskiy, V. N., Kanevskiy, Yu. S., Pinevich, M. M. (1987). Prikladnaya teoriya tsifrovyh avtomatov. Kyiv: Vischa shk. Golovnoe izd-vo, 375. Available at: http://stu.scask.ru/book_pta.php?id=62
  18. Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Upravlyayuschie sistemy i mashiny, 2, 39–57. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87194
  19. Riznyk, V., Solomko, M. (2017). Application of super-sticking algebraic operation of variables for Boolean functions minimization by combinatorial method. Technology Audit and Production Reserves, 6 (2 (38)), 60–76. doi: https://doi.org/10.15587/2312-8372.2017.118336
  20. Akinina, Ju. S., Podvalniy, S. L., Tyurin, S. V. (2016). The application of karnaugh maps for the polinomial transformation of boolean functions. Vestnik Voronezhskogo gosudarstvennogo tehnicheskogo universiteta, 12 (1), 4–7. Available at: https://cyberleninka.ru/article/n/primenenie-kart-karno-dlya-polinomialnogo-preobrazovaniya-bulevyh-funktsiy
  21. Rytsar, B. Ye. (2013). A Numeric Set-Theoretical Interpretation of Reed-Muller Expressions with Fixed and Mixed Polarity. Upravlyayuschie sistemy i mashiny, 3, 30–44. Available at: http://dspace.nbuv.gov.ua/handle/123456789/83164
  22. Tran, A. (1987). Graphical method for the conversion of minterms to Reed-Muller coefficients and the minimisation of exclusive-OR switching functions. IEE Proceedings E Computers and Digital Techniques, 134 (2), 93. doi: https://doi.org/10.1049/ip-e.1987.0016
  23. Rytsar, B. Ye. (2015). A New Method of Minimization of Logical Functions in the Polynomial Set-theoretical Format. 2. Minimization of Complete and Incomplete Functions. Upravlyayuschie sistemy i mashiny, 4, 9–20. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87235
  24. Riznyk, V., Solomko, M. (2018). Research of 5-bit boolean functions minimization protocols by combinatorial method. Technology Audit and Production Reserves, 4 (2 (42)), 41–52. doi: https://doi.org/10.15587/2312-8372.2018.140351
  25. Riznyk, V., Solomko, M., Tadeyev, P., Nazaruk, V., Zubyk, L., Voloshyn, V. (2020). The algorithm for minimizing Boolean functions using a method of the optimal combination of the sequence of figurative transformations. Eastern-European Journal of Enterprise Technologies, 3 (4 (105)), 43–60. doi: https://doi.org/10.15587/1729-4061.2020.206308
  26. Solomko, M., Khomiuk, N., Ivashchuk, Y., Nazaruk, V., Reinska, V., Zubyk, L., Popova, A. (2020). Implementation of the method of image transformations for minimizing the Sheffer functions. Eastern-European Journal of Enterprise Technologies, 5 (4 (107)), 19–34. doi: https://doi.org/10.15587/1729-4061.2020.214899
  27. Mishchenko, A., Perkowski, M. (2001). Fast Heuristic Minimization of Exclusive-Sums-of-Products. Proc. Reed-Muller Inter. Workshop’01, 242–250. Available at: https://www.researchgate.net/publication/2367778_Fast_Heuristic_Minimization_of_Exclusive-Sums-of-Products

Downloads

Published

2021-04-30

How to Cite

Solomko, M., Batyshkina, I., Khomiuk, N., Ivashchuk, Y., & Shevtsova, N. (2021). Developing the minimization of a polynomial normal form of boolean functions by the method of figurative transformations. Eastern-European Journal of Enterprise Technologies, 2(4 (110), 22–37. https://doi.org/10.15587/1729-4061.2021.229786

Issue

Vol. 2 No. 4 (110) (2021): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2021 Mykhailo Solomko, Iuliia Batyshkina, Nataliia Khomiuk, Yakiv Ivashchuk, Natalia Shevtsova

Creative Commons License

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

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.