Computer Science Department
School of Computer Science, Carnegie Mellon University
Hybrid Spectral Transform Diagrams
Edmund M. Clarke, Masahiro Fujita*, Wolfgang Heinle**
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
*Fujitsu Laboratories of America, Inc., Santa Clara, California.
**Institut fur Informatik und angewandte Mathematik,
University of Bern, Switzerland.