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.
Sampling and the Nyquist–Shannon theorem
Sampling a continuous signal every seconds produces the sequence . The sampling rate is samples per second. Can we get 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 is band-limited: its Fourier transform is zero for . If it is sampled at a rate , then is exactly determined by its samples, and The rate is called the Nyquist rate, and half the sampling rate, , the Nyquist frequency.
Proof
Represent the sampled signal by a train of impulses, . A periodic impulse train with period has a Fourier series whose coefficients are all , so it equals . Multiplying by shifts its spectrum by (the modulation property), so The spectrum of the sampled signal is the original spectrum, repeated every . If , the copies centred at do not overlap, and an ideal low-pass filter with gain and cut-off keeps the central copy, which is . That filter's impulse response is , and applying it to the impulse train places a sinc at each sample, which is the formula.
∎
Aliasing, and the filter that prevents it
What happens if the signal does contain frequencies above ? Their spectral copies spill into the band from to , where they masquerade as lower frequencies. This is aliasing. A tone at frequency shows up at a frequency between 0 and . The program samples a 7 kHz sine at 10 kHz and compares the samples with those of a 3 kHz sine.
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)}")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 like a ball between two walls: 6 kHz appears at 4 kHz, 9 kHz and 11 kHz both at 1 kHz.
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 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 kHz fold into the audible band, so the filter must go from flat at 20 kHz to 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.
Quantisation and the 6 dB per bit rule
An -bit ADC can output only different codes. If its input range is to , the codes are spaced by the step (or LSB, least significant bit) and each sample is rounded to the nearest level, with an error between and .
Theorem— Quantisation SNR of an ideal converter
If the quantisation error is uniformly distributed over and uncorrelated with the signal, an ideal -bit converter digitising a full-scale sine wave achieves a signal-to-noise ratio of
Proof
A random error uniform on has mean zero and mean square ; this is the noise power. A full-scale sine has amplitude and power . So
∎
Each extra bit halves the step, which halves the error and so improves the SNR by 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.
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})")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, . 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.
The discrete Fourier transform
A computer holds 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 samples is the list of complex numbers and the inverse DFT recovers the samples: .
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 samples. That is exactly how to read it. The DFT treats the samples as one period of a periodic signal and finds its harmonics.
What frequency is bin ? The harmonic completes cycles in samples, that is, in seconds. So bin corresponds to the frequency
and bins above represent the negative frequencies , by the same folding as aliasing. The bin spacing is the reciprocal of the record length: one second of data gives bins 1 Hz apart, whatever the sampling rate. For a real signal, , so only the first half of the bins carries information, which is why NumPy offers np.fft.rfft.
In matrix form the DFT is , where . The columns of are orthogonal, and is a unitary matrix, a rotation in -dimensional complex space (see Linear algebra). Computing directly costs complex multiplications.
The fast Fourier transform
The FFT computes exactly the same numbers as the DFT, in about multiplications instead of . The most common form, the radix-2 decimation-in-time FFT, works when is a power of 2. Split the sum into even- and odd-numbered samples: where , and and are the -point DFTs of the even and odd samples (because ). Those are periodic in with period , and , so the second half of the outputs comes almost free:
Apply the same split to and , and again, until the DFTs have length 1 (where the DFT of one sample is itself). There are levels, each doing butterflies, for multiplications in all.
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}")Our dozen-line FFT agrees with NumPy's to about , 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 , the negative frequency kHz; each peak has height , because the cosine's amplitude is split equally between 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.
Windowing, leakage and zero padding
The DFT assumes the 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 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.
| Window | Highest sidelobe | Main-lobe width (null to null) | Typical use |
|---|---|---|---|
| Rectangular (none) | −13 dB | 2 bins | tones exactly on bins; transients |
| Hann | −31 dB | 4 bins | general-purpose spectrum analysis |
| Hamming | −43 dB | 4 bins | FIR filter design, speech |
| Blackman | −58 dB | 6 bins | large 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.
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")With no window, the strong tone's leakage is still at about dB fifty hertz away, and the weak tone at dB is buried: the 250 Hz bin reads dB, no different from its neighbours. With the Hann window the leakage falls below dB, and the weak tone stands out at 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 , 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.
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 misconceptions
Misconception
"Sampling at exactly twice the highest frequency is enough." The theorem needs , 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, .
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.
A short history
Harry Nyquist, a Swedish-born engineer at AT&T, showed in 1928 that a channel of bandwidth can carry at most 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
1. Sampling and the FFT
Warm-upHumanAn 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
CoreHumanA 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-upHumanA 3 kHz tone is sampled at 48 kHz, and you take a 4096-point FFT. In which bin (between 0 and 2048) does the tone's peak appear?
4. Sampling and the FFT
CoreHumanYou 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?
5. Sampling and the FFT
CoreHumanA 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?
6. Sampling and the FFT
CoreComputationalComplete the recursive radix-2 FFT. For an input whose length is a power of 2: transform the even-indexed and odd-indexed samples separately, then combine them with the butterfly , , where . The tests compare with np.fft.fft (which they block you from calling).
7. Sampling and the FFT
StretchComputationalZero 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.
Further reading and resources
- Communication in the presence of noise · Claude E. Shannon · 1949Shannon's paper, which states the sampling theorem and proves it with the sinc interpolation formula.
- An algorithm for the machine calculation of complex Fourier series · James W. Cooley and John W. Tukey · 1965The five-page paper that made the FFT widely known.
- On the use of windows for harmonic analysis with the discrete Fourier transform · Fredric J. Harris · 1978The classic survey of window functions and their trade-offs.
- MT-001: Taking the mystery out of the infamous formula SNR = 6.02N + 1.76 dB · Analog DevicesA converter manufacturer's tutorial (number MT-001 in its tutorial series) on the quantisation-noise formula and why to measure it carefully.
- FFTW · Matteo Frigo and Steven G. JohnsonA widely used open-source FFT library, with notes on how fast FFTs are engineered.
- numpy.fft · NumPyThe FFT routines used in this lesson, with their conventions for frequency ordering and normalisation.