informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2020-17-3-44-53inform-1072Research ArticleЛОГИЧЕСКОЕ ПРОЕКТИРОВАНИЕLOGICAL DESIGNЭвристический метод алгебраической декомпозиции частичных булевых функцийA heuristic 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 of Informatics Problems of the National Academy of Sciences of Belarus2020110620201734453Copyright © Поттосин Ю.В., 20202020Поттосин Ю.В.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/1072

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

The problem of decomposition of a Boolean function is to represent a given Boolean function in the form of a superposition of some Boolean functions whose number of arguments are less than the number of given function. The bi-decomposition represents a given function as a logic algebra operation, which is also given, over two Boolean functions. The task is reduced to specification of those two functions. A method for bi-decomposition of incompletely specified (partial) Boolean function is suggested. The given Boolean function is specified by two sets, one of which is the part of the Boolean space of the arguments of the function where its value is 1, and the other set is the part of the space where the function has the value 0. The complete graph of orthogonality of Boolean vectors that constitute the definitional domain of the given function is considered. In the graph, the edges are picked out, any of which has its ends corresponding the elements of Boolean space where the given function has different values. The problem of bi-decomposition is reduced to the problem of a weighted two-block covering the set of picked out edges of considered graph by its complete bipartite subgraphs (bicliques). Every biclique is assigned with a disjunctive normal form (DNF) in definite way. The weight of a biclique is a pair of certain parameters of   assigned DNF. According to each biclique of obtained cover, a Boolean function is constructed whose arguments are the variables from the term of minimal rank on the DNF. A technique for constructing the mentioned cover for two kinds of output function is described.

частичная булева функциядекомпозиция булевой функциисуперпозиция функцийоперации алгебры логикизадача о покрытииполный двудольный подграф графаэвристический методpartial Boolean functionBoolean function bi-decompositionsuperposition of functionslogic algebra operationscovering problemcomplete bipartite subgraphheuristic methodReferencesPerkowski, 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-AidedDesign. – 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/ACM International Conference on Computer-Aided Design (ICCAD’2010). San Jose, IEEE Press, 2010, pp. 586–591.Fiљer, P. Small but nasty logic synthesis examples / P. Fiљer, J. Schmidt ; ed. by B. Steinbach // Proc. of the 8th Intern. Workshop on Boolean Problems (IWSBP’8), Freiberg, Germany, 18–19 Sept. 2008. – Freiberg, 2008. – P. 183–190.Fiљer P., Schmidt J. Small but nasty logic synthesis examples. Proceedings of the 8th International Workshop on Boolean Problems (IWSBP’8), Freiberg, Germany, 18–19 September 2008. 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.Поттосин, Ю. В. Декомпозиция системы частичных булевых функций с помощью покрытия графа полными двудольными подграфами / Ю. В. Поттосин, Е. А. Шестаков // Новые информационные технологии в исследовании дискретных структур : докл. Второй Всерос. конф., Екатеринбург, 2–5 нояб. 1998. – Екатеринбург : УрО РАН, 1998. – С. 185–189.Pottosin Yu. V., Shestakov E. A. Dekompozicija sistemy chastichnyh bulevyh funkcij s pomoshch’ju pokrytij grafa polnymi dvudol’nymi podgrafami [Decomposition of a system of partial Boolean functions using covering graph with bipartite complete subgraphs]. Doklady Vtoroj Vserossijskoj konferencii "Novye informacionnye tehnologii v issledovanii diskretnyh struktur" [Proceedings of the Second All-Russian Conference "Novel Information Technologies in the research of Discrete Structures"]. Ekaterinburg, Ural’skoe otdelenie Rossijskoi akademii nauk, 1998, pp. 185–189 (in Russian).Поттосин, Ю. В. Метод бидекомпозиции частичных булевых функций / Ю. В. Поттосин // Информатика. – 2019. – Т. 16, № 4. – С. 77–87.Pottosin Yu. V. Metod bidekompozicii chastichnyh bulevyh funkcij [A method for bi-decomposition of partial Boolean functions]. Informatika [Informatics], 2019, vol. 16, no. 4, pp. 77–87 (in Russian).Pottosin, Yu. V. A method for bi-decomposition of partial Boolean functions / Yu. V. Pottosin // Прикладная дискретная математика. – 2020. – № 47. – С. 108–116.Pottosin Yu. V. A method for bi-decomposition of partial Boolean functions. Prikladnaja diskrjetnaja matematika [Applied Discrete Mathematics], 2020, no. 47, pp. 108–116.Kravets, V. N. Sequential logic synthesis using symbolic bi-decomposition / V. N. Kravets, A. Mishchenko // Advanced Techniques in Logic Synthesis, Optimizations and Applications. – New York, Dordrecht, Heidelberg, London : Springer, 2011. – P. 31–46.Kravets V. N., Mishchenko A. Sequential logic synthesis using symbolic bi-decomposition. Advanced Techniques in Logic Synthesis, Optimizations and Applications. New York, Dordrecht, Heidelberg, London, Springer, 2011, pp. 31–46.Jућwiak, L. An effective and efficient method for functional decomposition of Boolean functions based on information relationship measures / L. Jућwiak, A. Chojnacki // Design and Diagnostics of Electronic Circuits and Systams: Proc. of 3rd DDECS Workshop, Smolenice castle, Slovakia, 5–7 April 2000. – Bratislava : Institute of Informatics, Slovak Academy of Sciences, 2000. – P. 242–249.Jућwiak L., Chojnacki A. An effective and efficient method for functional decomposition of Boolean functions based on information relationship measures. Design and Diagnostics of Electronic Circuits and Systems: Proceedings of 3rd DDECS Workshop, Smolenice castle, Slovakia, 5–7 April 2000. Bratislava, Institute of Informatics, Slovak Academy of Sciences, 2000, pp. 242–249.Закревский, А. Д. Декомпозиция частичных булевых функций – проверка на разделимость по заданному разбиению / А. Д. Закревский // Информатика. – 2007. – № 1(13). – С. 16–21.Zakrevskij A. D. Dekompozicija chastichnyh bulevyh funkcij – proverka na razdielimost’ po zadannomu razbieniju [Decomposition of partial Boolean functions: checking decomposability at a given partition]. Informatika [Informatics], 2007, no. 1(13), pp. 16–21 (in Russian).Поттосин, Ю. В. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций / Ю. В. Поттосин, Е. А. Шестаков // Вестник Томского гос. университета. Управление, вычислительная техника и информатика. – 2011. – № 3(16). – Р. 100–107.Pottosin Yu. V., Shestakov E. A. Primjenjenie apparata pokrytij troichnyh matric dlja poiska razbienija mnozhestva argumentov pri dekompozicii buljebyh funkcij [Application of the apparatus of covering ternary matrices for searching partition of argument set at decomposition of Boolean functions]. Vestnik Tomskogo gosudarstvennogo universitjeta. Upravlenie, vychislitjel’naja tehnika i informatika [Tomsk State University Journal of Control and Computer Science], 2011, no. 3(16), pp. 100–107 (in Russian).Taghavi Afshord, S. An input variable partitioning algorithm for functional decomposition of a system of Boolean functions based on the tabular method / S. Taghavi Afshord, Yu. V. Pottosin, B. Arasteh // Discrete Applied Mathematics. – 2015. – Vol. 185. – P. 208–219.Taghavi Afshord S., Pottosin Yu. V., Arasteh B. An input variable partitioning algorithm for functional decomposition of a system of Boolean functions based on the tabular method. Discrete Applied Mathematics, 2015, vol. 185, pp. 208–219.

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