Fast Walsh–Hadamard transform
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/04/Fast_walsh_hadamard_transform_8.svg/250px-Fast_walsh_hadamard_transform_8.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/58/1010_0110_Walsh_spectrum_%28fast_WHT%29.svg/400px-1010_0110_Walsh_spectrum_%28fast_WHT%29.svg.png)
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 would have a computational complexity of O(). The FWHTh requires only additions or subtractions.
The FWHTh is a divide-and-conquer algorithm that recursively breaks down a WHT of size into two smaller WHTs of size . [1] This implementation follows the recursive definition of the Hadamard matrix :
The 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 , where A is m-th root of . [2]
Python example code
def fwht(a) -> None: """In-place Fast Walsh–Hadamard Transform of array a.""" 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
References
External links
- Charles Constantine Gumas, A century old, the fast Hadamard transform proves useful in digital communications
- v
- t
- e
![]() | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |
- v
- t
- e