Understanding convolution is the biggest test DSP learners face. After knowing about what a system is, its types and its impulse response, one wonders if there is any method through which an output signal of a system can be determined for a given input signal. Convolution is the answer to that question, provided that the system is linear and time-invariant (LTI).
We start with real signals and LTI systems with real impulse responses. The case of complex signals and systems will be discussed later.
Convolution of Real Signals
Assume that we have an arbitrary signal . Then, can be decomposed into a scaled sum of shifted unit impulses through the following reasoning. Multiply with a unit impulse shifted by samples as . Since is equal to 0 everywhere except at , this would multiply all values of by 0 when is not equal to and by 1 when is equal to . So the resulting sequence will have an impulse at with its value equal to . This process is clearly illustrated in Figure below.
This can be mathematically written as
Repeating the same procedure with a different delay gives
In summary, the above equation states that can be written as a summation of scaled unit impulses, where each unit impulse has an amplitude . An example of such a summation is shown in Figure below.
Consider what happens when it is given as an input to an LTI system with an impulse response .
This leads to an input-output sequence as
During the above procedure, we have worked out the famous convolution equation that describes the output for an input to an LTI system with impulse response :
This can be verified by plugging in Eq (2) which yields and hence .
Remember that although both convolution and conjugate of a signal defined in the article about complex numbers are denoted by an , the difference is always visible in the context. When used for convolution, it appears as an operator between two signals, e.g., . On the other hand, when used for conjugation, it appears as a superscript of a signal, e.g., .
Convolution is a very logical and simple process but many DSP learners can find it confusing due to the way it is explained. As we did in transforming a signal, we will describe a conventional method and another more intuitive approach.
Most textbooks after defining the convolution equation suggest its implementation through the following steps. For every individual time shift ,
[Flip] Arranging the equation as , consider the impulse response as a function of variable , flip about to obtain .
[Shift] To obtain for time shift , shift by units to the right for positive and left for negative .
[Multiply] Point-wise multiply the sequence by sequence to obtain a product sequence .
[Sum] Sum all the values of the above product sequence to obtain the convolution output at time .
[Repeat] Repeat the above steps for every possible value of .
An example of convolution between two signals and is shown in Figure below, where the result is shown for each .
Note a change in signal representation above. The actual signals and are a function of time index but the convolution equation denotes both of these signals with time index . On the other hand, is used to represent the time shift of before multiplying it with point-wise. The output is a function of time index , which was that shift applied to .
Next, we turn to the more intuitive method where flipping a signal is not required.
There is another method to understand convolution. In fact, it is built on the derivation of convolution equation (Eq 2)), i.e., find the output as
Let us solve the same example as in the above Figure, where and . This is shown in Table below.
Such a method is illustrated in Figure below. From an implementation point of view, there is no difference between both methods.
The Curious Case of Benjamin Button was a 2008 American film based on a remarkable account of a man living his life in reverse. He was born an old man and got younger with time until he became an infant at his death.
Running the impulse response backwards in time to perform convolution reminds me of that story. Instead of a curious case, it has been an interesting convention in DSP history to regard convolution between two signals as the flipped version of one signal sliding over the other. The textbooks have justified it as a necessary mathematical trick for finding LTI system response, thus creating confusion for students and new learners of DSP.
As we saw from the intuitive method above, flipping is essentially not there at all. Flipping only occurs in the universe of time index , not in the universe of time index . And it is at each where we are finding every new output.
To further understand everything in terms of time index , consider the following quote:
"Nothing has happened in the past; it happened in the Now. Nothing will ever happen in the future; it will happen in the Now."
One can infer from the above quote — buried in mathematical details of convolution — is that the NOW, represented by in convolution equation , is itself a moving pointer which actually keeps changing during the process. Time ticks and with each passing tick, we are able to access one unit into the future where a new input comes and kicks out another impulse response (scaled by input amplitude at that instant) from the system.
Since no practical input can be applied before the NOW, let us start from time index .
- The input contributes in the NOW, which becomes the first output sample at time . It actually sets in motion the complete impulse response scaled by its value (, , ) but those will occur in the future.
- The new NOW is time index . Input arrives and launches a complete impulse response of its own, but only happens in the NOW. Also, having moved unit into the future implies has arrived at this time. So the output at time is .
- Continuing in this way, it can be seen that during the convolution operation, the NOW advances with every tick. Each such activates a new impulse response which of course starts with , and hence the expression . Only those contributions from past inputs can be summed here which contribute in the present moment. Obviously, will be the contribution from an input occurring at time , from , and so on. The input contributes in the NOW, while sends into the future to arrive time units later.
In summary, the argument of is nothing but a length of time separation of every individual input from the NOW (time index ) — owing to this memory, it acts to find out the effect of every past input into the NOW.
Some important properties of convolution are as below.
Since a single unit impulse can only generate a single instance of impulse response , convolution of an impulse response by a unit impulse is the impulse response itself. This result is general and holds for any signal .
Significance of Complex Sinusoids
In a previous article about frequency response, we raised two questions about the frequency domain output for a unit impulse input and significance of complex sinusoids. To investigate these questions, let us excite an LTI system with a real impulse response (i.e., ) by an input complex sinusoid with
where is an arbitrary discrete frequency in the range as detailed in the post on discrete frequency. The output is given by convolution of the input and system impulse response as
where the last equality resulted from Eq (4). The and components of the output are then expressed as
Expanding by identities and ,
For a real from this Eq where ,
From this Eq, the above equation can clearly be seen as a product between and input complex sinusoid as
A similar result holds for a complex impulse response. There can be a possibility of confusion regarding above Eq as how a time domain signal can get multiplied with a frequency domain signal . This is not what the equation says. Actually, is not an arbitrary input signal here. It is a specific complex sinusoid with discrete frequency . All the equation says is that if given as an input, the same complex sinusoid appears at the output scaled by the system frequency response at discrete frequency . Explicitly,
The significant conclusion from the above equation is that the output response of an LTI system to a complex sinusoid at its input is nothing but the same complex sinusoid at the same frequency but with different amplitude and phase. The following note answers the questions asked at the start of this article.
Since output of an LTI system to a complex sinusoid is the same complex sinusoid but with altered amplitude and phase, to find out how an LTI system responds in frequency domain, the most logical method is to probe the system at its input with a complex sinusoid at every possible frequency. This implies forming an input signal with complex sinusoids of equal magnitudes. In this manner, the output amplitudes and phases at all available frequency bins are examined and checked how a system deals with each possible complex sinusoid. The magnitude and phase of the frequency response are called magnitude response and phase response, respectively.
It can also be concluded from the above discussion that impulse response in time domain and frequency response in frequency domain are two equivalent descriptions of a system.
Convolution of Complex Signals
Convolution between a complex signal input to a system with complex impulse response can be understood through writing Eq (2) in form. It is defined in a similar manner as
and can be decomposed as in this Eq,
Due to the identity , a negative sign in expression indicates that phases of the two aligned-axes terms are actually adding together. Obviously, the identity applies in above equations only if magnitude can be extracted as common term, but the concept of phase-alignment still holds. Similarly, the identity implies that phases of the two cross-axes terms are also adding together in expression. Hence, a complex convolution can be described as a process that
- computes real convolutions: , , and
- adds by phase aligning the aligned-axes convolutions ( – ) to obtain the component
- adds the cross-axes convolutions ( + ) to obtain the component.
These computations are shown in Figure below.
Convolution and Frequency Domain
After understanding convolution both intuitively and mathematically, we want to see the interpretation of this process in frequency domain. Specifically, what is the DFT of ? To answer this question, we want to apply the DFT definition to the result of Eq (2). However, we saw in the article about Discrete Fourier Transform that the way both time and frequency domain sequences are defined within a range , DFT works with circular shift which appears due to the inherent periodicity arising from sampling in frequency domain. That leads us to circular convolution.
Circular convolution between two signals, denoted by , is very similar to regular convolution except that the flipping and time shifts are circular as explained in the post about transforming a signal.
Let us compute the DFT of the resultant signal. We focus on real signals as the derivation for complex signals is similar. Since is a real signal in our case, and , and the component in frequency domain from DFT definition can be expressed as
Using the identities ,
The above equation can be rearranged as
Since both and are real for the purpose of this derivation, and while a similar identity holds for ,
A similar computation for component yields
Therefore, we arrive at an extremely important result that is widely utilized in most DSP applications.
The above relation is true for both real and complex signals.
The above finding is actually proved for regular convolution through continuous signals. Since we limit ourselves to discrete domain here, we deal with circular convolution and corresponding DFT only.
The following points sum up what we have learned above so far.
- Convolution tells us how an LTI system behaves in response to a particular input.
- Convolution in time domain induces sample-by-sample multiplication in frequency domain.
- Thanks to intuitive method above, we can say that convolution is also multiplication in time domain (and flipping the signal is not necessary), except the fact that this time domain multiplication involves memory.