# Circular Convolution Formula Deduction from DFT

I am trying to get to the circular convolution formula from the product of the DFT of two input signals. I came across this webpage, which contains the following.

Could someone help me to solve that equation?

I have something like this

$$x_3(n) = \frac{1}{N} \sum^{N-1}_{k=0} \exp{\left [ \frac{j 2 \pi k n}{N} \right ]} \left [ \sum^{N-1}_{m=0} x_1(m) \exp{\left [ \frac{-j 2 \pi k m}{N} \right ]} \right ] \left [ \sum^{N-1}_{m=0} x_2(m) \exp{\left [ \frac{-j 2 \pi k m}{N} \right ]} \right ]$$

I am not sure what is next. The following doesn't seem to be right.

\begin{aligned} x_3(n) &= \frac{1}{N} \sum^{N-1}_{k=0} \left [ \sum^{N-1}_{m=0} x_1(m) \exp{\left [ \frac{-j 2 \pi k m}{N} \right ] \exp{\left [ \frac{j 2 \pi k n}{N} \right ]}} \right ] \left [ \sum^{N-1}_{m=0} x_2(m) \exp{\left [ \frac{-j 2 \pi k m}{N} \right ]} \right ]\\ \\ &= \frac{1}{N} \sum^{N-1}_{k=0} \left [ \sum^{N-1}_{m=0} x_1(m) \exp{\left [ \frac{-j 2 \pi k (m-n)}{N} \right ]} \right ] \left [ \sum^{N-1}_{m=0} x_2(m) \exp{\left [ \frac{-j 2 \pi k m}{N} \right ]} \right ]\\ \end{aligned}

## 1 Answer

Let $$x$$ and $$y$$ be signals of $$N$$ samples each, numbered as $$x(0),\ldots,x(N-1)$$. Then their DFTs are $$X$$ and $$Y$$, which also have $$N$$ entries each: $$\begin{eqnarray} X(k) &=& \sum_{n=0}^{N-1}x(n)e^{-2\pi i kn/N},\\ Y(k) &=& \sum_{m=0}^{N-1}y(m)e^{-2\pi i k m/N}, \end{eqnarray}$$ where the indices run from $$0$$ to $$N-1$$.

The $$k^{\textrm{th}}$$ entry of the entry-by-entry product of $$X$$ and $$Y$$ is $$$$\begin{split} X(k)Y(k) ~=& \left(\sum_{n=0}^{N-1}x(n)e^{-2\pi i kn/N}\right)\left(\sum_{m=0}^{N-1}y(m)e^{-2\pi i k m/N}\right)\\ ~=& \sum_{n=0}^{N-1}\sum_{m=0}^{N-1}x(n)y(m)e^{-2\pi i k(n+m)/N} \end{split}$$$$

Now we consider the $$\ell^{\textrm{th}}$$ entry of the IDFT of this entry-by-entry product: $$$$\begin{split} \mathsf{IDFT}(XY)(\ell) ~=& \frac{1}{N}\sum_{k=0}^{N-1}X(k)Y(k)e^{2\pi i\ell k/N }\\ ~=& \frac{1}{N}\sum_{k=0}^{N-1}\left[\sum_{n=0}^{N-1}\sum_{m=0}^{N-1}x(n)y(m)e^{-2\pi i k(n+m)/N}\right]e^{2\pi i\ell k/N }\\ ~=& \frac{1}{N}\sum_{n=0}^{N-1}\sum_{m=0}^{N-1}x(n)y(m)\sum_{k=0}^{N-1}e^{-2\pi i k(n+m-\ell)/N} \end{split}$$$$ The sum over $$k$$ is equal to 0 unless $$$$n+m-\ell=0~\textrm{mod}~N~~~(m=\ell-n~\textrm{mod}~N),$$$$ in which case it is equal to $$N$$: $$$$\sum_{k=0}^{N-1}e^{-2\pi i k(n+m-\ell)/N} = N\delta_{m,\ell-n~\textrm{mod}~N},$$$$ where $$\delta_{a,b}$$ is the Kronecker delta. One intuitive way to see this is to see that

$$\bullet$$ if the exponent is not 0, we are adding all $$N$$ of the $$N^{\textrm{th}}$$ roots of unity (view them in the complex plane), which will cancel one another out when added; As noted by the OP, my struck-through claim is true for all $$n$$, $$m$$, and $$\ell$$ only if $$N$$ is prime. The correct proof is to note that if $$e^{-2\pi i(n+m-\ell)/N}\neq 1$$, then $$$$\begin{split} \sum_{k=0}^{N-1}e^{-2\pi i k(n+m-\ell)/N} &=~ \sum_{k=0}^{N-1}\left(e^{-2\pi i (n+m-\ell)/N}\right)^k\\ &=~\frac{ 1- \left(e^{-2\pi i (n+m-\ell)/N}\right)^N}{1 - e^{-2\pi i (n+m-\ell)/N}}\\ &=~\frac{ 1- e^{N\times(-2\pi i (n+m-\ell)/N)}}{1 - e^{-2\pi i (n+m-\ell)/N}}\\ &=~\frac{ 1- e^{-2\pi i (n+m-\ell)}}{1 - e^{-2\pi i (n+m-\ell)/N}}\\ &=~\frac{ 1- 1}{1 - e^{-2\pi i (n+m-\ell)/N}} ~~=~~ 0. \end{split}$$$$

$$\bullet$$ if the exponent is 0, then we are adding 1 $$N$$ times.

(Another not as intuitive away can be found in this video.)

So far, we have $$$$\begin{split} \mathsf{IDFT}(XY)(\ell) ~=& \frac{1}{N}\sum_{n=0}^{N-1}\sum_{m=0}^{N-1}x(n)y(m)N\delta_{m,\ell-n~\textrm{mod}~N}\\ ~=& \sum_{n=0}^{N-1}\sum_{m=0}^{N-1}x(n)y(m)\delta_{m,\ell-n~\textrm{mod}~N} \end{split}$$$$ When we perform the sum over $$m$$, the only nonzero term is the one for which $$m=\ell-n~\textrm{mod}~N$$, so $$$$\begin{split} \mathsf{IDFT}(XY)(\ell) ~=& \sum_{n=0}^{N-1}x(n)y(\ell -n~\textrm{mod}~N). \end{split}$$$$ The expression on the right-hand side is the $$\ell^{\textrm{th}}$$ entry of the circular convolution of $$x$$ and $$y$$. $$$$\mathsf{IDFT}(XY)(\ell) = (x\circledast y)(\ell),$$$$ so $$\mathsf{IDFT}(XY) = x\circledast y$$.

• This answer also reminded me of how the product of two sums can be nested. Wow. It is a very thorough answer, thank you a lot. May 12 '20 at 20:36
• Can you expand on this? if the exponent is not 0, we are adding all 𝑁 of the 𝑁th roots of unity (view them in the complex plane), which will cancel one another out when added; I am still trying to visualize it. May 13 '20 at 15:10
• The complex numbers 1, exp(-2πi/N), exp(-2πi 2/N),..., exp(-2πi (N-1)/N) are the Nth roots of unity, and, when viewed as vectors in the complex plane, they are N equally-spaced (in terms of angles between them) unit vectors anchored at the origin. By the symmetry of their directions and sizes, they cancel out one another when they are all added together. For N = 2, for example, the roots of unity are 1 and -1, which clearly cancel each other out. May 13 '20 at 20:45
• I understand what you said by $$\sum_{k=0}^{N-2} e^{\frac{-j2\pi k n}{N}} = 0$$. But then, what you said above on the answer is a bit different, since you are multiplying the exponential by an integer, which could be multiple anything. For multiples of N, it is clear for me that the result will be one, but what is not clear is how the result would be zero otherwise. I could visualize yet how multiples of $2\pi / N$ could still be rotated and yield zero. May 13 '20 at 20:56
• I finally your concern exactly, and it is valid. A better explanation than mine is to use the fact that if the number w is not 1, then 1 + w + w^2 + ... + w^(N-1) = (1 - w^N)/(1 - w). In your case, w = exp(-2πic/N), where c is as you defined. Then the numerator is 1 - w^N = 1 - exp(N×(-2πic/N)) = 1 - 1 = 0. May 14 '20 at 17:23