ІНДЕКСНИЙ МЕТОД МІНІМІЗАЦІЇ БУЛЕВИХ ФУНКЦІЙ
DOI:
https://doi.org/10.24025/2306-4412.2.2023.273763Ключові слова:
метод мінімізації булевих функцій, матричний метод паралельної декомпозиції, результативні рядки булевої функції, розпаралелювання процесу мінімізації, базисний коефіцієнт K, фрактальний комп’ютерАнотація
У роботі представлено новий метод мінімізації, що реалізує булеву функцію у класичній мінімальній формі представлення шляхом направленого перебору можливих шляхів мінімізації за критеріями необхідної і достатньої умови – індексний метод. Цей метод є продовженням еволюційного розвитку методів мінімізації шляхом зменшення значення базисного коефіцієнта К: методу мінімізації по частинах, методу паралельної декомпозиції шляхом зменшення К, матричного методу паралельної декомпозиції. Еволюція методів шляхом зменшення значення базисного коефіцієнта К йде шляхом досконалого вивчення будови та структурної організації множини булевих функцій, детального аналізу сильних і слабких сторін уже існуючих попередніх варіантів методів, виявлення критичних місць, що суттєво сповільнюють процес мінімізації, та пошуку альтернативних шляхів прискорення процесу мінімізації. Індексний метод розроблено на основі використання нового способу запису окремих булевих функцій у вигляді індексів значущих рядків таблиці істинності. Завдяки такій формі запису вдалося як реалізувати сильні сторони, шо використовували попередні методи, так і значно поліпшити слабкі етапи попередніх методів, що в цілому дає великий виграш у часі мінімізації. Перевагою методу є двоетапна мінімізація процесу, що дає можливість безпосередньо не використовувати критерій спрямованого сортування. При формуванні повного списку елементів одразу отримують елементи остаточної відповіді без зазначення проміжних результатів. Структурні елементи методу – повний набір можливих елементів кінцевої відповіді для булевих функцій, що містить одну кількість аргументів для значення базового коефіцієнта K=1...n, – формуються ще до початку виконання методу і використовуються як табличне значення. При реалізації методу в стовпцях таблиці істинності обробляються тільки одиниці без нулів, що зменшує кількість об'єктів обробки. Метод реалізується дворівневою обробкою стовпців – перевіркою необхідних і достатніх умов. Машинна реалізація методу використовує розпаралелювання процесу мінімізації. Все це істотно скорочує час мінімізації – основну цінність, що відрізняє цей метод від інших. Розроблений метод мінімізації є однією зі складових частин створення програмного коду, що є основою розробки фрактального комп’ютера. Головною особливістю фрактального комп’ютера є наявність у його програмному коді фрактальних (негладких) функцій, що дозволить радикально розширити його можливості в окремих областях обчислень. На сьогоднішній день жоден iз сучасних комп'ютерів не використовує ці функції в програмному коді.
Посилання
E. McCluskey, "Minimization of Boolean functions", The Bell System Technical Journal, vol. 35, pp. 1417-1444, Nov. 1956.
W. Quine, "The problem of simplifying truth functions", American Mathematical Monthly, vol. 59, pp. 521-531, 1952.
C. E. Shannon, "A mathematical theory of communication", Bell System Technical Journal, vol. 27, pp. 379-423, 623-656, 1948.
Yu. A. Kochkaryev, N. M. Panteleeva, N. L. Kazarinova, and S. A. Shakun, Classical and alternative minimal forms of logical functions: Reference catalog. Cherkasy: Cherkasy Institute of Management, 1999 [in Ukrainian].
O. P. Pinko, "Minimization of CNF of partially monotone Boolean functions", Dopovidi Natsionalnoi akademii nauk Ukrainy, no. 3, pp. 18-21, 2019 [in Ukrainian].
V. Riznyk, and M. Solomko, "Research of 5-bit boolean functions minimization protocols by combinatorian method", Technology Audit and Production Reserves, vol. 4, iss. 2 (42), pp. 41-52, 2018.
I. P. Chukhrov, "On the minimization of Boolean functions for additive complexity measures", Journal of Applied and Industrial Mathematics, vol. 13, pp. 418-435, 2019.
V. Riznyk, and M. Solomko, "Minimization of Boolean functions by combinatorial method", Technology Audit and Production Reserves, vol. 4, no. 2 (36), pp. 49-64, 2017.
I. P. Chukhrov, "On the complexity of minimizing quasicyclic Boolean functions", Diskretn. Anal. Issled., Open 25 (3), pp. 126-151, 2018 [J. Appl. Indust. Math., vol. 12, pp. 426-441, 2018].
Yu. A. Kochkarev, S. V. Burmistrov, and S. F. Aksyonov, "Minimization of Boolean functions by parts", Radioelektronni ta kompiuterni systemy, no. 4, pp. 110-116, 2012 [in Ukrainian].
Yu. A. Kochkarev, S. V. Burmistrov, and S. F. Aksyonov, "Minimization of partially defined Boolean functions in the orthogonal form of representation", Prykladna radioelektronika, vol. 12, no. 3, pp. 413-420, 2013 [in Ukrainian].
Yu. A. Kochkarev, V. N. Rudnytskyi, and S. V. Burmistrov, Minimization of systems of fully defined Boolean functions in the orthogonal form of representation. Heuristic algorithms and distributed computing in applied problems: Coll. monograph, Prof. Melnikov (Ed.), iss. 2. Vinnitsa, Kharkiv, 2013, pp. 87-100 [in Ukrainian].
S. V. Burmistrov, "Parallel decomposition as the main method of minimizing Boolean functions in the orthogonal form of representation", Visnyk Cherkaskoho derzhavnoho tekhnolohichnoho universytetu, no. 2, pp. 67-73, 2014 [in Ukrainian].
S. V. Burmistrov, and E. N. Panasco, "Parallel decomposition by reducing the value of the basic coefficient K as an alternative method of minimizing Boolean functions", Visnyk Pryazovskoho derzhavnoho tekhnichnoho universytetu. Seriia: Tekhnichni nauky, no. 1, pp. 189-195, 2015 [in Ukrainian].
S. V. Burmistrov, and O. B. Piven, "The matrix method of parallel decomposition as a generalized method of minimization in the orthogonal form of representation", Nauka i tekhnika Povitrianykh Syl Zbroinykh Syl Ukrainy, no. 4 (21), pp. 151-157, 2015 [in Ukrainian].
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
URN
Ліцензія
Авторське право (c) 2023 Сергій Бурмістров, Владислав Хотунов, Марія Захарова, Сергій Михайлюта, Майя Люта
Ця робота ліцензується відповідно до Creative Commons Attribution-NonCommercial 4.0 International License.
Автори, які публікуються в цьому збірнику, погоджуються з наступними умовами:
Автори залишають за собою право на авторство своєї роботи та передають збірнику право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License CC BY-NC, яка дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи в цьому збірнику.
Автори мають право укладати самостійні додаткові угоди щодо неексклюзивного розповсюдження роботи в тому вигляді, в якому її опубліковано цим збірником (наприклад, розміщувати роботу в електронному сховищі установи або публікувати в складі монографії), за умови збереження посилання на першу публікацію роботи в цьому збірнику.
Політика збірника наукових праць дозволяє і заохочує розміщення авторами в мережі Інтернет (наприклад, у сховищах установ або на особистих веб-сайтах) рукопису роботи як до подання цього рукопису до редакції, так і під час його редакційного опрацювання, оскільки це сприяє виникненню продуктивної наукової дискусії та позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).