Point-product with fft

Question

According to the convolution theorem, a convolution in the time domain is a product in the fft domain. With correct zero-padding, it works:

% convolution in time domain
a = [1 2 3];
b = [4 5 6];
c = conv(a,b);

a_padded=[a 0 0]; b_padded=[b 0 0];
c_bis=ifft(fft(a_padded).*fft(b_padded));
% we do find c_bis=c

However, this theorem is suposed to work the other way around as well, a product in the time domain is a convolution in the fft domain. I dont get this part:

d = a.*b;
D=conv(fft(a_padded),fft(b_padded));
d_bis=ifft(D);

Which gives a complex vector for d_bis. How could one inverse a point-wise product made in the time domain using a convolution in the frequency domain ?

Answer 1

Interesting question!

The mistake (although a subtle one) is when you say

A product in the time domain is a convolution in the FFT domain

That's true with Fourier transforms. With Discrete Fourier transforms (DFT, or FFT), the correct formulation is

A product in the time domain is a circular convolution in the FFT domain, divided by the sequence length

So you have to change this in your d_bis computation:

• use circular convolution, not convolution;
• divide by the sequence length;
• don't apply padding.

If you have the Signal Processing toolbox you can use cconv to compute the circular convolution:

N = length(a);
D = cconv(fft(a),fft(b), N)/N;
d_bis=ifft(D); %// now this equals d

---

To make sure, the correct formulation in the first case (convolution in time domain gives product in frequency domain) also involves circular convolution:

A circular convolution in the time domain is a product in the FFT domain

(no dividing by sequence length in this case)

But since you padded with zeros in the time domain, the difference between normal and circular convolution disappears and you get the correct result. Without padding, it would be:

c = cconv(a, b, N);
c_bis=ifft(fft(a).*fft(b)); %// this equals c