Discrete-Time Processing of Continuous-Time Signals

Chapter 20 established that a band-limited signal loses nothing when it is reduced to a list of numbers, and Chapter 21 showed how the waveform is put back together again. Taken together they describe a round trip that achieves precisely nothing: a signal goes in, the same signal comes out. The point of the exercise is what happens in between.

Between the sampler and the reconstructor sits a computation — a sequence in, a sequence out, performed by a processor. The arrangement is so common that it is worth drawing once and then studying as an object in its own right. The world outside the dashed box is analogue: a microphone, an antenna, a strain gauge on one side, a loudspeaker or an actuator on the other. Inside it, everything is arithmetic.

Why go to the trouble? Because inside the box the engineering constraints disappear. A digital filter's coefficients are exact numbers; they do not drift with temperature, they do not have 5% tolerances, and they do not age. A response can be made exactly linear in phase, which no finite analogue network can achieve. A filter can be changed by rewriting a table, adapted while it runs, or replaced entirely by a different algorithm between one sample and the next. Signals can be stored, reversed, delayed by an arbitrary amount without a delay line, and processed by operations — median filtering, sorting, decision logic — that have no analogue circuit at all.

The price is the two converters, and the whole content of this chapter is the accounting of that price. Two questions must be answered. First, given the discrete-time system \(H(e^{j\Omega})\) that has been programmed, what continuous-time system has actually been built? Second, since the sampling rate is now a design variable rather than a fact of nature, how does one change it — and what is lost when one does?

Both converters must be defined precisely before anything can be proved about the cascade. The continuous-to-discrete converter, written C/D, is the simplest object in the subject: it produces the sequence of sample values.

It is worth being clear about how this differs from the impulse-train sampler of Chapter 20. There, \(x_p(t) = \sum_n x_c(nT)\delta(t-nT)\) was a continuous-time signal carrying impulses of the right weights — a device invented purely so that the Fourier transform could be applied to it. It is not something a converter builds. What a converter delivers is a list of numbers indexed by \(n\), with no units of time attached and no memory of the rate at which it was taken. The impulse train was scaffolding; the sequence is the building.

Chapter 20 nevertheless left the frequency-domain relation between the two worlds in final form, and it is repeated here because everything below rests on it.

The discrete-to-continuous converter, D/C, is the ideal reconstructor of Chapter 21: it lays down one sinc pulse per sample and adds them up. Nothing else will do, because only band-limited interpolation inverts the sampling operation exactly.

Its frequency-domain description follows in one line. The interpolating pulse \(\sin(\pi t/T)/(\pi t/T)\) is the impulse response of an ideal lowpass filter of cutoff \(\pi/T\) and passband gain \(T\); shifting it to \(t = nT\) multiplies its transform by \(e^{-j\omega nT}\). Summing over \(n\) with weights \(y[n]\) therefore gives

Read the two boxed relations side by side. C/D takes a spectrum, stretches its axis by \(1/T\), replicates it every \(2\pi\), and divides by \(T\). D/C takes one period of a spectrum, compresses the axis by \(T\), throws away everything outside \((-\pi/T, \pi/T)\), and multiplies by \(T\). They are inverses of one another whenever the replicas of the first operation do not overlap — which is the sampling theorem, seen once more.

Now assemble the chain. Assume — and this hypothesis is the whole story — that the input is band-limited so that \(X_c(j\omega) = 0\) for \(|\omega| \ge \pi/T\). Then in the base period \(|\Omega| \le \pi\) only the \(k=0\) term of the replication sum survives, and the C/D relation collapses to a clean statement:

The discrete-time system then multiplies by its frequency response, which is legitimate because \(x[n]\) is being passed through an LTI system and Chapter 16 established that multiplication of DTFTs is what such a system does:

Finally the D/C relation converts back, evaluating the sequence spectrum at \(\Omega = \omega T\) and multiplying by \(T\). For \(|\omega| \lt \pi/T\),

The output spectrum is the input spectrum multiplied by a fixed function of \(\omega\). That is exactly the signature of a continuous-time LTI system, and the function is its frequency response.

Three features of this result deserve separate attention.

The first is the cancellation of \(T\). The C/D converter introduced a factor \(1/T\) and the D/C converter a factor \(T\), and they annihilate each other. The gain of the effective system is therefore the digital filter's gain, unmodified, at every rate. Only the frequency axis depends on \(T\). This is a genuine convenience: a unity-gain digital filter builds a unity-gain analogue system whether it runs at 8 kHz or 8 MHz.

The second is the truncation at \(\pi/T\). Whatever the digital filter does, \(H_{\text{eff}}\) is identically zero above the Nyquist frequency, because the D/C converter's final lowpass forbids anything else. No system of this form can produce an output component above \(f_s/2\) — so a chain of this kind cannot generate a harmonic, cannot up-convert, and cannot manufacture bandwidth. If that is what is wanted, the rate must be raised first, which is what Section 22-8 is for.

The third is the periodicity that has quietly vanished. \(H(e^{j\Omega})\) is \(2\pi\)-periodic and always will be; \(H_{\text{eff}}(j\omega)\) is not periodic at all, because only one period of it is ever used. The truncation window \(|\omega| \lt \pi/T\) selects a single period and discards the rest.

With the equivalence established, most practical work reduces to fluency in converting a frequency between the three currencies in circulation. The continuous-time world quotes \(\omega\) in radians per second or \(f\) in hertz; the discrete-time world quotes \(\Omega\) in radians per sample, or sometimes the normalised frequency \(f/f_s\) in cycles per sample. All four are the same number wearing different clothes.

The last row of that table is the one students find unsettling and it is worth stating plainly: a component at exactly the sampling frequency is indistinguishable from a constant, because it is sampled at the same point of its cycle every time. There is nothing pathological here — it is the \(2\pi\)-periodicity of Chapter 3 arriving in physical units.

The design consequence is that the same coefficients are a different filter at every rate. A lowpass whose cutoff is programmed at \(\Omega_c = 0.2\pi\) cuts at 800 Hz in a telephone codec running at 8 kHz and at 4410 Hz in an audio player running at 44.1 kHz — same multiplications, same additions, entirely different physical behaviour. A digital filter is specified in normalised frequency and only becomes a physical object when a clock is attached to it.

This cuts both ways, and pleasantly so. To meet an analogue specification, convert the specification to \(\Omega\), design once, and the design is then reusable at any rate simply by re-scaling the clock. An entire filter library can be written in normalised frequency and deployed across products whose sampling rates differ by three orders of magnitude.

The equivalence is not only a tool for analysis. Read backwards, it is a design method: name the analogue system you want, map its frequency response onto \(|\Omega| \lt \pi\), and the discrete-time filter falls out. Two classic cases show what this buys, and both produce systems that would be awkward or impossible to build with components.

Start with the differentiator. The wanted effective response is \(H_{\text{eff}}(j\omega) = j\omega\) over the whole representable band. Substituting \(\omega = \Omega/T\) gives the digital filter immediately.

Its impulse response comes from the inverse DTFT of Chapter 16. Because \(j\Omega\) is odd and purely imaginary, the integral splits neatly:

For integer \(n\) the second term vanishes and \(\cos\pi n = (-1)^n\), leaving a strikingly simple sequence.

Compare that with the naive first difference \(y[n] = (x[n]-x[n-1])/T\), whose response is \(\big(1-e^{-j\Omega}\big)/T\), of magnitude \(2\sin(\Omega/2)/T\). At low frequencies \(2\sin(\Omega/2) \approx \Omega\) and the two agree, but at \(\Omega = \pi\) the true differentiator has gain \(\pi/T\) while the first difference has only \(2/T\) — an error of 36%. The first difference is a differentiator only in the bottom fraction of the band.

The second case is stranger and more useful. Consider a delay of \(\Delta\) sampling periods, where \(\Delta\) need not be an integer. The wanted analogue system is \(H_{\text{eff}}(j\omega) = e^{-j\omega\Delta T}\), so \(H(e^{j\Omega}) = e^{-j\Omega\Delta}\), and the impulse response is a shifted sinc.

When \(\Delta\) is an integer the sinc's zeros land on every sample but one and the filter degenerates to a shift, as it must. When \(\Delta\) is fractional no such collapse occurs and the response is infinite and non-causal — because "delay by half a sample" is a statement about the underlying continuous waveform, not about the list of numbers. There is no half-way position between two entries of an array; there is a perfectly definite half-way position on the band-limited curve those entries define, and the sinc filter computes it. Fractional delays of this kind are how a beamformer steers an array, how a digital audio workstation aligns two tracks recorded at slightly different offsets, and how a timing-recovery loop nudges a receiver's sampling instant.

The converters can be arranged the other way round: a sequence in, D/C to make a waveform, an analogue system, then C/D to make a sequence again. This arrangement is rarely built — nobody converts to analogue in order to filter and converts back — but it is analytically valuable, because it is how one gives meaning to the phrase "the continuous-time system equivalent to this digital filter", and it is the tidiest derivation of the fractional-delay result just quoted.

The algebra runs in the same three steps with the roles exchanged. The D/C output is band-limited to \(|\omega| \lt \pi/T\) by construction, so the final C/D can never alias, and no hypothesis is needed this time — the equivalence is unconditional.

Setting \(H_c(j\omega) = e^{-j\omega \Delta T}\) reproduces the fractional delay in a line. Setting \(H_c(j\omega) = j\omega\) reproduces the differentiator. The construction is a definition-maker: any analogue operation whose response is known can be transported into the discrete domain by reading it on the compressed axis \(\omega = \Omega/T\).

There is a catch, and it is the reason this is not the standard filter-design method. Real analogue prototypes — a Butterworth lowpass, a Chebyshev bandpass — are not band-limited. They have nonzero response above \(\pi/T\), and the recipe above simply ignores it, which is the same as inserting a brick-wall filter that the prototype did not have. Two repairs are in common use. Impulse invariance sets \(h[n] = T\,h_c(nT)\), sampling the prototype's impulse response, and consequently aliases the prototype's tail back into the band — acceptable for lowpass designs with fast roll-off, useless for highpass. The bilinear transform instead substitutes \(s = \frac{2}{T}\frac{1-z^{-1}}{1+z^{-1}}\), which maps the entire \(j\omega\) axis onto the unit circle exactly once and so cannot alias at all, at the cost of warping the frequency axis nonlinearly. Both belong to a filter-design course; the machinery they rest on — the mapping between the \(s\)-plane and the \(z\)-plane — is built in Chapter 23.

Once a signal is a sequence, its sampling rate becomes something a program can change. The two elementary operations are removing samples and inserting them, and each has a characteristic effect on the spectrum that must be understood before either can be used safely.

Downsampling by an integer factor \(M\) keeps every \(M\)th sample and discards the rest.

Since the result is what a slower converter would have produced, one already knows what to expect: replicas every \(2\pi\) in the new variable are replicas every \(2\pi/M\) in the old one, so the danger of overlap is \(M\) times greater. The derivation makes this precise, and the trick is to reach the answer without leaving the discrete domain. Define an intermediate sequence \(x_p[n]\) which keeps the retained samples in place and zeroes the others,

The second form of the comb is the finite geometric sum: for \(n\) a multiple of \(M\) every term is 1 and the average is 1, while otherwise the \(M\) unit vectors are equally spaced around the circle and cancel. Multiplying by \(e^{j2\pi kn/M}\) shifts a DTFT by \(2\pi k/M\), so

Removing the intervening zeros is a pure re-indexing which stretches the frequency axis by \(M\): since \(x_d[n] = x_p[nM]\) and every nonzero sample of \(x_p\) survives, \(X_d(e^{j\Omega}) = X_p(e^{j\Omega/M})\). Substituting gives the result.

The remedy is the same one Chapter 21 prescribed for the analogue sampler: filter first. A digital lowpass of cutoff \(\pi/M\) placed ahead of the downsampler guarantees the condition, at the cost of deliberately discarding the band from \(\pi/M\) to \(\pi\). The cascade of that filter with the downsampler is called a decimator, and the word "decimation" in the literature always implies the filter; a bare downsampler with no filter is an invitation to aliasing.

The efficiency argument is worth noting. It appears wasteful to compute a filtered value at every input sample and then throw \(M-1\) out of every \(M\) away, and it is: a polyphase implementation computes only the outputs that will be kept, dividing the arithmetic by \(M\) with no change to the result. That reorganisation is standard in multirate design and rests on nothing more than writing the convolution sum with its indices grouped modulo \(M\).

The opposite operation inserts \(L-1\) zeros between consecutive samples. The result is a sequence at \(L\) times the rate carrying the same information, and — importantly — one whose spectrum requires no approximation to describe.

The derivation is a single substitution: only the indices \(n = mL\) contribute to the transform sum, and \(e^{-j\Omega n}\) becomes \(e^{-j\Omega Lm}\). No aliasing can occur and no information can be lost, because nothing has been thrown away — a fact that makes upsampling the safe half of rate conversion.

What has happened instead is that the frequency axis has been compressed by \(L\). A spectrum that occupied \((-\pi, \pi)\) now occupies \((-\pi/L, \pi/L)\), and the \(2\pi\)-periodic repetitions that used to sit outside the interval have been pulled inside it. There are now \(L-1\) unwanted copies — images — within a single period, and they are precisely what makes the zero-stuffed sequence sound and look wrong: the staircase of zeros is high-frequency junk.

The gain \(L\) is easy to justify without appealing to energy arguments. The impulse response of the ideal image-rejection filter is \(h[n] = \sin(\pi n/L)/(\pi n/L)\), a sinc stretched by \(L\), whose value at \(n=0\) is exactly 1 and which is zero at every other multiple of \(L\). Convolving \(x_e\) with it therefore leaves the original samples untouched at positions \(n = mL\) and fills the gaps with the band-limited curve through them. The DTFT of that sequence is \(L\) in the passband — so the gain is not a normalisation chosen for convenience but the value that makes \(x_i[mL] = x[m]\) hold exactly.

Cheaper interpolators replace the ideal sinc with something short. Holding each sample for \(L\) output instants is the discrete zero-order hold, \(h[n] = 1\) for \(0 \le n \le L-1\); joining the samples by straight lines is the triangular kernel \(h[n] = 1 - |n|/L\) for \(|n| \le L\), which is the discrete twin of the analogue linear interpolator. Both are poor image rejecters — Chapter 21's droop analysis applies verbatim, since the triangle is the convolution of two rectangles and so has a \(\operatorname{sinc}^2\) response — but both are so cheap that they are used constantly in graphics and in coarse rate changes.

Integer factors are rarely what practice demands. A studio recording at 48 kHz must be issued on a compact disc at 44.1 kHz; a codec running at 8 kHz must feed a system running at 16 kHz; a software radio must move between whatever rate the hardware provides and whatever rate the demodulator wants. All of these are rational ratios, and any rational ratio can be realised by an interpolator followed by a decimator.

Two details make this work. The first is that the expander must come before the compressor. Downsampling first would discard information that the subsequent upsampling could never restore; upsampling first is lossless, so the pair in that order preserves everything the final rate can carry. The second is that the two filters the cascade appears to need — an anti-image lowpass at \(\pi/L\) and an anti-alias lowpass at \(\pi/M\) — sit back to back at the same rate and therefore merge into one, whose cutoff is the more restrictive of the two.

The intermediate rate can be alarming. Converting 44.1 kHz to 48 kHz needs \(L/M = 48/44.1 = 480/441 = 160/147\), so the signal passes through a nominal rate of \(160 \times 44.1 = 7.056\) MHz. Nothing is actually computed at that rate: the expander's output is mostly zeros, the filter's multiplications by those zeros are skipped, and the decimator's discarded outputs are never formed. A polyphase structure reduces the work to roughly one filter's worth of arithmetic per output sample, which is the only reason such conversions are routine.

The chapter closes by redeeming a promise made at the end of Chapter 21. The analogue anti-aliasing filter ahead of a converter must pass the signal band and reject everything from \(f_s - f_M\) upwards, and at rates barely above Nyquist that transition is so narrow that only a high-order elliptic design will do — expensive, phase-distorting, and drifting with temperature. Oversampling removes the problem by moving it. Sample at \(K f_s\) instead of \(f_s\); the first replica now begins at \(Kf_s - f_M\), so the analogue filter's transition band is enormous and a simple second-order design suffices. The sharp filtering is then done digitally, at \(\Omega_c = \pi/K\), and the sequence is decimated by \(K\) to the wanted rate.

The same argument runs backwards at the output. Chapter 21 computed the compact-disc reconstruction problem as a transition ratio of \((44.1-20)/20 = 1.205\), which demanded ninth-order elliptic analogue filters in the first generation of players. Four-times oversampling — interpolate the stored samples by 4 with a digital filter, then convert at 176.4 kHz — turns that ratio into \((176.4-20)/20 = 7.82\) and reduces the analogue filter to something a single op-amp will build. The impossible analogue problem has been traded for an easy digital one, which is a fair summary of what the whole chapter is for.

What has been assumed throughout is that the discrete-time systems in these diagrams can be designed, analysed and checked for stability. For finite-length filters that is straightforward; for the recursive filters that do most of the work economically it is not, and the tool that makes it possible is the subject of Chapter 23. Chapter 26 will then supply the algorithms that make the arithmetic fast.

Problems 1 to 3 exercise the frequency map and the effective-system result; 4 and 5 concern systems that exist only in this framework; 6 to 8 are multirate. In every rate-change problem, state the band limit before you state the answer.