The Sampling Theorem

Every part of this book so far has run two parallel tracks. Chapter 6 built linear time-invariant systems in continuous time and in discrete time; Chapter 7 built convolution twice over; Chapters 13 and 16 built the Fourier transform twice over. The two tracks have been kept deliberately separate, developed by analogy but never joined. This chapter joins them.

The engineering reason is immediate. A microphone, a thermocouple, an antenna and a strain gauge all produce a continuously varying voltage. A processor holds numbers, a finite list of them, updated at a finite rate. Between the physical world and the processor sits a device that looks at the voltage at instants \(t = 0, T, 2T, \dots\) and records what it sees. That device is a sampler, and \(T\) is the sampling period.

Stated plainly, what the sampler does ought to be a disaster. Between any two sample instants lies an interval containing uncountably many values of \(x(t)\), and every one of them is thrown away. The signal could do anything in there — spike, oscillate a thousand times, change sign — and the samples would be none the wiser. On the face of it, reconstructing \(x(t)\) from \(\{x(nT)\}\) is not merely difficult but meaningless, because infinitely many different signals pass through any given set of points.

And yet the compact disc works. Recorded music is stored as 44 100 numbers per second per channel and played back as sound no listener can distinguish from the original. Something must be wrong with the pessimistic argument, and what is wrong is the phrase "the signal could do anything in there". Real signals cannot. A signal that is band-limited — one whose Fourier transform vanishes above some frequency \(\omega_M\) — is forbidden by that very fact from wiggling arbitrarily fast. It is constrained, and the whole content of this chapter is that the constraint is exactly strong enough.

Before anything can be proved, the sampler needs a mathematical model, and the obvious model turns out to be awkward. Writing \(x[n] = x(nT)\) is certainly what the sampler produces, but \(x[n]\) is a sequence, an object living in the discrete-time world with its own transform and its own frequency variable. Comparing its spectrum with \(X(j\omega)\) means comparing quantities defined on different axes, which is precisely the confusion to be avoided while the argument is being built.

The standard device is to introduce an intermediate signal that carries the samples but still lives in continuous time. Take the impulse train — a periodic string of unit impulses spaced \(T\) apart, sometimes called the sampling function or the Dirac comb — and multiply the signal by it.

The second equality is nothing but the sampling property of the impulse from Chapter 3: \(x(t)\delta(t-kT) = x(kT)\delta(t-kT)\), because an impulse multiplying a signal cares only about the signal's value where the impulse sits. The result is a train of impulses whose weights are exactly the sample values. Nothing has been added and nothing lost — \(x_p(t)\) and the list \(\{x(kT)\}\) contain identical information — but \(x_p(t)\) is a continuous-time signal, so \(X_p(j\omega)\) exists and can be set beside \(X(j\omega)\) on the same axis.

Two points about the model deserve emphasis before the algebra starts. First, \(x_p(t)\) is a mathematical fiction; no laboratory instrument produces impulses. It is used because it makes the frequency-domain argument short and exact, and Section 20-6 returns to what real hardware does instead. Second, the impulse train is periodic, with period \(T\). That is the entire reason the argument works: everything known about periodic signals from Chapter 10 is about to be applied to it.

The sampled signal is a product of two continuous-time signals, and Chapter 14 established what a product does in the frequency domain: it convolves the transforms, with a factor of \(1/2\pi\) in front. So the first job is to find the Fourier transform of the impulse train.

Because \(p(t)\) is periodic with period \(T\), it has a Fourier series (Chapter 10) with fundamental frequency \(\omega_s = 2\pi/T\), and its coefficients are the easiest ones in the whole subject. Over one period centred on the origin the only impulse present is \(\delta(t)\), and sifting does the rest.

Every harmonic is present, and every one has the same weight \(1/T\) — a flat line spectrum stretching to infinity in both directions, which is the frequency-domain signature of an object as sharp as an impulse. Transforming term by term with the pair \(e^{\,j\omega_0 t}\leftrightarrow 2\pi\delta(\omega-\omega_0)\) from Chapter 13 turns the series into a transform.

Now apply the multiplication property. Convolving any transform with a shifted impulse simply moves it — \(X(j\omega) * \delta(\omega-k\omega_s) = X\big(j(\omega-k\omega_s)\big)\) — so convolving with a whole train of them produces a whole train of shifted copies.

This one line is the whole of Part 6. Everything that follows in this chapter and the next is a consequence of reading the picture it describes. Sampling does not blur the spectrum, does not attenuate it, does not distort its shape; it makes copies. Whatever damage sampling can do must therefore come from copies landing on top of one another, and from nothing else.

It is worth checking the scale factor for sanity. Faster sampling means smaller \(T\), hence larger \(1/T\), hence taller replicas — which is right, because \(x_p(t)\) then contains more impulses per second and carries more "area" per unit time. It also means larger \(\omega_s\), hence replicas pushed further apart. Both effects move in the helpful direction at once, and that is the reason sampling faster is always safer.

Suppose \(x(t)\) is band-limited, meaning \(X(j\omega) = 0\) for \(|\omega| \gt \omega_M\). Then the \(k=0\) copy occupies the band \([-\omega_M, \omega_M]\), the \(k=1\) copy occupies \([\omega_s-\omega_M,\ \omega_s+\omega_M]\), and so on for every \(k\). These two copies fail to overlap precisely when the left edge of the second lies to the right of the right edge of the first.

If that holds for the nearest pair of copies it holds for every pair, since all the other copies are further apart still. And when no copies overlap, the baseband copy sits alone in \([-\omega_M,\omega_M]\), scaled by \(1/T\) but otherwise untouched — so \(X(j\omega)\) can be read straight out of \(X_p(j\omega)\), and a signal whose transform is known is itself known. That is the theorem.

The two terms are constantly confused and it is worth fixing them apart now. The Nyquist rate is a property of the signal: double its highest frequency, the slowest sampling that could ever work. The Nyquist frequency is a property of the sampler: half of whatever rate you happen to be running at, the highest signal frequency that particular sampler can handle. A 20 kHz signal has a Nyquist rate of 40 kHz; a 48 kHz sampler has a Nyquist frequency of 24 kHz.

The strict inequality is not pedantry. At \(\omega_s = 2\omega_M\) exactly, adjacent copies meet edge to edge, and if the spectrum carries an impulse at \(\pm\omega_M\) — that is, if the signal contains a pure sinusoid exactly at the band edge — the two impulses land on top of each other and add. What happens then depends on the phase, and in the worst case it is total.

Every sample lands exactly on a zero crossing. The sampled record is indistinguishable from that of the signal \(x(t)=0\), and no reconstruction procedure whatever can tell them apart. Sampling a 1 kHz sine at exactly 2 kHz can return silence; sampling it at 2.001 kHz cannot. This is why practical rates always carry a margin, and why the audio standard is 44.1 kHz rather than 40 kHz for a 20 kHz band.

When the condition fails — when \(\omega_s \lt 2\omega_M\) — the copies march into one another and their overlapping tails add. In the overlap region the value of \(X_p(j\omega)\) is a sum of contributions from two different parts of the original spectrum, and once added they cannot be separated again. High-frequency content has taken on the identity of low-frequency content. This is aliasing, and Chapter 21 is largely devoted to it; the diagram below is what it looks like.

The theorem asserts that the samples determine \(x(t)\); the recovery filter says how. Looking again at the first spectrum diagram, the operation needed is obvious: keep the baseband copy, discard everything else, and correct the \(1/T\) scaling. That is an ideal lowpass filter with a very particular gain.

The verification is a single line of algebra. Inside the passband, only the \(k=0\) term of the replication sum is non-zero, because every other copy has been pushed beyond \(\omega_c\) by the non-overlap condition. So \(H(j\omega)X_p(j\omega) = T \cdot \tfrac1T X(j\omega) = X(j\omega)\) for \(|\omega| \lt \omega_c\), and zero outside — which is \(X(j\omega)\) itself, since the signal was band-limited to \(\omega_M \lt \omega_c\) in the first place. The output transform equals the input transform, so the output signal equals the input signal.

Notice how much freedom the cutoff has. Any \(\omega_c\) strictly between \(\omega_M\) and \(\omega_s-\omega_M\) works equally well, and the width of that interval is the guard band \(\omega_s - 2\omega_M\). Sampling exactly at the Nyquist rate shrinks the interval to a point, demanding a filter with a vertical skirt — physically impossible. Sampling at twice the Nyquist rate leaves a guard band as wide as the signal band itself, and an ordinary analogue filter of modest order will do. Oversampling buys filter order, and Chapter 21 puts numbers on that trade.

Real samplers do not multiply by impulses. A switch closes for a short but non-zero time \(\tau\), and either the signal passes through unaltered while the switch is closed, or a capacitor charges to the signal value and holds it. These are natural and flat-top sampling respectively, and they behave very differently in the frequency domain — one benignly, the other not.

Natural sampling replaces the impulse train by a train of rectangular pulses of width \(\tau\) and unit height. The product is still a multiplication, so the analysis of Section 20-3 runs again with new Fourier coefficients. For a rectangular pulse train the coefficients are the familiar sinc values.

The replicas survive, but each is now scaled by a different constant \(c_k\) instead of the common factor \(1/T\). The crucial point is that within any one replica the scaling is constant — \(c_k\) does not depend on \(\omega\). The baseband copy is therefore \(c_0 X(j\omega) = (\tau/T)X(j\omega)\), an undistorted version of the original, and a lowpass filter of gain \(T/\tau\) recovers \(x(t)\) exactly. Natural sampling costs nothing but a gain adjustment.

Flat-top sampling is the one that does damage, and it is also the one every practical sample-and-hold circuit performs. Here the signal is measured at \(t=nT\) and that single value is held constant for \(\tau\) seconds. Each output pulse is a rectangle whose height is a sample value, so the output is not a product with \(x(t)\) at all — it is the impulse-sampled signal convolved with one rectangular pulse.

Convolution in time is multiplication in frequency, so \(X_{ft}(j\omega) = H(j\omega)X_p(j\omega)\), and the transform of a rectangle of width \(\tau\) starting at the origin was computed in Chapter 14.

How serious the droop is depends entirely on the duty ratio \(\tau/T\). A narrow aperture, \(\tau \ll T\), makes \(\sin(\omega\tau/2)/(\omega\tau/2)\) nearly flat over the signal band and the aperture effect becomes negligible — which is exactly the sense in which the impulse model of Section 20-2 is a good approximation. A wide aperture is a worse offender, and the extreme case \(\tau = T\), where the held value persists until the next sample arrives, is the zero-order hold. It is the standard way of turning samples back into a waveform, and Chapter 21 works out its droop in detail.

The rule \(f_s \gt 2f_M\) is stated in terms of the highest frequency present, and for a signal whose spectrum runs continuously from zero up to \(f_M\) that is the natural measure. But consider a radio channel occupying 20 MHz to 24 MHz. Its highest frequency is 24 MHz, so the theorem as stated demands 48 million samples per second — for a signal carrying only 4 MHz of information. The band from 0 to 20 MHz is empty, and sampling that fast is spending an enormous amount of hardware on nothing.

Return to what the derivation actually required. Nothing in Section 20-3 mentioned \(f_M\); the condition was that replicas must not overlap. When the spectrum occupies only a strip, the replicas are strips too, and strips can be interleaved. The empty region between DC and the lower band edge is room in which the shifted copies of neighbouring replicas may be parked, provided they are parked precisely.

The 20-to-24 MHz channel makes the point vividly. Here \(B = 4\) MHz and \(f_H/B = 6\), so \(k\) may be as large as 6, and \(f_s = 2(24)/6 = 8\) MHz suffices. Following the replicas confirms it: with \(f_s = 8\) MHz the positive band shifted down by \(3f_s = 24\) MHz lands on \(-4\) to \(0\) MHz, the negative band \(-24\) to \(-20\) MHz shifted up by 24 MHz lands on \(0\) to \(4\) MHz, and the two fit together in the baseband without a gap and without an overlap. A 48 MHz converter has been replaced by an 8 MHz one.

The technique is called undersampling or bandpass sampling, and it is the foundation of software-defined radio. The sampler is doing two jobs at once: it discretises, and it translates the channel down to baseband, replacing a mixer and a local oscillator. The price is that the analogue front-end filter must now be a genuinely sharp bandpass filter — any energy outside \([f_L, f_H]\) will alias in with nothing to stop it — and that the sample-and-hold aperture must be short enough and its timing steady enough to track a 24 MHz waveform even though it fires only 8 million times a second.

The impulse train has served its purpose and can now be dismissed. What a converter really delivers is the sequence \(x[n] = x(nT)\), and the question is how its discrete-time Fourier transform relates to \(X(j\omega)\). The answer falls out by writing both transforms as sums over the same numbers.

Take the transform of \(x_p(t)\) directly from its definition as a sum of weighted impulses, using the sifting property once more:

The two expressions are the same sum. They differ only in how the exponent is written, and they coincide under the single substitution \(\Omega = \omega T\). The discrete-time frequency variable is therefore nothing but the continuous-time one measured in units of the sampling rate — a normalised frequency, radians per sample rather than radians per second.

This closes a loop opened in Chapter 3. There it was observed, as a curiosity of algebra, that \(e^{j(\Omega+2\pi)n} = e^{j\Omega n}\) — that discrete-time frequency lives on a circle and that the fastest possible oscillation occurs at \(\Omega = \pi\). Chapter 16 then found the DTFT to be inescapably \(2\pi\)-periodic and took the periodicity as given. The reason is now visible: \(2\pi\) in \(\Omega\) is \(\omega_s\) in \(\omega\), and the periodicity of the DTFT is precisely the spectral replication that sampling performs. A sequence knows nothing about the rate at which it was taken, so it cannot distinguish frequencies separated by \(\omega_s\); its spectrum repeats because those frequencies were made identical the moment the samples were recorded.

The practical consequence is the one every DSP engineer works with daily. A digital filter specified to cut off at \(\Omega_c = 0.3\pi\) cuts off at \(0.3\pi/(2\pi T) = 0.15 f_s\) — 1.2 kHz if it is running at 8 kHz, 6.6 kHz if it is running at 44.1 kHz. The same coefficients, the same sequence of arithmetic, a different filter in the physical world. Chapter 22 builds the whole discrete-time processing chain on this correspondence.

Problems 1 to 3 drill the Nyquist rate; 4 to 6 work with the replicated spectrum; 7 and 8 push into the practical and bandpass cases. Sketch \(X_p(j\omega)\) before computing anything wherever a spectrum is involved.