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 would have a computational complexity of O(). The FWHTh requires only additions or subtractions.

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)

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 /= 2
        h *= 2

See also

References
  1. Fino, B. J.; Algazi, V. R. (1976). "Unified Matrix Treatment of the Fast Walsh–Hadamard Transform". IEEE Transactions on Computers. 25 (11): 1142–1146. doi:10.1109/TC.1976.1674569. S2CID 13252360.
  2. Yarlagadda and Hershey, "Hadamard Matrix Analysis and Synthesis", 1997 (Springer)


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.