Characterizing and Enumerating Walsh-Hadamard Transform Algorithms

François Serre, Markus Püschel

We propose a way of characterizing the algorithms computing a Walsh-Hadamard transform that consist of a sequence of arrays of butterflies ($I_{2^{n-1}}\otimes {\text{DFT}}_2$) inter…