Homec4science
Diffusion epfl (master) Browse

R2653/teaching/MOOC/refactored/part3.txt
1471bc7137d7master

Last Change
Raw File

part3.txt
View Options

Introduction to Module 3.1
Up to now, we have described signals using a discrete-time paradigm, that is, a mathematical model in which events can be successfully described as countable sequences of complex numbers. In physics and engineering, however, the "traditional" model of the world is one in which physical quantities such as time possess an infinite granularity and are therefore best described in terms of real numbers. This so-called continuous-time paradigm speaks the language of calculus and, in it, signals are described by functions of a real-valued variable.
This model, which appeared long before the "invention" of discrete time, has been extremely successful in both abstract and applied domains and it is still the framework of choice in applications such as electronics. And, indeed, we have already used the continuous-time model, however informally, in previous modules when we have been called to label our plots with units that took into account a real-world experimental setup (such as the real frequency values in a DFT plot).
In this module we will finally build a solid mathematical bridge between these two worlds, the discrete- and continuous-time paradigms. We will soon see that for most signals of interest, these two models are equivalent, in the sense that the description of a signal can be freely translated from one language to the other and back again with no loss of information.
Historically, most of mankind's attempts to record and understand the world have taken place in discrete time: time series, as we have seen in the Introduction, represented the only available way to commit a phenomenon to paper (or clay tablet); it was only during the 17th century that a great intellectual drive to idealized abstraction put calculus at the forefront of scientific research, where it solidly remains even today. Still, because of the current ubiquity of digital processing devices, the granular nature of our data records has become "native" again; we will therefore start our journey in the world of continuous time by considering interpolation first, that is, the way to turn a sequence of samples into a function of a real variable.
Afterwards, we will show that under very mild conditions, a continuous-time function can indeed be sampled, i.e., reduced to a countable set of values, with no loss of information. The result, known as the Sampling Theorem, is perhaps the cornerstone of digital processing, since it allows us to move from the analog world to the digital world with a precise knowledge of how infomation is preserved.
Introduction to Lesson 3.1.1
By continuous-time world we indicate a description of the world in which quantities are represented by "real" numbers, i.e., numbers with an infinite granularity. This is the usual model for the world we live in, that is, our physical reality. By contrast, the discrete-time world is the model we use to describe the the world inside a digital computer, where quantities are always countable. We are first going to look at models of the world and compare digital with analog views of the world. Then we are going to look at the similarities (and the few differences) between continuous-time and discrete-tiem signal processing; this will include introducing the last form of Fourier transform we will see in this class, the continuous-time Fourier transform.
Summary of Lesson 3.1.1
There are two views of the world:
the continuous-time world, where phenomena are described functions of a real variable $$t \in \mathbb{R}$$, and where frequency $$f \in \mathbb{R}$$ is expressed in Hz. The continuous-time Fourier transform (FT) is the type of Fourier transform for these functions. The FT is not periodic.
the discrete-time world, i.e. a model of reality that lives inside a digital computer. In discrete-time, phenomena are sequences indexed an integer variable $$n \in \mathbb{Z}$$ and frequency $$\omega \in [ - \pi, \pi]$$ is dimensionless. The DTFT is the type of Fourier transform for these sequences. The DTFT is $$2\pi-$$periodic.
In continuous-time, many of the signal processing concepts that we have studied in discrete-time still hold their meaning:
the inner product between two functions is defined as $$\langle x(t), y(t) \rangle = \int_{-\infty}^{+\infty} x^*(t)y(t)dt$$.
the FT maps time to frequency (and the inverse transform goes back to time). A notable class of functions is represented by the set of bandlimited functions. The prototypical bandlimited function is the sinc(). Bandlimited functions will play a fundamental role in sampling and interpolation.
we can also define continuous-time filters and derive an equivalent convolution theorem. The FT of the output of the filter is the product of the FT of the transfer function and the FT of the input.
We are interested in moving back an forth between these two views of the world. On the one hand, interpolation describes the operation of moving from discrete-time to continuous-time, i.e. build a function from a set of samples. On the other hand, sampling describes the operation of moving from the continuous-time world to the discrete-time world, i.e., define a sequence from a function. Under which conditions the function and the sequence are faithful representation of each other is a central topic of this module.
Introduction to Lesson 3.1.2
Interpolation is the process of moving from the discrete-time world to the continuous-time world. We are given a sequence $$x[n]$$ and we would like to build a continuous-time function $$x(t)$$ that somehow "embeds" the sequence in continuous time.
We are first going to look at polynomial interpolation for finite-length data sets. Then we are going to study another method called local interpolation, where a single interpolation "shape" (or kernel) can be applied sequentially to sequences of arbitrary length. Finally, we will see how the two approaches converge to the same ideal method when the original signal is infinite-length.
Summary of Lesson 3.1.2
When we interpolate a sequence, we want to fill the gaps between samples of a sequence in such a way that
the result is smooth
the result is equal to the samples value at the samples location, mathematically $$x(t) = x[nT_s]$$ for $$t = T_s$$.
The first method to do this is called polynomial interpolation. Given a set of $$N$$ points, we can always define a polynomial of degree $$N-1$$ that passes through these N points. Beyond the simple naive approach and without loss of generality, we can define a set of $$2N+1$$ Lagrange polynomials of degree 2N
$$L_n^{(N)} (t) = \prod_{k=-N, k\neq n}^N \frac{t-k}{k-n}, n = -N, …, N$$
that have the property that
$$L_n^{(N)} (t) = \begin{cases} 1 \text{ for }t=n \\ 0 \text{ at integer multiples.} \end{cases}$$
From this set, the interpolation formula is
$$x(t) = \sum_{n=-N}^N x[n] L_n^{(N)} (t)$$
Lagrange interpolation is maximally smooth but has the drawback that the interpolation kernel depends on $$N$$. To avoid this drawback, we can define another interpolation method called local interpolation. This method uses only a neighbourhood of $$2N+1$$ points and an interpolation kernel $$i_c(t)$$ defined over these 2N+1 points that is equal to 1 at zero and 0 at nonzero integer points. Then, the interpolation formula is given by the weighted sum of these kernels by the sample value
$$x(t) = \sum_{n=-N}^{N} x[n]i_c(t-n)$$
In particular, for $$c=0$$, the interpolation kernel is a rect function and we obtain a so-called piecewise-constant interpolation. For $$c=1$$, we draw a line between consecutive samples. For $$c \rightarrow \infty$$, the interpolation kernel is a sinc function. We have now an interpolation kernel that does not depends on $$N$$ but we loose some of the smoothness in the result.
Finally, it can be shown that when N goes to infinity, the Lagrange interpolation corresponds also to a sinc interpolation. In the limit, global and local interpolation are equivalent.
Introduction to Lesson 3.1.3
In the previous lesson, we have derived an ideal iterpolation scheme based on the sinc function. Remember that the sinc is a bandlimited function; we will start this lesson by showing that the result of sinc interpolation is also bandlimited.
This raises the question: if any sequence can be interpolated to a bandlimited function via the sinc, is the converse also true? Namely, can any bandlimited function be converted to a discrete-time sequence The answer will be easy to prove once we recognize that the set of bandlimited functions constitutes a Hilbert space and that sampling is simply the decomposition of a function in this space into a linear combination of basis functions.
The final result will be the full statement of the sampling theorem.
Summary of Lesson 3.1.3
The function $$\mbox{sinc}(t/T_s)$$, whose zeros fall at multiples of $$T_s$$, is $$F_s$$-bandlimited, where $$F_s = 1/T_s$$. When we interpolate a sequence with this sinc interpolator, we obtain a continuous-time signal $$x(t)$$
$$x(t) = \sum_{n=-\infty}^{\infty} x[n] \mbox{sinc}\left( \frac{t - nT_s}{T_s} \right)$$
whose continuous-time Fourier transform is a scaled version of the DTFT of $$x[n]$$ on the interval $$[-F_s/2, F_s/2]$$ and 0 otherwise. The interpolated function is thus bandlimited.
If we take all $$F_s$$-bandlimited functions, we obtain a Hilbert space and the set of rescaled and shifted sinc function forms an orthonormal basis for this space. In other words, we can interpret sampling as the basis expansion
$$x[n] = \langle \mbox{sinc} \left( \frac{t - nT_s}{T_s} \right), x(t) \rangle = T_s x(nT_s)$$
and the interpolation as a reconstruction formula
$$x(t) = \frac{1}{T_s} \sum_{n=-\infty}^{\infty} x[n] \mbox{sinc}\left( \frac{t - nT_s}{T_s} \right)$$
Therefore any $$F_s$$-banldimited function $$x(t)$$ can be represented with no loss of information by a sequence of samples taken every $$T_s$$ seconds, as long as $$T_s \leq 1/F_s$$.
Further reading:
The sampling theorem has a very interesting history which goes back well before Shannon. Numerical analysts were concerned about interpolating tables of functions and the first one to prove a version of the sampling theorem was Whittaker in England in 1915. Harry Nyquist at Bell Labs came up with the Nyqvist criterion, namely that a function that has a maximum frequency $$F_N$$​ could be sampled at $$2F_N$$. In the Soviet Union, Kotelnikov proved another version of the sampling theorem. Whittaker's son further proved results on the sampling theorem. Then Herbert Raabe in Berlin wrote his PhD thesis about the sampling theorem but, wrong time wrong city, he got no credit for it. Denis Gabor worked on a version of the sampling theorem in the mid-1940s. Then Claude Shannon, the inventor of information theory, wrote a beautiful paper where the sampling theorem appears in the form that we use today. Last but not least, in 1949 Someya in Japan also independently proved the sampling theorem.
For a more in-depth treatment of sampling and interpolation with a similar perspective, we recommend Chapter 5, ‘’Sampling and Interpolation’’, of the “Foundations of Signal Processing’’ book by Vetterli, Kovacevic and Goyal.
For the original version of the Shannon sampling theorem, see here and look at the original paper (alternate link); the sampling theorem is Theorem 13 on p. 34. Regarding the paper, this is probably the most important paper written about communications, and it is both profound and readable, so truly a masterpiece!
Intro to Module 3.2
"Naive" or "raw" sampling is associated to the very intuitive idea of measuring the value of a phenomenon of interest over time in order to record its evolution. We have all done it in our lives, whether to monitor the temperature of a cake we are cooking or to keep track of weather patterns. In the previous lesson we have formalized this intuition and shown the conditions under which the sampling operation entails no loss of information and allows for perfect reconstruction, namely:
the function is $$F_s$$-bandlimited (that is, the highest positive frequency is $$F_s/2$$)
the sampling interval $$T_s$$ is smaller or equal to $$1/F_s$$
The mathematical derivations showed that sampling should in fact be interpreted as the decomposition of a continuous-time signal into a linear combination of sinc basis functions and that the samples are in fact the coefficients of this linear combination. The equivalence between sinc sampling and raw sampling of course only holds if the previous two conditions are met.
In signal processing practice, however, there are many situation in which this idealized setup does not hold:
we may think the signal is bandlimited but in reality it is not
we may not be able to sample fast enough
In these and in many other cases, the hypothesis of perfect bandlimitedness required by the sampling theorem is not fulfilled. We will therefore now study in detail what happens when we raw-sample a signal at a rate that is not adapted to its spectral support.
Introduction to Lesson 3.1.4
If we take samples of a continuous-time signal without fulfilling the conditions imposed by the sampling theorem, we will incur a phenomenon called aliasing. We have already encountered a simple example in the first part of this course, when we looked at the so-called wagonwheel effect: when looking at the video of a spoked wheel going forward, sometimes the wheel appears to rotate backwards.
In this lecture we are going to explore this in details, starting with sinusoids instead of wheels and then moving on to arbitrary signals. We will see that, if we sample a signal carelessly, the resulting aliasing error can be extremely disrupting.
Summary of Lesson 3.1.4
The result of raw sampling a complex exponential depends on its frequency $$f_0$$ and on the value of the sampling frequency $$F_s$$; there are three cases:
if $$F_s > 2f_0$$, we are within the condition of the sampling theorem and everything is fine
if $$f_0 < F_s < 2f_0$$, we perceive and reconstruct a sinusoid with negative frequency, i.e., the signal goes in the opposite direction
if $$F_s < f_0$$, we perceive and reconstruct a sinusoid of low frequency, in other words, frequencies above a threshold are mapped back to low frequencies.
In the last two cases we are in the presence of aliasing.
For generic signals, it turns out that the the spectrum of a raw sampled signal is (up to a scaling factor) the sum of an infinite number of translated copies of the original continuous-time spectrum. The translation "step" for each copy is equal to $$F_s$$ so, if the maximum frequency in the signal is greater than $$F_s/2$$, there will be overlap between the different repetitions and the resulting spectrum will be corrupted by aliasing.
Intro to sampling strategies
When the conditions of the sampling theorem are not fulfilled we have aliasing. The distortion introduced by aliasing cannot be undone in the discrete-time domain, so aliasing must be avoided before sampling. This is done by first lowpass filtering the signal with a filter with cutoff frequency $$F_s/2$$. This operation can be interpreted within the setup of the Hilbert space we have studied previously. This initial filtering operation is an orthogonal projection of the signal onto the subspace of bandlimited signals, from which it can be perfectly sampled and reconstructed at sampling frequency $$1/T_s$$
Sometimes, when the signal is bandpass, alias-free sampling can be achieved at rates below the nominal rate stipulated by the sampling theorem. This operation is called bandpass sampling and it's a useful exercise to understand what happens when we move from the continuous-time to the discrete-time domain.
Intro to Module 3.3
The sampling theorem provides us with a tool to map a continuous-time signal to a sequence of discrete-time samples taken at a given sampling rate. By choosing a different sampling rate, the same continuous-time signal can be mapped to an arbitrary number of different discrete-time signals. What is the relationship between these sequences as seen purely from the discrete-time world? Otherwise stated: can we transform one into another without the need to interpolate back to continuous time? These are the questions that multirate theory sets out to answer.
While the primary application of multirate theory is implicit sampling rate conversion, we will see that multirate plays an important role in a variety of applied signal processing algorithms, from the design of efficient filters, to spectral shaping for communication systems, to data compression standards. From a more theoretical point of view, multirate theory is at the cornerstone of advanced analysis techniques which go under the name of time-frequency decompositions.
Intro to 3.3.1
The fundamental operations in multirate signal processing are upsampling and downsampling; upsampling increases the number of samples in a sequence, while downsampling reduces it.
We will examine each operation in turn, both in the time and in the frequency domains. We will see that, while upsampling is a "safe" operation that can always be undone, downsampling involves a potential loss of data and therefore it must be performed with caution.
The sampling rate changes introduced by up- and downsampling represent a sort of "discrete-time sampling theorem" and the spectral characteristics of each operation will require the use of an appropriate filter to either remove unwanted spectral components or to prevent aliasing.
Finally, we will show how upsampling and downsampling can be combined to perform a fractional sampling rate change in the discrete-time domain, as we would need to do for instance if we needed to converd a CD-audio standard to DVD-audio.
What have we learned
The two fundamental operations in multirate signal processing are:
upsampling by $$N$$, in which we increase the number of samples by inserting $$N-1$$ zeros after each original sample; the insertion of zeros causes the spectrum of the original sequence to contract by $$N$$, which "brings in" $$N$$ copies of the original spectrum in the $$[-\pi, \pi]$$ interval. To remove the extra copies we need to use a lowpass with cutoff $$\pi/N$$ after upsampling.
downsampling by $$N$$, in which we decrease the number of samples by keeping only 1 sample out of $$N$$ in the original sequence; the operation causes the spectrum of the original sequence to expand by $$N$$ and produces an overlap of spectral copies that may result in aliasing. To prevent aliasing we need to use a lowpass with cutoff $$\pi/N$$ before downsampling.
Upsampling and downsampling change the underlying sampling rate by an integer factor. For a rational rate change, we can cascade an upsampler by $$M$$, a lowpass filter and a downsampler by $$M$$; the cutoff of the filter should be $$\pi/K$$ where $$K$$ is the max between $$M$$ and $$N$$. However, when $$M$$ and $$N$$ are large coprime numbers, the theoretical approach may be too onerous; in this case we can use local interpolation techniques to perform these sampling rate changes on the fly at a very low computational cost.
Intro to Mocule 4
In this module we will talk about what is really the second half of the story in digital signal processing. The first half is the discretization of time, that is, sampling; we need sampling because computing devices can only process sequences of numbers and not continous-time signals. But digital devices, which always store input values using a finite number of bits, can in fact only manipulate integer values.
Of course we have a lot of sophisticated ways to approximate real-valued quantities in a digital device using internal representations such as fixed point, floating point, double precision etc. But, ultimately, if variables are physically encoded by $$R$$ bits each, the number of possible distinct values for a sample cannot be larger than $$2^R$$.
In order to have a digital device perform signal processing on a real-world signal, after sampling the signal must be quantized, that is, each sample value must be mapped onto one of the possible values that the device can accept as input.
Quantization introduces an irreversible loss of information, which we want to keep as small as possible. Mathematically, it is convenient to model the quantization error as an additive source of noise and therefore the performance analysis of a quantizer will be analyzed using the stochastic signal processing results that we studied in the second part of this signal processing class, in module 2.3.
Introduction to Lesson 3.2.1
The easiest way to visualize what a quantizer does is to think about a simple, old fashioned thermometer: when we read the temperature, we are helped by a graduated scale in which each tick represents a degree or a fraction of a degree. While the height of the mercury column can be arbitrary, we look at the tick on the scale that is closest to the tip of the column and use that value as the temperature value, thereby discarding the micro-variations around the tick.
The open questions for a signal quantizers are
how to best design the implicit "graduated scale"
what is the error (that is, the loss of information) introduced by the quantization
We will only examine some simple cases but, in so doing, we will introduce the classic framework used in quantizer analysis: signals are consireder stochastic and, under reasonable hypotheses, quantization noise can be modeled as an additive white noise source.
what have we learned
In digital signal processing, samples are stored and processed as integers. This operation is called quantization. It maps the numeric range of the discrete samples onto a finite set of integers. Because of the difference between the actual value and the represented integer, the quantizer introduces noise in the original signal. We focused on scalar quantizers, that is, those where samples are quantized individually and independently.
If the signal's amplitude is bounded over the interval $$[A, B]$$ and uniformly distributed on this interval, the optimal $$R$$-bit quantizer is a uniform quantizer where the interval is divided into $$2^R$$ intervals of equal size and for which the optimal representation value for each subinterval is the subinterval midpoint. The error analysis is performed by modeling the resulting quantization error as a white noise source. The resulting signal-to-noise ratio is equal to $$6R$$dB.
Quantization analysis becomes more complex for different input distributuions; in many practical cases, devices such as companders are used to "shoehorn" non-uniform inputs into standard uniform quantizers.
Intro to AD DA
"Analog to Digital", or A/D, is the operation that transforms a real-world signal into a digital signal and it is achievedby combining sampling and quantization. Conversely, "Digital to Analog", or D/A, is the operation that, by combining an inverse quantization with an interpolator, produces an analog continuous-time signal from a digital sequence.
These operations, being at the interface between the digital and analog domains, are not simple "algorithms" but must be implemented by specialized hardware.
In this optional lesson, we will briefly look (in simplified terms) at the electronic circuits that are at the heard of the inexpensive, commercially available A/D and D/A converters.
Intro to Oversampling
"Oversampling" is a term used to indicate a processing technique that is improved by using a sampling rate larger than the minimum rate dictated by the sampling theorem. In this lesson we will examine two types of oversampling
in oversampled A/D we increase the sampling rate in order to compensate for the use of a cheap quantizer
in oversampled D/A we increase the sampling rate in order to compensate for the fact that an inexpensive interpolator will not use a sinc kernel
Oversampled A/D and D/A are very clever techniques that exploit the inexpensiveness of digital processing to reduce the cost of the analog electronics used in the conversion. Once again, the enormous success of digital signal processing is also due to the fact that a simple quantitative change (increase the sampling rate) can compensate for a qualitative deficiency (cheap analog circuits). Arguably, for instance, oversampled D/A is the force behind the ubiquity and affordability of digital audio devices.
What have we learned
In oversampled A/D the idea is to take more samples per unit of time. If we assume that the error remains independent from the signal, we can achieve a better SNR by lowpass filtering the oversampled signal and downsampling in the digital domain:
in the time domain, oversampled A/D corresponds to taking more samples than needed and then "averaging" them together via a lowpass filter. Averaging improves the SNR
in the frequency domain, oversampled A/D results in a "useful" signal with a narrower spectral support, while the quantization noise remains full band. The lowpass filter eliminates the out of band noise, thereby improving the SNR
In oversampled D/A we use digital oversampling to create extra "room" in the digital spectrum (the spectrum "contracts"). After interpolation to continuous time using a non-ideal interpolator there will be spurious frequency content in the analog spectrum at multples of the interpolation frequency. The extra gap created by oversampling allows us to use an analog lowpass filter after D/A with a much larger transition band, that is, a much cheaper filter.
c4science · Help