Впровадження методу образних перетворень для мінімізації функцій Шеффера
DOI:
https://doi.org/10.15587/1729-4061.2020.214899Ключові слова:
метод образних перетворень, мінімізація функцій Шеффера, штрих Шеффера, терм Шеффера, ДНФШ-1, ДНФШ-2Анотація
Проведеними дослідженнями встановлена можливість зменшення обчислювальної складності, збільшення продуктивності мінімізації булевих функцій у класі досконалих нормальних форм функцій алгебри Шеффера методом образних перетворень.
Поширення методу образних перетворень на мінімізацію функцій алгебри Шеффера дає змогу виявляти нові алгебричні правила логічних перетворень. Особливістю спрощення функцій Шеффера на бінарних структурах 2-(n, b)-блок-схем (англ. 2-(n, b)-designs) є виняткові ситуації. Вони мають застосування як при виведенні результату спрощення функцій з бінарної матриці, так і при введенні функції Шеффера до матриці.
Показано, що досконалу нормальну форму n-містної функції Шеффера можна подати бінарними наборами або матрицею. Логічні операції над структурою матриці забезпечують результат спрощення функцій Шеффера. Це дозволяє зосередити принцип мінімізації у межах таблиці істинності заданої функції та обійтись без допоміжних об’єктів, як то карта Карно, діаграми Вейча, таблиці покриття та ін.
Порівняно з аналогами мінімізації функцій алгебри Шеффера розглянутий метод дозволяє:
– зменшити алгоритмічну складність мінімізації досконалих нормальних форм функцій Шеффера (ДНФШ-1 та ДНФШ-2);
– збільшити продуктивність мінімізації функцій алгебри Шеффера на 100–150 %;
– демонструвати наочність процесу мінімізації ДНФШ-1 або ДНФШ-2;
– забезпечити самодостатність методу образних перетворень для мінімізації функцій алгебри Шеффера за рахунок впровадження ознаки мінімальної функції та мінімізації на повній таблиці істинності ДНФШ-1 і ДНФШ-2.
Є підстави стверджувати, що застосування методу образних перетворень для мінімізації функцій алгебри Шеффера виводить проблему мінімізації ДНФШ-1 та ДНФШ-2 на рівень добре дослідженої задачі у класі диз’юнктивно-кон’юнктивних нормальних форм (ДКНФ) булевих функційПосилання
- Pucknell, D. A. (1990). Fundamentals of Digital Logic Design: With VLSI Circuit applications. Prentice Hall, 486.
- Mano, M. M., Kime, C. (2003). Logic and Computer Design Fundamentals. Prentice Hall, 650.
- Baranov, S. (2008). Logic and System Design of Digital Systems. Tallinn: TUT Press.
- De Micheli, G. (1994). Synthesis and Optimization of Digital Circuits. McGraw-Hill, 597.
- Zakrevskij, A., Pottosin, Yu., Cheremisinova, L. (2009). Optimization in Boolean Space. Tallinn: TUT Press. Available at: http://www.ester.ee/record=b2461762*est
- Luba, T. (2000). Synteza układ´ow logicznych. Warszawa: WSISiZ.
- Rawski, M., Łuba, T., Jachna, Z., Tomaszewicz, P. (2005). The Influence of Functional Decomposition on Modern Digital Design Process. Design of Embedded Control Systems, 193–204. doi: https://doi.org/10.1007/0-387-28327-7_17
- Bibilo, N. (2009). Decomposition of Boolean Functions by Means of Solving Logical Equations. Minsk: Belaruskaya Navuka.
- Borowik, G., Łabiak, G., Bukowiec, A. (2015). FSM-Based Logic Controller Synthesis in Programmable Devices with Embedded Memory Blocks. Topics in Intelligent Engineering and Informatics, 123–151. doi: https://doi.org/10.1007/978-3-319-12652-4_8
- 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. doi: https://doi.org/10.15587/1729-4061.2020.206308
- 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. doi: http://doi.org/10.24425/123535
- Maxfield, M. (2018). Implementing Logic Functions Using Only NAND or NOR Gates. Available at: https://www.eeweb.com/implementing-logic-functions-using-only-nand-or-nor-gates/
- An algorithm to implement a boolean function using only NAND's or only NOR's. Available at: https://cnx.org/contents/vJcXn_C0@4.9:vLMEHoQ0@6/An-algorithm-to-implement-a-boolean-function-using-only-NAND-s-or-only-NOR-s
- Kana, A. F. (2008). Implimenting logical circuit using NAND and NOR gate only. Digital Logic Design, 47–54. Available at: http://american.cs.ucdavis.edu/academic/ecs154a.sum14/postscript/cosc205.pdf
- Shaik, E. haq, Rangaswamy, N. (2017). Realization of all-optical NAND and NOR logic functions with photonic crystal based NOT, OR and AND gates using De Morgan’s theorem. Journal of Optics, 47 (1), 8–21. doi: https://doi.org/10.1007/s12596-017-0441-y
- 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. doi: https://doi.org/10.1007/978-3-642-20505-7_36
- Macia, J., Sole, R. (2014). How to Make a Synthetic Multicellular Computer. PLoS ONE, 9 (2), e81248. doi: https://doi.org/10.1371/journal.pone.0081248
- Dychka, I. A., Tarasenko, V. P., Onai, M. V. (2019). Osnovy prykladnoi teoriyi tsyfrovykh avtomativ. Kyiv: KPI im. Ihoria Sikorskoho, 508.
- 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. doi: https://doi.org/10.15587/2312-8372.2018.146312
- 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. doi: https://doi.org/10.15587/2312-8372.2017.118336
- Havrylenko, S. Yu., Klymenko, A. M., Noskov, V. I. (2014). Lohika dyskretnykh avtomativ. Kharkiv, 129. Available at: http://web.kpi.kharkov.ua/otp/wp-content/uploads/sites/152/2016/05/Kompyuterna_logika_2sem_praktikum.pdf
- Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi: https://doi.org/10.15587/2312-8372.2017.108532
- Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Upravlyayushchie sistemy i mashiny, 2, 39–57.
- Riznyk, V., Solomko, M. (2018). Research of 5-bit boolean functions minimization protocols by combinatorial method. Technology Audit and Production Reserves, 4 (2 (42)), 41–52. doi: https://doi.org/10.15587/2312-8372.2018.140351
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Mykhailo Solomko, Nataliia Khomiuk, Yakiv Ivashchuk, Vitalii Nazaruk, Vikroriia Reinska, Liudmyla Zubyk, Anzhela Popova
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
