As we have seen, a continuous-time signal can be converted to a discrete-time sequence via sampling. By changing the value of the sampling rate we can obtain an arbitrary number of discrete-time signals from the same original continuous-time source; the number of samples per second will increase or decrease linearly with the sampling rate and, according to whether the conditions of the sampling theorem are satisfied or not, the resulting discrete-time sequences will be an exact representation of the original signal or will be affected by aliasing. Mutirate theory studies the relationship between such sequences; or, in other words, it addresses the question of whether we can transform a sampled representation into another with a different underlying sampling frequency purely from within discrete time.
The primary application of multirate theory is digital sampling rate conversion, an operation that becomes necessary when the original sampling frequency of a stored signal is incompatible with the working rate of the available D/A device. But we will see that multirate also plays an important role in a variety of applied signal processing algorithms; in particular, the technique of \textit{oversampling} is often used in situations where an increase of the data rate is used to improve the performance of the analog elements in the processing chain. Since speeding up digital computations is in general much cheaper than using high-performance analog circuits, oversampling is commonly used in consumer-level devices. Other applications of multirate range from efficient filter design, to spectral shaping for communication systems, to data compression standards. And, finally, from a more theoretical point of view, multirate is a fundamental ingredient of advanced analysis techniques which go under the name of time-frequency decompositions.
Upsampling a sequence by an integer factor $N$ produces a higher-rate sequence by creating $N-1$ new samples for every sample in the original signal. In its basic form, an upsampler simply inserts $N-1$ zeros after every input sample, as shown in Figure~\ref{fig:mr:up}. If we denote by $\mathcal{U}_N$ the upsampling operator, we have
No information is lost via upsampling and the original signal can be easily recovered by discarding the extra samples (as we will see in the next section, upsampling by $N$ followed by downsampling by $N$ returns the original signal). The spectrum of an upsampled signal can be easily obtained by first considering its \ztrans\:
In the frequency domain, therefore, upsampling is simply a contraction of the frequency axis by a factor of $N$. The inherent $2\pi$-periodicity of the spectrum must be taken into account so that, in this contraction, the periodic repetitions of the base spectrum are ``pulled in'' the $[-\pi, \pi]$ interval. The effects of upsampling on a signal's spectrum are shown graphically for a simple signal in Figures~\ref{fig:mr:upA} and~\ref{fig:mr:upB}; in all figures the top panel shows the original spectrum $X(e^{j\omega})$ over $[-\pi, \pi]$; the middle panel shows the same spectrum over a wider range to make the $2\pi$-periodicity explicitly; the last panel shows the upsampled spectrum $X_{N\uparrow}(e^{j\omega})$, highlighting the rescaling of the $[-N\pi, N\pi]$ interval.\index{upsampling|)} As a rule of thumb, upsampling ``brings in'' exactly $N$ copies of the original spectrum over the $[-\pi, \pi]$ interval even if, in the case of an even upsampling factor, one copy is split between the negative and positive frequencies.
\caption{Upsampling by $4$ in the time domain: original signal (top panel); upsampled signal, where 3 zeros have been appended to each original sample (bottom panel). Note the difference in time indexes between top and bottom panels. }\label{fig:mr:up}
The upsampled signal in~(\ref{eq:mr:up}), with its $N-1$ zeros between original samples, exhibits two problems. In the time domain, the upsampled signal looks ``jumpy'' because of the periodic zero runs. This is the discrete-time equivalent to a lack of smoothness, since the signal keeps dropping back to zero, and it is apparent in the bottom panel of Figure~\ref{fig:mr:up}. In the frequency domain, simple upsampling has ``brought in'' copies of the original spectrum in the $[-\pi, \pi]$ interval, creating spurious high frequency content. These two issues are actually one and the same and they can be solved, as we will see, by using an appropriate filter.
The problem of filling the gaps between nonzero samples in an upsampled sequence is, in many ways, similar to the discrete- to continuous-time interpolation problem of Section~\ref{sec:is:interp}, except that now we are operating entirely in discrete time. If we adapt the interpolation schemes that we have already studied, we have the following cases\index{interpolation!in multirate}:
In this discrete-time interpolation scheme, also known as \emph{piecewise-constant interpolation}, after upsampling by $N$, we use a filter with impulse response
\begin{equation}\label{eq:mr:zoh}
h_0 [n] =
\begin{cases}
1 & \ n = 0,1, \ldots, N-1 \\
0 & \mbox{ otherwise}
\end{cases}
\end{equation}
which is shown in Figure~\ref{fig:mr:zoh}-(a). This interpolation filter simply repeats the last original input samples $N$ times, giving a staircase approximation as shown in the top panel of Figure~\ref{fig:mr:upinterp}.
We know that, in continuous time, the smoothest interpolation is obtained by using a sinc function. This holds in discrete-time as well, and the resulting interpolation filter is the discrete-time sinc:
\begin{equation}
h[n] = \sinc\left(\frac{n}{N}\right)
\end{equation}
Note that the sinc above is equal to one for $n = 0$ and is equal to zero at all integer multiples of $N$, $n = kN$; this fulfills the interpolation condition, that is, after interpolation, the output equals the input at multiples of $N$: $(h \ast x_{N\downarrow})[kN] = x_{N\downarrow}[kN] = x[k]$.
The three impulse responses above are all lowpass filters; in particular, the sinc interpolator is an ideal lowpass with cutoff frequency $\omega_c = \pi/N$ while the others are approximations of the same. As a consequence, the effect of the interpolator in the frequency domain is the removal of the $N-1$ spectral copies ``drawn in'' the $[-\pi, \pi]$ interval by the upsampler. An example is shown in
Figure~\ref{fig:mr:upfilt} where the signal in Figure~\ref{upsamplingFigC} is filtered by an ideal lowpass filter with cutoff $\pi/4$.
It turns out that the smoothest possible interpolation in the time domain corresponds to the perfect removal of the spectral repetitions in the frequency domain. Interpolating with a zero-order or a first-order kernel, by contrast, only attenuates the replicas instead of performing a full removal, as we can readily see by considering their frequency responses. Since we are in discrete-time, however, there are no difficulties associated to the design of a digital lowpass filter which closely approximates an ideal filter, so that alternate kernel designs (such as optimal FIRs) can be employed.
This is in contrast to the design of discrete---to continuous---time interpolators, which are analog designs. That is why sampling rate changes are much more attractive in the discrete-time domain.
Downsampling by~$N$\index{downsampling|mie}\index{decimation} (also called subsampling or decimation)
produces a lower-rate sequence by keeping only one out of $N$ samples in the original signal. If we denote by $\mathcal{S}_N$ the downsampling operator\footnote{
We use the letter $\mathcal{S}$ rather than $\mathcal{D}$ since the latter is used for the delay operator.},
Downsampling, as shown in Figure~\ref{fig:mr:down} effectively {\em discards} $N-1$ out of $N$ samples and therefore a loss of information may be incurred. Indeed, in terms of the underlying sampling frequency, decimation produces the signal that would have been obtained by sampling $N$ times more slowly. The potential problems with this data reduction will take the form of aliasing, as we will see shortly.
\subsection{Properties of the Downsampling Operator}
The downsampling operator is linear but it is not time invariant. This can be easily verified with an example; if we subsample by~2 the signal $\mathbf{x}$ we obtain the sequence
One of the consequences of the lack of time-invariance is that complex sinusoids are not eigensequences for the downsampling operator; for instance, if $x[n] = e^{j \pi n} = (-1)^n$, we have
\begin{equation}
\label{eq:mr:12}
x_{2\downarrow}[n] = x[2n] = e^{j 2\pi n} = 1;
\end{equation}
in other words, the highest digital frequency has been mapped to the lowest frequency. This looks very much like aliasing, as we will now explore in detail.
\caption{Downsampling by $4$ in the time domain: original signal (top panel); samples ``killed'' by the downsampler (middle panel); downsampled signal (bottom panel). Note the difference in time indexes between top and bottom panels.}\label{fig:mr:down}
where $\boldsymbol{\xi}_N$ is a ``kill sequence'' defined as
\[
\xi_N[n] =
\begin{cases}
1 & \mbox{ for $n$ multiple of $N$} \\
0 & \mbox{ otherwise}
\end{cases}
\]
and shown in Figure~\label{fig:mr:xi}; indeed, multiplication by $\boldsymbol{\xi}_N$ will ``kill off'' all the terms in the sum for which the index is not a multiple of $N$. The sequence $\boldsymbol{\xi}_N$ is $N$-periodic and one way to represent it is as the inverse DFS of size $N$ of a vector of all ones, as in~(\ref{eq:fa:unitDFT1}):
we have the scaled sum of $N$ superimposed copies of the original spectrum $X(e^{j\omega})$ where each copy is shifted in frequency by a multiple of $2\pi/N$. We are in a situation similar to that of equation~(\ref{eq:is:periodizedFT}) where sampling created a periodization of the underlying spectrum; here the spectra are already inherently $2\pi$-periodic, and downsampling creates $N-1$ additional interleaved copies. The final spectrum $X_{N\downarrow} (e^{j\omega})$ is simply a stretched version of $A(e^{j\omega})$, so that the interval $[-\pi/N, \pi/N]$ becomes $[-\pi, \pi]$.
Because of the superposition, aliasing\index{aliasing!in multirate} can occur; this is a consequence of the potential loss of information that occurs when samples are discarded. For baseband signals, it is easy to verify that in order for the spectral copies in~(\ref{eq:mr:dss}) not to overlap, the maximum (positive) frequency $\omega_M$ of the original spectrum\footnote{
Here, for simplicity, we are imagining a lowpass real signal whose spectral magnitude is symmetric. More complex cases exist and some examples will be described next.}
must be less than $\pi/N$; this is the \emph{non-aliasing condition} for the downsampling operator. Conceptually, fulfillment of the non-aliasing condition indicates that the discrete-time representation of the original signal is intrinsically redundant; $(N-1)/N$ of the information can be safely discarded and this is mirrored by the fact that only $1/N$ of the spectral frequency support is nonzero. We will see shortly that, in this case, the original signal can be perfectly reconstructed with an upsampling and filtering operation.\index{downsampling|)}
In Figures~\ref{fig:mr:exA} to~\ref{fig:mr:exE}) the top panel shows the original spectrum $X(e^{j\omega})$; the second panel shows the same spectrum but plotted over a wider interval so as to make its periodic nature explicit; the third panel shows in different colors the individual terms in the sum in~(\ref{eq:mr:nonscaled}); the fourth panel shows $A(e^{j\omega})$ \emph{before} scaling and stretching by $N$; finally, the last panel shows $X_{N\downarrow}(e^{j\omega})$ over the usual $[-\pi, \pi]$ interval.
\itempar{Downsampling by 2.} If the downsampling factor is $2$, the \ztrans\ and the Fourier transform of the output are simply
Figure~\ref{fig:mr:exA} shows an example for a lowpass signal whose maximum frequency is $\omega_M = \pi/2$ (i.e.\ a half-band signal). The non-aliasing condition is fulfilled and, in the superposition, the two shifted versions of the spectrum do not overlap. As the frequency axis stretches by a factor of $2$, the original half-band signal becomes full band.
Figure~\ref{fig:mr:exB} shows an example in which the non-aliasing condition is violated. In this case, $\omega_M = 2\pi/3 > \pi/2$ and the spectral copies do overlap. We can see that, as a consequence, the downsampled signal loses its lowpass characteristics. Information is irretrievably lost and the original signal cannot be reconstructed.
\itempar{Downsampling by 3.} If the downsampling factor is $ 3 $ we have
\begin{equation*}
X_{3\downarrow}(e^{j\omega}) = \frac{1}{3}\, \left[ X \bigl(e^{j\frac{\omega}{3}} \bigr) + X \bigl(e^{j(\frac{\omega - 2\pi}{3})} \bigr) + X\bigl(e^{j(\frac{\omega - 4\pi}{3})} \bigr) \right]
\end{equation*}
Figure~\ref{fig:mr:exB} shows an example in which the non-aliasing condition is violated ($\omega_M = 2\pi/3 > \pi/3$).
\itempar{Downsampling a Highpass Signal.} Figure~\ref{fig:mr:exD} shows an example of downsampling by $2$ applied to a half-band {\em highpass} signal. Since the signal occupies only the upper half of the $[0, \pi]$ frequency band (and, symmetrically, only the lower half of the $[-\pi, 0]$ interval), the interleaved copies do not overlap and, technically, there is no aliasing. The shape of the signal, however, is changed by the downsampling operation and what started out as a highpass signal is transformed into a lowpass signal. To make the details of the transformation clearer in this example we have used a {\em complex-valued} highpass signal for which the positive and negative parts of the spectrum have different shapes; it is apparent how the original left and right spectral halves are end up in reverse positions in the final result. The original signal can be exactly reconstructed (since there is no destructive overlap between spectral copies) but the required procedure is a bit more creative and will be left as an exercise.
\subsection{Antialiasing Filters in Downsampling}
We have seen in Section~\ref{sec:is:antialias} that, in order to control the error when sampling a non-bandlimited signal, our best strategy is to bandlimit the signal using a lowpass filter. The same holds when downsampling by $N$ a signal whose spectral support extends beyond $\pi/N$: before downsampling we should apply a lowpass with cutoff $\omega_c = \pi/N$ as shown in Figure~\ref{fig:mr:downfilt}. While a loss of information is still unavoidable, the filtering operation allows us to control said loss and prevent the disrupting effects of aliasing.
An example of the processing chain is shown in Figure~\ref{fig:mr:exE} for a downsampling factor of~$2$; a half-band lowpass \index{half-band filter} filter is used to truncate the signal's spectrum outside of the $[-\pi/2, \pi/2]$ interval and then downsampling proceeds as usual with non-overlapping spectral copies.
\caption{Downsampling by $3$; the highest frequency is larger than $\pi/3$ (here, $\omega_M = 2\pi/3$) and aliasing occurs. Notice how three spectral replicas contribute to the final spectrum.}\label{fig:mr:exC}
\caption{Downsampling by~$2$ of a {\em complex} highpass signal; the asymmetric spectrum helps to understand how non-destructive aliasing works.}\label{fig:mr:exD}
The conversion from one sampling rate to another can always take the ``obvious'' route of interpolating to continuous time and resampling the resulting signal at the desired rate; but this would require dedicated analog equipment and would introduce some quality loss because of the inevitable analog noise. We have just seen, however, that we can increase or decrease the implicit rate of a sequence by an integer factor entirely in the discrete-time domain, by using an upsampler or a downsampler and a digital lowpass filter. For fractional sampling rate changes we simply need to cascade the two operators.
The order in which upsampling and downsampling are performed in a rate changer is crucial since, in general, the operators are not commutative. It is easy to appreciate this fact by means of
Intuitively it's clear that, since no information is lost when using an upsampler, in a fractional sampling rate change the upsampling operation will come first. Typically, a rate change by $N/M$ is obtained by cascading an upsampler by~$N$, a lowpass filter, and a downsampler by~$M$. Since normally the upsampler is followed by a lowpass with cutoff $\pi/N$ while the downsampler is preceded by a lowpass with cutoff $\pi/M$, we can use a single lowpass whose cutoff frequency is the minimum of the two. A block diagram of this system is shown in Figure~\ref{fig:mr:frac}.\index{fractional sampling rate change} \index{rational sampling rate change}
As an example, suppose we want to increase the rate of a sequence originally sampled at 24~KHz up to 32~KHz. For this we need a fractional change of $32/24$ which, after simplification, corresponds to an upsampler by 4 followed by a downsampler by 3, as shown in the top panel of Figure~\ref{fig:mr:fracex}; the lowpass filter's cutoff frequency is $\pi/4$ and, in this case, the lowpass filter acts solely as an interpolator since the overall rate is increased. Conversely, if we want to convert a 32~KHz signal to a 24~KHz, that is, apply a sampling rate change by $3/4$, we can use the cascade shown in the bottom panel of Figure~\ref{fig:mr:fracex}; the cutoff frequency of the filter does not change but the filter, in this case, acts as an anti-alias.
If the ratio between the two sampling frequencies cannot be decomposed into a ratio of small coprime factors, the intermediate rates in a fractional rate changer can be prohibitively high. That was the rationale, for instance, behind an infamous engineering decision taken by the audio industry in the early 90's when the first digital audio recorders (call DAT) were introduced on the market; in order to make it impossible for users to create perfect copies of CDs on digital tapes, the sampling frequency of the recorders was set to 48~KHz. Since CDs are encoded at 44.1~KHz, this required fractional change rate of 160/147. At the time, a 160-fold upsampling was simply not practical to implement so users would have to necessarily go through the analog route to copy CDs. Incidentally, although digital audio tapes have quickly faded into obsolescence, the problem of converting audio from 44.1~KHz to 48~KHz remains relevant today since the sampling frequency used in DVDs is also 48~KHz. The good news is that fractional resamplers can be implemented using local interpolation techniques rather than via a formal upsampling/downsampling chain. To understand the procedure, let's first analyze the practical version of a subsample interpolator and then apply the idea to a resampler.
\itempar{Subsample Interpolation.}
\index{subsample interpolation}
Consider an $F_s$-bandlimited continuous-time signal $\mathbf{x}_c$ and its sampled version $\mathbf{x}$ defined by $x[n] = x_c(nT_s)$, with $T_s \leq 1/F_s$. Given a fractional delay $\tau T_s$, with $|\tau|< 1/2$, we want to determine the sequence
\[
x_\tau[n] = x_c(nT_s + \tau T_s)
\]
using only discrete-time processing; for simplicity, let's just assume $T_s=1$. We know from Section~\ref{sec:is:duality} that the theoretical way to obtain $\mathbf{x}_\tau$ from $\mathbf{x}$ is to use an ideal fractional delay filter:
\[
\mathbf{x}_\tau = \mathbf{d}_\tau \ast \mathbf{x}
\]
where
\begin{align*}
D_\tau(e^{j\omega}) &= e^{j\omega\tau} \\
d_\tau[n] &= \sinc(n - \tau).
\end{align*}
As we have seen in Section~\ref{sec:is:sincinterp}, the sinc interpolator originates as the limit of polynomial interpolation when the number of interpolation points goes to infinity. In this case we can work backwards, and replace the sinc with a low-degree, \textit{local} Lagrange interpolation as in Section~\ref{sec:is:lagrange}. Given $L$ samples to the left and the right of $x[n]$, we can build the continuous-time signal\index{Lagrange interpolation}
where $L_k^{(N)}(t)$ is the $k$-th Lagrange polynomial of order $2N$ defined in~(\ref{eq:is:lagPoly}). With this, we can use the approximation
\begin{equation} \label{eq:mr:subApprox}
x_\tau[n] = l_x(n; \tau) \approx x(n + \tau).
\end{equation}
Figure~\ref{fig:mr:lagPoly} shows for instance the quadratic Lagrange polynomials that would be used for a three-point local interpolation ($L=1$); an example of the interpolation and approximation procedures are shown graphically in Figure~\ref{fig:mr:approx}.
which is the convolution, computed in $n$, between the input signal and the $(2N+1)$-tap FIR
\begin{equation}\label{eq:mr:FIRcoeffs}
\hat{d}_\tau[n] = \begin{cases}
L_k^{(N)}(\tau) & \mbox{for $|n| \leq L$} \\
0 & \mbox{otherwise}
\end{cases}
\end{equation}
For instance, for a quadratic interpolation as in Figure~\ref{fig:mr:approx}, the nonzero coefficients are
\begin{align*}
\hat{d}_\tau [-1] & = \tau \frac{ \tau -1 }{2} \\
\hat{d}_\tau [0] & = - (\tau +1)(\tau -1) \\
\hat{d}_\tau [ 1] & = \tau \frac{\tau +1}{2}
\end{align*}
The FIR interpolator is expressed in noncausal form purely out of convenience; in practical implementations an additional delay would be used to make the whole processing chain causal.
\itempar{Local resampling.} The principle of the subsample interpolator we just described can be used to perform fractional resampling. Again, consider an $F_s$-bandlimited continuous-time signal $\mathbf{x}_c$ and its sampled version $x[n] = x(n T_1)$, with $T_1 \leq 1/F_s$. Given a second sampling period $T_2 \leq 1/F_s$, we want to estimate $y[n] = x(nT_2)$ using only the discrete-time samples $x[n]$. Call
\begin{equation}
\beta = \frac{T_2}{T_1} = \frac{F_1}{F_2}
\end{equation}
the ratio between sampling frequencies; if $\beta < 1$ we are interpolating to a higher underlying rate (i.e. creating more samples overall) whereas if $\beta > 1$ we are downsampling (discarding samples overall). For any output index $n$ we can always write
\begin{equation}%\label{eq:mr:FIRcoeffs}
nT_2 = [m(n) + \tau(n)]\,T_1
\end{equation}
with\footnote{``nint'' denotes the nearest integer function, so that $\mbox{nint}(0.2) = \mbox{nint}(-0.4) = 0$.}
that is, we can associate each output sample $x_2[n]$ to a reference index $m(n)$ in the input sequence plus a fractional delay $\tau(n)$ which is kept less than one half in magnitude. With this, we can use subsample interpolation to approximate each sample
where the coefficients $\hat{d}_{\tau(n)}[k]$, defined in~(\ref{eq:mr:FIRcoeffs}), are now dependent on the output index $n$. In theory, a new set of FIR coefficients is needed for each output sample but, if $F_1$ and $F_2$ are commensurable, we only need to precompute a finite set of interpolation filters. Indeed, if we can write
\[
\beta = \frac{A}{B}, \qquad A, B \in \mathbb{N}
\]
then it is easy to verify from~(\ref{eq:mr:taun}) that
\[
\tau(n + kB) = \tau(n) \quad \mbox{for all $k\in\mathbb{Z}$}.
\]
In other words, there are only $B$ distinct values of $\tau$ that are needed for the subsample interpolation. In the case of our CD to DVD conversion, for instance, we need 147~three-tap filters.
In practical algorithms, which need to work causally, resampling takes place incrementally; this is particularly important in digital communication system design where resampling is vital in order to compensate for slight timing differences between the transmitter's D/A and the receiver's A/D, as we will see in Chapter~\ref{ch:cs}. In general, when $\beta < 1$ we will need to sometimes reuse the same anchor sample with a different $\tau$ in order to produce more samples; conversely, for $\beta > 1$, sometimes we will need to skip one or more input samples. The first case is illustrated in Figure~\ref{fig:mr:resampleup} for $\beta = 0.78$, i.e. for a 28\% sampling rate increase, and the computation of the first few resampled values proceeds as follows:
\begin{itemize}
\item $n=0$: with initial synchronism, $m(0) = 0$, $\tau(0) = 0$ so $y[0] = x[0]$.
The second case is illustrated in Figure~\ref{fig:mr:resampledown} for $\beta = 1.22$ (i.e. an 18\% rate reduction) and the computation of the first few resampled values proceeds as follows:
\begin{itemize}
\item $n=0$: with initial synchronism, $m(0) = 0$, $\tau(0) = 0$ so $y[0] = x[0]$.
-The term ``oversampling'' describes a situation in which a signal's sampling rate is deliberately increased beyond the minimum value required by the sampling theorem in order to improve the performance of A/D and D/A converters at a lower cost than would be required by the use of more sophisticated analog circuitry.
-The sampling theorem guarantees that we can losslessly convert an $F_s$-band\-limited signal $\mathbf{x}_c$ into a discrete-time sequence, provided that the sampling frequency is larger than $F_s$. In a full A/D conversion, therefore, the only remaining source of distortion is introduced by quantization. Assuming a uniformly distributed input and a matching uniform quantizer, in Section~\ref{sec:da:quantization}, we have modeled this distortion as an additive noise source,
-\begin{equation}\label{eq:mr:overAD}
- \hat{\mathbf{x}} = \mathbf{x + e},
-\end{equation}
-where $\mathbf{e}$ is a white process, \textit{uncorrelated with $\mathbf{x}$}, and whose uniform power spectral density
-depends only on $\Delta$, the width of quantization interval or, equivalently, on the number of bits per sample. This is represented pictorially in the top panel of Figure~\ref{fig:mr:overAD} which shows the PSDs of a critically sampled signal and that of the associated quantization noise; the total SNR is the ratio between the areas under the two curves. One way to improve the SNR, as we know, is to increase $R$, the number of bits per sample used by the quantizer; unfortunately, the number of electronic components in an A/D converter grows proportionally to $R^2$, and so this is an expensive option.
-
-A clever digital workaround is provided by the observation that the sampling frequency used to convert $\mathbf{x}_c$ into a digital signal does not appear explicitly in~(\ref{eq:mr:overAD}) and therefore if we oversample the analog signal by, say, a factor of two, we will ``shrink'' the support of the signal's PSD without affecting the noise; this is shown in the middle panel of Figure~\ref{fig:mr:overAD}. Increasing the sampling rate does not modify the power of the signal, so the overall SNR does not change: in the figure, note how the shrinking support is matched by a proportional increase in amplitude for the signal's PSD\footnote{
- Although we haven't explicitly introduced a sampling theorem for random processes, the formula for the spectrum of a sampled signal in~(\ref{eq:is:noAliasingSpecEq}) formally holds for power spectral densities as well, and the change in amplitude is due to the sampling frequency appearing as a scaling factor.}.
-At this point, however, we are in the digital domain and therefore it is simple (and cheap) to filter the out-of-band noise with a sharp lowpass filter with a magnitude response close to the dashed line in Figure~\ref{fig:mr:overAD}. In the example, this will halve the total power of the noise, increasing the SNR by a factor of 2 (that is, by 3~dB). We can now digitally downsample the result to obtain a critically sampled input signal with an improved SNR as illustrated in the bottom panel of Figure~\ref{fig:mr:overAD}. To foster the intuition, we can look at the process from the time domain: at a high sampling rate, neighboring samples can be seen as repeated measurements of the same value (the signal varies slowly compared to the speed of sampling) affected by quantization noise that is supposed to be independent from sample to sample; the lowpass filter acts as a local averager which reduces the variance of the noise for the subsampled sequence.
- \caption{Oversampling for A/D conversion: signal's PSD and quantization error's PSD (gray) for critically sampled signal (top panel); oversampled signal and lowpass filter (middle panel); filtered and downsampled signal (bottom panel).}\label{fig:mr:overAD}
-In general, the block diagram for an oversampled A/D is as in Figure~\ref{fig:mr:overADblock} and, theoretically, the SNR of the quantized signal improves by 3~dB for every doubling of the sampling rate with respect to the baseline SNR provided by the quantizer. However, as we just illustrated with a time-domain analysis, the technique is predicated on two fundamental assumptions, the statistical independence between signal and noise and the absence of correlation between successive noise samples, both of which become invalid as the sampling rate increases. With high oversampling factors the correlation between successive noise samples increases and therefore most of the quantization noise will leak in the band of the signal. More efficient oversampling technique use feedback and nonlinear processing to push more and more of the quantization noise out of band; these converters, known under the name of Sigma-Delta quantizers, are however very difficult to analyze theoretically.
-All practical D/A converters use a kernel-based interpolator; recall from Section~\ref{sec:is:locInterp} that the interpolated continuous-time signal in this case is
-with, as usual, $F_s = 1/T_s$. The above expression is the product of two terms; the first is the periodic digital spectrum, rescaled so that $\pi \rightarrow F_s/2$, and the second is the frequency response of the interpolation kernel.
-
-An ideal D/A converter would require a sinc interpolator, which we know not to be realizable in practice, but which would completely remove the out-of-band components from the spectrum interpolated signal as shown in Figure~\ref{fig:mr:sincInterp}, where the top panel shows a digital spectrum, the middle panel shows the two terms of Equation~(\ref{eq:mr:interpSpec}), and the bottom panel shows the final analog spectrum.
-At the other end of the interpolation gamut lies the zero-order hold which, as we have seen, is easy to implement but has terrible spectral properties; the problems are shown in Figure~\ref{fig:mr:sincInterp}, in which the contents of the three panels are as in Figure~\ref{fig:mr:sincInterp}. The ZOH-interpolated spectrum is affected in two ways:
-\begin{enumerate}
- \item there is significant out-of-band energy due to the spectral copies that are only attenuated and not eliminated by the interpolator;
- \item there is in-band distortion due to the fact that the interpolator has a non-flat passband.
-\end{enumerate}
-Yet, the zero-order-hold is so easy and cheap to implement that most D/A circuits use it exclusively.
-In theory, to compensate for the resulting problems, we would need an \textit{analog} filter whose frequency response is sketched in Figure~\ref{fig:mr:zohComp}; such a filter, however, even assuming we could design it exactly, would be a costly device since an analog filter with a sophisticated response requires high-precision electronic components.
-Again, rather than using complicated and expensive analog filters, the performance of the D/A converter can be dramatically improved if we are willing to perform the conversion at a higher rate than the nominal sampling frequency, as shown in Figure~\ref{fig:mr:overDAblock}. The digital signal is first oversampled by a factor of $N$ and then filtered with a discrete-time filter $F(e^{j\omega})$ that combines the out of band frequency rejection of a sharp lowpass with cutoff $\pi/N$ with an in-band frequency shaping that mimics the characteristic of the filter in Figure~\ref{fig:mr:zohComp}. Since the filter is digital, there is no difficulty in designing, say, an unconditionally stable FIR with the desired characteristic.
-
-The oversampled D/A procedure using a zero-order hold and an oversampling factor $N=2$ is illustrated in Figure~\ref{fig:mr:overDA}. The top panels shows the DTFT of the original signal; the spectrum that enters the interpolator is
- We use an ideal filter for convenience but of course, in practical implementations, this would be a realizable sharp lowpass.}
-matches the upsampler's rate and where $C(e^{j\omega})$ compensates for the nonflat in-band characteristics of the interpolator; the resulting spectrum is shown in the third panel. Note how oversampling has created some ``room'' to the left and the right of the spectrum; this will be important for the analog part of the D/A. If we now interpolate $x_o[n]$ at a rate of $F_o = NF_s$~Hz, we have
-\begin{align}
- X_o(f) &= \frac{1}{F_o}\,X_o(e^{j2\pi f / F_o})\, I_0\left(\frac{f}{F_o}\right) \nonumber \\
-The fourth panel in Figure~\ref{fig:mr:overDAblock} shows the digital spectrum mapped on the real frequency axis and the magnitude response of the zero-order hold; note that now the first zero crossing for the latter occurs at $NF_s$ (compare that to Figure~\ref{fig:mr:zohInterp}). Since $C(e^{j\omega})$ is designed to compensate for $I_0(f)$, we have that
-that is, the interpolation is equivalent to a sinc interpolation over the baseband. The only remaining problem is the spurious high frequency content at multiples of $F_o$, as shown in the last panel of Figure~\ref{fig:mr:overDAblock}. This needs to be eliminated with an analog filter but, because of the room between spectral replicas created by oversampling, the required filter can have a wide transition band as shown in Figure~\ref{fig:mr:overDAlast} and therefore can be implemented very cheaply using for instance a low-order Butterworth lowpass. Finally, note that the present analysis remains valid also with higher order kernels, such as the first- and third-order interpolators detailed in Section~\ref{sec:is:locInterp}, since their frequency response is similar to that of the zero-order hold.
-The success of digital signal processing originates primarily in the versatility of the digital representation of information, in which both time and amplitude are discrete quantities. We have seen in great detail how the discrete-time paradigm allows us to encode any processing goal as step-by-step algorithmic procedure that operates on countable sequences of data points; in so doing, the actual physical nature of the processing device becomes irrelevant, as long as it can carry out the standard arithmetic operations. But the discretization of time is only half of the story: in order to exploit the power of general-purpose digital processing units, we need to be able to store the discrete-time samples in a format that is compatible with digital storage, that is, as a sequence of integer numbers. The operation that achieves this discretization of amplitude is called \textit{quantization} and the cascade of a sampler followed by a quantizer is called an analog-to-digital converted (or ADC for short). An ADC, as the name implies, lies at the boundary between the analog and the digital worlds and, as such, it is a physical electronic device -- it is, in fact, the only physical device we need before we are safely ensconced in the familiar world of numerical processing.
-
-Quantization, as opposed to sampling, is not a lossless operation: as we move from the nominally infinite precision of an analog measurement to the finite precision of a digital value, some information is irreversibly discarded. Nevertheless, even in analog measurement, there is always a limit to the achievable precision which is due to the limitations of the measuring instruments and to the ubiquitous background noise that affects electronic circuits. Because of this, the error introduced by quantization is usually accepted as
-
-
-
-While we will not
-
-
-
-
-
-Modern digital memory consists of a large number of addressable binary cells called \textit{bits}, usually organized in groups called \textit{words} containing $N$ bits each. Irrespective of the strategy used to encode information into words, each word can contain at most $2^N$ distinct possible values, that is, an element from the set of integers in the interval from zero to $2^N-1$.
-
-In order to store the value of a sample into digital memory, this value must first be mapped onto a finite set of pre-determined reference levels and, if the representation uses $N$ bits per sample, the cardinality of this set cannot exceed $2^N$. The mapping operation, called \textit{quantization}, returns the index of the element in the set that best represents the input value; this index is the integer between zero and $2^N-1$ that is stored in digital memory.
-
-
-, where and the mapping operation is .
-
-
-
-The conversion from the real world (or analog value of a signal to its discretized digital
-counterpart is called analog-to-digital (A/D) conversion.
-
-
-
-
-The discrete-time paradigm that we have used from the start originates in the need to use
-
-The word ``digital'' in ``digital signal processing'' indicates that the representation of a signal is discrete \emph{both} in time and in amplitude.
-
-The
-necessity to discretize the {\em amplitude} values of a
-discrete-time signal comes from the fact that, in the
-digital world, all variables are necessarily represented
-with a finite precision. Specifically, general-purpose
-signal processors are nothing but streamlined processing
-units which address memory locations whose granularity is
-%a multiple of $8$
-an integer number of bits.
-Analogously, a transition in the opposite direction is
-shorthanded as a D/A conversion; in this case, we are
-associating a physical analog value to a digital internal
-representation of a signal sample.
-Note that, just as was the case with sampling, quantization
-and its inverse lie at the boundary between the analog and
-the digital world and, as such, they are performed by actual
+The success of digital signal processing originates primarily in the versatility of the digital representation of information, in which both time and amplitude are discrete quantities. We have seen in great detail how the discrete-time paradigm allows us to encode any processing goal as step-by-step algorithmic procedure that operates on countable sequences of data points; in so doing, the actual physical nature of the processing device becomes irrelevant, as long as it can carry out the standard arithmetic operations. But the discretization of time is only half of the story: in order to exploit the power of general-purpose digital processing units, we need to be able to store the discrete-time samples in a format that is compatible with digital storage, that is, as a sequence of integer numbers. The operation that achieves this discretization of amplitude is called \textit{quantization} and the cascade of a sampler followed by a quantizer is called an analog-to-digital converter (or AD for short). An AD, as the name implies, lies at the boundary between the analog and the digital worlds and, as such, it is a physical electronic device -- it is, in fact, the only physical device we need before we are safely ensconced in the familiar world of numerical processing.
+Quantization, as opposed to sampling, is not a lossless operation: as we move from the nominally infinite precision of an analog measurement to the finite precision of a digital value, some information is irreversibly discarded. We accept this loss because even in the analog domain there is always a limit to the achievable precision due to the imperfections of the measuring instruments and to the ubiquitous background noise that affects electronic circuits. As long as the error introduced by quantization is small and comparable the error inherent to the measurements, it can be accepted as a negligible distortion.
In Chapter~\ref{ch:intro} we illustrated the difference between analog and digital signals with the example of a home-made weather chart, drawn with the help of a simple mercury thermometer: while the outside temperature is a physical phenomenon with arbitrarily fine precision both in time and in amplitude, its evolution can be adequately described using daily measurements whose amplitude is rounded off to the nearest tick in the thermometer's graduated scale. In the weather chart example the discretization of time takes place at a rate of a single sample per day, whereas the discretization of amplitude (that is, the quantization of the temperature values) is determined by the precision of the thermometer's scale. On top of the rounding errors due to the physical size of the ticks, the thermometer also has a limited operational range and it will stop measuring accurately if the temperature becomes too high or too low.
+
\subsection{Memoryless Scalar Quantization}
+\label{sec:qt:scalarq}
+
For a generic real-valued input, an $M$-level memoryless scalar quantizer\footnote{
A memoryless scalar quantizer operates on a real-valued sequence independently on each sample and one sample at a time. More sophisticated quantization schemes may exploit potential correlation between successive samples and thus introduce memory effects in the process, or they can quantize several samples at a time to achieve performance gains.}
implements a function $q : \mathbb{R} \rightarrow \{\hat{x}_0, \hat{x}_1, \ldots, \hat{x}_{M-1}\}$ that maps the real axis onto a set $Q$ containing $M$ predetermined values. The \textit{quantization error} is defined as the difference between the original value and the associated quantization level:
\begin{equation}
e = q(x) - x;
\end{equation}
since we obviously want to minimize the quantization error, the quantization function will be
This function implicitly partitions the real axis into $M$ non-overlapping contiguous segments $I_k = [i_k, i_{k+1})$, called the quantization cells (or bins); to avoid ambiguity at the boundary, we will use right-open quantization cells. An example is shown in Figure~\ref{fig:qt:quantization}.
\caption{Quantization of the real line with $M=4$ levels; the expected input range is the interval $I=[A,B]$, the quantization values are $\hat{x}_0$ to $\hat{x}_3$ and they determine the four quantization cells $I_k = [i_k, i_{k+1})$. The quantization error for an input value $x$ falling in the third quantization cell is also shown.}\label{fig:qt:quantization}
Much as in the case of a thermometer, a quantizer is always designed with an expected range of input values in mind, called the \textit{non-overload region}; over this range $I$, with $I = [A, B]$, the quantization error will be relatively small. Conversely, if an input value falls outside of the nominal input range, it will be clipped to the maximum or minimum available quantization level and, in this case, the associated error can grow very large. Except in very rare cases, practical quantizers have a non-overload region symmetric around zero, that is, $I = [-A, A]$.
-\itempar{AD and DA.} The quantization function $q$ subsumes in fact two distinct operations:
-\begin{enumerate}
- \item the \textit{encoding} phase implements the function $q_e : \mathbb{R} \rightarrow \{0, 1, \ldots, {M-1}\}$, returning the \textit{index} of the quantization level that is closest to the input; this integer value is what is stored in digital memory during an analog-to-digital conversion process.
- \item the \textit{decoding} phase implements the function $q_d : \mathbb{N} \rightarrow \mathbb{R}$ defined by $q_d[k] = \hat{x}_k$; this function returns the quantization level associated to a valid quantization index and it is used when converting a digital signal back to the analog domain.
-\end{enumerate}
-
-
-\itempar{Bit rate.} Modern digital memory consists of a large number of addressable binary cells called \textit{bits}, usually organized in groups of $R$ bits called \textit{words}; at any one time, a word can store an element from the set of integers between zero and $2^R-1$. In a quantizer, the encoding function returns an integer index between zero and $M-1$; it is therefore almost always the case that quantizers are designed so that $M=2^R$ for some value of $R$ so that no storage is wasted. In these cases, $R$ is called the number of bits per sample or the \textit{rate} of the quantizer.
-
-
\itempar{Quantization error analysis.} Given a discrete-time signal $\mathbf{x}$ and its quantized version $\hat{\mathbf{x}}$, we can write
\[
\hat{x}[n] = x[n] + e[n]
\]
where $\mathbf{e}$ is the error (or the \textit{distortion}) introduced by the quantizer. Since quantization is a nonlinear operation, a precise analysis of the distortion is extremely difficult: while some exact results can be obtained in the case of simple signals such as a sinusoid, the problem becomes quickly intractable for generic inputs.
To simplify the problem, the first step is to move to a stochastic framework and cast the input $\mathbf{x}$ as an identically-distributed random process with sample probability density function $f_x(x)$. Looking at Figure~\ref{fig:qt:quantization}, we can express the average power of the error signal as
that is, each quantization cell contributes independently to the total distortion.
The second simplification attempts to linearize the quantization step by modeling the error as an \textit{independent, additive white noise process}, as illustrated in Figure~\ref{fig:qt:noiseModel}. The model is obviously unrealistic, since $\mathbf{e}$ is clearly a deterministic function of $\mathbf{x}$, but it can yield accurate enough results provided that:
\begin{itemize}
\item the input signal $\mathbf{x}$ is an i.i.d.\ process with a smooth pdf $f_x(x)$;
\item the input is always within the non-overload region;
\item the number of quantization levels is sufficiently large.
\end{itemize}
This set of hypotheses, called the \textit{high-resolution model}, ...
\caption{Top: standard AD conversion chain with a sampler followed by a quantizer; the digital signal is distorted nonlinearly by the quantization process. Bottom: linearized quantization model where the quantization error is an independent additive white noise source.}\label{fig:qt:noiseModel}
+The quantization function $q$ subsumes in fact two distinct operations:
+\begin{enumerate}
+ \item the \textit{encoding} phase implements the function $q_e : \mathbb{R} \rightarrow \{0, 1, \ldots, {M-1}\}$, returning the \textit{index} of the quantization level that is closest to the input;
+ \item the \textit{decoding} phase implements the function $q_d : \mathbb{N} \rightarrow \mathbb{R}$ defined by $q_d[k] = \hat{x}_k$; this function returns the quantization level associated to a valid quantization index.
+\end{enumerate}
+
+An analog-to-digital converter (or ADC), schematically illustrated in Figure~\ref{fig:qt:adda}, is an electronic device that cascades a sampler at $F_s$ samples per second with an encoding function $q_e$; the sampler is optionally preceded by an analog anti-alias lowpass filter with cutoff $F_s/2$. The ADC converts a continuous-time signal into a sequence of quantization indices $\mathbf{k}$, that is, into a sequence of integers between $0$ and $M-1$. If the signal is to be stored in memory or transmitted over a communication channel, the sequence $\mathbf{k}$ can be used as-is. Otherwise, if the signal is to be processed digitally, the processing device will first map the sequence $\mathbf{k}$ to a sequence $\hat{\mathbf{k}}$ using a digital implementation of the function $q_d$ that converts the quantization indices to an internal digital representation of the quantization levels (e.g. a floating point or a fixed point encoding).
+
+A digital-to-analog converter (or DAC), also shown in Figure~\ref{fig:qt:adda}, is a matched electronic device that combines a hardware implementation of the function $q_d$ with an interpolator at frequency $F_s$. The device takes as input a sequence of quantization indices and produces a continuous-time signal $\hat{x}_c$.
+
+
+\itempar{Bit rate.} Modern digital memory consists of a large number of addressable binary cells called \textit{bits}, usually organized in groups of $R$ bits called \textit{words}; at any one time, a word can store an element from the set of integers between zero and $2^R-1$. In a quantizer, the encoding function returns an integer index between zero and $M-1$; it is therefore almost always the case that quantizers are designed so that $M=2^R$ for some value of $R$ so that no storage is wasted. In these cases, $R$ is called the number of bits per sample or the \textit{rate} of the quantizer.
\uput[90](! -1 0.125 add 0.25 0 mul add dup){\gray 000}
\uput[90](! -1 0.125 add 0.25 1 mul add dup){\gray 001}
\uput[90](! -1 0.125 add 0.25 2 mul add dup){\gray 010}
%\uput[90](! -1 0.125 add 0.25 3 mul add dup){\gray 011}
\uput[90](! -1 0.125 add 0.25 4 mul add dup){\gray 100}
\uput[90](! -1 0.125 add 0.25 5 mul add dup){\gray 101}
\uput[90](! -1 0.125 add 0.25 6 mul add dup){\gray 110}
\uput[90](! -1 0.125 add 0.25 7 mul add dup){\gray 111}
\end{pspicture}
\caption{Uniform quantization function for $I = [-1,1]$ and $M=2^3=8$ levels; the quantization step is $\Delta = 2/8 = 0.25$. Dots on the vertical axis indicate the quantization values $\hat{x}_k$; binary numbers show the values returned by the encoding function $q_e$.}\label{fig:qt:quant8}
\itempar{Mid-riser vs. mid-tread.} We can distinguish two types of uniform quantizers:
\begin{itemize}
\item if $M$ is even, the quantizer is called \textit{mid-riser} and an input value of zero will be mapped to the first positive quantization level; a plot of the quantization function for $A=1$ and $M=8$ is shown in Figure~\ref{fig:qt:quant8}. For $x \in I$, the quantization function can be expressed mathematically as
\item when $M$ is odd, the quantizer is called \textit{mid-tread} (or \textit{deadzone}) and zero will be quantized to zero; an example for $A=1$ and $M=3$ is plotted in Figure~\ref{fig:qt:quant3}. For $x \in I$, deadzone quantization can be expressed as
\caption{Mid-tread quantization function for $I = [-1,1]$ and $M=3$; note that the binary label $11$ is not used.}\label{fig:qt:quant3}
\end{figure}
\itempar{Error analysis for a uniformly-distributed input.} As we have seen in equation~(\ref{eq:qn:errorpow}), the power of the error in a quantized random process depends both on the structure of the quantizer and on the probability distribution of the input samples, which are assumed to be identically distributed with pdf $f_x(x)$. Here, the structure of the uniform quantizer is fixed by design so the distortion will depend only on the input's distribution.
If the input samples are uniformly distributed over the non-overload region, that is, if
\[
f_x(x) = \begin{cases}
1/(B-A) & x \in [A, B] \\
0 & \mbox{otherwise,}
\end{cases}
\]
then the input process and the quantizer are perfectly matched. In this case we can rewrite~(\ref{eq:qn:errorpow}) to determine the power of the error signal as
stating that {\em each additional bit per sample improves the SNR by $6$~dB}. For example, a compact disk uses $16$~bits per sample, yielding an SNR of approximately $96$~dB\index{CD!SNR}\index{SNR!of a CD}. Since 96~dB is the ratio between the loudest signal that can be encoded and the smallest signal that is not buried under the quantization noise, this figure is often called the \textit{dynamic range}\index{dynamic range} of the medium. For DVD-audio, which uses up to 24 bits per sample, the dynamic range can grow to 144~dB.
Please note the ``6~dB rule'' is an approximation that holds only when $R$ is sufficiently large and that is further undermined by the unrealistic assumptions that the input is i.i.d.\ and that the error is uncorrelated to the input; use with caution.
\itempar{Error analysis for non-matched inputs.} Uniform quantizers are the most common type of quantizers available off the shelf, so they are often used with inputs that are not necessarily matched to their characteristics, with an expected performance penalty.
For input processes that do not overload the quantizer but whose sample distribution is not uniform, the power of the error can still be estimated if the number of quantization levels is sufficiently large. In this case the quantization cells are small enough to consider $f_x(x)$ constant over each integration interval and so we have
where, in the penultimate line, we have interpreted the sum as the Riemann approximation to the integral of the pdf, which is equal to one. For an $R$-bit quantizer, the SNR in this case will be of the form
\begin{equation} \label{eq:qt:snr_generic}
\mbox{SNR} \approx C + 6R \;\mbox{dB}
\end{equation}
where the constant $C$ accounts for the fact that the input is not uniformly distributed.
Finally, input processes that are not strictly bounded will overload the quantizer with nonzero probability and incur additional distortion because of clipping. Consider for example a Gaussian white noise process with variance $\sigma^2$; since the process is not bounded, it will overload any uniform quantizer with probability
where $[-A, A]$ is the quantizer's nominal input range. We can choose $A$ to make the probability of clipping reasonably small; for instance, if $A = 3\sigma$, then over $99\,$\% of the samples will fall in the non-overload region. With this choice, and assuming the high-resolution conditions hold, the SNR will still be of the form shown in~(\ref{eq:qt:snr_generic}), where the constant term $C$ will now also include the extra distortion due to clipping. For a Gaussian input the overload distortion can be made negligible but for input distributions with heavier tails it may be necessary to use non-uniform quantizers as detailed in the next section.
When the input distribution $f_x(x)$ is known, equation~(\ref{eq:qn:errorpow}) allows us to compute the power of the error as a function of the quantizer's parameters; the Lloyd-Max algorithm \index{Lloyd-Max} uses an iterative minimization of the distortion to determine the structure of a quantizer that is optimally matched to the input.
The fixed parameters of the procedure are the desired number of levels $M$ and the values of the extremal cell boundaries $i_0$ and $i_M$ which, in the case of distributions that are not compactly supported, can be $-\infty$ and $+\infty$ respectively; the optimization is used to determine the quantization levels $\hat{x}_k$ and the internal cell boundaries $i_k$. The quantization error power is a quadratic cost function, and its minimum can be found by solving
In the first set of partial derivatives, recall from~(\ref{eq:qn:errorpow}) that each quantization cell contributes to the overall distortion independently; from
Note that the optimal values correspond to the center of mass of the input distribution over each quantization interval, that is, to the conditional expectations
\[
\hat{x}_k = \expt{x | x \in [i_k, \leq i_{k+1})}.
\]
The optimal values of the internal cell boundaries are determined by setting the following expression to zero for $k = 1, \ldots, M-1$:
which indicates that the optimal boundaries always lie half-way between successive quantization levels. Since the dependence between quantization levels and cell boundaries is circular, the solution is usually found iteratively by first guessing an initial set of levels and then by alternating between the adjustment of boundaries via~(\ref{eq:qt:lloydmax2}) and the adjustment of levels via~(\ref{eq:qt:lloydmax1}) until the values stabilize.
If the input distribution is uniform over an interval $[A, B]$, the Lloyd-Max procedure returns the matched uniform quantizer described in the previous section, which is therefore optimal. For a Gaussian input distribution with variance $\sigma^2$, it can be shown that the signal to noise ratio of an $R$-bit non-uniform optimal quantizer is
Although interesting from the theoretical perspective, the Lloyd-Max algorithm is rarely used in practical designs since the realization of bespoke quantization circuitry is an extremely costly endeavor (recall that quantizers are physical devices, not digital algorithms). As we will see in the next section, simpler techniques exist to reshape input distributions for use with uniform, off-the-shelf quantizers.
\subsection{Companding}
-All signal processing systems, whether analog or digital, are designed for a specific range of admissible input values; in analog systems, for instance, the nominal range corresponds to the voltage excursion that the internal components can withstand and over which they behave linearly. In a digital system the {\em internal\/} range is determined by the numerical precision used in algorithmic computations while the input range is determined by the non-overload region of the AD converter. The latter is usually design to accommodate the maximum expected amplitude of the input signal (the so-called \textit{peak-to-peak} range) but naturally occurring signals are rarely uniformly distributed over this range. The amplitude of human speech, for example, is known to follow a generalized gamma distribution, which is very concentrated around the origin; if speech is quantized uniformly with a quantizer designed not to overload, the vast majority of samples will fall into just the first few cells around zero. Operationally, this is equivalent to encoding the signal with only a reduced number of quantization steps of relatively large size, with an associated increase in perceived distortion.
-
-The situation in these cases can be ameliorated with non-uniform dynamic range compression, usually via an invertible {\em companding\/} nonlinear function\index{compander}. The job of the compander is to compress the large values and expand the small one, de facto bringing the input distribution closer to uniform. The signal is then quantized uniformly and, at digital-to-analog end, the samples are processed by the inverse companding function to recover the original signal.
+All signal processing systems, whether analog or digital, are designed for a specific range of admissible input values; in analog systems, for instance, the nominal range corresponds to the voltage excursion that the internal components can withstand and over which they behave linearly. In a digital system the {\em internal\/} range is determined by the numerical precision used in algorithmic computations while the input range is determined by the non-overload region of the AD converter. The latter is usually design to accommodate the maximum expected amplitude of the input signal (the so-called \textit{peak-to-peak} range) but naturally occurring signals are rarely uniformly distributed over this range. The amplitude of human speech, for example, is known to follow a generalized gamma distribution, which is very concentrated around the origin; if speech is quantized uniformly with a quantizer designed not to overload, the vast majority of samples will fall into just the first few cells around zero. Operationally, this is equivalent to encoding the signal with only a reduced number of quantization steps of relatively large size, with an associated increase in perceived distortion.
-where it is assumed that $|x|<1$; the parameter $\mu$ controls the shape of the function, shown in Figure~\ref{fig:qt:mulaw} for $\mu=255$.
+The situation in these cases can be ameliorated with non-uniform dynamic range compression, usually via an invertible {\em companding\/} nonlinear function\index{compander} $c : \mathbb{R} \rightarrow [-A, A]$. The job of the compander is to compress the large values and expand the small one, de facto bringing the input distribution closer to uniform. The signal is then quantized uniformly and, at digital-to-analog end, the samples are processed by the inverse companding function to recover the original signal, as illustrated in Figure~\ref{fig:qt:compChain}; note that the compander is an analog device and it is usually applied directly to the continuous-time signal.
-If the companded signal is needed in quantized form, instead
-of running the analog values through an analog compander and
-then quantize uniformly we can directly design a nonuniform
-quantizer which follows the $\mu$-law characteristic. The
-method is shown in Figure~\ref{mulawQuantFig} for a $3$-bit
-quantizer with only the positive $x$-axis displayed. The
-uniform subdivision of the compander's output defines four
-unequal quantization intervals;
-\index{quantization!nonuniform} the splitting points are
-obtained using the inverse $\mu$-law transformation as
+Since the companding function must be implemented in hardware, there is limited flexibility in its design, but some established standards do exist. In speech processing, for instance, a common choice is the $\mu$-law\index{mulaw@$\mu$-law} compander, whose direct and inverse functions are
+the parameter $\mu$ controls the shape of the function, as shown in Figure~\ref{fig:qt:mulaw}. Note that the cascade of a compander with a uniform quantizer is equivalent to a non-uniform quantizer\index{quantization!nonuniform} whose internal cell boundaries are given by
+An example of the subdivision of the input range induced by a $\mu$-law compander is shown in Figure~\ref{fig:qt:mulawquant} for a 3-bit uniform quantizer over $[-1, 1]$; the vertical axis shows the uniformly-spaced quantization cells and the horizontal axis the new non-uniform subdivision induced by the compander, together with the last four new quantization levels.
+The term \textit{oversampling} describes a digital signal processing paradigm in which the sampling rate is deliberately increased beyond the critical value required by the sampling theorem in return for a performance improvement of a specific application. In particular, oversampling is commonly used in AD and DA conversion, since it trades digital processing (which is cheap) for more complicated analog circuitry (which is expensive).
+The sampling theorem guarantees that an $F_s$-band\-limited signal $\mathbf{x}_c$ can be perfectly represented by a discrete-time sequence $x[n] = x_c(nT)$ provided that $T < 1/F_s$; in AD conversion, therefore, the only source of distortion is introduced by quantization. Under the high-resolution hypothesis of Section~\ref{sec:qt:scalarq} the distortion can be modeled as an additive noise source
+\begin{equation}\label{eq:qt:overAD}
+ \hat{\mathbf{x}} = \mathbf{x + e},
+\end{equation}
+where $\mathbf{e}$ is a white process, \textit{uncorrelated with $\mathbf{x}$}, and whose uniform power spectral density
+depends only on $\Delta$, the width of quantization interval or, equivalently, on the number of bits per sample. This is sketched in the top panel of Figure~\ref{fig:qt:overAD} which shows the PSDs of a critically sampled signal and that of the associated quantization noise; the overall SNR is the ratio between the areas under the two curves. One way to improve the SNR, as we know, is to increase $R$, the number of bits per sample used by the quantizer; unfortunately, the number of electronic components in an A/D converter grows superlinearly with $R$, and so this is an expensive option.
+
+A clever digital workaround is provided by the observation that the underlying sampling frequency does not appear explicitly in~(\ref{eq:qt:overAD}) and therefore if we oversample the analog signal by, say, a factor of two, we will manage to shrink its spectral support without affecting the quantization noise; this is shown in the middle panel of Figure~\ref{fig:qt:overAD}. Increasing the sampling rate does not modify the power of the signal, so the overall SNR does not change: in the figure, note how the shrinking support is matched by a proportional increase in amplitude for the signal's PSD\footnote{
+ Although we haven't explicitly introduced a sampling theorem for random processes, the formula for the spectrum of a sampled signal in~(\ref{eq:is:noAliasingSpecEq}) formally holds for power spectral densities as well, and the change in amplitude is due to the sampling frequency appearing as a scaling factor.}.
+Since we are now operating in the digital domain, it is simple (and cheap) to filter the noise outside of the signal's bandwidth using a sharp lowpass filter with a magnitude response close to the dashed line in Figure~\ref{fig:qt:overAD}. In the example, this operation will halve the total power of the noise, increasing the SNR by a factor of 2 (that is, by 3~dB). We can now digitally downsample the result to obtain a critically sampled input signal with an improved SNR as illustrated in the bottom panel of Figure~\ref{fig:qt:overAD}.
+
+To foster the intuition, we can look at the process also from the time domain: at a high sampling rate, neighboring samples can be seen as repeated measurements of the same value since the signal varies slowly compared to the speed of the sampler; under the assumption that the quantization noise is independent of the samples, the lowpass filter can be seen as a local averager that reduces the noise variance for the subsampled sequence.
+ \caption{Oversampling for A/D conversion: signal's PSD and quantization error's PSD (gray) for critically sampled signal (top panel); oversampled signal and lowpass filter (middle panel); filtered and downsampled signal (bottom panel).}\label{fig:qt:overAD}
+In general, the block diagram for an oversampled A/D is as in Figure~\ref{fig:qt:overADblock} and, theoretically, the SNR of the quantized signal improves by 3~dB for every doubling of the sampling rate with respect to the baseline SNR provided by the quantizer. However, as we just illustrated in the above time-domain analysis, the technique is predicated on two assumptions, the statistical independence between signal and noise and the absence of correlation between successive noise samples, both of which become increasingly less realistic as the sampling rate increases. With high oversampling factors the correlation between successive noise samples increases and therefore most of the quantization noise will leak into the band of the signal. More efficient oversampling technique use feedback and nonlinear processing to push more and more of the quantization noise out of band; these converters, known under the name of Sigma-Delta quantizers, are however very difficult to analyze theoretically.
+All practical DA converters use a kernel-based interpolator; recall from Section~\ref{sec:is:locInterp} that the interpolated continuous-time signal in this case is
+with, as usual, $F_s = 1/T_s$. The above expression is the product of two terms; the first is the periodic digital spectrum, rescaled so that $\pi \rightarrow F_s/2$, and the second is the frequency response of the interpolation kernel.
+
+An ideal DA converter would require a sinc interpolator, which we know not to be realizable in practice, but which would completely remove the out-of-band components from the spectrum of the interpolated signal; this is shown in Figure~\ref{fig:qt:sincInterp}, where the top panel shows a digital spectrum, the middle panel shows the two terms of Equation~(\ref{eq:qt:interpSpec}), and the bottom panel shows the final analog spectrum.
+At the other end of the interpolation gamut lies the zero-order hold which, as we have seen, is easy to implement but has terrible spectral properties; the problems are shown in Figure~\ref{fig:qt:sincInterp}, in which the contents of the three panels are as in Figure~\ref{fig:qt:sincInterp}. The ZOH-interpolated spectrum is affected in two ways:
+\begin{enumerate}
+ \item there is significant out-of-band energy due to the spectral copies that are only attenuated and not eliminated by the interpolator;
+ \item there is in-band distortion due to the fact that the interpolator has a non-flat passband.
+\end{enumerate}
+Yet, the zero-order-hold is so easy and cheap to implement that it is used in most DAC devices. In theory, to compensate for the resulting problems, we would need an \textit{analog} filter whose frequency response is sketched in Figure~\ref{fig:qt:zohComp}; such a filter, however, even if designed exactly, would be a costly device since an analog filter with a nonstandard frequency response requires high-precision electronic components.
+Rather than using complicated and expensive analog filters, the performance of the D/A converter can be dramatically improved if we are willing to perform the conversion at a higher rate than the nominal sampling frequency, as shown in Figure~\ref{fig:qt:overDAblock}. The digital signal is first oversampled by a factor of $N$ and then filtered with a discrete-time filter $F(e^{j\omega})$ that combines the out of band frequency rejection of a sharp lowpass with cutoff $\pi/N$ with an in-band frequency shaping that mimics the characteristic of the filter in Figure~\ref{fig:qt:zohComp}. Since the filter is digital, there is no difficulty in designing, say, an unconditionally stable FIR with the desired characteristic.
+
+The oversampled DA procedure using a zero-order hold and an oversampling factor $N=2$ is illustrated in Figure~\ref{fig:qt:overDA}. The top panels shows the DTFT of the original signal; the spectrum that enters the interpolator is
+ We use an ideal filter for convenience but of course, in practical implementations, this would be a realizable sharp lowpass.}
+matches the upsampler's rate and where $C(e^{j\omega})$ compensates for the nonflat in-band characteristics of the interpolator; the resulting spectrum is shown in the third panel. Note how oversampling has created some ``room'' to the left and the right of the spectrum; this will be important for the final analog filter in the DAC. If we now interpolate $x_o[n]$ at a rate of $F_o = NF_s$~Hz, we have
+\begin{align}
+ X_o(f) &= \frac{1}{F_o}\,X_o(e^{j2\pi f / F_o})\, I_0\left(\frac{f}{F_o}\right) \nonumber \\
+The fourth panel in Figure~\ref{fig:qt:overDAblock} shows the digital spectrum mapped on the real frequency axis and the magnitude response of the zero-order hold; note that now the first zero crossing for the latter occurs at $NF_s$ (compare that to Figure~\ref{fig:qt:zohInterp}). Since $C(e^{j\omega})$ is designed to compensate for $I_0(f)$, we have that
+that is, the interpolation is equivalent to a sinc interpolation over the baseband. The only remaining problem is the spurious high frequency content at multiples of $F_o$, as shown in the last panel of Figure~\ref{fig:qt:overDAblock}. This needs to be eliminated with an analog filter but, because of the room between spectral replicas created by oversampling, the required filter can have a wide transition band as shown in Figure~\ref{fig:qt:overDAlast} and therefore can be implemented very cheaply using for instance a low-order Butterworth lowpass. Finally, note that the present analysis remains valid also with higher order kernels, such as the first- and third-order interpolators detailed in Section~\ref{sec:is:locInterp}, since their frequency response is similar to that of the zero-order hold.