title: Fast Sequency-ordered Walsh-Hadamard Transform
body: <p><strong>EDIT</strong> You can checkout my implementation on Github: <a href="https://github.com/Sheljohn/WalshHadamard" rel="nofollow">https://github.com/Sheljohn/WalshHadamard</a></p>
  
  <hr>
  
  <p>I am looking for an implementation, or indications on how to implement, the <strong>sequency-ordered</strong> Fast Walsh Hadamard transform (see <a href="http://en.wikipedia.org/wiki/Hadamard_transform" rel="nofollow">this</a> and <a href="http://en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform" rel="nofollow">this</a>).</p>
  
  <p>I slightly adapted a very nice implementation found <a href="http://www.musicdsp.org/showone.php?id=18" rel="nofollow">online</a>:</p>
  
  <pre><code>// (a,b) -&gt; (a+b,a-b) without overflow
  void rotate( long&amp; a, long&amp; b )
  {
      static long t;
      t = a;
      a = a + b;
      b = t - b;
  }
  
  // Integer log2
  long ilog2( long x )
  {
      long l2 = 0;
      for (; x; x &gt;&gt;=1) ++l2;
      return l2;
  }
  
  /**
   * Fast Walsh-Hadamard transform
   */
  void fwht( std::vector&lt;long&gt;&amp; data )
  {
      const long l2 = ilog2(data.size()) - 1;
  
      for (long i = 0; i &lt; l2; ++i)
      {
          for (long j = 0; j &lt; (1 &lt;&lt; l2); j += 1 &lt;&lt; (i+1))
          for (long k = 0; k &lt; (1 &lt;&lt; i ); ++k)
              rotate( data[j + k], data[j + k + (1&lt;&lt;i)] );
      }
  }
  </code></pre>
  
  <p>but it does not compute the WHT in sequency order (the natural Hadamard matrix is used implicitly). Note that in the code above (and if you try it), the size of data needs to be a power of 2.</p>
  
  <p>My question is: is there a simple adaptation of this implementation that gives the sequency-ordered FWHT?</p>
  
  <p>A possible solution would be to write a small function to compute dynamically the elements of Hn (the Hadamard matrix of order n), count the number of zero crossings, and create a ranking of the rows, but I am wondering whether there is a smarter way. Thanks in advance for any input! Cheers</p>