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

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

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

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. Поттосин, Ю. В. Метод многоблочной параллельной декомпозиции системы частичных булевых функций / Ю. В. Поттосин // Информатика. - 2017. - № 3(55). - С. 92-98.

12. Поттосин, Ю. В. Параллельная декомпозиция системы частичных булевых функций / Ю. В. Поттосин // Вестник Томск. гос. ун-та. Управление, вычислительная техника и информатика. - 2018. - № 45. -С. 83-91.

13. Закревский, А. Д. Логические основы проектирования дискретных устройств / А. Д. Закревский, Ю. В. Поттосин, Л. Д. Черемисинова. - М. : Физматлит, 2007. - 592 с.

14. Поттосин, Ю. В. Нахождение в графе максимальных полных двудольных подграфов / Ю. В. Поттосин // Автоматизация логического проектирования дискретных систем. - Минск : Ин-т техн. кибернетики АН Беларуси, 1991. - С. 19-27.

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