The development of the DFT

If we have a signal, such as following:

Error creating thumbnail: File missing

How do we put it into computer?

We can use A/D converter and a low pass filter to sample the signal that is wanted instead of from $t=-\mathrm{\infty }to\mathrm{\infty }$:

Error creating thumbnail: File missing

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:

Error creating thumbnail: File missing

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=-\mathrm{\infty }}^{\mathrm{\infty }}\delta (f-\frac{n}{NT})=\sum _{m=-\mathrm{\infty }}^{\mathrm{\infty }}\frac{1}{NT}\sum _{n=0}^{N-1}x(nT)e^{-j2\pi \frac{m}{NT}nT}\delta (f-\frac{n}{NT})$

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\ne 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(m))$

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)form>\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}\underset{-\frac{NT}{2}}{\overset{\frac{NT}{2}}{\int }}x(t)e^{-j2\pi tf}dt$