DFT(Discrete Fourier Transform)

Fourier Transform is $X(\omega)=\Sigma_{n=-\infty}^{\infty}x(n)e^{-j\omega n}$
Since $x(n)$ is discrete-time signal, $X(\omega)$ is periodic with period $2\pi$.
If we take N samples in the $2\pi$ frequency domain, the component frequency $X(\frac{2\pi}{N}k)$
$X(\frac{2\pi}{N}k)=\Sigma_{n=-\infty}^{\infty}x(n)e^{-j2\pi kn/N}=\Sigma_{n=0}^{N-1}x_p e^{-j2\pi kn/N}$, $x_p(n)=\Sigma_{l=-\infty}^{\infty}x(n-lN)$ is a periodic repeatition of $x(n)$ every N samples.
If $x_p(n)$ is expanded in a Fourier Series as
$x_p(n)=\Sigma_{k=0}^{N-1}c_k e^{j2\pi kn/N}$, $c_k=\frac{1}{N}\Sigma_{n=0}^{N-1}x_p(n)e^{-j2\pi kn/N}=\frac{1}{N}X(\frac{2\pi}{N}k)$
Therefor, $x_p(n)=\frac{1}{N}\Sigma_{k=0}^{N-1}X(\frac{2\pi}{N}k)e^{j2\pi kn/N}$.

When $x(n)$ has a finite duration of length $L \leq N$, $x_p(n)$ is simply a periodic repeatition of $x(n)$.

$u_k = f(u_k) = \Sigma_{n=0}^{N-1}c_ne^{inx_k} = \frac{1}{N}\Sigma_{n=0}^{N-1}U_n e^{inx_k}$
$U_n = Nc_n = \Sigma_{n=0}^{N-1}f_ke^{-inx_k}$

• Aperiodic continuous-time signal

It is possible to express the spectrum $X(\omega)$ directly in terms of its samples $X(2 \pi k/N)$, k=0,1,…,N-1.
Interpolation function $X(\omega) = \Sigma_{k=0}^{N-1} X(\frac{2\pi}{N}k) P(\omega-\frac{2\pi}{N}k)$, $N \ge L$
$P(\omega) = \frac{sin(\omega N/2)}{N sin(\omega/2)} e^{-j \omega (N-1)/2}$

$P(\frac{2\pi}{N}k)$ = 1 for k=0 and =0 for k=1,2,…,N-1
Consequently, the inteerpolation formula gives exactly the sample values $X(2\pi k/N)$ for $\omega = 2\pi k/N$

• vector notation

$U = [U_0 \cdots U_{N-1}] = F_N u$ where $u = {[u_0\cdots u_{N-1}]}^T, F_N = [e_{nk}] = [e^{-inx_k}]=[e^{-2\pi ink/N}]=[w^{nk}]$,$w=w_N=e^{-2\pi i/N}$
$u = F_N^{-1}U$ where $F_N^{-1} = \frac{1}{N}\bar{F}_N, \bar{F}_N = \frac{1}{N}[\bar{w}^{nk}]$

• Use DFT to approach $c_n$ of Complex Fourier Series

$c_n \simeq \frac{1}{N}U_n$

• Use DFT to approach Complex Fourier Transform

$\hat{f}(w) \simeq \frac{2\pi L}{N}\Sigma_{j=0}^{N-1}f(\frac{2\pi jL}{N})e^{-2\pi ijk/N}$

page revision: 18, last edited: 25 Apr 2016 05:56