recommended netscape fonts: 14-point New Century Schoolbook or Helvetica
versions for printing: postscript and PDF (version one and version two)


revised after internal review
and ready to submit to the First IEEE Workshop on Signal Processing Education,
Hunt, Texas, Oct. 15-18, 2000.





Multi-Rate DSP Before Discrete-Time Signals and Systems

Jeffrey O. Coleman1
Senior Member, IEEE
jeffc@alum.mit.edu

Naval Research Laboratory
Advanced Radar Systems Branch
Washington, DC

Adjunct Associate Professor of Computer Science
Michigan Technological University

Adjunct Assistant Professor of Electrical Engineering
University of Maryland, Baltimore County

Abstract:

If discrete-time (d.t.) signals and sequences are viewed as distinct, with d.t. signals simply trains of impulses in continuous time (c.t.) whose areas, systematically normalized, are the sample sequences realizing those signals in computational DSP, then basic c.t. signals and systems is easily followed by an introduction to multi-rate systems for processing d.t. signals. Classic d.t. signals and systems then becomes follow-on material about realizing such systems computationally.

1 Introduction

In a strictly continuous-time world in which discrete-time signals are just trains of impulses, a good deal of DSP system design is easily handled by undergraduates through manipulation of Fourier sketches. Multi-rate signals are natural here, as are complex signals and hybrid analog/DSP systems. Impulse areas, systematically normalized, become the sample sequences that realize these signals in computational DSP systems, the later study of which encompasses traditional d.t. topics like convolution, $z$-tranforms, and the various discrete-time Fourier transforms. The c.t. approach to DSP sketched next amounts to concise teaching notes for an undergraduate presentation by a signals-and-systems instructor.

2 Digital Signal Processing in C.T.

A ``discrete-time'' (d.t.) signal $x(t)$ is one that is nonzero only on some discrete and uniformly spaced set of times including $t=0$. Expressing this as $x(t)=x(t)e^{j2\pi t/T}\!$ and Fourier transforming to $X(f)=X(f-1/T)$ shows that $1/T$, the signal's impulse rate, is a period of $X(f)$, so discrete-time signals are paired with periodic transforms. Fourier series $X(f)=\sum_n a_{n} e^{-j2\pi
nfT}\!$ has inverse Fourier transform $x(t)=\sum_n a_n \delta(t-nT)$, so discrete-time signals are just uniformly spaced impulse trains.

We are done with (explicit) math. Now it is time for pictures.

Signals versus Realization, Notation

Figure 1: From top: discrete-time signal, D/A conversion, conversion output, and sampling (output at top).
\begin{figure}{\setlength{\unitlength}{1cm}\begin{picture}(7.1,5.1)(3.3,.1)
\put(0,0){%
\input{figfigs/sampling4.tex}}
\end{picture}}
\end{figure}

Signal amplitudes here are dimensionless, but signal $x(t)$ might be realized, say, as voltage $V_{\rm ref}\,x(t)$ as on the third line of Fig. 1, with reference voltage $V_{\rm ref}$ chosen for implementation convenience. Signal impulse areas have time dimensions, so area $a T_{\rm ref}$ is naturally realized as dimensionless number $a$, and a discrete-time signal is realized computationally as a sequence of such numbers, samples, occuring at some sample rate $1/T$. For uniformly spaced impulses, we choose constant $T_{\rm ref}$ as the sample spacing $T$, as in the top line of Fig. 1. (The rest of the figure is discussed later.)

Figure 2: Interpolation leaves the signal unchanged but transforms its realization to a higher sample rate.
\begin{figure}\centering\input{figfigs/interp2.tex}
\vspace{.5ex}
\end{figure}

Is the upper left signal of Fig. 2 simply the widely spaced impulses visible? Or is it actually narrowly spaced impulses with many areas zero? The second and fourth lines of the figure show two of many possible realizations as sequences. (Halving the standard $T_{\rm ref}$, sample spacing $T$, doubles the sample scaling.) We will resolve such ambiguity by explicitly indicating the sample rate to be used in realization.

Our standard signal notation is a schematic frequency-domain sketch that mirrors signal properties, showing perhaps an impulsive nature or bandlimiting or conjugate symmetry. The example d.t. signal on the top line of Fig. 2 is shown in both time and frequency domains. In the spectral sketch, ellipses on the right indicate the spectral periodicity that flags a signal as d.t. For brevity, we generally omit the axis label ``$f$'' and the explicit ``$0$'' at the origin tic. The triangular tic mark indicates the sample rate to be used in the corresponding computational-DSP realization. Note that realizing impulse area $a T$ as dimensionless sample $a$ amounts to scaling that impulse area by tic-marked rate $1/T$ in the realization. This sample-rate tic has nothing to do with the signal itself and so can be omitted if the realizion is not of interest.

D/A Conversion

Digital-to-analog (D/A) conversion refers to filtering a d.t. input with any c.t. impulse response, but by default the latter is a centered rectangle of sample-interval width and unit area, as in the second line of Fig. 1. Unity DC gain makes the $\,{\rm sinc} (fT)$ frequency response easily sketched. The input (above axis) tic in the Fig. 1 sketch indicates the arrival rate and normalization of realization input samples. (In not indicating the reference voltage that scales the realization output, we forego logical consistency.) The omitted half-sample delay that would make the impulse response causal is of no more significance than the propagation delays generally omitted from models of other circuits and computational systems. We prefer simplicity and model such delays only when they matter.

Sampling

Multiplying d.t. signals nonsensically multiplies co-located impulses, but multiplication is valid when one signal is d.t. and the other is continuous at its impulse times, as in sampling, decimation, and multiplication by sinusoids, here considered separately.

At the bottom of Fig. 1 is a sampling example. An input signal--here a stairstep--is multiplied by a sampling waveform, impulses at some rate $1/T$ and of uniform area $T$. This becomes frequency-domain convolution with unit-area spectral impulses at impulse-rate multiples. The output (below axis) tic refers both to the sampling waveform and to the sampling operation, where it denotes an output rate and normalization in the realization, an analog-to-digital (A/D) converter (quantization ignored).

Example System: Signal Reconstruction

Figure 4: Sampling (upper left) and four systems for reconstruction of the signal sampled.
\begin{figure*}\hspace*{-.5cm}\input{figfigs/oversamp.tex}
\vspace{-1.5\baselineskip}
\end{figure*}

The first (leftmost) column of Fig. 4 describes a system using sampling (A/D conversion) and reconstruction (a D/A conversion system to ``undo'' sampling) to convert a bandlimited real signal, perhaps music in a recording studio, to d.t. form, as on a CD, and back again. The spectral sketches describe frequency-domain relationships algebraically, representing variables pictorially so their basic properties can be seen. Assume `` ${\color{blue}=\,}$'' on the left for unmarked lines after the first. Read lines from top to bottom: first ${\color{green}\star \,}$ second ${\color{blue}=\,}$ third and ( third ${\color{green}\times\,}$ fourth) ${\color{green}\times\,}$ fifth ${\color{blue}=\,}$ sixth.

Upsampling and Interpolation

The third line of Fig. 2 shows the notation for the processing step that scales the realization sample rate by some integer without affecting the signal itself. Changing the normalization of the samples from that implied by the input tic to that implied by the output tic amounts to scaling by the tic-frequency ratio. Inserting zero samples into the sample sequence in the realization to increase the sample rate by an integer factor $M$ is upsampling by $M$, denoted $\uparrow\!M$. We strain terminology by referring to the tic-mark-shifting null signal operation on the right as interpolation, corresponding to upsampling and renormalization scaling in the realization.

Digital Filtering

A digital filter convolves its d.t. input signal with its d.t. impulse response. Its input and output sample rates and frequency-response period are by default identical, as in Fig. 3.

Figure 3: A digital filter applies a periodic frequency response to a discrete-time input.
\begin{figure}\centering\vspace{2mm}
\input{figfigs/dtfiltering.tex}
\vspace{.5ex}
\end{figure}

Example System: Oversampling

The second, third, and fourth columns of Fig. 4 show oversampling alternatives to the reconstruction system in the lower part of the first column. Each digital-filtering step has an output rate a multiple of its input rate, denoting interpolation followed by digital filtering, efficiently realized in combination.

The Most-Noble Identity

Figure 5: Reordering a spectral-shaping and sampling system for practicality, two examples.
\begin{figure*}\centering\input{figfigs/firststep.tex}
\end{figure*}

Suppose we wish to shape a bandlimited signal with filtering and sample the result. Because digital filtering is more precise and repeatable than analog filtering, we might wish to use a d.t. impulse response, as in the leftmost column of Fig. 5, with the needed shaping characteristics in one period of the associated frequency response. This plan is, of course, impractical, as we have no way to apply a d.t. impulse response to an analog signal except by suffering the same implementation problems as analog filters in general. To realize the benefits of digital filtering, convolutions with d.t. responses must have inputs that are d.t. signals at compatible rates. In that Fig. 5 example, it would be much more convenient if the two operations could be reversed without affecting the output! But (suppressing the $f$ dependence) when, if ever, does $({\color{blue}X}{\color{green}\mbox{}\times H}){\color{green}\mbox{}\star G}
{\...
...}} ({\color{blue}X}{\color{green}\mbox{}\star G}){\color{green}\mbox{}\times
H}$ hold?

Figure 6: The most-noble identity, proved on the left and summarized on the right.
\begin{figure*}\centering\input{figfigs/noble2.tex}
\end{figure*}

Consider this question more generally. At the left in Fig. 6 are two systems that apply identical operations in opposite orders to a common input. On the left, ``all'' spectral copies in the output have been shifted in frequency, scaled by impulse areas, and shaped by frequency response $H(f)$, as the clumsy labeling indicates. On the right spectral shaping comes first, so it is product $X(f)H(f)$ that is shifted and output copy $k$ takes the form $a_k
X(f-\mbox{shift}_k)H(f-\mbox{shift}_k)$. The two system outputs are thus identical except that copy $k$ is shaped by $H(f)$ in one and by $H(f-\mbox{shift}_k)$ in the other. The results are identical if every shift is by a multiple of the period of $H(f)$. This most-noble identity, a generalization of the noble identity for decimation, is summarized on the right in Fig. 6.

The second column of Fig. 5 shows the now-permitted interchange of operations in our earlier example. In a second example, on the right side of Fig. 5, the new identity does not apply because the frequency-response period is too large. A standard ``trick'' applies: Function ${\color{green}G}$ is split into ${\color{green}G_1\star G_2}$, so that

\begin{eqnarray*}
({\color{blue}X}{\color{green}\mbox{}\times H}){\color{green}\...
...
{\color{green}\mbox{}\times H})
{\color{green}\mbox{}\star G_2}
\end{eqnarray*}



using associativity and the most-noble identity. Operation ${\color{green}\mbox{}\star G_2}$ at the end occurs routinely and multiplies a d.t. input in the time domain with a particular continuous waveform. But with what?

Decimation

Figure 7: Decimation multiplies a d.t. signal by a continuous waveform to discard signal impulses and replicate its spectrum.
\begin{figure}\centering\input{figfigs/dirichlet.tex}
\vspace{.5ex}
\end{figure}

On the right in Fig. 7, the periodic input spectrum is convolved with $N$ unit impulses such that the spectral result has one $N$th the input period, implying that all but every $N$th of the input impulses are multiplied by zero in the time domain. The total area $N$ of the frequency-domain impulses then gives the time-domain scaling of the $t=0$ and, by periodicity, other time-domain impulses.

Realizing this operation with the minimum input and output sample rates, as shown by the tics, results in a normalization change that divides amplitude by $N$ and cancels the scaling of the nonzeroed impulse areas. The realization is just $\downarrow\! N$, decimation by $N$.

Example: Complex Signals and IQ Downconversion

Complex d.t. signals are quite natural. The impulses have complex areas, and the samples that realize them are complex numbers. In our visual notation, conjugate-symmetric Fourier transforms of real signals have been represented in schematic form by spectral sketches even about the origin. Similarly, an asymmetric spectral sketch conveniently signifies a time-domain waveform that could be complex. Generally waveforms should be shown real only where required for correct results. For example, because the correctness of the most-noble identity was argued in Fig. 6 using a complex input signal and a complex frequency response, we know that its validity is not limited to real waveforms and frequency responses.

Our Fig. 5 discussion of spectral shaping and replication used complex signals and frequency responses throughout and can be easily extended to a realistic complex-signal application [1]. The top half of Fig. 8 shows a real narrowband bandpass input signal embedded in wideband noise and interference. To distill this signal to a minimal representation, we first filter out everything extraneous, including the redundant (by symmetry) half of the signal spectrum. The stopband of the three-filter cascade is just wide enough to suppress the negative-frequency portion of the signal and interference, and its passband is just wide enough to pass the desired positive-frequency portion of the signal. Other passbands appear periodically, but they fall where the input spectrum is empty. The system output comprises residual noise and (scaled) samples of the input's complex envelope, so by tradition the real and imaginary parts of the output are designated I and Q, the complex baseband signal's in-phase and quadrature components, and the system is an IQ demodulator or IQ downconverter.

Figure 8: Design of a demodulator for a narrowband signal embedded in wideband but bandlimited noise.
\begin{figure*}\centering {\setlength{\unitlength}{1cm}\begin{picture}(16.4,8.8)...
...,.1)
\put(0,0){%
\input{figfigs/ulslh.tex}}
\end{picture}}\\ [1ex]
\end{figure*}

To put the processing steps of this narrowband IQ demodulator into realizable order, split the spectral convolution to ``factor out'' a decimation by two and apply the most-noble identity to exchange the higher-rate sampling factor with the lowest-rate filter. Continuing in this way will result in the realizable system in the lower half of Fig. 8 after four-way factorization of the original sampling step and half a dozen applications of the most-noble identity. Here the first filter operates on a real input with a complex impulse response, and the other two filters operate on complex inputs with real impulse responses. Each filtering-decimation combination can be realized as a unit for computational efficiency.

3 Conclusion

There is certainly much more to be said on these subjects, particularly on rationales for various design decisions. Yet a development along these lines should give undergraduates enough multi-rate DSP to motivate study of more-traditional realization-oriented d.t. signals and systems and ultimately of a more-thorough multi-rate text such as Vaidyanathan [2].

Bibliography

1
Dan P. Scholnik and J. O. Coleman,
``Simple, exact models of sample-interleaving demodulators/modulators for quadrature bandpass sampling/reconstruction,''
in Proc. 1997 Conf. on Information Sciences and Systems (CISS '97), Baltimore, MD, Mar. 1997.

2
P. P. Vaidyanathan,
Multirate Systems And Filter Banks,
Prentice Hall, http://www.phptr.com/, 1993.



Footnotes

...1
The development of the digital-receiver example was supported by the Office of Naval Research (ONR) Base Program at NRL. The other material was developed for undergraduate and graduate courses at MTU and UMBC.