Декомпозиция Ашенхёрста для таблично заданных булевых функций

Декомпозиция сложных систем – широко распространённый метод анализа и преобразований, применяемый в различных областях. Декомпозиция в менее сложные подсистемы, помимо того, что уменьшает в целом представление исходной системы (при этом, возможно, оптимизируются и другие её характеристики), позволяет выявить скрытую структуру системы, что, в частности, позволяет провести её более глубокий анализ и преобразования. В статье рассмотрен подход к декомпозиции Ашенхёрста для таблично заданных булевых функций (это могут быть таблицы истинности, характеристические вектора нулей и единиц и так далее), основанный на интерпретации композиции таких функций как их соединения-с-равенством (аналогично SQL оператору JOIN ON с равенством). Задача декомпозиции сведена к задаче решения с использованием базисов Грёбнера системы квадратных уравнений над конечным полем порядка 2 для некоторых специально введённых параметров. Решение системы индуцирует разбиение входных переменных исходной функции на связанные и свободные переменные, что, в свою очередь, позволяет определить функции-компоненты декомпозиции, при этом сами вычисленные параметры связывают их, выступая для одной в качестве значений результата, а для другой значений аргумента. Приведены результаты экспериментов по декомпозиции в системе компьютерной алгебры Maple. Рассмотрены варианты обобщения данного подхода.

1. Ashenhurst R. The Decomposition of Switching Functions. In Proc. of the International Symposium on the Theory of Switching, 1957. pp. 74–116.

2. Curtis H. A. A New Approach to the Design of Switching Circuits. D. van Nostrand company, 1962. 635 p.

3. Roth J. P., Karp R. M. Minimization over Boolean Graphs. IBM Journal of Research and Development, 6(2), 1962, pp. 227–238. DOI: 10.1147/rd.62.0227.

4. Perkowski M.A., Grygiel S. A Survey of Literature on Function Decomposition, Version IV. Rep. of PSU Electrical Engineering Department, Portland State University, Portland,

5. Oregon, USA. Опубликован: November 20, 1995. 188 p. Available at https://web.cecs.pdx.edu/~mperkows/=PUBLICATIONS/PER/G1995/survey.pdf, accessed 25.10.2025.

6. Mishchenko A., Steinbach B., Perkowski M. An Algorithm for Bi-Decomposition of Logic Functions. Proc. of the 38th Design Automation Conference, 2001, pp. 103–108. DOI: 10.1145/378239.378353.

7. Steinbach B., Lang C. Exploiting Functional Properties of Boolean Functions for Optimal Multi-Level Design by Bi-Decomposition. Artificial Intelligence Review, 20(3-4), 2003, pp. 319-360. DOI:

8. 1023/B:AIRE.0000006606.01771.8f.

9. Mishchenko A., Brayton R., Calvino A.T., De Micheli G. Boolean Decomposition Revisited. In Proc. of the 32th International Workshop on Logic & Synthesis, 2023. 5 p.

10. Hien B., Walter W., Calvino A.T., Mishchenko A., Wille R. Ashenhurst-Curtis Decomposition Using Don’t Cares. In Proc. of the 34th International Workshop on Logic & Synthesis, 2025. 8 p.

11. Calvino A. T., De Micheli G., Mishchenko A., Brayton R. Enhancing Delay-Driven LUT Mapping with Boolean Decomposition. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 44(3), 2024, pp. 1017-1030. DOI: 10.1109/TCAD.2024.3457378.

12. Li Y., Tsai E., Perkowski M., Song X. Grover-Based Ashenhurst-Curtis Decomposition Using Quantum Language Quipper. Quantum Information and Computation, 19(1-2), 2019, pp. 0035-0066. DOI: 10.26421/QIC19.1-2-4.

13. Miyasaka Y., Mishchenko A., Wawrzynek J., Fraser N.J. Synthesizing a Class of Practical Boolean Functions Using Truth Tables. In Proc. of the 31th International Workshop on Logic & Synthesis, 2022. 7 p.

14. Advanced Techniques in Logic Synthesis, Optimizations and Applications, eds. Khatri, S.P., Gulati, K. Springer, New York, NY, USA, 2011. 423 p. DOI: 10.1007/978-1-4419-7518-8.

15. Stanion T., Sechen C. A Method for Finding Good Ashenhurst Decompositions and Its Application to FPGA Synthesis. In Proc. of the 32th Design Automation Conference, 1995. pp. 60-64. DOI: 10.1145/217474.217507.

16. Yang C., Ciesielski M. BDS: a BDD-Based Logic Optimization System. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21(7), 2002, pp. 866-876. DOI: 10.1109/TCAD.2002.1013899.

17. Choudhury M., Mohanram K. Bi-decomposition of Large Boolean Functions Using Blocking Edge Graphs. Proc. of the 2010 IEEE/ACM International Conference on Computer-Aided Design, 2010, pp. 586–591. DOI: 10.1109/ICCAD.2010.5654210.

18. Bengtsson T., Martinelli A., Dubrova E. A BDD-based fast heuristic algorithm for disjoint decomposition. In Proc. of the 31st Asia and South Pacific Design Automation Conference, 2003. pp. 191–196. DOI: 10.1145/1119772.1119810.

19. Lin H.-P., Jiang J.-H. R., Lee R.-R. To SAT or not to SAT: Ashenhurst decomposition in a large scale. In Proc. of the 2008 IEEE/ACM International Conference on Computer-Aided Design, 2008. pp. 32–37. DOI: 10.5555/1509456.1509476.

20. Chen H., Janota M., Marques-Silva J. QBF-Based Boolean Function Bi-Decomposition. In Proc. of the 2012 Design, Automation & Test in Europe Conference, 2012. pp. 816-819. DOI: 10.1109/DATE.2012.6176606.

21. Поттосин Ю.В. Эвристический метод алгебраической декомпозиции частичных булевых функций. Информатика, том 17, № 3, 2020, стр. 44–53. DOI: 10.37661/1816-0301-2020-17-3-44-53. / Pottosin Yu.V. A Heuristic Method for Bi-Decomposition of Partial Boolean Functions. Informatics, 2020, vol. 17, no. 3, pp. 44−53 (in Russian). DOI: 10.37661/1816-0301-2020-17-3-44-53.

22. Поттосин Ю.В. Синтез комбинационных схем с помощью алгебраической декомпозиции булевых функций. Информатика, том 19, № 1, 2022, стр. 7–18. DOI: 10.37661/1816-0301-2022-19-1-7-18. / Pottosin Yu.V. Synthesis of Combinational Circuits by Means of Bi-Decomposition of Boolean Functions. Informatics, 2022, vol. 19, no. 1, pp. 7−18 (in Russian). DOI: 10.37661/1816-0301-2022-19-1-7-18.

23. Emelyanov P., Ponomaryov D. On the Tractability of Disjoint AND-Decomposition of Boolean Formulas. In Proc. of the PSI 2014: Ershov Informatics Conference. Lecture Notes in Computer Science, vol. 8974, 2015. pp. 92-101. DOI: 10.1007/978-3-662-46823-4_8.

24. Емельянов П.Г., Пономарев Д.К. Алгоритмические вопросы конъюнктивной декомпозиции булевых формул. Программирование, № 3, 2015, стр. 62-72. / Emelyanov P.G., Ponomaryov D.K. Algorithmic Issues of AND-Decomposition of Boolean Formulas. Programming and Computer Software, 2015, vol. 41, no. 3, pp. 162–169. DOI: 10.1134/S0361768815030032.

25. Emelyanov P., Ponomaryov D. On a Polytime Factorization Algorithm for Multilinear Polynomials over F2. In Proc. of the 20th International Workshop on Computer Algebra in Scientific Computing. Lecture Note in Computer Science, vol. 11077, 2018. pp. 164-176. DOI: 10.1007/978-3-319-99639-4_11.

26. Emelyanov P., Ponomaryov D. The Complexity of AND-decomposition of Boolean Functions. Discrete Applied Mathematics. 280, 2020, pp. 113–132. DOI: 10.1016/j.dam.2019.07.005.

27. Emelyanov P. AND-Decomposition of Boolean Polynomials with Prescribed Shared Variables. In Proc. of the Second International Conference on Algorithms and Discrete Applied Mathematics. Lecture Note in Computer Science, vol. 9602, 2016. pp. 164-175. DOI: 10.1007/978-3-319-29221-2_14.

28. Emelyanov P. On two kinds of dataset decomposition. In Proc. of the 18th International Conference on Computational Science. Part II. Lecture Notes in Computer Science, vol. 10861, 2018. pp. 171–183. DOI: 10.1007/978-3-319-93701-4_13.

29. Papenbrock T., Ehrlich J., Marten J., Neubert T., Rudolph J., Schoenberg M., Zwiener J., Naumann F. Functional dependency discovery: an experimental evaluation of seven algorithms. Proceedings of the VLDB Endowment, 8(10), 2015, pp. 1082-1093. DOI: 10.14778/2794367.2794377.

30. Кокс Д., Литтл Дж., О'Ши Д. Идеалы, многообразия и алгоритмы. Введение в вычислительные аспекты алгебраической геометрии и коммутативной алгебры: Пер. с англ. Мир, 2000. 687 с.

31. Maple Online Help, Groebner Basis (overview). Available at https://www.maplesoft.com/support/help/view.aspx?path=Groebner%2fBasis, accessed 25.10.2025.

32. Faugère J.C. A New Efficient Algorithm for Computing Gröbner Bases 〖(F〗_4). Journal of Pure and Applied Algebra, 139(1-3), 1999, pp. 61-88. DOI: 10.1016/S0022-4049(99)00005-5.