Homec4science
Diffusion epfl (master) Browse

R2653/teaching/MOOC/refactored/part1.txt
80c15e86371emaster

Last Change
Raw File

part1.txt
View Options

Welcome, and thank you for your interest in our DSP course! This is the new, refurbished version of the original DSP class that we have been offering on Coursera since 2013. For this new edition, we split the material into four independent courses:
DSP1: Digital signals and Fourier transforms
DSP2: Linear filters and adaptive processing
DSP3: Sampling and interpolation
DSP4: Digital communications and real-time DSP
The new structure will allow you to progress incrementally if you are new to the world of digital signal processing or, if you would like a simple refresher course, you will be able to choose the module that best fits your needs. All four courses follow the same principles of the original set of lectures: the material is based on a freely-available textbook and each module includes automatically graded exercises that will be used for your final grade. There are no programming assignments but every module is complemented by Jupyter notebooks in Python that implement most of the algorithms discussed in the lectures.
In this module, DSP1, you will learn about the basics of digital signal processing starting from first principles. Our personal approach is to describe signal processing using the language of vector space and linear algebra; while perhaps a bit perplexing initially (especially if you're a hands-on practicioner), this approach has the advantage to let us describe very naturally the dual nature of signals in the time and in the frequency domains. In particular, the Fourier transform will emerge as a simple change of basis (that is, a literal change of viewpoint) in the space of digital signals.
Introduction to Lesson 1.1.1
In this introductory video, we will leisurely talk about signal processing from both a historical and a technical perspective. In particular, we will illustrate how, in the history of scientific inquiry, there have always been two models for the world around us, an idealized abstraction in which we describe things by way of functions and we use calculus, and a more pragmatic approach in which we describe things via sets of numerical measurements. Digital Signal Processing is the crowning achievement of this latter approach, and the ability (via the Sampling Theorem) to bridge DSP to the classical mathematical models of reality is the reason why we are so successful at harnessing information in this time and age.
At the end of the introduction we will illustrate the latter point in detail by showing how information is transmitted over transoceanic cables; a companion Python notebook is available in this module so you can play with the numerical aspects of the approach.
Introduction to Lesson 1.1.2
In this lecture we will formally introduce the concept of discrete-time signal, together with examples of the most common signals we will encounter in the rest of the course. We will also talk about basic operations on discrete-time signals, which will enable us to start designing simple algorithms in the next lecture.
Introduction to Lesson 1.1.3
In the first part of this lecture we will quickly look at how to bridge the gap between the abstract world of discrete-time signals and what is known as the "analog world", that is, the world described in mathematical terms that are used in physics and electronics. In particular, we will lay down the basic principles that are at work in your computer soundcard when you play a digital sound file.
In the second part of the lecture we will illustrate a simple, and yet surprisingly effective, sound synthesis system, known as the Karplus-Strong algorithm. You will be able to see that, even with the limited DSP tools at our disposal at this point in the class, we can already perform some non-trivial signal processing. By the way, don't forget to check out the associated Python notebook so you can play with the Karplus-Strong synthesizer!
Introduction to Lesson 1.1.4
We have seen some examples of discrete-time two lessons ago. This lecture is devoted entirely to a type of signal that will play a fundamental role in many topics to come, from Fourier analysis to data modulation and filtering: the complex exponential.
The complex exponential describes in compact form an oscillatory behavior with a given frequency and an initial phase; the complex-valued notation is both convenient and practical and is the standard in digital signal processing. The only caveat is that, in discrete time, the concept of frequency becomes a bit tricky because of a phenomenon called "aliasing".
Notes and Supplementary Material
This module follows Chapters 1 and 2 in the reference textbook.
For a beautiful history of information, from the earliest times to contemporary technology, see
James Gleick, "The Information: A History, a Theory, a Flood'' New York: Pantheon Books, 2011.
For a quick introduction on signal processing, digital signal processing and discrete-time signal processing, these Wikipedia pages are a good start:
Signal Processing
Digital Signal Processing
Discrete Signal
Wikipedia has become a widely-referenced resource for Digital Signal Processing. DSP articles on Wikipedia, in some senses, have become a knowledge representation of DSP on the Internet. These articles form an impressive knowledge network worth exploring.
Knowledge network of DSP articles on Wikipedia
Introduction to Module 1.2
In the previous module we have looked at the basics of signal processing and introduced some simple examples by way of intuition. We are now going to set up a proper mathematical framework for the rest of the course.
The way we teach signal processing is a little bit different than usual. The fundamental idea is that we try to express most of the theoretical concepts in terms of linear algebra and vector spaces. While this may seem a little abstract at first, it will pay off handsomely in the end by providing us with very simple proofs of complex results (such as the sampling theorem). While this module may feel a bit dry and "math-y", do bear with us, it's worth the effort!
Introduction to Lesson 1.2.1
In this short introductory lecture we will make the case for using vector spaces in signal processing and provide you with simple intuitive examples of what vector spaces can do for us.
Introduction to Lesson 1.2.2
In these two videos we will first describe the concept of vector space both deductively (by example) and inductively (by enunciating the axioms that regulate vector spaces). We will illustrate the properties that derive from the axiomatic definition of vector space and establish a correspondence between the different classes of discrete-time signals introduced in the previous module and an appropriate vector space.
Introduction to Lesson 1.2.4
Another application of basis vectors in signal processing is in signal approximation and compression. In this lecture we will explore the power of orthogonal projections and approximation for a rather unusual vector space. Although the example is not an instance of discrete-time signal processing, it will hopefully illustrate the power of generalization provided by vector space theory and show that the same concept (dimensionality reduction) can be applied to abstract mathematical objects in the same way we will later apply it to audio or video files.
Notes and Supplementary Material
The current module is based on Chapter 3 in our textbook.
The book shown in the introduction video is a facsimile copy of "Six Books of Euclid", by Oliver Byrne (Taschen). For Euclid's Elements, see wikipedia.org/Euclid_Elements.
For a fun read about thinking in geometrical spaces, there is the all time classic "Flatland: A Romance of Many Dimensions'' , by Edwin Abbott Abbott.
If you would like to dig deeper into Hilbert Spaces, there are many books available. For a free online version with a point of view similar to what is done in this class, we recommend Chapter 2, ''From Euclid to Hilbert'', in ''Foundation of Signal Processing,'' by M.Vetterli, J.Kovacevic and V.K.Goyal, downloadable at http://www.fourierandwavelets.org/. The book is published by Cambridge University Press.
Introduction to Module 1.3
This module is concerned with understanding the frequency domain representation of signals via a tool called Fourier transform. The Fourier transform is a fundamental tool in the arsenal of any engineer and it is used in virtually all scientific domains.
The ancient Greeks and, later on, Arab scientists were intrigued by the rainbow phenomenon and tried in vain to come up with an explanation for it. In 1300, a Dominican monk, Theoderich of Freiberg. held a bottle of water to the sun and recognised the colors of the rainbow, and understood the role of water drops in the phenomenon. It took another 300 years until Descartes and Newton gave a full explanation of how white light can be decomposed into colors. Newton in particular devised a crucial experiment proving once and for all that white light is actually composed of many fundamental frequencies associated to different colors. This was the birth of notion of spectrum.
The main character in the rest of the story is Joseph Fourier, an 19th century French mathematician and physicist. Fourier provided the mathematics to really understand what Descartes and Newton described as physicists. Fourier proposed to decompose any well-behaved function into a sum of harmonic sines and cosines. How this could be done? He wrote long hand into a book called Théorie Analytique de la Chaleur. The reason Fourier was studying this was a physical problem. He wanted to understand the solution to the heat equation and it turns out that sines and cosines are eigenfunctions of the heat equation and therefore represent a very natural basis where to search for a solution of this partial differential equation. The original manuscript looks very complicated but today, thanks to efficient mathematical notation and electronic means to carry out the actual computations, we not only understand this quite easily but use it in everyday life (although, often, we're not even aware of it)
Introduction to Lesson 1.3.1
In this lesson we will talk about Fourier analysis first from an intuitive point of view. We will start by introducing the concept of frequency domain. We will then see that we can use the concept of vector space to explain Fourier analysis as a change of basis in the space of finite-length signals. To this end, we will study the so-called Fourier basis for this space.
Summary of Lesson 1.3.1
Many natural and man-made phenomena exhibit an periodic behavior: after a certain amount of time, called the period, these phenomena repeat exactly. The inverse of the period, that is, the number of repetitions per unit of time, is called the frequency. Sines and cosines, simple oscillatory functions, are natural candidates as the basic building blocks to represent more complicated oscillatory signals. This is the basic goal of Fourier analysis: to decompose a signal in terms of sines and cosines.
We have two kinds of Fourier tools, Fourier analysis and Fourier synthesis. Fourier analysis allows determining the weight of each periodic basic building block in a given signal; with the analysis, we move from the time domain to the frequency domain. Fourier synthesis allows building signals with a "user-defined" frequency content: with this we move from the frequency domain to the time domain.
We have started our exploration of Fourier analysis with the simplest tool, the discrete Fourier transform (DFT) that applies to finite-length signals. If $$N$$ is the length of the signals, we have seen that the set of complex exponentials
$$w_k[n] = e^{j \frac{2\pi}{N} nk}, n=0, …, ˙N-1, k = 0, …, N-1$$
forms an orthogonal basis of $$\mathbb{C}^N.$$ The DFT is simply a change of basis in this vector space.
Introduction to Lesson 1.3.2
In this lesson we will talk about the discrete Fourier transform (DFT) in more details. We will introduce it more formally, we will show some examples and we will show you how to interpret a DFT plot.
Summary of Lesson 1.3.2
In this lesson, we have studied in greater details the discrete Fourier transform (DFT), the Fourier analysis tool for finite-length signals.
The DFT is a simple change of basis. The analysis formula (moving from the time domain to the frequency domain) is given by the inner product of the signal with each of the Fourier basis vectors:
$$\begin{eqnarray} X[k] & = & \langle \mathbf{w}^{(k)}, \mathbf{x} \rangle \\ & = & \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N} nk}\end{eqnarray}.$$
The synthesis formula (moving from the frequency domain to the time domain) is a linear combination of the basis functions, scaled by the coefficients we found in the analysis formula:
$$\begin{eqnarray} x[n] & = & \frac{1}{N} \sum_{k=0}^{N-1} X[k]\mathbf{w}^{(k)} \\ & = & \frac{1}{N} \sum_{k=0}^{N-1} X[k] e^{j \frac{2\pi}{N} nk} \end{eqnarray}$$
In the most general case, the DFT coefficients $$X[k]$$ are complex numbers and thus have a real and imaginary part. In order to interpret these coefficients, it is convenient to represent their magnitude $$|X[k]|$$ and phase $$\angle X[k]$$, wrapped between $$-\pi$$ and $$\pi$$. In a DFT plot, frequencies between $$0$$ and $$N/2$$ (resp. $$N/2$$ and $$N-1$$) correspond to digital frequencies smaller than $$\pi$$ (resp. larger than $$\pi$$), in other words counterclockwise rotations (resp. clockwise rotations). Frequencies close to $$0$$ and $$N-1$$ corresponds to the low frequencies and those close to $$N/2$$ to the high frequencies.
Finally, the DFT of a real signal is symmetric in magnitude, mathematically
$$|X[k]| = |X[N-k]|$$, $$k = 1, …, \lfloor{N/2}\rfloor$$.
Introduction to Lesson 1.3.3
In this lesson we will look at the DFT in practice by showing you some analysis examples. Furthermore we will demonstrate how to label the DFT axes to relate the DFT to real-world quantities such as frequencies in Hertz. We will talk also about DFT synthesis, i.e., how we move from the frequency domain to the time domain.
Summary of Lesson 1.3.3
The DFT can be used as an analysis tool to understand the oscillatory components that make up a signal. If a signal has an associated system clock $$T_s$$ (or a frequency $$F_s = 1/T_s$$), we can map the index $$k$$ of the DFT coefficients to real-world frequencies. The largest digital frequency $$N/2$$ is associated with the largest continuous-time frequency $$F_s/2$$. Thus, the continuous frequency corresponding to index $$k$$ is given by $$\frac{kF_s}{N}$$ and is measured in Hz.
The DFT synthesis can be seen as a series of N sinusoidal generators added together:
sinusoidal generator k has frequency $$2\pi k/N$$
the amplitude of sinusoidal generator $$k$$ is given by the magnitude of the DFT coefficient $$|X[k]|$$
the phase of sinusoidal generator $$k$$ is given by the phase of the DFT coefficients $$\angle X[k]$$
If we let the DFT synthesis run beyond $$N-1$$, we obtain a N-pediodic signal, $$x[n + N] = x[n]$$. Likewise, the analysis formula produces also a $$N$$-periodic series of Fourier coefficients. This fact will be very important when we study another form of Fourier transform for periodic sequences, namely the discrete Fourier series (DFS).
Introduction to Lesson 1.3.4
The STFT is not a new kind of Fourier transform but a clever way of using the DFT to analyse the properties of a signal whose properties evolve over time. We will see why we need this tool by comparing the advantages and disadvantages of the time-domain and of the frequency-domain representations for a signal. The graphical way to represent STFT data is called the spectrogram.
Summary of Lesson 1.3.4
Consider a signal in which frequency components begin and end at different points in time. If we apply a simple DFT on the whole signal, the frequency representation completely obfuscates time information. A solutions to this problem is called the short-time Fourier transform (STFT).
The STFT is nothing more than a repeated application of the DFT to subsequent segments of length $$L$$ of a given signal. In this way we obtain simultaneously time and frequency information. The STFT is visually depicted using a spectrogram, i.e., a plot the of magnitude of the DFT coefficients in dB. The spectrogram is indexed by two quantities, the portion of the signal under scrutiny and the frequency index $$k$$. Various colors are used to represent various magnitudes and darker values corresponds to smaller ones.
When we increase the length $$L$$ of the analysis window we can detect more frequencies, i.e, the resolution in frequency is increased. But, as $$L$$ grows larger, our timing detection is less precise, that is, the resolution in time is decreased. This observation shows a fundamental properties of the STFT: we cannot increase simultaneously time and frequency resolution. There is a fundamental uncertainty principle between time and frequency.
Introduction to Module 1.4
The DFT, which we studied in the previous module, is not only a mathematical analysis formula but also a practical algorithm that we can compute numerically (that is, with a computer) on any given finite-length data set. As such, the DFT is an invaluable tool in all practical signal processing applications.
The DFT, however, covers only one of the possible types of discrete-time signals that we have seen, the finite-length case. In this module we will briefly talk about the DFS, which is a straightforward extension of the DFT to periodic signals, but, more importantly, we will introduce the Fourier analysis tool for infinite-length sequences, the so-called DTFT. This transform, as opposed to the algorithmic DFT, is a purely mathematical tool but one that will allow us to derive general results for all types of signals in the rest of this course.
This module is a bit more abstract and mathematical than the previous ones, but necessary to lay the basis for applications to come such as filtering.
Introduction to Lesson 1.4.1
In the previous module we remarked that, if we let the DFT synthesis run beyond $$N-1$$, we obtain a N-pediodic signal $$x[n + N] = x[n]$$. Likewise, the analysis formula produces also a $$N$$-periodic series of Fourier coefficients. Thus the concept of DFT naturally extends to periodic sequences and we will talk about discrete Fourier series (DFS) in the case of periodic sequences.
Summary of Lesson 1.4.1
The discrete Fourier series is simply a different name for the DFT, when the inherent periodicities are considered explicitly: $$N$$-periodic sequences in the time domain are mapped onto $N$-periodic sequences in the frequency domain. Furthermore, the definition of the DFS retrospectively better justifies the use of circular shifts as the natural extension of shifts for finite-length sequences.
We also remarked that, if we take the DFT of $$L$$ repetitions of a finite length sequence of length $$N$$, we obtain a series which is non-zero only at multiple integers of $$L$$. Moreover, these non zero coefficients are just scaled versions of the DFT coefficients of the original finite-length sequence. Therefore, all the spectral information of an $$N$$-periodic sequence is entirely captured by the DFT coefficients of one period.
Introduction to Lesson 1.4.2
The discrete-time Fourier transform (DTFT) is the Fourier tool of choice for infinite-length sequences. We will look at this tool from an intuitive point of view and then we will formally define it, together with an illustration of its properties. The DTFT can still be seen as a formal change of basis in an appropriate vector space, and this will be illustrated by way of the Dirac delta formalism.
Summary of Lesson 1.4.2
In this lesson, we have studied the Fourier tool of choice for infinite-length sequences, called the discrete-time Fourier transform (DTFT). We have started our journey from an intuitive point of view: as a signal become longer, the fundamental DFT frequencies $$\frac{2\pi}{N}k$$ become denser and denser and we can replace them in the DFT formula with a real-valued frequency $$\omega \in \mathbb{R}$$. This leads to our definition of the DTFT analysis and synthesis formula
$$X(e^{j\omega}) = \sum_{n=-\infty}^{+\infty} x[n]e^{-j\omega n}$$
$$x[n] = \frac{1}{2\pi}\int_{-\infty}^{+\infty} X(e^{j\omega}) e^{j \omega n} d\omega.$$
The DTFT thus maps an infinite length sequence x[n] onto a function of real variable $$\omega$$. The DTFT is $$2\pi$$-periodic and we write $$X(e^{j\omega})$$ to stress this, although the variable is $$\omega$$ only. This is a standard convention in the DTFT literature. Furthermore, by convention, the DTFT is represented on the $$[-\pi, \pi]$$ interval.
Frequencies between $$0$$ and $$\pi$$ (resp. $$-\pi$$ and $$0$$) are the positive (resp. negative) frequencies, corresponding to counterclockwise (resp. clockwise) rotations. Low (resp. high) frequencies are those close to $$0$$ (resp. $$-\pi$$ and $$\pi$$).
The question of the existence is essential. We want to ensure that the sum of the analysis formula does not blow up. It can be shown that the DTFT converges for all square summable sequences.
The DTFT can be interpreted as a change of basis in the space $$\mathbb{C}^{\infty}$$ where the uncountable set of functions $${e^{j\omega n}}_{\omega \in \mathbb{R}}$$ forms an orthogonal basis. This space is not a proper vector space and we need a mathematical trick to reconcile this intuition. We hence introduce the concept of the Dirac delta function $$\delta(t)$$ of real variable t defined by the sifting property
$$\int_{-\infty}^{+\infty} \delta(t - s) f(t) dt = f(s), \forall f(t), t \in \mathbb{R}$$
With this trick, we can define the DTFT for certain interesting non square summable sequences, such as
$$\text{DTFT}(1) = 2\pi \sum_{k=-\infty}^{\infty} \delta(w - 2\pi k)$$.
Introduction to Lesson 1.4.3
In the previous lessons, we have seen how to calculate the spectrum of signals. In most cases this spectrum is mostly limited around a certain range of frequencies. Depending on this range, we can define different types of signals. For example, if most of the energy of a signal is concentrated around zero (resp. $$-\pi$$ or $$+\pi$$) , we call it a lowpass (reps. highpass) signal. If the energy is concentrated somewhere in between we call it a bandpass signal.
Modulation is a method to shift the spectral content of a signal in frequency; for example, we can modulate a lowpass signal (such as voice) into a bandpass signal (such as an AM radio signal): modulation is at the heart of most communications systems. A modulated signal can be demodulated back to its original position in frequency.
For fun, we will also show how modulation can be used to tune a guitar. Maybe you have already done it yourself or you have heard musicians do it on stage. Now you will understand the theory behind it.
Introduction to Lesson 1.4.4
In the first lesson we will look at the mathematical relationships between the DFT, DFS and DTFT. We will see that the DTFT is indeed the most general tool, since we can obtain a DTFT representation of finite-support and periodic signals as well. The interest of this lesson is primarily theoretical. If you like the fine details of the mathematics behind the Fourier transforms, you will probably enjoy it. If not, feel free to skip this lesson with no consequences!
In the second lesson we will look at zero-padding, a technique that is sometimes used to make the DFT "look" better but that reveals no more information about the signal than the original DFT.
Introduction to Lesson 1.4.5
The Fast Fourier Transform is not a new type of Fourier transform but indicates a fast algorithmic technique to numerically compute the DFT of a finite data set. In general, the straightforward DFT computation of a signal of length $$N$$ requires on the order of $$N^2$$ arithmetic operations whereas a good FFT algorithm requires only $$N\log N$$ operations. The availability of fast DFT algorithms was the fundamental game changer in the history of digital signal processing, allowing for more and more complex applications on inexpensive hardware.
In this lesson, we will look at the historical development of fast DFT algorithms and explore in detail a particular type of FFT called "decimation in frequency".
Notes and Supplementary Material
Module 1.30 is based on Chapter 4 of the textbook of the class. If you like the history of science, we can highly recommend James Gleick’s biography of Isaac Newton, where his work in "Opticks" is discussed in historical context (Isaac Newton, Pantheon Books, 2003).
Fourier series, Fourier analysis, and applications of the Fourier transform are the topic of many books in both mathematics and engineering. Below we just mention a selection.
For a historical perspective, the original book by Fourier, ‘’Théorie Analytique de la Chaleur’’, is interesting. One can see how difficult it was, in the early 19th century, to prove properties that now follow easily from Hilbert space geometry (e.g. orthogonality of harmonic sines and cosines).
From an engineering perspective, we recommend the ‘’The Fourier Transform and its Applications’’ by R.Bracewell, McGraw Hill, 2000.
A beautiful book about Fourier analysis is by Thomas Körner, Fourier Analysis, Cambridge University Press, 1988.
For some interesting reads on the algorithmic side of the Fourier Transform you can check the following:
Gauss and the History of the FFT
Homepage of FFTW
c4science · Help