Spectral transforms for large boolean functions with applications to technology mapping

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spectral transforms for large boolean functions with applications to technology mapping

Full text

Pdf (622 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 30th international Design Automation Conference table of contents

Dallas, Texas, United States

Pages: 54 - 60

Year of Publication: 1993

ISBN:0-89791-577-1

Authors

E. M. Clarke
K. L. McMillan
X Zhao
M. Fujita
J. Yang

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 18, Citation Count: 52

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/157485.164569 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	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]
	2	M. A. Harrison. Introduction to switching and automata theory. McGraw-Hill, 1965.
	3	Stanley L. Hurst , Jon C. Muzio , D. Michael Miller, Spectral Techniques in Digital Logic, Academic Press, Inc., Orlando, FL, 1985
	4	R. J. Lechner. A transform approach to logic design. IEEE Transactions on Computers, C-19(7), 1970.
	5	Frédéric Mailhot , Giovanni De Micheli, Technology mapping using boolean matching and don't care sets, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	6	Giovanni De Micheli , David Ku , Frederic Mailhot , Thomas Truong, The Olympus Synthesis System, IEEE Design & Test, v.7 n.5, p.37-53, September 1990 [doi>10.1109/54.60605]
	7	Jerry C Yang , Giovanni DeMicheli, Spectral Techniques for Technology Mapping, Stanford University, Stanford, CA, 1994

CITED BY 52

	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
	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
	Enrico Macii , Massimo Poncino, Predicting the functional complexity of combinational circuits by symbolic spectral analysis of Boolean functions, Proceedings of the conference on European design automation, p.294-299, September 18-22, 1995, Brighton, England
	Debatosh Debnath , Tsutomu Sasao, Exact minimization of fixed polarity Reed-Muller expressions for incompletely specified functions, Proceedings of the 2000 conference on Asia South Pacific design automation, p.247-252, January 2000, Yokohama, Japan
	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
	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
	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
	Zheng Zhou , Wayne Burleson, Equivalence checking of datapaths based on canonical arithmetic expressions, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.546-551, June 12-16, 1995, San Francisco, California, United States
	James Smith , Giovanni De Micheli, Polynomial methods for component matching and verification, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.678-685, 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
	R. Iris Bahar , Erica A. Frohm , Charles M. Gaona , Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Algebraic decision diagrams and their applications, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.188-191, November 07-11, 1993, Santa Clara, California, United States
	James Smith , Giovanni De Micheli, Polynomial circuit models for component matching in high-level synthesis, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.9 n.6, p.783-800, 12/1/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
	Paul Tafertshofer , Massoud Pedram, Factored Edge-Valued Binary Decision Diagrams, Formal Methods in System Design, v.10 n.2-3, p.243-270, April -May 1997
	Kiyoharu Hamaguchi , Akihito Morita , Shuzo Yajima, Efficient construction of binary moment diagrams for verifying arithmetic circuits, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.78-82, November 05-09, 1995, San Jose, California, United States
	Christoph Kern , Mark R. Greenstreet, Formal verification in hardware design: a survey, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.2, p.123-193, April 1999
	Shin-ichi Minato, Streaming BDD Manipulation, IEEE Transactions on Computers, v.51 n.5, p.474-485, May 2002
	Jeffery P. Hansen , Masatoshi Sekine, Synthesis by spectral translation using Boolean decision diagrams, Proceedings of the 33rd annual conference on Design automation, p.248-253, June 03-07, 1996, Las Vegas, Nevada, United States
	Christoph Scholl , Bernd Becker, Checking equivalence for partial implementations, Proceedings of the 38th conference on Design automation, p.238-243, June 2001, Las Vegas, Nevada, United States
	Randal E. Bryant , Christoph Meinel, Ordered binary decision diagrams, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Luca Benini , Giovanni De Micheli, A survey of Boolean matching techniques for library binding, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.2 n.3, p.193-226, July 1997
	M. Thornton , R. Drechsler, Spectral decision diagrams using graph transformations, Proceedings of the conference on Design, automation and test in Europe, p.713-719, March 2001, Munich, Germany
	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
	Janett Mohnke , Paul Molitor , Sharad Malik, Limits of Using Signatures for Permutation Independent Boolean Comparison, Formal Methods in System Design, v.21 n.2, p.167-191, September 2002
	Yung-Te Lai , Massoud Pedram , Sarma B. K. Vrudhula, Formal Verification Using Edge-Valued Binary Decision Diagrams, IEEE Transactions on Computers, v.45 n.2, p.247-255, February 1996
	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
	Jürgen Ruf , Thomas Kropf, Symbolic Verification and Analysis of Discrete Timed Systems, Formal Methods in System Design, v.23 n.1, p.67-108, July 2003
	Edmund M. Clarke , Bernd-Holger Schlingloff, Model checking, Handbook of automated reasoning, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 2001
	R. I. Bahar , E. A. Frohm , C. M. Gaona , G. D. Hachtel , E. Macii , A. Pardo , F. Somenzi, Algebric Decision Diagrams and Their Applications, Formal Methods in System Design, v.10 n.2-3, p.171-206, April -May 1997
	M. Fujita , P. C. McGeer , J. C.-Y. Yang, Multi-Terminal Binary Decision Diagrams: An Efficient DataStructure for Matrix Representation, Formal Methods in System Design, v.10 n.2-3, p.149-169, April -May 1997
	Jürgen Ruf , Thomas Kropf, Analyzing real-time systems, Proceedings of the conference on Design, automation and test in Europe, p.243-249, March 27-30, 2000, Paris, France
	Randal E. Bryant , Yirng-An Chen, Verification of arithmetic circuits with binary moment diagrams, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.535-541, June 12-16, 1995, San Francisco, California, United States
	Rolf Drechsler, Verifying integrity of decision diagrams, Integration, the VLSI Journal, v.32 n.1-3, p.61-75, November 2002
	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
	Bogdan J. Falkowski , Chip-Hong Chang, Forward and Inverse Transformations Between Haar Spectra and Ordered Binary Decision Diagrams of Boolean Functions, IEEE Transactions on Computers, v.46 n.11, p.1272-1279, November 1997
	Dragan Jankovic , Radomir S. Stankovic , Rolf Drechsler, Decision Diagram Method for Calculation of Pruned Walsh Transform, IEEE Transactions on Computers, v.50 n.2, p.147-157, February 2001
	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
	Kanupriya Gulati , Nikhil Jayakumar , Sunil P. Khatri, An algebraic decision diagram (ADD) based technique to find leakage histograms of combinational designs, Proceedings of the 2005 international symposium on Low power electronics and design, August 08-10, 2005, San Diego, CA, USA
	Mohammad Ali Ghodrat , Tony Givargis , Alex Nicolau, Equivalence checking of arithmetic expressions using fast evaluation, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA
	Henrik Reif Andersen , Henrik Hulgaard, Boolean expression diagrams, Information and Computation, v.179 n.2, p.194-212, December 15, 2002
	René Krenz , Elena Dubrova, Improved Boolean function hashing based on multiple-vertex dominators, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Jawahar Jain , James Bitner , Magdy S. Abadir , Jacob A. Abraham , Donald S. Fussell, Indexed BDDs: Algorithmic Advances in Techniques to Represent and Verify Boolean Functions, IEEE Transactions on Computers, v.46 n.11, p.1230-1245, November 1997
	Alfred Koelbl , Carl Pixley, Constructing efficient formal models from high-level descriptions using symbolic simulation, International Journal of Parallel Programming, v.33 n.6, p.645-666, December 2005
	Tomasz S. Czajkowski , Stephen D. Brown, Functionally linear decomposition and synthesis of logic circuits for FPGAs, Proceedings of the 45th annual conference on Design automation, June 08-13, 2008, Anaheim, California
	Håkan L. S. Younes , Reid G. Simmons, Statistical probabilistic model checking with a focus on time-bounded properties, Information and Computation, v.204 n.9, p.1368-1409, September 2006
	Donald Chai , Andreas Kuehlmann, Building a better Boolean matcher and symmetry detector, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	James Smith , Giovanni De Micheli, Polynomial methods for allocating complex components, Proceedings of the conference on Design, automation and test in Europe, p.45-es, January 1999, Munich, Germany
	C. Moraga , T. Sasao , R. Stanković, A Unifying Approach to Edge-valued and Arithmetic Transform Decision Diagrams, Automation and Remote Control, v.63 n.1, p.125-138, January 2002
	Tsutomu Sasao , Shinobu Nagayama , Jon T. Butler, Numerical Function Generators Using LUT Cascades, IEEE Transactions on Computers, v.56 n.6, p.826-838, June 2007
	Peter Bazan , Reinhard German, Approximate transient analysis of large stochastic models with WinPEPSY-QNS, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.53 n.8, p.1289-1301, June, 2009
	Håkan L. S. Younes, Planning and execution with phase transitions, Proceedings of the 20th national conference on Artificial intelligence, p.1030-1035, July 09-13, 2005, Pittsburgh, Pennsylvania
	Shinobu Nagayama , Tsutomu Sasao , Jon T. Butler, Design Method for Numerical Function Generators Using Recursive Segmentation and EVBDDs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E90-A n.12, p.2752-2761, December 2007