DFT - Discrete Fourier Transform

page = 461

We can implement this in a fast way using the FFT- Fast Fourier Transform

THIS IS DIFFERENT THAN DTFT - Discrete Time Fourier Transform

DTFT - Discrete Time Fourier Transform

DTFT is a way of looking at the signal in the frequency domain. The formula is given by $X(\omega )={\sum }_{n=-\infty }^{\infty }x[n]e^{-j\omega n}$

Link to original

This is not a convenient representation because our $n$ starts at $n=-\infty$. We want to implement this on a computer.

1. We reduce the limit from $\infty \to N-1$
2. We start at $n=0$
3. $\omega$ is continuous, but a computer needs discrete values.

We can therefore write the DFT as

$$X({\omega }_k)=\sum _{n=0}^{N-1}x[n]e^{-j{\omega }_{k}n}$$

where $w_k=\frac{2\pi k}{N}$, and $k=0,1,\dots ,N-1$

Frequency-domain sampling

DTFT $X(\omega ){|}_{w_k}$

$$X\left(\frac{2\pi k}{N}\right)=\sum _{n=0}^{N-1}{x}_p[n]e^{-j2\pi kn/N}$$

Where $x_p[n]={\sum }_{l=-\infty }^{\infty }x[n-lN]$, and $k=0,1,\dots ,N-1$

We need to have $N$ large enough that we don’t experience Time Domain Aliasing.

Shifting of DFT signals

Read the book (?) Something about a circle or smth