Впровадження нестандартної системи для спрощення функцій Пірса-Вебба

Автор(и)

  • Михайло Тимофійович Соломко Національний університет водного господарства та природокористування, Україна https://orcid.org/0000-0003-0168-5657
  • Петро Олександрович Тадеєв Національний університет водного господарства та природокористування, Україна https://orcid.org/0000-0002-2885-6674
  • Микола Степанович Антонюк Рівненський державний гуманітарний університет, Україна https://orcid.org/0000-0002-6888-6392
  • Юлія Анатоліївна Мала Університет митної справи та фінансів, Україна https://orcid.org/0000-0002-2539-4793
  • Степанія Михайлівна Бабич Рівненський державний гуманітарний університет, Україна https://orcid.org/0000-0003-2145-6392
  • Яків Григорович Іващук Національний університет водного господарства та природокористування, Україна https://orcid.org/0000-0003-4899-9303

DOI:

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

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

спрощення ДНФ, функція Пірса-Вебба, базис Пірса-Вебба, нестандартна система, логічна схема, вентилі І-НЕ, АБО-НЕ

Анотація

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

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

Експериментально підтверджено, що нестандартна система дає змогу:

– зменшити алгоритмічну складність спрощення функцій Пірса-Вебба;

– збільшити продуктивність спрощення функцій Пірса-Вебба на 200–300 %;

– демонструвати наочність процесу спрощення функцій;

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

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

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

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

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

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

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

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

Микола Степанович Антонюк, Рівненський державний гуманітарний університет

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

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

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

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

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

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

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

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

Яків Григорович Іващук, Національний університет водного господарства та природокористування

Кандидат фізико-математичних наук

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

Посилання

  1. Pucknell, D. A. (1990). Fundamentals of Digital Logic Design, With VLSI Circuit applications. Prentice Hall, 472.
  2. Mano, M., Kime, C. (2004). Logic and Computer Design Fundamentals. Prentice Hall.
  3. Baranov, S. (2008). Logic and System Design of Digital Systems. Tallinn: TUT Press.
  4. Micheli, G. (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill.
  5. Zakrevskij, A., Pottosin Yu., Cheremisinova, L. (2009). Optimization in Boolean Space. Tallinn: TUT Press.
  6. Baranov, S., Karatkevich, A. (2018). On Transformation of a Logical Circuit to a Circuit with NAND and NOR Gates Only. INTL JOURNAL OF ELECTRONICS AND TELECOMMUNICATIONS, 64 (3), 373–378. Available at: https://journals.pan.pl/dlibra/publication/123535/edition/107750/content
  7. Maxfield, M. (2018). Implementing and Converting Logic Circuits Using Only NAND or NOR Gates. Available at: https://www.eeweb.com/implementing-logic-functions-using-only-nand-or-nor-gates/
  8. Poomiga, M., Ananthi, M., Sinega, M., Aashika, S M., Nambi Rajan, M. (2021). Optimization of simple combinational universal logic gates. International Research Journal of Modernization in Engineering Technology and Science, 03 (08), 1000‒1006. Available at: https://www.irjmets.com/uploadedfiles/paper/volume_3/issue_8_august_2021/15911/final/fin_irjmets1630308031.pdf
  9. Olenev, A., Potekhina, E., Khabarov, A., Zvereva, L. (2024). Information and logical transformations in Schaeffer and Pierce Bases in Maple. ITM Web of Conferences, 59, 02006. https://doi.org/10.1051/itmconf/20245902006
  10. Menshikh, V. V., Nikitenko, V. A. (2022). Minimization of representations of the logical function in schaeffer and pierce bases. Bulletin of the South Ural State University Series “Mathematics. Mechanics. Physics,” 14 (4), 20–27. https://doi.org/10.14529/mmph220403
  11. Barland, I. (2012). An algorithm to implement a boolean function using only NAND's or only NOR's. Rice University. Available at: https://archive.org/details/cnx-org-col10347/page/n1/mode/2up
  12. Rajaei, A., Houshmand, M., Rouhani, M. (2011). Optimization of Combinational Logic Circuits Using NAND Gates and Genetic Programming. Soft Computing in Industrial Applications, 405–414. https://doi.org/10.1007/978-3-642-20505-7_36
  13. Dychka, I. A., Tarasenko, V. P., Onai, M. V. (2019). Osnovy prykladnoi teorii tsyfrovykh avtomativ. Kyiv, 505.
  14. Kalyadin, N. I. (2006). Praktikum po diskretnoy matematike (Chast' IV. Minimizatsiya FAL). Izhevsk: Izd-vo IzhGTU, 48.
  15. 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. https://doi.org/10.15587/2312-8372.2017.118336
  16. Solomko, M., Antoniuk, M., Voitovych, I., Ulianovska, Y., Pavlova, N., Biletskyi, V. (2023). Implementing the method of figurative transformations to minimize partially defined Boolean functions. Eastern-European Journal of Enterprise Technologies, 1 (4 (121)), 6–25. https://doi.org/10.15587/1729-4061.2023.273293
  17. Solomko, M. (2024). Development of a non-standard system for simplifying boolean functions. Eastern-European Journal of Enterprise Technologies, 3 (4 (129)), 6–34. https://doi.org/10.15587/1729-4061.2024.305826
  18. Kondratenko, N. R. (2010). Kompiuternyi praktykum z matematychnoi lohiky. Vinnytsia: VNTU, 117.
  19. 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. https://doi.org/10.15587/2312-8372.2018.146312
  20. Ritsar, B. E. (1997). Metod minimizatsii bulevyh funktsiy. Problemy upravleniya i informatiki, 3, 100–113.
  21. Cheng, D. (2005). Semi-tensor Product of Matrices and its Applications to Dynamic Systems. New Directions and Applications in Control Theory, 61–79. https://doi.org/10.1007/10984413_5
  22. Feng, J., Zhao, R., Cui, Y. (2022). Simplification of logical functions with application to circuits. Electronic Research Archive, 30 (9), 3320–3336. https://doi.org/10.3934/era.2022168
  23. Cortadella, J. (2003). Timing-driven logic bi-decomposition. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 22 (6), 675–685. https://doi.org/10.1109/tcad.2003.811447
  24. Mishchenko, A., Steinbach, B., Perkowski, M. (2001). An algorithm for bi-decomposition of logic functions. Proceedings of the 38th Conference on Design Automation - DAC ’01, 103–108. https://doi.org/10.1145/378239.378353
  25. Chang S.-C., Marek-Sadowdka, M., Hwang, T. (1996). Technology mapping for TLU FPGAs based on decomposition of binary decision diagrams. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15 (10), 1226–1236. https://doi.org/10.1109/43.541442
  26. Pottosin, Yu. V. (2022). Synthesis of combinational circuits by means of bi-decomposition of Boolean functions. Informatics, 19 (1), 7–18. https://doi.org/10.37661/1816-0301-2022-19-1-7-18
  27. 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
  28. Minziuk, V. (2023). Method of minimizing boolean functions for designing digital combinational circuits. Information and Communication Technologies, Electronic Engineering, 3 (1), 146–153. https://doi.org/10.23939/ictee2023.01.146
  29. 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. https://doi.org/10.15587/1729-4061.2020.214899
  30. 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. https://doi.org/10.15587/1729-4061.2021.225325
  31. 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. https://doi.org/10.15587/1729-4061.2020.206308
  32. 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
Впровадження нестандартної системи для спрощення функцій Пірса-Вебба

##submission.downloads##

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

2024-10-31

Як цитувати

Соломко, М. Т., Тадеєв, П. О., Антонюк, М. С., Мала, Ю. А., Бабич, С. М., & Іващук, Я. Г. (2024). Впровадження нестандартної системи для спрощення функцій Пірса-Вебба. Eastern-European Journal of Enterprise Technologies, 5(4 (131), 6–32. https://doi.org/10.15587/1729-4061.2024.312968

Номер

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

Розділ

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

Ліцензія

Авторське право (c) 2024 Mykhailo Solomko, Petro Tadeyev, Mykola Antoniuk, Yuliia Mala, Stepaniia Babych, Yakiv Ivashchuk

Creative Commons License

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

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

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