Shared binary decision diagram with attributed edges for efficient Boolean function manipulation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Shared binary decision diagram with attributed edges for efficient Boolean function manipulation

Full text

Pdf (647 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 27th ACM/IEEE Design Automation Conference table of contents

Orlando, Florida, United States

Pages: 52 - 57

Year of Publication: 1991

ISBN:0-89791-363-9

Authors

Shin-ichi Minato	Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto, 606, Japan
Nagisa Ishiura	Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto, 606, Japan
Shuzo Yajima	Department of Information Science, Faculty of Engineering, Kyoto University, Kyoto, 606, Japan

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS : Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 21, Downloads (12 Months): 55, Citation Count: 55

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/123186.123225 What is a DOI?

ABSTRACT

The efficiency of Boolean function manipulation depends on the form of representation of Boolean functions. Binary Decision Diagrams (BDD's) are graph representations proposed by Akers and Bryant. BDD's have some properties which can be used to enable efficient Boolean function manipulation. In this paper, we describe a technique of more efficient Boolean function manipulation that uses Shared Binary Decision Diagrams (SBDD's) with attributed edges. Our implements include an ordering algorithm of input variables and a method of handling don't care. We show experimental results produced by the implementation of the Boolean function manipulator.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	S. B. Akers: "Binary Decision Diagram", IEEE Trans. on Computers, Vol. C-27, No. 6, pp. 509- 516, (June, 1978).
	2	Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
	3	Jean-Christophe Madre , Jean-Paul Billon, Proving circuit correctness using formal comparison between expected and extracted behaviour, Proceedings of the 25th ACM/IEEE conference on Design automation, p.205-210, June 12-15, 1988, Atlantic City, New Jersey, United States
	4	K. Cho , R. E. Bryant, Test pattern generation for sequential MOS circuits by symbolic fault simulation, Proceedings of the 26th ACM/IEEE conference on Design automation, p.418-423, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74452]
	5	F. Brglez, H. Fujiwara: "A neutral netlist of 10 combinational circuits", Special Session on A TPG and Fault Simulation, Proc. 1985 IEEE International Symposium Circuit and Systems, Kyoto, Jap an, (June, 1985).
	6	M. Fujita, H. Fujisawa and N. Kawato: "Evaluation and Improvements of Boolean Comparison Method Based on Binary Decision Diagrams", IEEE ICCAD-88 Tech. Papers, pp. 2-5, (November, 1988).
	7	S. Malik, A. R. Wang, R. K. Brayton and A. S. Vimcentelli: "Logic Verification using Binary Decision Diagrams in a Logic Synthesis Environment" IEEE ICCAD-88 Tech. Papers, pp. 6-9, (November, 1988).

CITED BY 55

	S. Minato , S. Ishihara, Streaming BDD manipulation for large-scale combinatorial problems, Proceedings of the conference on Design, automation and test in Europe, p.702-707, March 2001, Munich, Germany
	M. R. Mercer , R. Kapur , D. E. Ross, Functional approaches to generating orderings for efficient symbolic representations, Proceedings of the 29th ACM/IEEE conference on Design automation, p.624-627, June 08-12, 1992, Anaheim, California, United States
	Per Lindgren , Mikael Kerttu , Mitch Thornton , Rolf Drechsler, Low power optimization technique for BDD mapped circuits, Proceedings of the 2001 conference on Asia South Pacific design automation, p.615-621, January 2001, Yokohama, Japan
	Nagisa Ishiura , Yutaka Deguchi , Shuzo Yajima, Coded time-symbolic simulation using shared binary decision diagram, Proceedings of the 27th ACM/IEEE conference on Design automation, p.130-135, June 24-27, 1990, Orlando, Florida, United States
	Kuang-Chien Chen , Yusuke Matsunaga , Saburo Muroga , Masahiro Fujita, A resynthesis approach for network optimization, Proceedings of the 28th conference on ACM/IEEE design automation, p.458-463, June 17-22, 1991, San Francisco, California, United States
	H. Sawada , S. Yamashita , A. Nagoya, Restructuring logic representations with easily detectable simple disjunctive decompositions, Proceedings of the conference on Design, automation and test in Europe, p.755-761, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Tony Stornetta , Forrest Brewer, Implementation of an efficient parallel BDD package, Proceedings of the 33rd annual conference on Design automation, p.641-644, June 03-07, 1996, Las Vegas, Nevada, United States
	Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
	M. A. Thornton , V. S. S. Nair, Behavioral synthesis of combinational logic using spectral-based heuristics, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.2, p.219-230, April 1999
	Luc Burgun , N. Dictus , Alain Greiner , E. Prado Lopes , C. Sarwary, Multilevel logic optimization of very high complexity circuits, Proceedings of the conference on European design automation, p.14-19, September 19-23, 1994, Grenoble, France
	Zohair Sahraoui , Paul Six , Ivo Bolsens , Hugo De Man, Search space reduction through clustering in test generation, Proceedings of the conference on European design automation, p.242-247, September 18-22, 1995, Brighton, England
	Y.-T. Lai , S. Sastry, Edge-valued binary decision diagrams for multi-level hierarchical verification, Proceedings of the 29th ACM/IEEE conference on Design automation, p.608-613, June 08-12, 1992, Anaheim, California, United States
	Hiroyuki Ochi , Nagisa Ishiura , Shuzo Yajima, Breadth-first manipulation of SBDD of Boolean functions for vector processing, Proceedings of the 28th conference on ACM/IEEE design automation, p.413-416, June 17-22, 1991, San Francisco, California, United States
	R. Drechsler , A. Sarabi , M. Theobald , B. Becker , M. A. Perkowski, Efficient representation and manipulation of switching functions based on ordered Kronecker functional decision diagrams, Proceedings of the 31st annual conference on Design automation, p.415-419, June 06-10, 1994, San Diego, California, United States
	S. Höreth, Compilation of optimized OBDD-algorithms, Proceedings of the conference on European design automation, p.152-157, September 1996, Geneva, Switzerland
	Yutaka Deguchi , Nagisa Ishiura , Shuzo Yajima, Probabilistic CTSS: analysis of timing error probability in asynchronous logic circuits, Proceedings of the 28th conference on ACM/IEEE design automation, p.650-655, June 17-22, 1991, San Francisco, California, United States
	Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992
	Takashi Horiyama , Toshihide Ibaraki, Ordered binary decision diagrams as knowledge-bases, Artificial Intelligence, v.136 n.2, p.189-213, April 2002
	Hiroshige Fujii , Goichi Ootomo , Chikahiro Hori, Interleaving based variable ordering methods for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.38-41, November 07-11, 1993, Santa Clara, California, United States
	Randal E. Bryant , Christoph Meinel, Ordered binary decision diagrams, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Shin-ichi Minato, Streaming BDD Manipulation, IEEE Transactions on Computers, v.51 n.5, p.474-485, May 2002
	Hiroyuki Ochi , Koichi Yasuoka , Shuzo Yajima, Breadth-first manipulation of very large binary-decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.48-55, November 07-11, 1993, Santa Clara, California, United States
	K. Kubiak , S. Parkes , W. K. Fuchs , R. Saleh, Exact evaluation of diagnostic test resolution, Proceedings of the 29th ACM/IEEE conference on Design automation, p.347-352, June 08-12, 1992, Anaheim, California, United States
	Wolfgang Günther , Rolf Drechsler, Minimization of free BDDs, Integration, the VLSI Journal, v.32 n.1-3, p.41-59, November 2002
	Shin-ichi Minato, Zero-suppressed BDDs for set manipulation in combinatorial problems, Proceedings of the 30th international conference on Design automation, p.272-277, June 14-18, 1993, Dallas, Texas, United States
	Patrice Godefroid , David E. Long, Symbolic Protocol Verification with Queue BDDs, Formal Methods in System Design, v.14 n.3, p.257-271, May 1999
	Christoph Meinel , Christian Stangier, Algorithms and heuristics in VLSI design, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Rolf Drechsler , Wolfgang Günther , Stefan Höreth, Minimization of word-level decision diagrams, Integration, the VLSI Journal, v.33 n.1, p.39-70, December 2002
	Takashi Horiyama , Toshihide Ibaraki, Translation among CNFs, characteristic models and ordered binary decision diagrams, Information Processing Letters, v.85 n.4, p.191-198, 28 February 2003
	Amit Goel , Gagan Hasteer , Randal E. Bryant, Symbolic representation with ordered function templates, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
	Wolfgang Günther , Rolf Drechsler, Efficient Minimization and Manipulation of Linearly Transformed Binary Decision Diagrams, IEEE Transactions on Computers, v.52 n.9, p.1196-1209, September 2003
	J. Gergov , C. Meinel, Efficient Boolean Manipulation with OBDD's Can be Extended to FBDD's, IEEE Transactions on Computers, v.43 n.10, p.1197-1209, October 1994
	Shinobu Nagayama , Tsutomu Sasao, Minimization of memory size for heterogeneous MDDs, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.871-874, January 27-30, 2004, Yokohama, Japan
	Kenneth M. Butler , Don E. Ross , Rohit Kapur , M. Ray Mercer, Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams, Proceedings of the 28th conference on ACM/IEEE design automation, p.417-420, June 17-22, 1991, San Francisco, California, United States
	Gianpiero Cabodi , Paolo Camurati , Stefano Quer, Auxiliary variables for BDD-based representation and manipulation of Boolean functions, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.309-340, July 1998
	A. Hett , B. Becker , R. Drechsler, MORE: an alternative implementation of BDD packages by multi-operand synthesis, Proceedings of the conference on European design automation, p.164-169, September 1996, Geneva, Switzerland
	Yu-Liang Wu , Hongbing Fan , Malgorzata Marek-Sadowska , C. k. Wong, OBDD Minimization Based on Two-Level Representation of Boolean Functions, IEEE Transactions on Computers, v.49 n.12, p.1371-1379, December 2000
	Beate Bollig , Ingo Wegener, Improving the Variable Ordering of OBDDs Is NP-Complete, IEEE Transactions on Computers, v.45 n.9, p.993-1002, September 1996
	Rolf Drechsler, Verifying integrity of decision diagrams, Integration, the VLSI Journal, v.32 n.1-3, p.61-75, November 2002
	Masahiro Fujita , Yusuke Matsunaga , Taeko Kakuda, On variable ordering of binary decision diagrams for the application of multi-level logic synthesis, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Shin-Ichi Minato , F. Somenzi, Arithmetic Boolean Expression Manipulator Using BDDs, Formal Methods in System Design, v.10 n.2-3, p.221-242, April -May 1997
	Detlef Sieling, The nonapproximability of OBDD minimization, Information and Computation, v.172 n.2, p.103-138, January 29, 2002
	Farn Wang, Symbolic Parametric Safety Analysis of Linear Hybrid Systems with BDD-Like Data-Structures, IEEE Transactions on Software Engineering, v.31 n.1, p.38-51, January 2005
	Tsutomu Sasao , Munehiro Matsuura, BDD representation for incompletely specifiedvmultiple-output logic functions and its applications to functional decomposition, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Pejman Lotfi-Kamran , Mohammad Hosseinabady , Hamid Shojaei , Mehran Massoumi , Zainalabedin Navabi, TED+: a data structure for microprocessor verification, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Hiroki Nakahara , Tsutomu Sasao , Munehiro Matsuura, A fast logic simulator using a look up table cascade emulator, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Christel Baier , Marjan Sirjani , Farhad Arbab , Jan Rutten, Modeling component connectors in Reo by constraint automata, Science of Computer Programming, v.61 n.2, p.75-113, July 2006
	Christoph Meinel , Christian Stangier, Data structures for Boolean functions, Computational Discrete Mathematics: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2001
	Olaf Schröer , Ingo Wegener, The Theory of Zero-Suppressed BDDs and the Number of Knight‘s Tours, Formal Methods in System Design, v.13 n.3, p.235-253, Nov. 1998
	A. Hett , R. Drechsler , B. Becker, Fast and Efficient Construction of BDDs by Reordering Based Synthesis, Proceedings of the 1997 European conference on Design and Test, p.168, March 17-20, 1997
	Ansaf Salleb-Aouissi , Christel Vrain, A Contribution to the Use of Decision Diagrams for Loading and Mining Transaction Databases, Fundamenta Informaticae, v.78 n.4, p.575-594, December 2007
	Tobias Blechmann , Christel Baier, Checking Equivalence for Reo Networks, Electronic Notes in Theoretical Computer Science (ENTCS), 215, p.209-226, June, 2008
	Stanislav StankoviĆ , Jaakko Astola, XML Framework for Various Types of Decision Diagrams for Discrete Functions, IEICE - Transactions on Information and Systems, v.E90-D n.11, p.1731-1740, November 2007
	Munehiro Matsuura , Tsutomu Sasao, BDD Representation for Incompletely Specified Multiple-Output Logic Functions and Its Applications to the Design of LUT Cascades, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.12, p.2762-2769, December 2007
	Orna Grumberg , Shlomi Livne , Shaul Markovitch, Learning to order BDD variables in verification, Journal of Artificial Intelligence Research, v.18 n.1, p.83-116, January 2003