Skip to content
LumenaryAcademy
Signals 70 min

Sampling and the FFT

How a continuous signal becomes a list of numbers without losing anything, what goes wrong when it does, and the algorithm that made digital spectrum analysis practical.

Code tested · 6AI-draftedAwaiting review by an electrical engineer

Your guides: Chloe · The Physicist, Margaret · The Bench Engineer, Gideon · The Design Reviewer

MotivationH

From waves to numbers

Almost every signal you meet today passes through a computer: the voice in a phone call, the music on a streaming service, the current in an electric car's motor, the echo in a medical ultrasound scanner. Each began as a continuous voltage, and each was turned into a list of numbers by an analogue-to-digital converter (ADC) that measures the voltage at regular instants (sampling) and rounds each measurement to one of a finite set of levels (quantisation).

Both steps throw something away, and an engineer has to know exactly what. Sampling discards everything that happens between the instants, yet, astonishingly, for the right signals and a fast enough rate it loses nothing at all. Quantisation adds a small error to every sample, which behaves like a noise whose size depends on the number of bits. And once the signal is a list of numbers, the Fourier analysis of the previous lesson becomes a computation, the discrete Fourier transform, which a clever algorithm, the fast Fourier transform (FFT), performs thousands of times faster than its definition suggests.

This lesson takes each step in turn, with numbers you can check: where a 7 kHz tone lands when sampled at 10 kHz, how many bits buy how many decibels, how to write an FFT in a dozen lines, and why a spectrum analyser sometimes shows peaks that are not there and hides ones that are.

DefinitionsH

Sampling and the Nyquist–Shannon theorem

Sampling a continuous signal x(t)x(t) every TT seconds produces the sequence x[n]=x(nT)x[n] = x(nT). The sampling rate is fs=1/Tf_s = 1/T samples per second. Can we get x(t)x(t) back from the samples? Not for every signal: between samples anything could happen. But for signals that do not wiggle too fast, yes.

Theorem— The Nyquist–Shannon sampling theorem

Suppose x(t)x(t) is band-limited: its Fourier transform is zero for ∣f∣≥B|f| \ge B. If it is sampled at a rate fs>2Bf_s > 2B, then x(t)x(t) is exactly determined by its samples, and x(t)=∑n=−∞∞x[n] sinc ⁣(t−nTT),sinc(u)=sin⁡πuπu.x(t) = \sum_{n=-\infty}^{\infty} x[n]\, \mathrm{sinc}\!\left(\frac{t - nT}{T}\right), \qquad \mathrm{sinc}(u) = \frac{\sin \pi u}{\pi u}. The rate 2B2B is called the Nyquist rate, and half the sampling rate, fs/2f_s/2, the Nyquist frequency.

Proof

Represent the sampled signal by a train of impulses, xs(t)=∑nx(nT) δ(t−nT)=x(t)∑nδ(t−nT)x_s(t) = \sum_n x(nT)\,\delta(t - nT) = x(t)\sum_n \delta(t - nT). A periodic impulse train with period TT has a Fourier series whose coefficients are all 1/T1/T, so it equals 1T∑mej2πmfst\frac1T\sum_m e^{j2\pi m f_s t}. Multiplying x(t)x(t) by ej2πmfste^{j2\pi m f_s t} shifts its spectrum by mfsm f_s (the modulation property), so Xs(f)=1T∑m=−∞∞X(f−mfs).X_s(f) = \frac{1}{T}\sum_{m=-\infty}^{\infty} X(f - m f_s). The spectrum of the sampled signal is the original spectrum, repeated every fsf_s. If fs>2Bf_s > 2B, the copies centred at 0,±fs,±2fs,…0, \pm f_s, \pm 2f_s, \dots do not overlap, and an ideal low-pass filter with gain TT and cut-off fs/2f_s/2 keeps the central copy, which is X(f)X(f). That filter's impulse response is sinc(t/T)\mathrm{sinc}(t/T), and applying it to the impulse train places a sinc at each sample, which is the formula.

∎

0fs−fsfs/2fs > 2B: the copies do not touch, and a low-pass filter recovers the original0fs−fs2fs−2fsfs/2fs < 2B: the copies overlap around fs/2 and add (aliasing)
The spectrum of a sampled signal is the original spectrum repeated every fs. Top: with fs greater than twice the bandwidth B, the copies are separate and the original can be recovered. Bottom: with fs too low, the copies overlap near fs/2 and add together; no filter can separate them afterwards.
ComputationC

Aliasing, and the filter that prevents it

What happens if the signal does contain frequencies above fs/2f_s/2? Their spectral copies spill into the band from 00 to fs/2f_s/2, where they masquerade as lower frequencies. This is aliasing. A tone at frequency ff shows up at falias=∣f−mfs∣,m the integer nearest f/fs,f_{\text{alias}} = |f - m f_s|, \qquad m \text{ the integer nearest } f/f_s, a frequency between 0 and fs/2f_s/2. The program samples a 7 kHz sine at 10 kHz and compares the samples with those of a 3 kHz sine.

python
import numpy as np

fs = 10_000                      # samples per second
n = np.arange(8)
t = n / fs

high = np.sin(2 * np.pi * 7000 * t)     # a 7 kHz tone: above fs/2 = 5 kHz
low = -np.sin(2 * np.pi * 3000 * t)     # a 3 kHz tone, inverted
show = lambda v: np.round(v, 6) + 0.0   # + 0.0 prints -0.0 as 0.0
print("n      7 kHz sine    -(3 kHz sine)")
for k in n:
    print(f"{k}    {show(high[k]):+.6f}     {show(low[k]):+.6f}")
print("identical samples:", np.allclose(high, low))

def alias(f, fs):
    """The frequency in [0, fs/2] that a tone at f appears at after sampling at fs."""
    return abs(f - fs * round(f / fs))

print("\nsampling at 10 kHz: where each tone lands")
for f in (1000, 4000, 5000, 6000, 9000, 11_000, 23_500):
    print(f"{f:7} Hz  ->  {alias(f, fs):6.0f} Hz")

# How steep must the analogue anti-aliasing filter be?  A Butterworth low-pass of order N
# with its -3 dB point at fc attenuates a frequency f by 10*log10(1 + (f/fc)^(2N)) dB.
def butterworth_order(fc, f_stop, atten_db):
    return int(np.ceil(np.log10(10 ** (atten_db / 10) - 1) / (2 * np.log10(f_stop / fc))))

print("\nButterworth order for 96 dB of attenuation where aliases would land in 0-20 kHz:")
for fs_adc in (44_100, 48_000, 96_000, 64 * 44_100):
    f_stop = fs_adc - 20_000          # anything above this folds back into 0..20 kHz
    print(f"fs = {fs_adc / 1000:7.1f} kHz: stop band starts at {f_stop / 1000:7.1f} kHz,"
          f" order {butterworth_order(20_000, f_stop, 96)}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

The 7 kHz samples are identical to those of an inverted 3 kHz sine. Once the samples are taken, no computation can tell which tone was there: the information is gone. The second table shows the folding pattern. Frequencies reflect back and forth between 0 and fs/2f_s/2 like a ball between two walls: 6 kHz appears at 4 kHz, 9 kHz and 11 kHz both at 1 kHz.

7 kHz sine3 kHz sine, invertedsamples at 10 kHzt1 ms
Aliasing in time. Sampled 10,000 times a second, a 7 kHz sine (solid) and an inverted 3 kHz sine (dashed) pass through exactly the same points.

You have seen aliasing in films: a car's wheels appear to turn slowly backwards when their rotation rate is just below a multiple of the camera's frame rate. In engineering it is subtler and worse. Aliased noise and interference land on top of the wanted signal and cannot be filtered out afterwards, because they now occupy the same frequencies.

The anti-aliasing filter

The cure is to remove everything above fs/2f_s/2 before sampling, with an analogue low-pass anti-aliasing filter in front of the ADC. How steep must it be? The last table of the program answers this for audio. Suppose we want everything that could alias into the audible band (0 to 20 kHz) attenuated by 96 dB, the dynamic range of 16-bit audio. Sampling at 44.1 kHz, frequencies above 44.1−20=24.144.1 - 20 = 24.1 kHz fold into the audible band, so the filter must go from flat at 20 kHz to −96-96 dB at 24.1 kHz. A Butterworth filter would need order 60, impractical in analogue electronics. Sampling at 96 kHz relaxes the requirement to order 9.

The program's last line shows the modern solution. Oversampling converters sample far faster than needed (here 64 times 44.1 kHz), so that a gentle third-order analogue filter suffices; a digital filter then removes everything above 20 kHz and the rate is reduced (decimated) to the final value. Sharp filters are easy and cheap in digital form, as Digital filters shows, so modern converters move the hard work across the boundary into the digital domain.

Worked examplesH

Quantisation and the 6 dB per bit rule

An NN-bit ADC can output only 2N2^N different codes. If its input range is −V-V to +V+V, the codes are spaced by the step (or LSB, least significant bit) Δ=2V2N,\Delta = \frac{2V}{2^N}, and each sample is rounded to the nearest level, with an error between −Δ/2-\Delta/2 and +Δ/2+\Delta/2.

Theorem— Quantisation SNR of an ideal converter

If the quantisation error is uniformly distributed over [−Δ/2,Δ/2][-\Delta/2, \Delta/2] and uncorrelated with the signal, an ideal NN-bit converter digitising a full-scale sine wave achieves a signal-to-noise ratio of SNR=6.02 N+1.76 dB.\mathrm{SNR} = 6.02\,N + 1.76\ \text{dB}.

Proof

A random error uniform on [−Δ/2,Δ/2][-\Delta/2, \Delta/2] has mean zero and mean square 1Δ∫−Δ/2Δ/2e2 de=Δ2/12\frac{1}{\Delta}\int_{-\Delta/2}^{\Delta/2} e^2\,de = \Delta^2/12; this is the noise power. A full-scale sine has amplitude V=2N−1ΔV = 2^{N-1}\Delta and power V2/2=22NΔ2/8V^2/2 = 2^{2N}\Delta^2/8. So SNR=22NΔ2/8Δ2/12=32⋅22N,10log⁡10SNR=10log⁡101.5+N⋅20log⁡102=1.76+6.02 N dB.\mathrm{SNR} = \frac{2^{2N}\Delta^2/8}{\Delta^2/12} = \frac{3}{2}\cdot 2^{2N}, \qquad 10\log_{10}\mathrm{SNR} = 10\log_{10}1.5 + N\cdot 20\log_{10}2 = 1.76 + 6.02\,N\ \text{dB}.

∎

Each extra bit halves the step, which halves the error and so improves the SNR by 20log⁡102≈6.0220\log_{10} 2 \approx 6.02 dB. The program quantises a full-scale 997 Hz tone (a frequency deliberately unrelated to the sampling rate, so the errors do not repeat) and measures the SNR directly.

python
import numpy as np

def quantise(x, bits, full_scale=1.0):
    """Round x to the nearest of 2**bits equally spaced levels, step apart, filling -full_scale..+full_scale."""
    step = 2 * full_scale / 2 ** bits
    levels = np.floor(x / step) + 0.5                  # level centres at (k + 1/2) * step
    levels = np.clip(levels, -2 ** (bits - 1) + 0.5, 2 ** (bits - 1) - 0.5)
    return levels * step

fs, N = 48_000, 48_000                       # one second of samples
t = np.arange(N) / fs
f0 = 997.0                                   # a tone not locked to the sample rate

def snr_db(signal, bits):
    error = quantise(signal, bits) - signal
    return 10 * np.log10(np.mean(signal ** 2) / np.mean(error ** 2))

full = 0.9999 * np.sin(2 * np.pi * f0 * t)   # a full-scale sine
print("bits   measured SNR   6.02N + 1.76")
for bits in (4, 6, 8, 10, 12, 16):
    print(f"{bits:4}   {snr_db(full, bits):9.2f} dB   {6.02 * bits + 1.76:9.2f} dB")

quiet = 0.1 * full                           # the same tone, 20 dB below full scale
print(f"\n16 bits, tone at -20 dBFS: {snr_db(quiet, 16):.2f} dB")

err = quantise(full, 8) - full
step = 2 / 2 ** 8
print(f"\n8-bit error: mean {np.round(np.mean(err) / step, 4) + 0.0:+.4f} steps, RMS {np.sqrt(np.mean(err ** 2)) / step:.4f} steps"
      f" (uniform model: 0, 1/sqrt(12) = {1 / np.sqrt(12):.4f})")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

From 8 bits up, the formula is accurate to a tenth of a decibel; 16 bits give 98.1 dB, the figure usually quoted for CD audio. At 4 bits it overestimates by about half a decibel, because with so few levels the error is visibly correlated with the signal, so the "uniform random error" model is only approximate. Two practical lessons follow. First, the formula is for a full-scale signal: the same tone 20 dB quieter gets 78.1 dB, 20 dB less, so a converter's range should match the signal. Second, real converters fall short of the ideal because of thermal noise, clock jitter and nonlinearity; datasheets quote the measured SINAD (signal to noise and distortion) and the effective number of bits, ENOB=(SINAD−1.76)/6.02\mathrm{ENOB} = (\mathrm{SINAD} - 1.76)/6.02. A "16-bit" converter with an ENOB of 14 is common and honest.

When the signal is small or simple, the quantisation error can become a distorting pattern rather than a gentle hiss. Adding a small random dither signal before quantising breaks up the pattern, turning distortion into benign noise; audio mastering and many measurement systems do this deliberately.

DefinitionsH

The discrete Fourier transform

A computer holds NN samples, not a function on the whole real line. The discrete Fourier transform is the Fourier analysis of such a finite list.

Definition— Discrete Fourier transform (DFT)

The DFT of NN samples x[0],…,x[N−1]x[0], \dots, x[N-1] is the list of NN complex numbers X[k]=∑n=0N−1x[n] e−j2πkn/N,k=0,1,…,N−1,X[k] = \sum_{n=0}^{N-1} x[n]\, e^{-j2\pi kn/N}, \qquad k = 0, 1, \dots, N - 1, and the inverse DFT recovers the samples: x[n]=1N∑k=0N−1X[k] ej2πkn/Nx[n] = \frac{1}{N}\sum_{k=0}^{N-1} X[k]\, e^{j2\pi kn/N}.

Compare this with the Fourier series analysis formula of the previous lesson: the DFT is that formula with the integral over one period replaced by a sum over NN samples. That is exactly how to read it. The DFT treats the NN samples as one period of a periodic signal and finds its harmonics.

What frequency is bin kk? The harmonic ej2πkn/Ne^{j2\pi kn/N} completes kk cycles in NN samples, that is, in NTNT seconds. So bin kk corresponds to the frequency fk=kNT=k fsN,for k<N/2,f_k = \frac{k}{NT} = k\,\frac{f_s}{N}, \qquad \text{for } k < N/2, and bins above N/2N/2 represent the negative frequencies (k−N)fs/N(k - N)f_s/N, by the same folding as aliasing. The bin spacing fs/N=1/(NT)f_s/N = 1/(NT) is the reciprocal of the record length: one second of data gives bins 1 Hz apart, whatever the sampling rate. For a real signal, X[N−k]=X[k]‾X[N - k] = \overline{X[k]}, so only the first half of the bins carries information, which is why NumPy offers np.fft.rfft.

In matrix form the DFT is X=Wx\mathbf X = W\mathbf x, where Wkn=e−j2πkn/NW_{kn} = e^{-j2\pi kn/N}. The columns of WW are orthogonal, and W/NW/\sqrt N is a unitary matrix, a rotation in NN-dimensional complex space (see Linear algebra). Computing WxW\mathbf x directly costs N2N^2 complex multiplications.

ComputationC

The fast Fourier transform

The FFT computes exactly the same numbers as the DFT, in about N2log⁡2N\tfrac{N}{2}\log_2 N multiplications instead of N2N^2. The most common form, the radix-2 decimation-in-time FFT, works when NN is a power of 2. Split the sum into even- and odd-numbered samples: X[k]=∑m=0N/2−1x[2m] e−j2πk(2m)/N+∑m=0N/2−1x[2m+1] e−j2πk(2m+1)/N=E[k]+WNk O[k],X[k] = \sum_{m=0}^{N/2-1} x[2m]\, e^{-j2\pi k(2m)/N} + \sum_{m=0}^{N/2-1} x[2m+1]\, e^{-j2\pi k(2m+1)/N} = E[k] + W_N^k\, O[k], where WN=e−j2π/NW_N = e^{-j2\pi/N}, and EE and OO are the N/2N/2-point DFTs of the even and odd samples (because e−j2πk(2m)/N=e−j2πkm/(N/2)e^{-j2\pi k(2m)/N} = e^{-j2\pi km/(N/2)}). Those are periodic in kk with period N/2N/2, and WNk+N/2=−WNkW_N^{k + N/2} = -W_N^k, so the second half of the outputs comes almost free: X[k]=E[k]+WNk O[k],X[k+N/2]=E[k]−WNk O[k],0≤k<N/2.X[k] = E[k] + W_N^k\, O[k], \qquad X[k + N/2] = E[k] - W_N^k\, O[k], \qquad 0 \le k < N/2 .

E[k]O[k]×WkX[k] = E + WkOX[k+N/2] = E − WkO−
The butterfly, the FFT's basic operation. One multiplication by a twiddle factor W^k and one addition and one subtraction produce two outputs. An N-point FFT is log2 N stages of N/2 butterflies.

Apply the same split to EE and OO, and again, until the DFTs have length 1 (where the DFT of one sample is itself). There are log⁡2N\log_2 N levels, each doing N/2N/2 butterflies, for N2log⁡2N\tfrac N2 \log_2 N multiplications in all.

python
import numpy as np

def dft(x):
    """The DFT straight from its definition: an N x N matrix times a vector, N^2 operations."""
    N = len(x)
    n = np.arange(N)
    W = np.exp(-2j * np.pi * np.outer(n, n) / N)
    return W @ x

def fft(x):
    """Radix-2 decimation-in-time FFT. len(x) must be a power of 2."""
    N = len(x)
    if N == 1:
        return np.array(x, dtype=complex)
    E = fft(x[0::2])                                   # DFT of the even-indexed samples
    O = fft(x[1::2])                                   # DFT of the odd-indexed samples
    twiddle = np.exp(-2j * np.pi * np.arange(N // 2) / N)
    return np.concatenate([E + twiddle * O,            # X[k]         for k < N/2
                           E - twiddle * O])           # X[k + N/2]

rng = np.random.default_rng(0)
x = rng.standard_normal(1024)
X_numpy = np.fft.fft(x)
print("largest difference from np.fft.fft:")
print(f"  definition (matrix): {np.max(np.abs(dft(x) - X_numpy)):.1e}")
print(f"  our radix-2 FFT:     {np.max(np.abs(fft(x) - X_numpy)):.1e}")

# Where do the bins sit?  A 1 kHz tone, sampled at 8 kHz for 64 samples, lands in bin 1000 / (8000/64) = 8.
fs, N = 8000, 64
tone = np.cos(2 * np.pi * 1000 * np.arange(N) / fs)
mag = np.abs(fft(tone))
print(f"\nbin spacing fs/N = {fs / N} Hz; largest bins:", sorted(int(k) for k in np.argsort(mag)[-2:]),
      f"with |X| = {mag.max():.1f} = N/2")

print("\n       N    multiplications: DFT (N^2)    FFT ((N/2) log2 N)    ratio")
for p in (3, 6, 10, 16, 20):
    N = 2 ** p
    direct, fast = N * N, N // 2 * p
    print(f"{N:8}    {direct:24,}    {fast:18,}    {direct / fast:9,.0f}")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Our dozen-line FFT agrees with NumPy's to about 10−1310^{-13}, closer than the direct matrix product does, because it performs far fewer arithmetic operations and so accumulates less rounding error. The 1 kHz tone appears in bin 8 and in bin 56, which is 64−864 - 8, the negative frequency −1-1 kHz; each peak has height N/2=32N/2 = 32, because the cosine's amplitude is split equally between ±1\pm 1 kHz. And the table shows why the algorithm changed the world: for a million points it does about 100,000 times less work. A transform that would take minutes takes milliseconds.

Worked examplesH

Windowing, leakage and zero padding

The DFT assumes the NN samples are one period of a periodic signal. If a tone completes a whole number of cycles in the record, that assumption holds and the tone lands in a single bin. If not, the repeated record has a jump where its end meets its start, and the jump spreads energy across many bins. This is spectral leakage. Equivalently, taking NN samples multiplies the signal by a rectangular window, and so (by the multiplication property) convolves its spectrum with the window's sinc-shaped spectrum, whose sidelobes fall slowly.

The fix is to multiply the record by a window that tapers smoothly to zero at both ends, removing the jump. The trade-off is the time–bandwidth relation again: a smooth taper has much lower sidelobes but a wider main lobe.

WindowHighest sidelobeMain-lobe width (null to null)Typical use
Rectangular (none)−13 dB2 binstones exactly on bins; transients
Hann−31 dB4 binsgeneral-purpose spectrum analysis
Hamming−43 dB4 binsFIR filter design, speech
Blackman−58 dB6 binslarge dynamic range

The program looks for a weak tone, 60 dB below a strong one and 50 Hz away from it, using 256 samples at 1 kHz.

python
import numpy as np

fs, N = 1000, 256                              # 0.256 s of data; bins are fs/N = 3.9 Hz apart
n = np.arange(N)
strong = np.sin(2 * np.pi * 200.0 * n / fs)    # 200 Hz falls between bins 51 and 52
weak = 1e-3 * np.sin(2 * np.pi * 250.0 * n / fs)   # 60 dB quieter, 50 Hz away
x = strong + weak

def spectrum_db(x, window):
    w = window(len(x))
    X = np.abs(np.fft.rfft(x * w)) / (np.sum(w) / 2)   # scaled so a full-size tone reads 0 dB
    return 20 * np.log10(np.maximum(X, 1e-12))

rect = spectrum_db(x, np.ones)
hann = spectrum_db(x, np.hanning)
freqs = np.fft.rfftfreq(N, 1 / fs)
print("  f (Hz)   rectangular    Hann")
for k in range(48, 70, 1):
    if k % 2 == 0 or k in (51, 64):
        mark = "  <- weak tone (250 Hz)" if k == 64 else ("  <- nearest bin to the strong tone (200 Hz)" if k == 51 else "")
        print(f"{freqs[k]:7.1f}   {rect[k]:7.1f} dB  {hann[k]:7.1f} dB{mark}")

# Zero padding interpolates the spectrum; only a longer record separates close tones.
def peaks(x, nfft, lo=90, hi=112):
    """Frequencies of the local maxima of the Hann-windowed spectrum between lo and hi Hz."""
    X = np.abs(np.fft.rfft(x * np.hanning(len(x)), nfft))
    f = np.fft.rfftfreq(nfft, 1 / fs)
    i = np.arange(1, len(X) - 1)
    is_peak = (X[i] > X[i - 1]) & (X[i] > X[i + 1]) & (X[i] > 0.1 * X.max())
    return [round(float(f[k]), 1) for k in i[is_peak] if lo < f[k] < hi]

print("\ntwo equal tones at 100.0 Hz and 101.5 Hz:")
for T in (0.25, 2.0):
    m = np.arange(int(T * fs))
    pair = np.sin(2 * np.pi * 100.0 * m / fs) + np.sin(2 * np.pi * 101.5 * m / fs)
    for nfft in (len(m), 16 * len(m)):
        print(f"  record {T:4} s, FFT length {nfft:5}: grid {fs / nfft:6.4f} Hz, peaks at {peaks(pair, nfft)} Hz")
Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

With no window, the strong tone's leakage is still at about −36-36 dB fifty hertz away, and the weak tone at −60-60 dB is buried: the 250 Hz bin reads −35.8-35.8 dB, no different from its neighbours. With the Hann window the leakage falls below −75-75 dB, and the weak tone stands out at −59.3-59.3 dB, close to its true level. The price shows near the strong tone, whose peak is now spread over more bins.

Zero padding is not resolution. Appending zeros before the FFT (the second argument of np.fft.rfft) computes the same underlying spectrum on a finer grid of frequencies: it interpolates. It cannot reveal detail the data do not contain. In the second experiment, two tones 1.5 Hz apart recorded for 0.25 s appear as one peak, and padding sixteen-fold only draws that single peak more smoothly (at 100.8 Hz, between the two). Recording for 2 s separates them, because the true frequency resolution is set by the record length: about 1/T1/T, widened by a factor of 1.5 to 2 by the window. Zero padding is useful for locating an isolated peak precisely, as one of the exercises below shows.

ExplanationH

Sampling and the FFT in practice

Converters. Different ADC architectures cover different corners of the speed–precision plane. Successive-approximation (SAR) converters, which binary-search for each sample's code, dominate microcontrollers and data acquisition at up to a few million samples per second with 12 to 18 bits. Sigma-delta converters oversample heavily with a coarse quantiser and use feedback to push the quantisation noise to high frequencies, where a digital filter removes it; they dominate audio and precision measurement. Pipelined and time-interleaved converters reach hundreds of millions to billions of samples per second for radio and instruments, and RF-sampling converters now digitise signals at several gigahertz directly. Sensors and data conversion builds and characterises them.

FFTs everywhere. Wi-Fi and 4G and 5G mobile networks use OFDM, in which the transmitter builds each symbol with an inverse FFT and the receiver takes it apart with an FFT: the original 802.11a Wi-Fi used 64 points for a 20 MHz channel, and later generations use larger transforms with narrower subcarriers. Digital oscilloscopes and spectrum analysers compute FFTs continuously; vibration analysis on factory machinery looks for bearing faults as spectral lines; radio astronomers compute enormous FFTs to form spectra and images. Hardware FFT blocks are standard components on FPGAs and in modem chips.

Software. NumPy's np.fft is based on the pocketfft library; FFTW is widely used in scientific computing; GPU vendors provide their own (such as NVIDIA's cuFFT and AMD's rocFFT); and Arm's CMSIS-DSP provides FFTs tuned for microcontrollers. Conventions differ in sign, scaling and frequency ordering, so read the documentation before comparing results across tools.

Common misconceptionsH

Common misconceptions

Misconception

"Sampling at exactly twice the highest frequency is enough." The theorem needs fs>2Bf_s > 2B, strictly, and practice needs a margin for the anti-aliasing filter's transition band. CD audio's 44.1 kHz for a 20 kHz band is already a tight margin.

Misconception

"Aliasing can be filtered out after sampling." Once a 7 kHz tone has become indistinguishable from a 3 kHz one, no digital processing can separate them. Anti-aliasing must happen in the analogue domain, before the converter (or, in oversampling converters, at the high rate, before decimation).

Misconception

"Zero padding increases frequency resolution." It only interpolates between the bins of the same spectrum. Resolution is set by how long you record, Δf≈1/T\Delta f \approx 1/T.

Misconception

"The FFT is an approximation to the DFT." It computes exactly the same values, in a different order of operations, and usually with less rounding error than the direct sum.

Misconception

"More bits always mean a better measurement." Only if the signal fills the range and the analogue front end is quiet enough. A 24-bit audio converter's theoretical 146 dB is far beyond what its analogue circuits achieve; its ENOB is typically closer to 20 bits.

History & global context

A short history

Harry Nyquist, a Swedish-born engineer at AT&T, showed in 1928 that a channel of bandwidth BB can carry at most 2B2B independent pulses per second. Versions of the sampling theorem were found independently by Edmund Whittaker in Britain (1915, in interpolation theory), Vladimir Kotelnikov in the Soviet Union (1933) and Claude Shannon in the United States (1949), and it carries different names in different countries. The FFT has an even longer pre-history: Carl Friedrich Gauss used the idea around 1805 to interpolate the orbits of asteroids, in work published only after his death, and several later authors rediscovered parts of it. James Cooley and John Tukey's paper of 1965, written when computers were becoming fast enough to need it, made it universally known, and it is often listed among the most important algorithms of the twentieth century.

Exercises

Exercises

1. Sampling and the FFT

Warm-upHuman

An audio interface samples at 48 kHz with a poor anti-aliasing filter, and a 41 kHz ultrasonic tone from a nearby device gets through. At what frequency, in hertz, does it appear in the recording?

2. Sampling and the FFT

CoreHuman

A sensor system needs a quantisation SNR of at least 90 dB for a full-scale sine wave. Using the ideal-converter formula, what is the smallest number of bits that achieves it?

3. Sampling and the FFT

Warm-upHuman

A 3 kHz tone is sampled at 48 kHz, and you take a 4096-point FFT. In which bin kk (between 0 and 2048) does the tone's peak appear?

4. Sampling and the FFT

CoreHuman

You record 0.1 s of a signal at 10 kHz (1000 samples) and want to know whether it contains one tone near 500 Hz or two tones 3 Hz apart. A colleague suggests zero padding to 100,000 points to get a 0.1 Hz frequency grid. What will happen?

Choose one

5. Sampling and the FFT

CoreHuman

A vibration engineer is looking for a faint bearing-fault line 70 dB below the strong rotation line of a motor, at a frequency several bins away from it. Which analysis is most suitable?

Choose one

6. Sampling and the FFT

CoreComputational

Complete the recursive radix-2 FFT. For an input whose length NN is a power of 2: transform the even-indexed and odd-indexed samples separately, then combine them with the butterfly X[k]=E[k]+WkO[k]X[k] = E[k] + W^k O[k], X[k+N/2]=E[k]−WkO[k]X[k + N/2] = E[k] - W^k O[k], where W=e−j2π/NW = e^{-j2\pi/N}. The tests compare with np.fft.fft (which they block you from calling).

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

7. Sampling and the FFT

StretchComputational

Zero padding cannot separate close tones, but it can locate an isolated tone far more precisely than the bin spacing. Fix peak_frequency(x, fs, nfft) so that it zero-pads the Hann-windowed FFT to length nfft and returns the frequency of the largest peak. With 1000 samples at 1 kHz the bins are 1 Hz apart; with nfft = 32000 your estimate must be within 0.05 Hz of the true frequency.

Runs entirely in your browser, in an isolated worker. Nothing is sent to a server.

Further reading and resources