Example of using FFT to convolve two functions:
First show ordinary (non-FFT) convolution:
octave:2> a=[1 2 3]
a =
1 2 3
octave:3> b=[4 5 9]
b =
4 5 9
octave:4> c=conv(a,b)
c =
4 13 31 33 27
Now show how we can use FFT to get same result:
octave:5> A=fft([a 0 0])
A =
Columns 1 through 3:
6.00000 + 0.00000i -0.80902 - 3.66547i 0.30902 + 1.67760i
Columns 4 and 5:
0.30902 - 1.67760i -0.80902 + 3.66547i
octave:6> B=fft([b 0 0])
B =
Columns 1 through 3:
18.0000 + 0.0000i -1.7361 - 10.0453i 2.7361 + 5.6206i
Columns 4 and 5:
2.7361 - 5.6206i -1.7361 + 10.0453i
octave:7> ifft(A.*B)
ans =
4.0000 13.0000 31.0000 33.0000 27.0000