Efficient representation and manipulation of switching functions based on ordered Kronecker functional decision diagrams

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient representation and manipulation of switching functions based on ordered Kronecker functional decision diagrams

Full text

Pdf (158 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 31st annual Design Automation Conference table of contents

San Diego, California, United States

Pages: 415 - 419

Year of Publication: 1994

ISBN:0-89791-653-0

Authors

R. Drechsler	Computer Science Department, Johann Wolfgang Goethe University, D-60054 Frankfurt am Main, Germany
A. Sarabi	Department of Electrical Engineering, Portland State University, Portland, OR
M. Theobald	Computer Science Department, Johann Wolfgang Goethe University, D-60054 Frankfurt am Main, Germany
B. Becker	Computer Science Department, Johann Wolfgang Goethe University, D-60054 Frankfurt am Main, Germany
M. A. Perkowski	Department of Electrical Engineering, Portland State University, Portland, OR

Sponsors

IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation
EDAC : Electronic Design Automation Consortium

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 16, Citation Count: 39

Additional Information:

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/196244.196444 What is a DOI?

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	B. Becker, R. Drechsler, and M. Theobald, On the Implementation of a Package for Efficient Representation and Manipulation of Functional Decision Diagrams, IFIP WG 10.5 Workshop on Appl. of Reed- Muller Expans. in Circ. Design, 1993.
	2	B. Becker, R. Drechsler, and R. Werchner, On the Relation Between BDDs and FDDs, Technical report, University of Frankfurt, 12/93, 1993.
	3	Karl S. Brace , Richard L. Rudell , Randal E. Bryant, Efficient implementation of a BDD package, Proceedings of the 27th ACM/IEEE conference on Design automation, p.40-45, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123222]
	4	Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
	5	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]
	6	Randal E. Bryant, Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys (CSUR), v.24 n.3, p.293-318, Sept. 1992 [doi>10.1145/136035.136043]
	7	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
	8	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 [doi>10.1109/12.324545]
	9	N. Ishiura, H. Sawada, and S. Yajima, Minimization of Binary Decision Diagrams Based on Exchange of Variables, Proc. Int. Conf. on Computer-Aided Design, pages 472-475, 1991.
	10	U. Kebschull, E. Schubert, and W. Rosenstiel, Multilevel Logic Based on Functional Decision Diagrams, Proc. European Design Automation Conf., pages 43- 47, 1992.
	11	S. Malik, A. R. Wang, R. K. Brayton, and A. L. Sangiovanni-Vincentelli, Logic Verification Using Binary Decision Diagrams in a Logic Synthesis Environment, Proc. Int. Conf. on Computer-Aided Design, pages 6-9, 1988.
	12	Shin-ichi Minato , Nagisa Ishiura , Shuzo Yajima, Shared binary decision diagram with attributed edges for efficient Boolean function manipulation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.52-57, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123225]
	13	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
	14	A. Sarabi , M. A. Perkowski, Fast exact and quasi-minimal minimization of highly testable fixed-polarity AND/XOR canonical networks, Proceedings of the 29th ACM/IEEE conference on Design automation, p.30-35, June 08-12, 1992, Anaheim, California, United States
	15	A. Sarabi, P. F. Ho, K. Iravani, W. R. Daasch, and M. A. Perkowski, Minimal Multi-Level Realization of Switching Functions Based on Kronecker Functional Decision Diagrams, Int. Workshop on Logic Synth., pages P3a:l-6, 1993.
	16	Tsutomu Sasao, Logic Synthesis and Optimization, Kluwer Academic Publishers, Norwell, MA, 1997
	17	T. Sasao , P. Besslich, On the Complexity of Mod-2l Sum PLA's, IEEE Transactions on Computers, v.39 n.2, p.262-266, February 1990 [doi>10.1109/12.45212]

CITED BY 39

	Randal E. Bryant, Binary decision diagrams and beyond: enabling technologies for formal verification, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.236-243, November 05-09, 1995, San Jose, California, United States
	S. Höreth , R. Drechsler, Dynamic minimization of word-level decision diagrams, Proceedings of the conference on Design, automation and test in Europe, p.612-617, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Rolf Drechsler , Bernd Becker , Michael Theobald, Fast OFDD based minimization of fixed polarity Reed-Muller expressions, Proceedings of the conference on European design automation, p.2-7, September 19-23, 1994, Grenoble, France
	Amit Narayan , Jawahar Jain , M. Fujita , A. Sangiovanni-Vincentelli, Partitioned ROBDDs—a compact, canonical and efficiently manipulable representation for Boolean functions, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.547-554, November 10-14, 1996, San Jose, California, United States
	Jawahar Jain , William Adams , Masahiro Fujita, Sampling schemes for computing OBDD variable orderings, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.631-638, November 08-12, 1998, San Jose, California, United States
	Yirng-An Chen , Randal E. Bryant, PHDD: an efficient graph representation for floating point circuit verification, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.2-7, November 09-13, 1997, San Jose, California, United States
	Christoph Scholl , Bernd Becker , Thomas M. Weis, Word-level decision diagrams, WLCDs and division, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.672-677, November 08-12, 1998, San Jose, California, United States
	Subdodh M. Reddy , Wolfgang Kunz , Dhiraj K. Pradhan, Novel verification framework combining structural and OBDD methods in a synthesis environment, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.414-419, June 12-16, 1995, San Francisco, California, United States
	E. M. Clarke , M. Fujita , X. Zhao, Hybrid decision diagrams, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.159-163, November 05-09, 1995, San Jose, California, United States
	Unni Narayanan , C. L. Liu, Low power logic synthesis for XOR based circuits, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.570-574, November 09-13, 1997, San Jose, California, United States
	Marek A. Perkowski , Philip Ho, Free Kronecker decision diagrams and their application to Atmel 6000 series FPGA mapping, Proceedings of the conference on European design automation, p.8-13, September 19-23, 1994, Grenoble, France
	Rolf Drechsler, BiTeS: a BDD based test pattern generator for strong robust path delay faults, Proceedings of the conference on European design automation, p.322-327, September 19-23, 1994, Grenoble, France
	Yibin Ye , Kaushik Roy, A graph-based synthesis algorithm for AND/XOR networks, Proceedings of the 34th annual conference on Design automation, p.107-112, June 09-13, 1997, Anaheim, California, United States
	Randal E. Bryant , Christoph Meinel, Ordered binary decision diagrams, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Whitney J. Townsend , Mitchell A. Thornton , Rolf Drechsler , D. Michael Miller, Computing walsh, arithmetic, and reed-muller spectral decision diagrams using graph transformations, Proceedings of the 12th ACM Great Lakes symposium on VLSI, April 18-19, 2002, New York, New York, USA
	Bwolen Yang , David R. O'Hallaron, Parallel breadth-first BDD construction, ACM SIGPLAN Notices, v.32 n.7, p.145-156, July 1997
	Wolfgang Günther , Rolf Drechsler, Efficient manipulation algorithms for linearly transformed BDDs, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.50-54, November 07-11, 1999, San Jose, California, United States
	Amit Narayan , Adrian J. Isles , Jawahar Jain , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Reachability analysis using partitioned-ROBDDs, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.388-393, November 09-13, 1997, San Jose, California, United States
	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
	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
	Radomir S. Stanković, Non-Abelian Groups in Optimization of Decision Diagrams Representations of Discrete Functions, Formal Methods in System Design, v.18 n.3, p.209-231, May 2001
	J. Jain , K. Mohanram , D. Moundanos , I. Wegener , Y. Lu, Analysis of composition complexity and how to obtain smaller canonical graphs, Proceedings of the 37th conference on Design automation, p.681-686, June 05-09, 2000, Los Angeles, California, United States
	Detlef Sieling, Lower bounds for linearly transformed OBDDs and FBDDs, Journal of Computer and System Sciences, v.64 n.2, p.419-438, March 2002
	Rolf Drechsler, Verifying integrity of decision diagrams, Integration, the VLSI Journal, v.32 n.1-3, p.61-75, November 2002
	Rolf Drechsler , Bernd Becker , Stefan Ruppertz, The K*BMD: A Verification Data Structure, IEEE Design & Test, v.14 n.2, p.51-59, April 1997
	Rolf Drechsler , Michael Theobald , Bernd Becker, Fast OFDD-Based Minimization of Fixed Polarity Reed-Muller Expressions, IEEE Transactions on Computers, v.45 n.11, p.1294-1299, November 1996
	John Lafferty , Alexander Vardy, Ordered Binary Decision Diagrams and Minimal Trellises, IEEE Transactions on Computers, v.48 n.9, p.971-986, September 1999
	Christoph Scholl , Bernd Becker , Thomas Weis, On WLCDs and the Complexity of Word-Level Decision Diagrams—A Lower Bound for Division, Formal Methods in System Design, v.20 n.3, p.311-326, May 2002
	Bernd Becker , Rolf Drechsler , Michael Theobald, On the Expressive Power of OKFDDs, Formal Methods in System Design, v.11 n.1, p.5-21, July 1997
	Henrik Reif Andersen , Henrik Hulgaard, Boolean expression diagrams, Information and Computation, v.179 n.2, p.194-212, December 15, 2002
	Rolf Drechsler , Bernd Becker , Andrea Jahnke, On Variable Ordering and Decomposition Type Choice in OKFDDs, IEEE Transactions on Computers, v.47 n.12, p.1398-1403, December 1998
	Christoph Meinel , Christian Stangier, Data structures for Boolean functions, Computational Discrete Mathematics: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2001
	Stefan Höreth , Rolf Drechsler, Formal verification of word-level specifications, Proceedings of the conference on Design, automation and test in Europe, p.11-es, January 1999, Munich, Germany
	R. Drechsler , B. Becker, Sympathy: fast exact minimization of fixed polarity Reed-Muller expressions for symmetric functions, Proceedings of the 1995 European conference on Design and Test, p.91, March 06-09, 1995
	B. Becker , R. Drechsler, How many decomposition types do we need? [decision diagrams], Proceedings of the 1995 European conference on Design and Test, p.438, March 06-09, 1995
	B. Becker , R. Drechsler, Synthesis for testability: circuits derived from ordered Kronecker functional decision diagrams, Proceedings of the 1995 European conference on Design and Test, p.592, March 06-09, 1995
	Rolf Drechsler , Bernd Becker , Stefan Ruppertz, K*BMDs: A New Data Structure for Verification, Proceedings of the 1996 European conference on Design and Test, p.2, March 11-14, 1996
	Julian F. Miller , Dominic Job , Vesselin K. Vassilev, Principles in the Evolutionary Design of Digital Circuits—Part I, Genetic Programming and Evolvable Machines, v.1 n.1-2, p.7-35, April 2000
	Rolf Drechsler , Bernd Becker , Nicole Göckel, A genetic algorithm for the construction of small and highly testable OKFDD-circuits, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California