2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Re 2.: google "fast convolution"; more material out there than we could sensibly reproduce as an answer here. Re: 1. I think you can deduct the difference between these two pretty well: Consider padding at begging is exactly the same signal as padding at end, just circularly shifted. Now, a circular shift in time domains is equivalent to what in frequency domain? $\endgroup$ – Marcus Müller Mar 9 at 13:37
  • 2
    $\begingroup$ Read up on Overlap Add Convolution or Overlap Save Convolution $\endgroup$ – Hilmar Mar 9 at 13:43
  • $\begingroup$ @MarcusMüller, circular shift in time domain should cause a phase shift in frequency domain. Do you know a good book which covers this for self-learning? I am a chemist who just got recently interested in it. $\endgroup$ – M. Farooq Mar 9 at 13:50
  • 2
    $\begingroup$ @M.Farooq I must admit I enjoyed "Discrete-Time Signal Processing" by Oppenheim. Not everyone does. I was brought up with the Book "Signale und Systeme" by Jäkel + (Kiencke || Puente). $\endgroup$ – Marcus Müller Mar 9 at 13:55
  • 2
    $\begingroup$ @M.Farooq Discrete-Time Signal Processing - Oppenheim or Digital Signal Processing - Proakis are really good classical books $\endgroup$ – jomegaA Mar 9 at 14:01
1
$\begingroup$

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.

enter image description here 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).

| improve this answer | |
$\endgroup$
1
$\begingroup$

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:

enter image description here

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, I am still trying to find out that convolution by FFT is a circular one, so how do we ensure that the output is a linear convolution, because the "ends" of linear vs. circular convolutions would be different. $\endgroup$ – M. Farooq Mar 9 at 23:08
  • 1
    $\begingroup$ Look at the FFT length ;-) ( I also have detailed answers for circular convolution linear convolution and fft) $\endgroup$ – Fat32 Mar 10 at 0:08
  • 1
    $\begingroup$ I will check your other answers. Right, it is a linear convolution: 80+100-1=179. $\endgroup$ – M. Farooq Mar 10 at 0:57
  • $\begingroup$ Basically the C2 is the faster version of C1, otherwise known as linear fast-convolution. $\endgroup$ – jomegaA Mar 11 at 9:01
  • $\begingroup$ Before performing C2, A and B can be padded with zeros bringing the total length of A and B to 179 and perform C2 = real( ifft( fft(A).*fft(B) ) ); % convolution using freq domain $\endgroup$ – jomegaA Mar 11 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.