next up previous
Next: A Simple Example Up: wht Previous: Sequency Ordered Walsh-Hadamard Matrix

Fast Walsh-Hadamard Transform (Sequency Ordered)

The sequency-ordered Walsh-Hadamard transform ($WHT_w$, also called Walsh ordered $WHT$) can be obtained by first carrying out the fast $WHT_h$ and then reordering the components of ${\bf X}$ as shown above. Alternatively, we can use the following fast $WHT_w$ directly with better efficiency.

The sequency ordered WHT of $x[m]$ can also be defined as

\begin{displaymath}X[k]=\sum_{m=0}^{N-1} w[k,m] x[m]
=\sum_{m=0}^{N-1} x[m] \prod_{i=0}^{n-1} (-1)^{(k_i+k_{i+1})m_{n-1-i}}
\end{displaymath}

where $N=2^n$, $k_n\stackrel{\triangle}{=}0$, and the exponent of $-1$ represents the conversion from sequency ordering to Hadamard ordering (binary-to-Gray code conversion and bit-reversal conversion).

In the following, we assume $n=3,\;\;N=2^3=8$, and we represent $m$ and $k$ in binary form as, respectively, $(m_2 m_1 m_0)_2$ and $(k_2k_1k_0)_2$, i.e.,

\begin{displaymath}m=\sum_{i=0}^{n-1}m_i 2^i=4m_2+2m_1+m_0 \;\;\;\;\;\; (m_i=0,1) \end{displaymath}


\begin{displaymath}k=\sum_{i=0}^{n-1}k_i 2^i=4k_2+2k_1+k_0 \;\;\;\;\;\; (k_i=0,1) \end{displaymath}

As the first step of the algorithm, we rearrange the order of the samples $x[m]$ by bit-reversal to get

\begin{displaymath}x_0[4m_0+2m_1+m_2] \stackrel{\triangle}{=} x[4m_2+2m_1+m_0]
\;\;\;\;\;\;m=0,1, \cdots 7
\end{displaymath}

We also define $l_i=m_{n-1-i}$. Now the $WHT_w$ can be written as
$\displaystyle X[k]$ $\textstyle =$ $\displaystyle \sum_{m_2=0}^1 \sum_{m_1=0}^1 \sum_{m_0=0}^1 x_0[4m_0+2m_1+m_2]
\prod_{i=0}^2 (-1)^{(k_i+k_{i+1}) m_{n-1-i}}$  
  $\textstyle =$ $\displaystyle \sum_{l_0=0}^1 \sum_{l_1=0}^1 \sum_{l_2=0}^1 x_0[4l_2+2l_1+l_0]
\prod_{i=0}^2 (-1)^{(k_i+k_{i+1})l_i}$  

Expanding the 3rd summation into two terms, we get
$\displaystyle X[k]$ $\textstyle =$ $\displaystyle \sum_{l_0=0}^1 \sum_{l_1=0}^1
\prod_{i=0}^1 (-1)^{(k_i+k_{i+1})l_i}
[ x_0[2l_1+l_0)+(-1)^{k_2+k_3} x_0[4+2l_1+l_0] ]$  
  $\textstyle =$ $\displaystyle \sum_{l_0=0}^1 \sum_{l_1=0}^1 \prod_{i=0}^1
(-1)^{(k_i+k_{i+1})l_i} x_1[4k_2+2l_1+l_0]$  

where $k_3 \stackrel{\triangle}{=} 0$ and $x_1$ is defined as
\begin{displaymath}
x_1[4k_2+2l_1+l_0] \stackrel{\triangle}{=}
x_0[2l_1+l_0]+(-1)^{k_2+k_3} x_0[4+2l_1+l_0]
\end{displaymath} (11)

Expanding the 2nd summation into two terms, we get
$\displaystyle X[k]$ $\textstyle =$ $\displaystyle \sum_{l_0=0}^1 (-1)^{(k_i+k_{i+1})l_0}
[ x_1[4k_2+l_0]+(-1)^{k_1+k_2} x_1[4k_2+2+l_0] ]$  
  $\textstyle =$ $\displaystyle \sum_{l_0=0}^1 (-1)^{(k_i+k_{i+1})l_0}
x_2[4k_2+2k_1+m_0]$  

where $x_2$ is defined as
\begin{displaymath}
x_2[4k_2+2k_1+l_0] \stackrel{\triangle}{=}
x_1[4k_2+l_0]+(-1)^{k_1+k_2} x_1[4k_2+2+l_0]
\end{displaymath} (12)

Finally, expanding the 1st summation into two terms, we have
\begin{displaymath}
X[k]=x_2[4k_2+2k_1]+(-1)^{k_0+k_1}x_2[4k_2+2k_1+1]
\end{displaymath} (13)

Summarizing the above steps, we get the fast $WHT_w$ algorithm composed of the bit-reversal and the three equations (11), (12), and (13), as illustrated below:

wht_1.gif


next up previous
Next: A Simple Example Up: wht Previous: Sequency Ordered Walsh-Hadamard Matrix
Ruye Wang 2013-10-22