Fast Walsh–Hadamard transform

From Wikipedia, the free encyclopedia

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

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 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 $2 N$ into two smaller WHTs of size $2 N - 1$ . This implementation follows the recursive definition of the $N \times N$ 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, FWHT_w, is obtained by computing the FWHT_h as above, and then rearranging the outputs.