URN: http://vtn.chdtu.edu.uaurn:2306:44551.2018.162604

DOI: https://doi.org/10.24025/2306-4412.1.2018.162604

МАТРИЧНИЙ МЕТОД ПАРАЛЕЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ МІНІМІЗАЦІЇ СИМЕТРИЧНИХ БУЛЕВИХ ФУНКЦІЙ У ВИГЛЯДІ РОЗШИРЕНОГО ПОЛІНОМА

S. V. Burmistrov, O. M. Panasco, N. V. Kovalska

Анотація


В роботі розроблено матричний метод паралельної декомпозиції для мінімізації симетричних булевих функцій в ортогональній формі представлення у вигляді розширеного полінома суми за модулем 2. Симетричні булеві функції характеризуються тим, що вони погано мінімізуються в класичній формі представлення, але добре – поліномами Жегалкіна. Результати, отримані цим методом, порівняно з результатами в поліномі Жегалкіна мають суттєве покращення показників складності реалізації цифрових пристроїв за сумарними коефіцієнтами SL (в 1,49 разу) та SAD (в 2,37 разу) за рахунок незначного погіршення сумарного
коефіцієнта SS (погіршення в 1,293 разу), що не є таким значущим при розробці таких цифрових пристроїв, як коефіцієнти SL і SAD. Також за рахунок поляризації входів булевих функцій цей метод може бути використано як один із складових чинників повного матричного методу паралельної декомпозиції для отримання комплексної мінімальної форми булевих функцій, що має кращі показники складності реалізації, ніж класичні форми представлення булевих функцій. Цей метод дає можливість отримувати для булевих функцій кілька результатів з однаковими показниками складності реалізації, що є суттєвим при мінімізації систем булевих функцій. Суттєвою особливістю методу є застосування вже готових
розширених матриць і таблиць повного переліку кон’юнктивних наборів, що суттєво прискорює процес мінімізації в часі.


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


симетрична булева функція; мінімізація симетричних булевих функцій; ортогональна форма представлення; класична форма представлення; поліноміальна форма представлення Ріда-Мюллера; поліном Жегалкіна; розширений поліном суми за модулем 2.

Повний текст:

PDF

Пристатейна бібліографія ГОСТ


1. Kochkarev, Yu. A., Panteleev, N N,  Kazarinova, N. L. (1999) Classical and
alternative minimal forms of logical functions: catalog-reference book.
Monograph. G. E. Pukhov Institute of Modeling Problems in Energy Sector,
Cherkasy Institute of Management, 195 p. [in Russian].


2. Burmistrov, S. V. (2016) Synthesis of discrete devices based on the use of Boolean functions in the orthogonal form of representation: dissertation for Ph.D. in technical sciences, 209 p. [in Ukrainian].


3. Burmistrov, S. V. Piven, O. B. (2015) The matrix method of parallel decomposition as a generalized method of minimization in the orthogonal form of representation. Nauka i tekhnika Povitryanykh Syl Zbroynykh Syl Ukrayiny, No. 4, pp. 151–156 [in Ukrainian]. 


4. Dyachenko, V. V., Suprun, V. P. (2015) Minimization of symmetric Boolean
functions in the class of Reed-Muller polynomials. International scientific conference "Discrete mathematics, algebra and their applications. Abstracts», Minsk, Republic of Belarus, p. 152 [in Russian].

5. Alekseychuk, A. N., Konyushok, S. N. (2014) Algebraically degenerate approximations of Boolean functions. Cybernetics and system analysis, Т. 50, No. 6, pp. 3–14 [in Russian].


6. Alekseychuk, A. N., Kulinich, O. N., Sokur, V. V., Konyushok, S. N. (2016)
Estimates of complexity and algorithms for minimizing Boolean functions in the class of canonical polarized polynomials. Modelyuvannya ta informatsiyni
tekhnolohiyi. National Academy of Science of Ukraine, G. E. Pukhov Institute of
Modeling Problems in Energy Sector. Kiev, Vol. 76, pp. 95–99 [in Russian]. (ISSN 2309- 7647)

7. Zhen-Xue He, Li-Min Xiao, Li Ruan, Fei Gu, Zhi-Sheng Huo, Guang-Jun Qin, Ming-Fa Zhu, Long-Bing Zhang, Rui Liu, Xiang Wang. (2017) A power and area optimization approach of mixed polarity Reed-Muller expression for incompletely specified Boolean functions. Journal of Computer Science and Technology, Vol. 32, Issue 2, pp. 297–311.


8. Kochkarev, Yu. A., Kushch, S. O., Panasco, O. M. (2010) The analysis of consumer indicators of realization of Reed-Muller form of representation of logical functions. Visnyk Cherkaskoho derzhavnoho tekhnolohichnoho universytetu, No. 2, pp. 64–68 [in Ukrainian].


9. Kochkarev, Yu. A., Panasco, O. M. (2010) Estimation of efficiency of application of bitwise inverting of input variables at optimization of structure of digital blocks. Prikladnaya radioelektronika. Kharkov National University of Radio Electronics, Vol. 10, No. 2, pp. 295–299 [in Russian].

10. Kochkarev, Yu. A., Panasco, O. M. (2010) Investigation of the efficiency of
polarization of variables when optimizing the structure of digital blocks. Informatsiyni tekhnolohiyi v osviti, nautsi i tekhnitsi: VII All-Ukr. sci.-pract. conf. (05-06.04), p. 81 [in Russian].





Copyright (c) 2018 S. V. Burmistrov, O. M. Panasco, N. V. Kovalska