I am studying Discrete Fourier Transform currently and I have a doubt in that.

Consider two sequences $$\left\{1,2,3,4\right\}$$ and $$\left\{0,1,0,0\right\}$$ When I convolve them linearly, I get this $$\left\{0,1,2,3,4,0,0\right\}$$

However, if I take the 4 point DFT 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\}$$

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

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

I know that the output of linear convolution here would need at least 7 elements and I am calculating the 4 point 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.


1 Answer 1


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)^*)$$

  • $\begingroup$ So, its just that whenever we take a N point DFT where N < output length, we get a circular convolution? $\endgroup$ Sep 30, 2018 at 2:14
  • $\begingroup$ I am not sure what you mean by “output length”, output of what? $\endgroup$ Sep 30, 2018 at 2:15
  • $\begingroup$ Output length here is 7. len(x(n)) + len(y(n)) - 1. $\endgroup$ Sep 30, 2018 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$ Sep 30, 2018 at 2:19
  • $\begingroup$ @DanBoschen How to fasten up the linear (regular) convolution? I presume OP is bit confused with fast convolution and circular convolution. $\endgroup$
    – jomegaA
    Mar 11, 2020 at 8:48

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.