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!
Answer
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.
No comments:
Post a Comment