The development of the DFT

If we have a signal, such as following:

How do we put it into computer? We can use A/D converter and a low pass filter to sample the signal with wanted instead of from t = -\infty to \infty:

But then we have to make it periodic, so we convolve it with impulse function with NT apart to have impulse function in both time and frequency domain:

From the equations of final signal in both time and frequency domain, we can see that in the computer we have x(n) and in the frequency domain:

$\sum _{n=0}^{N-1}x(nT)\,e^{-j2\pi \,fnT}\,\cdot \,{\frac {1}{NT}}\sum _{m=-\infty }^{\infty }\delta \left(f-{\frac {n}{NT}}\right)=\sum _{m=-\infty }^{\infty }{\frac {1}{NT}}\sum _{n=0}^{N-1}x(nT)\,e^{-j2\pi {\frac {m}{NT}}nT}\delta \left(f-{\frac {n}{NT}}\right)$

Then the areas of the impulse functions is:

$\sum _{n=0}^{N-1}x(n)\,e^{-j2\pi {\frac {nm}{N}}}$

Which is the definition of the $DFT(x(n))$.

Property of the DFT

• DFT is periodic.

Proof:

$X(m+N)=\sum _{n=0}^{N-1}x(n)\,e^{-j2\pi {\frac {n(m+N)}{N}}}=\sum _{n=0}^{N-1}x(n)\,e^{-j2\pi {\frac {nm}{N}}}e^{-j2\pi {\frac {nN}{N}}}=\sum _{n=0}^{N-1}x(n)\,e^{-j2\pi {\frac {nm}{N}}}=X(m)$

Inverse DFT

Let's try to get back x(l) if we have X(m)

$X(m)=\sum _{n=0}^{N-1}x(n)\,e^{-j2\pi {\frac {nm}{N}}}$

Let's try do some trick to this DFT, let's sum it up and with exponents tag along.

$\sum _{m=0}^{N-1}X(m)\,e^{j2\pi {\frac {lm}{N}}}=\sum _{m=0}^{N-1}\sum _{n=0}^{N-1}x(n)\,e^{-j2\pi {\frac {nm}{N}}}e^{j2\pi {\frac {lm}{N}}}=\sum _{n=0}^{N-1}x(n)\sum _{m=0}^{N-1}e^{j2\pi {\frac {(l-n)m}{N}}}$

Note: $\sum _{m=0}^{N-1}e^{j2\pi {\frac {(l-n)m}{N}}}$ will be N if $l=n$.

Let $e^{j2\pi {\frac {(l-n)m}{N}}}=r^{m}$ then $r=e^{j2\pi {\frac {(l-n)}{N}}}$

So we know the sum of $r^{m}=S=1+r+r^{2}+r^{3}+...+r^{N-1}$

Therefore, we can divide r at both side of equation and get ${\frac {S-1}{r}}=S-r^{N-1},S({\frac {1}{r}}-1)={\frac {1}{r}}-r^{N-1},S={\frac {1-r^{N}}{1-r}}$

Think about this, if $l\neq \,n,r=e^{j2\pi {\frac {(l-n)}{N}}},S={\frac {1-e^{j2\pi (l-n)}}{1-e^{j2\pi {\frac {(l-n)}{N}}}}}=0$, since $e^{j2\pi (l-n)}=1$ for any integer of l and n.

So $\sum _{m=0}^{N-1}X(m)\,e^{j2\pi {\frac {lm}{N}}}=\sum _{n=0}^{N-1}x(n)N\delta _{n,l}=Nx(l)$

$x(l)={\frac {1}{N}}\sum _{m=0}^{N-1}X(m)\,e^{j2\pi {\frac {lm}{N}}}\equiv \,IDFT(X(n))$

Key points to note:

• By doing the DFT, we make the signal periodic in both time domain and frequency domain.

$X(m+N)=X(m),\,\,x(n+N)=x(n)$

• $X(m)\,\,for\,\,\,m>{\frac {N}{2}}$ corresponds to $X(m-N)$

Approximation of Fourier integral

We can kind of see the DFT as an approximation to the Fourier integral.

$X(m)=\sum _{n=0}^{N-1}x(n)\,e^{-j2\pi {\frac {nm}{N}}}={\frac {1}{T}}\sum _{n=-{\frac {N}{2}}}^{N-1-{\frac {N}{2}}}x(n)\,e^{-j2\pi \,nT{\frac {m}{NT}}}T\cong {\frac {1}{T}}\int _{-{\frac {NT}{2}}}^{\frac {NT}{2}}\,x(t)e^{-j2\pi \,tf}\,dt$