next up previous [pdf]

Next: The Nyquist frequency Up: FOURIER TRANSFORM Previous: FOURIER TRANSFORM

FT as an invertible matrix

A Fourier sum may be written

\begin{displaymath}
B(\omega) \quad =\quad \sum_t \ b_t \ e^{i\omega t}
\quad =\quad \sum_t \ b_t \ Z^t
\end{displaymath} (6)

where the complex value $Z$ is related to the real frequency $\omega$ by $Z=e^{i\omega}$. This Fourier sum is a way of building a continuous function of $\omega$ from discrete signal values $b_t$ in the time domain. Here we specify both time and frequency domains by a set of points. Begin with an example of a signal that is nonzero at four successive instants, $( b_0, b_1, b_2, b_3)$. The transform is
\begin{displaymath}
B(\omega) \quad =\quad b_0 + b_1 Z + b_2 Z^2 + b_3 Z^3
\end{displaymath} (7)

The evaluation of this polynomial can be organized as a matrix times a vector, such as
\begin{displaymath}
\left[ \begin{array}{c}
B_0 \\
B_1 \\
B_2 \\
B_3 \en...
...array}{c}
b_0 \\
b_1 \\
b_2 \\
b_3 \end{array} \right]
\end{displaymath} (8)

Observe that the top row of the matrix evaluates the polynomial at $Z=1$, a point where also $\omega=0$. The second row evaluates $B_1=B(Z=W=e^{i\omega_0})$, where $\omega_0$ is some base frequency. The third row evaluates the Fourier transform for $2\omega_0$, and the bottom row for $3\omega_0$. The matrix could have more than four rows for more frequencies and more columns for more time points. I have made the matrix square in order to show you next how we can find the inverse matrix. The size of the matrix in (8) is $N=4$. If we choose the base frequency $\omega_0$ and hence $W$ correctly, the inverse matrix will be
\begin{displaymath}
\left[ \begin{array}{c}
b_0 \\
b_1 \\
b_2 \\
b_3 \en...
...array}{c}
B_0 \\
B_1 \\
B_2 \\
B_3 \end{array} \right]
\end{displaymath} (9)

Multiplying the matrix of (9) with that of (8), we first see that the diagonals are +1 as desired. To have the off diagonals vanish, we need various sums, such as $1+W +W^2+W^3$ and $1+W^2+W^4+W^6$, to vanish. Every element ($W^6$, for example, or $1/W^9$) is a unit vector in the complex plane. In order for the sums of the unit vectors to vanish, we must ensure that the vectors pull symmetrically away from the origin. A uniform distribution of directions meets this requirement. In other words, $W$ should be the $N$-th root of unity, i.e.,
\begin{displaymath}
W \quad =\quad
\sqrt[N]{1} \quad =\quad
e^{2\pi i/N}
\end{displaymath} (10)

The lowest frequency is zero, corresponding to the top row of (8). The next-to-the-lowest frequency we find by setting $W$ in (10) to $Z=e^{i\omega_0}$. So $\omega_0=2\pi /N$; and for (9) to be inverse to (8), the frequencies required are

\begin{displaymath}
\omega_k \quad =\quad { (0, 1, 2, \ldots , N- 1) \, 2\pi \over N}
\end{displaymath} (11)


next up previous [pdf]

Next: The Nyquist frequency Up: FOURIER TRANSFORM Previous: FOURIER TRANSFORM

2013-01-06