Sequency Ordered Walsh-Hadamard Matrix

In order for the elements in the spectrum ${\bf X}=[ X[0], X[1], \cdots, X[N-1] ]^T$ to represent different sequency components contained in the signal in a low-to-high order, we can re-order the rows (or columns) of the Hadamard matrix $H$ according to their sequencies.

The conversion of a given sequency $s$ into the corresponding index number $k$ in Hadamard order is a three-step process:

1. represent $s$ in binary form:
   
   $$s=(s_{n-1}s_{n-2}\cdots s_1s_0)_2=\sum_{i=0}^{n-1} s_i2^i$$
   
   

2. convert this binary form to Gray code:
   
   $$g_i=s_i \oplus s_{i+1}\;\;\;\;(i=0,\cdots,n-1)$$
   
   
   where $\oplus$ represents exclusive or and $s_n=0$ by definition.

3. bit-reverse $g_i$'s to get $k_i$'s:
   
   $$k_i=g_{n-1-i}=s_{n-1-i} \oplus s_{n-i}$$
   
   

Now $k$ can be found as

$$k=(k_{n-1} k_{n-2}\cdots k_1 k_0)_2 =\sum_{i=0}^{n-1} s_{n... ... s_{n-i} 2^i =\sum_{j=0}^{n-1} s_j \oplus s_{j+1} 2^{n-1-j}$$

where $j=n-1-i$ or equivalently $i=n-1-j$.

For example, $n=log_2 N=log_2 8 = 3$, we have

$$\begin{tabular}{ccccccccc} s & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 ... ...101 & 001 \\ k & 0 & 4 & 6 & 2 & 3 & 7 & 5 & 1 \end{tabular}$$

Now the sequency-ordered or Walsh-ordered Walsh-Hadamard matrix can be obtained as

$${\bf W}=\frac{1}{\sqrt{8}}\left[ \begin{array}{rrrrrrrr} 1 &... ...& 6 3 & 2 \\ 4 & 3 5 & 7 6 & 5 7 & 1 \end{array}$$

The first column on the right of the matrix is for the sequency $s$ of the corresponding row, which is the index for the sequency-ordered matrix, and the second column is the index $k$ of the Hadamard ordered. We see that this matrix is still symmetric:

$$w[k,m]=w[m,k]$$