linear convolution

Table of Contents

A linear convolution is the sum of the product of two sequences after one is reversed and progressively shifted.

\begin{equation} (f[n] * g[n]) = \sum_(k = -\infty)(\infty) f[x]g[n-k] \end{equation}

Here, we are basically assuming that each signal is infinitely padded with zeros.

This operation commutes.

For example, \[ (1 2 3) * (4 5) = ((3*4) (2*4 + 3*5) (1*4 + 2*5) (1*5)) \]

The most important use of the linear convolution is to compute the output of a linear time invariant system.

It is possible to compute the linear convolution fast using the FFT. We need to pad each sequence to (at least) length \(N+M-1\) with zeros at the end. This basically removes the overlap in the circular convolution.

This number is relevant because its the output length of a lin. conv. between signals of length n, m.

1. Further reading:

Back to index