Convolution using Fourier Transform

Question

I think I get wrong result with a very simple example, so please help me point out what my mistake is:

I want to con-volute [1,1] with [1,1], so the correct result would be [1,2,1].

Now I do it using Fourier transform, [1,1] would become [2,0]. [2,0] point.wise.multiplies.with [2,0] would be [4,0], then inverse fft [4,0] and finally get [2,2]. Why didn't I get correct result?

You should note that convolution via the Fourier domain results in "circular convolution", not normal convolution. That is, unless you've taken proper steps to correctly pad your input/output arrays... — twalberg

hotpaw2 hotpaw2 · Accepted Answer · 2014-04-16T22:17:22

For a linear fast convolution, you need to zero pad both your input vectors and use a longer FFT (of a length at least the sum of the two input vector lengths - 1), so that the circular convolution results don't wrap around an mix up the result.

Convolution using Fourier Transform

1 Answers