MATLAB Answers

IFFT of Convolution equivalence

6 views (last 30 days)
JOB
JOB on 18 Dec 2019
Commented: JOB on 19 Dec 2019
I was trying out the equation IFFT(x*y) = IFFT(x).IFFT(y), where both 'x' and 'y' are complex numbers. The 'x' and 'y' are 1x8 matrices. The result was different for both sides of the equation. However i was able to prove that x*y = IFFT[ FFT(x).FFT(y)] and FFT(x*y)=FFT(x).FFT(y). What did I miss out when I tried to solve the IFFT relation? Please let me know of any source that has helpful content regarding this relationship

  0 Comments

Sign in to comment.

Accepted Answer

Ridwan Alam
Ridwan Alam on 18 Dec 2019
Edited: Ridwan Alam on 18 Dec 2019
Sorry for the confusion. Here is what I tried:
a1 = randi(50,8,1);
b1 = randi(50,8,1);
x = complex(a1,b1)
a2 = randi(50,8,1);
b2 = randi(50,8,1);
y = complex(a2,b2)
xifft = ifft(x)
yifft = ifft(y)
mifft = xifft.*yifft
z = cconv(x,y,length(x))
zifft = ifft(z)./length(z)
% zifft-mifft is almost zero
Summary: you need circular convolution in frequency domain instead of linear convulation.
More details:

  2 Comments

JOB
JOB on 18 Dec 2019
Thanks again, I equated it by using linear convolution with zero padding.
Ridwan Alam
Ridwan Alam on 18 Dec 2019
sure. glad to help.

Sign in to comment.

More Answers (1)

David Goodmanson
David Goodmanson on 18 Dec 2019
Edited: David Goodmanson on 19 Dec 2019
Hi JOB/Ridwan
Here is a small example where a and b are padded with zeros, so that regular convolution can be compared with convolution by fft and ifft. (The zeros ensure that for fft and ifft, which do circular convolution, the nonzero parts can't overlap by going 'the other way around the circle.'
a = [(1:3)+i*(2:4) zeros(1,4)]
b = [(3:5)+i*(4:6) zeros(1,4)]
n = length(a)
convab = conv(a,b)
convab1 = ifft(fft(a).*fft(b))
convab2 = n*fft(ifft(a).*ifft(b))
All of these results agree (not counting that the conv result is a longer vector and contains more zeros than the other two). For the convab2 result you have to multiply by an extra factor of n. This is because the Matlab ifft algorithm contains an overall factor of (1/n) and the fft does not.

  3 Comments

Ridwan Alam
Ridwan Alam on 18 Dec 2019
Hey David,
Thanks for the example. I agree, the circular convolution is the issue here.
I believe what JOB is trying to show is that:
z = ifft(convab);
m = ifft(a).*ifft(b);
But m is not equal to z, not even to z/length(a).
David Goodmanson
David Goodmanson on 19 Dec 2019
HI Ridwan,
what you say is true, but it's because a &b have different length than convab. One could do a circular convolution of a and b by a method other than ifft and then compare, but this example just pads out a and b to simulate a linear convolution as before, then pads them out again to be the same length as convab:
a = [(1:3)+i*(2:4) zeros(1,4)];
b = [(3:5)+i*(4:6) zeros(1,4)];
n = length(a);
convab = conv(a,b)
nconvab = length(convab);
apad = [a zeros(1,nconvab-n)]
bpad = [b zeros(1,nconvab-n)]
% the following two expressions are the same
ifft(convab)
nconvab*ifft(apad).*ifft(bpad)
JOB
JOB on 19 Dec 2019
Thanks for the lucid explanation.

Sign in to comment.

Sign in to answer this question.


Translated by