The Discrete Fourier Transform

The Discrete-Time Fourier Transform

• Let's "get rid of" the infinities by just taking limits

  $$ \hat{f}(\omega) = \lim_{W \rightarrow \infty} \int_{-W}^{W} f(t) e^{-i \omega t} dt $$

  A very long signal relative to its period should be well-approximated

• Now a fiddly argument ensues. If the signal is periodic, we should be able to replace the limits by the period: after all, it doesn't change anything

  $$ \hat{f}(\omega) = \int_{0}^{P} f(t) e^{-i \omega t} dt $$

• Let's turn the integral into a sum by treating \(f(t)\) as a series of impulses: nonzero only at discrete timesteps

  $$ X[k] = \sum_{n=0}^{N-1} x[n] e^{-i k n / N} $$

• The frequency-domain value at unit frequency k, namely \(X[k]\) has been written as a weighted sum of the discrete time-domain values \(x[i]\) over the period \(N\)

• The inverse transformation works similarly

  $$ x[n] = \frac{1}{2 \pi N} \sum_{k=0}^{N-1} X[k] e^{i k n / N} $$

Notes On The DFT

• The \(X\)s are still complex (!)

• The inverse is computed only as the sum of discrete frequencies

• Be careful about the amplitude. The bin amplitudes grow like \(N\): there's different conventions about where to put the \(1/N\) to scale them back. I am following Wikipedia here, and putting the scaling in the inverse transform.

• This math is so full of fiddly that it is really easy to get it screwed up

• Frequency resolution is a function of sampled period

  The sampling rate is handled here by unit frequency. Frequency needs to be scaled by the sample rate to be meaningful: if you do a 1024-point DFT of a signal sampled at 1024 × 48 samples per second, each bin of the DFT result represents about 24Hz of signal

• Windowing is a thing: next lecture. In brief, because the signal is treated as cyclic, truncating the signal so that the left and right ends don't match up (at all frequencies!) is… bad