Walsh-Hadamard Transform

This paper is going to practice the simulation like Fourier series by Walsh-Hadamard transform.
Walsh-Hadamard has 2 power's number of data for the input like Fast Fourier transform, and is a transform
by rectangle orthogonal bases. Here, let's experience the transform as itself.

Source Signal Selection

Constant Peak
2 Peaks 3 Peaks
Trapezoid Ramp
Random

Execute Walsh-Hadamard Transform


DC(0th)
1st 2nd
3rd 4th

Composite Spectrums

0

Explanation

This program executes 8 points' Walsh-Hadamard transform. To compare with Fourier transform, the orthogonal
bases are categorized to frequency components. For the frequencies from a fundamental to 3 times, the
orthogonal bases(shown by red and green) are given as sin wave and cos wave. Although Fourier transform
can represents the phase by 2 orthogonal bases, Walsh-Hadamard can be also considered in the same way.
In another of the highest order(4th), the orthogonal basis becomes one, but, this is only a formal
categorization. Essentially, 8 orthogonal bases satisfy orthogonal conditions each other, and they
sometimes become forms to complement each other between bases.
Now, 8 points' Hadamard matrix is (1).

\(\large{ H_8= \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & 1 & -1 & -1 & -1 & -1 & 1 & 1 \\ 1 & 1 & -1 & -1 & 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ 1 & -1 & 1 & -1 & -1 & 1 & -1 & 1 \\ 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1 \\ \end{bmatrix} } \qquad (1)\)

The element \(H_n\left(r, c\right)\) of \(n~n\)Hadamard matrix is calculated by (2).

\(\large{H_n\left(r, c\right)=\left(-1\right)^{d\left(r, c\right)}} \qquad (2)\)
\(\large{r, c}\): Row, Column's index order

\(\large{d\left(r, c\right)= \displaystyle \sum_{k=0}^{p-1} b\left(k, r\right)f\left(k, c\right)}\) \(\large{\left(p=\log_{2} n\right)}\)
\(\large{f\left(k, c\right)= \begin{eqnarray} \left\{ \begin{array}{l} b\left(p-1, c\right) \qquad \qquad \qquad \qquad \qquad (k=0) \\ b\left(p-k, c\right) + b\left(p-k-1, c\right) \qquad (0 \lt k \lt p) \\ \end{array} \right. \end{eqnarray} }\)

\(\large{b\left(j, i\right)= \left(i \gg j \right) \& 1}\)
\(\large{i \gg j}\): Apply logical right-shift to \(i\) with \(j\) times \(\large{\&}\): Bitwise AND

Put source signal's data series as \(Y\), the calculation of spectrum series \(S\) becomes (3).

\(\large{S=\frac{1}{n}H_n Y} \qquad (3)\)

\(\large{ Y= \begin{bmatrix} y\left(0\right) \\ y\left(1\right) \\ y\left(2\right) \\ \vdots \\ y\left(n-1\right) \\ \end{bmatrix} }\) \(\large{ S= \begin{bmatrix} DC(0th) \\ 1st[sin] \\ 1st[cos] \\ \vdots \\ n/2-1th[sin] \\ n/2-1th[cos] \\ n/2th \\ \end{bmatrix} }\)

Here, consider \(\frac{1}{n} H_n\) as a transform, \(H_n\) as an inverse transform. To be \(\frac{1}{n} H_n\) as the transform, the
compositions can work as the source signal intensity. In addition, to exchange the transform for the
inverse transform is no problem, if the source signal returns to original intensity by the transform\(\Rightarrow \)
the inverse transform. In another, \(\frac{1}{\sqrt n} H_n\) can be OK for both the transform and the inverse transform.
From the above, multiplications of calculating \(H_n Y\) is unnecessary. To be able to be only addition and
subtraction, the calculation of spectrums will be accelerated.