A heuristic method for bi-decomposition of partial Boolean functions

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.

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

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

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

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

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

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

7. Cheng D., Xu X. Bi-decomposition of logical mappings via semi-tensor product of matrices. Automatica, 2013, vol. 49, no. 7, pp. 1979–1985.

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

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

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

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

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

13. Pottosin Yu. V. A method for bi-decomposition of partial Boolean functions. Prikladnaja diskrjetnaja matematika [Applied Discrete Mathematics], 2020, no. 47, pp. 108–116.

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

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

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

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

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