Why does filtering work? What enables us to enhance the bass in our audio players?
There is one operation that stands behind it all: convolution.
In order to fully master filtering, be it finite impulse response (FIR) or infinite impulse response (IIR) filtering, one needs to understand the definition, derivation and the properties of the convolution operation very well. That will be the topic of this and a few following articles.
We are going to dig deep into the convolution and we will get to know it so well, that it won’t surprise us any more and we’ll be able to recognize it from afar.
This article outlines the mathematical definition of the convolution and gives you some intuition behind it. In the next article we will introduce some basic properties along with their proofs (told you it’s going to go deep).
Are you ready?
The Convolution Series
- Definition of convolution and intuition behind it
- Mathematical properties of convolution
- Convolution property of Fourier, Laplace, and z-transforms
- Identity element of the convolution
- Star notation of the convolution
- Circular vs. linear convolution
- Fast convolution
- Convolution vs. correlation
- Convolution in MATLAB, NumPy, and SciPy
- Deconvolution: Inverse convolution
- Convolution in probability: Sum of independent random variables
Definition
In its simplest form, the convolution between two discrete-time signals and can be expressed as an infinite sum
Whoa, what’s happened here? Under the sum we have the two signals, but the second one is not only shifted in time by but also time-reversed!
Important assumptions
In order to make this discussion feasible, we must enforce and to have finite energy. A signal is said to have finite energy, if
i. e., is square-summable.
Additionally, we also assume that all considered signals (, etc.) are 0 for negative time indices, i. e., .
Intuition
In order to get an intuition behind the convolution, we should look at it from different perspectives.
Filtering perspective
Let’s consider a generic filter with input , output , and impulse response (Figure 1).
Figure 1. A generic filter.
A filter is a linear time-invariant (LTI) system. From signal processing we know that any LTI system is completely specified by its impulse response . The output of an LTI system is by definition equal to the convolution of the input with the system’s impulse response . That is why the output of an LTI system is called a convolution sum or a superposition sum in case of discrete systems and a convolution integral or a superposition integral in case of continuous systems.
Now, let’s consider again Equation 1 with denoting the filter’s impulse response and denoting the filter’s input signal. We may look at the filter’s output as a weighted sum of filter’s impulse responses. How?
Consider . At the output we get
because and for all . What do we get for ?
As you can see, x[0] has moved “further down the road” (further into the filter’s “buffer”) and now constitutes the weight for of filter’s impulse response. At the same time enters the “buffer” and (as previously) weights . The operation repeats for every following input sample. stops weighting filter’s impulse response when it has weighted its last sample (unless it is an IIR filter which by definition has an infinite impulse response; then, weights the filter’s impulse response infinitely).
Delaying-and-summing perspective
We can also look at that operation from a different perspective. What if we fix in Equation 1? In this case, it describes the output of the system if only input sample was given:
The above equation basically says, that once enters the filter, it will weigh its entire impulse response delayed by samples with respect to . We then just have to sum up over all possible values to conclude that is just filter’s impulse response, delayed and weighted by each sample of .
This may all get a little bit confusing at this moment, so let’s look at an example, shall we?
Example
Let’s consider the following signal of length 4, i. e., consisting of , and
Figure 2. Input signal .
and filter’s impulse response of length 3
Figure 3. Filter’s impulse response .
The result of their convolution is the following signal (filter’s output)
Figure 4. Filter’s output after feeding at the input.
Not very meaningful, is it? The only thing that we can observe is that output’s length is the sum of input’s and filter’s lengths minus one.
Let’s try some color coding. We can depict each of ’s samples in a different color:
Figure 5. Color-coded .
We can now examine the impact of particular samples on the filter’s output. What would happen if only blue entered the filter?
Figure 6. Filter’s response to .
We can see that the entire impulse response of the filter got scaled by which in this case is equal to .
Now, let’s imagine, that only second sample, namely orange , entered the filter. What could we observe at the output?
Figure 7. Filter’s response to .
Notice that at the filter’s output is , because at that time has not yet entered the filter. But from onwards we get again the filter’s impulse response scaled by the newly entering sample.
The same thing happens for green and red
Figure 8. Filter’s response to .
Figure 9. Filter’s response to .
Viewing all these “partial” responses on a plot shows the impact of each individual input sample over time
Figure 10. Overlayed filter’s responses to individual samples of .
Summing them all up (as if summing over in the convolution formula) we obtain:
Figure 11. Summation of signals in Figures 6-9.
what corresponds to the signal above.
Continuous convolution
Convolution is defined for continuous-time signals as well (notice the conventional use of round brackets for non-discrete functions)
Although it may not be as intuitive in interpretation as the discrete convolution, nevertheless, we could try to imagine the continuous case as an infinitely densely sampled discrete signal (so that the sum over discrete samples changes to an integral over continuous functions). But keep in mind that it is only an intuitive view not a mathematically strict interpretation.
Summary
In this article, we introduced the mathematical operation of convolution, gave the justification for its form, and provided a little bit of intuition on how can we view the convolution from different angles. In the next articles we are going to study convolution more closely.
Up next: mathematical properties of convolution!.
Bibliography
[1] Convolution on Wikipedia. Retrieved: 09.03.2021.
[2] Alan V Oppenheim, Ronald W. Schafer Discrete-Time Signal Processing, 3rd Edition, Pearson 2010.
[3] Alan V. Oppenheim, Alan S. Willsky, with S. Hamid Signals and Systems, 2nd Edition, Pearson 1997.
Comments powered by Talkyard.