0
$\begingroup$

I am reading the Wiki for DFT. There is a part for circular convolution theorem which sounds a bit odd saying:

$$ \mathcal{F} \left \{ \mathbf{x\cdot y} \right \}_k \ \stackrel{\mathrm{def}}{=} \sum_{n=0}^{N-1} x_n \cdot y_n \cdot e^{-\frac{2\pi i}{N} k n} =\frac{1}{N} (\mathbf{X * Y_N})_k, \,$$   which is the circular convolution of $\mathbf{X}$ and $\mathbf{Y}$.

I feel it's incorrect because writing $y_n$ in Fourier basis, and multiplying it by $e^{-\frac{2\pi i}{N} k n}$ will result in a shift in index by $k$, and that means the result should be the cross-corrolation of two signals.

And secondly if either this or my argument is correct why this does not hold for continuous signals.

P.S. The question has been asked here as well since I was unaware of the most proper domain for my question.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by it doesn't hold for continuous signals? The Fourier transform of the multiplication of two signals is proportional to the convolution of the two Fourier transforms, also in continuous time. $\endgroup$ – Matt L. Jun 27 '14 at 14:48
  • $\begingroup$ My mistake, I am sorry. I just checked it. But what is wrong with my argumentation above? $\endgroup$ – Cupitor Jun 27 '14 at 14:51
1
$\begingroup$

I'm not sure I understand your argument, but here's a proof which should make the relationship clear:

$$IDFT\left\{\frac{1}{N}(X*Y_N)_k\right\}=\frac{1}{N^2}\sum_{k=0}^{N-1}(X*Y_N)_ke^{i2\pi nk/N}=\\ =\frac{1}{N^2}\sum_{k=0}^{N-1}\sum_{l=0}^{N-1}X_lY_{(k-l)_N}e^{i2\pi nk/N}= \frac{1}{N^2}\sum_{l=0}^{N-1}X_l\sum_{k=0}^{N-1}Y_{(k-l)_N}e^{i2\pi nk/N}=\\ \frac{1}{N^2}\sum_{l=0}^{N-1}X_le^{i2\pi nl/N}\sum_{k=0}^{N-1}Y_{(k-l)_N}e^{i2\pi n(k-l)/N}=\\=\frac{1}{N}\sum_{l=0}^{N-1}X_le^{i2\pi nl/N}\cdot\frac{1}{N}\sum_{k=0}^{N-1}Y_{k}e^{i2\pi nk/N}=x_ny_n$$

where $(k-l)_N$ means $(k-l)$ modulo $N$. I hope this helps.

$\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.