Comparison of Linear Convolution and N Point DFT

Question

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.

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