Fast Walsh–Hadamard transform

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

Divide-and-conquer algorithm to compute a Hadamard transform

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}$ {\displaystyle n=2^{m}} would have a computational complexity of O( $n^{2}$ {\displaystyle n^{2}}). The FWHT_h requires only $n\log n$ {\displaystyle n\log n} additions or subtractions.

The FWHT_h is a divide-and-conquer algorithm that recursively breaks down a WHT of size $n$ {\displaystyle n} into two smaller WHTs of size $n/2$ {\displaystyle n/2}. ^[1] This implementation follows the recursive definition of the $2^{m}\times 2^{m}$ {\displaystyle 2^{m}\times 2^{m}} Hadamard matrix $H_{m}$ {\displaystyle H_{m}}:

H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.

{\displaystyle 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}}$ {\displaystyle 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}$ {\displaystyle H_{m}=A^{m}}, where A is m-th root of $H_{m}$ {\displaystyle H_{m}}. ^[2]

Python example code

[edit ]

importmath
deffwht(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

References

[edit ]

^ Fino, B. J.; Algazi, V. R. (1976). "Unified Matrix Treatment of the Fast Walsh–Hadamard Transform". IEEE Transactions on Computers. 25 (11): 1142–1146. doi:10.1109/TC.1976.1674569. S2CID 13252360.
^ Yarlagadda and Hershey, "Hadamard Matrix Analysis and Synthesis", 1997 (Springer)