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

Автор(и)

  • Volodymyr Riznyk Національний університет «Львівська політехніка», вул. С. Бандери, 12, м. Львів, Україна, 79013, Україна https://orcid.org/0000-0002-3880-4595
  • Mykhailo Solomko Національний університет водного господарства та природокористування, вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-0168-5657

DOI:

https://doi.org/10.15587/2312-8372.2017.118336

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

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

Анотація

Розглянуто нову процедуру алгебри логіки – супер-склеювання змінних, яка застосовується при наявності у структурі таблиці істинності повної бінарної комбінаторної системи з повторенням або неповної бінарної комбінаторної системи з повторенням. Ефективність алгебричної операції суперсклеювання змінних суттєво спрощує алгоритм мінімізації булевих функцій, що дозволяє здійснювати ручну мінімізацію функцій з числом змінних до 10.

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

Volodymyr Riznyk, Національний університет «Львівська політехніка», вул. С. Бандери, 12, м. Львів, Україна, 79013

Доктор технічних наук, професор

Кафедра автоматизованих систем управління

Mykhailo Solomko, Національний університет водного господарства та природокористування, вул. Соборна, 11, м. Рівне, Україна, 33028

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

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

Посилання

  1. Quine–McCluskey algorithm. (2017, August 1). Wikipedia. Available at: https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
  2. Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi:10.15587/2312-8372.2017.108532
  3. Solairaju, A., Periyasamy, R. (2011). Optimal Boolean Function Simplification through K-Map using Object-Oriented Algorithm. International Journal of Computer Applications, 15 (7), 28–32. doi:10.5120/1959-2621
  4. Kumar, R., Rawat, S. (2016). Cubical Representation and Minimization through Cubical Technique A Tabular Approach. International Journal of Applied Engineering Research, 11 (7), 4822–4829. Available at: https://www.ripublication.com/ijaer16/ijaerv11n7_27.pdf
  5. Stergiou, S., Daskalakis, K., Papakonstantinou, G. (2004). A Fast and Efficient Heuristic ESOP Minimization Algorithm. Proceedins of the 14th ACM Great Lakes symposium on VLSI – GLSVLSI '04. Boston. doi:10.1145/988952.988971
  6. Dusa, A., Thiem, A. (2015). Enhancing the Minimization of Boolean and Multivalue Output Functions WitheQMC. The Journal of Mathematical Sociology, 39 (2), 92–108. doi:10.1080/0022250x.2014.897949
  7. Voudouris, D., Sampson, M., Papakonstantinou, G. (2005). Exact ESCT minimization for functions of up to six input variables – PRELIMINARY VERSION, 17. Available at: http://mule.cslab.ece.ntua.gr/xor/docs/xmin6.pdf
  8. Valli, M., Periyasamy, R., Amudhavel, J. (2017). A State of Appraoches on Minimization of Boolean Functions. Journal of Advanced Research in Dynamical and Control Systems, 12, 1322–1341. Available at: http://www.jardcs.org/abstract.php?archiveid=1323#
  9. Boyar, J., Peralta, R. (2010). A New Combinational Logic Minimization Technique with Applications to Cryptology. Lecture Notes in Computer Science, 178–189. doi:10.1007/978-3-642-13193-6_16
  10. Eungi, K. (2013). Derivations of Single Hypothetical Don't-Care Minterms Using the Quasi Quine-McCluskey Method. Journal of the Korea Industrial Information Systems Research, 18 (1), 25–35. doi: 10.9723/jksiis.2013.18.1.025
  11. Dubrova, E., Jiang, Y., Brayton, R. (2001). Minimization of Multiple-Valued Functions in Post Algebra, 5. Available at: https://pdfs.semanticscholar.org/e9fa/a422aad8b92c0448eb8d41425852717cb637.pdf
  12. Anjuli, S. A. (2013). 2-Bit Magnitude Comparator Design Using Different Logic Styles. International Journal of Engineering Science Invention, 2 (1), 13–24. Available at: http://www.ijesi.org/papers/Vol(2)1%20(version%202)/C211324.pdf
  13. Buniak, A. (2001). Elektronika ta mikroskhemotekhnika. Kyiv: Aston, 382.
  14. Rytsar, B. Ye. (2013). Minimization of logic functions system by konjuncterms parallel splittingmethod. Bulletin of the Lviv Polytechnic National University. Radio Electronics and Telecommunications, 766, 18–27. Available at: http://nbuv.gov.ua/UJRN/VNULPPT_2013_766_6
  15. Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Upravliaiushchie sistemy i mashiny, 2, 39–57. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87194
  16. Samofalov, K. G., Romlinkevich, A. M., Valuiskii, V. N., Kanevskii, Yu. S., Pinevich, M. M. (1987). Prikladnaia teoriia tsifrovyh avtomatov. Kyiv: Vishcha shkola, 375.
  17. Plehanov, A. (2016, March 8). Simmetrichnye karty kak sredstvo minimizatsii bulevyh funktsii. Geektimes. Available at: https://geektimes.ru/post/272294/
  18. Plehanov, A. (2016, May 5). Eshche raz o minimizatsii bulevyh funktsii. Habrahabr. Available at: https://habrahabr.ru/post/283030/
  19. Triohmernaia karta Karno. (2016, February 9). Cyclowiki. Available at: http://cyclowiki.org/wiki/Трёхмерная_карта_Карно
  20. Karta Karno. (2017, September 30). Wikipedia. Available at: https://ru.wikipedia.org/wiki/Карта_Карно

##submission.downloads##

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

2017-11-30

Як цитувати

Riznyk, V., & Solomko, M. (2017). Застосування алгебричної операції супер-склеювання змінних для мінімізації булевих функцій комбінаторним методом. Technology Audit and Production Reserves, 6(2(38), 60–76. https://doi.org/10.15587/2312-8372.2017.118336

Номер

Том 6 № 2(38) (2017): Інформаційно-керуючі системи

Розділ

Математичне моделювання: Оригінальне дослідження

Ліцензія

Авторське право (c) 2017 Volodymyr Riznyk, Mykhailo Solomko

Creative Commons License

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

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