CMU-CS-97-149
Computer Science Department
School of Computer Science, Carnegie Mellon University


CMU-CS-97-149

Hybrid Spectral Transform Diagrams

Edmund M. Clarke, Masahiro Fujita*, Wolfgang Heinle**

June 1997

CMU-CS-97-149.ps


Keywords: (Multi-Terminal) binary decision diagrams, hybrid transform diagrams, (Hybrid) spectral transformation, Walsh transform, Reed-Muller transform, spectrum of a boolean function


We give a uniform algebraic framework for computing hybrid spectral transforms in an efficient manner. Based on properties of the Kronecker product, we derive a set of recursive equations, which leads naturally to an algorithm for computing such transforms efficiently. As a result, many applications of transforms like the Walsh transform and the Reed-Muller transform, which were previously impossible because of memory constraints, have now become feasible. The same set of recursive equations also gives a new way of explaining hybrid transform diagrams, an efficient data-structure for integer valued boolean functions.

16 pages

*Fujitsu Laboratories of America, Inc., Santa Clara, California.
**Institut fur Informatik und angewandte Mathematik,
University of Bern, Switzerland.

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by [email protected]