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 of order $n = 2^m$ 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^m \times 2^m$ Hadamard matrix $H_m$:

:$H_m = \frac \begin H_ & H_ \\ H_ & -H_ \end.$

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, FWHT_''w'', is obtained by computing the FWHT_''h'' 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$. Yarlagadda and Hershey, "Hadamard Matrix Analysis and Synthesis", 1997 (Springer)

Python example code

import math
def fwht(a) -> None:
"""In-place Fast Walsh–Hadamard Transform of array a."""
assert math.log2(len(a)).is_integer(), "length of a is a power of 2"
h = 1
while h < len(a):
# perform FWHT
for i in range(0, len(a), h * 2):
for j in range(i, i + h):
x = a y = a + h a = x + y
a + h= x - y
# normalize and increment
a /= math.sqrt(2)
h *= 2

See also

* Fast Fourier transform

References

External links

* Charles Constantine Gumas
A century old, the fast Hadamard transform proves useful in digital communications

Digital signal processing
Articles with example Python (programming language) code

{{algorithm-stub