
CMUCS97149
Computer Science Department
School of Computer Science, Carnegie Mellon University
CMUCS97149
Hybrid Spectral Transform Diagrams
Edmund M. Clarke, Masahiro Fujita*, Wolfgang Heinle**
June 1997
CMUCS97149.ps
Keywords: (MultiTerminal) binary decision diagrams, hybrid transform
diagrams, (Hybrid) spectral transformation, Walsh transform, ReedMuller
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 ReedMuller 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 datastructure 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.
