0
$\begingroup$

I am studying Discrete Fourier Transform currently and I have a doubt in that. Consider two sequences {1,2,3,4} and {0,1,0,0}. When I convolve them linearly, I get this {0,1,2,3,4,0,0}. However, if I take the 4 pt DFTs of {1,2,3,4} and {0,1,0,0} and then multiply them, and after that if I take IDFT of the result, I get this {4, 1, 2, 3}.

$$DFT({1,2,3,4}) = {10, -2+2j, -2, -2-2j}$$ $$DFT({0,1,0,0}) = {1, -j, -1, j}$$

Element wise product = $${10, 2+2j, 2, 2-2j}$$ $$IDFT({10, 2+2j, 2, 2-2j}) = {4, 1, 2, 3}$$

I know that the output of linear convolution here would need atleast 7 elements and I am calculating the 4 pt. DFT/IDFT which of course would not be enough. But what inference should I take from this. The result of IDFT looks somewhat like circular convolution but it is not exactly the result that you would get even after circular convolution.

$\endgroup$
3
$\begingroup$

The result {4,1,2,3} is the circular convolution of {1,2,3,4} and {0,1,0,0} which you correctly get by taking the inverse DFT of the product of the DFTs of the two sequences.

We can check this by doing the circular convolution the long way via matrix multiplication as follows:

$x(n) = [1,2,3,4]$

$y(n) = [0,1,0,0]$

To solve for the circular convolution $x(n) (*) y(n)$, (where I use $(*)$ to denote circular connvolution) we can do that with multiplication as $Xy$, where $X$ is a matrix formed by repeating $x(n)$ in each column with a circular rotation of shift n with n = 0,1,2,3 and $y$ is $y(n)$ as a column vector:

$$ Xy =\begin{bmatrix} 1 & 4 & 3 &2 \\ 2 & 1 & 4 & 3 \\ 3 & 2 & 1 & 4 \\ 4 & 3 & 2 & 1 \\ \end{bmatrix} \begin{bmatrix}0 \\ 1 \\ 0 \\ 0 \end{bmatrix} = [4,1,2,3]$$

Confirming the relatinship:

$$x[n](*)y[n] = IFFT(FFT(a)FFT(b))$$

Where the ($*$) operator here is specifically circular convolution. And the multiplication of the two FFT results is the element by element product.

Also to add to this: In comparison, if you instead conjugate one of the FFT results prior to multiplication as follows, the result is a circular cross-correlation of the two sequences!

$$XCORR = IFFT(FFT(a)FFT(b)^*)$$

$\endgroup$
  • $\begingroup$ So, its just that whenever we take a N point DFT where N < output length, we get a circular convolution? $\endgroup$ – Himanshu Sharma Sep 30 '18 at 2:14
  • $\begingroup$ I am not sure what you mean by “output length”, output of what? $\endgroup$ – Dan Boschen Sep 30 '18 at 2:15
  • $\begingroup$ Output length here is 7. len(x(n)) + len(y(n)) - 1. $\endgroup$ – Himanshu Sharma Sep 30 '18 at 2:15
  • $\begingroup$ That is the length of a regular convolution, but the point is whenever you do IFFT(FFT(a)FFT(b)) you get circular convolution where a and b must be padded to the same length to do that. There are no further conditions. The regular convolution has a length of len(a)+len(b) -1. $\endgroup$ – Dan Boschen Sep 30 '18 at 2:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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