Discrete Fourier transform

Contents

1   Derivation

The discrete Fourier transform is derived from the Fourier series. The Fourier series is expressed as $$f(t)=\sum_{n=-\infty}^\infty A_ne^{2i\pi nt/T} \label{eq:fourier_series}$$ where $$A_n=\frac{1}{T}\int_0^T f(t)e^{-2i\pi nt/T}\,dt. \label{eq:A_n}$$

If $0\leq n,t\leq N-1$ and $T=N$, we can rewrite Eqs. \eqref{eq:fourier_series} and \eqref{eq:A_n} in a discrete form as $$f(t)=\sum_{n=0}^{N-1}F(n)e^{2i\pi nt/N} \label{eq:synthesis}$$ and $$F(n)=\frac{1}{N}\sum_{t=0}^{N-1}f(t)e^{-2i\pi nt/N}. \label{eq:analysis}$$

2   Proof of identity

Plugging Eq. \eqref{eq:analysis} into Eq. \eqref{eq:synthesis} and using Euler’s formula yields $$\begin{split} f(t)&=\sum_{n=0}^{N-1}\frac{1}{N}\sum_{u=0}^{N-1}f(u)e^{-2i\pi nu/T}e^{2i\pi nt/N}\\ &=\frac{1}{N}\sum_{u=0}^{N-1}f(u)\sum_{n=0}^{N-1}e^{2i\pi(t-u)n/N}\\ &=\frac{1}{N}\sum_{u=0}^{N-1}f(u)\sum_{n=0}^{N-1}\left[\cos\left(2\pi(t-u)n/N\right)+i\sin\left(2\pi(t-u)n/N\right)\right]. \end{split} \label{eq:proof}$$ Consider $$\sum_{n=0}^{N-1}\left[\cos\left(2\pi(t-u)n/N\right)+i\sin\left(2\pi(t-u)n/N\right)\right]. \label{eq:sum_cos_sin}$$ For $u=t$, Eq. \eqref{eq:sum_cos_sin} becomes $N$ because $\cos\left(2\pi(t-u)n/N\right)+i\sin\left(2\pi(t-u)n/N\right)=\cos 0+i\sin 0=1$. For $u\neq t$, both cosine and sine terms complete $t-u$ cycles over $0\leq n\leq N-1$, which makes Eq. \eqref{eq:sum_cos_sin} 0. That is $$\sum_{n=0}^{N-1}\left[\cos\left(2\pi(t-u)n/N\right)+i\sin\left(2\pi(t-u)n/N\right)\right]=N\delta_{t,u} \label{eq:sum_cos_sin_2}$$ where $\delta_{t,u}$ is the Kronecker delta ($\delta_{t,u}=0$ for $t\neq u$ and $\delta_{t,u}=1$ for $t=u$).

Plugging Eq. \eqref{eq:sum_cos_sin_2} into Eq. \eqref{eq:proof} yields $$\begin{split} f(t)&=\frac{1}{N}\sum_{u=0}^{N-1}f(u)N\delta_{t,u}\\ &=\sum_{u=0}^{N-1}f(u)\delta_{t,u}\\ &=f(t) \end{split} \label{eq:proof_2}$$ because $\delta_{t,u}=1$ only once when $u=t$ and $0$ otherwise.