Implementation of the method of figurative transformations to minimizing symmetric Boolean functions

Authors

DOI:

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

Keywords:

minimization of symmetric Boolean functions by the method of figurative transformations, singular function, main basis

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 symmetrical Boolean functions in the main and polynomial bases. Prospective reserves in the analytical method were identified, such as simplification of polynomial function conjuncterms using the created equivalent transformations based on the method of inserting the same conjuncterms followed by the operation of super-gluing the variables.

The method of figurative transformations was extended to the process of minimizing the symmetrical Boolean functions with the help of algebra in terms of rules for simplifying the functions of the main and polynomial bases and developed equivalent transformations of conjuncterms. It was established that the simplification of symmetric Boolean functions by the method of figurative transformations is based on a flowchart with repetition, which is the actual truth table of the assigned function. This is a sufficient resource to minimize symmetrical Boolean functions that makes it possible to do without auxiliary objects, such as Karnaugh maps, cubes, etc.

The perfect normal form of symmetrical functions can be represented by binary matrices that would represent the terms of symmetrical Boolean functions and the OR or XOR operation for them.

The experimental study has confirmed that the method of figurative transformations that employs the 2-(n, b)-design, and 2-(n, x/b)-design combinatorial systems improves the efficiency of minimizing symmetrical Boolean functions. Compared to analogs, this makes it possible to enhance the productivity of minimizing symmetrical Boolean functions by 100‒200 %.

There are grounds to assert the possibility of improving the effectiveness of minimizing symmetrical Boolean functions in the main and polynomial bases by the method of figurative transformations. This is ensured, in particular, by using the developed equivalent transformations of polynomial function conjuncterms based on the method of inserting similar conjuncterms 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

Petro Tadeyev, National University of Water and Environmental Engineering

Doctor of Pedagogical Sciences, PhD, Professor

Department of Higher Mathematics

Liudmyla Zubyk, Taras Shevchenko National University of Kyiv

PhD, Associate Professor

Department of Software Systems and Technologies

Stepaniia Babych, Rivne State University of Humanities

PhD, Associate Professor

Department of Information and Communication Technologies and Methods of Teaching Informatics

Yuliia Mala, University of Customs and Finance

PhD

Department of Computer Science and Software Engineering

Oksana Voitovych, Rivne State University of Humanities

Doctor of Pedagogical Sciences, Associate Professor

Department of Ecology, Geography and Tourism

References

  1. Shannon, C. E. (1938). A symbolic analysis of relay and switching circuits. Electrical Engineering, 57 (12), 713–723. doi: https://doi.org/10.1109/ee.1938.6431064
  2. Avgul', L. B., Petrochenko, A. S. (1989). Dekompozitsiya simmetricheskih bulevyh funktsiy i bulevyh funktsiy s chastichnoy simmetriey v bazise monotonnyh funktsiy. Kibernetika i sistemniy analiz, 3, 26–40.
  3. Sasao, T. (1993). FPGA Design by Generalized Functional Decomposition. Logic Synthesis and Optimization, 233–258. doi: https://doi.org/10.1007/978-1-4615-3154-8_11
  4. Svirshcheva, E. A. (1988). Strukturniy sintez neizomorfnyh sistem s odnorodnymi komponentami. Kharkiv, 256. Available at: http://www.techlibrary.ru/b1/2z1c1j1r2a1f1c1a_3l.2h._2z1t1r1u1l1t1u1r1o2c1k_1s1j1o1t1f1i_1o1f1j1i1p1n1p1r1v1o2c1w_1s1j1s1t1f1n_1s_1p1e1o1p1r1p1e1o2c1n1j_1l1p1n1q1p1o1f1o1t1a1n1j._1998.pdf
  5. Rytsar, B. Ye. (1996). Do formalizatsiyi symetrychnykh lohichnykh funktsiy n zminnykh. Materialy mizhnar. konf. “Suchasni problemy avtomatyzovanoi obrobky i vyrobnytstva radioelektronnykh zasobiv zastosuvannia zasobiv zviazku”. Ch. 2. Lviv-Slavsk, 28–30.
  6. Rytsar, B. Ye. (1999). Dekompozytsiya bulovykh funktsiy metodom q-rozbyttia. Upravlyayushchie sistemy i mashiny, 5, 29–42.
  7. Povarov, G. N. (1960). O gruppovoy invariantnosti bulevyh funktsiy. Primenenie logiki v nauke i tekhnike. Moscow: Izd-vo AN SSSR. Available at: https://www.twirpx.com/file/2906517/
  8. Mukhopadhyay, A. (1963). Detection of Total or Partial Symmetry of a Switching Function with the Use of Decomposition Charts. IEEE Transactions on Electronic Computers, EC-12 (5), 553–557. doi: https://doi.org/10.1109/pgec.1963.263654
  9. Das, S. R., Sheng, C. L. (1971). On Detecting Total or Partial Symmetry of Switching Functions. IEEE Transactions on Computers, C-20 (3), 352–355. doi: https://doi.org/10.1109/t-c.1971.223243
  10. Lupanov, O. B. (1965). Ob odnom podhode k sintezu upravlyayushchih sistem - printsipe lokal'nogo kodirovaniya. Problemy kibernetiki, 14, 31–110. Available at: http://new.math.msu.su/department/dm/dmmc/publ_4.htm
  11. Avgul', L. B. (1996). Polinomial'noe razlozhenie simmetricheskih bulevyh funktsiy tablichnym metodom. Kibernetika i sistemnyy analiz, 6, 59–71.
  12. Rytsar, B. E. (1997). Metod minimizatsii bulevyh funktsiy. Problemy upravleniya i informatiki,2, 100–113.
  13. Paulin, O. N., Lyahovetskiy, A. M. (2002). Model' i metod proektirovaniya mnogooperandnogo summatora na baze simmetricheskih funktsiy. Tr. mezhdunar. konf. po induktivnomu modelirovaniyu «MKIM – 2002». Lviv, 208–213.
  14. Paulin, O. N., Drozd, Yu. V. (1998). O sinteze logicheskih moduley, opisyvaemyh simmetricheskimi funktsiyami. Mat-ly mezhdunar. NTK «Priborostroenie». Evpatoriya, 189–192.
  15. Schnieber, M., Froehlich, S., Drechsler, R. Depth Optimized Synthesis of Symmetric Boolean Functions. Available at: http://www.informatik.uni-bremen.de/agra/doc/konf/2021_ISVLSI_SymmetricFunctions.pdf
  16. Burmistrov, S. V., Panasco, O. M., Kovalska, N. V. (2018). Matrix method of parallel decomposition for minimization of symmetric boolean functions in the form of extended polynomial. Bulletin of Cherkasy State Technological University, 1, 130–135. doi: https://doi.org/10.24025/2306-4412.1.2018.162604
  17. Papakonstantinou, G. (2014). A parallel algorithm for minimizing esop expressions. Journal of Circuits, Systems and Computers, 23 (01), 1450015. doi: https://doi.org/10.1142/s0218126614500157
  18. Brandão, L. T. A. N., Çalık, Ç., Sönmez Turan, M., Peralta, R. (2019). Upper bounds on the multiplicative complexity of symmetric Boolean functions. Cryptography and Communications, 11 (6), 1339–1362. doi: https://doi.org/10.1007/s12095-019-00377-3
  19. Zhang, J. S., Mishc, A., Brayton, R., Chrzanowska-Jeske, M. (2006). Symmetry detection for large Boolean functions using circuit representation, simulation, and satisfiability. 2006 43rd ACM/IEEE Design Automation Conference. doi: https://doi.org/10.1109/dac.2006.229269
  20. Drechsler, R., Becker, B. (1995). Sympathy: fast exact minimization of fixed polarity Reed-Muller expressions for symmetric functions. Proceedings the European Design and Test Conference. ED&TC 1995. doi: https://doi.org/10.1109/edtc.1995.470414
  21. Drechsler, R. (1997). Pseudo Kronecker expressions for symmetric functions. Proceedings Tenth International Conference on VLSI Design. doi: https://doi.org/10.1109/icvd.1997.568188
  22. Möller, D., Molitor, P., Drechsler, R. (1995). Symmetry Based Variable Ordering for ROBDDs. Logic and Architecture Synthesis, 70–81. doi: https://doi.org/10.1007/978-0-387-34920-6_7
  23. Arnold, R. F., Harrison, M. A. (1963). Algebraic Properties of Symmetric and Partially Symmetric Boolean Functions. IEEE Transactions on Electronic Computers, EC-12 (3), 244–251. doi: https://doi.org/10.1109/pgec.1963.263535
  24. Rytsar, B. Y. (2003). Identification of symmetry of boolean function decomposition cloning method. 6th International Conference on Telecommunications in Modern Satellite, Cable and Broadcasting Service, 2003. TELSIKS 2003. doi: https://doi.org/10.1109/telsks.2003.1246296
  25. 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
  26. 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. doi: https://doi.org/10.15587/1729-4061.2021.229786
  27. Paulin, O. N., Yanko, V. G. (2014). O minimizatsii simmetricheskih bulevyh funktsiy. Konferentsiya «Modern Problems And Ways Of Their Solution In Science, Transport, Production And Education 2014». SWorld.
  28. 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
  29. Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Upravlyayushchie sistemy i mashiny, 2, 39–57. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87194
  30. Yablonskiy, S. V. (1986). Vvedenie v diskretnuyu matematiku. Moscow: Nauka, 384. Available at: https://stugum.files.wordpress.com/2014/03/yablonskiy-vvedenie-v-diskretnuyu-matematiku.pdf
  31. Rytsar, B. Y. (2019). A New Method for Symmetry Recognition in Boolean Functions Based on the Set-Theoretical Logic Differentiation. I. Control Systems and Computers, 4 (282), 3–13. doi: https://doi.org/10.15407/csc.2019.04.003
  32. 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
  33. Zakrevskiy, A. D. (1981). Logicheskiy sintez kaskadnyh skhem. Moscow, 416. Available at: https://urss.ru/cgi-bin/db.pl?lang=Ru&blang=ru&page=Book&id=272497
  34. Barkalov, A. A., Krasichkov, A. A. (2002). Metody dekompozitsii bulevyh funktsiy. Naukovi pratsi DonNTU, 39, 116–121.
  35. Rytsar, B. E. (2009). A new approach to the decomposition of boolean functions. 4. Non-disjoint decomposition: p,q-partition. Kibernetika i sistemniy analiz, 3, 15–41. Available at: http://dspace.nbuv.gov.ua/handle/123456789/44365
  36. Rytsar, B. Ye. (2013). Minimization of logic functions system by konjuncterms parallel splitting method. Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Radioelektronika ta telekomunikatsiyi, 766, 18–27. Available at: http://nbuv.gov.ua/UJRN/VNULPPT_2013_766_6
  37. Viter, V. V., Gur'yanov, A. V., Kozyuminskiy, V. D., Mishchenko, V. A., Tereshko, S. M. (1984). Pat. No. 1228099 SSSR. Chetyrekhvhodoviy odnorazryadniy summator. No. 3696344; declareted: 30.01.1984; published: 30.04.1986. Available at: http://patents.su/3-1228099-chetyrekhvkhodovyjj-odnorazryadnyjj-summator.html
  38. Avgul', L. B., Dubovik, Yu. I., Suprun, V. P., Yakush, V. P. (1986). Pat. No. 1374216 SSSR. Chetyrekhvhodoviy odnorazryadniy summator. No. 4098636; declareted: 30.07.1986; published: 15.02.1988. Available at: https://patents.su/3-1374216-chetyrekhvkhodovyjj-odnorazryadnyjj-summator.html
  39. Avgul', L. B., Suprun, V. P. (1987). Pat. No. 1429108 SSSR. Chetyrekhvhodoviy odnorazryadniy summator. No. 4195013; declareted: 17.02.1987; published: 07.10.1988. Available at: http://patents.su/3-1429108-chetyrekhvkhodovyjj-odnorazryadnyjj-summator.html
  40. Anisimova, L. O., Zemtsova, N. K., Mutihina, O. I., Hlystov, A. V., Chizhuhin, G. N. (1987). Pat. No. 1524045 SSSR. Chetyrekhvhodoviy odnorazryadniy summator. No. 4238062; declareted: 04.05.1987; published: 23.11.1989. Available at: https://patents.su/2-1524045-chetyrekhvkhodovyjj-odnorazryadnyjj-summator.html
  41. Avgul', L. B., Suprun, V. P. (1987). Pat. No. 1479928 SSSR. Chetyrekhvhodoviy odnorazryadniy summator. No. 4306252; declareted: 14.09.1987; published: 15.05.1989. Available at: https://patents.su/2-1479928-chetyrekhvkhodovyjj-odnorazryadnyjj-summator.html
  42. Avgul', L. B., Suprun, V. P. (1988). Pat. No. 1575172 SSSR. Chetyrekhvhodoviy odnorazryadniy summator. No. 4404427; declareted: 05.04.1988; published: 30.06.1990. Available at: https://patents.su/2-1575172-chetyrekhvkhodovyjj-odnorazryadnyjj-summator.html
  43. Avgul', L. B., Suprun, V. P. (1988). Pat. No. 1658145 SSSR. Chetyrekhvhodoviy odnorazryadniy summator. No. 4476179; declareted: 26.08.1988; published: 23.06.1991. Available at: https://findpatent.ru/patent/165/1658145.html
  44. Chizhuhin, G. N. (1989). Pat. No. 1683007 SSSR. Chetyrekhvhodoviy odnorazryadnyy summator. No. 4746424; declareted: 02.10.1989; published: 07.10.1991. Available at: https://patents.su/2-1683007-chetyrekhvkhodovojj-odnorazryadnyjj-summator.html
  45. 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
  46. 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
  47. 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
  48. 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
  49. Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi: https://doi.org/10.15587/2312-8372.2017.108532
  50. Riznyk, V., Solomko, M. (2018). Minimization of conjunctive normal forms of boolean functions by combinatorial method. Technology Audit and Production Reserves, 5 (2 (43)), 42–55. doi: https://doi.org/10.15587/2312-8372.2018.146312
  51. Lobanov, V. I. (2002). Russkaya logika protiv klassicheskoy (azbuka matematicheskoy logiki). Moscow: Sputnik+, 113. Available at: https://rusneb.ru/catalog/000199_000009_002095987/

Downloads

Published

2021-08-30

How to Cite

Solomko, M., Tadeyev, P., Zubyk, L., Babych, S., Mala, Y., & Voitovych, O. (2021). Implementation of the method of figurative transformations to minimizing symmetric Boolean functions . Eastern-European Journal of Enterprise Technologies, 4(4(112), 23–39. https://doi.org/10.15587/1729-4061.2021.239149

Issue

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

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2021 Mykhailo Solomko, Petro Tadeyev, Liudmyla Zubyk, Stepaniia Babych, Yuliia Mala, Oksana Voitovych

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.