The Cascading Haar Wavelet algorithm for computing the Walsh-Hadamard Transform

A novel algorithm for computing the Walsh–Hadamard transform (WHT) is proposed, which consists entirely of Haar wavelet transforms. It is proved that the algorithm, referred to as the cascading Haar wavelet algorithm, shares precisely the same serial complexity as the popular divide-and-conquer algorithm for the WHT. A natural parallelization of the algorithm is also proposed, which has a number of attractive features.