Эвристический метод алгебраической декомпозиции частичных булевых функций

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

1. Perkowski, 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.

2. 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.

3. 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.

4. 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.

5. Бибило, П. Н. Декомпозиция булевых функций на основе решения логических уравнений / П. Н. Бибило. – Минск : Беларус. навука, 2009. – 211 с.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. Поттосин, Ю. В. Декомпозиция системы частичных булевых функций с помощью покрытия графа полными двудольными подграфами / Ю. В. Поттосин, Е. А. Шестаков // Новые информационные технологии в исследовании дискретных структур : докл. Второй Всерос. конф., Екатеринбург, 2–5 нояб. 1998. – Екатеринбург : УрО РАН, 1998. – С. 185–189.

12. Поттосин, Ю. В. Метод бидекомпозиции частичных булевых функций / Ю. В. Поттосин // Информатика. – 2019. – Т. 16, № 4. – С. 77–87.

13. Pottosin, Yu. V. A method for bi-decomposition of partial Boolean functions / Yu. V. Pottosin // Прикладная дискретная математика. – 2020. – № 47. – С. 108–116.

14. 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.

15. 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.

16. Закревский, А. Д. Декомпозиция частичных булевых функций – проверка на разделимость по заданному разбиению / А. Д. Закревский // Информатика. – 2007. – № 1(13). – С. 16–21.

17. Поттосин, Ю. В. Применение аппарата покрытий троичных матриц для поиска разбиения множества аргументов при декомпозиции булевых функций / Ю. В. Поттосин, Е. А. Шестаков // Вестник Томского гос. университета. Управление, вычислительная техника и информатика. – 2011. – № 3(16). – Р. 100–107.

18. 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.