Flipping the impulse response in convolution

Question

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

Answer 1

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 $$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.

Answer 2

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'.

Answer 3

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.

Answer 4

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].

Answer 5

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.

Answer 6

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).