Why do the lengths of the sampled signals $x_1, \: x_2$ have to be $\text{length}(x_1)+\text{length}(x_2)-1$?

Question

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.

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?

Answer 1

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.

Answer 2

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.

Answer 3

Let $x_1[k]$ and $x_2[k]$ be two discrete time signals with respective lengths $N_1$ and $N_2$. Let $X_1[r]$ be the DFT of $x_1[k]$ and $X_2[r]$ be the DFT of $x_2[k]$. Then it holds that the circular convolution between $x_1[k]$ and $x_2[k]$ is equivalent to multiplying $X_1[r]$ and $X_2[r]$

$$ x_1[k] \circledast x_2[k] \Leftrightarrow X_1[r]X_2[r].$$

where circular convolution is defined for two $N_0$-periodic sequences as

$$x_1[k] \circledast x_2[k] = \sum_{n=0}^{N_0-1} x_1[n]x_2[k-n]. $$

So to perform the circular convolution, $x_1[k]$ and $x_2[k]$ must have the same length $N_0$ and assumed to be periodic. Achieving the same length can be done by appropriately zero-padding the signals.

Linear convolution is used to find the response of an LTI system to an input signal. If $x_1[k]$ is the input signal and $x_2[k]$ is the impulse response of a system then we can find the zero-state response as

$$y_{zs}[k] = x_1[k] \ast x_2[k] = \sum_{m=0}^{k} x_1[m]x_2[k-m] $$

where it assumed that $x_1[k]$ and $x_2[k]$ are causal.

Here comes the important part.

Circular convolution of $x_1[k]$ and $x_2[k]$ is equal to the linear convolution of $x_1[k]$ and $x_2[k]$ if $x_1[k]$ and $x_2[k]$ both have length of at least $N_1+N_2-1$.

It is for this reason that we zero-pad both $x_1[k]$ and $x_2[k]$ to the length $N_1+N_2-1$ when we want to find the zero-state response via multiplying the DFT's of. Because if we didn't do it, then multiplication of the DFT's and performing the IDFT would not yield the zero-state response but something else instead.

Answer 4

Convolution can be realized as a polynomial multiplication. A sequence of samples can be represented as a polynomial of order one less than the length of sequence, whereas, the coefficients of polynomial are the sample amplitudes of the sequence. When you multiply two polynomials the resultant is always sum of the length of each minus 1.

For example, consider sequence [1, 1] and [1 2 3]. We can represent them as: $x + 1$ and $x^2 + 2x + 3$. If we multiply the two polynomials, the result will be: $x^3 + 3x^2 + 5x + 3$. If you recall z-transform then actually x can be replaced with $z^{-1}$.