In computational mathematics, the Hadamard ordered fast Walsh–Hadamard transform (FWHTh) is an efficient algorithm to compute the Walsh–Hadamard transform (WHT). A naive implementation of the WHT of order n = 2^m would have a computational complexity of O(n^2). The FWHTh requires only n \log n additions or subtractions. The FWHTh 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 Hadamard matrix H_m: The 1/\sqrt2 normalization factors for each stage may be grouped together or even omitted. The sequency-ordered, also known as Walsh-ordered, fast Walsh–Hadamard transform, FWHTw, is obtained by computing the FWHTh as above, and then rearranging the outputs. A simple fast nonrecursive implementation of the Walsh–Hadamard transform follows from decomposition of the Hadamard transform matrix as H_m = A^m, where A is m-th root of H_m.

Python example code