linear convolution
Table of Contents
A linear convolution is the sum of the product of two sequences after one is reversed and progressively shifted.
(f[n]∗g[n])=∑(k=−∞)(∞)f[x]g[n−k]
Here, we are basically assuming that each signal is infinitely padded with zeros.
This operation commutes.
For example, (123)∗(45)=((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.