Linear and Circular Convolution in Fourier Domain (DFT)

Question

Suppose we have two vectors A and B of length 100 and 80 obtained as a function of time. If we wish to perform convolution of the two vectors in the Fourier domain, we need to multiply the Fourier transforms of A and B. For that purpose, the length of B must be the same as A. The output would be of the same length as A or B after zero padding.

1. Where should we do zero padding in B, should this be at the beginning of B or at the end of B?

2. I was reading that convolution achieved via FFT is essentially a circular one. If our desire is to get a linear convolution, how do we ensure that the output is a linear convolution, i.e., how many end points should be rejected from both ends after inverse FFT?

Answer 1

Lot of good comments and a nice answer but still I felt OP's question may have gone unanswered.

A is length 100 sequence, B is length 80 sequence. So conv(A,B) linear convolution operation results in a 179 length sequence. The important thing to keep in mind is that the resulting sequence is 179 length.

Now, coming to DFT of these sequences (remember FFT is just one among many ways to implement Discrete Fourier Transform, DFT but I am using these 2 terms interchangeably here), DFT assumes that the underlying sequence is periodic, so multiplication of DFT of 2 sequences is periodic convolution (aka circular convolution) of these 2 sequences. Since A and B have 2 different lengths, we will take the higher length as DFT size and multiply their DFTs. So what we will do is to zero-pad B with 20 zeros to match length of B. For now, I will add the zeros at the end (I will answer later what will happen if we add in the beginning).

So now we have 2 100-point sequences, whose multiplication of DFT and its inverse-DFT results in a 100-point sequence which is the circular convolution of A and B. Remember, the linear convolution output was 179 points. Here we have taken 100-point inverse DFT. So this will result in aliasing in time domain. It is like making infinite copies of 179-point sequences and overlapping them with interval of 100. Sample at 178 (last sample) will alias with sample at 178-100 = 78. Similarly, sample at 100 will alias with sample at 0 (100-100 = 0). So in the resulting 100 point sequence, first 79 points will be incorrect. Only samples from 79 to 99 will be correct. Not to speak of samples 100 to 178 which we have lost.

That is why in other answer, we took 179 point FFT. This is how we ensure the resulting circulation convolution is equivalent to linear convolution. Here both the sequences are 179 point, resulting sequence after IFFT is 179 point. But most of the values are zeros in the 357-point linear convolution. Only the first 179 points (samples from 0 to 178) are non-zero (rest are all zeros till 356). So the sample at 179 will overlap with sample at 0 (179-179) but we know that sample at 179 is zero hence it has no effect. So we are safe if FFT length is more than or equal to 179.

To answer, the first question, if we had added zeros in the beginning, it is like delaying the sequence by 20 samples. This will result in an equivalent delay in the output (remember these are LTI operation - so delay in the input will result in equivalent delay in output). But now your sequence will be 100-point sequence (not 80-point because you have added zeros in the beginning). So you need to change your computations accordingly.

All the above knowledge have been made possible thanks to chapter 8 in Alan Oppenheim's book (Discrete Time Signal Processing).

Answer 2

the following matlab/octave code gives the linear convolution result using frequency domain :

A = ((-1).^[0:79]').*hamming(80);    % input one
B = blackman(100);   % input two

C1 = conv(A,B);     % A * B (convolution) in time domain
C2 = real( ifft( fft(A,179).*fft(B,179) ) ); % convolution using freq domain

The output will be identical of length 179 samples:

Answer 3

Here's an answer from me in a video form: Circular vs. Linear Convolution on YouTube

and a blog post: Circular vs. Linear Convolution on TheWolfSound.com