Zero suppressed decision diagram
From Wikipedia, the free encyclopedia
 |
Please help improve this article or section by expanding it. Further information might be found on the talk page or at requests for expansion. (April 2008) |
A zero suppressed decision diagram (ZSDD or ZDD) is a version of binary decision diagram (BDD) where instead of nodes being introduced when the positive and the negative part are different, they are introduced when negative part is different from constant 0. Zero suppressed decisions diagrams are also commonly referred to as zero suppressed binary decision diagram (ZBDD).
They are useful when dealing with functions which are almost everywhere 0.
[edit] Available packages
- CUDD: A BDD package written in C that implements BDDs and ZBDDs, University of Colorado, Boulder
- JDD, A java library that implements common BDD and ZBDD operations
[edit] References
- Shin-ichi Minato, "Zero-suppressed BDDs for set manipulation in combinatorial problems", DAC '93: Proceedings of the 30th international conference on Design automation, 1993
- Ch. Meinel, T. Theobald, "Algorithms and Data Structures in VLSI-Design: OBDD - Foundations and Applications", Springer-Verlag, Berlin, Heidelberg, New York, 1998.
[edit] External links
- Alan Mishchenko, ["http://www.eecs.berkeley.edu/~alanmi/publications/2001/tech01_zdd.pdf An Introduction to Zero-Suppressed Binary Decision Diagrams"]
