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.