A method for bi-decomposition of partial Boolean functions
Abstract
The problem of bi-decomposition of a Boolean function is to represent a given Boolean function in the form of a given logic algebra operation over two Boolean functions and so is reduced to specification of these functions. Any of the required functions must have fewer arguments than the given function. A method of bi-decomposition for an incompletely specified (partial) Boolean function is suggested, this method uses the approach applied in solving the general problem of parallel decomposition of partial Boolean functions. The specification of the given function must be in the form of a pair of matrices. One of them, argument matrix, can be ternary or binary and represents the definitional domain of the given function. The other one, value matrix, is a binary column-vector and represents the function values on the intervals or elements of the Boolean space of the arguments. The graph of orthogonality of the argument matrix rows and the graph of orthogonality of one-element rows of the value matrix are considered. The problem of bi-decomposition is reduced to the problem of a weighted two-block covering the edge set of the orthogonality graph of the value matrix rows by complete bipartite subgraphs (bicliques) of the orthogonality graph of the argument matrix rows. Every biclique is assigned with a disjunctive normal form (DNF) in definite way. The weight of a biclique is the minimum rank of a term of the assigned DNF. According to each biclique of the obtained cover, a Boolean function is constructed whose arguments are the variables from the term of minimal rank on the DNF.
About the Author
Yu. V. Pottosin
The United Institute ofInformatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
Yuri V. Pottosin- Cand. Sci. (Phys.-Math.), Leading Researcher.
Minsk
References
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/ACMInternational Conference on Computer-Aided Design (ICCAD’2010). San Jose, IEEE Press, 2010, pp. 586-591.
9. Fiser P., Schmidt J. Small but nasty logic synthesis examples. Proceedings of the 8th International Workshop on Boolean Problems (IWSBP’8), 18-19 September 2008, Freiberg, Germany. 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. Metod mnogoblochnoj parallel’noj dekompozicii sistemy chastichnyh bulevyh funkcij [A method for multi-block parallel decomposition of a system of partial Boolean functions]. Informatika [Informatics], 2017, no. 3(55), pp. 92-98 (in Russian).
12. Pottosin Yu. V. Parallel’naja dekompozicija sistemy chastichnyh bulevyh funkcij [Parallel decomposition of a system of partial Boolean functions]. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel’naja tehnika i informatika [Tomsk State University Journal of Control and Computer Science], 2018, no. 45, pp. 83-91 (in Russian).
13. Zakrevskij A. D., Pottosin Yu. V., Cheremisinova L. D. Logicheskie osnovy proektirovanija diskretnyh ustrojstv. Logical Fundamentals for Design of Discrete Devices. Moscow, Fizmatlit, 2007, 592 p. (in Russian).
14. Pottosin Yu. V. Nahozhdenie v grafe maksimal’nyh polnyh dvudol’nyh podgrafov [Finding maximal complete bipartite subgraphs in a graph]. Avtomatizacija logicheskogo proektirovanija diskretnyh system [Automation of Logical Design of Discrete Systems], Minsk, Institute of Engineering Cybernetics of Academy of Sciences of Belarus, 1991, pp. 19-27 (in Russian).
15. Pottosina S., Pottosin Yu., Sedliak B. Finding maximal complete bipartite subgraphs in a graph. Journal of Applied Mathematics, 2008, vol. 1, no. 1, pp. 75-81.
Review
For citations:
Pottosin Yu.V. A method for bi-decomposition of partial Boolean functions. Informatics. 2019;16(4):77-87. (In Russ.)
Views: 639
Email this article 