×

zbMATH — the first resource for mathematics

Minimization of binary decision diagrams for systems of incompletely defined Boolean functions. (English. Russian original) Zbl 1320.94114
J. Comput. Syst. Sci. Int. 52, No. 6, 909-927 (2013); translation from Izv. Ross. Akad. Nauk, Teor. Sist. Upravl. 2013, No. 6, 68-86 (2013).
Summary: Algorithms for minimizing multilevel representations of systems of incompletely defined Boolean functions for various initial functional forms are proposed. The multilevel representations are based on the Shannon decomposition. Results of experimental studies indicate that the proposed algorithms are efficient for synthesizing logic circuits of library elements.
MSC:
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
94C15 Applications of graph theory to circuits and networks
Software:
ModelSim
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Kuznetsov, O P, Program implementation of logic functions and automata, (1977) · Zbl 0416.68047
[2] S. B. Akers, “Binary decision diagrams,” IEEE Trans. Comput. C-27(6) (1978). · Zbl 0377.94038
[3] R. E. Bryant, “Graph-based algorithms for Boolean functions manipulation,” IEEE Trans. Comput. C-35(8) (1986). · Zbl 0593.94022
[4] R. Drechsler and B. Becker, Binary Decision Diagrams: Theory and Implementation (Kluwer, Boston, 1998).
[5] C. Meinel and T. Theobald, Algorithms and Data Structures in VLSI Design: OBDD-Foundations and Applications (Springer, Berlin, 1998). · Zbl 0899.68040
[6] Bryant, R E; Meinel, C; Hassoun, S (ed.); Sasao, T (ed.); Brayton, R K (ed.), Ordered binary decision diagrams, (2002) · Zbl 0995.68105
[7] T. F. Tabloski and F. J. Mowle, “A numerical expansion technique and its application to minimal multiplexer logic circuit,” IEEE Trans. Comput. C-25(7) (1976). · Zbl 0329.94014
[8] Yu. G. Karpov, MODEL CHECKING: Verification of Parallel and Distributed Software (BKhV-Peterburg, St. Petersburg, 2010) [in Russian].
[9] Bibilo, P N; Leonchik, P V, An algorithm for the construction of a binary decision diagram for a system of completely defined Boolean functions, (2009)
[10] Bibilo, P N; Leonchik, P V, Decomposition of systems of Boolean functions determined by binary decision diagrams, J. Comput. Syst. Sci. Int., 50, 609-624, (2011) · Zbl 1320.94115
[11] Brayton, R K; Hachtel, G D; Sangiovanni-Vincentelli, A L, Multilevel logic synthesis, Proc. IEEE, 78, 264-300, (1990)
[12] Shneider, A A, Analysis and classification of heuristic algorithms for vertex coloring, (1984)
[13] A. A. Utkin, Analysis of Logic Networks and Boolean Calculation Techniques (Nauka i tekhnika, Minsk, 1979) [in Russian].
[14] D. E. Knut, The Art of Computer Programming. Combinatrorial Algorithms (Addison-Wesley, Reading, Mass., 2011; Vil’yams, Moscow, 2013), Vol. 4A, Part 1.
[15] S. Stojkovich, M. Stancovi, and R. Stancovi, “Determining assignment of incompletely specified Boolean functions for compact representations by binary decision diagrams,” in Proc. of the 10th Int. Workshop on Boolean Problems, Freiberg, Sachsen, 2012. · Zbl 0416.68047
[16] P. N. Bibilo, Design Systems for Integrated Circuits Based on VHDL. StateSAD, ModelSim, LeonardoSrestrum (SOLON-Press, Moscow, 2005) [in Russian].
[17] Bibilo, P N; Novikov, D Ya, Verification of logic circuits implementing systems of partial Boolean functions, (2011)
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.