5
$\begingroup$

My question is about the number of data points when doing a convolution (or correlation) in the the time or frequency domain. let's say we have two signals, $a(t)$ and $b(t)$ each of length $16$. When we do the convolution as follows:

$$c(t) =a(t)\star b(t)$$

$c(t)$ consists of $31$ points, right? Now if we transform these into $A(f) = \mathrm{FFT}(a(t))$ and $B(f) = \mathrm{FFT}(b(t))$, $A(f)$ and $B(f)$ each consist of $16$ points still, were the first half is a mirror of the second half. The convolution is just a multiplication in the frequency domain:

$$C(f) = A(f)\cdot B(f)$$

I believe $C(f)$ should be $16$ points. I'm fine with that much, but if we transform $C(f)$ back to the time domain, doesn't $c(t)$ end up having $16$ points?

I'm sure I'm just not thinking correctly about this. Thanks for any clarification!

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
7
$\begingroup$

Normally, the variables $t$ and $f$ are used for continuous time and frequency. But from your question I understand that you're talking about discrete time and frequency, and their relation via the Discrete Fourier Transform (DFT).

If you have discrete-time sequences $a[n]$ and $b[n]$ and their DFTs $A[k]$ and $B[k]$, then the DFT of the linear convolution $c[n]=a[n]\star b[n]$ is NOT equal to $A[k]\cdot B[k]$. The product of the DFTs corresponds to circular (or cyclic) convolution in the time domain.

The linear convolution of two $16$-point sequences has indeed $2\cdot 16-1=31$ points, whereas the circular convolution of two $16$-point sequences also has $16$ points.

Improve this answer
$\endgroup$
2
  • $\begingroup$ ahh, okay I think I see my confusion now. So if we would have stayed in continuous, then multiplication of the DTFT would have given given us the same result as the convolution in the time domain (after taking the inverse DTFT of course). Does that sound correct? Also, circular convolution in the time domain would have given me the same result of multiplication of the DFT for my original question, right? $\endgroup$
    – gerrgheiser
    Feb 25, 2016 at 14:06
  • $\begingroup$ @gerrgheiser: Yes, that's right. With the FT and DTFT (i.e. continuous frequency variable) everything would be fine. $\endgroup$
    – Matt L.
    Feb 25, 2016 at 15:05
2
$\begingroup$

If you want to do linear convolution in the frequency domain, first you would zero-pad your length 16 sequences to 31 or 32 long, then do the FFT, multiply, IFFT, to end up with your 31 point result (plus perhaps one extra in the more efficient 32 point case).

Otherwise, circular convolution would munge the 15 more results of the 31 in with the first 16 results, making a mess (unless you wanted a circular convolution).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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