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 $2^{m}\times 2^{m}$ Hadamard matrix $H_{m}$ :

$H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.$ The $1/{\sqrt {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, 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

def fwht(a) -> None:
"""In-place Fast Walsh–Hadamard Transform of array a."""
h = 1
while h < len(a):
for i in range(0, len(a), h * 2):
for j in range(i, i + h):
x = a[j]
y = a[j + h]
a[j] = x + y
a[j + h] = x - y
h *= 2