Fast Walsh–Hadamard transform

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

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

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

This signal processing-related article is a stub.

You can help Wikipedia by expanding it.This algorithms or data structures-related article is a stub.