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

$$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}}$$

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.,

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

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

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

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

We also define $l_i=m_{n-1-i}$. Now the $WHT_w$ can be written as

$$X[k] = \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}}$$

$$= \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

$$X[k] = \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] ]$$

$$= \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

$$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]$$ (11)

Expanding the 2nd summation into two terms, we get

$$X[k] = \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] ]$$

$$= \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

$$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]$$ (12)

Finally, expanding the 1st summation into two terms, we have

$$X[k]=x_2[4k_2+2k_1]+(-1)^{k_0+k_1}x_2[4k_2+2k_1+1]$$ (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: