Aliasing and the idea of the FFT

When you sample too slowly

If the Shannon condition is not met, a frequency too high for the sampling rate does not disappear: it masquerades as a lower frequency. This is aliasing. A high note can thus reappear, after digitization, as a low note that never existed.

Sampling a fast sinusoid too slowly:

true signal (fast)   :  /\  /\  /\  /\  /\      (high frequency)
sampled points       :  *      *      *        (too far apart)
reconstructed signal :  *------*------*         (a fake slow sinusoid!)

(the same sampled points also fit a lower frequency: the true frequency is "folded")

It is the same effect that makes car wheels seem to turn backward in movies: the camera samples the fast motion of the wheel too slowly.

The remedy

An anti-aliasing filter is placed before the sampler, cutting off all frequencies above Fe/2. That way, no frequency can fold over anymore, and the digitized signal remains faithful.

Computing the spectrum: the FFT

To analyze a sampled signal, we compute its discrete Fourier transform (on the samples). Done naively, this computation costs on the order of N² operations for N samples — quickly prohibitive. The FFT (Fast Fourier Transform) is a clever "divide and conquer" algorithm that brings this cost down to about N log N.

cost of computing the spectrum for N samples:

direct method   :  N^2         (e.g. N = 1,000,000 -> 10^12 operations)
FFT             :  N log N      (e.g. N = 1,000,000 -> ~2 x 10^7 operations)

(the FFT is tens of thousands of times faster for large N)

It is this efficiency that makes frequency analysis practical in real time, in your phone as well as in a mixing console.

Classic pitfall

Increasing the sampling frequency after the fact never recovers information that has already been aliased: once two frequencies have been merged during digitization, no subsequent processing can separate them. The anti-aliasing filter must act BEFORE sampling, never after.