Characterizing And Enumerating Walsh-hadamard Transform Algorithms

Serre François, Püschel Markus. Arxiv 2017

[Paper]    
ARXIV Independent

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\)) interleaved by linear permutations. Linear permutations are those that map linearly the binary representation of its element indices. We also propose a method to enumerate these algorithms.

Similar Work