Homec4science
Diffusion epfl (master) Browse

R2653/teaching/MOOC/refactored/part2.txt
1325afb1aa6emaster

Last Change
Raw File

part2.txt
View Options

Welcome to the second part of the Digital Signal Processing course.
In the first part of this class we concentrated on the concept of signal and on its analysis. We looked at signals, we took them apart and we put them back together. Now it is time to start addressing the second part of the story, the processing part. When we process a signal we no longer simply analyze it, but we manipulate it and we transform it into another signal. There are many ways to skin a cat and probably even more ways to process a signal. But, in this second part of the DSP course, we will look exclusively at a class of algorithms that goes under the name of linear time-invariant filters.
Filters are simple and yet very powerful device that have been around for a very long time especially in analog electronics. To get an intuition of what a filter does, think of the nobs on your stereo with which you boost the bass or dim the treble in the music you listen to. In the digital world filters have the added advantage that they can be implemented very simply on general purpose architectures.
This class contains three modules. In the first we will describe how filters work both in the time domain and in the frequency domain. In the second module we will learn how to design a filter with a certain set of characteristics. Finally, in the last module, we will introduce the concept of stochastic and adaptive signal processing, a very powerful paradigm that allows digital filters to self-modify in order to better match the characteristics of their input.
This class corresponds to Chapters 5 to 7 in the reference textbook but we will skip some of the technicalities. Also remember that everything we do in this class you can implement in your numerical package of choice and apply it to your favorite signals!
This is a rather long module since not only do we need to define the filtering paradigm but then we also need to understand how to implement and design filters that do what we want them to do. And in spite of the length, this module only scratches the surface of the world of active signal processing. We will leave for future classes the concepts of adaptive signal processing or nonlinear signal processing but I am sure this module will wet your appetite with respect to everything that you can do in the world of digital signal processing.
The module is structured like this. The three first lessons will concentrate on the concept of filter and we will characterise a filter in the time domain. We will illustrate the key points using the mock problem where we try to remove noise from an otherwise smooth signal. By now, we now the time domain is always only half of the picture and we will spend the following lessons to extend the paradigm of filter in the frequency domain. This will allow us to define a class of filters called ideals filters that represent really the best filter that we can think of. Unfortunately, ideal filters turn out to be too good to be true so we will spend Lessons 2.1.6 until 2.1.10 to explore the kind of filters that we can implement and design in practice. At first we will try to mimic ideal filters but the method we will show is limited very soon. So we will introduce a new tool called the z-transform that will allow us to explore the full range of filters that we can design and implement.
Introduction to Lesson 2.1.1
We will first examine the two key properties of filters which are linearity and time invariance. These two properties are enough to define the fundamental mode of operation of filters, namely, the convolution of the input with an impulse response that characterizes the filter.
Summary of Lesson 2.1.1
In this lesson we have studied a special class of processing devices called linear time-invariant (LTI) filters. As the name indicates, these systems are characterized by two properties:
linearity: the output of a linear combination of inputs is equal to the linear combination of the outputs
time-invariance: the system behaves in exactly the same way independently of when it is being switched on.
These are very reasonable assumptions to make in practice and, as we will see, there is already a large set of processing methods that falls under this category.
LTI filters are entirely characterized by their impulse response, i.e., their response to the delta sequence $$\delta[n]$$. From the impulse response $$h[n]$$, the output of an LTI filter $$y[n]$$ can be computed by convolving the input $$x[n]$$ with the impulse response,
$$y[n] = \sum_{k=-\infty}^{\infty} x[k] h[n-k]$$.
Introduction to Lesson 2.1.2
In the previous lesson we introduced the concept of filtering and that of convolution but we did not say much about the kind of applications that can be achieved with linear filters. In this module we will see some filtering in action by setting up a mock problem where we try to remove noise from an otherwise smooth signal. The two characters that we will introduce in this lesson are two friends that will remain with us for a very long time, the moving average filter and the leaky integrator.
Summary of Lesson 2.1.2
In this lesson we have studied two examples of LTI filters, the moving average and the leaky integrator. The moving average is a local average computed over the last $$M$$ observations, including the current one.
From a simple recursive formula to compute the moving average efficiently we derived the leaky integrator: as $$M$$ becomes large the filter becomes defined by a time-invariant recursion. The basic idea is to add a portion $$\lambda$$ of the past accumulated values so far and a fraction $$1 - \lambda$$ of the current observation. By setting the value of $$\lambda$$ less than 1, we ensure the system never blows up.
Introduction to Lesson 2.1.3
We will now examine the problem of filter stability and also draw a first classification of filters based on their properties in the time domain.
Summary of Lesson 2.1.3
We have started this lesson with a classification of LTI filters based on their impulse response: finite impulse response (FIR) and infinite impulse response filters (IIR). Another time-domain property of filters is causality, when the output only depends on past values of the inputs and past values of the outputs. A filter is causal if its impulse response is zero for negative values of $$n$$.
We have also defined the notion of bounded input bounded output (BIBO) stability: the output of a bounded input is bounded. We have also seen that a necessary and sufficient condition for stability is that the impulse response is absolutely summable. As a consequence, FIR filters are always stable. Later in this module, we will study other indirect techniques to assess the stability of an IIR filter.
Introduction to Lesson 2.1.4
By now, we now that in signal processing the time domain is always only half of the picture. The time has come to look at filters from the frequency domain perspective and the starting point is this amazing result: if you take a complex exponential and process it with a linear time-invariant filter what you get at the output is a complex exponential at the same frequency as the input. Only the phase and the amplitude may have changed. This has all sorts of interesting implications when we consider the Fourier representation of the elements involved in the filtering operation. We will derive what is called the frequency response of a filter. We will also revisit our friends, the moving average, the leaky integrator and even the Karplus-Strong algorithm to see how they fare in frequency.
Summary of Lesson 2.1.4
We have started this lesson with a remarkable result: complex exponentials are eigensequences of LTI filters. This means that when we input a complex exponential at a given frequency in a LTI filter, what we get at the output is a complex exponential at the same frequency; only its magnitude and/or phase may have changed.
A direct consequence of this property is the so-called convolution theorem: for any input $$x[n]$$, the DTFT of the output signal is equal to the product of the DTFT of the input and the DTFT of the filter impulse response. The latter is called the frequency response of a filter. To understand the behavior of a filter, the frequency response, a complex function of the frequency in general, is typically decomposed into
a magnitude term: where does the filter amplify/attenuate
a phase term: delay and change of shape.
A filter whose frequency response can be expressed as the product of a real amplitude and a pure complex exponential is called a linear phase filter. In a linear phase filter we need only concern ourselves with the magnitude response because the phase term corresponds to a simple delay. As an example, the moving average filter is linear phase.
Introduction to Lesson 2.1.5
In the previous lesson we have made our acquaintance with the frequency response and the latter leads to a natural classification of filters according to which frequency bands they attenuate or they boost. For example, a low pass filter will be a filter that lets only the low frequencies go through and kills high frequencies. Vice-versa, a highpass filter lets high frequencies go through and attenuates low frequencies.
After we have developed this classification of filters as lowpass, highpass and passband, the natural question that arises is what is the best filter in each category that we can think of. In this lesson, we will introduce the family of so-called ideal filters. These filters are ideal in a platonic sense: they can be imagined and described but we cannot implement them in practice. Nevertheless they will remain the paradigm that we will try to get as close as possible in our real-world filter design problems.
Summary to Lesson 2.1.5
We have started this lesson with a filter classification based on the magnitude response: lowpass filters let low frequencies go through and kill high frequencies; the opposite is true for highpass filters. A bandpass filter is a filter that lets a certain range of frequency go through and a allpass filter has constant magnitude over all frequencies.
We have studied the ideal lowpass filter, in some sense the best lowpass filter we can think of. Its frequency response is characterised by
a passband centered around zero with cutoff frequency $$\omega_c$$
an infinite attenuation in the stop band
no phase term (aka no delay).
Its corresponding impulse response is a sinc function whose support is two-sided and infinite length. Because of this it is not possible to implement this filter with a finite number of operations. This is the reason why we call this filter ideal and we will spend the following lessons trying to derive good approximations. Furthermore, from the ideal lowpass filters, we have also derived ideal highpass and bandpass filters.
We have concluded this lesson by revisiting the demodulation problem. When we demodulate a signal, we multiply it by a cosine of the same carrier frequency and subsequently apply a lowpass filter to get rid off the spurious high frequency components.
Introduction to Module 2.2
The subject of this module is filter design, that is, the ability to determine the algorithmic parameters of a filter from a set of engineering specifications with respect to a desired frequency response. Abstract requirements on the filter's characteristics have led us to ideal filters in the previous module, but we have seen that these filters cannot be implemented in practice.
In this module we will abandon the abstract requirements of the previous module and introduce target specifications with tolerances. For the design strategy, at first we will try to mimic ideal filters but the method will show its limitations very soon. So we will introduce a new tool called the z-transform that will allow us to explore the full range of filters that we can design and implement.
Introduction to Basic Filter Design
The first filter design strategy that we will explore be that of imitation, that is, we will try to replicate the structure of either the impulse response or the frequency response of ideal filters. In this lesson, we will see three fundamental methods to approximate ideal filters, impulse truncation, the window method and frequency sampling.
Although limited, these strategies remain a very good "back of the envelope" method to quickly prototype digital filters and can be used in the initial phase of a project before moving on to more sophisticated design methods.
Summary of Lesson 2.2.1
In this lesson, we have studied different methods to approximate an ideal filter.
The first method is called impulse truncation: we simply truncate the filter impulse response over a finite set of $$N$$ points, centered around zero. While, it seems like a good idea in the first place, as this method minimises the mean squared error between the ideal and the approximate filter, this method suffers from an important limitation known as Gibbs phenomenon. The maximum error around the transition band cannot be made arbitrarily small, even when we increase the number of points $$N$$.
The impulse truncation can be interpreted as the product of the ideal filter response and a rectangular window of $$N$$ points. From the modulation theorem, the DTFT of the product of two signals is equivalent to the convolution of their DTFTs. Hence, the choice of window influences the quality of the approximation results. The window method is just a generalization of the impulse truncation method where we use a different window shape. For example, by using a triangular window, we reduce the Gibbs error at the price of a longer transition.
The third approximation we have studied is called frequency sampling: we sample the impulse of the ideal filter in the frequency domain and obtain the impulse response of the filter by computing the IDFT of these samples. Again, this method does not allow to control the maximum error in the passband and/or the stopband.
Introduction to Lesson 2.1.7
In the first lesson on filter design we took a very intuitive approach and we quickly realized a series of drawbacks, mostly in the sense that not all parameters of the resulting filters were under our control. Before we study more sophisticated methods, however, we need to take a step back and answer a fundamental question: what is the largest class of realizable filters that we can implement?
We know that, in order to have a linear time-invariant system we need to have a system described by a linear combination of past input and output values scaled by constants. We call this a constant coefficient difference equation (CCDE). A CCDE is very complicated and cumbersome to manipulate in the raw. In this lesson, we will introduce a new tool called the z-transform that will greatly simply the task. With the z-transform, we will arrive at a new characterization of a filter in terms of what we call a rational transfer function, which is simply a ratio of polynomials. With this, filter design will become a polynomial fitting problem.
Summary of Lesson 2.1.7
We have started this lesson by recalling that a linear time-invariant system can only contain the following operations: additions, delays and multiplications by a constant. Moreover, if a LTI system is causal, its output is a linear function of past values of the input and past values of the output. Such systems can be represented in the time domain by a constant coefficient difference equation (CCDE).
We have then introduced a handy mathematical tool to represent LTI systems, the z-transform. It is defined as a power series $$X(z) = \sum_{n=-\infty}^{\infty} x[n] z^{-n}$$ that maps a discrete-time sequence $$x[n]$$ onto a function of the complex variable $$z$$. The z-transform is an extension of the DTFT to the whole complex plane and is equal to the DTFT for $$z=e^{j\omega}$$. In the z-domain, a CCDE is represented as a ratio $$H(z)$$ of two polynomials of $$z^{-1}$$ and the frequency response of a filter is equal to this transfer function evaluated at $$z=e^{j\omega}$$.
We have also studied conditions for convergence of the z-transform. In summary, we have seen that
the zeros (resp. the poles) are the roots of the numerator (resp. denominator) of the rational transfer function
the region of convergence is only determined by the magnitude of the poles
the z-transform of a causal LTI system extends outwards from the largest magnitude pole
an LTI system is stable if its region of convergence includes the unit circle.
This last condition in particular offers a simple method to study the stability of LTI systems.
Introduction to Lesson 2.1.8
In this lesson, we will talk about how to design a filter based only on the intuitive properties of its transfer function. This pedagogical lesson will show you several simple IIR filters whose properties can be easily derived based solely on the position of the poles and zeros in the associated transfer function.
Summary of Lesson 2.1.8
In this lesson, we have derived simple filters from known structures. In general, with a low order systems, it is possible to analyse and predict their characteristics from their poles zeros plot. Furthermore, to obtain a real filter, poles and zeros are added in complex conjugate pairs.
More specially, we have studied the following filters:
the resonator that selects one specific frequency $$\omega_0$$. It is derived by shifting the passband of a leaky integrator to $$\omega_0$$.
the DC notch that removes the direct current component. It contains a zero at $$z=1$$ (i.e. $$\omega = 0$$) and a pole at $$\lambda < 1$$.
the hum removal that removes a specific frequency $$\omega_0$$. It is a DC notch whose stopband is shifted to a particular frequency $$\omega_0$$.
Introduction to Lesson 2.1.9
In this lesson, we will briefly look at the major filter design techniques available to engineers today. We will start by reviewing what we mean by filter specifications and then we will briefly describe IIR and FIR filter design techniques.
We will not go into the gory details on how the transfer function coefficients are actually computed; this is the job of numerical packages that are currently available in most programming language or numerical toolbox. The idea for this lesson is to give you a map to navigate the various possibilities that will be available to you when you tackle a signal processing project.
An exception will be made for the Parks-McClellan optimal filter design algorithm, for which a detailed Python notebook is available in this module.
Summary of Lesson 2.1.9
A filter design problem starts from a set of filter specifications
what is the desired frequency response of the filter, what are the passband(s) and stopband(s)?
what are the desired phase characteristics?
what are the limits in terms of computation and/or precision?
Typically, we are interested in realizable filters. To depart from ideal filter characteristics we also specify
a transition band, ie, a range of frequencies between passband and stopband where the filter impulse response can transition freely
tolerance bands for the error in passband and stopband. In particular an equiripple filter is one where the error oscillates within this transition bands equally.
From these filters specification, the aim is to design a filter (either IIR or FIR), i.e., determine the following parameters:
the order of the polynomials $$N$$ and $$M$$ in the transfer function
the coefficients $$a_k$$ and $$b_k$$ in numerator and denominator of the transfer function
IIR design are adaptations of well-established methods in analog filter design. The routines to compute the transfer function coefficients in a digital implementation are available in most numerical packages. From the specs, a first filter is computed with a certain order $$N$$. Then the filter is tested to verify that it meets the desired requirements. If it is not the case, the procedure is run again either increasing the order or relaxing the stringency of the specifications.
FIR filters only exists in discrete time. In FIR filter design, we only have to determine the coefficients of one polynomial, since there are no poles in the transfer function. In the 70’s Parks and McClellan have devised a procedure to compute an optimal linear phase and equiripple FIR from a list of specifications (frequency response and ratio of maximum equiripple error between the passband and the stopband). This procedure is optimal in the minimax sense as it minimizes the maximum error.
With these methods, we have only scratched the surface of the topic and hopefully this review will you a map to navigate the various possibilities that will be available to you when you tackle a signal processing project.
Introduction to Lesson 2.2.5
In this lesson we will briefly look at some implementation issues with respect to digital filters. We can very easily "code" a CCDE in our favorite programming language, since the CCDE is itself a discrete-time algorithm containing only multiplications, additions and delays. Perhaps more interestingly, we can represent CCDE graphically using block diagrams, which we have already used informally in the first part of this course (remember the Karplus-Strong algorithm?) Block diagrams allow us to think of the algorithmic structure in different way and even perform language-independent optimization on the filter structure.
When implementing filters for real-time applications, the efficiency of the implementation is paramount. We will touch briefly on the constraints inherent to real-time processing and look at how general-purpose hardware such as your PC ferries the data from the real world and back.
Module 2.1: Notes and External Ressources
Filter design is a vast domain (to say the least), with inescapable ties to analog circuits and discrete electronics. At the same time, the fundamentals have been codified quite some time ago, so that there are some cornerstone references that one can turn to with confidence. A couple of textbooks that have passed the test of time with flying colors are:
Discrete-Time Signal Processing by A. V. Oppenheim and R. W. Schafer
Theory and Application of Digital Signal Processing by Rabiner and Gold
For a high-level review more in tune with the concepts and language used in this class, please download the free textbook "Foundations of Signal Processing" by M.Vetterli, J.Kovacevic and V. K. Goyal. Section 6.2.6 is particularly relevant.
Alternatively, a quick search on the internet will lead you to countless pages dedicated to filtering examples and filter design. Try it out but don't come back complaining if you end up spending too much time browsing all those cute examples!
Introduction to Module 2.3
In the previous modules we implicitly considered all signals and systems as known and deterministic, in the sense that they could either be expressed in closed form (e.g., $$x[n] = \lambda^n\,u[n]$$) or that they could be exactly described in terms of their samples or their CCDE coefficients, respectively.
In practice, however, this is almost never the case: although we can certainly acquire some knowledge on the general properties of a signal or of a system, it's very rare to know exactly their mathematical representation; in a sense, if we knew signal and systems exactly, we would never require any processing at the sample level at all, since all the information would be fully contained in the analytic description.It is therefore common to assume that in real-world signal processing, all signals at least contain a random component.
In this module we will extend our discrete-time signal processing toolbox to include random quantities and statistical estimation procedures. The approach will be purely data-driven in the sense that we will not make hypotheses on the precise statistical properties of the data but we will concern ourselves only with the minimization of a quadratic error measure.
We will see that this only requires the estimation of the data's autocorrelation, which can be done reliably even with limited datasets. The autocorrelation, which is in essence a self inner product, that is, a measure of self-similarity, is the fundamental operation that brings to the fore, if present at all, the inner structure and patterns in random signals.
In this module we will examine the two key subjects of statistical signal processing, namely, spectral estimation and adaptive filtering. The framework will be useful later on as well, in the context of quantization and data communications.
Introduction to Lecture 2.3.1
In the next lectures we will start with a quick overview of the key concepts in probability theory since we will need objects like random variables to properly describe the concept of stochastic process. For us, a stochastic (or random) process is the generic output of a stochastic system, namely, a system whose internals are not entirely known or predictable. As observers, we can look at one or (hopefully) more realizations of the process: a realization is the outcome of "running the system" for a given amount of time.
We will try to make our life simpler by assuming that our random systems are well behaved; this is formalized by the concept of Wide-Sense Stationarity, which is the stochastic equivalent of time invariance in deterministic systems. For WSS processes, we can derive two important results.
The first, is that we can characterize WSS processes in the frequency domain by way of a representation called the Power Spectral Density; this is the equivalent of the DTFT for stochastic processes, although some important differences exist.
Secondly, we can use standard LTI filters on stochastic processes as well, and the spectral properties of these filters carry on to the stochastic domain as well. This, in a nutshell, is what stochastic signal processing is all about: our deterministic tools still work with random signals.
What have we learned?
A discrete-time random signal $$x[n]$$ (that is, a collection of random variable indexed by an integer $$n$$) is said to be wide-sense stationary if the mean of each random variable is the same and if the autocorrelation is dependent only on the time lag:
$$\mbox{E}[x[n]x[m]] = r_x[m-n]$$
For WSS processes, we can derive a spectral representation that shows the expected distribution of power in frequency; this is obtained as the DTFT of the autocorrelation of the process and is called the Power Spectral Density:
$$P_x(e^{j\omega}) = \sum_{k = -\infty}^{\infty} r_x[k]\, e^{-j\omega k}.$$
A special class of WSS processes is white noise, for which the PSD is constant and equal to the variance of the process.
If we filter a WSS processes, the output is itself WSS. The stochastic equivalent of the convolution theorem links the input and output PSD's as
$$P_y(e^{j\omega}) = \bigl| H(e^{j\omega}) \bigr|^2 P_x(e^{j\omega})$$
In other words, the magnitude response of a filter preserves its properties in the case of random processes.
Introduction to Lecture 2.3.2
The question at the heart of adaptive signal processing is whether we can design a digital system that, when processing an unknown signal, can ``self-adapt'' to the input's properties in order to perform a certain task. For example, communication systems almost always have to operate over channels with unknown characteristics and unknown noise sources; a receiver's first task is trying to undo as much as possible the unwanted effects of the channel and produce a "clean" estimate of the original transmitted signal.
Adaptive system work by adjusting their internal parameters in a way that minimizes a well-chosen error measure. In this lecture we will consider the simple yet powerful case of systems that minimize the Mean Square Error between their output and a target goal. We will see two implementations, a one-shot solution that can be used with stationary signals and a time-varying adaptation algorithm that is used in practice to track signals whose characteristics change slowly over time.
Adaptive filters are arguably one of the biggest success stories of digital signal processing; adaptation, in the analog domain, is exceedingly difficult to perform properly but in the digital domain the same general purpose architecture that performs the processing is also performing the math associated to the adaptation, so that no complex hardware is required. The incredible success of digital communication systems is due primarily to the ease with which we can build adaptive signal processing systems.
What have we learned?
We studied two situations where we want to design a filter $$h[n]$$ so that, if $$x[n]$$ is a stochastic input signal and $$d[n]$$ is a desired output, the error
$$ e[n] = d[n] - \sum_{k=0}^{N-1}h[k]x[n-k] $$
is small. The minimization of the error is performed on its Mean Square value, $$J = \mbox{E}[|e[n]|^2]$$; this quadratic cost function is convenient both practically (it minimizes the energy of the error) and mathematically (the error surface has a unique minimum).
When the signals are stationary, the coefficients for the optimal filter can be found from the values of the autocorrelation of $$x[n]$$ and the cross-correlation between $$x[n]$$ and $$d[n]$$. Both correlations are deterministic sequences so that the values for $$h[n]$$ can be found by solving a standard system of equations. The structure of the associated matrix is such that fast algorithms have been designed for the task. The resulting filter is called the Optimal Least Squares filter.
In many practical applications, random signals can only be considered locally stationary, in the sense that their statistical properties change slowly in time. In this case, a global solution would not work efficiently. The alternative is to adapt the filter coefficients so that they track the changes in the input signal. To this end, we can first cast the Optimal Least Squares algorithm in iterative form, a technique known as steepest descent. The next step is to replace the expected value of the error in the iteration by its instantaneous value; this drastic simplification leads to the so-called LMS algorithm:
$$e[n] = d[n] - \mathbf{h}_n^T\mathbf{x}_n $$
$$\mathbf{h}_{n+1} = \mathbf{h}_n + \alpha_n\, e[n] \, \mathbf{x}_n $$
Although simple, the LMS adaptation is extremely effective and one of the most common adaptive technique in use today.
Notes and Supplementary Material
A classic reference on random processes with a good primer on probability theory is E. Parzen's Stochastic Processes, (Dover, 2015) although the focus is primarily on continuous-time processes. For a discrete-time approach to optimal filtering see also P.M. Clarkson's Optimal and Adaptive Signal Processing (CRC Press, 1993).
Quite problematically, however, it seems to be very difficult to accurately quantify the performance of adaptive systems other than in rather simple ``textbook'' cases in which the assumptions on the signals involved are far from realistic (see the infamous independence assumption in analyzing the LMS filter). In adaptive filtering and adaptive signal processing in general, the experimental approach seems to be the most important driving force -- a trend mirrored by recent astonishing (if unexplained) results in deep learning research. Interestingly, the update algorithm for most types of neural network is, in essence, the stochastic gradient descent used in the LMS algorithm; and it's a perhaps not so surprising twist that B. Widrow, the inventor of LMS, has also been one of the pioneers in the first wave of research in artificial neural networks in the mid 1960s!
c4science · Help