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

Hadamard Matrix

The Kronecker product of two matrices ${\bf A}=[a_{ij}]_{m\times n}$ and ${\bf B}=[b_{ij}]_{k\times l}$ is defined as

\begin{displaymath}{\bf A} \otimes {\bf B} \stackrel{\triangle}{=}\left[ \begin{...
...B} & \cdots & a_{mn}{\bf B} \end{array} \right]_{mk \times nl} \end{displaymath}

In general, ${\bf A}\otimes {\bf B} \neq {\bf B}\otimes {\bf A}$.

The Hadamard Matrix is defined recursively as below:


\begin{displaymath}{\bf H}_1 \stackrel{\triangle}{=} \frac{1}{\sqrt{2}} \left[
\begin{array}{rr} 1 & 1  1 & -1 \end{array} \right] \end{displaymath}


\begin{displaymath}
{\bf H}_n={\bf H}_1\otimes{\bf H}_{n-1}=\frac{1}{\sqrt{2}}\...
...}_{n-1}  {\bf H}_{n-1} & -{\bf H}_{n-1} \end{array} \right]
\end{displaymath}

Obviously ${\bf H}^T={\bf H}$ is rean and symmetric. Here are two examples for $n=2$ and $n=3$:

\begin{displaymath}{\bf H}_2={\bf H}_1 \otimes {\bf H}_1=\frac{1}{\sqrt{2}}\left...
...
1 & 1 & -1 & -1  1 & -1 & -1 & 1 \\
\end{array} \right]
\end{displaymath}


\begin{displaymath}{\bf H}_3={\bf H}_1 \otimes {\bf H}_2=\frac{1}{\sqrt{2}}\left...
... 3  3 & 4 \\
4 & 1  5 & 6  6 & 2  7 & 5
\end{array} \end{displaymath}

Note that ${\bf H}_n$ is $N=2^n$ by $N=2^n$ matrix.

The first column on the right of the matrix ${\bf H}_3$ is for the indecies of the $N=8$ rows, and the second column represents the sequency (the number of zero-crossings or sign changes) in each row. Sequency is similar to but different from frequency in the sense that it measures the rate of change of non-periodical signals.

The rows of the matrix can be considered as the $N=2^3$ samples of the following waveforms:

wht_waveform_0.gif

The Hadamard matrix can also be obtained by defining its element in the kth row and mth column of $H$ as

\begin{displaymath}h[k,m]=(-1)^{\sum_{i=0}^{n-1}k_im_i}
=\prod_{i=0}^{n-1} (-1)^{k_im_i}=h[m,k] \;\;\;\;\;
(k,m=0,1,\cdots,N-1)\end{displaymath}

where

\begin{displaymath}k=\sum_{i=0}^{n-1}k_i2^i=(k_{n-1}k_{n-2}\cdots k_1k_0)_2
\;\;\;\;(k_i=0,1) \end{displaymath}


\begin{displaymath}m=\sum_{i=0}^{n-1}m_i2^i=(m_{n-1}m_{n-2}\cdots m_1m_0)_2
\;\;\;\;(m_i=0,1) \end{displaymath}

i.e., $(k_{n-1}k_{n-2}\cdots k_1k_0)_2$ and $(m_{n-1}m_{n-2}\cdots m_1m_0)_2$ are the binary representations of $k$ and $m$, respectively. Obviously, $n=log_2 N$.

We can show the Hadamard matrix ${\bf H}$ is orthogonal by induction. First, it is obvious that ${\bf H}_1$ is orthogonal:

\begin{displaymath}
{\bf H}_1^T{\bf H}_1={\bf H}_1{\bf H}_1
=\frac{1}{2}\left[...
...egin{array}{rr}1&0 0&1\end{array}\right]={\bf I}_{2\times 2}
\end{displaymath}

Next we assume ${\bf H}_{n-1}$ is orthogonal, i.e.,

\begin{displaymath}
{\bf H}^T_{n-1}{\bf H}_{n-1}={\bf H}_{n-1}{\bf H}_{n-1}={\bf I}_{2^{n-1}\times 2^{n-1}}
\end{displaymath}

Finally we show that ${\bf H}_n={\bf H}_1\otimes{\bf H}_{n-1}$ is also orthogonal:
$\displaystyle {\bf H}_n^T{\bf H}_n={\bf H}_n{\bf H}_n$ $\textstyle =$ $\displaystyle \frac{1}{2}\left[ \begin{array}{rr}
{\bf H}_{n-1} & {\bf H}_{n-...
...f H}_{n-1} & {\bf H}_{n-1}   {\bf H}_{n-1}&-{\bf H}_{n-1} \end{array} \right]$  
  $\textstyle =$ $\displaystyle \frac{1}{2}\left[\begin{array}{rr}{\bf H}_{n-1}{\bf H}_{n-1}+{\bf...
...\bf H}_{n-1}+{\bf H}_{n-1}{\bf H}_{n-1}\end{array}\right]
={\bf I}_{N\times N}$  

In summary, the Hadamard matrix ${\bf H}$ is real, symmetric, and orthogonal:

\begin{displaymath}{\bf H}={\bf H}^*={\bf H}^T={\bf H}^{-1} \end{displaymath}


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