Decision diagram based techniques for the Haar wavelet transform

This paper describes a new data structure called the “Haar Spectral Diagram” (or HSD) useful for representing the Haar spectrum of Boolean functions. An alternative ordering of Haar coefficients is used to represent the Haar transform matrix in terms of a Kronecker product yielding a natural decision-diagram based representation. The resulting graph is a point-decomposition of the Haar spectrum using “0-element” edge values. For incompletely specified functions, the Haar spectrum represented as an HSD is shown to require no more nodes than the ROBDD for the same function, and for completely specified functions, the HSD is shown to be isomorphic to the ROBDD