Applying the DFT

The Discrete Fourier Transform

  • A discrete frequency-domain representation for a discrete time-domain PCM signal

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


  • \(x[n]\) is treated as cyclic: it is assumed that the length of \(x\) is exactly the period of the signal

  • If you have a cycle-and-a-half of a sine, it's going to look like there's a sharp edge in it

  • To fix this, we taper off the signal toward the ends of the DFT by multiplying it by a window function. For example, a "sine window" applies as

    $$ sin(\pi n / N) x[n] $$

  • Sadly, this also acts as a low-pass filter. There are various tradeoffs between filtering and smoothing. It's something of a black art, and mostly beyond this course

Goertzel Filters

  • The DFT can be thought of as a Gaussian Filter bank like this

  • The transform as given is \(O(N^2)\), because we do \(O(N)\) work to compute each bin

  • But we can compute for just some of the bins if we like: even one. Just fix \(k\)

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

  • This is the so-called "Goertzel filter". I've used these a lot as a narrow bandpass filter

The Fast Fourier Transform

  • A dynamic programming trick gets the time complexity of the DFT down to \(O(N \lg N)\)

  • No, I'm not going to explain it here: treat it as a black box

  • The FFT gives exactly the same answers as the DFT, just faster

  • Limitation: The FFT requires a power-of-two number of samples

    • OK, there are fancy FFTs that work by prime factoring the number of samples. Many small factors are better

    • Powers of two have many small factors

  • Limitation: The output frequencies must be distributed linearly, which may not be what you wished for

The Discrete Cosine Transform

  • Usually you don't care about phase information

  • The DCT gives you something similar to the FFT, but only magnitudes

  • Still can be done \(O(N lg N)\)

  • The DCT has a different set of boundary conditions

  • DCTs are used a lot in compression and processing, for example in MPEG

Spectra of Common Signals

  • Triangle, square: Fundamental plus "odd harmonics"

    • Harmonic is a multiple of the fundamental. So odd harmonics of f appear at 3f, 5f, etc

    • Difference between triangle and square is decay rate, phase

    • Odd harmonics are a characteristic of many kinds of distortion

    • "Total Harmonic Distortion" measures this by inputting a sine wave and seeing what harmonics come out

  • "White noise" (random samples): Flattish noise spectrum ("noise is a sum of random frequencies")

Frequency Localization In Time

  • Fundamentally ill-defined: FT only works right on an infinite periodic signal, throws away all information about changes in frequency

  • Heisenbergy: Smaller DFT gives more local information about frequency, but at the cost of poorer accuracy. Low frequency signals, in particular, will not be captured

  • "Overlapping" heuristic: Do a DFT, slide over a few samples, do it again

  • Overlapping won't save you from abrupt changes: compare with windowing

DFT Application: Frequency Analysis

  • Pretty straightforward: do the DFT, look for peaks etc in the spectrum

  • Still have to do the analysis of the spectrum, which involves some kind of other math or heuristics

  • There are more sensitive frequency analysis methods that do not involve the DFT

DFT Application: Filtering

  • Pretty straightforward: do the DFT, adjust frequencies as desired, do the inverse DFT

  • See localization in time: will end up doing "overlapping windowed" DFT to track changes input frequencies

  • Expensive compared to "direct" filtering, which we will discuss next time

DFT Application: Lossy Compression

  • Do DFTs, remove "unwanted" stuff

  • Depends pretty hard on psychoacoustics

  • We will talk more about audio compression later in the course

Last modified: Wednesday, 8 April 2020, 3:14 AM