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

## Windowing

\(x[n]\) is treated as

*cyclic*: it is assumed that the length of \(x\) is exactly the period of the signalIf 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 betterPowers 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*, etcDifference 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