Метод мінімізації булевих функцій з великою кількістю змінних на основі направленого перебору
Анотація
Розвиток обчислювальної техніки напряму залежить від розвитку методів синтезу компонентів цифрової обчислювальної техніки, тому автоматизація процесу спостерігається і при розробці мікросхем. Для синтезу моделей схем широко використовується булева алгебра і однією із проблем, що виникають при цьому, вважається залежність складності реалізації певної схеми від кількості змінних булевої функції, що її реалізує. Виходячи з цього, можна стверджувати, що збільшення кількості змінних у функціях, які потребують мінімізації, вимагає пошуку нових або вдосконалення існуючих методів мінімізації булевих функцій, що будуть простими у застосуванні, наочними та матимуть можливість автоматизувати реалізацію процесу мінімізації. Залишається актуальною задача розробки ефективних методів мінімізації булевих функцій для моделювання схем, що мають лінійну та поліноміальну залежність швидкості моделювання від кількості змінних булевої функції, що реалізується. Об’єкт дослідження – процес мінімізації булевих функцій, які використовуються при побудові схем цифрових автоматів. Метою роботи є практична реалізація методу мінімізації булевих функцій на основі направленого перебору при збільшенні кількості змінних. Задача, яка розглядається в цій роботі, полягає в розробці та реалізації методу мінімізації булевих функцій, який дозволить мінімізувати булеві функції на основі направленого перебору, розрядність яких перевищує десять змінних, а також збільшити ефективність пошуку при склеюванні імплікант з великою невизначеністю на наборах функцій. Оскільки всі існуючі методи мінімізації стикаються з проблемою громіздких обчислень при збільшенні кількості змінних, для дослідження було вибрано саме метод направленого перебору, який є досить ефективним при великій невизначеності на наборах. На основі проведених розрахунків визначено, що розглянутий метод мінімізації булевих функцій дієвий та простий у застосуванні. Основною його перевагою є можливість реалізації засобами обчислювальної техніки, а покладений в основу направлений перебір дозволяє зменшити вимоги до програмно-апаратних ресурсів систем автоматизованого проектування
Ключові слова
метод мінімізації; булеві функції; набір значень функції; направлений перебір
Використані джерела
[1] V. H. Babenko, "A method of increasing the speed of information protection systems based on the use of specialized logical functions", Ph. D. thesis: 05.13.21, Cherkasy, 2009 [in Ukrainian].
[2] IT journal of articles. [Online]. Available: https://www.tutorialspoint.com/automata_ theory/dfa_minimization.htm [in Ukrainian].
[3] 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].
[4] Yu. A. Kochkarev, I. I. Osipenkova, and E. N. Panasko, "Ortogonal forms of presentation of Boolean functions in device blocks", Visnyk Cherkaskogo derzhavnogo tekhnolohichnogo universytetu, special issue, pp. 39-42, 2009.
[5] V. F. Senchukov, and T. V. Denysova, "Minimization of Boolean functions by numbers of argument value sets", Otkrytyie informatsionnyie i kompiuternyie integrirovannyie tekhnologiyi: sci. papers, Kharkiv: Nats. aerokosm. un-t "KhAI", iss. 83, pp. 156-167, 2019 [in Ukrainian].
[6] V. F. Senchukov, and T. V. Denysova, "vminimization of Boolean functions by distance matrix and reduction to a mathematical programming problem", Vidkryti informatsiini ta kompiuterni intehrovani tekhnolohii: coll. of sci. papers, Kharkiv: Nats. aerokosm. un-t "KhAI", iss. 88, pp. 123-133, 2020 [in Ukrainian]. doi: 10.32620/oikit.2020.88.10.
[7] Kh. Faraj, "Design error detection and correction system based on Reed-Muller matrix for memory protection", Inter. J. of Computer Applications (0975-8887), vol. 34, no. 8, pp. 42-55, Nov., 2011. [Online]. Available: https://www.ijcaonline.org/ archives/volume34/number8/4123- 5929. doi: 10.5120/4123-5929.
[8] M. T. Solomko, "Minimization of Boolean functions in polynomial and mixed bases by the method of image transformations", in Twenty-third Int. Sci. and Pract. Seminar Combinatorial Configurations and Their Applications, Zaporizhzhia-Kropyvnytskyi, May 13-15, 2021, pp. 168-174. [Online]. Available: https://zp.edu.ua/uploads/ dept_s&r/2021/conf/1.4/Petrenyuk_ISPS23-proc.pdf [in Ukrainian].
[9] V. Riznyk, and M. Solomko, "Research of 5-bit Boolean functions minimization protocols by combinatorial method", Technology Audit and Production Reserves, vol. 4 (2 (42)), pp. 41-52, 2018. [Online].Available: https://doi.org/10.15587/2312-8372.2018.140351
[10] Yu. A. Kochkarev, S. V. Burmistrov, and S. F. Aksenov, "Minimization of partially defined Boolean functions in an orthogonal form of representation", Prikladnaya radioelektronika, vol. 12, no. 3, pp. 423-430, 2013. [Online]. Available: http://nbuv.gov.ua/ UJRN/Prre_2013_12_3_8 [in Russian].
[11] Yu. A. Kochkarev, S. V. Burmistrov, and S. F. Aksenov, "Minimization of Boolean functions by parts", Radioelektronni i kompiuterni systemy, no. 4, pp. 110-115, 2012. [Online]. Available: http://nbuv.gov.ua/ UJRN/recs_2012_4_18 [in Russian].
[12] S. V. Burmistrov, "Parallel decomposition as the main method of minimizing Boolean functions in an orthogonal form of representation", Visnyk Cherkaskogo derzhavnogo tekhnolohichnogo universytetu, no. 2, pp. 67-73, 2014 [in Ukrainian].
[13] S. V. Burmistrov, O. M. Panasco, and N. V. Kovalska, "A matrix method of parallel decomposition for the minimization of symmetric Boolean functions in the form of an extended polynomial", Visnyk Cherkaskogo derzhavnogo tekhnolohich-nogo universytetu, no. 1, pp. 130-135, 2018. [Online]. Available: https://doi.org/10.24025/ 2306-4412.1.2018.162604 [in Ukrainian].
[14] T. V. Myronyuk, S. V. Sysoenko, V. G. Ba- benko et al., Information Protection Based on Information-Driven Permutation Operations: monograph, Cherkasy State Technol. Univ. Cherkasy, Ukraine: publisher Ye. I. Hordienko, 2021, pp. 103-164 [in Ukrainian]. ISBN 978-966-97302-2-0.
[15] S. G. Semenov, and I. V. Myronets, "Improvement of the method of minimization of Boolean functions under the condition of information redundancy", Systemy upravlinnia, navihatsii ta zviazku, iss. 3 (35), pp. 9299, Poltava: PNTU, 2015 [in Ukrainian].