informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-881Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNМетод бидекомпозиции частичных булевых функцийA method for bi-decomposition of partial Boolean functionsПоттосинЮ. В.PottosinYu. V.

Поттосин Юрий Васильевич - кандидат физикоматематических наук, ведущий научный сотрудник.

Минск

Yuri V. Pottosin- Cand. Sci. (Phys.-Math.), Leading Researcher.

Minsk

pott@newman.bas-net.byОбъединенный институт проблем информатики, Национальная академия наук БеларусиThe United Institute ofInformatics Problems of the National Academy of Sciences of Belarus2019261220191647787Copyright © Поттосин Ю.В., 20192019Поттосин Ю.В.Pottosin Y.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/881

Задача бидекомпозиции (от англ. bi-decomposition) булевой функции заключается в представлении заданной булевой функции в виде некоторой заданной операции алгебры логики над двумя булевыми функциями и сводится таким образом к определению этих функций. Каждая из искомых функций должна обладать меньшим числом аргументов, чем заданная. Предлагается метод бидекомпозиции для не полностью определенных (частичных) булевых функций, который использует подход, применяемый в решении общей задачи их параллельной декомпозиции. Задание исходной функции должно иметь вид пары матриц. Одна из них, матрица аргументов, может быть троичной или булевой и представляет область определения заданной функции. Другая матрица, матрица значений, имеет вид одного булева вектора-столбца и показывает значения функции на интервалах или элементах булева пространства аргументов. Рассматриваются граф ортогональности строк матрицы аргументов и граф ортогональности одноэлементных строк матрицы значений. Задача бидекомпозиции сводится к задаче о двухблочном взвешенном покрытии множества ребер графа ортогональности строк матрицы значений полными двудольными подграфами (бикликами) графа ортогональности строк матрицы аргументов. Каждой биклике приписывается определенным образом дизъюнктивная нормальная форма (ДНФ), и весом биклики считается минимальный ранг элементарной конъюнкции в соответствующей ДНФ. По каждой из биклик полученного покрытия строится булева функция, аргументами которой служат переменные из элементарной конъюнкции минимального ранга соответствующей ДНФ, что является решением задачи бидекомпозиции.

The problem of bi-decomposition of a Boolean function is to represent a given Boolean function in the form of a given logic algebra operation over two Boolean functions and so is reduced to specification of these functions. Any of the required functions must have fewer arguments than the given function. A method of bi-decomposition for an incompletely specified (partial) Boolean function is suggested, this method uses the approach applied in solving the general problem of parallel decomposition of partial Boolean functions. The specification of the given function must be in the form of a pair of matrices. One of them, argument matrix, can be ternary or binary and represents the definitional domain of the given function. The other one, value matrix, is a binary column-vector and represents the function values on the intervals or elements of the Boolean space of the arguments. The graph of orthogonality of the argument matrix rows and the graph of orthogonality of one-element rows of the value matrix are considered. The problem of bi-decomposition is reduced to the problem of a weighted two-block covering the edge set of the orthogonality graph of the value matrix rows by complete bipartite subgraphs (bicliques) of the orthogonality graph of the argument matrix rows. Every biclique is assigned with a disjunctive normal form (DNF) in definite way. The weight of a biclique is the minimum rank of a term of the assigned DNF. According to each biclique of the obtained cover, a Boolean function is constructed whose arguments are the variables from the term of minimal rank on the DNF.

частичная булева функциябидекомпозиция булевой функциисуперпозиция функцийоперации алгебры логикиматричное задание булевой функциизадача о покрытииполный двудольный подграф графаpartial Boolean functionBoolean function bi-decompositionsuperposition of functionslogic algebra operationsmatrix representation of Boolean functionscovering problemcomplete bipartite subgraphReferencesPerkowski, M. A. A Survey of Literature on Functional Decomposition, Version IV (Technical Report) / M. A. Perkowski, S. Grygiel. - Portland, USA : Portland State University, Department of Electrical Engineering, 1995. - 188 p.Perkowski M. A., Grygiel S. A Survey of Literature on Functional Decomposition, Version IV (Technical Report). Portland, USA, Portland State University, Department of Electrical Engineering, 1995, 188 p.Cortadella, J. Timing-driven logic bi-decomposition / J. Cortadella // IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems. - 2003. - Vol. 22, no. 6. - P. 675-685.Cortadella J. Timing-driven logic bi-decomposition. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, vol. 22, no. 6, pp. 675-685.Mishchenko, A. An algorithm for bi-decomposition of logic functions / A. Mishchenko, B. Steinbach, M. Perkowski // Proc. of the 38th Annual Design Automation Conf. (DAC’2001), 18-22 June 2001, Las Vegas, USA. - Las Vegas, 2001. - P. 103-108.Mishchenko A., Steinbach B., Perkowski M. An algorithm for bi-decomposition of logic functions. Proceedings of the 38th Annual Design Automation Conference (DAC’2001), 18-22 June 2001, Las Vegas, USA. Las Vegas, 2001, pp. 103-108.Chang, S.-C. Technology mapping for TLU FPGA’s based on decomposition of binary decision diagrams / S.-C. Chang, M. Marek-Sadowska, T. Hwang // IEEE Trans. Computer-Aided Design. - 1996. - Vol. 15, no. 10. -P. 1226-1235.Chang S.-C., Marek-Sadowska M., Hwang T. Technology mapping for TLU FPGA’s based on decomposition of binary decision diagrams. IEEE Transactions Computer-Aided Design, 1996, vol. 15, no. 10, pp. 1226-1235.Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. - Минск : Беларус. навука, 2009. - 211 с.Bibilo P. N. Dekompozicija bulevyh funkcij na osnove reshenija logicheskih uravnenij. Decomposition of Boolean functions on the base of solving logical equations. Minsk, Belaruskaja navuka, 2009, 211 p. (in Russian).Zakrevskij, A. D. On a special kind decomposition of weakly specified Boolean functions / A. D. Zakrevskij // Second Intern. Conf. on Computer-Aided Design of Discrete Devices (CAD DD’97), 12-14 Nov. 1997, Minsk, Belarus / National Academy of Sciences of Belarus, Institute of Engineering Cybernetics. - Minsk, 1997. - Vol. 1. - P. 36-41.Zakrevskij A. D. On a special kind decomposition of weakly specified Boolean functions. Second International Conference on Computer-Aided Design of Discrete Devices (CAD DD’97), Minsk, Belarus, 12-14 November 1997. National Academy of Sciences of Belarus, Institute of Engineering Cybernetics, Minsk, 1997, vol. 1, pp. 36-41.Cheng, D. Bi-decomposition of logical mappings via semi-tensor product of matrices / D. Cheng, X. Xu // Automatica. - 2013. - Vol. 49, no. 7. - P. 1979-1985.Cheng D., Xu X. Bi-decomposition of logical mappings via semi-tensor product of matrices. Automatica, 2013, vol. 49, no. 7, pp. 1979-1985.Choudhury, M. Bi-decomposition of large Boolean functions using blocking edge graphs / M. Choudhury, K. Mohanram // 2010 IEEE/ACM Intern. Conf. on Computer-Aided Design (ICCAD’2010). - San Jose : IEEE Press, 2010. - P. 586-591.Choudhury M., Mohanram K. Bi-decomposition of large Boolean functions using blocking edge graphs. 2010 IEEE/ACMInternational Conference on Computer-Aided Design (ICCAD’2010). San Jose, IEEE Press, 2010, pp. 586-591.Fiser, P. Small but nasty logic synthesis examples / P. Fiser, J. Schmidt ; ed. by B. Steinbach // Proc. of the 8th Intern. Workshop on Boolean Problems (IWSBP’8), 18-19 Sept. 2008, Freiberg, Germany. - Freiberg, 2008. -P. 183-190.Fiser P., Schmidt J. Small but nasty logic synthesis examples. Proceedings of the 8th International Workshop on Boolean Problems (IWSBP’8), 18-19 September 2008, Freiberg, Germany. Freiberg, 2008, pp. 183-190.Steinbach, B. Vectorial bi-decomposition for lattices of Boolean functions / B. Steinbach, C. Posthoff ; ed. by B. Steinbach // Further Improvements in the Boolean Domain. - Cambridge Scholars Publishing, 2018. -P. 175-198.Steinbach B., Posthoff C. Vectorial bi-decomposition for lattices of Boolean functions. Further Improvements in the Boolean Domain. In B. Steinbach (ed.). Cambridge Scholars Publishing, 2018, pp. 175-198.Поттосин, Ю. В. Метод многоблочной параллельной декомпозиции системы частичных булевых функций / Ю. В. Поттосин // Информатика. - 2017. - № 3(55). - С. 92-98.Pottosin Yu. V. Metod mnogoblochnoj parallel’noj dekompozicii sistemy chastichnyh bulevyh funkcij [A method for multi-block parallel decomposition of a system of partial Boolean functions]. Informatika [Informatics], 2017, no. 3(55), pp. 92-98 (in Russian).Поттосин, Ю. В. Параллельная декомпозиция системы частичных булевых функций / Ю. В. Поттосин // Вестник Томск. гос. ун-та. Управление, вычислительная техника и информатика. - 2018. - № 45. -С. 83-91.Pottosin Yu. V. Parallel’naja dekompozicija sistemy chastichnyh bulevyh funkcij [Parallel decomposition of a system of partial Boolean functions]. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel’naja tehnika i informatika [Tomsk State University Journal of Control and Computer Science], 2018, no. 45, pp. 83-91 (in Russian).Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. - М. : Физматлит, 2007. - 592 с.Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Fundamentals for Design of Discrete Devices. Moscow, Fizmatlit, 2007, 592 p. (in Russian).Поттосин, Ю. В. Нахождение в графе максимальных полных двудольных подграфов / Ю. В. Поттосин // Автоматизация логического проектирования дискретных систем. - Минск : Ин-т техн. кибернетики АН Беларуси, 1991. - С. 19-27.Pottosin Yu. V. Nahozhdenie v grafe maksimal’nyh polnyh dvudol’nyh podgrafov [Finding maximal complete bipartite subgraphs in a graph]. Avtomatizacija logicheskogo proektirovanija diskretnyh system [Automation of Logical Design of Discrete Systems], Minsk, Institute of Engineering Cybernetics of Academy of Sciences of Belarus, 1991, pp. 19-27 (in Russian).Pottosina, S. Finding maximal complete bipartite subgraphs in a graph / S. Pottosina, Yu. Pottosin, B. Sedliak // J. Applied Mathematics. - 2008. - Vol. 1, no. 1. - P. 75-81.Pottosina S., Pottosin Yu., Sedliak B. Finding maximal complete bipartite subgraphs in a graph. Journal of Applied Mathematics, 2008, vol. 1, no. 1, pp. 75-81.

The authors declare that there are no conflicts of interest present.