It is a fundamental operation in signal processing, given an LTI system $H$ and input $x[n]$, to find the output $y[n]$. From our study of LTI systems, we have seen that there are several ways to find the output of the system. --One is to find the output $y[n]$ at each time $n$ using the input-output relationship (which defines the out $y[n]$ in terms of the input and output at other various times).--Another option is to take the system matrix $H$ and the input vector $x[n]$ and perform a matrix multiplication $y=Hx$--A final option is to find the output at a given time in terms of a summation involving only the input and the system's impulse response:$y[n] ~=~ \sum_{m=-\infty}^\infty h[n-m]\, x[m]$That final option has a special name: it is the convolution of $x[n]$ and the system impulse response $h[n]$. It also has a special operator symbol, $\ast$, so that the convolution of $x[n]$ and $h[n]$ is expressed as $x[n]\ast h[n]$.
Computing convolution
Given an LTI system's impulse response $h[n]$ and an input $x[n]$, the process of computing the output $y[n]$ via the convolution sum formula ($\sum_{m=-\infty}^\infty h[n-m]\, x[m]$) is straightforward, according to the following steps:--Step 1: decide which of $x$ or $h$ you will flip and shift; you have a choice since $x \ast h = h \ast x$. We will suppose you choose to flip $h$. --Step 2: plot $x[m]$ --Step 3: plot $h[-m]$, the time reversed version of the impulse response --Step 4:~ To compute $y$ at the time point $n$, plot the time-reversed impulse response after it has been shifted to the right (delayed) by $n$ time units: $h[-(m-n)]=h[n-m]$--Step 5: $y[n]=$ the inner product between the signals $x[m]$ and $h[n-m]$(Note: for complex signals, do not complex conjugate the second signal in the inner product) -- Step 6: Repeat for all $n$ of interest (potentially all $n\in Z$)--Step 7: Plot $y[n]$ and perform a reality check to make sure your answer seems reasonableHere we will illustrate convolution by convolving two signals together, $x[n]$ and $h[n]$, plotted below. We will call the result of the convolution $y[n]$, so $y[n]=x[n]\ast h[n]$.
The second and third steps are to plot $x[m]$ and $h[-m]$:
Now step 4 and 5 are to shift $h[n-m]$ by varying $n$ and then computing the inner product between $h[n-m]$ and $x[m]$. For each shift, that inner product will be the value of the output $y[n]$ for that value of $n$. In the figures below, we will see how $h[n-m]$ and $x[m]$ look for each $n$ ($x[m]$ of course will not change), and will progressively build up $y[n]$ as $n$ increases. We'll start with $n=-1$:
So for $n\lt 0$, the dot products of $x[m]$ and $h[n-m]$ are zero, and hence $y[n]$ is zero for these $n$. Now let's consider $n=0$:
The next shift to the right makes $n=1$:
Continuing to shift $h[n-m]$ to the right, we have for $n=2$:
At $n=3$, $h[n-m]$ has moved past the point of maximum alignment; as with $n=1$, the dot product between it and $x[m]$ is $2$:
We're approaching the end of our work on this convolution problem. At $n=4$, $h[n-m]$ has just about moved on past the point of overlapping nonzero values with $x[m]$:
Finally, for $n=5$, there is no nonzero overlap between $x[m]$ and $h[n-m]$, so the dot product is zero. For all $n\gt 5$ (for which $h[n-m]$ moves even farther to the right) this is the case as well:
We have found the dot product between $x[m]$ and $h[n-m]$, and therefore $y[n]$, for all integer values of $n$, so our convolution computation is finished. The final step of the convolution is to examine the plot of $y[n]$ and do a quick "reality check" to make sure the answer is reasonable. At this introductory point, you might not know what to expect a convolution looks like, so it may not be clear if it is reasonable or not. But in time, especially as you understand the "flip and shift" nature of convolution, you will gain a feel for how convolutions should generally look.