Fast Walsh–Hadamard transform

File:Fast walsh hadamard transform 8.svg

The fast Walsh–Hadamard transform applied to a vector of length 8

File:1010 0110 Walsh spectrum (fast WHT).svg

Example for the input vector (1, 0, 1, 0, 0, 1, 1, 0)

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{1}{\sqrt{2}}\left(\begin{array}{cc}{H}_{m-1}& H_{m-1}\\ H_{m-1}& -H_{m-1}\end{array}\right).$

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, 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$.

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[j]
                y = a[j + h]
                a[j] = x + y
                a[j + h] = x - y
        # normalize and increment
        a /= math.sqrt(2)
        h *= 2

See also

• Fast Fourier transform

External links

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