Efficient variable ordering and partial representation algorithm

New Delhi, India January 04-January 07

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/ICVD.1995.512082

8th International Conference on VLSI ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by J. Jain Articles by D. Moundanos Articles by J. Bitner Articles by J.A. Abraham Articles by D.S. Fussell Articles by D.E. Ross

	ASCII Text	x
	J. Jain, D. Moundanos, J. Bitner, J.A. Abraham, D.S. Fussell, D.E. Ross, "Efficient variable ordering and partial representation algorithm," VLSI Design, International Conference on, pp. 81, 8th International Conference on VLSI Design, 1995.

	BibTex	x
	@article{ 10.1109/ICVD.1995.512082, author = {J. Jain and D. Moundanos and J. Bitner and J.A. Abraham and D.S. Fussell and D.E. Ross}, title = {Efficient variable ordering and partial representation algorithm}, journal ={VLSI Design, International Conference on}, volume = {0}, year = {1995}, isbn = {0-8186-6905-5}, pages = {81}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICVD.1995.512082}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - VLSI Design, International Conference on TI - Efficient variable ordering and partial representation algorithm SN - 0-8186-6905-5 SP EP A1 - J. Jain, A1 - D. Moundanos, A1 - J. Bitner, A1 - J.A. Abraham, A1 - D.S. Fussell, A1 - D.E. Ross, PY - 1995 KW - logic CAD; Boolean functions; data structures; VLSI; variable ordering; partial representation algorithm; ordered partial decision diagrams; truth table; Boolean function; data structures; BDDs; information-theoretic criteria; entropy; CAD problems VL - 0 JA - VLSI Design, International Conference on ER -

J. Jain, Fujitsu Lab. of America, San Jose, CA, USA

D. Moundanos, Fujitsu Lab. of America, San Jose, CA, USA

J. Bitner, Fujitsu Lab. of America, San Jose, CA, USA

J.A. Abraham, Fujitsu Lab. of America, San Jose, CA, USA

D.S. Fussell, Fujitsu Lab. of America, San Jose, CA, USA

D.E. Ross, Fujitsu Lab. of America, San Jose, CA, USA

In this paper we introduce some new methods for constructing Ordered Partial Decision Diagrams (OPDDs), The algorithms are effective in capturing a significant fraction of a given function's truth table using only a very small space. Using such data structures the importance of a variable in a Boolean function can be computed. Such methods can easily be used for computing effective variable orders to construct BDDs. The measures of a variable's importance are based on information-theoretic criteria, and require computation of the entropy of a variable for a given function. We have found that entropy measures can be quite efficient in distinguishing the importance of variables, and at times provide very effective variable order. The results show an encouraging approach towards the understanding and the solution of this well known problem.

Index Terms:

logic CAD; Boolean functions; data structures; VLSI; variable ordering; partial representation algorithm; ordered partial decision diagrams; truth table; Boolean function; data structures; BDDs; information-theoretic criteria; entropy; CAD problems

Citation:

J. Jain, D. Moundanos, J. Bitner, J.A. Abraham, D.S. Fussell, D.E. Ross, "Efficient variable ordering and partial representation algorithm," vlsid, pp.81, 8th International Conference on VLSI Design, 1995

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.