Suppose we have been given the circular convolution of two sequences and we want to find the linear convolution without knowing the sequences. How can we find it from the result of circular convolution?
If the sequences are not padded with (a sufficient number of) zeros you cannot retrieve the linear convolution. If the sequences are padded with zeros the linear convolution is identical to (a part of) the circular convolution. This property is used to calculate the linear convolution more efficiently, by calculating he circular convolution, which in turn can be calculated very efficiently in the frequency domain using the FFT algorithm.
If the sequences are not padded with (a sufficient number of) zeros you cannot retrieve the linear convolution. If the sequences are padded with zeros the linear convolution is identical to (a part of) the circular convolution. This property is used to calculate the linear convolution more efficiently, by calculating he circular convolution, which in turn can be calculated very efficiently in the frequency domain using the FFT algorithm.
Just an addition for the sake of completeness: Instead of padding with zeros you may as well pad with something else, as long as you know it (it's deterministic). A common alternative would be the cyclic prefix (artificially periodify) used in OFDM. Keywords to look for are Overlapp-Add and Overlap-Save.
you can use period of (N+1) samples. In this case the result of circular convolutiion = result of linear convolution. the zeros padding is another way to get the same result.
Suppose two sequences are x1(n) of lenght L and other sequences x2(n) of lenght M then addind the of (L+M-1) number of zeros in both sequences by zero padding method. now find circular convolutiion = linear convolution. [circular convolutiion as a Linear Transformation concept]
I know when the result of Linear Convolution is equal to circular convolution. My question was about getting linear convolution from result of circular convolution.
The result of Linear convolution is perfectly match the result of circular convolution.
You can't. The result is already aliased. If you are lucky enough that the resulting convolution leaves behind a trace of what the kernel looked like, you can try deconvolution, and reconvolve with the same kernel after padding.
- Badges
- Science topic