Fast Walsh–Hadamard transform

<h2 id="python-example-code">Python example code</h2>
import math
def fwht(a) -> None:
    """In-place Fast Walsh–Hadamard Transform of array a."""
    assert math.log2(len(a)).is_integer(), "length of a is a power of 2"
    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 /= math.sqrt(2)
        h *= 2

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Fast_Fourier_transform/caT7UUCh">Fast Fourier transform</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li>Charles Constantine Gumas, <a href="https://web.archive.org/web/20060513150253/http://archive.chipcenter.com/dsp/DSP000517F1.html">A century old, the fast Hadamard transform proves useful in digital communications</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Yarlagadda and Hershey, "Hadamard Matrix Analysis and Synthesis", 1997 (Springer) <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Fast Walsh–Hadamard transform open-in-new

Fast Walsh–Hadamard transform