\documentstyle[12pt]{article}
\usepackage{html}
\evensidemargin -0.9in
\oddsidemargin -0.9in
\textwidth 7.5in
\topmargin -0.2in
\begin{document}
\textheight 9.2in
\begin{center}
{\LARGE \bf Fourier Analysis}
\end{center}
%{\large
\section*{Continuous Fourier Transform}
\begin{itemize}
\item {\bf Definitions}
The Fourier transform pair in the most general form for a continuous and
aperiodic time signal $x(t)$ is (Eqs. 4.8, 4.9):
\[ X(j\omega)=\int_{-\infty}^{\infty} x(t) e^{-j\omega t} dt,\;\;\;\;\;\;\;
x(t)=\frac{1}{2\pi}\int_{-\infty}^{\infty} X(j\omega) e^{ j\omega t} d\omega \]
Replacing $\omega$ by $2\pi f$ in the above, we get the alternative
representation:
\[ X(f)=\int_{-\infty}^{\infty} x(t) e^{-j2\pi f t} dt,\;\;\;\;\;\;\;
x(t)=\int_{-\infty}^{\infty} X(f) e^{ j2\pi f t} df \]
Note we changed the notation $H(j\omega)$ in Eqs. 4.8 and 4.9 to $X(f)$ to
better illustrate the duality of Fourier transform in both time and frequency
domains. In this representation of Fourier transform the forward and inverse
transforms are in perfect symmetry with only a different sign for the exponent
due to the duality property of the transform (Section 4.3.6). This alternative
representation of Fourier transform will be used in the following discussion
as it is often more convenient.
\item {\bf Physical Meaning of Fourier Transform}
The complex spectrum $X(f)$ of a time signal $x(t)$ can be written in polar
form
\[ X(f)=X_r(f)+jX_i(f)=|X(f)|e^{j\angle{X(f)}} \]
and the inverse transform becomes:
\[ x(t)=\int_{-\infty}^{\infty} |X(f)| e^{j\angle{X(f)}}\;e^{j2\pi ft}\; df
=\int_{-\infty}^{\infty} |X(f)| e^{j(2\pi ft+\angle{X(f)})}\; df \]
which is a weighted linear combination (integration) of infinite sinusoids
with
\begin{itemize}
\item $\mbox{{\bf frequency: }} f$
\item $\mbox{{\bf amplitude: }}|X(f)|=\sqrt{X_r(f)^2+X_i(f)}$
\item $\mbox{{\bf phase: }}\angle{X(f)}=tan^{-1}(X_i(f)/X_r(f))$
\end{itemize}
\item {\bf Spectrum of Real Signal}
Fourier transform is a complex transform. But a physical signal
Fourier transform is a complex transform. But any physical signal
(temperature, voltage, pressure, etc.) $x(t)$ is always real
\[ x(t)=x_r(t)+jx_i(t)=x^*(t)=x_r(t)-jx_i(t),\;\;\;i.e., \;\;\;x_i(t)=0 \]
and its spectrum $X(f)$ is conjugate symmetric (Eq. 4.30):
\[ X(f)=X^*(-f),\;\;\;i.e.,\;\;\;X_r(f)+jX_i(f)=X_r(-f)-jX_i(-f) \]
i.e., the real part of $X(f)$ is even symmetric $X_r(f)=X_r(-f)$, and the
imaginary part odd $X_i(-f)=-X_i(-f)$.
\end{itemize}
\section*{Discrete Fourier Transform}
In practice, the expression $x(t)$ of the signal is not available, so the signal
has to be digitized (truncated and sampled) and then analyzed {\em numerically}
by a digital computer.
\begin{itemize}
\item {\bf Truncation}
As computer can only process finite amount of data, a signal $x(t)$ of
infinite duration $-\infty < t < \infty$ must be truncated, i.e., it is assumed
to be periodic $x(t)=x(t+T)$ with a finite period $T<\infty$. (We cannot assume
the signal is 0 outside the time range T, as that would still be an infinite
signal. Repeated signals carry no information while zero signals still do.)
The Fourier transform of this periodic signal $x_T(t)$ now becomes
{\bf Fourier series expansion} (Eq. 3.38):
\[ x_T(t)=\sum_{n=-\infty}^\infty X[n] e^{jn\omega_0 t}
=\sum_{n=-\infty}^\infty X[n] e^{j2n\pi f_0 t} \]
with coefficient $X[n]$ ($a_k$ in Eq. 3.39, which is changed to $X[k]$ in
Problem 5.54):
\[ X[n]=\frac{1}{T}\int_0^T x_T(t) e^{-jn\omega_0t} dt=\frac{1}{T}\int_0^T
x_T(t) e^{-jn2\pi f_0t} dt,\;\;\;\;\;(n=0, \pm 1, \pm 2, \cdots) \]
The spectrum of this periodic signal becomes discrete
\[ X(f)=\sum_{n=-\infty}^\infty X[n] \delta(f-nf_0) \]
where $f_0=1/T$ is the interval between two consecutive frequency components.
In particular, when $T\rightarrow \infty$, $f_0=1/T \rightarrow 0$, the discrete
spectrum $X(f)$ becomes continuous.
\htmladdimg{../truncation.gif}
\item {\bf Heisenberg's Uncertainty Principle}
Sometimes it is desirable to study the frequency characteristics of a signal
$x(t)$ over a short duration $T$. However, the time window $T$ and
the frequency resolution $f_0=1/T$ (the gap between two consecutive frequency
components available) are inversely related, i.e., it is impossible to
increase both the temporal resolution (small $T$) and frequency resolution
(small $f_0$). When one of the resolutions is improved, the other must suffer.
This relationship is similar to {\em Heisenberg's Uncertainty Principle} in
quantum physics which states that it is impossible to exactly measure both
the position and the momentum of a particle at the same time. The more precisely
one of the quantities is determined, the less precisely the other is known.
To better address this issue of time and frequency resolution, {\em Wavelet
transform} can be used.
\item {\bf Sampling}
As computer can only process discrete values, the continuous signal $x(t)$
must be sampled:
\[ x(t)=x(t) \cdot comb(t) = x(t) \cdot \sum_{m=-\infty}^\infty \delta(t-mt_0)
=\sum_{m=-\infty}^\infty x[m] \delta(t-mt_0) \]
where $x[m]=x(mt_0)$ is the mth sample, $t_0$ is the interval between two
consecutive samples $x[m]$ and $x[m+1]$, and $F=1/t_0$ is the sampling rate.
The number of samples in each period $T$ is assumed to be $N=T/t_0$. As the
signal is now discrete (as well as periodic), its spectrum becomes periodic
(as well as discrete) with period $F=1/t_0$. Note that the number of
coefficients in frequency domain is also $N$:
\[ F/f_0=\frac{1/t_0}{1/T}=T/t_0=N \]
This relation indicates that the representation of a signal in either time or
frequency domain has the same number of independent variables, or same degrees
of freedom. Moreover, the Parseval's theorem further indicates that the
representations in both domains contain the same amount of energy.
The nth Fourier coefficient is:
\[
X[n]=\frac{1}{T}\sum_{m=0}^{N-1} x[m] e^{-jn2\pi f_0mt_0},\;\;\;\;(n=0,1,\cdots,N-1)
\]
and the mth signal sample can be expressed as (Eq. 5.19):
\[
x[m]=\frac{1}{F}\sum_{n=0}^{N-1} X[n] e^{j2n\pi f_0 mt_0},\;\;\;\;(m=0,1,\cdots,N-1)
\]
As $t_0f_0=1/FT=1/N$, the above can be rewritten as (Eqs. P5.53-2, P5.54-2):
\[ X[n]=\frac{1}{N}\sum_{m=0}^{N-1} x[m] e^{-j2\pi mn/N},\;\;\;\;(n=0,1,\cdots,N-1) \]
\[ x[m]=\sum_{m=0}^{N-1} X[n] e^{ j2\pi mn/N},\;\;\;\;(m=0,1,\cdots,N-1) \]
This is the discrete Fourier transform (DFT), with both the time signal and its
spectrum discrete and finite, and the only form of Fourier transform that can be
implemented by a digital computer.
\htmladdimg{../sampled_truncation.gif}
%Note that there are $N$ samples (independent variables) in the representation of
%the signal in either time or frequency domain, i.e., the degrees of freedom of
%the signal (representing the amount of information) are conserved. Moreover,
%according to Parseval's relation, the amount of energy contained in the signal
%is also conserved in both time and frequency domains.
\end{itemize}
Alternatively, the truncation and sampling of the discretization process can be
carried out in a different order, sampling first followed by truncation.
\begin{itemize}
\item {\bf Sampling}
The signal becomes discrete after sampling with rate $F=1/t_0$:
\[ x(t)=x(t) \cdot comb(t0= x(t) \cdot \sum_{m=-\infty}^\infty \delta(t-mt_0)
=\sum_{m=-\infty}^\infty x[m] \delta(t-mt_0) \]
and its spectrum $X_F(f)$ become periodic (of period $F$):
\[ X_F(f)=\sum_{m=-\infty}^\infty x[m]e^{-j2\pi f mt_0} \]
and the mth signal sample can be written as:
\[
x[m]=\frac{1}{F}\int_F X_F(f) e^{j2\pi f mt_0} df,\;\;\;(m=0,\pm 1,\pm 2,\cdots)
\]
In particular, if we assume $F=1/t_0=1$, and replace $f$ by $\omega/2\pi$,
the above become the same as Eqs. 5.8 and 5.9:
\[ X(e^{j\omega})=\sum_{m=-\infty}^\infty x[m]e^{-j\omega m},\;\;\;\;
x[m]=\frac{1}{2\pi}\int_{2\pi} X(e^{j\omega}) e^{j\omega m} d\omega
\]
Note on alternative notations:
\begin{itemize}
\item The periodic spectrum $H(e^{j\omega})$ of a discrete signal in Eqs.
5.8 and 5.9 is changed to $X_F(f)$ to better illustrate the duality
of Fourier transform in both time and frequency domains.
\item The above notations of Fourier transform of discrete signals take
the sampling rate $F$ and period $t_0$ into consideration, while
Eqs. 5.8 and 5.9 as a special case ($t_0=F=1$) do not. That is why
they are modified to include sampling rate/period in section 7.4.
\end{itemize}
\htmladdimg{../sampling.gif}
\item {\bf Truncation:}
The sampled signal is then truncated by a time window $T$ and becomes periodic
with $T/t_0=N$ time samples in a period $T$. The spectrum become discrete (with
gap $f_0=1/T$) as well as periodic (with period $F$). There are also
$F/f_0=T/t_0=N$ coefficients in a period $F$:
\[ X(f)=\sum_{n=0}^{N-1} X[n] \delta(f-nf_0) \]
where $X[n]$ is the nth coefficient:
\[
X[n]=\frac{1}{T}\sum_{m=0}^{N-1} x[m] e^{-jn2\pi f_0mt_0},\;\;\;\;(n=0,1,\cdots,N-1)
\]
and the mth signal sample can be written as:
\[
x[m]=\frac{1}{F}\sum_{n=0}^{N-1} X[n] e^{j2n\pi f_0 mt_0},\;\;\;\;(m=0,1,\cdots,N-1)
\]
This is the same discrete Fourier transform as obtained above.
\htmladdimg{../truncated_sampling.gif}
\end{itemize}
\section*{Four Forms of Fourier Transform}
Depending on whether a signal $x(t)$ is periodic and discrete, its Fourier
transform will take one of the four forms:
\begin{itemize}
\item {\bf I. Aperiodic, continuous time signal $x(t)$,
continuous, aperiodic spectrum $X(f)$}
This is the most general form of Fourier transform:
\[ X(f)=\int_{-\infty}^{\infty} x(t) e^{-j2\pi ft} dt,\;\;\;\;
x(t)=\int_{-\infty}^{\infty} X(f) e^{j2\pi ft} df \]
\item {\bf II. Aperiodic, discrete time signal $x(n)$, continuous, periodic
spectrum $X_F (f)$}
The discrete time signal can be considered as a sequence of samples
of a continuous signal. The time interval between two consecutive
samples $x[m]$ and $x[m+1]$ is $t_0=1/F$, where $F$ is the sampling
rate, which is also the period of the spectrum in the frequency domain.
The discrete time signal can be written as
\[ x(t)=\sum_{m=-\infty}^{\infty} x[m]\delta(t-mt_0) \]
and its transform is:
\[ X_F(f)=\sum_{m=-\infty}^{\infty} x[m]e^{-j2\pi fmt_0},\;\;\;\;
x[m]=\frac{1}{F} \int_0^F X_F(f) e^{j2\pi fmt_0} df,
\;\;\;(m=0,\pm 1,\pm 2, \cdots) \]
\item {\bf III. Periodic, continuous time signal $x_T(t)$, discrete, aperiodic
spectrum $X[n]$}
This is the Fourier series expansion of periodic signals. The time
period is $T$, and the interval between two consecutive frequency components
is $f_0=1/T$, and its transform is:
\[ X[n]=\frac{1}{T} \int_0^T x_T(t) e^{-j2\pi nf_0t} dt,\;\;\;\;
x_T(t)=\sum_{n=-\infty}^{\infty} X[n]e^{j2\pi nf_0t},
\;\;\;(n=0, \pm 1, \pm 2, \cdots) \]
The discrete spectrum can also be represented as:
\[ X(f)=\sum_{n=--\infty}^{\infty} X[n]\delta(f-nf_0) \]
\item {\bf IV. Periodic, discrete time signal $x[m]$, discrete, periodic spectrum
$X[n]$}
\[ X[n]=\frac{1}{T}\sum_{m=0}^{N-1} x[m]e^{-j2\pi nmf_0t_0},\;\;\;
x[m]=\frac{1}{F}\sum_{n=0}^{N-1} X[n]e^{j2\pi nmf_0t_0},\;\;\;(m,n=0,1,\cdots,N-1) \]
where $N=T/t_0=F/f_0$ is the number of samples in each period in both temporal and
frequency domains. Since $t_0f_0=1/FT=1/N$, the above can be rewritten as:
\[ X[n]=\frac{1}{N}\sum_{m=0}^{N-1} x[m] e^{-j2\pi mn/N},\;\;\;\;
x[m]=\sum_{m=0}^{N-1} X[n] e^{ j2\pi mn/N},\;\;\;\;(m,n=0,1,\cdots,N-1) \]
The coefficients for forward and inverse transforms can be either $1/N$ and 1,
or $1/\sqrt{N}$ for both of them to make the transform pair perfectly symmetric.
These scaling factors are not essential in practice.
\end{itemize}
{\bf Four forms of Fourier transform} (Table 5.3):
\[ \begin{tabular}{c||c|c} \hline
& {\bf Signal $x(t)$} & {\bf Spectrum $X(f)$} \\ \hline \hline
I & {\bf Continuous, aperiodic} & {\bf Aperiodic, continuous} \\
& $ x(t)=\int_{-\infty}^\infty X(f)e^{ j2\pi ft}df $ &
$ X(f)=\int_{-\infty}^\infty x(t)e^{-j2\pi ft}dt $ \\ \hline
II & {\bf Discrete ($t_0$), aperiodic} & {\bf Periodic ($F=1/t_0$), continuous} \\
& $ x(t)=\sum_{m=-\infty}^\infty x[m]\delta(t-mt_0)$ & \\
& $ x[m]=\frac{1}{F}\int_F X_F(f)e^{j2\pi fmt_0}df $ &
$ X_F(f)=\sum_{m=-\infty}^\infty x[m]e^{-j2\pi fmt_0} $ \\ \hline
III & {\bf Continuous, periodic ($T$)} & {\bf Aperiodic, discrete ($f_0=1/T$)} \\
& $ x_T(t)=\sum_{n=-\infty}^\infty X[n]e^{j2\pi nf_0t} $ &
$ X[n]=\frac{1}{T}\int_T x_T(t)e^{-j2\pi nf_0t}dt $ \\
& & $X(f)=\sum_{n=-\infty}^\infty X[n]\delta(f-nf_0)$ \\ \hline
IV & {\bf Discrete ($t_0$), periodic ($T$)} & {\bf Periodic ($F=1/t_0$), discrete ($f_0=1/T$)} \\
& $ x_T[m]=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1} X[n]e^{j2\pi nm/N} $ &
$ X_F[n]=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1} x[m]e^{-j2\pi mn/N} $ \\
& $ x_T(t)=\sum_{m=0}^{N-1} x[m]\delta(t-mt_0)$ &
$X_F(f)=\sum_{n=0}^{N-1} X[n]\delta(f-nf_0)$ \\
& ($T/t_0=N$) & ($F/f_0=T/t_0=N$) \\ \hline
\end{tabular} \]
{\bf The Convolution theorem}
\[ \begin{tabular}{c||c|c} \hline
& Time domain & Frequency domain \\ \hline \hline
I & x(t)*y(t)=$\int_{-\infty}^\infty x(\tau)y(t-\tau)d\tau$ & $X(f)\cdot Y(f)$ \\
& $x(t)\cdot y(t)$ & $X(f)*Y(f)=\int_{-\infty}^\infty X(\phi)y(f-\phi)d\phi$ \\ \hline
II & $x_T(t)*y_T(f)=\frac{1}{T}\int_T x_T(\tau)y_T(t-\tau)d\tau$ & $X[n]\cdot Y[n]$ \\
& $x_T(t)\cdot y_T(t)$ & $X[n]*Y[n]=\sum_{k=-\infty}^\infty X[k]Y[n-k]$ \\ \hline
III & $x[m]*y[m]=\sum_{k=-\infty}^\infty x[k]y[m-k]$ & $X_F(f)\cdot Y_F(f)$ \\
& $x[m]\cdot y[m]$ & $X_F(f)*Y_F(f)=\frac{1}{F}\int_F X_F(\phi)Y_F(f-\phi)d\phi$ \\ \hline
IV & $x_T[m]*y_T[m]=\sum_{k=0}^{N-1} x[k]y[m-k]$ & $X_F[n]\cdot Y_F[n]$ \\
& $x[m]\cdot y[m]$ & $X_F[n]*Y_F[n]=\sum_{k=0}^{N-1} X_F[k]Y_F[n-k]$ \\ \hline
\end{tabular} \]
{\bf Parseval's formula}
\[ \begin{tabular}{c||c} \hline
I & $\int_{-\infty}^\infty | x(t) |^2 dt =\int_{-\infty}^\infty |X(f)|^2 df $ \\ \hline
II & $\frac{1}{T}\int_T |x_T(t)|^2 dt =\sum_{n=-\infty}^\infty | X[n] |^2$ \\ \hline
III & $\sum_{m=-\infty}^\infty | x[m] |^2 =\frac{1}{F}\int_F | X_F(f) |^2 df$ \\ \hline
IV & $\frac{1}{T}\sum_{m=0}^{N-1} | x_T[m] |^2 =\frac{1}{F}\sum_{n=0}^{N-1} | X_F[n] |^2$ \\ \hline
\end{tabular} \]
%\begin{itemize}
%\item I
%\[\int_{-\infty}^\infty | x(t) |^2 dt =\int_{-\infty}^\infty |X(f)|^2 df \]
%\item II
%\[ \frac{1}{T}\int_T |x_T(t)|^2 dt =\sum_{n=-\infty}^\infty | X[n] |^2 \]
%\item III
%\[ \sum_{m=-\infty}^\infty | x[m] |^2 =\frac{1}{F}\int_F | X_F(f) |^2 df \]
%\item IV
%\[ \frac{1}{T}\sum_{m=0}^{N-1} | x_T[m] |^2 =\frac{1}{F}\sum_{n=0}^{N-1} | X_F[n] |^2 \]
%\end{itemize}
\section*{Numerical Implementation of DFT}
\begin{itemize}
\item {\bf Vector Form of DFT}
Consider an N by N matrix ${\bf W}$ with its (m,n)th element defined as:
\[ w[m,n] \stackrel{\triangle}{=} W_N^{mn}=(e^{-j2\pi /N})^{mn}=e^{-j2\pi mn/N}
=w[n,m],\;\;\;(m,n=0,1,\cdots,N-1) \]
where
\[ W_N \stackrel{\triangle}{=} \frac{1}{\sqrt{N}}e^{-j2\pi/N} \]
Now the DFT can be written as (Eq. P5.54-2):
\[ X[n]=\frac{1}{\sqrt{N}}\sum_{m=0}^{N-1} x[m] e^{-j2\pi mn/N}
=\sum_{m=0}^{N-1} W_N^{mn} x[m]
=\sum_{m=0}^{N-1} w[m,n]x[m] \;\;\;\;(n=0,1,\cdots,N-1) \]
or in tabular form:
\[ \left[ \begin{array}{c}X[0]\\X[1]\\ \cdots \\X[N-1] \end{array} \right]
=\left[ \begin{array}{cccc}
w[0,0] & w[0,1] & \cdots & w[0,N-1]\\
w[1,0] & w[1,1] & \cdots & w[1,N-1]\\
\cdots & \cdots & \cdots & \cdots \\
w[N-1,0]& w[N-1,1] & \cdots & w[N-1,N-1] \end{array} \right]
\left[ \begin{array}{c}x[0]\\x[1]\\ \cdots \\x[N-1] \end{array} \right]
\]
or in matrix form:
\[ {\bf X}={\bf W} {\bf x} \]
where ${\bf x}$ and ${\bf X}$ are N by 1 column (vertical) vectors representing the
signal in time and frequency domain, respectively. Similarly, the inverse transform
DFT can be written as
\[ x[m]=\frac{1}{\sqrt{N}}\sum_{n=0}^{N-1} X[n] e^{j2\pi mn/N}
=\sum_{n=0}^{N-1} w^*[m,n]x[m] \;\;\;\;(m=0,1,\cdots,N-1) \]
or in matrix form:
\[ {\bf x}={\bf W}^* {\bf X} \]
where ${\bf W}^*$ is the complex conjugate of ${\bf W}$. Left multiplying
${\bf W}$ on both sides, we get
\[ {\bf W}{\bf x}={\bf W} {\bf W}^* {\bf X}={\bf X} \]
i.e., ${\bf W} {\bf W}^*={\bf I}$, or ${\bf W}^{-1}={\bf W^*}$. Also note
that ${\bf W}^T={\bf W}$ is symmetric.
In general, any matrix ${\bf A}$ satisfying ${\bf A}^{-1}={\bf A}^{*T}$ is
called a {\em unitary matrix}. In particular, if a real unitary matrix
${\bf A}={\bf A}^*$ satisfying ${\bf A}^{-1}={\bf A}^T$ is called an
{\em orthogonal matrix}. Any such unitary or orthogonal matrix ${\bf A}$
can be used to define a unitary or orthogonal transform:
\[ {\bf X}={\bf A} {\bf x} \]
\item {\bf Fast Fourier Transform}
The number of operations (multiplications and additions) needed for computing
each of the $N$ frequency components $X[n],\;(n=0,1,\cdots,N-1)$ is proportional
to $N$, i.e., the {\em computational complexity} of an N-point DFT is $O(N^2)$.
However, there exists a fast algorithm due to the properties of the DFT matrix
${\bf W}$. Specifically, based on the following three properties of
$W_N=e^{-j2\pi/N}$:
\begin{enumerate}
\item $ W_N^{kN}=e^{-j2kN\pi/N}=e^{-j2k\pi} \equiv 1$
\item $ W_{2N}^{2k}=e^{-j2k2\pi/2N}=e^{-jk2\pi/N} \equiv w_N^k$
\item $ W_{2N}^{N} =e^{-j2N\pi/2N}=e^{-j\pi} \equiv -1 $
\end{enumerate}
a {\em Fast Fourier Transform (FFT)} of complexity $O(N\;log_2 N)$ can be
derived (refer to problem 5.54 of OWN or \htmladdnormallink{this page}
{../../../e161/lectures/fourier/node7.html} for details). It is this major
improvement of computational complexity that makes Fourier transform
practically possible in many applications.
\item {\bf Example 1}
Consider a discrete signal of $N=8$ real values (imaginary components are 0):
%\begin{eqnarray}
%{\bf x} &=& [x[0],x[1],x[2],x[3],x[4],x[5],x[6],x[7]]^T \nonumber \\
% &=&[(0,0), (0,0), (2,0), (3,0), (4,0), (0,0), (0,0), (0,0)]^T
% \nonumber
%\end{eqnarray}
\[ {\bf x} =\left[
\begin{array}{c} x[0] \\ x[1] \\ x[2] \\ x[3] \\ x[4] \\ x[5] \\ x[6] \\ x[7]
\end{array} \right] =\left[\begin{tabular}{c}
(0,0) \\ (0,0) \\ (2,0) \\ (3,0) \\ (4,0) \\ (0,0) \\ (0,0) \\ (0,0)
\end{tabular} \right] \]
The forward discrete Fourier transform is:
\begin{eqnarray}
X[n] &=& X_r[n]+jX_i[n]=\sum_{m=0}^{N-1} x[m] e^{-j2\pi m n/N} \nonumber \\
&=& \sum_{m=0}^{N-1} (x_r[m]+jx_i[m]) (cos(2\pi m n/N)-j\;sin(2\pi mn/N)) \nonumber
\end{eqnarray}
or
\[ \left\{ \begin{array}{l}
X_r[n]=\sum_{m=0}^{N-1} x_r[m]cos(2\pi mn/N)+x_i[m]sin(2\pi m n/N) \\
X_i[n]=\sum_{m=0}^{N-1} x_i[m]cos(2\pi mn/N)-x_r[m]sin(2\pi m n/N)
\end{array} \right. \]
The inverse transform is:
\[ x[m]=x_r[m]+jx_i[m]=\frac{1}{N}\sum_{n=0}^{N-1} X[n] e^{j2\pi m n/N} \]
or
\[ \left\{ \begin{array}{l}
x_r[m]=\sum_{n=0}^{N-1} X_r[n]cos(2\pi mn/N)-X_i[n]sin(2\pi m n/N) \\
x_i[m]=\sum_{n=0}^{N-1} X_i[n]cos(2\pi mn/N)+X_r[n]sin(2\pi m n/N)
\end{array} \right. \]
To represent this transform in matrix forms ${\bf X}={\bf W} {\bf x}$, we find
\[ w[m,n]=e^{-j2\pi mn/N}=cos(2\pi mn/N)-j\;sin(2\pi mn/N)
=cos(\pi mn/4)-j\;sin(\pi mn/4) \]
and get
\begin{eqnarray}
& & {\bf X}={\bf W} {\bf x} = \nonumber \\
& &\left[ \begin{tabular}{rrrrrrrr}
(1.0,0.0) & (1.0,0.0) & (1.0,0.0) & (1.0,0.0) & (1.0,0.0) & (1.0,0.0) & (1.0,0.0) & (1.0,0.0) \\
(1.0,0.0) & (0.7,-0.7) & (0.0,-1.0)& (-0.7,-0.7)& (-1.0,0.0)& (-0.7,0.7)& (0.0,1.0) & (0.7,0.7) \\
(1.0,0.0) & (0.0,-1.0) & (-1.0,0.0)& (0.0,1.0) & (1.0,0.0) & (0.0,-1.0)& (-1.0,0.0) & (-0.0,1.0) \\
(1.0,0.0) & (-0.7,-0.7)& (0.0,1.0) & (0.7,-0.7) & (-1.0,0.0)& (0.7,0.7) & (0.0,-1.0) & (-0.7,0.7) \\
(1.0,0.0) & (-1.0,0.0) & (1.0,0.0) & (-1.0,0.0) & (1.0,0.0) & (-1.0,0.0)& (1.0,0.0) & (-1.0,0.0) \\
(1.0,0.0) & (-0.7,0.7) & (0.0,-1.0)& (0.7,0.7) & (-1.0,0.0)& (0.7,-0.7)& (0.0,1.0) & (-0.7,-0.7) \\
(1.0,0.0) & (0.0, 1.0) & (-1.0,0.0)& (0.0,-1.0) & (1.0,0.0) & (0.0,1.0) & (-1.0,0.0) & (-0.0,-1.0) \\
(1.0,0.0) & (0.7, 0.7) & (0.0,1.0) & (-0.7,0.7) & (-1.0,0.0)& (-0.7,-0.7)& (0.0,-1.0) & (0.7,-0.7) \\
\end{tabular} \right]
\left[ \begin{tabular}{c}
(0,0) \\ (0,0) \\ (2,0) \\ (3,0) \\ (4,0) \\ (0,0) \\ (0,0) \\ (0,0)
\end{tabular} \right] \nonumber \\
& & =\left[ \begin{tabular}{r}
(9.0,0.0) \\ (-6.1,-4.1) \\ (2.0,3.0) \\ (-1.9,-0.1) \\ (3.0,0.0) \\ (-1.9,0.1) \\ (2.0,-3.0) \\ (-6.1,4.1) \end{tabular} \right]
\nonumber
\end{eqnarray}
Note that the above matrix multiplication is a complex operation, and the product
of two complex numbers is defined as
\[ (a+jb)\;(c+jd)=(ac-bd)+j(ad+bc) \]
\htmladdimg{../dft1d_demo.gif}
\item {\bf Example 2}
Consider a discrete signal of N=60 samples:
\[ x[m]=4+2*cos(2\pi f_1 m)+3*sin(2\pi f_2 m),\;\;\;\;(m=0,1,\cdots,N-1) \]
The two sinusoids have frequencies $f_1=22/N$ and $f_2=6/N$ representing,
respectively, 22 and 6 cycles per period of $N=60$ points.
\htmladdimg{../dft1d_demo1t.gif}
By DFT, the spectrum of the signal can be found as shown below.
\htmladdimg{../dft1d_demo1f.gif}
In particular, $X_r[0]=4$ is the DC component, and the two real peaks
$X_r[22]=1$ and $X_r[38]=X_r[-22]=1$ represent the cosine function
\[ 2\;cos(2\pi f_1 m)=2[\frac{1}{2}(e^{j2\pi f_1m}+e^{-j2\pi f_1m})]
=X_r[22]e^{j2\pi 22/N}+X_r[-22]e^{-j2\pi 22/N} \]
and the two imaginary peaks $X_i[6]=-1.5$ and $X_i[54]=X_i[-6]=1.5$ represent the
sine function
\[ 3\;sin(2\pi f_2 m)=3[\frac{1}{2j}(e^{j2\pi f_2m}-e^{-j2\pi f_2m})]
=j\; [X_i[6]e^{j2\pi 6/N}-X_i[-6]e^{-j2\pi 6/N} ] \]
In general, the spectrum $X[n]$ of a real signal $x[m]$ has the following properties:
\begin{itemize}
\item $X_r[0]$ is the average or DC component of the signal:
\[ X_r[0]=Re\{X[0]\}=\frac{1}{N} \sum_{m=0}^{N-1}x[m] cos(2\pi m 0/N)
=\frac{1}{N}\sum_{m=0}^{N-1} x[m] \]
\item $X_r[N/2]$ is the difference between the even components and odd components:
\[ Re\{X[N/2]\}=\frac{1}{N} \sum_{m=0}^{N-1}x[m] cos(2\pi m N/2N)=
\frac{1}{N} \sum_{m=0}^{N-1}x[m] (-1)^m \]
\item $X_i[0]$ and $X_i[N/2]$ are always zero:
\[ X_i[0]=Im\{X[0]\}=-\frac{1}{N} \sum_{m=0}^{N-1} x[m] sin(2\pi m 0/N)=0 \]
\[ X_i[N/2]=Im\{X[N/2]\}=-\frac{1}{N} \sum_{m=0}^{N-1}x[m] sin(2\pi m N/2N)=0 \]
\item For $0 < n