Fast Walsh–Hadamard transform

The fast Walsh–Hadamard transform applied to a vector of length 8
Example for the input vector (1,0,1,0,0,1,1,0)

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 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 2N \times 2N Hadamard matrix H_N:

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

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, FWHTw, is obtained by computing the FWHTh as above, and then rearranging the outputs.

See also

References

External links


This article is issued from Wikipedia - version of the Thursday, September 10, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.