next up previous
Next: Fast Walsh-Hadamard Transform (Sequency Up: wht Previous: The Walsh-Hadamard Transform (Hadamard

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:

    \begin{displaymath}s=(s_{n-1}s_{n-2}\cdots s_1s_0)_2=\sum_{i=0}^{n-1} s_i2^i \end{displaymath}

  2. convert this binary form to Gray code:

    \begin{displaymath}g_i=s_i \oplus s_{i+1}\;\;\;\;(i=0,\cdots,n-1) \end{displaymath}

    where $\oplus$ represents exclusive or and $s_n=0$ by definition.

  3. bit-reverse $g_i$'s to get $k_i$'s:

    \begin{displaymath}k_i=g_{n-1-i}=s_{n-1-i} \oplus s_{n-i} \end{displaymath}

Now $k$ can be found as

\begin{displaymath}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}
\end{displaymath}

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

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

\begin{displaymath}\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}\end{displaymath}

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

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

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:

\begin{displaymath}w[k,m]=w[m,k] \end{displaymath}

wht_waveform_1.gif


next up previous
Next: Fast Walsh-Hadamard Transform (Sequency Up: wht Previous: The Walsh-Hadamard Transform (Hadamard
Ruye Wang 2013-10-22