×

zbMATH — the first resource for mathematics

Decomposition of a system of incompletely specified Boolean functions defined with a binary decision diagram. (English. Russian original) Zbl 1325.94173
Autom. Remote Control 75, No. 7, 1173-1194 (2014); translation from Avtom. Telemekh. 2014, No. 7, 17-42 (2014).
Summary: We propose a decomposition method for systems of incompletely specified Boolean functions represented as binary decision diagrams. Minimizing the number of intermediate functions in such a decomposition is intended to improve the performance of Boolean circuits made of library elements. A characteristic feature of our method is the fact that after decomposition (cutting) of the original binary decision diagram one of two decomposition units is represented as a system of DNFs.
MSC:
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
94C15 Applications of graph theory to circuits and networks
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Tanaev, V.S. and Povarich, M.P., Sintez graf-skhem algoritmov vybora reshenii (Synthesis of Flowgraphs for Decision Making Algorithms), Minsk: Nauka i Tekhnika, 1974.
[2] Blokh, A.Sh., Graf-skhemy i ikh primenenie (Flowgraphs and Their Applications), Minsk: Vysheishaya Shkola, 1975.
[3] Kuznetsov, OP, Program realization of logical functions and automata. I, II, Autom. Remote Control, 38, 1077-1088, (1977) · Zbl 0416.68046
[4] Akers, SB, Binary decision diagrams, IEEE Trans. Comput., 27, 509-516, (1978) · Zbl 0377.94038
[5] Bryant, RE, Graph-based algorithms for Boolean functions manipulation, IEEE Trans. Comput., 35, 677-691, (1986) · Zbl 0593.94022
[6] Bryant, RE; Meinel, C; Hassoun, S (ed.); Sasao, T (ed.); Brayton, RK (ed.), Ordered binary decision diagrams, (2002), Boston · Zbl 0995.68105
[7] Meinel, C. and Theobald, T., Algorithms and Data Structures in VLSI Design: OBDD-Foundations and Applications, Berlin: Springer-Verlag, 1998. · Zbl 0899.68040
[8] Karpov, Yu.G., MODEL CHECKING. Verifikatsiya parallel’nykh i raspredelennykh programmnykh sistem (Model Checking. Verification of Parallel and Distributed Software Systems), St. Petersburg: BKhVPeterburg, 2010.
[9] Bibilo, P.N., Dekompozitsiya bulevykh funktsii na osnove resheniya logicheskikh uravnenii (Decomposition of Boolean Functions Based on Solving Logical Equations), Minsk: Belarus. Navuka, 2009.
[10] Zakrevskii, A.D., Logicheskii sintez kaskadnykh skhem (Logical Synthesis of Cascade Circuits), Moscow: Nauka, 1981.
[11] Sasao, T; Sasao, T (ed.); Fujita, M (ed.), FPGA design by generalized functional decomposition, 233-258, (1996), Boston
[12] Scholl, C., Functional Decomposition with Applications to FPGA Synthesis, Boston: Kluwer, 2001. · Zbl 0989.94003
[13] Bibilo, P.N. and Romanov, V.I., Logicheskoe proektirovanie diskretnykh ustroistv s ispol’zovaniem produktsionnofreimovoi modeli predstavleniya znanii (Logical Design of Discrete Devices with Product-Frame Model of Knowledge Representation), Minsk: Belarus. Navuka, 2011.
[14] Cortadella, J, Timing-driven logic bi-decomposition, IEEE Trans. Comput.-Aided Design Integrat. Circuits Syst., 22, 675-685, (2003)
[15] Yang, S; Ciesielski, M, BDS: A BDD-based logic optimization system, IEEE Trans. Comput.-Aided Design Integrat. Circuits Syst., 21, 866-876, (2002)
[16] Bibilo, PN; Leonchik, PV, Decomposition of systems of Boolean functions defined by binary decision diagrams, 86-101, (2011)
[17] Shneider, AA, Analysis and classification of heuristic graph vertex coloring algorithms, 15-22, (1984)
[18] Bibilo, P.N. and Enin, S.V., Sintez kombinatsionnykh skhem metodami funktsional’noi dekompozitsii (Synthesis of Combinatorial Circuits with Functional Decomposition Methods), Minsk: Nauka i Tekhnika, 1987.
[19] Knuth, D.E., The Art of Computer Programming, vol. 4A: Combinatorial Algorithms, Part 1, Reading: Addison-Wesley, 2011. Translated under the title Iskusstvo programmirovaniya, tom 4, A. Kombinatornye algoritmy, ch. 1, Moscow: Vil’yams, 2013. · Zbl 1354.68001
[20] Stojkovich, S., Stancović, M., and Stancović, R., Determining Assignment of Incompletely Specified Boolean Functions for Compact Representations by Binary Decision Diagrams, 10 Int. Workshop Boolean Probl., September 19-21, 2012, Freiberg (Sachsen), pp. 233-238.
[21] Gavrilov, M.A., Devyatkov, V.V., and Pupyrev, E.I., Logicheskoe proektirovanie diskretnykh avtomatov (Logical Design of Discrete Automata), Moscow: Nauka, 1977.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.