Control Systems and Computers, N1, 2021, Стаття 1
https://doi.org/10.15407/csc.2021.01.003
Rytsar B.Ye., Belovolov А.O. A New Method of the Logical Functions Minimization in the Polynomial Set-Theoretical Format. «Handshaking» Procedure. Control Systems and Computers. 2021. № 1. pp. 3-14.
УДК 519.718
Рицар Б.Є., д.т.н., проф., Національний університет «Львівська політехніка», вул. С.Бандери, 12, Львів 79000, Україна, E–mail: bohdanrytsar@gmail.com,
Бєловолов А.О., Національний університет «Львівська політехніка», вул. С.Бандери, 12, Львів 79000, Україна
Новий метод мінімізації логікових функцій у поліномному теоретико-множинному форматі. 4. Процедура «рукостискання»
Вступ. Однією з причин складності мінімізації логікових функцій у поліномному форматі є те, що відомі процедури спрощення не носять узагальнений характер щодо гемінґової відстані між довільними двома кон’юнктермами різних рангів заданої функції, що не гарантує її остаточну мінімізацію. У відомих публікаціях на аналогічну тему згадана гемінґова відстань не перевищує число 3.
Мета. Метою цієї статті (яка є продовженням опублікованих статей в УСиМ у 2015 (№ 2, 4 і 5)) є розробка такої процедури над двома кон’юнктермами довільних рангів, гемінґова відстань між якими може бути довільною, а утворені внаслідок цього перетворені кон’юнктерми матимуть порівняно нижчі ранги і можуть бути використані для подальшого спрощення заданої функції за правилами, описаними в доведених теоремах (УСиМ № 2 за 2015).
Методи. Запропоновано процедуру так званого «рукостискання» (яка умовно відображає на візерунку заданої функції рух одної вершини до віддаленої другої вершини), що ґрунтується на ітераційному розширенні двох числових кон’юнктермів різних рангів логікової функції, заданої у поліномному теоретико-множинному форматі. При цьому гемінґова відстань між цими кон’юнктермами може бути довільною. Перетворені кон’юнктерми утвореної множини використовуються для подальшого спрощення заданої функції на основі простих теоретико-множинних правил у поліномному форматі.
Результати. На основі процедури «рукостискання» розроблено алгоритм та програму мінімізації логікових функцій у поліномному теоретико-множинному форматі. Проведені на бенчмарках експериментальні дослідження програми ілюструють ефективність нового методу мінімізації логікових функцій у поліномному теоретико-множинному форматі.
Висновок. Запропоновано метод мінімізації логікових функцій у поліномному теоретико-множинному форматі, що ґрунтується на так званій процедурі «рукостискання», яка відображає ітераційне поліномне розширення двох початкових кон’юнктермів довільних рангів, унаслідок якої утворюється деяка множина перетворених кон’юнктермів, що мають нижчі ранги, ніж початкові. Особливість процедури в тому, що гемінґова відстань між цими двома кон’юнктермами може бути довільною, завдяки чому елементи утвореної множини можна використати для подальшої мінімізації заданої функції за певними правилами. Це принципово відрізняє запропонований метод від відомих щодо ефективності мінімізації, що підтверджують наведені приклади та експериментальні дослідження розробленої програми.
Завантажити повний текст! (англійською)
Ключові слова: мінімізація логікової функції, кон’юнктерм, поліномний теоретико-множинний формат, гемінґова відстань, процедура «рукостискання».
Надійшла 24.11.2020
