## 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}$$

## Windowing

• $$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