Flipping the impulse response in convolution

During convolution on a signal, why do we need to flip the impulse response during the process?

• The latter half of this answer might help you understand. – Dilip Sarwate Nov 14 '12 at 23:16
• In addition to reading @DilipSarwate's great answer it's a good exercise to take a sheet of paper and to calculate the output of an LTI system graphically by adding up time-shifted and scaled versions of the impulse response. – Deve Nov 15 '12 at 9:15
• Note that you can flip either argument - the result is the same. – wakjah Nov 28 '12 at 22:23

Adapted from an answer to a different question (as mentioned in a comment) in the hope that this question will not get thrown up repeatedly by Community Wiki as one of the Top Questions....

There is no "flipping" of the impulse response by a linear (time-invariant) system. The output of a linear time-invariant system is the sum of scaled and time-delayed versions of the impulse response, not the "flipped" impulse response.

We break down the input signal $x$ into a sum of scaled unit pulse signals. The system response to the unit pulse signal $\cdots, ~0, ~0, ~1, ~0, ~0, \cdots$ is the impulse response or pulse response $$h[0], ~h[1], \cdots, ~h[n], \cdots$$ and so by the scaling property the single input value $x[0]$, or, if you prefer $$x[0](\cdots, ~0, ~0, ~1, ~0,~ 0, \cdots) = \cdots ~0, ~0, ~x[0], ~0, ~0, \cdots$$ creates a response $$x[0]h[0], ~~x[0]h[1], \cdots, ~~x[0]h[n], \cdots$$

Similarly, the single input value $x[1]$ or creates $$x[1](\cdots, ~0, ~0, ~0, ~1,~ 0, \cdots) = \cdots ~0, ~0, ~0, ~x[1], ~0, \cdots$$ creates a response $$0, x[1]h[0], ~~x[1]h[1], \cdots, ~~x[1]h[n-1], x[1]h[n] \cdots$$ Notice the delay in the response to $x[1]$. We can continue further in this vein, but it is best to switch to a more tabular form and show the various outputs aligned properly in time. We have $$\begin{array}{l|l|l|l|l|l|l|l} \text{time} \to & 0 &1 &2 & \cdots & n & n+1 & \cdots \\ \hline x[0] & x[0]h[0] &x[0]h[1] &x[0]h[2] & \cdots &x[0]h[n] & x[0]h[n+1] & \cdots\\ \hline x[1] & 0 & x[1]h[0] &x[1]h[1] & \cdots &x[1]h[n-1] & x[1]h[n] & \cdots\\ \hline x[2] & 0 & 0 &x[2]h[0] & \cdots &x[2]h[n-2] & x[2]h[n-1] & \cdots\\ \hline \vdots & \vdots & \vdots & \vdots & \ddots & \\ \hline x[m] & 0 &0 & 0 & \cdots & x[m]h[n-m] & x[m]h[n-m+1] & \cdots \\ \hline \vdots & \vdots & \vdots & \vdots & \ddots \end{array}$$ The rows in the above array are precisely the scaled and delayed versions of the impulse response that add up to the response $y$ to input signal $x$. But if you ask a more specific question such as

What is the output at time $n$?

then you can get the answer by summing the $n$-th column to get \begin{align*} y[n] &= x[0]h[n] + x[1]h[n-1] + x[2]h[n-2] + \cdots + x[m]h[n-m] + \cdots\\ &= \sum_{m=0}^{\infty} x[m]h[n-m], \end{align*} the beloved convolution formula that befuddles generations of students because the impulse response seems to be "flipped over" or running backwards in time. But, what people seem to forget is that instead we could have written \begin{align*} y[n] &= x[n]h[0] + x[n-1]h[1] + x[n-2]h[2] + \cdots + x[0]h[n] + \cdots\\ &= \sum_{m=0}^{\infty} x[n-m]h[m], \end{align*} so that it is the input that seems "flipped over" or running backwards in time! In other words, it is human beings who flip the impulse response (or the input) over when computing the response at time $n$ using the convolution formula, but the system itself does nothing of the sort.

Here is a C/C++ example that shows that convolution can be done without using the impulse response in reverse. If you inspect the convolve_scatter() function, no variable is negated anywhere. This is scattering convolution where each input sample is scattered (summed) to multiple output samples in memory, using weights given by the impulse response. This is wasteful because the output samples will need to be read and written to several times.

Normally convolution is done as gathering convolution, as in convolve_gather(). In this method, each output sample is formed separately, by gathering (summing) to it input samples, with the reversed impulse response as the weights. The output sample resides in a processor's register used as an accumulator while this is done. This is normally the method of choice, because there will be only one memory write per each filtered sample. There are now more memory reads of the input, but only as many as there were memory reads of the output in the scattering method.

#include <stdio.h>

const int Nx = 5;
const int x[Nx] = {1, 0, 0, 0, 2};
const int Ny = 3;
const int y[Ny] = {1, 2, 3};
const int Nz = Nx+Ny-1;
int z[Nz];

void convolve_scatter() { // z = x conv y
for (int k = 0; k < Nz; k++) {
z[k] = 0;
}
for (int n = 0; n < Nx; n++) {
for (int m = 0; m < Ny; m++) {
z[n+m] += x[n]*y[m]; // No IR reversal
}
}
}

void convolve_gather() { // z = x conv y
for (int k = 0; k < Nz; k++) {
int accu = 0;
for (int m = 0; m < Ny; m++) {
int n = k+m - Ny + 1;
if (n >= 0 && n < Nx) {
accu += x[n]*y[Ny-m-1]; // IR reversed here
}
}
z[k] = accu;
}
}

void print() {
for (int k = 0; k < Nz; k++) {
printf("%d ", z[k]);
}
printf("\n");
}

int main() {
convolve_scatter();
print();
convolve_gather();
print();
}


It convolves the sequences:

1 0 0 0 2
1 2 3


and using both convolution methods outputs:

1 2 3 0 2 4 6


I can't imagine anyone using the scattering method, unless the filter is time-varying, in which case the two methods will produce different results and one may be more appropriate.

• Interesting! So what is final conclusion I am interested to see – Failed Scientist Aug 23 '17 at 15:22
• Your architectural concern is interesting. Considering the available caches, SIMD instructions (SSE, AVX) and multi core architectures, the scattered method seems more suitable for parallel computations? But I haven't performed a detailed analysis though... – Fat32 Aug 23 '17 at 19:35
• @Fat32 me neither! You mean accumulation in gathering convolution might become a bottleneck with multiple cores working on multiplications? That could be mitigated by giving each core its own accumulator and summing them at the end. I think this overhead would not be much compared to the additional memory writes in scattered convolution. – Olli Niemitalo Aug 23 '17 at 21:10
• Actually I was more concerned with the scattered form's efficiency than the gathering forms bottleneck.My current C filtering codes are ( most probably) in the gathering form, but when it comes to ASM codes I tend to write them in SIMD SSE extensions which are more suitable to scattered form. I have to update my tets, however :-))) Memory IO is definitely an issue compared to register accumulation. And probably I'm missing the penalty of repeated memory IO... – Fat32 Aug 23 '17 at 21:32
• Anyone know better words than scattering and gathering? I'm not sure if these are reserved for sparse convolution kernels. – Olli Niemitalo Aug 24 '17 at 5:47

It's only 'flipped' for pointwise computation.

@Dilip explains what the convolution integral/summation represents, but to explain why one of the two input functions (often h(t)) is flipped for computation purposes, consider a discrete-time system with input x[n] and impulse response h[n]:

• You could take your input function x[n], and for each non-zero* sample x[n] calculate the scaled impulse response from sample n and on until the time-shifted h[n] dies down to zero (assuming a causal h[n]). This would involve no 'flipping' (or more accurately 'time-reversal') of either x[n] or h[n]. However, at the end you would have to add/superimpose all these scaled+shifted 'echos' of the impulse response for each non-zero x[n].

• Or, for convenience you could time-reverse one of the functions about the time origin (usually 0), making your computation {multiply, add, multiply, add, ...} instead of {multiply, multiply, ..., add, add, ...}. This results in the same output signal because it will perform the exact same multiply and add operations. For example, think about the output contribution from a non-zero input signal at time 0 x[0]. When k = 0 for the equation $$\sum_{k=-\infty}^{\infty} x[k]h[n-k]$$ the impulse reponse h[n] will only be time-reversed but not shifted, giving us the first sample response for x[n], which is x[0]h[0]. Then, incrementing k by one will shift h[n] to the right one time step, such that the time-reversed h[n]s second entry (h[1]) will now be laying on top of x[0], waiting to be multiplied. This will yield the desired contribution x[0]h[1] at time n=1, just as would have been done in the previous method.

*I say non-zero x[n] because $$\forall x[n] = 0$$ the impulse response h[n] is scaled to zero, thus contributing nothing to the final output y[n].

• "You could take your input function x[n], and for each non-zero* sample x[n] calculate the scaled impulse response from sample n and on until the time-shifted h[n] dies down to zero (assuming a causal h[n])" Are the five $n$ that occur in this sentence all the same number or are they different? – Dilip Sarwate Jan 28 '13 at 4:21
• @Dilip. All n are the same, except for 'the time-shifted h[n]', which implies 'h[n-k]', where 'k' is a constant used to shift the impulse response to the desired point of signal x[n]. ie: h[n-2] for calculating response to signal at x[2]. – abc Feb 24 '13 at 17:41

At index c[n], the convolution of a[n] and b[n], is such that:

"c[n] is a summation of all products (a[k]b[m]) such that m+k=n," so m = n - k or k = n - m, which means that one of the sequences has to be flipped.

Now why does convolution behave this way in the first place? Because of its connection with multiplying polynomials.

Multiplying two polynomials results in a new polynomial with co-efficients. The co-efficients of the product polynomial define the operation of convolution. Now, in signal processing, transfer functions- Laplace transforms or z-transforms are these polynomials, with each co-efficient corresponding to a different time-delay. Matching the co-efficients of the product and the multiplicands results in the fact that 'multiplication in one representation corresponds to convolution in the transformed representation'.

During convolution, no "flip" of the impulse response needs to occur at all...

However, if you want to prevent any phase alteration, you can convolute a signal with an impulse response and then reverse the impulse response and re-convolute to cancel phase effects.

In offline processing, you could just as easily reverse the signal after the first convolution to get to the same conclusion (as the comments suggest).

• He's referring to the "time reversal" on the impulse response in the convolution integral: $y(t) = \int_{-\infty}^{\infty}x(\tau) h(t-\tau) d\tau$. As someone else already pointed out, you don't have to flip the impulse response $h(t)$; you can flip either term (i.e. $x(t) * h(t) = h(t) * x(t)$). I think he's trying to figure out what the qualitative interpretation of that "flip-and-slide" action is. – Jason R Nov 29 '12 at 0:55
• @JasonR Ah, whoops! Sometimes hard to see what the question is getting at. Izhak, once you understand the answer you were looking for, you will understand where I was going. Ignore me for now! – learnvst Nov 29 '12 at 3:08

Just write the convolution integral $$\int_{-\infty}^\infty f(\tau) g(t-\tau) d\tau$$ instead as a handwaving $$\iint\nolimits_{t_1+t_2 = t} f(t_1) \, g(t_2) \, dt_1\, dt_2$$ namely integrating the product of $f$ and $g$ over all argument pairs that sum to $t$.

Now the handwaving form clearly shows the symmetry involved here and that no "flipping" is involved. Converting this into a proper one-dimensional integral, however, requires making one of the two arguments the actual integration variable. It's either that or finding a rigid symmetric form not involving handwaving. The latter is trickier. Basically, you have to get a normalization back in, making for something (when using the Dirac delta function/distribution) like $$\iint_{t_1,t_2} f(t_1)\,g(t_2)\,\delta(t-t_1-t_2)\,dt_1\,dt_2$$ If you then rearrange in one way, you get $$\int_{t_1}f(t_1)\, dt_1\int_{t_2}g(t_2) \delta(t-t_1-t_2) \,dt_2$$ and from the sifting property of the Dirac operator $$\int_{t_1}f(t_1)\,dt_1\,g(t-t_1)$$ which is the original integral with a bit of renaming.