Fast Walsh–Hadamard transform

In computational mathematics, the Hadamard ordered fast Walsh–Hadamard transform (FWHTh) is an efficient <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> to compute the <a href="/facts/Walsh%25E2%2580%2593Hadamard_transform/JFD5uojA">Walsh–Hadamard transform</a> (WHT). A naive implementation of the WHT of order 
 
 
 
 n
 =
 
 2
 
 m
 
 
 
 
 {\displaystyle n=2^{m}}
 
 would have a <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity</a> of <a href="/facts/Big_O_notation/weFFjSWg">O(
 
 
 
 
 n
 
 2
 
 
 
 
 {\displaystyle n^{2}}
 
)</a>. The FWHTh requires only 
 
 
 
 n
 log
 ⁡
 n
 
 
 {\displaystyle n\log n}
 
 additions or subtractions.
The FWHTh is a <a href="/facts/Divide-and-conquer_algorithm/pC1X7Ws7">divide-and-conquer algorithm</a> that <a href="/facts/Recursion/CxSKxJoW">recursively</a> breaks down a WHT of size 
 
 
 
 n
 
 
 {\displaystyle n}
 
 into two smaller WHTs of size 
 
 
 
 n
 
 /
 
 2
 
 
 {\displaystyle n/2}
 
. This implementation follows the recursive definition of the 
 
 
 
 
 2
 
 m
 
 
 ×
 
 2
 
 m
 
 
 
 
 {\displaystyle 2^{m}\times 2^{m}}
 
 <a href="/facts/Hadamard_matrix/q56o9lgM">Hadamard matrix</a> 
 
 
 
 
 H
 
 m
 
 
 
 
 {\displaystyle H_{m}}
 
:

H
          
            m
          
        
        =
        
          
            1
            
              2
            
          
        
        
          
            (
            
              
                
                  
                    H
                    
                      m
                      −
                      1
                    
                  
                
                
                  
                    H
                    
                      m
                      −
                      1
                    
                  
                
              
              
                
                  
                    H
                    
                      m
                      −
                      1
                    
                  
                
                
                  −
                  
                    H
                    
                      m
                      −
                      1
                    
                  
                
              
            
            )
          
        
        .
      
    
    {\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}.}

The 
 
 
 
 1
 
 /
 
 
 
 2
 
 
 
 
 {\displaystyle 1/{\sqrt {2}}}
 
 normalization factors for each stage may be grouped together or even omitted.
The <a href="/facts/Walsh_matrix/0jjH6Ms2">sequency-ordered</a>, 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 
 
 
 
 
 H
 
 m
 
 
 =
 
 A
 
 m
 
 
 
 
 {\displaystyle H_{m}=A^{m}}
 
, where A is m-th root of 
 
 
 
 
 H
 
 m
 
 
 
 
 {\displaystyle H_{m}}
 
.

Fast Walsh–Hadamard transform open-in-new

Fast Walsh–Hadamard transform