0
$\begingroup$

We know that convolution in time is equivalent to multiplication in frequency (Fourier). $$x_1(t) \ast x_2(t) \leftrightarrow X_1(\omega)X_2(\omega) \tag1$$ However, for a sampled signal, this property only holds if the frequency resolution $\Delta f = \frac{1}{T}$ for the sampled signals are the same, i.e. the signals have to have the same duration. This is illustrated below.

enter image description here

If the sampled signals $x_1(t)$ and $x_2(t)$ initially don't have the same duration, then we can zero pad the signals, such that they do. This is what is done in the lower graph pair and the samples now line up in the spectrum. Both $x_1(t)$ and $x_2(t)$ have been zero padded, such that they have a length of length(x1)+length(x2)-1 , which turns out to be the length of the convolution length(conv(x1,x2)) .

My question is, why does the length of the signals have to be the length of the convolution? If $x_1(t)$ is shorter than $x_2(t)$ why isn't it sufficient just to extend $x_1(t)$ to the length of $x_2(t)$? Then, both signals have the same length and the samples would still line up in the frequency spectrum, guaranteeing the property mentioned in (1), right?

$\endgroup$
3
$\begingroup$

Multiplication in the frequency domain is equivalent to circular convolution in the time domain with a period of NFFT. If you don't zero pad them to at least length(x1)+length(x2)-1 samples, the IFFT result would be aliased in the time domain. That's why overlap-save method discards part of the result.

$\endgroup$
9
  • $\begingroup$ Can you elaborate why we introduce aliasing if the length isn't at least length(x1)+length(x2)-1? $\endgroup$
    – Carl
    Sep 24 at 9:17
  • $\begingroup$ @Carl have a look at convolution theorem. $\endgroup$
    – ZR Han
    Sep 24 at 10:00
  • $\begingroup$ The link you provided does not help my understanding. $\endgroup$
    – Carl
    Sep 24 at 10:05
  • $\begingroup$ @Carl so what confuses you? $\endgroup$
    – ZR Han
    Sep 24 at 10:05
  • $\begingroup$ You state that if the length of the signal isn't at least: length(x1)+length(x2)-1 then the time signal will be aliased. I don't see where that's addressed in the link you provided. Could you point me to it? $\endgroup$
    – Carl
    Sep 24 at 10:12
2
$\begingroup$

Either someone didn't stress enough that there are four basic flavors of the Fourier Transform, or they did introduce that for you but you've forgotten.

For a sampled-time signal of infinite extent in time, you should use the DTFT (not to be confused with the discrete Fourier transform, of which the FFT is the fast version).

The DTFT is defined as $$X(\omega) = \sum_{n-=\infty}^\infty x_n e^{-i \omega n}. \tag2$$ Note the infinite sum, not the finite sum of the DFT. Note also the fact that the $\omega$ on the left hand side is continuous, but it repeats every $2 \pi$ radians (this is a property of the four flavors of Fourier transform -- if the domain of one side is sampled, then the domain of the other side repeats every $2 \pi$ radians; if the domain of one side is continuous, then the domain of the other side has infinite extent.)

If you use (2) in calculating (1), then there's no adjustment needed -- things just work. Technically, this is the "proper" way to do it, but it's not amenable to doing things numerically.

When you use the DFT, then (1) holds, but with the wrinkle that $\mathbf x$ must now be a finite vector, and the convolution is now circular -- meaning that instead of defining $$x_1(k) * x_2(\kappa) = \sum_{\kappa = -\infty}^\infty x_1(k - \kappa) x_2(\kappa) \tag3$$ you have $$x_1(k) * x_2(\kappa) = \sum_{\kappa = 0}^{N-1} x_1((k - \kappa) \mod N) x_2(\kappa) \tag 4$$

The problem with (4) is that because of the modulo on $k - \kappa$, if the result would have been longer than $N$, you end up with a result as long as $N$, but with it's tail added into its head.

If you're going to use the FFT to speed up the convolution, then the only way to avoid that is to pad out $x_1$ and $x_2$ so that the inverse FFT is at least as long as the expected result of the convolution.

$\endgroup$

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.