Впровадження методу образних перетворень для мінімізації симетричних булевих функцій

Автор(и)

  • Михайло Тимофійович Соломко Національний університет водного господарства та природокористування, Україна https://orcid.org/0000-0003-0168-5657
  • Петро Олександрович Тадеєв Національний університет водного господарства та природокористування , Україна https://orcid.org/0000-0002-2885-6674
  • Людмила Володимирівна Зубик Київський національний університет імені Тараса Шевченка, Україна https://orcid.org/0000-0002-2087-5379
  • Степанія Михайлівна Бабич Рівненський державний гуманітарний університет , Україна https://orcid.org/0000-0003-2145-6392
  • Юлія Анатоліївна Мала Університет митної справи та фінансів, Україна https://orcid.org/0000-0002-2539-4793
  • Оксана Петрівна Войтович Рівненський державний гуманітарний університет , Україна https://orcid.org/0000-0003-3056-861X

DOI:

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

Ключові слова:

мінімізація симетричних булевих функцій методом образних перетворень, сингулярна функція, основний базис

Анотація

Проведеними дослідженнями встановлена можливість збільшення ефективності методу образних перетворень для мінімізації симетричних булевих функцій в основному та поліномному базисах. Виявлено перспективні резерви аналітичного методу, як то спрощення кон’юнктермів поліномних функцій за допомогою створених рівносильних перетворень на основі методу вставки однакових кон’юнктермів з наступною операцією супер-склеювання змінних.

Поширення методу образних перетворень на процес мінімізації симетричних булевих функцій здійснено за допомогою алгебри у частині правил спрощення функцій основного та поліномного базисів та розроблених рівносильних перетворень кон’юнктермів. Встановлено, що спрощення симетричних булевих функцій методом образних перетворень ґрунтується на блок-схемі з повторенням, якою є власне таблиця істинності заданої функції. Це є достатнім ресурсом для мінімізації симетричних булевих функцій та дозволяє обходитись без допоміжних об’єктів, як то Карти Карно, куби та ін.

Досконалу нормальну форму симетричних функцій можна подати бінарними матрицями, які будуть представляти терми симетричних булевих функцій та операцію OR або XOR для них.

Експериментальними дослідженнями підтверджено, що метод образних перетворень, який використовує комбінаторні системи 2-(n, b)-design та 2-(n, x/b)-design підвищує ефективність мінімізації симетричних булевих функцій. У порівнянні з аналогами це дає змогу підвищити продуктивність мінімізації симетричних булевих функцій на 100–200 %.

Є підстави стверджувати про можливість збільшення ефективності мінімізації симетричних булевих функцій в основному та поліномному базисах методом образних перетворень. Це забезпечується, зокрема шляхом використання розроблених рівносильних перетворень кон’юнктермів поліномних функцій на основі методу вставки однакових кон’юнктермів з наступною операцією супер-склеювання змінних

Біографії авторів

Михайло Тимофійович Соломко, Національний університет водного господарства та природокористування

Кандидат технічних наук, доцент

Кафедра обчислювальної техніки

Петро Олександрович Тадеєв, Національний університет водного господарства та природокористування

Доктор педагогічних наук, кандидат фізико-математичних наук, професор

Кафедра вищої математики

Людмила Володимирівна Зубик, Київський національний університет імені Тараса Шевченка

Кандидат педагогічних наук, доцент

Кафедра програмних систем і технологій

Степанія Михайлівна Бабич, Рівненський державний гуманітарний університет

Кандидат технічних наук, доцент

Кафедра інформаційно-комунікаційних технологій та методики викладання інформатики

Юлія Анатоліївна Мала, Університет митної справи та фінансів

Кандидат технічних наук

Кафедра комп’ютерних наук та інженерії програмного забезпечення

Оксана Петрівна Войтович, Рівненський державний гуманітарний університет

Доктор педагогічних наук, доцент

Кафедра екології, географії та туризму

Посилання

  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/

##submission.downloads##

Опубліковано

2021-08-30

Як цитувати

Соломко, М. Т., Тадеєв, П. О., Зубик, Л. В., Бабич, С. М., Мала, Ю. А., & Войтович, О. П. (2021). Впровадження методу образних перетворень для мінімізації симетричних булевих функцій . Eastern-European Journal of Enterprise Technologies, 4(4(112), 23–39. https://doi.org/10.15587/1729-4061.2021.239149

Номер

Том 4 № 4(112) (2021): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2021 Mykhailo Solomko, Petro Tadeyev, Liudmyla Zubyk, Stepaniia Babych, Yuliia Mala, Oksana Voitovych

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.