Fast Walsh–Hadamard transform

In computational mathematics, the Hadamard ordered fast Walsh–Hadamard transform (FWHT_h) is an efficient algorithm to compute the Walsh–Hadamard transform (WHT). A naive implementation of the WHT would have a computational complexity of O( N 2 ). The FWHT_h requires only N log ⁡ N additions or subtractions.

The FWHT_h is a divide and conquer algorithm that recursively breaks down a WHT of size N into two smaller WHTs of size N / 2 . This implementation follows the recursive definition of the 2 N × 2 N Hadamard matrix H N :

The 1 / 2 normalization factors for each stage may be grouped together or even omitted.

The sequency ordered, also known as Walsh ordered, fast Walsh–Hadamard transform, FWHT_w, is obtained by computing the FWHT_h as above, and then rearranging the outputs.