In computational mathematics, the Hadamard ordered fast WalshâÂÂHadamard transform (FWHT<sub>h</sub>) 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 FWHT<sub>h</sub> requires only additions or subtractions.
The FWHT<sub>h</sub> is a divide-and-conquer algorithm that recursively breaks down a WHT of size into two smaller WHTs of size . 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, FWHT<sub>w</sub>, is obtained by computing the FWHT<sub>h</sub> 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 .